Минимизация функций в классе ДНФ

Проблема простейшего представления функций в заданном базисе связана с изучением свойств функций этого базиса. В настоящее время существенные результаты получены для базиса, состоящего из отрицания, конъюнкции и дизъюнкции. Именно этот базис и будет рассматриваться в дальнейшем.

Любая функция алгебры логики может быть записана в виде СДНФ. То, что запись в СДНФ часто является неэкономной, видно из примера.

ПримерПример 1. Пусть задана СДНФ

`xx<sub>2</sub> (xx<sub>1</sub>,xx<sub>2</sub>,xx<sub>3</sub>)=xx<sub>1</sub>xx<sub>2</sub>xx<sub>3</sub>Úxx<sub>1</sub>xx<sub>2</sub>` xx₃ Úxx₁`xx<sub>2</sub>xx<sub>3</sub>Ú xx<sub>1</sub>`xx₂`xx<sub>3</sub> Ú`xx₁xx₂xx₃.

Преобразуем эту СДНФ. Добавим еще один конъюнктивный член x₁x₂x₃. Это добавление не меняет данной функции, так как xxÚxx=xx,

ff(xx₁,xx₂,xx₃)=xx₁xx₂xx₃Úxx₁xx₂`xx<sub>3</sub>Úxx<sub>1</sub>`xx₂xx₃Úxx₁`xx<sub>2</sub>`xx₃Úxx₁xx₂xx₃Ú`xx₁xx₂xx₃.

Преобразуем это выражение, используя равенства: aa`bb Ú aabb=aa (операция склеивания) и aa×bbÚaa=aa, aa×bbÚ`aa=bbÚ`aa (операция поглощения).

Получим:

ff(xx₁,xx₂,xx₃)=xx₁xx₂(xx₃Ú`xx<sub>3</sub>)Úxx<sub>1</sub>`xx₂(xx₃Ú`xx<sub>3</sub>)Úxx<sub>2</sub>xx<sub>3</sub>(xx<sub>1</sub>Ú`xx₁)=xx₁xx₂Úxx₁`xx₂Úxx₂xx₃.

Аналогично предыдущему делаем дальнейшие преобразования:

ff(xx₁,xx₂,х₃)=xx₁(xx₂Ú`xx₂)Úxx₂xx₃=xx₁Úxx₂xx₃.

Если к исходной ДНФ применять лишь операции склеивания и поглощения, то наступит момент, когда эти преобразования окажутся уже невозможными. В этом случае получим тупиковую ДНФ (ТДНФ). Среди множества ТДНФ содержится и МДНФ. Получая всевозможные тупиковые ДНФ и сравнивая их по числу букв, можно найти все минимальные формы для данной функции. Величина необходимого перебора определяется числом элементов класса тупиковых ДНФ для функции алгебры логики, зависящей от n аргументов, и может быть очень большой.