Matematika 1 - Gyakorló feladatok


Halmazok, halmazműveletek. Matematikai és nem matematikai tartalmú halmazba rendezések.

Gyakorló feladatok (vö. Kiss 1996: 19-25; Monostory 2006: 7-10; Lavrov-Maximova 1987: 11-14):

Írjuk fel az A={a,b,c} halmaz összes részhalmazát! Számoljuk össze, hogy hány ilyen részhalmaz van?

Legyen az alaphalmaz I = {n∈ℕ | n≤15}, továbbá
A = {n∈I | 2|n},
B = {n∈I | 3|n},
C = {n∈I | 4|n},
D = {n∈I | 6|n}.
Adja meg az A, B, C és D halmazokat úgy, hogy felsorolja az elemeiket!
Készítsen Venn-diagramot, és töltse ki az A, B, C és D halmazok elemeivel a megfelelő részhalmazokat jelölő alakzatokat!
Az A, B, C és D halmazok ismeretében sorolja fel az alábbi halmazok elemeit, és adja meg a halmazokat formálisan is!

(a1) A∩B
(a2) A∩C (Hasonlítsa össze az A és C halmazokkal!)
(a3) A∩D (Hasonlítsa össze az A és D halmazokkal!)

(b1) B∩C
(b2) B∩D (Hasonlítsa össze a B és D halmazokkal!)

(c1) A∪B
(c2) A∪C (Hasonlítsa össze az A és C halmazokkal!)
(c3) A∪D (Hasonlítsa össze az A és D halmazokkal!)

(d1) B∪C
(d2) B∪D (Hasonlítsa össze a B és D halmazokkal!)

(e1) A∖C
(e2) C∖A

(f1) D∖B
(f1) B∖D

Tippek a Venn-diagram elkészítéséhez:
(1) körökkel (14 különböző terület a számok elhelyezésére; de egyrészt a piros és zöld köröknek nincs olyan közös részük, amely ne tartozna vagy a sárga, vagy a kék körhöz, ill. mindkettőhöz; másrészt a kék és sárga köröknek nincs olyan közös részük, amely ne tartozna vagy a piros, vagy a zöld körhöz, ill. mindkettőhöz)

négy halmaz ábrázolása Venn-diagramon

(2) ellipszisekkel

négy halmaz ábrázolása Venn-diagramon

(3) aszimmetrikus alakzatokkal

négy halmaz ábrázolása Venn-diagramon

Legyen az alaphalmaz I = {n∈ℕ | n≤15}, továbbá
A = {"6 pozitív osztói"},
B = {"10 pozitív osztói"},
C = {"15 pozitív osztói"}.
Adja meg az A, B és C halmazokat formálisan is, továbbá adja meg a halmazokat úgy is, hogy felsorolja az elemeiket!

Például az A⊆I halmaz esetén:
A = {x∈I | x|6} vagy A = {x∈I | ∃q (q*x=6)}
A = {1,2,3,6}

Az A, B és C halmazok ismeretében sorolja fel az alábbi halmazok elemeit, és adja meg a halmazokat formálisan is!

(a) A∩B

(b1) A∪B
(b2) A∪C
(b3) B∪C

(c) (A∩B)∪C

(d) (A∪C)∩(B∪C)

(e1) A
(e2) B
(e3) C

(f) ABC

(g1) A∩B (Hasonlítsa össze az AB halmazzal!)
(g2) AB

(h1) A∖B (Hasonlítsa össze az A∩B halmazzal!)
(h2) B∖A

(i) (A∖B)∩(B∖A)

(j) (A∖B)∪(B∖A) (szimmetrikus differencia)

(k) (A∪B)∖(A∩B) (szimmetrikus differencia)

Bizonyítsa be a halmazműveletek definíciója alapján, hogy tetszőleges A, B, C, D halmazokra teljesülnek az alábbi összefüggések, ill. azonosságok: (tipp: használja fel a részhalmaz reláció antiszimmetriáját az azonosságok bal- és jobboldalán szereplő kifejezések egyenlőségének bizonyításához!)

