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

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

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


O х	O у	O z	O x O y	O x O z	O уO z	O xO уO z
O х	O у	z	O x O y	O x z	O у z	O xO у z
O х	у	O z	O x y	O x O z	у O z	O x уO z
O х	у	z	O x y	O x z	y z	O x у z
х	O у	O z	x O y	x O z	O у O z	xO уO z
х	O у	z	x O y	x z	O у z	xO у z
х	у	O z	x y	xO z	у O z	x уO z
х	у	z	x y	x z	y z	x y z

В самом крайнем правом столбце стоят конъюнкции вида К = х1a1 … хnan , где хi a i = хi или хi a i = `хi . Полная карта имеет однообразный вид для всех n — местных булевых функций.

2. Разглядываем конкретную минимизируемую n — местную булеву функцию f(хn)и строим для нее множество элементарных комплектов {N}, входящих во внутренние конъюнкции СДНФ. К примеру, у функции f = (01100111)из Примера 3 множество {N} будет следующим: N 1= (x,`y, z); N 2= (x, y,`z); N 3= (x,`y, z); N 4= (x, y,`z) ; N 5= (x, y, z).

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

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



		Oу z	OxOу z
		уO z	Ox уOz


	x z	Oу z	xO у z
x y		у O z	x уO z
x y	x z		x y z

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

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

Т1= `y z U y`z U x z , Т2= `y z U y`z U x y .

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

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