Зарипова, Э.Р. Дискретная математика Часть II. Математическая логика

112 формы для формулы. 8. Проверить принадлежность функции классам монотонных функций, самодвойственных функций, линейных функций. Типовые вопросы для итогового контроля знаний: 1. Основные понятия теории множеств. 2. Понятие прямого произведения множеств. 3. Определение алгебры и подалгебры. Функции алгебры логики. 4. Соответствия и функции в теории множеств. 5. Булева алгебра и свойства булевых операций. 6. Принцип двойственности и свойство двойственности. 7. Совершенная дизъюнктивная нормальная форма. 8. Построение СДНФ для функции, заданной таблицей. 9. Совершенная конъюнктивная нормальная форма. 10. Основные эквивалентные преобразования и их доказательства. 11. Полином Жегалкина. 12. Алгоритм Куайна-МакКлоски. 13. Определение фиктивных и существенных переменных. 14. Понятие двойственности и примеры двойственных и самодвойственных функций. 15. Определение минимальной, кратчайшей и неизбыточной ДНФ. 16. Теорема о функциональной полноте. 17. Определение и свойства функциональной полноты и замкнутости. Замыкание. 18. Общие принципы построения формальной в теории исчисления высказываний. 19. Алгоритм преобразования формул в предваренную нормальную форму. 20. Метод резолюций для исчисления высказываний. 21. Алгоритм унификации. 22. Класс функций T0. Определение и доказательство