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

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

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

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

4 Справедливы утверждения Если 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.

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

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

7 Правило поглощения X XF = X.

8 Пример

9 Испытаем член 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 не лишний

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

11 Пример

12

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

14 Доказательство Для доказательства достаточно показать, что произвольная простая импликанта р = 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 поскольку р - ее импликанта.

15 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.

16 !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

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

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

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

20 Этап 1

21 Этап 2

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

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

24