ДНФ
| Определение: |
| Простой конъюнкцией (англ. inclusive conjunction) или конъюнктом (англ. conjunct) называется конъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная встречается не более одного раза. |
Простая конъюнкция
- полная, если в неё каждая переменная (или её отрицание) входит ровно [math] 1 [/math] раз;
- монотонная, если она не содержит отрицаний переменных.
| Определение: |
| Дизъюнктивная нормальная форма, ДНФ (англ. disjunctive normal form, DNF) — нормальная форма, в которой булева функция имеет вид дизъюнкции нескольких простых конъюнктов. |
Пример ДНФ:
[math]f(x,y,z) = (x \land y) \lor (y \land \neg {z})[/math].
СДНФ
| Определение: |
Совершенная дизъюнктивная нормальная форма, СДНФ (англ. perfect disjunctive normal form, PDNF) — ДНФ, удовлетворяющая условиям:
- в ней нет одинаковых простых конъюнкций,
- каждая простая конъюнкция полная.
|
Пример СДНФ:
[math]f(x,y,z) = (x \land \neg {y} \land z) \lor (x \land y \land \neg {z})[/math].
| Теорема: |
Для любой булевой функции [math]f(\vec {x})[/math], не равной тождественному нулю, существует СДНФ, ее задающая. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Для любой булевой функции выполняется следующее соотношение, называемое разложением Шеннона:
[math]f(\vec{x}) = \neg x_i \wedge f(x_1, \ldots ,x_{i-1},0,x_{i+1}, \ldots ,x_n) \vee
x_i \wedge f(x_1, \ldots ,x_{i-1},1,x_{i+1}, \ldots ,x_n)[/math].
Данное соотношение легко проверить подстановкой возможных значений [math]x_i[/math] ([math]0[/math] и [math]1[/math]). Эта формула позволяет выносить [math]x_i[/math] за знак функции. Последовательно вынося [math]x_1[/math], [math]x_2[/math],.., [math]x_n[/math] за знак [math]f(\vec{x})[/math], получаем следующую формулу:
[math] f(\vec{x}) = \neg x_1 \wedge \neg x_2 \wedge \ldots \wedge \neg x_{n-1} \wedge \neg x_n \wedge f(0,0,\ldots,0,0)~\vee~[/math]
[math]\neg x_1 \wedge \neg x_2 \wedge \ldots \wedge \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) [/math]
Так как применение данного соотношения к каждой из переменных увеличивает количество конъюнктов в два раза, то для функции от [math]n[/math] переменных мы имеем [math]2^n[/math] конъюнктов. Каждый из них соответствует значению функции на одном из [math]2^n[/math] возможных наборов значений [math] n [/math] переменных. Если на некотором наборе [math]f(\vec{x})=0[/math], то весь соответствующий конъюнкт также равен нулю и из представления данной функции его можно исключить. Если же [math] f(\vec{x})=1[/math], то в соответствующем конъюнкте само значение функции можно опустить. В результате для произвольной функции была построена СДНФ. |
| [math]\triangleleft[/math] |
Алгоритм построения СДНФ по таблице истинности
- В таблице истинности отмечаем те наборы переменных, на которых значение функции равно [math] 1 [/math].
- Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть [math] 1 [/math], то в конъюнкцию включаем саму переменную, иначе ее отрицание.
- Все полученные конъюнкции связываем операциями дизъюнкции.
Пример построения СДНФ для медианы
Построение СДНФ для медианы от трех аргументов
1. В таблице истинности отмечаем те наборы переменных, на которых значение функции равно [math] 1 [/math].
| [math] x [/math] |
[math] y [/math] |
[math] z [/math] |
[math] \langle x,y,z \rangle [/math]
|
| 0 |
0 |
0 |
0
|
| 0 |
0 |
1 |
0
|
| 0 |
1 |
0 |
0
|
| 0 |
1 |
1 |
1
|
| 1 |
0 |
0 |
0
|
| 1 |
0 |
1 |
1
|
| 1 |
1 |
0 |
1
|
| 1 |
1 |
1 |
1
|
2. Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть [math] 1 [/math], то в конъюнкцию включаем саму переменную, иначе ее отрицание.
| [math] x [/math] |
[math] y [/math] |
[math] z [/math] |
[math] \langle x,y,z \rangle [/math] |
|
| 0 |
0 |
0 |
0 |
|
| 0 |
0 |
1 |
0 |
|
| 0 |
1 |
0 |
0 |
|
| 0 |
1 |
1 |
1 |
[math](\neg {x} \land y \land z)[/math]
|
| 1 |
0 |
0 |
0 |
|
| 1 |
0 |
1 |
1 |
[math](x \land \neg {y} \land z)[/math]
|
| 1 |
1 |
0 |
1 |
[math](x \land y \land \neg {z})[/math]
|
| 1 |
1 |
1 |
1 |
[math](x \land y \land z)[/math]
|
3. Все полученные конъюнкции связываем операциями дизъюнкции:
[math] \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})[/math].
Построение СДНФ для медианы от пяти аргументов
| [math] x_1 [/math] |
[math] x_2 [/math] |
[math] x_3 [/math] |
[math]x_4[/math] |
[math] x_5 [/math] |
[math] \langle x_1, x_2, x_3, x_4, x_5 \rangle [/math] |
|
| 0 |
0 |
0 |
0 |
0 |
0 |
|
| 0 |
0 |
0 |
0 |
1 |
0 |
|
| 0 |
0 |
0 |
1 |
0 |
0 |
|
| 0 |
0 |
0 |
1 |
1 |
0 |
|
| 0 |
0 |
1 |
0 |
0 |
0 |
|
| 0 |
0 |
1 |
0 |
1 |
0 |
|
| 0 |
0 |
1 |
1 |
0 |
0 |
|
| 0 |
0 |
1 |
1 |
1 |
1 |
[math](\neg {x_1} \land \neg {x_2} \land x_3 \land x_4 \land x_5)[/math]
|
| 0 |
1 |
0 |
0 |
0 |
0 |
|
| 0 |
1 |
0 |
0 |
1 |
0 |
|
| 0 |
1 |
0 |
1 |
0 |
0 |
|
| 0 |
1 |
0 |
1 |
1 |
1 |
[math](\neg {x_1} \land x_2 \land \neg {x_3} \land x_4 \land x_5)[/math]
|
| 0 |
1 |
1 |
0 |
0 |
0 |
|
| 0 |
1 |
1 |
0 |
1 |
1 |
[math](\neg {x_1} \land x_2 \land x_3 \land \neg {x_4} \land x_5)[/math]
|
| 0 |
1 |
1 |
1 |
0 |
1 |
[math](\neg {x_1} \land x_2 \land x_3 \land x_4 \land \neg {x_5})[/math]
|
| 0 |
1 |
1 |
1 |
1 |
1 |
[math](\neg {x_1} \land x_2 \land x_3 \land x_4 \land x_5)[/math]
|
| 1 |
0 |
0 |
0 |
0 |
0 |
|
| 1 |
0 |
0 |
0 |
1 |
0 |
|
| 1 |
0 |
0 |
1 |
0 |
0 |
|
| 1 |
0 |
0 |
1 |
1 |
1 |
[math](x_1 \land \neg {x_2} \land \neg {x_3} \land x_4 \land x_5)[/math]
|
| 1 |
0 |
1 |
0 |
0 |
0 |
|
| 1 |
0 |
1 |
0 |
1 |
1 |
[math](x_1 \land \neg {x_2} \land x_3 \land \neg {x_4} \land x_5)[/math]
|
| 1 |
0 |
1 |
1 |
0 |
1 |
[math](x_1 \land \neg {x_2} \land x_3 \land x_4 \land \neg {x_5})[/math]
|
| 1 |
0 |
1 |
1 |
1 |
1 |
[math](x_1 \land \neg {x_2} \land x_3 \land x_4 \land x_5)[/math]
|
| 1 |
1 |
0 |
0 |
0 |
0 |
|
| 1 |
1 |
0 |
0 |
1 |
1 |
[math](x_1 \land x_2 \land \neg {x_3} \land \neg {x_4} \land x_5)[/math]
|
| 1 |
1 |
0 |
1 |
0 |
1 |
[math](x_1 \land x_2 \land \neg {x_3} \land x_4 \land \neg {x_5})[/math]
|
| 1 |
1 |
0 |
1 |
1 |
1 |
[math](x_1 \land x_2 \land \neg {x_3} \land x_4 \land x_5)[/math]
|
| 1 |
1 |
1 |
0 |
0 |
1 |
[math](x_1 \land x_2 \land x_3 \land \neg {x_4} \land \neg {x_5})[/math]
|
| 1 |
1 |
1 |
0 |
1 |
1 |
[math](x_1 \land x_2 \land x_3 \land \neg {x_4} \land x_5)[/math]
|
| 1 |
1 |
1 |
1 |
0 |
1 |
[math](x_1 \land x_2 \land x_3 \land x_4 \land \neg {x_5})[/math]
|
| 1 |
1 |
1 |
1 |
1 |
1 |
[math](x_1 \land x_2 \land x_3 \land x_4 \land x_5)[/math]
|
[math] \langle x_1, x_2, x_3, x_4, x_5 \rangle = (x_1 \land x_2 \land x_3 \land \overline{x_4} \land \overline{x_5}) \lor (x_1 \land x_2 \land \overline{x_3} \land x_4 \land \overline{x_5}) \lor \\ (x_1 \land \overline{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 \overline{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 \overline{x_3} \land \overline{x_4} \land x_5) \lor (x_1 \land \overline{x_2} \land x_3 \land \overline{x_4} \land x_5) \lor (\overline{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 \overline{x_4} \land x_5) \lor (x_1 \land \overline{x_2} \land \overline{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 (x_1 \land x_2 \land \overline{x_3} \land x_4 \land x_5) \lor (\overline{x_1} \land \overline{x_2} \land x_3 \land x_4 \land x_5) \lor (x_1 \land \overline{x_2} \land x_3 \land x_4 \land x_5) \lor (\overline{x_1} \land x_2 \land x_3 \land x_4 \land x_5) \lor (x_1 \land x_2 \land x_3 \land x_4 \land x_5) [/math].
Примеры СДНФ для некоторых функций
Стрелка Пирса: [math] x \downarrow y = (\neg {x} \land \neg {y})[/math].
Исключающее или: [math] 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)[/math].
См. также
Источники информации
