Курс, читаемый на Отделении теоретической и прикладной лингвистики (ОТиПЛ) филологического факультета МГУ

Список всех тем лекций

Лекция 1. Логика высказываний.
Вводное слово к курсу Что есть высказывание? Операции над высказываниями: логические и нелогические Примеры логических операций Язык логики высказываний Тавтологии, опровержимые формулы: определения Сколько строк в таблице истинности, если переменных n? Задания на определение тавтологий Основные эквивалентности

Лекция 2. Дизъюнктивная нормальная форма.
Знакомство с дизъюнктивными нормальными формами (ДНФ) Определение ДНФ и элементарной конъюнкции Приведение к ДНФ: теорема и примеры Составление формулы по таблице истинности Полные системы связок Штрих Шеффера и стрелка Пирса Подведение итогов

Лекция 3. Генценовское исчисление высказываний.
Определение логического следования Постановка задачи Пример A->B,C->D |= A\/C->B\/D Пример A->(B->C) |= A&B->C Пример A->B,C->D |= (A->C)->(B->D) Секвенции, аксиомы и правила Что такое вывод? Формулировка теоремы об эквивалентности Пример (P->Q)->R |= неR->P&неQ Доказательство теоремы Пример не(P&Q) |= неP&неQ Пример P\/Q->R |= R \/ не(неP->Q) Заключение по логике высказываний

Лекция 4. Логика I порядка. Синтаксис и семантика.
Структура сигнатуры Пример 1 Язык сигнатуры Σ (продолжение решения) Пример 2 Пример 3 Пример 4 Пример 5

Лекция 5. Логика I порядка. Общезначимость. Эквивалентность.
Структура сигнатуры Общезначимость Эквивалентность Основные эквивалентности Примеры Задача

Лекция 6. Логика I порядка. Выразимость. Изоморфизм.
Задача Изоморфизм Автоморфизм Примеры

Лекция 7. Изоморфизм и элементарная эквивалентность структур.
Задача Элементарная эквивалентность Пример Пример

Лекция 8. Логика предикатов с равенством.
Пример 1 Пример 2 Язык с равенством

Лекция 9. Выводимость в логике I порядка. Исчисление предикатов.
Логика высказываний Аналогичное исчисление для логики I порядка Пример 1 Пример 2 Пример 3 Пример 4 Пример 5 Пример 6 Как связаны выводимость и логическое следование? Примеры

Лекция 10. Теорема о компактности и её следствия.
Необходимые определения Теорема о компактности Теорема 2 Формальная теория Формальная арифметика Итог

Лекция 11. Модальная логика.
Модальная логика Примеры содержательных формул Семантика возможных миров Крипке Теорема

Лекция 12. Модальная логика. Семантика Крипке.
Модель Крипке Примеры модели Какие ещё свойства можно записать при помощи модальных формул (примеры) Свойства, которые нельзя выразить модальными формулами

Лекция 13. Минимальная модальная логика К и другие логики.
Описание Обратная импликация Пример Теорема Логика знаний

Лекция 14. Временная логика.
Язык с двумя модальностями необходимости Пример 1 Пример 2 Минимальная временная логика Формулы и свойства шкал Логика since/until

Лекция 15. Теория алгоритмов. Разрешимое и перечислимое множество.
Алгоритм Тезис Чёрча Разрешимые множества Примеры разрешимых множеств Перечислимые множества

Лекция 16. Теория алгоритмов. Универсальная вычислимая функция.
Универсальная вычислимая функция Пример перечислимого неразрешимого множества Задача (теорема о графике) Задача (теорема о проекции) Задача Задача для самостоятельного разбора