ДНФ

2012-03-14T22:29:58Z

178.178.30.201: /* СДНФ */

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

{{Определение
|definition =
ДНФ (Дизъюнктивная Нормальная Форма) — нормальная форма, в которой [[Определение булевой функции|булева функция]] имеет вид дизъюнкции нескольких простых конъюнктов.
}}
Пример ДНФ:
<tex>f(x,y) = (x \land y) \lor (y \land \neg {z})</tex>

== СДНФ ==
{{Определение
|definition =
СДНФ (Совершенная Дизъюнктивная Нормальная Форма)''' — это такая ДНФ, которая удовлетворяет условиям:
* в ней нет одинаковых простых конъюнкций
* каждая простая конъюнкция полная
}}
Пример СДНФ:
<tex>f(x,y,z) = (x \land \neg {y} \land z) \lor (x \land y \land \neg {z})</tex>

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

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

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

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

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

{| class="wikitable" style="width:10cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
| x || y || z || <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
|-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. Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть 1, то в конъюнкцию включаем саму переменную, иначе ее отрицание.

{| class="wikitable" style="width:16cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
| x || y || z || <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>

==Примеры СДНФ для некоторых функций==
Стрелка Пирса: <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 Е.Л Рабкин, Ю.Б. Фарфоровская — Дискретная математика]

[[Категория: Дискретная математика и алгоритмы]]

[[Категория: Булевы функции ]]

Викиконспекты - Вклад участника [ru]

ДНФ