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

Для функций с небольшим числом переменных можно использовать метод минимизирующих карт. Рассмотрим метод на примере ДНФ. Допустим, необходимо построить МДНФ 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).

1.7.Частично определенные функции.Их минимальное доопределение

При конструировании логических устройств зачастую встречаются ситуации, когда у реализуемой ими булевой функции f(хⁿ) на некоторой части наборов переменных`хⁿ значения функции не заданы. Обычно так бывает в тех случаях, когда состояния системы, описываемые данными наборами переменных, физически не достижимы либо срабатывание управляющей системы не влияет на производственный процесс. Допустим, необходимо реализовать функцию трех переменных f =(010??001), у которой в векторе истинности на местах с номерами 3 и 4(соответствующих наборам переменных (011) и (100)) значения не заданы и могут быть выбраны любыми (0 или 1).

Определение. Если значения функции f(хⁿ) не определены на некотором числе p наборов ее переменных`хⁿ, то ее называют частично определенной, сокращенно – ЧОФ.

Очевидно, доопределить (то есть присвоить недостающие значения истинности функции ¦ на p неопределенных наборах) можно 2^P способами. В рассмотренном выше примере р =2; 2^P =4. Наборам с номерами 3 и 4 могут быть присвоены значения (00), (01), (10), (11).

Определение. Функция g называется доопределением частично определенной функции ¦, если она совпадает с ней на тех наборах, где ¦ определена.

Например, функция g = (01000001) является одним из 4 возможных доопределений частично определенной функции ¦ =(010??001).

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

Определение. Пусть f(хⁿ)– частично определенная функция. Ее единичным f₁(хⁿ)(нулевым f₀(хⁿ)) доопределением называют такое доопределение, где на месте неизвестных значений ¦ стоят только единицы (нули).

Допустим, для ЧОФ необходимо построить нормальную форму заданного типа.

Определение. Минимальным доопределением частично определенной функции f называют ее доопределение g, имеющее минимальное число символов переменных, входящих в соответствующую нормальную форму.

Для ДНФ справедлива следующая теорема.

Теорема 2.1.1 о минимальном допределении частично определенной функции.