ДНФ — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (СДНФ)
м (rollbackEdits.php mass rollback)
 
(не показано 37 промежуточных версий 12 участников)
Строка 2: Строка 2:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
Простой конъюнкцией или конъюнктом называется конъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная встречается не более одного раза.
+
'''Простой конъюнкцией''' (англ. ''inclusive conjunction'') или '''конъюнктом''' (англ. ''conjunct'') называется конъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная встречается не более одного раза.
 
}}
 
}}
Элементарная конъюнкция
+
Простая конъюнкция
* '''правильная''', если в неё каждая переменная входит не более одного раза (включая отрицание);
+
* '''полная''', если в неё каждая переменная (или её отрицание) входит ровно <tex> 1 </tex> раз;
* '''полная''', если в неё каждая переменная (или её отрицание) входит ровно 1 раз;
 
 
* '''монотонная''', если она не содержит отрицаний переменных.
 
* '''монотонная''', если она не содержит отрицаний переменных.
  
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
ДНФ (Дизъюнктивная Нормальная Форма) нормальная форма, в которой [[Определение булевой функции|булева функция]] имеет вид дизъюнкции нескольких простых конъюнктов.
+
'''Дизъюнктивная нормальная форма, ДНФ''' (англ. ''disjunctive normal form, DNF'') {{---}} нормальная форма, в которой [[Определение булевой функции|булева функция]] имеет вид дизъюнкции нескольких простых конъюнктов.
 
}}
 
}}
 
Пример ДНФ:
 
Пример ДНФ:
<tex>f(x,y) = (x \land y) \lor (y \land \overline{z})</tex>
+
<tex>f(x,y,z) = (x \land y) \lor (y \land \neg {z})</tex>.
  
 
== СДНФ ==
 
