4.3. Минимизация логических функций

Процедура алгебраической минимизации логических функций известна студентам из курса дискретной математики, поэтому напомним только основные положения.

Смежными называют те минтермы, которые отличаются формой вхождения только одного аргумента ( и ). При склеивании по ИЛИ в результате исчезает этот элемент (X3). Результат склеивания называется импликантой . При склеивании импликант первого уровня получим более короткие импликанты второго уровня и т.д. Таким образом, в результате склеивания 2^m соседних минтермов получаем импликанту, которая не зависит от m переменных. Импликанты, которые не поддаются склеиванию, называют простыми. Из минтермов, не имеющих соседних, и простых минтермов получается сокращенная ДНФ. Некоторые импликанты в ней могут быть избыточными. В результате удаления этих импликант получают тупиковую ДНФ (несколько вариантов).

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

Метод Карно-Вейча

Карты Карно – прямоугольные таблицы, состоящие из 2ⁿ клеток, где n – число переменных. Каждая клетка соответствует уникальному набору переменных и заполняется соответствующим значением функции. Соседние клетки должны соответствовать соседним минтермам.

Для склеивания минтермов следует объединять их так, чтобы охватить всю совокупность единичных ячеек минимальным числом импликант.

Следует иметь в виду, что:

1. можно включать одну клетку в несколько импликант;

2. смежными являются клетки на противоположных краях таблицы;

3. объединять можно только 2^К клеток, где К – целое;

4. объединение надо начинать с клеток, у которых соседняя только одна единичная клетка.

П ример_2.

X0	X1	X2	X3	f	X0	X1	X2	X3	f
0	0	0	0	1	1	0	0	0	1
0	0	0	1	0	1	0	0	1	0
0	0	1	0	1	1	0	1	0	1
0	0	1	1	1	1	0	1	1	1
0	1	0	0	0	1	1	0	0	0
0	1	0	1	1	1	1	0	1	1
0	1	1	0	1	1	1	1	0	1 Результат
0	1	1	1	1	1	1	1	1	1

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

Пример 3

X0	X1	X2	X3	f	X0	X1	X2	X3	f
0	0	0	0	0	1	0	0	0	1
0	0	0	1	Ф	1	0	0	1	Ф
0	0	1	0	0	1	0	1	0	1
0	0	1	1	1	1	0	1	1	0
0	1	0	0	1	1	1	0	0	Ф
0	1	0	1	Ф	1	1	0	1	Ф
0	1	1	0	0	1	1	1	0	1
0	1	1	1	1	1	1	1	1	0

Результат