Экзаменационные вопросы:
1. Высказывания и логические операции над ними. Формулы логики высказываний, их истинностные значения. Классификация формул. Примеры.
2. Равносильность формул логики высказываний. Основные равносильности. Примеры.
3. Логическое следствие в логике высказываний. Способы доказательства логических следствий. Анализ правильности рассуждений. Примеры.
4. Нормальные формы формул логики высказываний. Распознавание вида формул (эффективные процедуры). Примеры.
5. Совершенные нормальные формы формул логики высказываний. Теоремы о существовании СКНФ и СДНФ. Примеры.
6. Формальные аксиоматические теории. Алфавит, формула, аксиомы, правила вывода. Понятия вывода и вывода из систем гипотез.
7. Исчисление высказываний (формальная теория L). Алфавит, формулы, аксиомы, правила вывода исчисления высказываний. Примеры.
8. Доказуемость и выводимость формул в исчислении высказываний. Теорема дедукции и ее следствия. Примеры.
9. Автоматическое доказательство теорем. Метод резолюций в исчислении высказываний. Привести пример.
10. Некоторые теоремы исчисления высказываний. Провести доказательство одной теоремы.
11. Проблемы полноты, разрешимости и непротиворечивости исчисления высказываний.
12. Независимость системы аксиом исчисления высказываний. Провести доказательство независимости одной из аксиом. Другие аксиоматизации исчисления высказываний.
13. Определение предиката. Множество истинности предиката (характеристическое множество). Классификация предикатов на множестве. Логические операции над предикатами. Геометрическая интерпретация этих операций на основе понятия
характеристических множеств. Примеры.
14. Кванторы общности и существования. Изменение местности предиката при связывании переменных кванторами. Свободные и связанные переменные. Формулы логики предикатов. Примеры.
15. Классификация формул в логике предикатов. Равносильные формулы логики предикатов. Основные равносильности. Проблема разрешения в логике предикатов. Примеры.
16. Исчисление предикатов. Общезначимость и полнота чистого исчисления предикатов. Метод резолюций в логике предикатов. Пример.
17. Понятие алгоритма. Основные требования. Необходимость уточнения понятия алгоритма. Формализация понятия алгоритма.
18. Формализация понятия алгоритма. Машина Тьюринга. Вычислимость по Тьюрингу. Тезис Черча.
19. Формализация понятия алгоритма. Рекурсивные функции. Примитивно рекурсивные, частично рекурсивные и общерекурсивные функции.
20. Меры сложности вычислений. Легко и трудноразрешимые задачи. Классы задач Р и NP. NP-полные задачи.
21. Основы нечеткой логики. Нечеткие множества. Алгебра нечетких множеств.
Ответы на данные вопросы можно скачать ОТСЮДА.
Ответы в виде шпаргалок можно скачать ОТСЮДА.
Похожие статьи: