Теория графов и комбинаторика

1 Б и raaiyx А , воли Уй, (CL^k^de &) . Шожеотвв Л и Ь называютоя равными, если казхдое из них оодержйтоя в другом: В ^ В Д . Пустым называется множество ^ , не содержащее ня одного элемента. Считается, что Ч А С 0 А ) . Ойычно вое рассматриваемые множества считаитоя подмножвотва- ш некоторого множестваQ , называемого унивароальннм множеотвом. Совокупнсть поданожеотв^З обозначается 2. • Таким образом, МАЛ<= . Операции объединения С , пересечения П и разнооти \ MKL^eoTB определяются так: AU f c V 0 C 6 & I , Л П Б = { э : ё Й : а : 6 / 4 ^ а : б Е . } , А \ Ь =1 { л с еД ?г . Здесь V , ^ - символы логических операций Ka3t. »HKnt"4 и конъюнк-, ции. Из приведенных определений следуют ооотношвния:;^ Ofi) Д , Д П Ь с б , б с А О Ь , AObcAVb.AOA-A.AOA^A. Ps3HooTb/4N6 называется дополнением множества В в множест­ ве Л - Дополнений Л b G c Q n A ^ наэы1.1втся дополнением А и обоэначаетоя f\ . Операции f , Г) Л удовлетворяют основным законам влгобрн логики, т . е . обладают овойотэами логических операций дизъюнкции V , конъюнкции ^ и отрицания 1 . Множество 2^ о операциями U , (] ,S образует булеву а.'-'еб- ру, называемую алгеброй множеств. Операции U , П , Ч называютоя внутоенними, так каг из подмножеств £ 2 поучаются по;.множества !й . Рассмотрим одну из внешних операций, называемую декартовым произведением множеств. Двкар'говы?л или лрямам про..зведанием множеств А и В нарчвает- оя множеотво (? •= Д х ft , состоящее из всех упорядоченных пар С- (a.,i ) , где Ь: & , Элементы О. я S нааываотся ос- отввтотввяно пешой и второй проекциями пары С и обозначаются; й'Яр^С ; 6 s Йр^С , Две упорядоченные najsi С v. d ав^ нн, eQmillf>,0=np,d)^(npj;mflf^c() . Тахим образом, ¥ • f А**й ^ 6 * Д . Понятие декартова произведения может быть распроотранено на большее число мномтелей оледающим o6pa_jMt A|'<A*,'<"* '=• xAj)x"'))fAM* 2лемвнтамй произведеки;' 4