Изменения

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

Элементарная Простая дизъюнкция* '''правильная''', если в неё каждая переменная входит не более одного раза (включая отрицание);* '''полная''', если в неё каждая переменная (или её отрицание) входит ровно 1 один раз;

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

<tex>f(x,y) = (x \lor y) \land (y \lor \overline{z})</tex> КНФ может быть преобразована к эквивалентной ей ДНФ путём раскрытия скобок по правилу: <tex>a (b\lor c)\to a b\lor a c</tex>, которое выражает дистрибутивность конъюнкции относительно дизъюнкции. После этого необходимо в каждой конъюнкции удалить повторяющиеся переменные или их отрицания, а также выбросить из дизъюнкции все конъюнкции, в которых встречается переменная вместе со своим отрицанием. При этом результатом не обязательно будет СДНФ, даже если исходная КНФ была СКНФ. Точно также можно всегда перейти от ДНФ к КНФ. Для этого следует использовать правило <tex>a\lor b c\to (a \lor b)(a \lor c)</tex>, выражающее дистрибутивность дизъюнкции относительно конъюнкции. Результат нужно преобразовать описанным выше способом, заменив слово «конъюнкция» на «дизъюнкция» и наоборот. Например КНФ <tex>\to</tex> ДНФ: <tex>(x \lor y) \land (y \lor \overline{z}) = (x \land y) \lor y \lor (x \land \overline{z}) \lor (y \land \overline{z}) = y \land (x \lor 1 \lor \overline{z}) \lor (x \land \overline{z}) = (x \land \overline{z}) \lor y</tex> Например ДНФ <tex>\to</tex> КНФ: <tex> (x \land \overline{z}) \lor y = (x \lor y) \land (y \lor \overlineneg{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} (\neg{x_{1}^{\overline{\sigma_{1}}} \vee \neg{x_{2}^{\overline{\sigma_{2}}} \vee ... \ldots \vee \neg{x_{n}^{\overline{\sigma_{n}}}) </tex>

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

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

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

| '''x ''' || '''y ''' || '''z ''' || <tex>med(\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>med(\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>med(\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{zx_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 {x_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> Исключающее или: <tex> 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)</tex> == См. также == * [[Специальные формы КНФ]]* [[ДНФ]] == Источники информации ==* [http://ru.wikipedia.org/wiki/%D0%A1%D0%9A%D0%9D%D0%A4 Википедия {{---}} СКНФ]* [http://dvo.sut.ru/libr/himath/w163rabk/index.htm Е.Л Рабкин, Ю.Б. Фарфоровская {{---}} Дискретная математика]

Исключающее или[[Категория: <tex> x \oplus y \oplus z = (\overline{x} \land \overline{y} \land z) \lor (\overline{x} \land y \land \overline{z}) \lor (x \land \overline{y} \land \overline{z}) \lor (x \land y \land z)</tex>Дискретная математика и алгоритмы]]

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