Опубликован: 24.04.2007 | Уровень: специалист | Доступ: платный
Языки и исчисления В курсе рассказывается об основных понятиях математической логики (логика высказываний, языки первого порядка, выразимость, исчисление высказываний, разрешимые теории, теорема о полноте, начала теории моделей).
Курс включает в себя около 200 задач различной трудности.

План занятий

ЗанятиеЗаголовок <<Дата изучения
-
Введение 
9 минут
Предисловие
Оглавление
    -
    Лекция 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
                  1 час
                  Игра Эренфойхта и понижение мощности
                  Рассматриваются критерии элементарной эквивалентности двух интерпретации одной сигнатуры в терминах игры двух игроков (двух интерпретации)
                  Оглавление
                    -
                    Тест 8
                    24 минуты
                    -
                    Лекция 9
                    1 час 8 минут
                    Исчисление предикатов
                    Рассматривается исчисление, аналогичное исчислению высказываний, для формул первого порядка, аксиомы, правила вывода, области действия формул, вопросы корректности
                    Оглавление
                      -
                      Тест 9
                      24 минуты
                      -
                      Лекция 10
                      1 час 42 минуты
                      Полнота исчисления предикатов
                      Рассматриваются вопросы непротиворечивости теории, совместных множеств замкнутых формул, а также полноты непротиворечивых теории
                      Оглавление
                        -
                        Тест 10
                        24 минуты
                        -
                        Лекция 11
                        47 минут
                        Теорема Эрбрана
                        Рассматривается теорема Эрбрана и следствия из неё, а также примеры приложений
                        Оглавление
                          -
                          Тест 11
                          24 минуты
                          -
                          Лекция 12
                          1 час 35 минут
                          Теории и модели
                          Рассматриваются аксиомы равенства на произвольных сигнатурах, критерии существования для соответствующих теории, вопросы полноты теорий
                          Оглавление
                            -
                            Тест 12
                            24 минуты
                            -
                            Лекция 13
                            1 час 25 минут
                            Диаграммы
                            Рассматриваются вопросы существования расширений интерпретации, являющиеся нормальной моделью теории с равенством
                            Оглавление
                              -
                              Тест 13
                              24 минуты
                              -
                              Лекция 14
                              2 часа 11 минут
                              Ультрафильтры и компактность
                              Рассматриваются вопросы, связанные с построением ультрафильтров и компактностью, расширимостью до ультрафильтров, приведены примеры
                              Оглавление
                                -
                                Тест 14
                                24 минуты
                                -
                                5 часов
                                -
                                Алексей Васильев
                                Алексей Васильев
                                Россия, Новосибирск
                                David Satseradze
                                David Satseradze
                                Грузия, Тбилиси