Эквивалентные формулы. Приведение формулы к нормальному виду.

1.      Исчисление высказываний. Формулы. Теорема о единственности представления формулы ИВ в виде конъюнкции,  дизъюнкции, отрицания или импликации других высказываний.

2.      Генценовское ИВ. Правила вывода. Секвенции.  Доказательства. Допустимые правила.

3.      Доказательство секвенций  и 

4.      Эквивалентные формулы.  Приведение формулы к нормальному виду.

5.      Интерпретация ИВ. Истинность формул и секвенций на наборе переменных. Тождественная истинность.

6.      Теорема о непротиворечивости ИВ.

7.      Теорема  о функциональной полноте ИВ.

8.      Теорема о полноте ИВ.

9.      Разрешимость классического исчисления высказываний.

10.  Понятие об интуиционизме и конструктивизме в логике.

11.  Интуиционистское ИВ. Недоказуемость  закона исключённого третьего.

12.  Эквивалентные множества и их свойства. Теорема Шрёдера – Бернштейна.

13.  Счётные множества и их свойства.

14.  Несчётность множества действительных чисел. Свойства множеств мощности континуума.

15.  Связь между счётными множествами и множествами мощности континуума.

16.  Теорема Кантора о мощности множества всех подмножеств данного множества. 

17.  Эквивалентность множеств  и

18.  Вполне упорядоченные множества и их свойства.

19.  Аксиома выбора. Теорема Цермело.

20.  Лемма Цорна.

21.  Ординальные числа и их свойства..

22.  Кардинальные числа и их свойства.

23.  Мощность множества

24.  Аксиомы Пеано натуральных чисел. Коммутативность сложения.

25.  Аксиомы действительных чисел.

26.  Модель, сигнатура. Формулы исчисления предикатов (логики первого порядка). Истинность формулы в данной модели.

27.  Элиминация кванторов.

28.  Фильтр. Центрированная система множеств.

29.  Ультрафильтр. Характеризация ультрафильтров.

30.  Ультрапроизведение моделей. Истинность формул на ультрапроизведении. Теорема Лося.

31.  Теорема Гёделя – Мальцева  и следствие из неё.

32.  Теорема Лёвенгейма-Скулема о повышении мощности

33.  Машины Тьюринга и вычислимые функции. Понятие алгоритма. Тезис Чёрча.

34.  Операторы суперпозиции и примитивной рекурсии. Примитивно рекурсивные функции.

35.  Оператор минимизации. Рекурсивные функции.

36.  Разрешимые и перечислимые множества.

37.  Универсальные вычислимые функции.

38.  Существование перечислимого неразрешимого множества.

39.   алгоритмически неразрешимые задачи. Алгоритмическая неразрешимость проблемы остановки машины Тьюринга.

Ссылка на основную публикацию
Adblock detector