йНМЯОЕЙР ОН МЮВЕПРЮРЕКЭМНИ ЦЕНЛЕРПХХ хМФЕМЕПМЮЪ ЦПЮТХЙЮ юПУХРЕЙРСПЮ щбл хМТНПЛЮРХЙЮ Х ХМТНПЛЮЖХНММШЕ РЕУМНКНЦХХ

Предыдущий разделУровень вышеСледующий раздел

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

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

Законы
коммутативности
А && В = 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. Упростите выражения:
    1) !X || !(X || Y) || !(Y && !(X && Y));
    2) !(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.

Предыдущий разделУровень вышеСледующий раздел

мЮВЕПРЮРЕКЭМЮЪ ЦЕНЛЕРПХЪ Х ХМФЕМЕПМЮЪ ЦПЮТХЙЮ, ОЕПЯОЕЙРХБЮ