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

КНФ

Простой дизъюнкцией{ англ. 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$.

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

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)$