СДНФ

СДНФ (Совершенная Дизъюнктивная Нормальная Форма) — это такая ДНФ, которая удовлетворяет трём условиям:

• в ней нет одинаковых элементарных конъюнкций
• в каждой конъюнкции нет одинаковых пропозициональных букв
• каждая элементарная конъюнкция содержит каждую пропозициональную букву из входящих в данную ДНФ пропозициональных букв, причем в одинаковом порядке.

Для любой функции алгебры логики существует своя СДНФ, причем единственная.

Пример нахождения СДНФ

Для того, чтобы получить СДНФ функции, требуется составить её таблицу истинности. К примеру, возьмём одну из таблиц истинности статьи Минимизация логических функций методом Квайна, в которой нахождение СДНФ встречается несколько раз:

$\mathbf{x_1}$	$\mathbf{x_2}$	$\mathbf{x_3}$	$\mathbf{x_4}$	$\mathbf{f}({x_1},{x_2},{x_3},{x_4})$
0	0	0	0	1
0	0	0	1	1
0	0	1	0	1
0	0	1	1	0
0	1	0	0	0
0	1	0	1	0
0	1	1	0	1
0	1	1	1	0
1	0	0	0	0
1	0	0	1	0
1	0	1	0	0
1	0	1	1	0
1	1	0	0	0
1	1	0	1	0
1	1	1	0	1
1	1	1	1	1

В ячейках результата $\mathbf{f}({x_1},{x_2},{x_3},{x_4})$ отмечаются лишь те комбинации, которые приводят логическое выражение в состояние единицы.
Далее рассматриваются значения переменных при которых функция равна 1. Если значение переменной равно 0, то она записывается с инверсией. Если значение переменной равно 1, то без инверсии.

Первая строка содержит 1 в указанном поле. Отмечаются значения всех четырёх переменных, это:

• $\mathbf{x_1}$ = 0
• $\mathbf{x_2}$ = 0
• $\mathbf{x_3}$ = 0
• $\mathbf{x_4}$ = 0

Нулевые значения — тут все переменные представлены нулями — записываются в конечном выражении инверсией этой переменной. Первый член СДНФ рассматриваемой функции выглядит так: $\overline{x_1}\cdot\overline{x_2}\cdot\overline{x_3}\cdot\overline{x_4}$
Переменные второго члена:

• $\mathbf{x_1}$ = 0
• $\mathbf{x_2}$ = 0
• $\mathbf{x_3}$ = 0
• $\mathbf{x_4}$ = 1

$\mathbf{x_4}$ в этом случае будет представлен без инверсии: $\overline{x_1}\cdot\overline{x_2}\cdot\overline{x_3}\cdot{x_4}$

Таким образом анализируются все ячейки $\mathbf{f}({x_1},{x_2},{x_3},{x_4})$. Совершенная ДНФ этой функции будет дизъюнкцией всех полученных членов (элементарных конъюнкций).

Совершенная ДНФ этой функции:

$\mathbf{f}({x_1},{x_2},{x_3},{x_4})=(\overline{x_1}\cdot\overline{x_2}\cdot\overline{x_3}\cdot\overline{x_4})$ $\vee$ $(\overline{x_1}\cdot\overline{x_2}\cdot\overline{x_3}\cdot{x_4})$ $\vee$ $(\overline{x_1}\cdot\overline{x_2}\cdot{x_3}\cdot\overline{x_4})$ $\vee$ $(\overline{x_1}\cdot{x_2}\cdot{x_3}\cdot\overline{x_4})$ $\vee$ $({x_1}\cdot{x_2}\cdot{x_3}\cdot\overline{x_4})$ $\vee$ $({x_1}\cdot{x_2}\cdot{x_3}\cdot{x_4})$

См. также

• ДНФ
• КНФ
• СКНФ

Ссылки

Примечания