Изменения

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

Элементарная Простая конъюнкция* '''правильная''', если в неё каждая переменная входит не более одного раза (включая отрицание);* '''полная''', если в неё каждая переменная (или её отрицание) входит ровно <tex> 1 </tex> раз;

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

<tex>f(x,y,z) = (x \land y) \lor (y \land \overlineneg {z})</tex> ДНФ может быть преобразована к эквивалентной ей КНФ путём раскрытия скобок по правилу: <tex>a\lor b c\to (a \lor b)(a \lor c)</tex>, которое выражает дистрибутивность дизъюнкции относительно конъюнкции. После этого необходимо в каждой дизъюнкции удалить повторяющиеся переменные или их отрицания, а также выбросить из конъюнкции все дизъюнкции, в которых встречается переменная вместе со своим отрицанием. При этом результатом не обязательно будет СКНФ, даже если исходная ДНФ была СДНФ. Точно также можно всегда перейти от КНФ к ДНФ. Для этого следует использовать правило <tex>a (b\lor c)\to a b\lor a c</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}) = \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,...,1,0) ~\vee~</tex>. # Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть <tex>x_1 \wedge x_2 \wedge ... \wedge x_{n-1} \wedge x_n \wedge f(1</tex>,1то в конъюнкцию включаем саму переменную,иначе ее отрицание.# Все полученные конъюнкции связываем операциями дизъюнкции..,1) </tex>

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

<center>{| class="wikitable" align="left" style="width:29cm10cm" border=1

! |<tex> x </tex>|| <tex> y </tex>|| <tex> z </tex>|| <tex>med(\langle x,y,z)\rangle </tex>|-align="center" bgcolor=#F0F0F0FFFFFF

|-align="center" bgcolor=#F0F0F0FFFFFF

|-align="center" bgcolor=#F0F0F0FFFFFF

|-align="center" bgcolor=#F0F0F0FFFFFF

|-align="center" bgcolor=#F0F0F0FFFFFF

|-align="center" bgcolor=#F0F0F0FFFFFF

|-align="center" bgcolor=#F0F0F0FFFFFF

|-align="center" bgcolor=#F0F0F0FFFFFF

2. Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть <tex> 1</tex>, то в конъюнкцию включаем саму переменную, иначе ее отрицание.

<center>{| class="wikitable" align="left" style="width:29cm16cm" border=1

| <tex> x </tex>|| <tex> y </tex>|| <tex> z </tex>|| <tex>med(\langle x,y,z)\rangle </tex> || |-align="center" bgcolor=#F0F0F0FFFFFF

|-align="center" bgcolor=#F0F0F0FFFFFF

|-align="center" bgcolor=#F0F0F0FFFFFF

|-align="center" bgcolor=#F0F0F0FFFFFF! 0 || 1 || 1 || 1 || <tex>(\overlineneg {x} \land y \land z)</tex>|-align="center" bgcolor=#F0F0F0FFFFFF

|-align="center" bgcolor=#F0F0F0FFFFFF! 1 || 0 || 1 || 1 || <tex>(x \land \overlineneg {y} \land z)</tex>|-align="center" bgcolor=#F0F0F0FFFFFF! 1 || 1 || 0 || 1 || <tex>(x \land y \land \overlineneg {z})</tex>|-align="center" bgcolor=#F0F0F0FFFFFF

3. Все полученные конъюнкции связываем операциями дизъюнкции.:

<tex>med(\langle x,y,z) \rangle = (x \land y \land z) \lor (\overlineneg {x} \land y \land z) \lor (x \land \overlineneg {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{zx_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>.

== Ссылки См. также == * [[Сокращенная и минимальная ДНФ]]* [[КНФ]] ==Источники информации ==