Изменения

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

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

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