Изменения

== Определение КНФ ==

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

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

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

<tex>f(x,y,z) = (x \lor y) \land (y \lor \overlineneg{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>, выражающее дистрибутивность дизъюнкции относительно конъюнкции. Результат нужно преобразовать описанным выше способом, заменив слово «конъюнкция» на «дизъюнкция» и наоборот.

'''Совершенная конъюнктивная нормальная форма, СКНФ ''' (Совершенная Конъюнктивная Нормальная Форма)англ. ''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>.

<center>{| class="wikitable" align="left" style="width:29cm10cm" border=1

| '''x ''' || '''y ''' || '''z ''' || <xyztex> \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>, то в дизъюнкцию включаем саму переменную, иначе ее отрицание.

<center>{| class="wikitable" align="left" style="width:29cm16cm" border=1

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

| ! 0 || 0 || 0 || 0 || <tex>( x \lor y \lor z)</tex>

| ! 0 || 0 || 1 || 0 || <tex>( x \lor y \lor \overlineneg{z})</tex>

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

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

<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>f(x,y,z) = ( x \lor y \lor z) \land (\overline{x} \lor y \lor z) \land (x \lor \overline{y} \lor z) \land ( x \lor y \lor \overline{z})</tex>Дискретная математика и алгоритмы]]

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