Emlékeztető: ⇋ "és", ⇋ "vagy", ⇋ "nem"; ⇋ "...ból következik, hogy..." (logikai kifejezésekben); x ⇋ "bármely / minden x-re teljesül, hogy ...", x ⇋ "létezik / van olyan x, amelyre teljesül, hogy ..."; ⇋ "...ból következik, hogy..." (levezetésekben); ⇋ "... pontosan akkor, ha ..." vagy "... akkor és csak akkor, ha ..."

Halmazelméleti szimbólumok:

A⊆B minden x∈I-re x∈A ⇒ x∈B
A∪B A∪B = {x∈I | x∈A ∨ x∈B}
minden x∈I-re x∈(A∪B) ⇔ x∈A ∨ x∈B
A∩B A∩B = {x∈I | x∈A ∧ x∈B}
minden x∈I-re x∈(A∩B) ⇔ x∈A ∧ x∈B
A A = {x∈I | x∉A}
x∉A ⇋ ⌝(x∈A)
minden x∈I-re x∈A ⇔ x∉A
AB AB = A∩B = {x∈I | x∈A ∧ x∉B}
minden x∈I-re x∈AB ⇔ x∈A ∧ x∉B

Fontosabb következtetési szabályok:

Legyenek A, B⊆I tetszőleges halmazok, a∈I tetszőleges halmazelem (∀a∈I (...)).
– részhalmaz reláció felbontása: a∈A, A⊆B ⇒ a∈B
– részhalmaz reláció bizonyítása: (a∈A ⇒ ... ⇒ a∈B) ⇒ A⊆B
– halmazok egyenlőségének bizonyítása: A⊆B ∧ B⊆A ⇒ A=B
– metszet felbontása: a∈(A∩B) ⇒ a∈A ∧ a∈B
– metszet visszaírása: (a∈A ∧ a∈B) ⇒ a∈A∩B
– unió felbontása: a∈(A∪B) ⇒ a∈A ∨ a∈B
– unió visszaírása: (a∈A ∨ a∈B) ⇒ a∈A∪B

Legyenek A, B, C tetszőleges állítások.
– a szűkítés szabálya: A ∧ B ⇒ A
   (pl. ha "kiváló" ⇋ "szorgalmas és okos", akkor "Janka kiváló" ⇒ "Janka szorgalmas")
– a bővítés szabálya: A ⇒ A ∨ B
   (pl. ha "tehetséges" ⇋ "szorgalmas vagy okos", akkor "Janka szorgalmas" ⇒ "Janka tehetséges")
– esetegyesítés: (A ⇒ B) és (A ⇒ C) teljesüléséből (A ⇒ B ∧ C) következik
– esetszétválasztás, esetelemzés: (A ⇒ C) és (B ⇒ C) teljesüléséből (A ∨ B ⇒ C) következik
   (pl. ha "tehetséges" ⇋ "szorgalmas vagy okos", és bizonyítjuk, hogy
   –– "aki szorgalmas, az bekerül az egyetemre" és
   –– "aki okos, az bekerül az egyetemre" akkor ezekből az állításokból
   –– "aki tehetséges, az bekerül az egyetemre" következik)

– logikai ekvivalencia bizonyítása: (A ⇒ B) és (B ⇒ A) teljesüléséből (A ⇔ B) következik

Példa: az A⊆B ⇔ A=A∩B összefüggés bizonyítása az előadás anyagában megtalálható

(a) A⊆A (a részhalmaz reláció reflexivitása); A⊆A∪B (tetszőleges B⊆I halmazra)

Legyen x∈A tetszőleges elem, ahol 'A' a reláció bal oldalán szereplő halmaz. Ez nyilvánvalóan eleme a reláció jobb oldalán szereplő A-nak is, tehát a részhalmaz reláció definíciója alapján A⊆A teljesül. A bizonyításból látszik, hogy ha a jobb oldalon szereplő 'A' halmazhoz tetszőleges elemeket hozzáadunk, a reláció ugyanúgy fennáll, azaz A⊆A∪B is teljesül tetszőleges 'B' halmazra (vö. a (c2) feladattal).

