Дискретная математика:
логика, группы, графы, фракталы

Акимов О.Е.

1.2. Формы представления булевых функций

Минимизация по методу сочетания индексов

Не менее эффективным способом минимизации логических функций является метод сочетания индексов. Для его изложения составим табл. 1.12, в столбцах которой записаны возможные сочетания индексов. В последней графе выписаны значения функции y. Анализ таблицы начинается слева по столбцам. Принцип исключения i,j-кода следующий. На пересечении i-столбца, например с сочетанием индексов 23, и j-строки, например 3-й, находится код 10, что соответствует импликанте x₂x₃. Следовательно, в этом столбце везде, где встречается код 10, т.е. в строках 2, 3, 10 и 11, эти коды исключаются, поскольку значение функции в 3-й строке равно нулю. Теперь возьмем столбец с сочетанием индексов 124. Здесь во 2-й и 6-й строках оставлены коды 010, а в 10-й и 14-й строках — код 011. Сделано это потому, что эти коды встречаются только на строках со значением функции, равным единице. Напротив, код 110 этого же столбца встречается как при единичных значениях функции, так и при нулевых.

Таблица 1.12

Итак, все коды на строках, заканчивающихся нулевыми значениями функции, исключаются автоматически. Если эти коды попадают на строки, заканчивающиеся единичным значением функции, то они также не учитываются. Остаются только те коды, которые расположены на строках с единичным значением функции (эти коды затемнены).

Далее руководствуются следующим правилом. Для того чтобы функция приняла значение, равное единице, достаточно того, чтобы только какая-нибудь одна импликанта на строке приняла единичное значение. Прежде всего оставляем минимальную импликанту x₂x₁, которая перекрывает единицы в строках 2, 6, 10 и 14. Затем, естественно, обращаемся к 12-й строке. Здесь оставляем единственный на строке код 011, что отвечает импликанте x₄x₃x₂. Эта же импликанта ответственна за 13-ю строку, оканчивающуюся тоже единицей. Осталось рассмотреть 5-ю и 7-ю строки. Общей для них является импликанта x₄x₃x₁.

Таким образом, тремя импликантами мы перекрыли все единичные значения функции, что совпадает с результатом, полученным на основе таблицы Куайна.