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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Определение)
Строка 52: Строка 52:
 
Т.к применение данного соотношения к каждой из переменных увеличивает количество дизъюнктивных членов в два раза, то для функции от <tex>n</tex> переменных мы имеем <tex>2^n</tex> дизъюнктивных членов. Каждый из них соответствует значению функции на одном из <tex>2^n</tex> возможных наборов значений n переменных. Если на некотором наборе <tex>f(\vec{x})=0</tex>, то весь соответствующий дизъюнктивный член также равен нулю и из представления данной функции его можно исключить. Если же <tex> f(\vec{x})=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.
 +
# Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть 1, то в конъюнкцию включаем саму переменную, иначе ее отрицание.
 +
# Все полученные конъюнкции связываем операциями дизъюнкции.
 
== Пример построения СДНФ ==
 
== Пример построения СДНФ ==
 
1. В таблице истинности отмечаем те наборы переменных, на которых значение функции равно 1.
 
1. В таблице истинности отмечаем те наборы переменных, на которых значение функции равно 1.
Строка 60: Строка 63:
 
|+
 
|+
 
|-align="center" bgcolor=#EEEEFF
 
|-align="center" bgcolor=#EEEEFF
! x || y || z || <xyz>
+
! x || y || z || <tex>med(x,y,z)</tex>
 
|-align="center" bgcolor=#F0F0F0
 
|-align="center" bgcolor=#F0F0F0
 
| 0 || 0 || 0 || 0
 
| 0 || 0 || 0 || 0
Строка 86: Строка 89:
 
|+
 
|+
 
|-align="center" bgcolor=#EEEEFF
 
|-align="center" bgcolor=#EEEEFF
! x || y || z || <xyz> ||  
+
| x || y || z || <tex>med(x,y,z)</tex> ||  
 
|-align="center" bgcolor=#F0F0F0
 
|-align="center" bgcolor=#F0F0F0
 
| 0 || 0 || 0 || 0 ||
 
| 0 || 0 || 0 || 0 ||
Строка 116: Строка 119:
  
 
== Ссылки ==
 
== Ссылки ==
* [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 Е.Л Рабкин,  Ю.Б. Фарфоровская — Дискретная математика]

Версия 07:15, 17 октября 2011

ДНФ

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

Элементарная конъюнкция

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


Определение:
ДНФ (Дизъюнктивная Нормальная Форма) — нормальная форма, в которой булева функция имеет вид дизъюнкции нескольких простых конъюнктов.

Пример ДНФ: [math]f(x,y) = (x \land y) \lor (y \land \overline{z})[/math]

ДНФ может быть преобразована к эквивалентной ей КНФ путём раскрытия скобок по правилу: [math]a\lor b c\to (a \lor b)(a \lor c)[/math], которое выражает дистрибутивность дизъюнкции относительно конъюнкции. После этого необходимо в каждой дизъюнкции удалить повторяющиеся переменные или их отрицания, а также выбросить из конъюнкции все дизъюнкции, в которых встречается переменная вместе со своим отрицанием. При этом результатом не обязательно будет СКНФ, даже если исходная ДНФ была СДНФ. Точно также можно всегда перейти от КНФ к ДНФ. Для этого следует использовать правило [math]a (b\lor c)\to a b\lor a c[/math], выражающее дистрибутивность конъюнкции относительно дизъюнкции. Результат нужно преобразовать описанным выше способом, заменив слово «дизъюнкция» на «конъюнкция» и наоборот.

СДНФ

Определение:
СДНФ (Совершенная Дизъюнктивная Нормальная Форма) — это такая ДНФ, которая удовлетворяет условиям:
  • в ней нет одинаковых элементарных конъюнкций
  • в каждой конъюнкции нет одинаковых переменных
  • каждая элементарная конъюнкция содержит каждый из аргументов функции.

Пример СДНФ: [math]f(x,y,z) = (x \land \overline{y} \land z) \lor (x \land y \land \overline{z})[/math]


Теорема:
Для любой булевой функции [math]f(\vec{x})[/math], не равной тождественному нулю, существует СДНФ, ее задающая.
Доказательство:
[math]\triangleright[/math]

Для любой булевой функции выполняется следующее соотношение, называемое разложением Шеннона.

[math]f(\vec{x}) = \overline 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)[/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}) = \overline x_1 \wedge \overline x_2 \wedge ...\wedge \overline x_{n-1} \wedge \overline x_n \wedge f(0,0,...,0,0)~\vee~[/math]

[math]\overline x_1 \wedge \overline x_2 \wedge ... \wedge \overline x_{n-1} \wedge x_n \wedge f(0,0,...,0,1) ~\vee~[/math]

[math]... [/math]

[math]~\vee~ x_1 \wedge x_2 \wedge ... \wedge x_{n-1} \wedge \overline x_n \wedge f(1,1,...,1,0) ~\vee~[/math]

[math]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] возможных наборов значений n переменных. Если на некотором наборе [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]med(x,y,z)[/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]med(x,y,z)[/math]
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1 [math](\overline{x} \land y \land z)[/math]
1 0 0 0
1 0 1 1 [math](x \land \overline{y} \land z)[/math]
1 1 0 1 [math](x \land y \land \overline{z})[/math]
1 1 1 1 [math](x \land y \land z)[/math]

3. Все полученные конъюнкции связываем операциями дизъюнкции.

[math]med(x,y,z) = (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})[/math]

Примеры СДНФ для некоторых функций

Стрелка Пирса: [math] x \downarrow y = (\overline{x} \land \overline{y})[/math]

Медиана трёх: [math]f(x,y,z) = (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})[/math]

Ссылки