Законы и правила упрощения логических функций

 

Соотношения, законы и правила алгебры логики

 

В алгебре логики имеют место следующие соотношения и действуют следующие законы (слайд 15).

Соотношения

 

Законы отрицания (инверсии)

 

а) отрицание конъюнкции

Отрицание от конъюнкции равно дизъюнкции отрицаний.

 

б) отрицание дизъюнкции

Отрицание от дизъюнкции равно конъюнкции отрицаний.

Переместительный закон

 

Логические функции И и ИЛИ подчиняются переместительному закону:

 

Сочетательный закон

 

Логические функции И и ИЛИ подчиняются сочетательному закону:

 

 

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

 

Непосредственной проверкой можно убедиться, что операции логического сложения и логического умножения подчиняются дистрибутивному (распределительному) закону: одинаковые переменные в конъюнкциях и дизъюнкциях можно выносить за скобку (слайд 16).

а)дистрибутивный закон умножения по отношению к сложению имеет такой же вид, как и для алгебраического сложения и умножения, например:

 

 (распределение конъюнкции по дизъюнкции);

 

б)дистрибутивный закон сложения по отношению к умножению является специфичным для алгебры логики и не имеет аналогов в обычной алгебре:

 

 (распределение дизъюнкции по конъюнкции).

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

Из первой формы дистрибутивного закона вытекают следующие правила (слайд 17):

Правило склеивания для ДНФ

 

а) (для 2 переменных)

 

.

 

б) (для 3 переменных)

 

Это правило позволяет заменить два члена, имеющие общую часть и аргумент с инверсией в одном члене и без инверсии в другом члене, одним общим членом, т.е. произвести склеивание.

 

Правило поглощения для ДНФ

 

а) (для 2 переменных)

 

XVXY = X.

 

б) (для 3 переменных)

 

XVX Λ YVX Λ Y Λ Z = X.

 

Это правило позволяет заменить 2 или больше члена, один из которых входит в другой (конъюнкция) в качестве сомножителя, одним этим членом, т.е. произвести “поглощение” члена конъюнкции общим членом.

Из второй формы дистрибутивного закона вытекает правило свертки (слайд 18).

 

Правило свертки для ДНФ

a)

или

 

b)

 

Это правило позволяет упростить один из членов дизъюнктивной нормальной формы.

Аналогичные формулы существуют для преобразования конъюнктивных нормальных форм (слайд 18).

 

Правило склеивания для КНФ

 

 

Правило поглощения для КНФ

 

 

Правило свертки для КНФ

Пример 5. Пусть логическая функция задана аналитически:

 

 

Требуется упростить функцию (получить ее минимальную форму) (слайды 19-20).

 

· Преобразуем член с инверсией:

 

 

· Раскроем скобки:

 

(конъюнкция )

· Преобразуем член с конъюнкцией:  

 

{ раскрываем скобки } =

 

· Подставляем преобразованные выражения в исходную формулу:  

 

Это нормальная дизъюнктивная форма. Применяя к ней правила склеивания и поглощения, можно ее упростить:

 

· к 1-му и 2-му членам применим правило склеивания:

 

 

· к 3-му и 5-му членам применим правило поглощения:

 

 

Получим:

 

 

Результат не подлежит дальнейшему преобразованию (упрощению). Следовательно, минимальная форма исходной функции: