ДНФ

ДНФ

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

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

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

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

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

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

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

СДНФ

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

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

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

Теорема:

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

Доказательство:

$\triangleright$

Для любой булевой функции выполняется следующее соотношение, называемое разложением Шеннона. $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)$ Данное соотношение легко проверить подстановкой всевозможных значений $x_i$ ($0$ и $1$). Эта формула позволяет выносить $x_i$ за знак функции. Последовательно вынося $x_1$, $x_2$,.., $x_n$ за знак $f(\vec{x})$, получаем следующую формулу : $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~$ $\overline x_1 \wedge \overline x_2 \wedge ... \wedge \overline x_{n-1} \wedge x_n \wedge f(0,0,...,0,1) ~\vee~$ $...$ $~\vee~ x_1 \wedge x_2 \wedge ... \wedge x_{n-1} \wedge \overline 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)$ Т.к применение данного соотношения к каждой из переменных увеличивает количество дизъюнктивных членов в два раза, то для функции от $n$ переменных мы имеем $2^n$ дизъюнктивных членов. Каждый из них соответствует значению функции на одном из $2^n$ возможных наборов значений n переменных. Если на некотором наборе $f(\vec{x})=0$, то весь соответствующий дизъюнктивный член также равен нулю и из представления данной функции его можно исключить. Если же $f(\vec{x})=1$, то в соответствующем дизъюннктивном члене само значение функции можно опустить. В результате для произвольной функции была построена СДНФ.

$\triangleleft$

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

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

Пример построения СДНФ

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

x	y	z	$\langle x,y,z \rangle$
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	$\langle x,y,z \rangle$
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1	$(\overline{x} \land y \land z)$
1	0	0	0
1	0	1	1	$(x \land \overline{y} \land z)$
1	1	0	1	$(x \land y \land \overline{z})$
1	1	1	1	$(x \land y \land z)$

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

$\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})$

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

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

Исключающее или: $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)$

Ссылки

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