A bizonyítás lépései formálisan leírva (b.o. = "bal oldal"; j.o. = "jobb oldal"):
  • x∈A [b.o.] ⇒
    • x∈A [j.o.] ⇒
    • A⊆A

A probléma egy konkrét feladatba ágyazása a következő:
Egy osztályban Petike kölcsönadja a kedvenc ceruzáját (c) Julcsinak. Julcsi beteszi a tolltartójába, a "tollai halmazába" (A; és innentől c∈A teljesül). Az óra végén Julcsi azt mondja, hogy nincs nála a ceruza. Petike szól a tanítónéninek. Hol fogja a tanító néni keresni a ceruzát? Megoldás: Julcsi tolltartójában (mert tudja, hogy minden 'x' ceruzára, tollra stb., amely Julcsinál van, x∈A teljesül).
A tanító néni tehát jól tudja, hogy minden olyan 'x' ceruzát, amelyet Julcsi beletett a tolltartóba (x∈A), a tolltartóban fogunk megtalálni (x∈A). Ezt formálisan úgy tudjuk kifejezni, hogy A⊆A teljesül.

(b) ha A⊆B és B⊆C teljesül, akkor A⊆C is teljesül (a részhalmaz reláció tranzitivitása)

Julcsinak nagyon tetszett a ceruza, ezért betette a tolltartót (A) a táskájába (B), azt pedig szünetben az osztályban levő szekrénybe (C). Vajon így megtalálja-e a ceruzát a tanító néni?

(c) A∩B⊆A (→c1), A⊆A∪B (→c2) és A∩B⊆A∪B (→c3)

(c1) A∩B⊆A (és nyilvánvalóan A∩B⊆B) (tipp: használja fel a minden x∈I elem esetén teljesülő x∈A ∧ x∈B ⇒ x∈A (ill. x∈A ∧ x∈B ⇒ x∈B) logikai törvényeket a bizonyításhoz!)

Legyen x∈I tetszőleges halmazelem, amely eleme az A és B halmazok metszetének (x∈A∩B). Erre teljesül, hogy 'x' eleme az 'A' halmaznak (x∈A), valamint a 'B' halmaznak is (x∈B).
Ha pedig a C=A∩B halmaz minden 'x' elemére teljesül, hogy eleme az 'A' halmaznak, akkor a C halmaz része az A halmaznak, vagyis C⊆A teljesül (és hasonlóan teljesül C⊆B is).
Tehát az A és B halmazok metszete része az A halmaznak (A∩B⊆A).


A∩B⊆A esetén a bizonyítás lépései formálisan leírva:
x∈A∩B ⇒ x∈A ∧ x∈B ⇒ x∈A
tehát A∩B⊆A teljesül (q.e.d.)

(c2) A⊆A∪B (és nyilvánvalóan B⊆A∪B) (tipp: használja fel a minden x∈I elem esetén teljesülő x∈A ⇒ x∈A ∨ x∈B (ill. x∈B ⇒ x∈A ∨ x∈B) logikai törvényeket a bizonyításhoz!)

A⊆A∪B esetén a bizonyítás lépései formálisan leírva:
x∈A ⇒ x∈A ∨ x∈B ⇒ x∈A∪B
tehát A⊆A∪B teljesül (q.e.d.)

(c3) A∩B⊆A∪B

(d) ha A⊆B, akkor A⊆A∩B (→d1) és A∪B⊆B (→d2) teljesül; ha A⊆A∩B akkor A⊆B (→d3) teljesül

(d1) ha A⊆B, akkor A⊆A∩B

(d2) ha A⊆B, akkor A∪B⊆B

A bizonyítás lépései formálisan leírva:
x∈A∪Bx∈A ∨ x∈B
     x∈A ∧ A⊆B ⇒ x∈B
     x∈Bx∈B
