logo

Алгебра скупова

Скупови под операцијама уније, пресека и комплемента задовољавају различите законе (идентитете) који су наведени у табели 1.

Табела: Закон алгебре скупова

Идемпотентни закони (а) А ∪ А = А (б) А ∩ А = А
Асоцијативни закони (а) (А ∪ Б) ∪ Ц = А ∪ (Б ∪ Ц) (б) (А ∩ Б) ∩ Ц = А ∩ (Б ∩ Ц)
Цоммутативе Лавс (а) А ∪ Б = Б ∪ А (б) А ∩ Б = Б ∩ А
Дистрибутивни закони (а) А ∪ (Б ∩ Ц) = (А ∪ Б) ∩ (А ∪ Ц) (б) А ∩ (Б ∪ Ц) =(А ∩ Б) ∪ (А ∩ Ц)
Де Морганови закони (а) (А ∪Б)цц∩ Бц (б) (А ∩Б)цц∪ Бц
Закони о идентитету (а) А ∪ ∅ = А
(б) А ∪ У = У
(ц) А ∩ У =А
(д) А ∩ ∅ = ∅
Комплементарни закони (а) А ∪ Ац= У
(б) А ∩ Ац= ∅
(ц) Уц= ∅
(д) ∅ц= У
Закон о инволуцији (а) (Ац)ц= А

У табели 1 приказан је закон алгебре скупова.

Пример 1: Докажите идемпотентне законе:

 (a) A ∪ A = A 

Решење:

 Since, B ⊂ A ∪ B, therefore A ⊂ A ∪ A Let x ∈ A ∪ A ⇒ x ∈ A or x ∈ A ⇒ x ∈ A ∴ A ∪ A ⊂ A As A ∪ A ⊂ A and A ⊂ A ∪ A ⇒ A =A ∪ A. Hence Proved. 

 (b) A ∩ A = A 

Решење:

 Since, A ∩ B ⊂ B, therefore A ∩ A ⊂ A Let x ∈ A ⇒ x ∈ A and x ∈ A ⇒ x ∈ A ∩ A ∴ A ⊂ A ∩ A As A ∩ A ⊂ A and A ⊂ A ∩ A ⇒ A = A ∩ A. Hence Proved. 

Пример 2: Доказати асоцијативне законе:

 (a) (A ∪ B) ∪ C = A ∪ (B ∪ C) 

Решење:

 Let some x ∈ (A'∪ B) ∪ C ⇒ (x ∈ A or x ∈ B) or x ∈ C ⇒ x ∈ A or x ∈ B or x ∈ C ⇒ x ∈ A or (x ∈ B or x ∈ C) ⇒ x ∈ A or x ∈ B ∪ C ⇒ x ∈ A ∪ (B ∪ C). Similarly, if some x ∈ A ∪ (B ∪ C), then x ∈ (A ∪ B) ∪ C. Thus, any x ∈ A ∪ (B ∪ C) ⇔ x ∈ (A ∪ B) ∪ C. Hence Proved. 

 (b) (A ∩ B) ∩ C = A ∩ (B ∩ C) 

Решење:

 Let some x ∈ A ∩ (B ∩ C) ⇒ x ∈ A and x ∈ B ∩ C ⇒ x ∈ A and (x ∈ B and x ∈ C) ⇒ x ∈ A and x ∈ B and x ∈ C ⇒ (x ∈ A and x ∈ B) and x ∈ C) ⇒ x ∈ A ∩ B and x ∈ C ⇒ x ∈ (A ∩ B) ∩ C. Similarly, if some x ∈ A ∩ (B ∩ C), then x ∈ (A ∩ B) ∩ C Thus, any x ∈ (A ∩ B) ∩ C ⇔ x ∈ A ∩ (B ∩ C). Hence Proved. 

Пример 3: Доказати комутативне законе

 (a) A ∪ B = B ∪ A 

Решење:

 To Prove A ∪ B = B ∪ A A ∪ B = {x: x ∈ A or x ∈ B} = {x: x ∈ B or x ∈ A} (∵ Order is not preserved in case of sets) A ∪ B = B ∪ A. Hence Proved. 

 (b) A ∩ B = B ∩ A 

Решење:

 To Prove A ∩ B = B ∩ A A ∩ B = {x: x ∈ A and x ∈ B} = {x: x ∈ B and x ∈ A} (∵ Order is not preserved in case of sets) A ∩ B = B ∩ A. Hence Proved. 

Пример 4: Доказати дистрибутивне законе

 (a) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) 

Решење:

 To Prove Let x ∈ A ∪ (B ∩ C) ⇒ x ∈ A or x ∈ B ∩ C ⇒ (x ∈ A or x ∈ A) or (x ∈ B and x ∈ C) ⇒ (x ∈ A or x ∈ B) and (x ∈ A or x ∈ C) ⇒ x ∈ A ∪ B and x ∈ A ∪ C ⇒ x ∈ (A ∪ B) ∩ (A ∪ C) Therefore, A ∪ (B ∩ C) ⊂ (A ∪ B) ∩ (A ∪ C)............(i) Again, Let y ∈ (A ∪ B) ∩ (A ∪ C) ⇒ y ∈ A ∪ B and y ∈ A ∪ C ⇒ (y ∈ A or y ∈ B) and (y ∈ A or y ∈ C) ⇒ (y ∈ A and y ∈ A) or (y ∈ B and y ∈ C) ⇒ y ∈ A or y ∈ B ∩ C ⇒ y ∈ A ∪ (B ∩ C) Therefore, (A ∪ B) ∩ (A ∪ C) ⊂ A ∪ (B ∩ C)............(ii) Combining (i) and (ii), we get A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C). Hence Proved 

 (b) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) 

Решење:

 To Prove Let x ∈ A ∩ (B ∪ C) ⇒ x ∈ A and x ∈ B ∪ C ⇒ (x ∈ A and x ∈ A) and (x ∈ B or x ∈ C) ⇒ (x ∈ A and x ∈ B) or (x ∈ A and x ∈ C) ⇒ x ∈ A ∩ B or x ∈ A ∩ C ⇒ x ∈ (A ∩ B) ∪ (A ∪ C) Therefore, A ∩ (B ∪ C) ⊂ (A ∩ B) ∪ (A ∪ C)............ (i) Again, Let y ∈ (A ∩ B) ∪ (A ∪ C) ⇒ y ∈ A ∩ B or y ∈ A ∩ C ⇒ (y ∈ A and y ∈ B) or (y ∈ A and y ∈ C) ⇒ (y ∈ A or y ∈ A) and (y ∈ B or y ∈ C) ⇒ y ∈ A and y ∈ B ∪ C ⇒ y ∈ A ∩ (B ∪ C) Therefore, (A ∩ B) ∪ (A ∪ C) ⊂ A ∩ (B ∪ C)............ (ii) Combining (i) and (ii), we get A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∪ C). Hence Proved 

