Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

Voprosy_MatLogika

.doc
Скачиваний:
5
Добавлен:
07.06.2018
Размер:
14.85 Кб
Скачать

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

  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. Примеры.

Соседние файлы в предмете Математическая логика и теория алгоритмов