x∈A ∨ x∈B ⇒ x∈B
tehát A∪B⊆B teljesül (q.e.d.)
Vegyük észre, hogy a bizonyításban a logikai "vagy" műveletet tartalmazó x∈A ∨ x∈B logikai kifejezés két eset vizsgálatát tette szükségessé (x∈A és x∈B). Mivel mindkét esetben ugyanazt a konklúziót kaptuk (x∈B), ezért levonhattuk az x∈A ∨ x∈B ⇒ x∈B következtetést. (Az alkalmazott logikai eljárást esetszétválasztásnak vagy esetelemzésnek nevezzük.)

(d3) ha A⊆A∩B, akkor A⊆B

(e) ha A⊆B és C⊆D teljesül, akkor A∩C⊆B∩D (→e1) és A∪C⊆B∪D (→e2) teljesül

(e1) ha A⊆B és C⊆D, akkor A∩C⊆B∩D

A bizonyítás lépései formálisan leírva:
x∈A∩C ⇒ x∈A ∧ x∈C
x∈A ∧ x∈C ⇒ x∈A
     x∈A ∧ A⊆B ⇒ x∈B
x∈A ∧ x∈C ⇒ x∈C
     x∈C ∧ C⊆D ⇒ x∈D
x∈A ∧ x∈C ⇒ x∈B ∧ x∈D
x∈B ∧ x∈D ⇒ x∈B∩D
tehát A∩C⊆B∩D teljesül (q.e.d.)

(e2) ha A⊆B és C⊆D, akkor A∪C⊆B∪D

A bizonyítás lépései formálisan leírva:
x∈A∪Cx∈A ∨ x∈C
     x∈A ∧ A⊆B ⇒ x∈B ⇒ x∈B ∨ x∈D
     x∈C ∧ C⊆D ⇒ x∈D ⇒ x∈D ∨ x∈B ⇒ x∈B ∨ x∈D
x∈A ∨ x∈Cx∈B ∨ x∈D
x∈B ∨ x∈D x∈B∪D
tehát A∪C⊆B∪D teljesül (q.e.d.)

(e/1) [kieg.] tetszőleges P, Q és C halmazok esetén,
ha C⊆P és C⊆Q teljesül, akkor C⊆P∩Q (két halmaz metszete tartalmaz minden olyan halmazt, amely a halmazok közös elemeiből áll; a metszet a "legnagyobb" ilyen tulajdonságú halmaz, a P és Q halmazok ún. legnagyobb alsó korlátja vagy infimuma)

Speciálisan, tetszőleges P, Q, C és C' halmazok esetén, ha P∪Q⊆C és P∪Q⊆C' teljesül, akkor P∪Q⊆C∩C' is teljesül (vagyis létezik olyan D=C∩C' halmaz, amelyre P∪Q⊆D, D⊆C és D⊆C' teljesül).

(e/2) [kieg.] tetszőleges P, Q és C halmazok esetén,
ha P⊆C és Q⊆C teljesül, akkor P∪Q⊆C (két halmaz uniója minden olyan halmaznak része, amely egyszerre tartalmazza mindkét halmaz elemeit; az unió a "legkisebb" ilyen tulajdonságú halmaz, a P és Q halmazok ún. legkisebb felső korlátja vagy szuprémuma)

(f) a metszetképzés és az unióképzés abszorpciója

(f1) A∩(A∪B)=A

A bizonyítás lépései formálisan leírva:

(1) x∈A∩(A∪B)
x∈A ∧ (x∈A ∨ x∈B) ⇒
x∈A
tehát A∩(A∪B)⊆A teljesül;

(2) x∈A
x∈A ∨ x∈B
x∈A(x∈A ∨ x∈B)
x∈A∩(A∪B)
tehát A⊆A∩(A∪B) teljesül;

(3) (1) és (2) alapján (A∩(A∪B)⊆A) ∧ (A⊆A∩(A∪B)) ⇒ A=A∩(A∪B) teljesül (q. e. d.)

(f2) A∪(A∩B)=A

A bizonyítás lépései formálisan leírva:

