8.5. Метод поразрядного сравнения рабочих и запрещенных наборов

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

Покажем это на примере минимизации функции «импликация х в y»:

х

у

(0)	0
(0)	1
1	(1)

1

0

Здесь отдельно записаны три рабочих (единичных) набора: 00, 01, 11. Набор 10 запрещенный (нулевой). Видно, что в наборе 00 достаточно оставить переменную x, поскольку значение этой переменной в одном – единственном запрещенном наборе равно 1. Таким образом, получили импликанту (0-). Эта же импликанта покрывает и набор 01. Тогда для набора 11 необходимо оставить переменную y, то есть, получили импликанту (-1). Таким образом, импликация представлена в виде (0-)(-1), то есть xy =xy.

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

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

Дано: двоичная переключательная функция (ПФ) №174₁₀ (табл. 39).

Получим соответствующий двоичный код: 10101110₂ (2⁷+2⁵+2³+2²+2¹).

Таблица 39

Таблица истинности ПФ №174₁₀

Минимизируем ПФ по кубу соседних чисел (рис. 49, рабочие вершины закрашены):

Рис. 49. Минимизация ПФ №174₁₀ по решетке Хассэ

Квадрат соответствует обобщенному коду – импликанте (--1).

Ребро соответствует обобщенному коду – импликанте (01–)

Таким образом, ДНФ ПФ имеет вид: , т.е f(abc)=c a b.

На использовании куба соседних чисел основан метод поразрядного сравнения рабочих и запрещенных восьмеричных наборов – метод Л.Ф. Викентьева [6, 17].