logo

Algebra množic

Množice pod operacijami unije, presečišča in komplementa izpolnjujejo različne zakone (identitete), ki so navedeni v tabeli 1.

Tabela: Zakon algebre množic

Idempotentni zakoni (a) A ∪ A = A (b) A ∩ A = A
Asociativni zakoni (a) (A ∪ B) ∪ C = A ∪ (B ∪ C) (b) (A ∩ B) ∩ C = A ∩ (B ∩ C)
Komutativni zakoni (a) A ∪ B = B ∪ A (b) A ∩ B = B ∩ A
Distributivni zakoni (a) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) (b) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
De Morganovi zakoni (a) (A ∪B)c=Ac∩ Bc (b) (A ∩ B)c=Ac∪ Bc
Zakoni o identiteti (a) A ∪ ∅ = A
(b) A ∪ U = U
(c) A ∩ U =A
(d) A ∩ ∅ = ∅
Dopolnilni zakoni (a) A ∪ Ac= U
(b) A ∩ Ac= ∅
(c) Uc= ∅
(d) ∅c= U
Involucijski zakon (a) (Ac)c= A

Tabela 1 prikazuje zakon algebre množic.

Primer 1: Dokažite idempotentne zakone:

 (a) A ∪ A = A 

rešitev:

 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 

rešitev:

 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. 

Primer 2: Dokažite asociativne zakone:

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

rešitev:

 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) 

rešitev:

 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. 

Primer3: Dokažite komutativne zakone

 (a) A ∪ B = B ∪ A 

rešitev:

 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 

rešitev:

 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. 

Primer 4: Dokaži distribucijske zakone

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

rešitev:

 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) 

rešitev:

 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 

Primer 5: Dokaži De Morganove zakone

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

rešitev:

 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> 

rešitev:

 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. 

Primer 6: Dokažite zakone identitete.

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

rešitev:

 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; 

rešitev:

 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 

rešitev:

 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 

rešitev:

 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. 

Primer7: Dokažite zakone komplementa

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

rešitev:

 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; 

rešitev:

 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; 

rešitev:

 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 

rešitev:

 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. 

Primer8: Dokažite involucijski zakon

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

rešitev:

 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. 

Dvojnost:

Dualni E∗ od E je enačba, dobljena z zamenjavo vsake pojavitve ∪, ∩, U in ∅ v E z ∩, ∪, ∅ oziroma U. Na primer, dvojnik

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

Kot načelo dualnosti je zapisano, da če je katera koli enačba E identiteta, potem je njena dvojnost E∗ prav tako identiteta.

Načelo razširitve:

V skladu z načelom razširitve sta dve množici A in B enaki, če in samo če imata enake člene. Enake množice označimo z A=B.

 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. 

Kartezični produkt dveh množic:

Kartezični produkt dveh množic P in Q v tem vrstnem redu je množica vseh urejenih parov, katerih prvi člen pripada množici P, drugi člen pa množici Q in je označen s P x Q, tj.

vrsta kopice
 P x Q = {(x, y): x &#x2208; P, y &#x2208; Q}. 

primer: Naj bo P = {a, b, c} in Q = {k, l, m, n}. Določite kartezični produkt P in Q.

rešitev: Kartezični produkt P in Q je

Algebra množic