(1) x∈A∪(A∩B)
x∈A ∨ (x∈A ∧ x∈B) ⇒
     x∈A ⇒ x∈A
     x∈A ∧ x∈B ⇒ x∈A
x∈A ∨ (x∈A ∧ x∈B) ⇒ x∈A
tehát A∪(A∩B)⊆A teljesül;

(2) x∈A
x∈A ∨ (x∈A ∧ x∈B) ⇒
x∈A∪(A∩B)
tehát A⊆A∪(A∩B) teljesül;

(3) (1) és (2) alapján (A∪(A∩B)⊆A) ∧ (A⊆A∪(A∩B)) ⇒ A=A∪(A∩B) teljesül (q. e. d.)

(g) [kieg.] tetszőleges A és B halmazok esetén A=(A∩B)∪(A∩B) teljesül (egy halmaz felbontása diszjunkt komponensekre) (mivel AB=A∩B, ezért az 'A' halmaz fenti felbontása A=(A∩B)∪(AB) alakban is írható)

A bizonyítás lépései formálisan leírva (megjegyzés: a (2) lépésben felhasználjuk, hogy x∈I ⇔ x∈(B∪B) mindig teljesül):

(1) x∈(A∩B)∪(A∩B)
(x∈A ∧ x∈B) ∨ (x∈A ∧ x∈B) ⇒
     x∈A ∧ x∈B ⇒ x∈A
     x∈A ∧ x∈B ⇒ x∈A
(x∈A ∧ x∈B) ∨ (x∈A ∧ x∈B) ⇒ x∈A
tehát (A∩B)∪(A∩B)⊆A teljesül;

(2) x∈A és x∈(B∪B)
x∈A ∧ (x∈B ∨ x∈B) ⇒
     x∈A ∧ x∈B ⇒ (x∈A ∧ x∈B) ∨ (x∈A ∧ x∈B)
     x∈A ∧ x∈B ⇒ (x∈A ∧ x∈B) ∨ (x∈A ∧ x∈B) ⇒ (x∈A ∧ x∈B) ∨ (x∈A ∧ x∈B)
x∈A ⇒ (x∈A ∧ x∈B) ∨ (x∈A ∧ B)
tehát A⊆(A∩B)∪(A∩B) teljesül;

(3) (1) és (2) alapján (A∩B)∪(A∩B)⊆A ∧ A⊆(A∩B)∪(A∩B) ⇒ A=(A∩B)∪(A∩B) teljesül (q. e. d.)

(h) [kieg.] a metszetképzés és az unióképzés disztributivitása

Tekintsük például az A∩(B∪C) = (A∩B)∪(A∩C) azonosságot. Először (I.) azt bizonyítjuk, hogy A∩(B∪C) ⊆ (A∩B)∪(A∩C) teljesül, azután pedig (II.) azt bizonyítjuk, hogy (A∩B)∪(A∩C) ⊆ A∩(B∪C) teljesül. Mivel a részhalmaz reláció antiszimmetrikus, I. és II. teljesüléséből az azonosság bal és jobb oldalán szereplő kifejezések egyenlősége már következik.
    (I.) Legyen x∈A∩(B∪C) tetszőleges elem. Ekkor a metszetképzés definíciója miatt x∈A és x∈(B∪C) teljesül. Az unióképzés definíciója miatt x∈(B∪C) pontosan akkor teljesül, ha vagy x∈B, vagy x∈C teljesül, amiből x∈A ∧ (x∈B ∨ x∈C) következik. Itt két eset lehetséges:
        (I.i.) x∈A és x∈B teljesül. Ebből a bővítés szabályát az x∈A ∧ x∈B kifejezésre alkalmazva
            x∈A ∧ x∈B ⇒ (x∈A ∧ x∈B) ∨ (x∈A ∧ x∈C) következik.
        (I.ii.) x∈A és x∈C teljesül. Ismét a bővítés szabályát alkalmazva az x∈A ∧ x∈C kifejezésre
            x∈A ∧ x∈C ⇒ (x∈A ∧ x∈C) ∨ (x∈A ∧ x∈B) ⇒ (x∈A ∧ x∈B) ∨ (x∈A ∧ x∈C) adódik.
    Mivel mindkét esetben azonos következtetésre jutottunk, ezért x∈A ∧ (x∈B ∨ x∈C) ⇒ (x∈A ∧ x∈B) ∨ (x∈A ∧ x∈C) teljesül (I.), amiből az unióképzés és a metszetképzés definíciója miatt x∈(A∩B)∪(A∩C) következik. A részhalmaz reláció definíciója következtében tehát A∩(B∪C) ⊆ (A∩B)∪(A∩C) teljesül.
    (II.) Legyen x∈(A∩B)∪(A∩C) tetszőleges elem. Ekkor az unióképzés definíciója miatt vagy x∈(A∩B), vagy x∈(A∩C) teljesül. Tehát most is két eset lehetséges:
        (II.i.) x∈(A∩B) teljesül. Ekkor a metszetképzés definíciója miatt x∈A és x∈B teljesül. Ebből a bővítés szabályát az x∈A ∧ x∈B kifejezésre alkalmazva
            x∈A ∧ x∈B ⇒ x∈A ∧ (x∈B ∨ x∈C) következik.
        (II.ii.) x∈(A∩C) teljesül. Ekkor a metszetképzés definíciója miatt x∈A és x∈C teljesül. Ismét a bővítés szabályát alkalmazva az x∈A ∧ x∈C kifejezésre
            x∈A ∧ x∈C ⇒ x∈A ∧ (x∈C ∨ x∈B) ⇒ x∈A ∧ (x∈B ∨ x∈C) adódik.
    Mivel mindkét esetben azonos következtetésre jutottunk, ezért x∈(A∧B)∨(A∧C) ⇒ x∈A ∧ (x∈B ∨ x∈C) teljesül (II.), amiből az unióképzés és a metszetképzés definíciója miatt x∈A∩(B∪C) következik. Emiatt a részhalmaz reláció definíciója miatt (A∩B)∪(A∩C) ⊆ A∩(B∪C) teljesül.
    (III.) Összegezve a fentieket: amint azt a bizonyítás elején említettük, a részhalmaz reláció antiszimmetriája miatt I. és II. teljesüléséből az azonosság bal és jobb oldalán szereplő kifejezések egyenlősége már következik. Ezért az A∩(B∪C) = (A∩B)∪(A∩C) azonosság tetszőleges A, B és C halmazok esetén fennáll.

A bizonyítás lépései formálisan leírva:
  • x∈A∩(B∪C)
    • x∈A ∧ x∈(B∪C) ⇒
    • x∈A ∧ (x∈B ∨ x∈C) ⇒*
      • x∈A ∧ x∈B ⇒ (x∈A ∧ x∈B) ∨ (x∈A ∧ x∈C)
      • x∈A ∧ x∈C ⇒ (x∈A ∧ x∈C) ∨ (x∈A ∧ x∈B) ⇒ (x∈A ∧ x∈B) ∨ (x∈A ∧ x∈C)
    • (x∈A ∧ x∈B) ∨ (x∈A ∧ x∈C) ⇒
    • (x∈A∩B) ∨ (x∈A∩C) ⇒
    • x∈(A∩B)∪(A∩C)
  • x∈(A∩B)∪(A∩C)
    • x∈(A∩B) ∨ x∈(A∩C) ⇒
    • (x∈A ∧ x∈B) ∨ (x∈A ∧ x∈C) ⇒*
      • x∈A ∧ x∈B ⇒ x∈A ∧ (x∈B ∨ x∈C)
      • x∈A ∧ x∈C ⇒ x∈A ∧ (x∈C ∨ x∈B) ⇒ x∈A ∧ (x∈B ∨ x∈C)
    • ⇒ x∈A ∧ (x∈B ∨ x∈C) ⇒
    • x∈A ∧ x∈(B∪C) ⇒
    • x∈A∩(B∪C)
  • A∩(B∪C)⊆(A∩B)∪(A∩C) ∧ (A∩B)∪(A∩C)⊆A∩(B∪C) ⇒
    • A∩(B∪C) = (A∩B)∪(A∩C) (q. e. d.)

Ha a bizonyítás során felhasználjuk az "és" és "vagy" logikai műveletek disztributivitását, ebből mind az I., mind a II. pont végkövetkeztetése azonnal következik. A következtetés logikáját például az alábbi két kijelentés szemlélteti:
(1) Láttam az utcán Katit és vagy Lenkét, vagy Zsuzsát.
(2) Láttam az utcán Katit és Lenkét, vagy Katit és Zsuzsát.
(Tegyük fel, hogy Kati és Zsuzsa egypetéjű ikrek, úgy hasonlítanak egymásra, mint két tojás. :) )
Az "és" és "vagy" logikai műveletek disztributivitása miatt a két kijelentésben ugyanazt állítjuk.

(i) [kieg.] de Morgan-féle azonosságok

(1) Bizonyítsuk be az (A∩B) = AB azonosságot.
A bizonyítás lépései formálisan leírva:
  • x∈(A∩B)
    • x∉(A∩B)
      • Ha az 'A' és 'B' halmazok elemei meghatározott tulajdonságok alapján választhatók ki, akkor A∩B azokat az elemeket jelenti, amelyek nem rendelkeznek egyszerre mind a két (ti. 'A' és 'B') tulajdonsággal. Ez ekvivalens azzal, hogy ezek az elemek vagy az egyik tulajdonsággal (A), vagy a másikkal (B) nem rendelkeznek.
    • x∉A ∨ x∉B
    • x∈A ∨ x∈B
    • x∈AB
  • x∈AB
    • x∈A ∨ x∈B
      • x∉A ⇒ x∉(A∩B)
      • x∉B ⇒ x∉(A∩B)
    • x∉(A∩B) ⇒
    • x∈(A∩B)
  • (A∩B)ABAB(A∩B)
    • (A∩B)=AB (q. e. d.)
(2) Bizonyítsuk be az (A∪B) = AB azonosságot.
A bizonyítás lépései formálisan leírva:
  • x∈(A∪B)
    • x∉(A∪B)
      • Ha az 'A' és 'B' halmazok elemei meghatározott tulajdonságok alapján választhatók ki, akkor A∪B kizárja azokat az elemeket, amelyek akár az 'A', akár a 'B' tulajdonsággal (vagy mindkettővel) rendelkeznek. Ez ekvivalens azzal, hogy ezek az elemek nem rendelkeznek sem az egyik (A), sem a másik (B) tulajdonsággal.
    • x∉A ∧ x∉B
    • x∈A ∧ x∈B
    • x∈AB
  • x∈AB
    • x∈A ∧ x∈B
    • x∉A ∧ x∉B ⇒
    • x∉(A∪B) ⇒
    • x∈(A∪B)
  • (A∪B)ABAB(A∪B)
    • (A∪B)=AB (q. e. d.)

Bizonyítsa be a halmazműveletekre vonatkozó azonosságok alapján, hogy tetszőleges A, B, C halmazokra mindig teljesülnek az alábbi azonosságok: (tipp: a halmazok különbségét írja át az AB = A∩B azonosság alapján, és utána alkalmazza az unió, metszet és komplementerképzésre vonatkozó azonosságokat!)

(a) AB = A∪B

(b) A(A∩B) = AB

(c) A∪B = A∪(BA)

(d) A∩(BA) = ∅

(e) (A∪B)B = AB

(f) (AB)C = A(B∪C) = (AC)(BC)

(g) A(BC) = (AB)∪(A∩C)

(h) (A∩B)C = (A∩B)(A∩C) = A∩(BC)

(i) (A∪B)C = (AC)∪(BC)

(j) A(B∪C) = (AB)∩(AC) = (AB)C

(k) A(B∩C) = (AB)∪(AC)

