Основные определения

Теорема о полноте даёт ответ на вопрос, из какой системы функций можно получить в виде суперпозиции любую функцию. Но в практических задачах нужна не столько возможность, сколько правила, пользуясь которыми можно получить представление, оп­тимальное в некотором смысле. Каждое представление функции в виде суперпозиции можно охарактеризовать некоторым числом, которое называется сложностью данного представления (напри­мер, число применений операции суперпозиции) и зависит от кон­кретной задачи. Тогда можно поставить задачу об отыскании пред­ставления логической функции наименьшей сложности. В принципе, такую задачу всегда можно решить последовательным перебором различных суперпозиций функций системы.

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

Минимальной ДНФ функции f(x₁, ..., x_n) называется ДНФ N = U₁ Ú U₂ Ú ... Ú U_k, представляющая функцию f(x₁, ..., x_n) и содер­жащая наименьшее количество букв по сравнению с другими ДНФ, то есть число букв в N равно , где r_i – ранг конъюнкции U_i, а минимизация проводится по всем ДНФ функции f(x₁, ..., x_n).

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

Прежде чем описать метод решения задачи дадим ещё несколь­ко определений.

Импликантом функции f(x₁, ..., x_n) называется эле­мен­тарная конъюнкция если выполнено соотношение U_i ® f(x₁, ..., x_n) º 1. Это означает, что если на некотором наборе импликант U_i обращается в единицу, то функция f(x₁, ..., x_n) на этом наборе тоже обращается в единицу. Любая элементарная конъюнк­ция произвольной СДНФ является импликантом данной функции.

Простым импликантом функции f(x₁, ..., x_n) называ­ется им­пликант функции f(x₁, ..., x_n), если элементарная конъюнкция, полу­чающаяся из него удалением любой буквы, не является импликан­том функции.

Сокращенной ДНФ функции f(x₁, ..., x_n) называется дизъюнк­ция всех простых импликантов функции f(x₁, ..., x_n).

Теорема 5 (без доказательства). Сокращённая ДНФ представляет функцию f(x₁,..., x_n).

Теорема 6 (без доказательства). Минимальная ДНФ функции f(x₁, ..., x_n) получается из ее сокращённой ДНФ удалением некото­рых элементарных конъюнкций.