Пример 5: Доказати Де Морганове законе

 (a) (A &#x222A;B)<sup>c</sup>=A<sup>c</sup>&#x2229; B<sup>c</sup> 

Решење:

 To Prove (A &#x222A;B)<sup>c</sup>=A<sup>c</sup>&#x2229; B<sup>c</sup> Let x &#x2208; (A &#x222A;B)<sup>c</sup> &#x21D2; x &#x2209; A &#x222A; B (&#x2235; a &#x2208; A &#x21D4; a &#x2209; A<sup>c</sup>) &#x21D2; x &#x2209; A and x &#x2209; B &#x21D2; x &#x2209; A<sup>c</sup> and x &#x2209; B<sup>c</sup> &#x21D2; x &#x2209; A<sup>c</sup>&#x2229; B<sup>c</sup> Therefore, (A &#x222A;B)<sup>c</sup> &#x2282; A<sup>c</sup>&#x2229; B<sup>c</sup>............. (i) Again, let x &#x2208; A<sup>c</sup>&#x2229; B<sup>c</sup> &#x21D2; x &#x2208; A<sup>c</sup> and x &#x2208; B<sup>c</sup> &#x21D2; x &#x2209; A and x &#x2209; B &#x21D2; x &#x2209; A &#x222A; B &#x21D2; x &#x2208; (A &#x222A;B)<sup>c</sup> Therefore, A<sup>c</sup>&#x2229; B<sup>c</sup> &#x2282; (A &#x222A;B)<sup>c</sup>............. (ii) Combining (i) and (ii), we get A<sup>c</sup>&#x2229; B<sup>c</sup> =(A &#x222A;B)<sup>c</sup>. Hence Proved. 

 (b) (A &#x2229;B)<sup>c</sup> = A<sup>c</sup>&#x222A; B<sup>c</sup> 

Решење:

 Let x &#x2208; (A &#x2229;B)<sup>c</sup> &#x21D2; x &#x2209; A &#x2229; B (&#x2235; a &#x2208; A &#x21D4; a &#x2209; A<sup>c</sup>) &#x21D2; x &#x2209; A or x &#x2209; B &#x21D2; x &#x2208; A<sup>c</sup> and x &#x2208; B<sup>c</sup> &#x21D2; x &#x2208; A<sup>c</sup>&#x222A; B<sup>c</sup> &#x2234; (A &#x2229;B)<sup>c</sup>&#x2282; (A &#x222A;B)<sup>c</sup>.................. (i) Again, Let x &#x2208; A<sup>c</sup>&#x222A; B<sup>c</sup> &#x21D2; x &#x2208; A<sup>c</sup> or x &#x2208; B<sup>c</sup> &#x21D2; x &#x2209; A or x &#x2209; B &#x21D2; x &#x2209; A &#x2229; B &#x21D2; x &#x2208; (A &#x2229;B)<sup>c</sup> &#x2234; A<sup>c</sup>&#x222A; B<sup>c</sup>&#x2282; (A &#x2229;B)<sup>c</sup>.................... (ii) Combining (i) and (ii), we get(A &#x2229;B)<sup>c</sup>=A<sup>c</sup>&#x222A; B<sup>c</sup>. Hence Proved. 

Пример 6: Закони о доказивању идентитета.

 (a) A &#x222A; &#x2205; = A 

Решење:

 To Prove A &#x222A; &#x2205; = A Let x &#x2208; A &#x222A; &#x2205; &#x21D2; x &#x2208; A or x &#x2208; &#x2205; &#x21D2; x &#x2208; A (&#x2235;x &#x2208; &#x2205;, as &#x2205; is the null set ) Therefore, x &#x2208; A &#x222A; &#x2205; &#x21D2; x &#x2208; A Hence, A &#x222A; &#x2205; &#x2282; A. We know that A &#x2282; A &#x222A; B for any set B. But for B = &#x2205;, we have A &#x2282; A &#x222A; &#x2205; From above, A &#x2282; A &#x222A; &#x2205; , A &#x222A; &#x2205; &#x2282; A &#x21D2; A = A &#x222A; &#x2205;. Hence Proved. 

 (b) A &#x2229; &#x2205; = &#x2205; 

Решење:

 To Prove A &#x2229; &#x2205; = &#x2205; If x &#x2208; A, then x &#x2209; &#x2205; (&#x2235;&#x2205; is a null set) Therefore, x &#x2208; A, x &#x2209; &#x2205; &#x21D2; A &#x2229; &#x2205; = &#x2205;. Hence Proved. 

 (c) A &#x222A; U = U 

Решење:

 To Prove A &#x222A; U = U Every set is a subset of a universal set. &#x2234; A &#x222A; U &#x2286; U Also, U &#x2286; A &#x222A; U Therefore, A &#x222A; U = U. Hence Proved. 

 (d) A &#x2229; U = A 

Решење:

 To Prove A &#x2229; U = A We know A &#x2229; U &#x2282; A................. (i) So we have to show that A &#x2282; A &#x2229; U Let x &#x2208; A &#x21D2; x &#x2208; A and x &#x2208; U (&#x2235; A &#x2282; U so x &#x2208; A &#x21D2; x &#x2208; U ) &#x2234; x &#x2208; A &#x21D2; x &#x2208; A &#x2229; U &#x2234; A &#x2282; A &#x2229; U................. (ii) From (i) and (ii), we get A &#x2229; U = A. Hence Proved. 

Пример 7: Доказати законе комплемента

 (a) A &#x222A; A<sup>c</sup>= U 

Решење:

 To Prove A &#x222A; A<sup>c</sup>= U Every set is a subset of U &#x2234; A &#x222A; A<sup>c</sup> &#x2282; U.................. (i) We have to show that U &#x2286; A &#x222A; A<sup>c</sup> Let x &#x2208; U &#x21D2; x &#x2208; A or x &#x2209; A &#x21D2; x &#x2208; A or x &#x2208; A<sup>c</sup> &#x21D2; x &#x2208; A &#x222A; A<sup>c</sup> &#x2234; U &#x2286; A &#x222A; A<sup>c</sup>................... (ii) From (i) and (ii), we get A &#x222A; A<sup>c</sup>= U. Hence Proved. 

 (b) A &#x2229; A<sup>c</sup>=&#x2205; 

Решење:

 As &#x2205; is the subset of every set &#x2234; &#x2205; &#x2286; A &#x2229; A<sup>c</sup>..................... (i) We have to show that A &#x2229; A<sup>c</sup> &#x2286; &#x2205; Let x &#x2208; A &#x2229; A<sup>c</sup> &#x21D2; x &#x2208; A and x &#x2208; A<sup>c</sup> &#x21D2; x &#x2208; A and x &#x2209; A &#x21D2; x &#x2208; &#x2205; &#x2234; A &#x2229; A<sup>c</sup> &#x2282;&#x2205;..................... (ii) From (i) and (ii), we get A&#x2229; A<sup>c</sup>=&#x2205;. Hence Proved. 

 (c) U<sup>c</sup>= &#x2205; 

Решење:

 Let x &#x2208; U<sup>c</sup> &#x21D4; x &#x2209; U &#x21D4; x &#x2208; &#x2205; &#x2234; U<sup>c</sup>= &#x2205;. Hence Proved. (As U is the Universal Set). 

 (d) &#x2205;<sup>c</sup> = U 

Решење:

 Let x &#x2208; &#x2205;<sup>c</sup> &#x21D4; x &#x2209; &#x2205; &#x21D4; x &#x2208; U (As &#x2205; is an empty set) &#x2234; &#x2205;<sup>c</sup> = U. Hence Proved. 

Пример 8: Доказати закон инволуције

 (a) (A<sup>c</sup> )<sup>c</sup> A. 

Решење:

 Let x &#x2208; (A<sup>c</sup> )<sup>c</sup> &#x21D4; x &#x2209; A<sup>c</sup>&#x21D4; x &#x2208; a &#x2234; (A<sup>c</sup> )<sup>c</sup> =A. Hence Proved. 

дуалност:

Дуално Е∗ од Е је једначина добијена заменом сваког појављивања ∪, ∩, У и ∅ у Е са ∩, ∪, ∅ и У, респективно. На пример, дуал оф

 (U &#x2229; A) &#x222A; (B &#x2229; A) = A is (&#x2205; &#x222A; A) &#x2229; (B &#x222A; A) = A 

Као принцип дуалности примећује се да ако је било која једначина Е идентитет, онда је њен дуални Е∗ такође идентитет.

Принцип проширења:

Према принципу проширења два скупа, А и Б су исти ако и само ако имају исте чланове. Једнаке скупове означавамо са А=Б.

 If A= {1, 3, 5} and B= {3, 1, 5}, then A=B i.e., A and B are equal sets. If A= {1, 4, 7} and B= {5, 4, 8}, then A&#x2260; B i.e.., A and B are unequal sets. 

Декартов производ два скупа:

Декартов производ два скупа П и К тим редоследом је скуп свих уређених парова чији први члан припада скупу П, а други члан скупу К и означен је са П к К, тј.

мап Јава итератор
 P x Q = {(x, y): x &#x2208; P, y &#x2208; Q}. 

Пример: Нека је П = {а, б, ц} и К = {к, л, м, н}. Одредити Декартов производ П и К.

Решење: Декартов производ П и К је

Алгебра скупова