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

Материал из Викиконспекты
Перейти к: навигация, поиск
(СДНФ)
м (Добавил англ. терминов; поправил аббревиатуры; убрал скобки в формулировке теоремы; выделил жирным шрифтом в определениях то, что нужно.)
Строка 2: Строка 2:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
Простой конъюнкцией или конъюнктом называется конъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная встречается не более одного раза.
+
'''Простой конъюнкцией''' (англ. ''inclusive conjunction'') или '''конъюнктом''' (англ. ''conjunct'') называется конъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная встречается не более одного раза.
 
}}
 
}}
 
Простая конъюнкция
 
Простая конъюнкция
Строка 10: Строка 10:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
ДНФ (Дизъюнктивная Нормальная Форма) нормальная форма, в которой [[Определение булевой функции|булева функция]] имеет вид дизъюнкции нескольких простых конъюнктов.
+
'''Дизъюнктивная нормальная форма, ДНФ''' (англ. ''disjunctive normal form, DNF'') {{---}} нормальная форма, в которой [[Определение булевой функции|булева функция]] имеет вид дизъюнкции нескольких простых конъюнктов.
 
}}
 
}}
 
Пример ДНФ:
 
Пример ДНФ:
Строка 18: Строка 18:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
СДНФ (Совершенная Дизъюнктивная Нормальная Форма)''' — это такая ДНФ, которая удовлетворяет условиям:
+
'''Совершенная дизъюнктивная нормальная форма, СДНФ''' (англ. ''perfect disjunctive normal form, PDNF'') — это такая ДНФ, которая удовлетворяет условиям:
 
* в ней нет одинаковых простых конъюнкций
 
* в ней нет одинаковых простых конъюнкций
 
* каждая простая конъюнкция полная
 
* каждая простая конъюнкция полная
Строка 28: Строка 28:
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Для любой булевой функции <tex>f(\vec {x})</tex>, не равной тождественному нулю (), существует СДНФ, ее задающая.
+
Для любой булевой функции <tex>f(\vec {x})</tex>, не равной тождественному нулю, существует СДНФ, ее задающая.
 
|proof =  
 
|proof =  
 
Для любой булевой функции выполняется следующее соотношение, называемое '''разложением Шеннона'''.
 
Для любой булевой функции выполняется следующее соотношение, называемое '''разложением Шеннона'''.

Версия 19:17, 5 января 2017

ДНФ

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

Простая конъюнкция

  • полная, если в неё каждая переменная (или её отрицание) входит ровно 1 раз;
  • монотонная, если она не содержит отрицаний переменных.


Определение:
Дизъюнктивная нормальная форма, ДНФ (англ. 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, \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)[/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 ...\wedge \neg x_{n-1} \wedge \neg x_n \wedge f(0,0,...,0,0)~\vee~[/math]

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

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

1. В таблице истинности отмечаем те наборы переменных, на которых значение функции равно 1.

x y z [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. Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть 1, то в конъюнкцию включаем саму переменную, иначе ее отрицание.

x y z [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 \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]

Ссылки