МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ АЛГЕБРЫ ЛОГИКИ
Аналитический метод минимизации ФЛ
Определение. Минимальная форма (МКФ и МДФ) представления ФЛ это форма, которая содержит минимальное количество термов и переменных в термах, и не должна допускать последующих упрощений.
Например, функция 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.
В настоящее время существенные результаты в решении задач минимизации получены лишь для базиса НЕ, И, ИЛИ, т.к. этот базис наиболее распространен в технике проектирования ЦА. Именно этому базису мы