Вопросы

ВОПРОСЫ К ЭКЗАМЕНУ ПО КУРСУ «МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ»

1. Понятие высказывания. Логические операции над высказываниями.

2. Понятие формулы алгебры высказываний. Логическое значение составного высказывания

3. Классификация формул алгебры высказываний. Составление таблиц истинности для формул.

4. Тавтологии алгебры высказываний. Основные правила получения тавтологий.

5. Понятие логической равносильности формул. Признак равносильности формул. Равносильные преобразования.

6. Понятие нормальных форм для формул алгебры высказываний. Совершенные нормальные формы

7. Представление формул алгебры высказываний совершенными дизъюнктивными нормальными (СДН) формами.

8. Способы приведения формул алгебры высказываний к совершенным дизъюнктивным нормальным (СДН) формам.

9. Представление формул алгебры высказываний совершенными конъюнктивными нормальными (СКН) формами.

10. Способы приведения формул алгебры высказываний к совершенным конъюнктивным нормальным (СКН) формам.

11. Понятие логического следования формул. Признаки логического следствия

12. Правила логических умозаключений.

13. Аксиоматическая теория высказываний. Первоначальные понятия. Система аксиом. Правило вывода.

14. Понятие вывода в формализованном исчислении высказываний. Свойства выводимости.

15. Теорема о дедукции формализованного исчисления высказываний.

16. Применение теоремы о дедукции в формализованном исчислении высказываний.

17. Свойства формализованного исчисления высказываний.

18. Булевы функции от одного и от двух аргументов.

19. Свойства булевых функций. Выражения одних булевых функций через другие.

20. Понятие булевой функции от n аргументов. Число булевых функций.

21. Выражение булевых функций через конъюнкцию, дизъюнкцию и отрицание.

22. Полные системы булевых функций.

23. Специальные классы булевых функций.

24. Теорема Поста о полноте системы булевых функций.

25. Понятие предиката. Классификация предикатов.

26. Множество истинности предиката. Равносильность предикатов. Следование предикатов.

27. Логические операции над предикатами.

28. Кванторные операции над предикатами. Квантор существования.

29. Кванторные операции над предикатами. Квантор общности.

30. Выражения одних кванторов через другие. Логический квадрат.

31. Понятие формулы логики предикатов.

32. Классификация формул логики предикатов.

33. Понятия равносильности формул логики предикатов.

34. Приведенная форма для формул логики предикатов

35. Предваренная нормальная форма для формул логики предикатов

36. Формализация понятия алгоритма.

37. Машина Тьюринга.

38. Композиция машин Тьюринга.

39. Нормальные алгоритмы Маркова.

40. Вычислимые функции.

41. Сложность алгоритмов.

42. Нечеткая логика.