Соверше́нная дизъюнкти́вная норма́льная фо́рма (СДНФ) — одна из форм представления функции алгебры логики (булевой функции) в виде логического выражения. Представляет собой частный случай ДНФ, удовлетворяющий следующим трём условиям[1]:
- в ней нет одинаковых слагаемых (элементарных конъюнкций);
- в каждом слагаемом нет повторяющихся переменных;
- каждое слагаемое содержит все переменные, от которых зависит булева функция (каждая переменная может входить в слагаемое либо в прямой, либо в инверсной форме).
Любая булева формула, не являющаяся тождественно ложной, может быть приведена к СДНФ, причём единственным образом, то есть для любой выполнимой функции алгебры логики существует своя СДНФ, причём единственная[2].
Краткая теория
правитьДНФ представляет собой «сумму произведений», причём в качестве операции «умножения» выступает операция И (конъюнкция), а в качестве операции «сложения» — операция ИЛИ (дизъюнкция). Сомножителями являются различные переменные, причём они могут входить в произведение как в прямом, так и в инверсном виде.
Ниже приведён пример ДНФ:
В составе ДНФ, вообще говоря, могут присутствовать повторяющиеся слагаемые, а в составе каждого слагаемого — повторяющиеся сомножители, например:
С математической точки зрения такое клонирование бессмысленно, так как в булевой алгебре умножение любого выражения на само себя и сложение выражения с самим собой не меняет результата ( ), а сложение выражения с собственной инверсией и умножение на собственную инверсию даёт константы ( ). В последнем выражении можно удалить повторяющиеся слагаемые и сомножители следующим образом:
По этой причине ДНФ с повторяющимися слагаемыми и сомножителями используются обычно только со вспомогательными целями, например, при аналитическом преобразовании выражений.
СДНФ является канонической формой представления булевой функции в виде ДНФ, в которой повторы слагаемых и сомножителей запрещены. Кроме того, в каждом слагаемом должны присутствовать все переменные (в прямой или инверсной форме).
Ниже приведён пример СДНФ:
Значение СДНФ состоит в том, что
- для каждой конкретной функции её СДНФ единственна и однозначна;
- СДНФ имеет однозначное соответствие с таблицей истинности функции. Каждое слагаемое СДНФ соответствует одной строке в таблице истинности, где функция равна единице. Таким образом, число слагаемых в СДНФ равно числу единичных значений, которые принимает булева функция в своей области определения;
- СДНФ элементарно получается из таблицы истинноcти функции;
- СДНФ удобна в качестве базового выражения для минимизации функции, в ней особенно просто находятся слагаемые, пригодные для «склейки».
Пример нахождения СДНФ
правитьДля того, чтобы получить СДНФ функции, требуется составить её таблицу истинности. К примеру, возьмём одну из таблиц истинности:
| 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 |
В ячейках результата отмечаются лишь те комбинации, которые приводят логическое выражение в состояние единицы. Далее рассматриваются значения переменных, при которых функция равна 1. Если значение переменной равно 0, то она записывается с инверсией. Если значение переменной равно 1, то без инверсии.
Первая строка содержит 1 в указанном поле. Отмечаются значения всех трёх переменных, это:
Нулевые значения — тут все переменные представлены нулями — записываются в конечном выражении инверсией этой переменной. Первый член СДНФ рассматриваемой функции выглядит так:
Переменные второго члена:
в этом случае будет представлен без инверсии:
Таким образом анализируются все ячейки . Совершенная ДНФ этой функции будет дизъюнкцией всех полученных членов (элементарных конъюнкций).
Совершенная ДНФ этой функции:
См. также
правитьПримечания
править- ↑ Виноградова М.С., Ткачев С.Б. Булевы функции. — М.: Изд-во МГТУ им. Н.Э. Баумана, 2007. — 32 с.
- ↑ Математическая логика. — Пермь: Изд-во ПГТУ, 1998. — 17 с. Архивировано 9 апреля 2016 года.
В статье не хватает ссылок на источники (см. рекомендации по поиску). |