Дискретная математика:
логика, группы, графы, фракталыАкимов О.Е.
1.1. Операции логики Буля
Симметрическая разность и эквивалентность
Остается привести еще две взаимно дополняющих операции — симметрическую разность и эквивалентность. Симметрическая разность двух множеств A и B есть объединение двух разностей:
A + B = (A – B) ∪ (B – A) = C1 ∪ C2 = {1, 3, 6, 8, 9}.
Эквивалентность определяется теми элементами множеств A и B, которые для них являются общими. Однако элементы, не входящие ни в A, ни в B, также считаются эквивалентными:
A ~ B = (A ∩ B) ∪ (A ∩ B) = C0 ∪ C3 = {2, 4, 5, 7, 10, 11}.
На рис. 1.11 и 1.12 показана штриховка диаграмм Эйлера — Венна, а табл. 1.7 и 1.8 представляют таблицы истинности соответствующих операций.
Рис. 1.11
Рис. 1.12
Таблица 1.7
x1 x2 y = x1 + x2 0 0 0 1 0 1 0 1 1 1 1 0 Таблица 1.8
x1 x2 y = x1 ~ x2 0 0 1 1 0 0 0 1 0 1 1 1 Из условия дополнительности операций вытекают следующие соотношения:
y = x1 ~ x2 = (x1 ∧ x2) ∨ (x1 ∧ x2) =
= (x1 ∨ x2) ∧ (x1 ∨ x2) ∧ (x1 ∨ x2);
(x1 + x2) ∨ (x1 ~ x2) = 1,
(x1 + x2) ∧ (x1 ~ x2) = 0.
В заключение отметим, что симметрическая разность имеет несколько названий: строгая дизъюнкция, исключающая альтернатива, сумма по модулю два. Эту операцию можно передать словами — «либо А, либо В», т.е. это логическая связка «или», но без включенной в нее связки «и».
|
|
