Изменения

'''Простой конъюнкцией''' (англ. ''inclusive conjunction'') или '''конъюнктом''' (англ. ''conjunct'') называется конъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная встречается не более одного раза.}}Простая конъюнкция* '''полная''', если в неё каждая переменная (или её отрицание) входит ровно <tex> 1 </tex> раз;* '''монотонная''', если она не содержит отрицаний переменных. {{Определение|definition ='''Дизъюнктивная нормальная форма, ДНФ ''' (Дизъюнктивная Нормальная Формаангл. ''disjunctive normal form, DNF'') — {{---}} нормальная форма, в которой [[Определение булевой функции|булева функция]] имеет вид дизъюнкции нескольких простых конъюнктов.

<tex>f(x,y,z) = (x \land y) \lor (y \land \overlineneg {z})</tex>.

'''Совершенная дизъюнктивная нормальная форма, СДНФ ''' (Совершенная Дизъюнктивная Нормальная Форма)англ. ''perfect disjunctive normal form, PDNF'' ) — это такая ДНФ, которая удовлетворяет удовлетворяющая условиям:* в ней нет одинаковых элементарных простых конъюнкций* в каждой конъюнкции нет одинаковых переменных,* каждая элементарная простая конъюнкция содержит каждый из аргументов функцииполная.

<tex>f(x,y,z) = (x \land \overlineneg {y} \land z) \lor (x \land y \land \overlineneg {z})</tex>. 

Для любой булевой функции <tex>f(\vec{x})</tex>, не равной тождественному нулю, существует СДНФ, ее задающая.

Для любой булевой функции выполняется следующее соотношение, называемое '''разложением Шеннона''': <tex>f(\vec{x}) = \neg x_i \wedge f(x_1, \ldots ,x_{i-1},0,x_{i+1}, \ldots ,x_n) \veex_i \wedge f(x_1, \ldots ,x_{i-1},1,x_{i+1}, \ldots ,x_n)</tex>. Данное соотношение легко проверить подстановкой возможных значений <tex>x_i</tex> (<tex>0</tex> и <tex>1</tex>). Эта формула позволяет выносить <tex>x_i</tex> за знак функции. Последовательно вынося <tex>x_1</tex>, <tex>x_2</tex>,.., <tex>x_n</tex> за знак <tex>f(\vec{x})</tex>, получаем следующую формулу: <tex> f(\vec{x}) = \neg x_1 \wedge \neg x_2 \wedge \ldots \wedge \neg x_{n-1} \wedge \neg x_n \wedge f(0,0,\ldots,0,0)~\vee~</tex>

<tex>f(\vecneg x_1 \wedge \neg x_2 \wedge \ldots \wedge \neg x_{xn-1}) = \overline x_i wedge x_n \wedge f(x_10,0,..\ldots,0,1) ~\vee~ \\\ldots \\~\vee~ x_1 \wedge x_2 \wedge \ldots \wedge x_{in-1}\wedge \neg x_n \wedge f(1,1,0\ldots,x_{i+1},..,x_n0) ~\vee~\\ x_i x_1 \wedge x_2 \wedge \ldots \wedge f(x_1,..,x_{in-1}\wedge x_n \wedge f(1,1,x_{i+\ldots,1},x_n)</tex>

Данное соотношение легко проверить подстановкой всевозможных значений Так как применение данного соотношения к каждой из переменных увеличивает количество конъюнктов в два раза, то для функции от <tex>x_in</tex> (переменных мы имеем <tex>02^n</tex> и <tex>1</tex>)конъюнктов. Эта формула позволяет выносить <tex>x_i</tex> за знак Каждый из них соответствует значению функции. Последовательно вынося на одном из <tex>x_12^n</tex>, возможных наборов значений <tex>x_2n </tex>,переменных.., <tex>x_n</tex> за знак Если на некотором наборе <tex>f(\vec{x})=0</tex>, получаем следующую формулу : то весь соответствующий конъюнкт также равен нулю и из представления данной функции его можно исключить. Если же <tex> f(\vec{x}) = \overline x_1 \wedge \overline x_2 \wedge ...\wedge \overline x_{n-1} \wedge \overline x_n \wedge f(0,0,...,0,0)~\vee~</tex>, то в соответствующем конъюнкте само значение функции можно опустить. В результате для произвольной функции была построена СДНФ.}}

