Практическая информатика

    

Законы булевой алгебры


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

Законы коммутативностиА && В = B && A A || B = B || A
Законы ассоциативностиA && (B && C) = (A && B) && C A || (B|| C) = (A || B) || C
Законы дистрибутивностиA && (B || C) = (A && B) || (A && C) A || (B && C) = (A || B) && (A || C)
Свойства операцийИ, ИЛИ A && T = A; A && F = F A || F = A; A || T = T
Свойства отрицанияA && !A = F; A || !A = T

Закон коммутативности утверждает, что можно переставлять операнды при использовании конъюнкции или дизъюнкции. Это может показаться очевидным, но имеются операторы вроде арифметического минуса, для которых это неверно: A - B отлично от B - A. Закон ассоциативности позволяет расставлять скобки произвольным образом, если в логическом выражении используется лишь одна из связок && и ||. В таких случаях можно вообще обойтись без скобок, так как закон ассоциативности гарантирует получение одного и того же результата независимо от того, как сгруппированы предложения.

Вместе эти пять законов определяют булеву алгебру. Из них можно получить другие полезные законы, например, такие:

Дополнение!( !A) = A
ИдемпотентностьA && A = A; A || A = A
ПоглощениеA && (A || B) = A

Приведем очень поучительное доказательство закона поглощения (попробуйте найти его сами прежде, чем ознакомиться с решением).

A && (A || B) =
{ свойство операции ИЛИ }
(A || F) && (A || B) =
{ дистрибутивность }
A || (F && B) =
{ коммутативность }
A || (B && F) =
{ свойство операции И }
A || F =
{ свойство операции ИЛИ }
A

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

Задания

  1. Упростите выражения:
    • !X || !(X || Y) || !(Y && !(X && Y));
    • !(X || Y || !(X && Y)) && !(Y ||X).
  2. Заданы логические функции:

    F1 = X && Y || X && Z || !Y && Z и F2 = (X && Y || Y && Z || X && !Z) && (X && !Y || !Y && Z).

    Упростите эти функции и проверьте, являются ли они тождествено равными между собой, т. е. совпадающими для всех возможных значений переменных X, Y и Z.



Содержание раздела