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

100 по одной и по всем переменным. 8. Построение СДНФ для функции, заданной таблицей. 9. Совершенная конъюнктивная нормальная форма: Опр. ЭД, ОЭД, КНФ, СКНФ. Представление функции, тождественно не равной единице через СКНФ. 10. Построение СКНФ для функции, заданной таблицей. 11. Основные эквивалентные преобразования и их доказательства (поглощение, склеивание, обобщенное склеивание, расщепление). 12. Теоремы о логическом следствии с доказательством. 13. Метод резолюций для исчисления высказываний. 14. Определение минимальной, кратчайшей и неизбыточной ДНФ. 15. Полином Жегалкина. Определение в общем виде. Частные случаи для 2 и 3 переменных. На примере для 2 переменных показать переход от любой логической функции к ПЖ. 16. Определение импликанта, простого импликанта. Теорема о представлении функции через простые имликанты. 17. Определение дополнения ЭК. Теорема о дополнениях импликанта. 18. Алгоритм перечисления простых импликантов (Куайна- МакКлоски). 19. Определение полной системы функций. Теорема о двух полных системах функций. Определение замыкания. 20. Класс функций T0. Определение и доказательство замкнутости. 21. Класс функций T1. Определение и доказательство замкнутости. 22. Класс функций S. Определение и лемма о несамодвойственной функции. 23. Класс функций M. Определение и лемма о немонотонной функции. 24. Класс функций L. Определение и лемма о нелинейной функции.