Изменения

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

<tex>f(x,y,z) = (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>.* {| class="wikitable" style="width:10cm" border=1|+|-align="center" bgcolor=#EEEEFF| '''x''' || '''y''' || '''z''' || <tex> \langle x,y,z \rangle </tex>|-align="center" bgcolor=#F0F0F0! 0 || 0 || 0 || 0|-align="center" bgcolor=#F0F0F0! 0 || 0 || 1 || 0|-align="center" bgcolor=#F0F0F0! 0 || 1 || 0 || 0|-align="center" bgcolor=#FFF| 0 || 1 || 1 || 1|-align="center" bgcolor=#F0F0F0! 1 || 0 || 0 || 0|-align="center" bgcolor=#FFF| 1 || 0 || 1 || 1|-align="center" bgcolor=#FFF| 1 || 1 || 0 || 1|-align="center" bgcolor=#FFF| 1 || 1 || 1 || 1|} 2. Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу : если значение некоторой переменной есть <tex>0</tex>, то в дизъюнкцию включаем саму переменную, иначе ее отрицание. * {| class="wikitable" style="width:16cm" border=1|+|-align="center" bgcolor=#EEEEFF| '''x''' || '''y''' || '''z''' || <tex> \langle x,y,z \rangle </tex> || |-align="center" bgcolor=#F0F0F0! 0 || 0 || 0 || 0 || <tex>( x \lor y \lor z)</tex>|-align="center" bgcolor=#F0F0F0! 0 || 0 || 1 || 0 || <tex>( x \lor y \lor \neg{z})</tex>|-align="center" bgcolor=#F0F0F0! 0 || 1 || 0 || 0 || <tex>(x \lor \neg{y} \lor z)</tex>|-align="center" bgcolor=#FFF| 0 || 1 || 1 || 1 || |-align="center" bgcolor=#F0F0F0! 1 || 0 || 0 || 0 || <tex>(\neg{x} \lor y \lor z)</tex>|-align="center" bgcolor=#FFF| 1 || 0 || 1 || 1 || |-align="center" bgcolor=#FFF| 1 || 1 || 0 || 1 || |-align="center" bgcolor=#FFF| 1 || 1 || 1 || 1 || |} 3. Все полученные дизъюнкции связываем операциями конъюнкции. <tex> \langle x,y,z \rangle = ( x \lor y \lor z) \land (\neg{x} \lor y \lor z) \land (x \lor \neg{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 {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 Википедия — свободная энциклопедияБулевы функции ]]