Voprosy_MatLogika

Вопросы к экзамену по дисциплине «Математическая логика и теория алгоритмов»

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. Сложность алгоритма. Классы P и NP. Примеры.