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

1) В алгебре логики имеют место следующие соотношения:

2) В алгебре логики имеют место следующие законы:

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

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

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

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

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

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

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

           («И»)

   («ИЛИ»)

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

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

            («И»)

   («ИЛИ»)

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

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

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

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

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

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

Доказательство:

Согласно основным соотношениям алгебры логики выражение в скобках

 равно1.

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

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

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

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

Доказательство:

,

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

Доказательство:

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

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

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

Доказательство:

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

Доказательство:

.

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

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

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

Доказательство:

Из второй формы дистрибутивного закона имеем:

или

Доказательство:

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

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

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

Доказательство:

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

Доказательство:

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

Доказательство:

Рассмотрим следующий пример:

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

F(A, B, C, D) =

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

Доказательство:

 =

2) Раскрываем скобки:

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

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

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

F(A, B, C, D) =

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

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

2) к 3-ему и 5-му членам применим формулу поглощения:

Получим: F(A, B, C, D) =

Результат: