Лучшие вопросы
Таймлайн
Чат
Перспективы
Совершенная конъюнктивная нормальная форма
класс КНФ в булевой алгебре Из Википедии, свободной энциклопедии
Remove ads
Совершенная конъюнктивная нормальная форма (СКНФ) — одна из форм представления функции алгебры логики (булевой функции) в виде логического выражения. Представляет собой частный случай КНФ, удовлетворяющий следующим трём условиям:
· в ней нет одинаковых множителей (элементарных дизъюнкций);
· в каждом множителе нет повторяющихся переменных;
· каждый множитель содержит все переменные, от которых зависит булева функция (каждая переменная может входить в множитель либо в прямой, либо в инверсной форме).
Любая булева формула, не являющаяся тождественно истинной, может быть приведена к СКНФ.[1].
Remove ads
Пример нахождения СКНФ
Суммиров вкратце
Перспектива
Для того, чтобы получить СКНФ функции, требуется составить её таблицу истинности. К примеру, возьмём одну из таблиц истинности статьи минимизация логических функций методом Квайна:
В ячейках строки́ отмечаются лишь те комбинации, которые приводят логическое выражение в состояние нуля.
Четвёртая строка содержит 0 в указанном поле. Отмечаются значения всех четырёх переменных, это:
В дизъюнкцию записывается переменная без инверсии, если она в наборе равна 0, и с инверсией, если она равна 1. Первый член СКНФ рассматриваемой функции выглядит так:
Остальные члены СКНФ составляются по аналогии:[2]
Remove ads
См. также
- Конъюнктивная нормальная форма
- Дизъюнктивная нормальная форма
- Совершенная дизъюнктивная нормальная форма
Примечания
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads