Метод минимизирующих карт

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

1. Вначале строится полная карта всех возможных конъюнкций из переменных `х ⁿ и их отрицаний. В первых n столбцах строят все возможные одиночные сочетания из (х₁,...,х_n) и их отрицаний. В следующих n(n – 1)/2 строят все различные (с точностью до перестановок) попарные произведения переменных, стоящих в первых n столбцах. Далее строят все различные произведения по 3, 4, ... , n множителей. Ниже показана карта для 3 – местных функций.

В самом крайнем правом столбце стоят конъюнкции вида К = х₁^a1& ... & х_n^an , где х_i ^{a i} = х_i либо х_i ^{a i} = `х_i . Полная карта имеет одинаковый вид для всех n - местных булевых функций.

2. Рассматриваем конкретную минимизируемую n - местную булеву функцию f(хⁿ)и строим для нее множество элементарных наборов {N}, входящих во внутренние конъюнкции СДНФ. Например, у функции f = (01100111)из Примера 3 множество {N} будет следующим: N ₁= (x,`y, z); N <sub>2</sub>= (x, y,`z); N ₃= (x,`y, z); N <sub>4</sub>= (x, y,`z) ; N ₅= (x, y, z).

В полной карте вычеркиваем те строки, у которых в последнем столбце стоят наборы переменных, не входящие в СДНФ функции. В рассматриваемом примере – это строки 0, 3, 4. Их номера можно было бы определить по вектору истинности f , поскольку на этих местах стоят нули.

3. Все конъюнкции, попавшие в вычеркнутые строки, вычеркиваем и из оставшихся строк. В примере таблица примет следующий вид:

В каждой строке оставляем только те конъюнкции, которые имеют минимальное число сомножителей. Более длинные вычеркиваем. В примере необходимо вычеркнуть все конъюнкции в столбце 7.

4. Множество тупиковых ДНФ {T} строим следующим образом: рассматриваем все возможные логические суммы, состоящие из конъюнкций, взятых по одной из каждой строки, устраняя возможное дублирование. В примере {T} имеет вид:

Т₁= `y z Ú y`z Ú x z , Т₂= `y z Ú y`z Ú x y .

5. Из множества тупиковых ДНФ {T} выбираем формы с минимальным количеством переменных, которые и будут искомыми минимальными формами.

Обе тупиковые формы являются также и минимальными.

ЗАДАЧИ

1. Доказать справедливость следующих правил преобразования нормальных форм:

а) полного склеивания,

б) неполного склеивания,

в) поглощения,

г) удаления дубликатов.

2. Доказать, что к простым элементарным наборам не применимы правила склеивания.

3. Построить СкДНФ, СкВНФ (в базисах {Ø, ¯} и {¯}) для функций:

а) Ø (x y) | (z Ú u) ; б) (x y ® z u) ® z ; в) (x ® u) (z Ú y) ;г) (01101110) ;д) (0110001010001001); е) (0011100101011010); ж) (1001011011000101).

4. Построить МДНФ, МВНФ (в базисах {Ø, ¯} и {¯}) следующих функций:

а) (x ® y) ® y z ; б) (x ® y z) ® u ; в) (x y | u) (x y ® z u);г) (01010011) ;д) (1000001010011000) ; е) (0101100101101000);ж) (1100010001100011).

5. Построить СкКНФ, СкШНФ (в базисах {Ø , |} и { | }) для функций:

а) (x y)|(z Ú u) ; б) (x ® y z) ® u ; в) (x y| u) Å (x y ® z u);г) (11010110) ; д) (1110101011101001); е) (0111101101011110) ;ж) (1101011011010101).

6. Построить МКНФ, МШНФ ( в базисах {Ø , | } и { | }) для функций:

а) (x ® y) ® y z; б) (x ® yz); в) (1110011011001011); г) (x ® u) Ú z y ;д) x y ® z u ;е) (01110110); ж) (0111100101111010);з) (1011101011011001).

7. Построить по методу минимизирующих карт МДНФ следующих функций: а)(xy ® zu) ® z;б) (x® u) (zÚ y);в) (01101011);г) (0010111010001010).

8. Рассмотреть метод минимизирующих карт для МКНФ и построить минимальные формы для функций: а) x y® z u ; б) (01100101); в) (0110110011011010).