Математическая логика и теория алгоритмов



Скачать 22.05 Kb.
Дата27.04.2018
Размер22.05 Kb.

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


  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, PSPACE, EXP, NP.

  29. Полиномиальная сводимость. NP-полные и NP-трудные задачи.

  30. Теорема Кука о NP-полноте проверки выполнимости КНФ (без док-ва). Примеры других NP-полных задач. Гипотеза PNP и ее значение в теории сложности.



Поделитесь с Вашими друзьями:


База данных защищена авторским правом ©znate.ru 2017
обратиться к администрации

    Главная страница