Меню Главная Случайная статья Настройки Совершенная дизъюнктивная нормальная форма Материал из https://ru.wikipedia.org Совершенная дизъюнктивная нормальная форма (СДНФ) — одна из форм представления функции алгебры логики (булевой функции) в виде логического выражения. Представляет собой частный случай ДНФ, удовлетворяющий следующим трём условиям[1]: в ней нет одинаковых слагаемых (элементарных конъюнкций); в каждом слагаемом нет повторяющихся переменных; каждое слагаемое содержит все переменные, от которых зависит булева функция (каждая переменная может входить в слагаемое либо в прямой, либо в инверсной форме). Любая булева формула, не являющаяся тождественно ложной, может быть приведена к СДНФ, причём единственным образом, то есть для любой выполнимой функции алгебры логики существует своя СДНФ, причём единственная[2]. Содержание 1 Краткая теория 2 Пример нахождения СДНФ 3 См. также 4 Примечания Краткая теория ДНФ представляет собой «сумму произведений», причём в качестве операции «умножения» выступает операция И (конъюнкция), а в качестве операции «сложения» — операция ИЛИ (дизъюнкция). Сомножителями являются различные переменные, причём они могут входить в произведение как в прямом, так и в инверсном виде. Ниже приведён пример ДНФ: ${\displaystyle F(A,B,C,D,E)={\bar {A}}B+A{\bar {B}}E+B{\bar {C}}D.}$ В составе ДНФ, вообще говоря, могут присутствовать повторяющиеся слагаемые, а в составе каждого слагаемого — повторяющиеся сомножители, например: ${\displaystyle F(A,B,C,D,E)={\bar {A}}B{\bar {B}}+A{\bar {B}}EA+B{\bar {C}}D+B{\bar {C}}D.}$ С математической точки зрения такое клонирование бессмысленно, так как в булевой алгебре умножение любого выражения на само себя и сложение выражения с самим собой не меняет результата (${\displaystyle x+x=x;x\cdot x=x}$), а сложение выражения с собственной инверсией и умножение на собственную инверсию даёт константы (${\displaystyle x+{\bar {x}}=1;x\cdot {\bar {x}}=0}$). В последнем выражении можно удалить повторяющиеся слагаемые и сомножители следующим образом: ${\displaystyle F(A,B,C,D,E)={\bar {A}}B{\bar {B}}+A{\bar {B}}EA+B{\bar {C}}D+B{\bar {C}}D={\bar {A}}\cdot (B{\bar {B}})+(AA)\cdot {\bar {B}}E+B{\bar {C}}D={\bar {A}}\cdot 0+A{\bar {B}}E+B{\bar {C}}D=A{\bar {B}}E+B{\bar {C}}D.}$ По этой причине ДНФ с повторяющимися слагаемыми и сомножителями используются обычно только со вспомогательными целями, например, при аналитическом преобразовании выражений. СДНФ является канонической формой представления булевой функции в виде ДНФ, в которой повторы слагаемых и сомножителей запрещены. Кроме того, в каждом слагаемом должны присутствовать все переменные (в прямой или инверсной форме). Ниже приведён пример СДНФ: ${\displaystyle F(A,B,C,D,E)={\bar {A}}BCDE+A{\bar {B}}C{\bar {D}}E+AB{\bar {C}}D{\bar {E}}.}$ Значение СДНФ состоит в том, что для каждой конкретной функции её СДНФ единственна и однозначна; СДНФ имеет однозначное соответствие с таблицей истинности функции. Каждое слагаемое СДНФ соответствует одной строке в таблице истинности, где функция равна единице. Таким образом, число слагаемых в СДНФ равно числу единичных значений, которые принимает булева функция в своей области определения; СДНФ элементарно получается из таблицы истинности функции; СДНФ удобна в качестве базового выражения для минимизации функции, в ней особенно просто находятся слагаемые, пригодные для «склейки». Пример нахождения СДНФ Для того, чтобы получить СДНФ функции, требуется составить её таблицу истинности. К примеру, возьмём одну из таблиц истинности: ${\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}}})}$ См. также Дизъюнктивная нормальная форма Конъюнктивная нормальная форма Совершенная конъюнктивная нормальная форма Примечания Виноградова М.С., Ткачев С.Б. Булевы функции. — М.: Изд-во МГТУ им. Н.Э. Баумана, 2007. — 32 с.