Изменения

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

* '''полная''', если в неё каждая переменная (или её отрицание) входит ровно 1 один раз;

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

<tex>f(x,y,z) = (x \lor y) \land (y \lor \neg{z})</tex>

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

<tex>f(x,y,z) = (x \lor \overlineneg{y} \lor z) \land (x\lor y \lor \overlineneg{z})</tex> 

Поскольку инверсия функции <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}}, ... \ldots ,x^{\sigma_{n}}) = 0} (x_{1}^{\sigma_{1}} \wedge x_{2}^{\sigma_{2}} \wedge ... \ldots \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}}, ... \ldots ,x^{\sigma_{n}}) = 0} (x_{1}^{\sigma_{1}} \wedge x_{2}^{\sigma_{2}} \wedge ... \ldots \wedge x_{n}^{\sigma_{n}})} ) </tex>

<tex> f(\vec x) = \bigwedge\limits_{f(x^{\sigma_{1}}, x^{\sigma_{2}}, ... \ldots ,x^{\sigma_{n}}) = 0} ( \overlineneg{x_{1}^{\sigma_{1}}} \vee \overlineneg{x_{2}^{\sigma_{2}}} \vee ... \ldots \vee \overlineneg{x_{n}^{\sigma_{n}}} ) </tex>

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

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

== Пример построения СКНФ для медианы===== Построение СКНФ для медианы от трех аргументов ===1. В таблице истинности отмечаем те наборы переменных, на которых значение функции равно <tex>0</tex>.

| '''x ''' || '''y ''' || '''z ''' || <tex> \langle x,y,z \rangle </tex>

|-align="center" bgcolor=#F0F0F0FFF

|-align="center" bgcolor=#F0F0F0FFF

|-align="center" bgcolor=#F0F0F0FFF

|-align="center" bgcolor=#F0F0F0FFF

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

| '''x ''' || '''y ''' || '''z ''' || <tex> \langle x,y,z \rangle </tex> ||

! 0 || 0 || 1 || 0 || <tex>( x \lor y \lor \overlineneg{z})</tex>|-align="center" bgcolor=#F0F0F0! 0 || 1 || 0 || 0 || <tex>(x \lor \overline{y} \lor z)</tex>

! 1 || 0 || 0 || 0 || <tex>(\overlineneg{x} \lor y \lor z)</tex>|-align="center" bgcolor=#F0F0F0FFF

|-align="center" bgcolor=#F0F0F0FFF

|-align="center" bgcolor=#F0F0F0FFF

