Досконалі диз’юнктивні нормальні форми (ДДНФ), Досконалі кон’юнктиві нормальні форми (ДКНФ)

Елементарною кон'юнкцією називається кон'юнкція булевих змінних, кожна з яких може стояти під знаком заперечення.
Булевий вираз записаний у диз'юнктивній нормальній формі, якщо він являє собою диз'юнкцію елементарних кон'юнкцій.
Диз'юнктивна нормальна форма від n змінних називається досконалою, якщо кожна елементарна кон'юнкція містить всі змінні, можливо з запереченням.
Зазначимо, що крім диз'юнктивних нормальних форм, широко застосовуються нормальні форми іншого типу - кон'юнктивні.
Нарешті розглянемо метод побудови ДДНФ за таблицею істинності.
Оскільки ДДНФ, що будується, є булевим виразом, який відповідає заданій таблиці істинності, він повинен приймати значення 1 при тих і тільки тих наборах значень аргументів, при яких у таблиці істинності стоїть 1.
Нехай заданий деякий набір значень: змінні x1, …, xn приймають значення відповідно s1, …, sn. Елементарна кон'юнкція, яка залежить від змінних x1, …, xn, при даних значеннях аргументів може дорівнювати 1 в одному і тільки одному випадку: якщо аргументи, що дорівнюють 0, входять до неї під знаком заперечення, а ті, що дорівнюють 1 - без знака заперечення. Іншими словами, єдина елементарна кон'юнкція, яка при x1= s1, …, xn= sn дорівнює 1, має вигляд y1…yn, де yi= xi при si= 1 і yi= xi при si= 0. Далі, оскільки таблиця істинності дорівнює 1 при декількох наборах значень аргументів, вона повинна являти собою диз'юнкцію усіх відповідних елементарних кон'юнкцій.
Приклад. Побудуємо ДДНФ за такою таблицею істинності:
x y z f(x, y, z)
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 1
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 1

До ДДНФ повинно увійти чотири елементарні кон'юнкції, які відповідають наборам, при яких функція приймає значення 1 (вони обведені рамками). Відповідно до цього ДДНФ матиме вигляд
xyz۷xyz۷xyz۷xyz

Методи мінімізації булевих функцій: карти та куб Карно, метод Квайн-Мак-Класкі, метод Борецького-Блейка.

Может ну его нах?