Лекция 8

"Введение в математическую логику и теорию алгоритмов" (Л. Д. Беклемишев, мехмат МГУ) Лекция 8 (23.10.2020) 00:00 Начало лекции 2:39 Логика высказываний. --- 5:36 Синтаксис логики высказываний. Понятие формулы. Индуктивные определения. 11:40 Лемма об однозначности прочтения. Понятие подформулы. 21:07 Соглашения об опускании скобок. 24:50 Дерево разбора формулы. Направленный ациклический граф (DAG). --- 29:21 Семантика логики высказываний. 29:40 Истинностные значения. Булева функция. Таблица истинности. 32:46 Оценка переменных, значение формулы при данной оценке. 38:18 Булева функция, задаваемая данной формулой. 40:51 Таблица истинности формулы. 42:45 Теорема о функциональной полноте. --- 55:03 Выполнимая формула. Выполнимое множество формул. 55:44 Тавтология. Тождественно ложная формула. 57:50 Задача проверки выполнимости данной формулы. Проблема P=NP. 1:02:57 Равносильность (эквивалентность) формул. 1:05:22 Свойства равносильности. Связь с понятием тавтологии. 1:06:34 Основные эквивалентности. --- 1:11:18 Подстановка. 1:12:31 Теорема о подстановке. 1:17:22 Теорема о замене подформулы на эквивалентную. --- 1:21:27 Дизъюнктивная и конъюнктивная нормальные формы (ДНФ и КНФ). 1:22:02 Дизъюнктивная нормальная форма. 1:24:57 Теорема о приведении формулы к ДНФ (КНФ). 1:27:25 Синтаксический алгоритм приведения формулы к ДНФ (КНФ). 1:30:35 Совершенные ДНФ и КНФ. 1:37:00 Алгоритм приведения формулы к совершенной ДНФ. 1:38:02 Единственность совершенных ДНФ и КНФ с точностью до графического равенства.