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