В классе КНФ

Построение минимальных КНФ для частично определенной функции аналогично построению минимальных КНФ для всюду определенной функции.

Алгоритм минимизации частично определенных функций в классе нормальных форм аналогичен алгоритму минимизации в классе нормальных форм для всюду определенных функций.

Пример 1. В классе нормальных форм минимизировать частично определенную функцию f (x, y, z, t) = (1---010010-01--1)

Решение. Минимизируем функцию f в классе ДНФ.

1. Строим сокращенную ДНФ для доопределения единицами f ₁ функции f по таблице 3.9.

Таблица 3.9

x y z t	f f 0 f 1 ` f h 0 h 1
0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1	1 1 1 0 0 0 - 0 1 - 0 1 - 0 1 - 0 1 - 0 1 - 0 1 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 - 0 1 - 0 1 0 0 0 1 1 1 1 1 1 1 1 1 - 0 1 - 0 1 - 0 1 - 0 1 1 1 1 0 0 0

2. Строим матрицу покрытий коституент единицы в СДНФ для доопределения нулями f ₀ функции f с помощью построенной сокращенной ДНФ для f ₁ (таблица 3.10).

Таблица 3.10

N	ПИ
					+	+
		+
				+	+
		+		+
			+
			+

3. По таблице строим решеточный многочлен

E = (2Ú 4)(5Ú 6)(3Ú 4)(1Ú 3)1 = 145 Ú 125 Ú 146 Ú 1236.

4. Строим все тупиковые ДНФ:

5. Из построенных тупиковых ДНФ выбираем минимальные:

Функции g ₁ и g ₃ есть минимальные доопределения функции f в классе ДНФ.

Минимизируем теперь функцию f в классе КНФ. Для этого проведем минимизацию функции ` f в классе ДНФ Пусть h <sub>0</sub> и h <sub>1</sub> есть доопределение нулями и единицами соответственно функции ` f.

Сокращенная ДНФ для

Матрица покрытия конституент единицы в СДНФ для h ₀ с помощью простых импликант в сокращенной ДНФ для h ₁ приведена в таблице 3.11.

Таблица 3.11

N	ПИ
					+	+
			+	+
			+
					+
		+	+
						+

 

3. Решеточное выражение E =5 (2 Ú 3 Ú 5) 2 (1Ú 4)(1Ú 6) = 25(1Ú 46) = 125 Ú 2446.

4. Строим две тупиковые ДНФ:

и

Минимальная.

5. Функция есть минимальное доопределение функции f в классе КНФ.

Найденные МДНФ g ₁, g ₃ и МКНФ являются минимальными доопределениями функции f в классе нормальных форм.

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