Информатика и вычислительная техника


Преобразование и минимизация логических выражений - часть 3


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

114

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

На рис. 5.5 показаны карты Карно для двух, трех и четырех аргументов, содержащие соответственно 4, 8 и 16 клеток.

Рис. 5.5. Карты Карно для двух (а), трех (б) и четырех (в) аргументов

В клетки карты Карно, соответствующие тем наборам аргументов, для которых минимизируемая функция в соответствии с заданной таблицей принимает единичное значение, заносятся единицы. При этом две конъюнкции, находящиеся в соседних клетках карты, могут быть заменены одной конъюнкцией, содержащей на одну переменную меньше. Если соседними являются две пары конъюнкций, то такая группа из четырех конъюнкций может быть заменена конъюнкцией, которая содержит на две переменные меньше. В общем случае наличие минтермов в 2n соседних клетках позволяет исключить n переменных.

Правила применения карт Карно состоят в следующем.

1. Если единица находится в двух соседних клетках строки, столбца или на противоположных концах любой строки или столбца, то соответствующие

115

этим единицам конъюнкции заменяются одной конъюнкцией на ранг ниже, причем в нее включаются переменные с одинаковыми показателями инверсии.

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

3. Конъюнкции, соответствующие оставшимся единицам, сохраняются без изменения.

Рассмотрим применение карт Карно на примерах.

Для функции F(x1, х2, x3), заданной таблицей 5.4, ДСИФ имеет вид:

F(x1, x2, x3) = x1 & x2 & x3 ? x1 & x2 & x3 ? x1 & x2 & x3 ? x1 & х2 & х3.

Таблица 5.4




Начало  Назад  Вперед