misle.ru страница 1
скачать файл
ВОПРОСЫ К ЭКЗАМЕНУ

ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ, ч. IV

(МАТЕМАТИЧЕСКАЯ ЛОГИКА)

Введение


1. Формальная логика и ее развитие. Основные понятия традиционной формальной логики. Предмет и метод математической логики.

Исчисление высказываний


2. Основные операции над высказываниями. Логические и алгебраические обозначения. Принцип экстенциональности.

3. Высказывательные (булевы) функции и таблицы истинности. Тавтологии и проблема разрешения исчисления высказываний.

4. Правила вывода в исчислении высказываний.

5. Законы эквивалентности и импликации.

6. Законы дизъюнкции, конъюнкции и отрицания.

7. Принцип двойственности для эквивалентности и импликации.

8. Теоремы Порецкого, теорема внесения и вынесения, преобразование импликации в эквивалентность.

9. Reductio ad absurdum, законы Клавия и Дунса Скота, дилеммы.

10. Нормальные формы в исчислении высказываний.

11. Конституэнты истины (единицы) и лжи (нуля). Переход от таблиц истинности к алгебраическим выражениям.

12. Теоремы разложения и упрощения высказывательных функций.

13. Базисы высказывательных функций и критерий Поста – Яблонского.


Исчисление множеств


14. Понятие множества. Парадоксы Рассела и Кантора.

15. Отношения между множествами и операции над множествами. Логические и алгебраические обозначения.

16. Понятие теоретико-множественной функции. Булевы функции множеств.

17. Декартово умножение и возведение множеств в степень.

18. Доказать в алгебре множеств формулу

19. Проверить в алгебре множеств формулы:



20. Сравнение алгебры высказываний и алгебры множеств.


Исчисление предикатов


21. Предикаты и кванторы. Логические и алгебраические обозначения. Коллизии переменных.

22. Тождество, принцип неразличимых Лейбница, квантор единственного существования и оператор описания.

23. Запись единичных, частных и общих высказываний в исчислении предикатов.

24. Тавтологии и проблема разрешения исчисления предикатов. Случай конечных миров речи. Семантические таблицы Бета.

25. Проверить по семантическим таблицам формулы:

26. Проверить по семантическим таблицам формулы:



27. Правила вывода в исчислении предикатов.

28. Введение и исключение кванторов. Квантование эквивалентности и импликации.

29. Квантование дизъюнкции, конъюнкции и отрицания.

30. Кратное и диагональное квантование.

31. Modus ponens и modus tollens в исчислении высказываний и исчислении предикатов.

32. Вывести из основных законов исчисления предикатов формулу

33. Вывести из основных законов исчисления предикатов формулу



34. Предваренные и нормальные формы в исчислении предикатов.

35. Привести формулу

к предваренной нормальной форме и найти функции Сколема.

36. Привести формулу

к предваренной нормальной форме и найти функции Сколема.

37. Привести формулу

к предваренной нормальной форме и найти функции Сколема.

38. Привести формулу

к предваренной нормальной форме и найти функции Сколема.


Исчисление отношений


39. Понятие отношения. Сведение отношений к множествам (конструкция Винера ­– Куратовского). Отношения между отношениями.

40. Бинарные отношения и их представление графами и матрицами. Сведение n-арных отношений к бинарным.

41. Алгебра бинарных отношений. Логические и алгебраические обозначения.

42. Рефлексивные, симметрические и транзитивные отношения.

43. Доказать, что иррефлексивное и транзитивное отношение асимметрично.

44. Доказать, что асимметрическое отношение иррефлексивно и антисимметрично.

45. Проверить, всякое ли симметрическое и транзитивное отношение рефлексивно.

46. Отношения эквивалентности и теорема Кантора. Отношения толерантности.

47. Частичный порядок, порядок, частичный строгий порядок, строгий порядок.

Аксиоматическое построение логических исчислений


48. Аксиоматическое построение исчисления высказываний. Система Гильберта – Аккермана.

49. Вывести в системе Гильберта – Аккермана формулу



и правило



|–

(примечание: в последнем правиле вывода должны быть готические буквы)

50. Вывести в системе Гильберта – Аккермана формулы:

.

51. Вывести в системе Гильберта – Аккермана формулы:



.

52. Вывести в системе Гильберта – Аккермана формулу



53. Вывести в системе Гильберта – Аккермана формулы:



54. Вывести в системе Гильберта – Аккермана правило замены взаимно выводимых.

55. Вывести в системе Гильберта – Аккермана формулы:

56. Вывести в системе Гильберта – Аккермана формулу



57. Непротиворечивость, независимость и полнота системы аксиом Гильберта – Аккермана для исчисления высказываний.



58. Аксиоматическое построение исчисления предикатов. Упрощенная система Гильберта – Аккермана.
скачать файл


Смотрите также: