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



Скачать 66.23 Kb.
страница1/3
Дата01.08.2018
Размер66.23 Kb.
ТипВопросы к экзамену
  1   2   3

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

Логика высказываний.



  1. Понятие высказывания и его структура: атомарные высказывания и составные высказывания. Логические союзы: дизъюнкция, конъюнкция, импликация, эквивалентность, отрицание. Символическая запись составных высказываний и формализация предложений естественного языка.

  2. Алфавит и слова в алфавите. Формальные языки.

  3. Алфавит языка логики высказываний. Индуктивное определение пропозициональной формулы. Понятие подформулы пропозициональной формулы. Индукция по длине построения формулы.

  4. Логическая сложность пропозициональных формул. Теорема характеризации множества пропозициональных формул.

  5. Теорема о единственности синтаксического анализа пропозициональной формулы.

  6. Оценки пропозициональных букв и индуктивное определение истинностного значения пропозициональной формулы. Множество истинностных оценок и функция истинности пропозициональной формулы. Таблица истинности пропозициональной формулы.

  7. Выполнимые и общезначимые формулы(тавтологии).

  8. Отношение семантического следования и семантической равносильности пропозициональных формул. Семантический modus ponens и семантическая теорема дедукции.

  9. Основные равносильности межу пропозициональными формулами и булева алгебра пропозициональных формул.

  10. Специальные виды пропозициональных формул. Литерал, дизъюнкты и конъюнкты относительно списка букв. Семантические свойства дизъюнктов и конъюнктов. Определение ДНФ и КНФ.

  11. Теорема о приведении любой пропозициональной формулы к КНФ и ДНФ. Алгоритм нормализации(приведения к КНФ и ДНФ).

  12. СДНФ и СКНФ. Теорема единственности СКНФ и СДНФ.

  13. Описание всех семантических следствий конечного списка пропозициональных формул через приведение к СКНФ.

  14. Переключательные схемы и их функции истинности. Представление схем пропозициональными формулами.

  15. Общее понятие исчисления(формальной аксиоматической теории).

  16. Логическое исчисление и вывод в исчислении (формальной теории): алфавит, множество выражений и правил вывода исчисления.

  17. Посылки и заключение правила вывода, понятие непосредственного следствия и определение вывода из множества выражений.

  18. Отношение выводимости, вывод из гипотез и определение доказуемости в исчислении. Порождающие грамматики как пример формальных теорий.

  19. Понятие о языке-объекте и метоязыке. Элементарные свойства отношения выводимости в формальной теории.

  20. Построение исчисления высказываний. Его аксиомы и правила вывода.

  21. Пример построения выводов в исчислении высказываний (ИВ).

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

  23. Применение теоремы дедукции к построению выводов. Допустимые правила в исчислении высказываний.

  24. Теорема адекватности исчисления высказываний.

  25. Непротиворечивые и противоречивые множества формул в исчислении высказываний. Теорема о непротиворечивости выполнимого множества формул.

  26. Свойства непротиворечивых множеств формул в исчислении высказываний. Непротиворечивое множество аксиом в исчислении высказываний.

  27. Нумерация пропозициональных формул по Геделю.

  28. Теорема о расширении непротиворечивого множества до максимально непротиворечивого множества до максимально непротиворечивого множества.

  29. Теорема о выполнимости максимально непротиворечивого множества.

  30. Теорема о полноте исчисления высказываний и некоторые её следствия.

  31. Понятие независимости формулы от множества формул. Пример зависимых и независимых пропозициональных формул.

  32. Понятие о многозначных логиках. Примеры трехзначных логик.

  33. Метод многозначных логик в доказательстве независимости аксиом исчисления высказываний.


Каталог:


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


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

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