Алгебраическая минимизация. 
Электротехника и электроника

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

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

=> рефлексивности (Л=Л);

=> симметричности (если А = В, то В = А);

=> транзитивности (если А = В, В = С, то А = С).

Аксиомы алгебры логики.

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

Основные законы алгебры логики.

fCnMMvmamuftHhiu (пепемегтитегткный) закон.

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

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

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

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

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

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

В выражениях (2)-г-(5), (11), (12) правая часть проще левой, поэтому путем преобразований логических функций по правилам алгебры логики можно добиться существенного упрощения исходного выражения.

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