Минимизация булевых функций

Аналитические методы минимизации

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

Представление булевой функции в Сов ДНФ в большинстве случаев не является минимальным.

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

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

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

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

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

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

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

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

.

Испытаем член 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. Поэтому член – лишний.

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

.