(l) (AB)∪B = A∪B

(m) A(AB) = A∩B

(n) (A∪B)∩(A∪B) = (A∩B)∪(AB)

Melyek azok a halmazok, amelyekre AB=BA teljesül? (tipp: először igazolja, hogy AB és BA diszjunktak, majd azt, hogy AB=BA=∅, végül azt, hogy A=B teljesül. Az utolsó lépéshez például fel lehet használni az A=(A∩B)∪(AB) azonosságot.)

[kieg.] Igazoljuk az (A∩B)∪(B∩A)∪(A∩B) = A∪B azonosságot! (tipp: induljunk ki a bal oldali kifejezésből, és a halmazműveletek ismert azonosságainak megfelelő átalakításaival jussunk el a jobb oldali kifejezéshez!)

Például zárójelezzük a bizonyítandó azonosság bal oldalát
    (A∩B)∪(B∩A)∪(A∩B) = ((A∩B)∪(B∩A))∪(A∩B)
módon, és ezután a disztributivitást kifejező azonosságon
    A∪(B∩C)=(A∪B)∩(A∩C)
hajtsuk végre az A↔(A∩B), B↔B és C↔A helyettesítést. Ekkor egy
    (A∩B)∪(B∩A)=((A∩B)∪B)∩((A∩B)∩A)
"új" azonossághoz jutunk, amelynek bal oldala a bizonyítandó azonosság jobb oldalán szerepel. Ezt pótolva az "új" azonosság jobb oldalával
    ((A∩B)∪(B∩A))∪(A∩B) = (((A∩B)∪B)∩((A∩B)∩A))∪(A∩B)
adódik a bizonyítandó azonosságra.

Egy lehetséges megoldás például a következő:
(A∩B)∪(B∩A)∪(A∩B) = (asszociativitás, zárójelezés)
((A∩B)∪(B∩A)) ∪ (A∩B) = (disztributivitás, helyettesítés, pótlás)
(((A∩B)∪B)((A∩B)∪A)) ∪ (A∩B) = (kommutativitás, helyettesítés, pótlás)
((B∪(A∩B))(A∪(A∩B))) ∪ (A∩B) = (disztributivitás, helyettesítés, pótlás)
(((B∪A)(B∪B))((A∪A)(AB))) ∪ (A∩B) = (A∪A=I, helyettesítés, pótlás)
(((B∪A)∩I)((A∪A)(AB))) ∪ (A∩B) = (A∪A=I ⇔ A∪A=I, pótlás)
(((B∪A)∩I)(I∩(AB))) ∪ (A∩B) = (A∩I=A, helyettesítés, pótlás)
((B∪A)(I∩(AB))) ∪ (A∩B) = (A∩I=A ⇔ I∩A=A, helyettesítés, pótlás)
((B∪A)(AB)) ∪ (A∩B) = (kommutativitás, pótlás)
((A∪B)(AB)) ∪ (A∩B) = (kommutativitás, helyettesítés, pótlás)
(A∩B) ∪ ((A∪B)(AB)) = (disztributivitás, helyettesítés)
((A∩B)∪(A∪B))((A∩B)∪(AB)) = (de Morgan szabály, helyettesítés, pótlás)
((A∩B)∪(A∪B))((A∩B)∪(A∩B)) = (A∪A=I, helyettesítés, pótlás)
((A∩B)∪(A∪B)) ∩ I = (A∩I=A, helyettesítés)
((A∩B)∪(A∪B)) = (asszociativitás, helyettesítés)
(((A∩B)∪A) ∪ B) = (kommutativitás, helyettesítés, pótlás)
((A∪(A∩B)) ∪ B) = (abszorpció, pótlás)
((A) ∪ B) = (felesleges zárójelek elhagyása)
A∪B (q.e.d.)
Vegyük észre, hogy a most levezetett azonosság bal oldala kifejezhető a szimmetrikus differenciával:
(A∩B)∪(B∩A)∪(A∩B) = (AΔB)∪(A∩B) = A∪B


Boda István, 2021.