ДНФ

Определение:

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

Пример ДНФ: [math]f(x,y) = (x \land y) \lor (y \land \overline{z})[/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, то в конъюнкцию включаем саму переменную, иначе ее отрицание.
• Все полученные конъюнкции связываем операциями дизъюнкции.

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

Стрелка Пирса: [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]

Ссылки

• Википедия — свободная энциклопедия
• Е.Л Рабкин, Ю.Б. Фарфоровская — Дискретная математика