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

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

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

Справедливы утверждения Если f 1, f 2,…,f n импликанты булевой функции f, то f 1 f 2 … f n и f 1 f 2 … f n также являются ее импликантами. Если функция f 1 f 2 … f n есть импликанта функции f, то функции f 1, f 2,…,f n также являются импликантами функции f.

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

Правило склеивания

Правило поглощения 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, но при В=1 F(A, B, C) = 0·1 + 0·0 = 0. Следовательно, член AC не лишний

Испытаем член BC, равный 1 при B = 0, C = 1. При этом Последнее выражение равно 1 как при A = 1, так и при A = 0. Поэтому член – лишний. Испытание члена по этой же методике показывает, что он не является лишним, в итоге тупиковая форма исходной функции имеет вид:.

Пример

Метод Квайна X XF = X

Доказательство Для доказательства достаточно показать, что произвольная простая импликанта р = x i1 x i2... x in может быть получена. В самом деле, применяя к р операцию развертывания (обратную операции склеивания): A = A (x v !x) = Ax v A!x по всем недостающим переменным x i^(k+l),..., X i^n исходной функции f, получаем совокупность S конституент единицы. При склеивании всех конституент из S получим импликанту р. Последнее очевидно, поскольку операция склеивания обратна операции развертывания. Множество S конституент обязательно присутствует в совершенной ДНФ функции f поскольку р - ее импликанта.

f = !x 1 !x 2 !x 3 x 4 + !x 1 !x 2 x 3 x 4 + +!x 1 x 2 !x 3 x 4 + !x 1 x 2 x 3 x 4 + +x 1 x 2 x 3 !x 4 + x 1 x 2 x 3 x : !x 1 !x 2 x 4 ; 1 - 3: !x 1 !x 3 x 4 ; 2 - 4: !x 1 x 3 x 4 ; 3 - 4: !x 1 x 2 x 4 ; 4 - 6: x 2 x 3 x 4 ; 5 - 6: x 1 x 2 x 3.

!x 1 !x 2 x 4 + !x 1 x 2 x 4 = = !x 1 !x 2 x 4 + !x 1 x 2 x 4 + !x 1 x 4 !x 1 !x 3 x 4 + !x 1 x 3 x 4 = =!x 1 !x 3 x 4 + !x 1 x 3 x 4 + !x 1 x 4 x 2 x 3 x 4 + x 1 x 2 x 3 + !x 1 x 4

Импликатная матрица f = x 1 x 2 x 3 + !x 1 x 4

Число N крестиков в одной строке всегда является степенью 2. Более того, читатель может легко убедиться в том, что N = 2 n-k где k - число букв, содержащихся в простой импликанте

Метод Квайна-МакКласки

Этап 1

Этап 2

Импликатная матрица

Операция сжатия