Лучшие вопросы
Таймлайн
Чат
Перспективы

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

класс КНФ в булевой алгебре Из Википедии, свободной энциклопедии

Remove ads

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

·       в ней нет одинаковых множителей (элементарных дизъюнкций);

·       в каждом множителе нет повторяющихся переменных;

·       каждый множитель содержит все переменные, от которых зависит булева функция (каждая переменная может входить в множитель либо в прямой, либо в инверсной форме).

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

Remove ads

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

Суммиров вкратце
Перспектива

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

Подробнее , ...

В ячейках строки́ отмечаются лишь те комбинации, которые приводят логическое выражение в состояние нуля.

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

В дизъюнкцию записывается переменная без инверсии, если она в наборе равна 0, и с инверсией, если она равна 1. Первый член СКНФ рассматриваемой функции выглядит так:

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

Remove ads

См. также


Примечания

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads