Минимизация функций алгебры логики

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

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

f(x₁, x₂, x₃)= &x₂&x₃ x₁& x₂& x₁& & x₃ x₁& & & x₂& x₃.

Добавим к функции один конъюнктивный член &x₂&x₃. Это добавление не меняет данной функции, так как x x=x:

f(x₁, x₂, x₃)= x₂x₃ x₁ x₂ x₁ x₃ x₁ x₂x₃ x₂x₃.

Преобразуем это выражение, используя сочетательные и распределительные свойства конъюнкции и дизъюнкции:

f(x₁, x₂, x₃)= x₂ (x₃ ) x₁ ( x₃ ) x₂ x₃ (x₁ ).

Используя свойство дизъюнкции, получаем:

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

.

Из примера виднанеэкономность совершенных нормальных форм для представления ФАЛ.

Проблема простейшего представления функций сводится к проблеме выбора базиса и проблеме наиболее экономного представления функций в этом базисе.

К настоящему времени существенные результаты в решении задачи минимизации лишь в базисе, состоящем из отрицания, конъюнкции и дизъюнкции.

Приведем ряд определений.

Определение. Конъюнкция называется элементарной, если в этой конъюнкции каждая переменная встречается не более одного раза.

Определение. Ранг элементарной конъюнкции – это число элементов, образующих эту конъюнкцию. Ранг – это ''n''.

Определение. Дизъюнкция элементарных конъюнкций называется дизъюнктивной нормальной формой (ДНФ).

Определение. ДНФ для функции f(x₁, x₂,…,x_n), состоящей из элементарных конъюнкций ранга n, называется дизъюнктивной совершенной нормальной формой.

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

Определение.Длиной ДНФ называют число элементарных конъюнкций, образующих эту ДНФ.

Определение.ДНФ, имеющая наименьшую длину по сравнению со всеми другими ДНФ, эквивалентными данной функции, называют кратчайшей ДНФ.

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

Аналогичные определения можно дать для случая конъюнктивных нормальных форм.

Дизъюнктивная (конъюнктивная) нормальная форма – это дизъюнкция (конъюнкция) конечного числа различных членов, каждый из которых представляет собой конъюнкцию (дизъюнкцию) отдельных переменных или их отрицаний, входящих в данный член не более одного раза.

, где

U₁,…U_n — элементарные конъюнкции.

,

где все различны; число r– ранг конъюнкции.

Известно, что любая булева функция, отличная от нуля, может быть представлена совершенной ДНФ.f(x₁,…,x_n)= ,

Совершенная ДНФ есть частный случай ДНФ.

Члены Д(К)НФ, представляющие собой элементарные конъюнкции (дизъюнкции) k букв, называют минитермами (макстермами) k ранга.

Если исходная формула содержит другие операции, то они предварительно выражаются через &, V, ù, например,

Определение.Импликантом функции f(x₁,…,x_n) называется элементарная конъюнкция если выполнено соотношение ,где .

Пример. Элементарная конъюнкция являетсяимпликантойфункции .

Очевидно, любая элементарная конъюнкция произвольной ДНФ, представляющей функции f(x₁,…,x_n), является ее импликантом, так как если эта элементарная конъюнкция на некотором наборе обращается в единицу, то функция f(x₁,…,x_n) тоже обращается в единицу.

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

Пример. –простаяимпликантабулевой функции , а импликанта не является простой для этой функции, так как (собственная часть импликанты ) является импликантой функции F .

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

Пример. являетсяСкДНФ булевойфункции . Отметим, что СкДНФ является единственной для конкретной булевой функции F .

Определение. ДНФ булевой функции F, содержащая наименьшее число слагаемых среди всех ДНФ, реализующих функцию F, называется кратчайшей ДНФ (КрДНФ).

Пример. –КрДНФэтой же булевой функции .

Вообще говоря, для заданной булевой функции F существует несколько различных по числу вхождений литералов КрДНФ.

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

Отметим, что для заданной булевой функции F существует, вообще говоря, несколько МДНФ, отличающихся друг от друга числом слагаемых.

Более того, МДНФ не всегда совпадает с КрДНФ булевой функции n переменных F . Хотя для начальных значений n (n=2 или n=3) МДНФ всегда совпадает с КрДНФ.)

Пример. является КрДНФ и МДНФ рассматриваемой функции .

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

Легко понять, что любая минимальная ДНФ является тупиковой, а обратное не верно.

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

Рассмотрим первый этап получения сокращенной ДНФ. Именно, укажем метод получения сокращенной ДНФ функции f(x₁,…,x_n) из СДНФ функции f(x₁,…,x_n) последовательным применением к ней двух равносильных преобразований:

1. Операции полного склеивания, которая состоит в замене выражения на А.

2. – операции неполного склеивания, которая состоит в замене выражения на , так как .

3. Операции поглощения, которая состоит в замене выражения на ,гдеА и В – произвольно элементарные конъюнкции.

В общем случае процесс построения минимальных ДНФ может быть охарактеризован следующей схемой