Название: Вычислительная техника (Захаров Н. Г.)

Жанр: Энергетический

Просмотров: 1545


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

 

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

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

Рассмотрим применение метода непосредственных преобразований на примере минимизации функции трех переменных, заданных ее СДНФ:

у  х1  х 2  х 3  х1  х 2  х 3  х1  х 2  х 3  х1  х 2  х 3  х1  х 2  х 3 .           (2.4)

 

Объединим попарно первое и третье, второе и третье, а также четвертое и пятое элементарные произведения:

у  (х1  х 2  х 3  х1  х 2  х 3 )  (х1  х 2  х 3  х1  х 2  х 3 )  (х1  х 2  х 3 

 х1  х 2  х 3 )  х 2  х 3  (х1  х1 )  х1  х 2  (х 3  х 3 )  х1  х 2  (х 3  х 3 ) 

 х 2  х 3  х1  х 2  х1  х 2

 х 2  х 3  х1 (х 2  х 2 )  х 2  х 3  х1 .

 

Эта формула гораздо проще исходной СДНФ. Здесь в формуле (2.4) в каждой паре объединяемые элементарные произведения различаются лишь одной перемен- ной, которая входит в первое произведение с отрицанием, а во второе – без отрица- ния. Такие элементарные произведения называются соседними. К соседним произве- дениям применима операция склеивания, в результате которой уменьшается число суммируемых произведений и на единицу уменьшается число переменных.