СКНФ

В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники. Эта отметка установлена 14 мая 2011.

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

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

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

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

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

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

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

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

В дизъюнкцию записывается переменная без инверсии если она в наборе равна 0 и с инверсией если она равна 1. Первый член СКНФ рассматриваемой функции выглядит так: ${x_1} \vee$ ${x_2} \vee$ $\overline{x_3}$ $\vee$ $\overline{x_4}$

Остальные члены СКНФ составляются по аналогии.

См. также

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