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

О необходимости минимизации

Структурные формулы в виде логических функций в СДНФ и СКНФ однозначно определяют структуру логической схемы комбинационного устройства. Однако нельзя быть уверенным в том, что построенное по такой формуле устройство будет наиболее полно удовлетворять заданным требованиям. Если рассматривать тождество алгебры логики для двух логических функций , то в общем случае количество операций в правой части тождества не равно числу операций в левой части. Так как для реализации каждой операции необходим логический элемент, то следует отдать предпочтение комбинационному устройству, структурная формула которого имеет меньшее число операций. Поэтому путем тождественных преобразований структурной формулы, приводящих только к изменению ее формы, а не значений, можно упростить схему комбинационного устройства. Преобразование структурной формулы с целью упрощения комбинационного устройства называется ее минимизацией.

Алгебраическая минимизация. Метод алгебраической минимизации структурных формул комбинационных устройств, представленных логическими функциями в СДНФ и СКНФ, состоит в упрощении исходного выражения с помощью аксиом, законов и тождеств алгебры логики. Ниже кратко изложены ее основные положения. В приведенных соотношениях символы А, В, С могут отражать как логические переменные, так и логические функции.

В алгебре логики определены три рассмотренные выше основные логические операции (отрицание, сложение и умножение) и отношение эквивалентности ( = ), удовлетворяющее следующим свойствам:

  • • рефлексивности (А = А);
  • • симметричности (если А = В, то В = А);
  • • транзитивности (если А = В, В = С то А = С).

Приведем аксиомы алгебры логики

(3.6)

(3.7)

(3.8)

(3.9)

(3.10)

(3.11)

Аксиома (3.6) отражает тот уже известный факт, что алгебра логики оперирует только с двоичными переменными. Аксиомы (3.7)-(3.11) являются по сути дела более общей формой представления рассмотренных выше правил логического сложения, умножения и отрицания двоичных переменных.

Рассмотрим основные законы алгебры логики.

Коммутативный (переместительный) закон

(3.12)

Ассоциативный (сочетательный) закон

(3.13)

Дистрибутивный (распределительный) закон

(3.14)

Закон двойственности (теорема де Моргана)

(3.15)

Другие соотношения.

Правило поглощения

(3.16)

Правило склеивания

(3.17)

Приведенные аксиомы, законы и соотношения, за исключением (3.11), записаны парами. Каждое из входящих в пару выражений может быть получено из другого заменой операций сложения на умножение, 0 на 1 и наоборот. Если в логическое выражение входят операции сложения и умножения, то следует соблюдать порядок выполнения операций: сначала выполняется умножение, затем – сложение. В сложных логических выражениях для задания порядка выполнения операций используются скобки.

В выражениях (3.7)-(3.10), (3.16), (3.17) правая часть проще левой, поэтому путем соответствующих преобразований можно добиться существенного упрощения исходного выражения.

 
< Пред   СОДЕРЖАНИЕ     След >