== СДНФ ==
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
СДНФ (Совершенная Дизъюнктивная Нормальная Форма)''' — это такая ДНФ, которая удовлетворяет условиям:
+
'''Совершенная дизъюнктивная нормальная форма, СДНФ''' (англ. ''perfect disjunctive normal form, PDNF'') — ДНФ, удовлетворяющая условиям:
* в ней нет одинаковых элементарных конъюнкций
+
* в ней нет одинаковых простых конъюнкций,
* в каждой конъюнкции нет одинаковых переменных
+
* каждая простая конъюнкция полная.
* каждая элементарная конъюнкция содержит каждый из аргументов функции.
 
 
}}
 
}}
 
Пример СДНФ:
 
Пример СДНФ:
<tex>f(x,y,z) = (x \land \overline{y} \land z) \lor (x \land y \land \overline{z})</tex>
+
<tex>f(x,y,z) = (x \land \neg {y} \land z) \lor (x \land y \land \neg {z})</tex>.
  
  
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Для любой булевой функции <tex>f(\overline{x})</tex>, не равной тождественному нулю, существует СДНФ, ее задающая.
+
Для любой булевой функции <tex>f(\vec {x})</tex>, не равной тождественному нулю, существует СДНФ, ее задающая.
 
|proof =  
 
|proof =  
Для любой булевой функции выполняется следующее соотношение, называемое '''разложением Шеннона'''.
+
Для любой булевой функции выполняется следующее соотношение, называемое '''разложением Шеннона''':
  
<tex>f(\vec{x}) = \overline x_i \wedge f(x_1,..,x_{i-1},0,x_{i+1},..,x_n) \vee
+
<tex>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,..,x_{i-1},1,x_{i+1},x_n)</tex>
+
x_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>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 x_1 \wedge \overline x_2 \wedge ...\wedge \overline x_{n-1} \wedge \overline x_n \wedge f(0,0,...,0,0)~\vee~</tex>
+
<tex> 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~</tex>
  
<tex>\overline x_1 \wedge \overline x_2 \wedge ... \wedge \overline x_{n-1} \wedge x_n \wedge f(0,0,...,0,1) ~\vee~</tex>
+
<tex>\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) </tex>
  
<tex>... </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,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.
+
# В таблице истинности отмечаем те наборы переменных, на которых значение функции равно <tex> 1 </tex>.
# Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть 1, то в конъюнкцию включаем саму переменную, иначе ее отрицание.
+
# Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть <tex> 1 </tex>, то в конъюнкцию включаем саму переменную, иначе ее отрицание.
 
# Все полученные конъюнкции связываем операциями дизъюнкции.
 
# Все полученные конъюнкции связываем операциями дизъюнкции.
  
== Пример построения СДНФ ==
+
== Пример построения СДНФ для медианы==
1. В таблице истинности отмечаем те наборы переменных, на которых значение функции равно 1.
+
=== Построение СДНФ для медианы от трех аргументов ===
 +
1. В таблице истинности отмечаем те наборы переменных, на которых значение функции равно <tex> 1 </tex>.
  
 
{| class="wikitable" style="width:10cm" border=1
 
{| class="wikitable" style="width:10cm" border=1
 
|+
 
|+
 
|-align="center" bgcolor=#EEEEFF
 
|-align="center" bgcolor=#EEEEFF
| x || y || z || <tex> \langle x,y,z \rangle </tex>
+
|<tex> x </tex>||<tex> y </tex>||<tex> z </tex>|| <tex> \langle x,y,z \rangle </tex>
|-align="center" bgcolor=#F0F0F0
+
|-align="center" bgcolor=#FFFFFF
 
| 0 || 0 || 0 || 0
 
| 0 || 0 || 0 || 0
|-align="center" bgcolor=#F0F0F0
+
|-align="center" bgcolor=#FFFFFF
 
| 0 || 0 || 1 || 0
 
| 0 || 0 || 1 || 0
|-align="center" bgcolor=#F0F0F0
+
|-align="center" bgcolor=#FFFFFF
 
| 0 || 1 || 0 || 0
 
| 0 || 1 || 0 || 0
|-align="center" bgcolor=#F0F0F0
+
|-align="center" bgcolor=#FFFFFF
 
! 0 || 1 || 1 || 1
 
! 0 || 1 || 1 || 1
|-align="center" bgcolor=#F0F0F0
+
|-align="center" bgcolor=#FFFFFF
 
| 1 || 0 || 0 || 0
 
| 1 || 0 || 0 || 0
|-align="center" bgcolor=#F0F0F0
+
|-align="center" bgcolor=#FFFFFF
 
! 1 || 0 || 1 || 1
 
! 1 || 0 || 1 || 1
|-align="center" bgcolor=#F0F0F0
+
|-align="center" bgcolor=#FFFFFF
 
! 1 || 1 || 0 || 1
 
! 1 || 1 || 0 || 1
|-align="center" bgcolor=#F0F0F0
+
|-align="center" bgcolor=#FFFFFF
 
! 1 || 1 || 1 || 1
 
! 1 || 1 || 1 || 1
 
|}
 
|}
  
2. Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть 1, то в конъюнкцию включаем саму переменную, иначе ее отрицание.
+
2. Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть <tex> 1 </tex>, то в конъюнкцию включаем саму переменную, иначе ее отрицание.
  
 
{| class="wikitable"  style="width:16cm" border=1
 
{| class="wikitable"  style="width:16cm" border=1
 
|+
 
|+
 
|-align="center" bgcolor=#EEEEFF
 
|-align="center" bgcolor=#EEEEFF
| x || y || z || <tex> \langle x,y,z \rangle </tex> ||  
+
|<tex> x </tex>||<tex> y </tex>||<tex> z </tex>|| <tex> \langle x,y,z \rangle </tex> ||  
|-align="center" bgcolor=#F0F0F0
+
|-align="center" bgcolor=#FFFFFF
 
| 0 || 0 || 0 || 0 ||
 
| 0 || 0 || 0 || 0 ||
|-align="center" bgcolor=#F0F0F0
+
|-align="center" bgcolor=#FFFFFF
 
| 0 || 0 || 1 || 0 ||
 
| 0 || 0 || 1 || 0 ||
|-align="center" bgcolor=#F0F0F0
+
|-align="center" bgcolor=#FFFFFF
 
| 0 || 1 || 0 || 0 ||
 
| 0 || 1 || 0 || 0 ||
|-align="center" bgcolor=#F0F0F0
+
|-align="center" bgcolor=#FFFFFF
! 0 || 1 || 1 || 1 || <tex>(\overline{x} \land y \land z)</tex>
+
! 0 || 1 || 1 || 1 || <tex>(\neg {x} \land y \land z)</tex>
|-align="center" bgcolor=#F0F0F0
+
|-align="center" bgcolor=#FFFFFF
 
| 1 || 0 || 0 || 0 ||
 
| 1 || 0 || 0 || 0 ||
|-align="center" bgcolor=#F0F0F0
+
|-align="center" bgcolor=#FFFFFF
! 1 || 0 || 1 || 1 || <tex>(x \land \overline{y} \land z)</tex>
+
! 1 || 0 || 1 || 1 || <tex>(x \land \neg {y} \land z)</tex>
|-align="center" bgcolor=#F0F0F0
+
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 0 || 1 || <tex>(x \land y \land \overline{z})</tex>
+
! 1 || 1 || 0 || 1 || <tex>(x \land y \land \neg {z})</tex>
|-align="center" bgcolor=#F0F0F0
+
|-align="center" bgcolor=#FFFFFF
 
! 1 || 1 || 1 || 1 || <tex>(x \land y \land z)</tex>
 
! 1 || 1 || 1 || 1 || <tex>(x \land y \land z)</tex>
 
|}
 
|}
  
3. Все полученные конъюнкции связываем операциями дизъюнкции.
+
3. Все полученные конъюнкции связываем операциями дизъюнкции:
 
                                                                    
 
                                                                    
<tex> \langle x,y,z \rangle = (x \land y \land z) \lor (\overline{x} \land y \land z) \lor (x \land \overline{y} \land z) \lor (x \land y \land \overline{z})</tex>
+
<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>.
 +
 
 +
===  Построение СДНФ для медианы от пяти аргументов ===
 +
{| 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 {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 = (\overline{x} \land \overline{y})</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>.
 +
 
 +
== См. также ==
  
Исключающее или: <tex> x \oplus y \oplus z = (\overline{x} \lor \overline{y} \lor z) \land (\overline{x} \lor y \lor \overline{z}) \land (x \lor \overline{y} \lor \overline{z}) \land (x \lor y \lor z)</tex>
+
* [[Сокращенная и минимальная ДНФ]]
 +
* [[КНФ]]
  
== Ссылки ==
+
==Источники информации ==
 
* [http://ru.wikipedia.org/wiki/%D0%A1%D0%94%D0%9D%D0%A4 СДНФ — Википедия]
 
* [http://ru.wikipedia.org/wiki/%D0%A1%D0%94%D0%9D%D0%A4 СДНФ — Википедия]
 
* [http://dvo.sut.ru/libr/himath/w163rabk/index.htm Е.Л Рабкин,  Ю.Б. Фарфоровская — Дискретная математика]
 
* [http://dvo.sut.ru/libr/himath/w163rabk/index.htm Е.Л Рабкин,  Ю.Б. Фарфоровская — Дискретная математика]
 +
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
 +
[[Категория: Булевы функции ]]

Текущая версия на 19:35, 4 сентября 2022

ДНФ

Определение:
Простой конъюнкцией (англ. 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]

Алгоритм построения СДНФ по таблице истинности

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

Пример построения СДНФ для медианы

Построение СДНФ для медианы от трех аргументов

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 = (\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 {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)[/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].

См. также

Источники информации