Изменения

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

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

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

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

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

| <tex> x </tex>|| <tex> y </tex>|| <tex> z </tex>|| <tex> \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>, то в конъюнкцию включаем саму переменную, иначе ее отрицание.

| <tex> x </tex>|| <tex> y </tex>|| <tex> z </tex>|| <tex> \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> \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 {x_4} \land x_5) \lor (\overline{zx_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> x \oplus y \oplus z = (\overline{x} \lor land \overline{y} \lor land z) \land lor (\overline{x} \lor land y \lor land \overline{z}) \land lor (x \lor land \overline{y} \lor land \overline{z}) \land lor (x \lor land y \lor land z)</tex>.

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