Выделим наборы переменных, на которых 5=0. Это, очевидно, 0100 и 1100. Для каждого из них построим дизъюнкцию (VI и У2 на рис. 6), заменив в ней все Х1=1 их инверсиями. Заметим, что У1=0 лишь на наборе 0100, во всех остальных случаях У1=1. Точно так же, но на наборе 1100, ведет себя и У2. Легко видеть, что функция Б может быть получена как 5=У1&У2.

В "микросхемном" изображении эта структура приобретает вид (рис. 7). Здесь, очевидно, мы также воспользовались простейшим эквивалентным преобразованием — двойным отрицанием X г X. И здесь-фрагмент, выделенный штриховой, можно заменить значительно более простым функциональным эквивалентом (рис. 8).

Эквивалентными преобразованиями (X = X, ШУХ2 в Х1&Х2, хТ&^2нХ1УХ2, рядом других) можно привести исходную КНФ-или ДНФ-структуру к виду, уже не допускающему дальнейших упрощений. Такую форму называют тупиковой. В зависимости от пути, по которому ведут преобразования, получаются разные тупиковые формы. Среди них есть н предельно простые, содержащие минимально возможное число базисных элементов. Высший класс в синтезе схемы, реализующей заданную функцию (группу функций) — построение структуры минимальной сложности. К сожалению, простых средств, эффективных алгоритмов, позволяющих получить нужный результат, здесь нет. Синтез минимальных структур относится к категории так называемых переборных задач, требующих выбора среди множества возможных решений (предварительно полученных). В сколько-нибудь сложных случаях эта задача оказывается непосильной и для самой современной вычислительной техники.

Таблица 1

СПИСОК ЛИТЕРАТУРЫ

1. Бирюков С. Микросхемы серии КР1554.— Радио, 1995, № 9, с.62.

2. Акимов H.H., Ващуков Е.П., Прохоренко В.А., Шалимо В.В. Справочник.— "Беларусь", Минск, 1994

3. Виноградов Ю. RS-триггер из логических элементов. — Радио, 1995, № 6, с. 35, 36.