Реферат: Введение в математическую логику

ВВЕДЕНИЕ В МАТЕМАТИЧЕСКУЮ ЛОГИКУ

проф. Н.К. Верещагин

1/2 года, 1 курс

1. Элементы теории множеств.

1. Равномощность множеств. Свойства счётных множеств.

2. Сравнение мощностей. Теорема Кантора-Бернштейна.

3. Теорема Кантора

4. Частично упорядоченные множества, линейно упорядоченные множества, вполне упорядоченные множества, начальные отрезки и их свойства.

5. Трансфинитная индукция и трансфинитная рекурсия.

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

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

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

9. Равенства для бесконечных множеств A.

^ 2. Пропозициональная логика.

10. Пропозициональные формулы.

11. Таблица истинности формулы. Возможность представления любой булевой функции некоторой формулой. Дизъюнктивные и конъюнктивные нормальные формы. Эквивалентные формулы, выполнимые формулы и тавтологии.

12. Исчисление высказываний (ИВ) (аксиомы, правила вывода, понятие выводимой формулы из данного множества формул).

13. Вывод формулы .

14. Лемма о дедукции для ИВ.

15. Выводы в ИВ.

16. Лемма о таблице истинности:, где , , а есть значение формулы А, если её переменные принимают значения соответственно.

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

^ 3. Логика первого порядка.

18. Определение формулы данной сигнатуры.

19. Интерпретации данной сигнатуры.

20. Понятие истинности формулы в данной интерпретации.

21. Выразимые в данной интерпретации предикаты. Доказательства невыразимости с помощью автоморфизмов.

22. Элиминация кванторов в интерпретации (или в интерпретации ). Невыразимость отношения ''быть меньше'' в этой интерпретации.

24. Исчисление предикатов (ИП): аксиомы, правила вывода. Допустимость применения правила обобщения.

25. Теорема о корректности исчисления предикатов. Теорема Геделя о полноте (без доказательства).

26. Примеры выводов в исчислении предикатов: вывод формул , , , (где A – одноместный предикатный символ), , .

27. Теорема о том, что замена любой подформулы на доказуемо эквивалентную формулу даёт доказуемо эквивалентную формулу.

28. Аксиомы равенства. Теорема о корректности исчисления предикатов с равенством. Теорема Геделя о полноте для исчисления предикатов с равенством (без доказательства).

29. Выводимость из посылок для исчисления предикатов. Свойства этого понятия.

30. Понятие теории, модели теории, непротиворечивости и совместности теорий. Теорема Гёделя о полноте в сильной форме (без доказательства).


Литература

1. Верещагин Н., Шень А. Математическая логика и теория алгоритмов. Начала теории множеств. М., изд-во МЦНМО, 1999.

2. Верещагин Н., Шень А. Математическая логика и теория алгоритмов. Исчисления и языки. М, изд-во МЦНМО, 2000.

Краткие (40 стр.) конспекты лекций в postscript формате и в формате для печати на принтерах Laser Jet фирмы Нewlett Packard с разрешением 600dpi доступны по Интернет в http://lpcs.math.msu.ru/˜ver