Аналитические методы минимизации булевых функций. Метод Квайна. Метод карт Карно. Простые импликанты (стр. 1 )

Аналитические методы минимизации булевых функций.

Метод Квайна. Метод карт Карно. Простые импликанты.

Под литералом будем понимать булевскую переменную или ее отрицание.

Рассмотрим СДНФ некоторой функции. Если функция имеет К единиц, то число литералов, входящих в СДНФ, равно произведению (К*n), где n – число переменных.

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

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

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

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

Элементарную конъюнкцию φк назовем импликантой булевой функции f, если не существует такого двоичного набора переменных, при котором функция φк принимает значение 1, а функция f – значение 0, то ecть φk Ú f = f.

Для того чтобы проверить является ли заданная элементарная конъюнкция импликантой функции f, следует всем переменным, которые входят в эту конъюнкцию без знака отрицания, придать значение 1, а тем переменным, которые входят с отрицанием – значение 0. Тогда элементарная конъюнкция будет иметь истинностное значение 1. После этого следует, проверить, принимает ли функция f значение 1 при любых значениях остальных переменных. В дальнейшем для упрощения записи булевых функций знаки конъюнкции будем заменять знаками умножения или просто опускать.

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

.

Решение. Полагая в первом случае Х1 = 1, X2 = 1, имеем φ1 = l и φ2 = l и

,

следовательно, φ2 – импликанта заданной функции.

Во втором случае полагаем X1 = 0, X2 = l. Тогда

φ2 = 1, а ,

следовательно, φ2 не является импликантой функции f.

Справедливы следующие утверждения:

1. Если импликанты булевой функции f, то и также являются ее импликантами.

2. Если функция есть импликанта функции f, то функции также являются импликантами функции f.

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

Сокращенной ДНФ данной булевой функции называется ее ДНФ, составленная только из простых импликант.

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

.

Например,

Используя операции поглощения и склеивания, его можно существенно упростить. Часто используется неполное склеивание, при котором оба члена, участвовавших в склеивании (или один из них), могут повторно склеиваться с другими оставшимися членами СДНФ.

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

Две смежные конституенты, склеиваясь, образуют импликанту рангом на единицу ниже, чем исходные конституенты.

Используя, например, неполное склеивание последней коституенты в СДНФ функции F1 последовательно с остальными, приходим к следующему выражению:

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

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

Сокращенная ДНФ, из которой удалены все лишние импликанты, называется тупиковой ДНФ

Исключение лишних импликант из сокращенной ДНФ проводится с помощью правила поглощения: дизъюнкцию двух элементарных конъюнкций, из которых одна полностью содержится и другой, можно заменить конъюнкцией, имеющей меньший ранг, например, X Ú XF = X,

.

Правила склеивания, и поглощения легко доказываются с помощью таблиц истинности. Кроме этих правил, при минимизации функции могут быть использованы любые известные равносильности.

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

Найдем для примера тупиковую форму Сокр ДНФ

.

Испытаем член AC. AC = 1, если A = 1 и C = 1. Подставим в оставшееся выражение A = 1 и C = 1, получим

.

При B = 0 F(A, B, C) = 1·1 Ъ 0·0 = 1, но при F(A, B, C) = 0·1 Ъ 0·0 = 0. Следовательно, член AC не лишний.

Испытаем член BC, равный 1 при B = 0, C = 1. При этом

.

Последнее выражение равно 1 как при A = 1, так и при A = 0. Поэтому член – лишний.

Испытание члена по этой же методике показывает, что он не является лишним, в итоге тупиковая форма исходной функции имеет вид:

.

Пример. Найти минимальную ДНФ для функции

.

Решение. Склеивая первый и третий одночлены по переменной Х2, получим Х1X3X4. Из первого и четвертого, а затем из второго и третьего слагаемых после склеивания получим соответственно X1X2X3, и т. д. Окончательный список импликант имеет вид

В этом списке имеется два одночлена X1X3 и Х2Х3Х4, которые не поглощают других одночленов из этого списка, следовательно, являются простыми импликантами. Поэтому сокращенная ДНФ имеет вид

,

οна же является и минимальной

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

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