Языки и исчисления: Информация
Авторы: Николай Верещагин, Александр Шень
Форма обучения:
дистанционная
Стоимость самостоятельного обучения:
бесплатно
Доступ:
свободный
Документ об окончании:
Вам нравится? Нравится 11 студентам
Уровень:
Специалист
Длительность:
25:56:00
Студентов:
722
Выпускников:
35
Качество курса:
4.60 | 4.30
В курсе рассказывается об основных понятиях математической логики (логика высказываний, языки первого порядка, выразимость, исчисление высказываний, разрешимые теории, теорема о полноте, начала теории моделей).
Курс включает в себя около 200 задач различной трудности.
Специальности: Программист
Теги: beta, MP@ML, алгебра, анализ, вычисления, графика, дедукция, законы, игры, изоморфизм, импликация, истинность формул, исчисление предикатов, книги, логика, подформула, поиск, полугруппа, предикатный символ, сложность, тавтология, теория, элементы
План занятий
Занятие
Заголовок <<
Дата изучения
Лекция 1
1 час 19 минут
Логика высказываний
Рассматриваются основные понятия алгебры логики (аксиомы, формулы, эквивалентность, вывод, разбор формул, полнота связок и другие)
Оглавление
-
Лекция 2
1 час 40 минут
Схемы из функциональных элементов
Рассматриваются базовые логические схемы, наборы схем, вопросы их полноты, сложность булевой функции относительно базовых наборов схем, теоремы оценки сложности
Оглавление
-
Лекция 3
1 час 19 минут
Исчисление высказываний
Рассматриваются аксиомы исчисления высказываний, правила вывода, выводимость, критерии обращения формул в теоремы, тавтологии
Оглавление
-
Лекция 4
1 час 48 минут
Контрпример
Рассматриваются исчисление секвенции, вопросы корректности и полноты исчисления секвенции
Оглавление
-
Лекция 5
1 час 3 минуты
Языки первого порядка
Рассматриваются языки первого порядка, вопросы определения сигнатуры таких языков, их интерпретации, выяснения истинности формул над такими языками
Оглавление
-
Лекция 6
1 час 30 минут
Выразимость в арифметике
Рассматриваются арифметические предикаты (формулы, определенные на сигнатуре с арифметическими операциями типа сложения и умножения), вопросы арифметичности произвольных предикатов
Оглавление
-
Лекция 7
1 час 47 минут
Арифметика Пресбургера
Рассматриваются вопросы выразимости множеств для сигнатуры вида {=, <, +, 0, 1} и носителя Z, критерии существования бескванторных эквивалентных формул, вопросы элементарной эквивалентности
Оглавление
-
Лекция 8
1 час
Игра Эренфойхта и понижение мощности
Рассматриваются критерии элементарной эквивалентности двух интерпретации одной сигнатуры в терминах игры двух игроков (двух интерпретации)
Оглавление
-
Лекция 9
1 час 8 минут
Исчисление предикатов
Рассматривается исчисление, аналогичное исчислению высказываний, для формул первого порядка, аксиомы, правила вывода, области действия формул, вопросы корректности
Оглавление
-
Лекция 10
1 час 42 минуты
Полнота исчисления предикатов
Рассматриваются вопросы непротиворечивости теории, совместных множеств замкнутых формул, а также полноты непротиворечивых теории
Оглавление
-
Лекция 11
47 минут
Теорема Эрбрана
Рассматривается теорема Эрбрана и следствия из неё, а также примеры приложений
Оглавление
-
Лекция 12
1 час 35 минут
Теории и модели
Рассматриваются аксиомы равенства на произвольных сигнатурах, критерии существования для соответствующих теории, вопросы полноты теорий
Оглавление
-
Лекция 14
2 часа 11 минут
Ультрафильтры и компактность
Рассматриваются вопросы, связанные с построением ультрафильтров и компактностью, расширимостью до ультрафильтров, приведены примеры
Оглавление
-