Дискретная математика

13 1 ) (Л)=А- свойство инволютивности; 2) AuB^BUA\ 3) АпВ—ВпА I ~ законы коммутативности\ 4) AU(BUC)=(AUB)LXJ "1 5) Ап(ВпС)=(АпВ)пС Г ' законы ассоциативности', 6) Ап(ВиС) (AnB)u(Ar)Q "j. _ законы дмстрыбутменостм; 7) Аи(ВпС)=(АиВ)п(АиС) ^ 8) Ап(АиВ)=А 9) Аи(АпВ)=А 10) Аи0=А 11) AuU=U 12) Ап0=0 В) AnU=A • • законы поглощения'. - свойства операций с 0 и с t/: 14) АиВ= А п В - законы де Моргана", 15) АпВ=_А и В 16) А и А= и \ ,1^ л 7 /Of г - Свойства дополнения', 17) An А=0 J 18) AuA-^A ~l . , , ^ законы идемпотентности. 19) АпА=А J J Докажем, например, равенство 1). Пусть хе(А). Имеем, что хе(А) тогда и только тогда, когда х0А. Последнее имеет место тогда и только тогда, когда хеА. Итак, (А )=А. Аналогичным образом можно доказать и остальные соотношения 2) -19). § 3. Разбиение множества. Декартово произведение Семейство подмножеств (В/, В2, ..., S,,}, образует разбиение множества А тогда и только тогда, когда 1 ) Bi^0, l<i<n; 2) BIDBJ = 0 если г^5'; 3) B,uB2U...UB „=A. Пример разбиения приведен на рис. 1.6. Пусть А и В - два множества и положим asA, bsB, сеА, deB. Упорядоченной парой называется объект (а.Ь) такой, что (a,b)-(c,d} тогда и только тогда, когда а=с и b=d. В упорядоченной паре (а,Ь) элемент а считается первым элементом, b - вторым. Рис. 1.6