Лекция 10

"Введение в математическую логику и теорию алгоритмов" (Л. Д. Беклемишев, мехмат МГУ) Лекция 10 (06.11.2020) 00:00 Начало лекции 0:30 Определимость (выразимость) (повторение из предыдущей лекции) 4:18 Гомоморфизм моделей 8:36 Изоморфизм моделей 9:14 Теорема о сохранении значения формулы при изоморфизме 12:47 Примеры доказательства невыразимости предиката методом автоморфизмов 16:51 Автоморфизмы плоскости с отношением "между" 31:45 Автоморфизмы плоскости с отношением "между" и равенством длин 34:41 Формула, выполнимая в модели. Выполнимая формула 37:24 Общезначимая, тождественно ложная формулы 42:05 Равносильные формулы 43:20 Основные равносильности с кванторами 50:18 Особенности подстановки в логике предикатов 53:54 Замена всех вхождений Р в формулу С на формулу А (подстановка формулы вместо пропозициональной переменной в формулу) 56:09 Условие допустимости (разрешимости) подстановки 57:10 Замена подформулы на эквивалентную 59:01 Замена связной переменной 1:01:18 Семантика расширенного языка (в преддверии теоремы о подстановке) 1:02:35 Теорема о подстановке 1:06:19 Предварённая формула. Теорема о существовании эквивалентной данной формуле предварённой формулы от тех же свободных переменных (приведение формулы к предварённой форме)