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

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

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

	1	2	3	4	5	6	7
0	 х	 у	 z	 x  y	 x  z	 у z	 x у z
1	 х	 у	z	 x  y	 x z	 у z	 x у z
2	 х	у	 z	 x y	 x  z	у  z	 x у z
3	 х	у	z	 x y	 x z	y z	 x у z
4	х	 у	 z	x  y	x  z	 у  z	x у z
5	х	 у	z	x  y	x z	 у z	x у z
6	х	у	 z	x y	x z	у  z	x у z
7	х	у	z	x y	x z	y z	x y z

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

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

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

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

	1	2	3	4	5	6	7
0
1						у z	xу z
2						у z	x уz
3
4
5					x z	у z	x у z
6				x y		у  z	x у z
7				x y	x z		x y z

В каждой строке оставляем только те конъюнкции, которые имеют минимальное число сомножителей. Более длинные вычеркиваем. В примере необходимо вычеркнуть все конъюнкции в столбце 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).