Законы булевой алгебры
При работе с логическими выражениями часто используют следующие законы.
| Законы коммутативности | А && В = 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.
Задания
- Упростите выражения:
- !X || !(X || Y) || !(Y && !(X && Y));
- !(X || Y || !(X && Y)) && !(Y ||X).
- Заданы логические функции:
F1 = X && Y || X && Z || !Y && Z и F2 = (X && Y || Y && Z || X && !Z) && (X && !Y || !Y && Z).
Упростите эти функции и проверьте, являются ли они тождествено равными между собой, т. е. совпадающими для всех возможных значений переменных X, Y и Z.