== Алгоритм построения СДНФ по таблице истинности ==# В таблице истинности отмечаем те наборы переменных, на которых значение функции равно <tex>\overline x_1 \wedge \overline x_2 \wedge ... \wedge \overline x_{n-1} \wedge x_n \wedge f(0,0,</tex>...,0,# Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть <tex> 1) ~\vee~</tex>, то в конъюнкцию включаем саму переменную, иначе ее отрицание.# Все полученные конъюнкции связываем операциями дизъюнкции.

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

{| class="wikitable" style="width:10cm" border=1|+|-align="center" bgcolor=#EEEEFF|<tex> x </tex>||<tex> y </tex>||<tex> z </tex>|| <tex>~\vee~ x_1 langle x,y,z \wedge x_2 \wedge ... \wedge x_{nrangle </tex>|-align="center" bgcolor=#FFFFFF| 0 || 0 || 0 || 0|-align="center" bgcolor=#FFFFFF| 0 || 0 || 1 || 0|-align="center" bgcolor=#FFFFFF| 0 || 1 || 0 || 0|-align="center" bgcolor=#FFFFFF! 0 || 1 || 1 || 1|-align="center" bgcolor=#FFFFFF| 1 || 0 || 0 || 0|-align="center" bgcolor=#FFFFFF! 1} \wedge \overline x_n \wedge f(|| 0 || 1 || 1,|-align="center" bgcolor=#FFFFFF! 1,...,|| 1,|| 0) ~\vee~</tex>|| 1|-align="center" bgcolor=#FFFFFF! 1 || 1 || 1 || 1|}

2. Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть <tex>x_1 \wedge x_2 \wedge ... \wedge x_{n-1} \wedge x_n \wedge f(1,1,...,1) </tex>, то в конъюнкцию включаем саму переменную, иначе ее отрицание.

Т{| class="wikitable" style="width:16cm" border=1|+|-align="center" bgcolor=#EEEEFF|<tex> x </tex>||<tex> y </tex>||<tex> z </tex>|| <tex> \langle x,y,z \rangle </tex> || |-align="center" bgcolor=#FFFFFF| 0 || 0 || 0 || 0 |||-align="center" bgcolor=#FFFFFF| 0 || 0 || 1 || 0 |||-align="center" bgcolor=#FFFFFF| 0 || 1 || 0 || 0 |||-align="center" bgcolor=#FFFFFF! 0 || 1 || 1 || 1 || <tex>(\neg {x} \land y \land z)</tex>|-align="center" bgcolor=#FFFFFF| 1 || 0 || 0 || 0 |||-align="center" bgcolor=#FFFFFF! 1 || 0 || 1 || 1 || <tex>(x \land \neg {y} \land z)</tex>|-align="center" bgcolor=#FFFFFF! 1 || 1 || 0 || 1 || <tex>(x \land y \land \neg {z})</tex>|-align="center" bgcolor=#FFFFFF! 1 || 1 || 1 || 1 || <tex>(x \land y \land z)</tex>|} 3.к применение данного соотношения к каждой из переменных увеличивает количество дизъюнктивных членов в два разаВсе полученные конъюнкции связываем операциями дизъюнкции: <tex> \langle x,y, то z \rangle = (x \land y \land z) \lor (\neg {x} \land y \land z) \lor (x \land \neg {y} \land z) \lor (x \land y \land \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 |||-align="center" bgcolor=#FFFFFF| 0 || 0 || 0 || 0 || 1 || 0 |||-align="center" bgcolor=#FFFFFF| 0 || 0 || 0 || 1 || 0 || 0 |||-align="center" bgcolor=#FFFFFF| 0 || 0 || 0 || 1 || 1 || 0 |||-align="center" bgcolor=#FFFFFF| 0 || 0 || 1 || 0 || 0 || 0 |||-align="center" bgcolor=#FFFFFF| 0 || 0 || 1 || 0 || 1 || 0 |||-align="center" bgcolor=#FFFFFF| 0 || 0 || 1 || 1 || 0 || 0 |||-align="center" bgcolor=#FFFFFF! 0 || 0 || 1 || 1 || 1 || 1 || <tex>(\neg {x_1} \land \neg {x_2} \land x_3 \land x_4 \land x_5)</tex>|-align="center" bgcolor=#FFFFFF| 0 || 1 || 0 || 0 || 0 || 0 |||-align="center" bgcolor=#FFFFFF| 0 || 1 || 0 || 0 || 1 || 0 |||-align="center" bgcolor=#FFFFFF| 0 || 1 || 0 || 1 || 0 || 0 |||-align="center" bgcolor=#FFFFFF! 0 || 1 || 0 || 1 || 1 || 1 || <tex>(\neg {x_1} \land x_2 \land \neg {x_3} \land x_4 \land x_5)</tex>|-align="center" bgcolor=#FFFFFF| 0 || 1 || 1 || 0 || 0 || 0 |||-align="center" bgcolor=#FFFFFF! 0 || 1 || 1 || 0 || 1 || 1 || <tex>(\neg {x_1} \land x_2 \land x_3 \land \neg {x_4} \land x_5)</tex>|-align="center" bgcolor=#FFFFFF! 0 || 1 || 1 || 1 || 0 || 1 || <tex>(\neg {x_1} \land x_2 \land x_3 \land x_4 \land \neg {x_5})</tex>|-align="center" bgcolor=#FFFFFF! 0 || 1 || 1 || 1 || 1 || 1 || <tex>(\neg {x_1} \land x_2 \land x_3 \land x_4 \land x_5)</tex>n|-align="center" bgcolor=#FFFFFF| 1 || 0 || 0 || 0 || 0 || 0 |||-align="center" bgcolor=#FFFFFF| 1 || 0 || 0 || 0 || 1 || 0 |||-align="center" bgcolor=#FFFFFF| 1 || 0 || 0 || 1 || 0 || 0 |||-align="center" bgcolor=#FFFFFF! 1 || 0 || 0 || 1 || 1 || 1 || <tex>(x_1 \land \neg {x_2} \land \neg {x_3} \land x_4 \land x_5)</tex> переменных мы имеем |-align="center" bgcolor=#FFFFFF| 1 || 0 || 1 || 0 || 0 || 0 |||-align="center" bgcolor=#FFFFFF! 1 || 0 || 1 || 0 || 1 || 1 || <tex>2^n(x_1 \land \neg {x_2} \land x_3 \land \neg {x_4} \land x_5)</tex> дизъюнктивных членов. Каждый из них соответствует значению функции на одном из |-align="center" bgcolor=#FFFFFF! 1 || 0 || 1 || 1 || 0 || 1 || <tex>2^n(x_1 \land \neg {x_2} \land x_3 \land x_4 \land \neg {x_5})</tex> возможных наборов значений n переменных. Если на некотором наборе |-align="center" bgcolor=#FFFFFF! 1 || 0 || 1 || 1 || 1 || 1 || <tex>f(x_1 \vecland \neg {xx_2}\land x_3 \land x_4 \land x_5)</tex>|-align="center" bgcolor=#FFFFFF| 1 || 1 || 0 || 0 || 0|| 0 |||-align="center" bgcolor=#FFFFFF! 1 || 1 || 0 || 0 || 1 || 1 || <tex>(x_1 \land x_2 \land \neg {x_3} \land \neg {x_4} \land x_5)</tex>, то весь соответствующий дизъюнктивный член также равен нулю и из представления данной функции его можно исключить. Если же |-align="center" bgcolor=#FFFFFF! 1 || 1 || 0 || 1 || 0 || 1 || <tex> f(x_1 \land x_2 \land \neg {x_3} \land x_4 \land \vecneg {xx_5})</tex>|-align="center" bgcolor=#FFFFFF! 1|| 1 || 0 || 1 || 1 || 1 || <tex>(x_1 \land x_2 \land \neg {x_3} \land x_4 \land x_5)</tex>, то в соответствующем дизъюннктивном члене само значение функции можно опустить. В результате для произвольной функции была построена СДНФ.|-align="center" bgcolor=#FFFFFF! 1 || 1 || 1 || 0 || 0 || 1 || <tex>(x_1 \land x_2 \land x_3 \land \neg {x_4}\land \neg {x_5})</tex>|-align="center" bgcolor=Алгоритм построения СДНФ по таблице истинности#FFFFFF! 1 || 1 || 1 || 0 || 1 || 1 || <tex>(x_1 \land x_2 \land x_3 \land \neg {x_4} \land x_5)</tex>|-align="center" bgcolor=#FFFFFF* В таблице истинности отмечаем те наборы переменных, на которых значение функции равно ! 1 || 1 || 1 || 1 || 0 || 1.|| <tex>(x_1 \land x_2 \land x_3 \land x_4 \land \neg {x_5})</tex>|-align="center" bgcolor=#FFFFFF* Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу : если значение некоторой переменной есть ! 1 || 1 || 1 || 1 || 1 || 1|| <tex>(x_1 \land x_2 \land x_3 \land x_4 \land x_5)</tex>|} <tex> \langle x_1, x_2, x_3, то в конъюнкцию включаем саму переменнуюx_4, иначе ее отрицание.* Все полученные конъюнкции связываем операциями дизъюнкцииx_5 \rangle = (\overline {x_1} \land \overline {x_2} \land x_3 \land x_4 \land x_5) \lor (\overline {x_1} \land x_2 \land \overline {x_3} \land x_4 \land x_5) \lor (\overline {x_1} \land x_2 \land x_3 \land \overline {x_4} \land x_5) \lor (\overline {x_1} \land x_2 \land x_3 \land x_4 \land \overline {x_5}) \lor (\overline {x_1} \land x_2 \land x_3 \land x_4 \land x_5) \lor (x_1 \land \overline {x_2} \land \overline {x_3} \land x_4 \land x_5) \lor (x_1 \land \overline {x_2} \land x_3 \land \overline {x_4} \land x_5) \lor (x_1 \land \overline {x_2} \land x_3 \land x_4 \land \overline {x_5}) \lor (x_1 \land \overline {x_2} \land x_3 \land x_4 \land x_5) \lor (x_1 \land x_2 \land \overline {x_3} \land \overline {x_4} \land x_5) \lor (x_1 \land x_2 \land \overline {x_3} \land x_4 \land \overline {x_5}) \lor (x_1 \land x_2 \land \overline {x_3} \land x_4 \land x_5) \lor (x_1 \land x_2 \land x_3 \land \overline {x_4} \land \overline {x_5}) \lor (x_1 \land x_2 \land x_3 \land \overline {x_4} \land x_5) \lor (x_1 \land x_2 \land x_3 \land x_4 \land \overline {x_5}) \lor (x_1 \land x_2 \land x_3 \land x_4 \land x_5)</tex>.

Стрелка Пирса: <tex> x \downarrow y = (\overlineneg {x} \land \overlineneg {y})</tex>.

Медиана трёхИсключающее или: <tex>f(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 \overline{z})</tex>.

== Ссылки См. также == * [[Сокращенная и минимальная ДНФ]]* [[КНФ]] ==Источники информации ==* [http://ru.wikipedia.org/wiki/%D0%A1%D0%94%D0%9D%D0%A4 СДНФ — Википедия — свободная энциклопедия]

== Пример построения СДНФ ==[[Категория: Дискретная математика и алгоритмы]] [[Категория: Булевы функции ]]