Дизъюнктивная нормальная форма (ДНФ) и конъюнктивная нормальная форма (КНФ). Совершенные ДНФ и КНФ.

Дизъюнктивной нормальной формой или ДНФ называется дизъюнкция простых конъюнкций. Например — является ДНФ.

Совершенной дизъюнктивной нормальной фор

мой или СДНФ называется такая ДНФ, у которой в каждую конъюнкцию входят все переменные данного набора пременных, причём в одном и том же порядке. Например: .

Конъюнктивная нормальная форма. КНФ — это конъюнкция простых дизъюнкций.

Совершенной конъюнктивной нормальной формой (СКНФ), называется такая КНФ, у которой в каждую дизъюнкцию входят все переменные данного набора, причём в одном и том же порядке.

КНФ может быть преобразована к эквивалентной ей ДНФ путём раскрытия скобок по правилу:

1. Предмет комбинаторики. Логические правила комбинаторики. 

2. Число r-перестановок (с повторениями и без повторений) из n элементов. Число всех

подмножеств n-элементного множества. 

3. Число r-сочетаний из n элементов. Биномиальная теорема и следствия из нее. Основные

свойства биномиальных коэффициентов. Треугольник Паскаля. 

4. Число-разбиений конечного множества. Другая комбинаторная интерпретация

этого числа. Полиномиальная теорема. 

5. Число r-сочетаний с повторениями из n элементов. 

6. Метод включения и исключения (формула для числа элементов, не обладающих ни

одним из заданных свойств). 

7. Метод включения и исключения (формула для числа элементов, обладающих в точности

t (t ≥ 1) свойствами из числа заданных свойств). 

8. Применение метода включения и исключения (задача о беспорядках, задача о числе

сюръективных отображений). 

9. Понятие рекуррентного соотношения. Рекуррентное соотношение k-го порядка для

функции одной переменной, его общее решение. 

10. Общее решение линейного однородного рекуррентного соотношения с постоянными

коэффициентами. 

11. Числа Фибоначчи. Вывод формулы n-го числа Фибоначчи решением линейного

однородного рекуррентного соотношения 2-го порядка. 

12. Общее решение линейного неоднородного рекуррентного соотношения с постоянными

коэффициентами. 

13. Разбиение подстановки на циклы. Число подстановок n-элементного множества,

имеющих предписанных циклический тип. 

14. Число Стирлинга 1-го рода. Рекуррентное соотношение для числа Стирлинга 1-го рода. 

15. Упорядоченные и неупорядоченные разбиения множеств. Число Стирлинга 2-го рода.

Формула и рекуррентное соотношение для числа Стирлинга 2-го рода. 

16. Число Белла. Рекуррентное соотношение для числа Белла. 

17. Упорядоченные и неупорядоченные разбиения чисел. Рекуррентные соотношения для

количества неупорядоченных разбиений натурального числа на фиксированное число

слагаемых. 

18. Система различных представителей. Теорема Холла (без доказательства). 

19. Система общих представителей, критерий существования. 

20. Теорема Рамсея. 

21. Булевы функции. Способы их задания. Число булевых функций от n переменных. 

22. Основные логические равносильности. 

23. Разложение Шеннона и следствие из него. 

24. Двойственное разложение Шеннона и следствие из него. 

25. Дизъюнктивная нормальная форма (ДНФ) и конъюнктивная нормальная форма (КНФ).

Совершенные ДНФ и КНФ. 

26. Задача минимизации булевых функций в классе ДНФ. Полная и приведенная системы

импликант булевой функции. Связь между минимальной и тупиковой ДНФ. 

27. Алгоритм Квайна нахождения минимальной ДНФ булевой функции. 

28. Полиномиальная нормальная форма. Полином Жегалкина. Теорема о единственности

представления булевой функции посредством полинома Жегалкина. 

29. Замкнутые классы булевых функций. 

30. Полнота системы булевых функций. Теорема Поста (без доказательства)

26 Задача минимизации булевых функций в классе ДНФ. Полная и приведенная системы импликант булевой функции. Связь между минимальной и тупиковой ДНФ. Задача минимизации булевой функции в классе ДНФ формулируется следующим образом: тре­буется для булевой функции n переменных F построить ДНФ с минимально возможным числом слагаемых (КрДНФ) или с мини­мально возможным числом вхождений литералов (МДНФ).   множество импликант булевой функции образует полную систему импликант,если любая существенная вершина булевой функции покрывается хотя бы одной импликантой этого множества.   Система простых импликант называется приведенной,если она является полной,а никакая ее собственная часть уже не образует полную систему импликант. Связь: Всякая минимальная ДНФ некоторой функции является ее тупиковой ДНФ. Для получения МДНФ функции f необходимо построить все ТДНФ функции f и выбрать те из них, которые содержат минимальное число букв.