Изменения

==Канонические формы логических формулДНФ ==Любая логическая формула задает некоторую [[булева функция|булеву функцию]]. Но для всякой [[булева функция|булевой функции]] можно привести бесконечно много формул ее представляющих. Одной из задач алгебры логики является построение '''канонических форм'''(т.е формул построенных по определенному правилу). 

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

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

|definition = Формула называется '''дизъюктивной нормальной формой (ДНФ) Совершенная дизъюнктивная нормальная форма, СДНФ''', если она является дизъюнкцией неповторяемых элементарных конъюнкций(англ.}} {{Определение|definition = Формула <tex>f(\vec{x})</tex> от n переменных называется ''perfect disjunctive normal form, PDNF'совершенно дизъюктивной нормальной формой (СДНФ) ''', если <tex>f(\vec x)</tex> является — ДНФ, удовлетворяющая условиям:* в которой ней нет одинаковых простых конъюнкций,* каждая элементарная простая конъюнкция есть конъюнкция <tex>n</tex> переменных <tex>x_1</tex>, <tex>x_2</tex>,...,<tex>x_n</tex>, причем на <tex>i</tex>-ом месте этой конъюнкции стоит <tex>i</tex>-ый термполная.

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

Для любой булевой функции выполняется следующее соотношение, называемое '''разложением Шеннона''':

<tex>f(\vec{x}) = \overline 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}) = \overline neg x_1 \wedge \overline neg x_2 \wedge ...\ldots \wedge \overline neg x_{n-1} \wedge \overline neg x_n \wedge f(0,0,...\ldots,0,0)~\vee~</tex>

<tex>\overline neg x_1 \wedge \overline neg x_2 \wedge ... \ldots \wedge \overline neg x_{n-1} \wedge x_n \wedge f(0,0,...\ldots,0,1) ~\vee~\\\ldots \\~\vee~ x_1 \wedge x_2 \wedge \ldots \wedge x_{n-1} \wedge \neg x_n \wedge f(1,1,\ldots,1,0) ~\vee~\\ x_1 \wedge x_2 \wedge \ldots \wedge x_{n-1} \wedge x_n \wedge f(1,1,\ldots,1) </tex>

Так как применение данного соотношения к каждой из переменных увеличивает количество конъюнктов в два раза, то для функции от <tex>n</tex> переменных мы имеем <tex>2^n</tex> конъюнктов.Каждый из них соответствует значению функции на одном из <tex>2^n</tex> возможных наборов значений <tex> n </tex> переменных.Если на некотором наборе <tex>f(\vec{x})=0</tex>, то весь соответствующий конъюнкт также равен нулю и из представления данной функции его можно исключить. Если же <tex> f(\vec{x})=1</tex>, то в соответствующем конъюнкте само значение функции можно опустить. В результате для произвольной функции была построена СДНФ.}}

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

== Пример построения СДНФ для медианы===== Построение СДНФ для медианы от трех аргументов ===1. В таблице истинности отмечаем те наборы переменных, на которых значение функции равно <tex>x_1 \wedge x_2 \wedge ... \wedge x_{n-1} \wedge x_n \wedge f(1,1,...,1) </tex>.

Т.к применение данного соотношения к каждой из переменных увеличивает количество дизъюнктивных членов в два раза, то для функции от {| class="wikitable" style="width:10cm" border=1|+|-align="center" bgcolor=#EEEEFF|<tex>nx </tex> переменных мы имеем ||<tex>2^ny </tex> дизъюнктивных членов. Каждый из них соответствует значению функции на одном из ||<tex>2^nz </tex> возможных наборов значений n переменных. Если на некотором наборе || <tex>f(\vec{langle x})=0,y,z \rangle </tex>, то весь соответствующий дизъюнктивный член также равен |-align="center" bgcolor=#FFFFFF| 0 || 0 || 0 || 0|-align="center" bgcolor=#FFFFFF| 0 || 0 || 1 || 0 и из представления данной функции его можно исключить. Если же <tex> f(\vec{x})|-align="center" bgcolor=#FFFFFF| 0 || 1</tex>, то в соответствующем дизъюннктивном члене само значение функции можно опустить. В результате для произвольной функции была построена '''СДНФ'''.|| 0 || 0|-align="center" bgcolor=#FFFFFF}}! 0 || 1 || 1 || 1|-align="center" bgcolor=Алгоритм построения СДНФ по таблице истинности#FFFFFF| 1 || 0 || 0 || 0|-align="center" bgcolor=#FFFFFF! 1 || 0 || 1 || 1|-align="center" bgcolor=# В таблице истинности отмечаем те наборы переменных, на которых значение функции равно FFFFFF! 1 || 1 || 0 || 1.|-align="center" bgcolor=# FFFFFF! 1 || 1 || 1 || 1|} 2. Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу : если значение некоторой переменной есть <tex> 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>|-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>(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>(x_1 \land \neg {x_2} \land x_3 \land x_4 \land \neg {x_5})</tex>|-align="center" bgcolor=#FFFFFF! 1 || 0 || 1 || 1 || 1 || 1 || <tex>(x_1 \land \neg {x_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>(x_1 \land x_2 \land \neg {x_3} \land x_4 \land \neg {x_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 = (\neg {x} \land \neg {y})</tex>. Исключающее или: <tex> 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 z)</tex>. == См. также == * [[Сокращенная и минимальная ДНФ]]* [[КНФ]] ==Источники информации ==* [http://ru.wikipedia.org/wiki/%D0%A1%D0%94%D0%9D%D0%A4 СДНФ — Википедия]* [http://dvo.sut.ru/libr/himath/w163rabk/index.htm Е.Л Рабкин, Ю.Б. Фарфоровская — Дискретная математика] [[Категория: Дискретная математика и алгоритмы]] [[Категория: Булевы функции ]]