КНФ

Определение

Определение:

Простой дизъюнкцией или дизъюнктом называется дизъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная встречается не более одного раза.

Элементарная дизъюнкция

• правильная, если в неё каждая переменная входит не более одного раза (включая отрицание);
• полная, если в неё каждая переменная (или её отрицание) входит ровно 1 раз;
• монотонная, если она не содержит отрицаний переменных.

Определение:

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

Пример КНФ: $f(x,y) = (x \lor y) \land (y \lor \overline{z})$

КНФ может быть преобразована к эквивалентной ей ДНФ путём раскрытия скобок по правилу: $a (b\lor c)\to a b\lor a c$, которое выражает дистрибутивность конъюнкции относительно дизъюнкции. После этого необходимо в каждой конъюнкции удалить повторяющиеся переменные или их отрицания, а также выбросить из дизъюнкции все конъюнкции, в которых встречается переменная вместе со своим отрицанием. При этом результатом не обязательно будет СДНФ, даже если исходная КНФ была СКНФ. Точно также можно всегда перейти от ДНФ к КНФ. Для этого следует использовать правило $a\lor b c\to (a \lor b)(a \lor c)$, выражающее дистрибутивность дизъюнкции относительно конъюнкции. Результат нужно преобразовать описанным выше способом, заменив слово «конъюнкция» на «дизъюнкция» и наоборот.

Определение:

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

Пример СКНФ: $f(x,y,z) = (x \lor \overline{y} \lor z) \land (x\lor y \lor \overline{z})$

Теорема:

Для любой булевой функции $f(\vec{x})$, не равной тождественной единице, существует СКНФ, ее задающая.

Доказательство:

$\triangleright$

Поскольку инверсия функции $\overline{f}(\vec x)$ равна единице на тех наборах, на которых $f(\vec x)$ равна нулю, то СДНФ для $\overline{f}(\vec x)$ можно записать следующим образом: $\overline{f}(\vec x) = \bigvee\limits_{f(x^{\sigma_{1}}, x^{\sigma_{2}}, ... ,x^{\sigma_{n}}) = 0} (x_{1}^{\sigma_{1}} \wedge x_{2}^{\sigma_{2}} \wedge ... \wedge x_{n}^{\sigma_{n}})$, где $\sigma_{i}$ обозначает наличие или отсутствие отрицание при $x_{i}$ Найдём инверсию левой и правой части выражения: $f(\vec x) = \overline{\bigvee\limits_{f(x^{\sigma_{1}}, x^{\sigma_{2}}, ... ,x^{\sigma_{n}}) = 0} (x_{1}^{\sigma_{1}} \wedge x_{2}^{\sigma_{2}} \wedge ... \wedge x_{n}^{\sigma_{n}})}$ Применяя дважды к полученному в правой части выражению правило де Моргана, получаем: $f(\vec x) = \bigwedge\limits_{f(x^{\sigma_{1}}, x^{\sigma_{2}}, ... ,x^{\sigma_{n}}) = 0} (x_{1}^{\overline{\sigma_{1}}} \vee x_{2}^{\overline{\sigma_{2}}} \vee ... \vee x_{n}^{\overline{\sigma_{n}}})$ Последнее выражение и является СКНФ. Так как СКНФ получена из СДНФ, которая может быть посторена для любой функции, то теорема доказана.

$\triangleleft$

Алгоритм построения СКНФ по таблице истинности

1. В таблице истинности отмечаем те наборы переменных, на которых значение функции равно 0.

x	y	z	<xyz>
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

2. Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу : если значение некоторой переменной есть 0, то в дизъюнкцию включаем саму переменную, иначе ее отрицание.

x	y	z	<xyz>
0	0	0	0	$( x \lor y \lor z)$
0	0	1	0	$( x \lor y \lor \overline{z})$
0	1	0	0	$(x \lor \overline{y} \lor z)$
0	1	1	1
1	0	0	0	$(\overline{x} \lor y \lor z)$
1	0	1	1
1	1	0	1
1	1	1	1

3. Все полученные дизъюнкции связываем операциями конъюнкции.

$med(x,y,z) = ( x \lor y \lor z) \land (\overline{x} \lor y \lor z) \land (x \lor \overline{y} \lor z) \land ( x \lor y \lor \overline{z})$

Примеры СКНФ для некоторых функций

Стрелка Пирса: $x \downarrow y = (\overline{x} \lor y) \land (x \lor \overline{y}) \land (\overline{x} \lor \overline{y})$

Медиана трёх: $f(x,y,z) = ( x \lor y \lor z) \land (\overline{x} \lor y \lor z) \land (x \lor \overline{y} \lor z) \land ( x \lor y \lor \overline{z})$

Ссылки

• Википедия — свободная энциклопедия
• Е.Л Рабкин, Ю.Б. Фарфоровская — Дискретная математика