МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ АЛГЕБРЫ ЛОГИКИ

Аналитический метод минимизации ФЛ

Определение. Минимальная форма (МКФ и МДФ) представления ФЛ это форма, которая содержит минимальное количество термов и переменных в термах, и не должна допускать последующих упрощений.

Например, функция x1+x2 может быть упрощена, если применить распределительный закон: x1x2+x3=(x1+x3)(x2+х3), тогда

x1+x2=(+x1)(x1+х2)=x1+x1x1+х2+x1x2=

=0+x1+х2(+x1)=x1+х2.

Упрощение сложных логических выражений может быть осуществлено на основании применения законов и аксиом алгебры логики, изложенных выше.

Пример. Пусть задана СДНФ

x1x2x3+x1x2+x1x3+x1+x2x3=

(добавим еще один конъюнктивный терм x1x2x3 согласно аксиомы х+х=х,) тогда,

=x1x2x3+x1 x2+x1x3+x1+x1x2x3+x2x3=

(используем сочетательное и распределительное свойство конъюнкции и дизъюнкции)

=x1x2(x3+)+x1(x3+)+x2x3(x1+)=

=x1x2+x1+x2x3=x1(x2+)+x2x3=x1+x2x3.

В настоящее время существенные результаты в решении задач минимизации получены лишь для базиса НЕ, И, ИЛИ, т.к. этот базис наиболее распространен в технике проектирования ЦА. Именно этому базису мы