Изменения
КНФ
,→СКНФ
|definition =
СКНФ (Совершенная Конъюнктивная Нормальная Форма)''' — это такая КНФ, которая удовлетворяет условиям:
* в ней нет одинаковых элементарных простых дизъюнкций* в каждой дизъюнкции нет одинаковых переменных* каждая элементарная простая дизъюнкция содержит каждый из аргументов функции.полная
}}
Пример СКНФ:
<tex>f(x,y,z) = (x \lor \overlineneg{y} \lor z) \land (x\lor y \lor \overlineneg{z})</tex>
Для любой булевой функции <tex>f(\vec{x})</tex>, не равной тождественной единице, существует СКНФ, ее задающая.
|proof =
Поскольку инверсия функции <tex>\overlineneg{f}(\vec x)</tex> равна единице на тех наборах, на которых <tex>f(\vec x)</tex> равна нулю, то СДНФ для <tex>\overlineneg{f}(\vec x)</tex> можно записать следующим образом:<tex> \overlineneg{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}}) </tex>, где <tex> \sigma_{i} </tex> обозначает наличие или отсутствие отрицание при <tex> x_{i} </tex>
Найдём инверсию левой и правой части выражения:
<tex> f(\vec x) = \overlineneg{\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}})} </tex>
Применяя дважды к полученному в правой части выражению правило де Моргана, получаем:
<tex> f(\vec x) = \bigwedge\limits_{f(x^{\sigma_{1}}, x^{\sigma_{2}}, ... ,x^{\sigma_{n}}) = 0} ( \overlineneg{x_{1}^{\sigma_{1}}} \vee \overlineneg{x_{2}^{\sigma_{2}}} \vee ... \vee \overlineneg{x_{n}^{\sigma_{n}}} ) </tex>
Последнее выражение и является СКНФ. Так как СКНФ получена из СДНФ, которая может быть посторена для любой функции, то теорема доказана.
