logo

Àlgebra de conjunts

Els conjunts sota les operacions d'unió, intersecció i complement compleixen diverses lleis (identitats) que s'enumeren a la taula 1.

Taula: Llei de l'àlgebra dels conjunts

Lleis idempotents (a) A ∪ A = A (b) A ∩ A = A
Lleis associatives (a) (A ∪ B) ∪ C = A ∪ (B ∪ C) (b) (A ∩ B) ∩ C = A ∩ (B ∩ C)
Lleis commutatives (a) A ∪ B = B ∪ A (b) A ∩ B = B ∩ A
Lleis distributives (a) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) (b) A ∩ (B ∪ C) =(A ∩ B) ∪ (A ∩ C)
Les lleis de De Morgan (a) (A ∪B)c=Ac∩ Bc (b) (A ∩B)c=Ac∪ Bc
Lleis d'identitat (a) A ∪ ∅ = A
(b) A ∪ U = U
(c) A ∩ U =A
(d) A ∩ ∅ = ∅
Lleis complementàries (a) A ∪ Ac= U
(b) A ∩ Ac= ∅
(c) Uc= ∅
(d) ∅c= U
Llei d'involució (a) (Ac)c= A

La taula 1 mostra la llei de l'àlgebra dels conjunts.

Exemple 1: Demostrar lleis idempotents:

 (a) A ∪ A = A 

Solució:

 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 

Solució:

 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. 

Exemple 2: Demostrar lleis associatives:

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

Solució:

 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) 

Solució:

 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. 

Exemple 3: Demostrar lleis commutatives

 (a) A ∪ B = B ∪ A 

Solució:

 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 

Solució:

 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. 

Exemple 4: Demostrar lleis distributives

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

Solució:

 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) 

Solució:

 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 

Exemple 5: Demostrar les lleis de De Morgan

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

Solució:

 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> 

Solució:

 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. 

Exemple 6: Demostrar lleis d'identitat.

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

Solució:

 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; 

Solució:

 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 

Solució:

 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 

Solució:

 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. 

Exemple 7: Demostrar lleis complementàries

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

Solució:

 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; 

Solució:

 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; 

Solució:

 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 

Solució:

 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. 

Exemple8: Demostrar la llei d'involució

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

Solució:

 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. 

Dualitat:

L'E∗ dual d'E és l'equació que s'obté substituint cada aparició de ∪, ∩, U i ∅ a E per ∩, ∪, ∅ i U, respectivament. Per exemple, el dual de

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

S'observa com a principi de dualitat, que si qualsevol equació E és una identitat, aleshores el seu dual E∗ també és una identitat.

Principi d'extensió:

Segons el principi d'extensió, dos conjunts, A i B són iguals si i només si tenen els mateixos membres. Denotem conjunts iguals per 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. 

Producte cartesià de dos conjunts:

El producte cartesià de dos conjunts P i Q en aquest ordre és el conjunt de tots els parells ordenats el primer membre dels quals pertany al conjunt P i el segon membre pertany al conjunt Q i es denota amb P x Q, és a dir,

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

Exemple: Sigui P = {a, b, c} i Q = {k, l, m, n}. Determineu el producte cartesià de P i Q.

Solució: El producte cartesià de P i Q és

Àlgebra de conjunts