double arrow

Основные определения. Теорема о полноте даёт ответ на вопрос, из какой системы функций можно получить в виде суперпозиции любую функцию


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

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

Минимальной ДНФ функции f(x1, ..., xn) называется ДНФ N = U1 Ú U2 Ú ... Ú Uk, представляющая функцию f(x1, ..., xn) и содер­жащая наименьшее количество букв по сравнению с другими ДНФ, то есть число букв в N равно , где ri – ранг конъюнкции Ui, а минимизация проводится по всем ДНФ функции f(x1, ..., xn).

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

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

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

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

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

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

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


Сейчас читают про: