Федеральное агентство по образованию. 1. Высказывания. Операции над высказываниями

ВОПРОСЫ К ЭКЗАМЕНУ

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. Две теоремы Геделя о неполноте (формулировки)

40. Разрешимость теорий

РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА

Основная литература

1. Игошин В.И. Математическая логика и теория алгоритмов. – М.: Академия, 2008. – 448 с.

2. Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов. - М.: Академия, 2007. – 304 с.

3. Судоплатов С.В., Овчинникова Е.В. Математическая логика и теория алгоритмов. - М.: Инфра-М, 2008. – 224 с.

4. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. – М.: Физматлит, 2004. – 256 с.

Дополнительная литература

1. Мендельсон Э. Введение в математическую логику. – М.: Наука, 1976. – 320 с.

2. Ершов Ю.Л., Палютин Е.А.Математическая логика. – М.: Наука, 1987. – 336 с.

3. Колмогоров А.Н., Драгалин А.Г. Математическая логика. – М.: КомКнига, 2006. – 240 с.

4. Новиков П.С. Элементы математической логики. – М.: Наука, 1973. –

400 с.

5. Шенфилд Дж. Математическая логика. – М., Наука, 1975. – 528 c.

6. Шапорев С. Д. Математическая логика. Курс лекций и практических занятий. – СПб.: БХВ-Петербург, 2005. – 416 с.

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