<tex> \langle x,y,z \rangle = ( x \lor y \lor z) \land (\overlineneg{x} \lor y \lor z) \land (x \lor \overlineneg{y} \lor z) \land ( x \lor y \lor \neg{z})</tex> === Построение СКНФ для медианы от пяти аргументов === {| class="wikitable" style="width:16cm" border=1|+|-align="center" bgcolor=#EEEEFF|<tex> x_1 </tex>||<tex> x_2 </tex>||<tex> x_3 </tex>||<tex>x_4</tex>||<tex> x_5 </tex>||<tex> \langle x_1, x_2, x_3, x_4, x_5 \rangle </tex> |||-align="center" bgcolor=#FFFFFF! 0 || 0 || 0 || 0 || 0 || 0 || <tex>(x_1 \lor x_2 \lor x_3 \lor x_4 \lor x_5)</tex>|-align="center" bgcolor=#FFFFFF! 0 || 0 || 0 || 0 || 1 || 0 || <tex>(x_1 \lor x_2 \lor x_3 \lor x_4 \lor \neg {x_5})</tex>|-align="center" bgcolor=#FFFFFF! 0 || 0 || 0 || 1 || 0 || 0 || <tex>(x_1 \lor x_2 \lor x_3 \lor \neg {x_4} \lor x_5)</tex>|-align="center" bgcolor=#FFFFFF! 0 || 0 || 0 || 1 || 1 || 0 || <tex>(x_1 \lor x_2 \lor x_3 \lor \neg {x_4} \lor \neg {x_5})</tex>|-align="center" bgcolor=#FFFFFF! 0 || 0 || 1 || 0 || 0 || 0 || <tex>(x_1 \lor x_2 \lor \neg {x_3} \lor x_4 \lor x_5)</tex>|-align="center" bgcolor=#FFFFFF! 0 || 0 || 1 || 0 || 1 || 0 || <tex>(x_1 \lor x_2 \lor \neg {x_3} \lor x_4 \lor \neg {x_5})</tex>|-align="center" bgcolor=#FFFFFF! 0 || 0 || 1 || 1 || 0 || 0 || <tex>(x_1 \lor x_2 \lor \neg {x_3} \lor \neg {x_4} \lor x_5)</tex>|-align="center" bgcolor=#FFFFFF| 0 || 0 || 1 || 1 || 1 || 1 |||-align="center" bgcolor=#FFFFFF! 0 || 1 || 0 || 0 || 0 || 0 || <tex>(x_1 \lor \neg {x_2} \lor x_3 \lor x_4 \lor x_5)</tex>|-align="center" bgcolor=#FFFFFF! 0 || 1 || 0 || 0 || 1 || 0 || <tex>(x_1 \lor \neg {x_2} \lor x_3 \lor x_4 \lor \neg {x_5})</tex>|-align="center" bgcolor=#FFFFFF! 0 || 1 || 0 || 1 || 0 || 0 || <tex>(x_1 \lor \neg {x_2} \lor x_3 \lor \neg {x_4} \lor x_5)</tex>|-align="center" bgcolor=#FFFFFF| 0 || 1 || 0 || 1 || 1 || 1 |||-align="center" bgcolor=#FFFFFF! 0 || 1 || 1 || 0 || 0 || 0 || <tex>(x_1 \lor \neg {x_2} \lor \neg {x_3} \lor x_4 \lor x_5)</tex>|-align="center" bgcolor=#FFFFFF| 0 || 1 || 1 || 0 || 1 || 1 |||-align="center" bgcolor=#FFFFFF| 0 || 1 || 1 || 1 || 0 || 1 |||-align="center" bgcolor=#FFFFFF| 0 || 1 || 1 || 1 || 1 || 1 |||-align="center" bgcolor=#FFFFFF! 1 || 0 || 0 || 0 || 0 || 0 || <tex>(\neg {x_1} \lor x_2 \lor x_3 \lor x_4 \lor x_5)</tex>|-align="center" bgcolor=#FFFFFF! 1 || 0 || 0 || 0 || 1 || 0 || <tex>(\neg {x_1} \lor x_2 \lor x_3 \lor x_4 \lor \neg {x_5})</tex>|-align="center" bgcolor=#FFFFFF! 1 || 0 || 0 || 1 || 0 || 0 || <tex>(\neg {x_1} \lor x_2 \lor x_3 \lor \neg {x_4} \lor x_5)</tex>|-align="center" bgcolor=#FFFFFF| 1 || 0 || 0 || 1 || 1 || 1 |||-align="center" bgcolor=#FFFFFF! 1 || 0 || 1 || 0 || 0 || 0 || <tex>(\neg {x_1} \lor x_2 \lor \neg {x_3} \lor x_4 \lor x_5)</tex>|-align="center" bgcolor=#FFFFFF| 1 || 0 || 1 || 0 || 1 || 1 |||-align="center" bgcolor=#FFFFFF| 1 || 0 || 1 || 1 || 0 || 1 |||-align="center" bgcolor=#FFFFFF| 1 || 0 || 1 || 1 || 1 || 1 |||-align="center" bgcolor=#FFFFFF! 1 || 1 || 0 || 0 || 0 || 0 || <tex>(\neg {x_1} \lor \neg {x_2} \lor x_3 \lor x_4 \lor x_5)</tex>|-align="center" bgcolor=#FFFFFF| 1 || 1 || 0 || 0 || 1 || 1 |||-align="center" bgcolor=#FFFFFF| 1 || 1 || 0 || 1 || 0 || 1 |||-align="center" bgcolor=#FFFFFF| 1 || 1 || 0 || 1 || 1 || 1 |||-align="center" bgcolor=#FFFFFF| 1 || 1 || 1 || 0 || 0 || 1 |||-align="center" bgcolor=#FFFFFF| 1 || 1 || 1 || 0 || 1 || 1 |||-align="center" bgcolor=#FFFFFF| 1 || 1 || 1 || 1 || 0 || 1 |||-align="center" bgcolor=#FFFFFF| 1 || 1 || 1 || 1 || 1 || 1 |||} <tex> \langle x_1, x_2, x_3, x_4, x_5 \rangle = (x_1 \lor x_2 \lor x_3 \lor x_4 \lor x_5) \land (x_1 \lor x_2 \lor x_3 \lor x_4 \lor \overline {x_5}) \land \\ (x_1 \lor x_2 \lor x_3 \lor \overline {x_4} \lor x_5) \land (x_1 \lor x_2 \lor x_3 \lor \overline {x_4} \lor \overline {x_5}) \land (x_1 \lor x_2 \lor \overline {x_3} \lor x_4 \lor x_5) \land \\ (x_1 \lor x_2 \lor \overline {x_3} \lor x_4 \lor \overline {x_5}) \land (x_1 \lor x_2 \lor \overline {x_3} \lor \overline {x_4} \lor x_5) \land (x_1 \lor \overline {x_2} \lor x_3 \lor x_4 \lor x_5) \land \\ (x_1 \lor \overline {x_2} \lor x_3 \lor x_4 \lor \overline {x_5}) \land (x_1 \lor \overline {x_2} \lor x_3 \lor \overline {x_4} \lor x_5) \land (x_1 \lor \overline {x_2} \lor \overline {x_3} \lor x_4 \lor x_5) \land (\overline {x_1} \lor x_2 \lor x_3 \lor x_4 \lor x_5) \land (\overline{zx_1} \lor x_2 \lor x_3 \lor x_4 \lor \overline {x_5}) \land (\overline {x_1} \lor x_2 \lor x_3 \lor \overline {x_4} \lor x_5) \land (\overline {x_1} \lor x_2 \lor \overline {x_3} \lor x_4 \lor x_5) \land (\overline {x_1} \lor \overline {x_2}\lor x_3 \lor x_4 \lor x_5)</tex>

Стрелка Пирса: <tex> x \downarrow y = (\overlineneg{x} \lor {y}) \land ({x } \lor \overlineneg {y}) \land (\overlineneg {x} \lor \overlineneg {y})</tex>

== Ссылки См. также == * [[Специальные формы КНФ]]* [[ДНФ]] == Источники информации ==* [http://ru.wikipedia.org/wiki/%D0%A1%D0%9A%D0%9D%D0%A4 Википедия {{---}} СКНФ — Википедия]* [http://dvo.sut.ru/libr/himath/w163rabk/index.htm Е.Л Рабкин, Ю.Б. Фарфоровская — {{---}} Дискретная математика]