СКНФ. Теорема о представлении в виде СКНФ. Построение СКНФ по таблице

КНФ

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

Простая дизъюнкция

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

Конъюнктивная нормальная форма, КНФ { англ. conjunctive normal form, CNF } нормальная форма, в которой булева функция имеет вид конъюнкции нескольких простых дизъюнктов.

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

СКНФ

Совершенная конъюнктивная нормальная форма, СКНФ { англ. perfect conjunctive normal form, PCNF } — это такая КНФ, которая удовлетворяет условиям:

• в ней нет одинаковых простых дизъюнкций
• каждая простая дизъюнкция полная

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

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

Доказательство: Поскольку инверсия функции $\neg { f } (\vec x)$ равна единице на тех наборах, на которых $f(\vec x)$ равна нулю, то СДНФ для $\neg { f } (\vec x)$ можно записать следующим образом:

$\neg { 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) = \neg ( { \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 } , \dots ,x^ { \sigma_n } ) = 0 } $ $(\neg { x_1^ { \sigma_1 } } \vee \neg { x_2^ { \sigma_2 } } \vee \dots \vee \neg { x_n^ { \sigma_n } } ) $

Последнее выражение и является СКНФ. Так как СКНФ получена из СДНФ, которая может быть построена для любой функции, не равной тождественному нулю, то теорема доказана.

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

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

Пример построения СКНФ для медианы

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

x	y	z	$ \langle x,y,z \rangle $
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	$ \langle x,y,z \rangle $
0	0	0	0	$( x \lor y \lor z)$
0	0	1	0	$( x \lor y \lor \neg { z } )$
0	1	0	0	$(x \lor \neg { y } \lor z)$
0	1	1	1
1	0	0	0	$(\neg { x } \lor y \lor z)$
1	0	1	1
1	1	0	1
1	1	1	1

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

$ \langle x,y,z \rangle = ( x \lor y \lor z) \land (\neg { x } \lor y \lor z) \land (x \lor \neg { y } \lor z) \land ( x \lor y \lor \neg { z } )$

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

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

Исключающее или: $ x \oplus y \oplus z = (\neg { x } \lor \neg { y } \lor z) \land (\neg { x } \lor y \lor \neg { z } ) \land (x \lor \neg { y } \lor \neg { z } ) \land (x \lor y \lor z)$