Языки и исчисления: Информация

Форма обучения:
дистанционная
Стоимость самостоятельного обучения:
бесплатно
Доступ:
свободный
Документ об окончании:
 
Уровень:
Специалист
Длительность:
25:56:00
Студентов:
635
Выпускников:
29
Качество курса:
4.60 | 4.30
В курсе рассказывается об основных понятиях математической логики (логика высказываний, языки первого порядка, выразимость, исчисление высказываний, разрешимые теории, теорема о полноте, начала теории моделей).
Курс включает в себя около 200 задач различной трудности.
Специальности: Программист
 

План занятий

Занятие
Заголовок <<
Дата изучения
Лекция 1
1 час 19 минут
Логика высказываний
Рассматриваются основные понятия алгебры логики (аксиомы, формулы, эквивалентность, вывод, разбор формул, полнота связок и другие)
-
Тест 1
21 минута
-
Лекция 2
1 час 40 минут
Схемы из функциональных элементов
Рассматриваются базовые логические схемы, наборы схем, вопросы их полноты, сложность булевой функции относительно базовых наборов схем, теоремы оценки сложности
-
Тест 2
24 минуты
-
Лекция 3
1 час 19 минут
Исчисление высказываний
Рассматриваются аксиомы исчисления высказываний, правила вывода, выводимость, критерии обращения формул в теоремы, тавтологии
-
Тест 3
24 минуты
-
Лекция 4
1 час 48 минут
Контрпример
Рассматриваются исчисление секвенции, вопросы корректности и полноты исчисления секвенции
-
Тест 4
24 минуты
-
Лекция 5
1 час 3 минуты
Языки первого порядка
Рассматриваются языки первого порядка, вопросы определения сигнатуры таких языков, их интерпретации, выяснения истинности формул над такими языками
-
Тест 5
24 минуты
-
Лекция 6
1 час 30 минут
Выразимость в арифметике
Рассматриваются арифметические предикаты (формулы, определенные на сигнатуре с арифметическими операциями типа сложения и умножения), вопросы арифметичности произвольных предикатов
-
Тест 6
24 минуты
-
Лекция 7
1 час 47 минут
Арифметика Пресбургера
Рассматриваются вопросы выразимости множеств для сигнатуры вида {=, <, +, 0, 1} и носителя Z, критерии существования бескванторных эквивалентных формул, вопросы элементарной эквивалентности
-
Тест 7
24 минуты
-
Игра Эренфойхта и понижение мощности
Рассматриваются критерии элементарной эквивалентности двух интерпретации одной сигнатуры в терминах игры двух игроков (двух интерпретации)
-
Тест 8
24 минуты
-
Лекция 9
1 час 8 минут
Исчисление предикатов
Рассматривается исчисление, аналогичное исчислению высказываний, для формул первого порядка, аксиомы, правила вывода, области действия формул, вопросы корректности
-
Тест 9
24 минуты
-
Лекция 10
1 час 42 минуты
Полнота исчисления предикатов
Рассматриваются вопросы непротиворечивости теории, совместных множеств замкнутых формул, а также полноты непротиворечивых теории
-
Тест 10
24 минуты
-
Лекция 11
47 минут
Теорема Эрбрана
Рассматривается теорема Эрбрана и следствия из неё, а также примеры приложений
-
Тест 11
24 минуты
-
Лекция 13
1 час 25 минут
Диаграммы
Рассматриваются вопросы существования расширений интерпретации, являющиеся нормальной моделью теории с равенством
-
Тест 13
24 минуты
-
Лекция 14
2 часа 11 минут
Ультрафильтры и компактность
Рассматриваются вопросы, связанные с построением ультрафильтров и компактностью, расширимостью до ультрафильтров, приведены примеры
-
Тест 14
24 минуты
-
1 час 40 минут
-