WikiSort.ru - Не сортированное

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

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

Любая булева формула, не являющаяся тождественно ложной, может быть приведена к СДНФ, причем единственным образом^[1], то есть для любой выполнимой функции алгебры логики существует своя СДНФ, причём единственная.

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

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

${\displaystyle x_{1}}$	${\displaystyle x_{2}}$	${\displaystyle x_{3}}$	${\displaystyle f(x_{1},x_{2},x_{3})}$
0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	0

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

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

• ${\displaystyle x_{1}=0}$
• ${\displaystyle x_{2}=0}$
• ${\displaystyle x_{3}=0}$

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

Переменные второго члена:

• ${\displaystyle x_{1}=0}$
• ${\displaystyle x_{2}=0}$
• ${\displaystyle x_{3}=1}$

${\displaystyle x_{3}}$ в этом случае будет представлен без инверсии: ${\displaystyle {\overline {x_{1}}}\cdot {\overline {x_{2}}}\cdot x_{3}}$

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

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

${\displaystyle f(x_{1},x_{2},x_{3})=({\overline {x_{1}}}\land {\overline {x_{2}}}\land {\overline {x_{3}}})\vee ({\overline {x_{1}}}\land {\overline {x_{2}}}\land x_{3})\vee ({\overline {x_{1}}}\land x_{2}\land {\overline {x_{3}}})\vee (x_{1}\land x_{2}\land {\overline {x_{3}}})}$

См. также

• Дизъюнктивная нормальная форма
• Конъюнктивная нормальная форма
• Совершенная конъюнктивная нормальная форма

Примечания

Для улучшения этой статьи желательно: Найти и оформить в виде сносок ссылки на независимые авторитетные источники, подтверждающие написанное.