Изменения

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

<mathtex>f(x,y,z) = (x \lor y) \land (y \lor \neg{z})</tex> == СКНФ == {{Определение|definition ='''Совершенная конъюнктивная нормальная форма, СКНФ''' (англ. ''perfect conjunctive normal form, PCNF'') — это такая КНФ, которая удовлетворяет условиям:* в ней нет одинаковых простых дизъюнкций* каждая простая дизъюнкция полная}}Пример СКНФ:<tex>f(x,y,z) = (x \or lor \neg{y} \lor z) \and land (x\lor y \or lor \neg {z})</mathtex> 

''' {{Теорема|statement=Для любой булевой функции <tex>f(\vec{x})</tex>, не равной тождественной единице, существует СКНФ , ее задающая.|proof = Поскольку инверсия функции <tex>\neg{f}(Совершенная Конъюнктивная Нормальная Форма\vec x)''' — это такая КНФ</tex> равна единице на тех наборах, которая удовлетворяет условиямна которых <tex>f(\vec x)</tex> равна нулю, то СДНФ для <tex>\neg{f}(\vec x)</tex> можно записать следующим образом:* в ней нет одинаковых элементарных дизъюнкций* в каждой дизъюнкции нет одинаковых переменных* каждая элементарная дизъюнкция содержит каждую из входящих в данную КНФ переменных.<tex>\neg{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) = \neg ({\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}^{\sigma_{1}}} \vee \neg{x_{2}^{\sigma_{2}}} \vee \ldots \vee \neg{x_{n}^{\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''' || <mathtex> \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 \or 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 } \or lor z) </tex>|-align="center" bgcolor=#FFF| 0 || 1 || 1 || 1 || |-align="center" bgcolor=#F0F0F0! 1 || 0 || 0 || 0 || <tex>(\and 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\or lor y \or lor \neg {z})</mathtex> === Построение СКНФ для медианы от пяти аргументов === {| 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, если она в наборе равна 0x_3, и с инверсиейx_4, если она равна 1. *Полученные дизъюнкции связываем операциями конъюнкции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>

Стрелка Пирса: <mathtex>x \downarrow y = (\neg {x } \or lor {y}) \and land ({x } \or lor \neg {y}) \and land (\neg {x } \or lor \neg {y})</mathtex> Исключающее или: <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 Е.Л Рабкин, Ю.Б. Фарфоровская {{---}} Дискретная математика] [[Категория: Дискретная математика и алгоритмы]]

Медиана трёх[[Категория: <math>( x \or y \or z) \and (\neg x \or y \or z) \and (x \or \neg y \or z) \and ( x \or y \or \neg z)</math>Булевы функции ]]