19
правок
Изменения
ДНФ
,Исправил замечания
}}
Простая конъюнкция
* '''полная''', если в неё каждая переменная (или её отрицание) входит ровно <tex> 1 </tex> раз;
* '''монотонная''', если она не содержит отрицаний переменных.
}}
Пример ДНФ:
<tex>f(x,y,z) = (x \land y) \lor (y \land \neg {z})</tex>.
== СДНФ ==
{{Определение
|definition =
'''Совершенная дизъюнктивная нормальная форма, СДНФ''' (англ. ''perfect disjunctive normal form, PDNF'') — это такая ДНФ, которая удовлетворяет удовлетворяющая условиям:* в ней нет одинаковых простых конъюнкций,* каждая простая конъюнкция полная.
}}
Пример СДНФ:
<tex>f(x,y,z) = (x \land \neg {y} \land z) \lor (x \land y \land \neg {z})</tex>.
Для любой булевой функции <tex>f(\vec {x})</tex>, не равной тождественному нулю, существует СДНФ, ее задающая.
|proof =
Для любой булевой функции выполняется следующее соотношение, называемое '''разложением Шеннона'''.:
<tex>f(\vec{x}) = \neg x_i \wedge f(x_1, \dots ,x_{i-1},0,x_{i+1}, \dots ,x_n) \vee
x_i \wedge f(x_1, \dots ,x_{i-1},1,x_{i+1}, \dots ,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> 1</tex>.# Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть <tex> 1</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> \langle x,y,z \rangle </tex>
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 0 || 0
|}
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 ||
|}
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 Е.Л Рабкин, Ю.Б. Фарфоровская — Дискретная математика]
