KURZUS: Matematika (Függvénytan)

MODUL: Halmazok

2. lecke: További műveletek halmazokkal

Tanulási cél: Megismerkedni a komplementer képzés, a szimmetrikus differencia műveletekkel és a legfontosabb azonosságaikkal.

Tananyag:
Tankönyv: Ács László, Gáspár Csaba: Analízis I
Fejezet: 1.1

Elméleti összefoglaló:
Egy konkrét halmazelméleti feladat vagy gondolatmenet esetén feltételezhetjük, hogy van egy H alaphalmaz, amelynek a szóban forgó feladatban vagy gondolatmenetben szereplő összes halmaz részhalmaza. (Ez nem egy erős feltevés, a feladatban szereplő össze halmaz uniója mindig ilyen tulajdonságú például.)

Ekkor az AH halmaz H-ra vonatkozó kiegészítő vagy komplementer halmaza az A ¯ =H\A halmaz. (Felhívjuk a figyelmet arra, hogy egy adott A halmaz komplementere függ attól, hogy melyik H alaphalmazra vonatkoztatjuk, persze az alaphalmazt egy feladaton belül nem szokás változtatni.) Ez a művelet idempotens, azaz A ¯ ¯ =A .

Érvényesek az alábbi úgynevezett de Morgan azonosságok:

AB ¯ = A ¯ B ¯ ,

AB ¯ = A ¯ B ¯ .

Ezek nem csak két halmaz esetén igazak:

A 1 A 2 A 3 ... A n ¯ = A 1 ¯ A 2 ¯ A 3 ¯ ... A n ¯ ,

A 1 A 2 A 3 ... A n ¯ = A 1 ¯ A 2 ¯ A 3 ¯ ... A n ¯ .

A figyelmes olvasó észrevehette, hogy eddig egyetlen olyan azonosságot sem adtunk meg, amelyben a különbségképzés művelete szerepelt volna. Ennek az oka az, hogy ilyen azonosságokra nincs szükség, a kivonás kifejezhető más műveletekkel, ahogyan azt a következő, könnyen igazolható és gyakran felhasznált formula mutatja:

A\B=A B ¯ .

Az A és a B halmazok szimmetrikus differenciája az

AB=( A\B )( B\A )

halmaz.

A szimmetrikus differencia kommutatív:

AB=BA

és asszociatív:

A( BC )=( AB )C .

Kidolgozott feladatok:

1. feladat Tetszőleges A, B és C halmazok esetén ábrázoljuk Venn-diagramon az A ¯ ( BC ) és az A ¯ ( BC ) ¯ halmazokat.

Megoldás: Kezdjük az A ¯ ( BC ) halmazzal. Egy két tagú metszetet kell ábrázolnunk, (amelynek a második tagja egy kéttagú unió). Ábrázoljuk az első ábrán a metszet első tagját:

2-1. ábra

: A ¯ .

A következő ábra a metszet második tagját mutatja:

2-2. ábra

: BC .

A metszethez a mindkét ábrán megjelölt elemek tartoznak:

2-3. ábra

: A ¯ ( BC ) .

Ábrázoljuk ezután az A ¯ ( BC ) ¯ halmazt is. Ha az ábrázolni kívánt halmazban sok a komplementer képzés alkalmazhatjuk a következő fogást. Először nem az eredeti halmazt ábrázoljuk, hanem a komplementerét. Ez most A ¯ ( BC ) ¯ ¯ . De a második de Morgan azonosság miatt, felhasználva azt is, hogy egy halmaz komplementerének komplementere az eredeti halmaz

A ¯ ( BC ) ¯ ¯ =A( BC ) .

Ennek a halmaznak az ábráját mutatja a következő ábra:

2-4. ábra

: A( BC ) .

Az eredetileg ábrázolandó halmazba azok az elemek tartoznak bele, amelyek az utolsó ábrán nincsenek megjelölve, azaz a végeredmény

2-5. ábra

: A ¯ ( BC ) ¯ .

2. feladat Bizonyítsuk be levezetéssel is, hogy tetszőleges A és B halmaz esetén

( A\B )( AB )( B\A )=AB .

Megoldás: Amikor levezetéssel igazolunk egy formulát, akkor általában az első lépés az, hogy eltüntetjük a kivonásokat a formulából. Ha ezt most is megtesszük, akkor az igazolandó képlet a következő lesz:

( A B ¯ )( AB )( B A ¯ )=AB .

Persze legtöbbször a bonyolultabb oldalt alakítjuk át, egyszerűsítjük, amíg a másik oldalt nem kapjuk. Ez most a bal oldal. Ha jól megnézzük ennek a három tagú uniónak az első két tagját, felismerhetjük benne a metszetnek az unióra vonatkozó disztributivitását kifejező azonosság egyik oldalát. Úgy szoktuk ezt mondani, hogy az első két tagból kiemelhető az A halmaz.

Az unió asszociatív, ezért egy zárójellel össze is foglalhatjuk ezt a két tagot, ekkor a bal oldal így fog kinézni:

( A B ¯ )( AB )( B A ¯ )=( ( A B ¯ )( AB ) )( B A ¯ ) .

Ha most az első zárójelben lévő két tag helyett az említett azonosság másik oldalát írjuk, azt kapjuk, hogy

( ( A B ¯ )( AB ) )( B A ¯ )=( A( B ¯ B ) )( B A ¯ ) .

Mivel B ¯ B=H és AH=A , az eredeti összefüggés bal oldala így alakul:

( A( B ¯ B ) )( B A ¯ )=A( B A ¯ ) .

Mivel az A halmaznak egy két tagú metszettel kell képezni az unióját most alkalmazható a másik disztributivitás, ami célhoz is vezet:

A( B A ¯ )=( AB )( A A ¯ )=( AB )H=AB ,

ismét felhasználva, hogy egy halmaznak és a komplementerének az uniója az alaphalmaz és azt, hogy bármely halmaznak az alaphalmazzal vett metszete a szóban forgó halmaz.

Mutatunk egy másik megoldást is.

Az eredeti azonosságunk középső tagja, a metszet kommutativitása miatt, így is írható:

( A B ¯ )( AB )( B A ¯ )=( A B ¯ )( BA )( B A ¯ ) .

Most meg a második két tagot lehet összefogni egy zárójellel és kiemelni a B-t, ez arra vezet, hogy

( A B ¯ )( ( BA )( B A ¯ ) )=( A B ¯ )( B( A A ¯ ) )=( A B ¯ )B .

Bármelyik úton is indulunk el a disztributivitás felhasználása eltünteti az AB tagot. Jó lenne ha az két példányban lenne meg, mert akkor mindkét átalakítást elvégezhetnénk.

Innen már könnyen rájöhetünk, hogy, miután AA=A , egy halmazalgebrai kifejezésben az egyik tagot mindig lecserélhetjük önmagával vett többszörös uniójával. (ugyanez igaz metszetre is).

Tehát a levezetés így is alakulhat:

( A B ¯ )( AB )( B A ¯ )=( A B ¯ )( AB )( AB )( B A ¯ )= =( A B ¯ )( AB )( BA )( B A ¯ )= =( ( A B ¯ )( AB ) )( ( BA )( B A ¯ ) )= =( A( B B ¯ ) )( B( A A ¯ ) )=AB

Ez fogás egy kicsit hasonlít ahhoz, mint amikor másodfokú kifejezést teljes négyzetté egészítünk ki a hiányzó rész becsempészésével.

3. feladat Bizonyítsuk be, hogy tetszőleges A, B és C halmazok esetén

A\( BC )=( A\B )\C .

Megoldás: "Igazoljuk" az összefüggést először Venn-diagramokkal. Ez úgy történhet, hogy lerajzoljuk először az azonosság bal oldalát, majd egy ugyanolyan kiinduló ábrán az azonosság jobb oldalát, és megállapítjuk, hogy mindkét esetben ugyanazokat az elemeket jelöltük meg.

Kezdjük a bal oldallal. Az alábbi ábrák, reméljük, önmagukért beszélnek:

: A : BC : A\( BC )

Az azonosság jobb oldalához tartozó ábrák:

: A\B : C : ( A\B )\C

Ezután levezetéssel bebizonyítjuk a formulánkat. Átalakítjuk először a bal oldalt, felhasználva, hogy két halmaz különbsége az elöl álló halmaz és a hátul álló halmaz komplementerének a metszete:

A\( BC )=A ( BC ) ¯ .

Az unió komplementerére vonatkozó de Morgan azonosság alapján

A ( BC ) ¯ =A( B ¯ C ¯ ) .

De a metszet asszociatív, így

A( B ¯ C ¯ )=( A B ¯ ) C ¯ .

Ez tehát a bal oldal. Ha a jobb oldalon is eltüntetjük a kivonásokat, kapjuk, hogy

( A\B )\C=( A B ¯ )\C=( A B ¯ ) C ¯ ,

ami valóban ugyanaz, mint az átalakított bal oldal.

4. feladat Igazoljuk, hogy tetszőleges A, B és C halmazok esetén

A\( B\C )=( A\B )( AC ) .

Megoldás: A bal oldalhoz tartozó Venn-diagramok:

: A : B\C : A\( B\C ) .

A jobb oldalhoz tartózóak:

: A\B : AC : ( A\B )( AC ) .

Látjuk, hogy valóban ugyanazok az elemek vannak mindkét oldal Venn-diagramján megjelölve.

Lássuk a formula matematikai szempontból precíz levezetését.

Induljunk ki a bal oldalból és először szabaduljunk meg a kivonásoktól:

A\( B\C )=A\( B C ¯ )=A ( B C ¯ ) ¯ .

Felhasználva az egyik de Morgan azonosságot és azt, hogy C ¯ ¯ =C ez így folytatható:

A ( B C ¯ ) ¯ =A( B ¯ C ¯ ¯ )=A( B ¯ C ) .

Végül, felhasználva a metszet unióra vonatkozó disztributivitását,

A( B ¯ C )=( A B ¯ )( AC )=( A\B )( AC ) ,

ami a bizonyítandó formula jobb oldala.

5. feladat Igazoljuk az alábbi állítást:

ABC akkor és csak akkor, ha A B ¯ C .

Megoldás: Most is tanulságos lehet Venn-diagramokat rajzolni. Ebben az esetben nem egy halmazalgebrai egyenlőség két oldalát kell ábrázolni, hanem fel kell venni halmazokat úgy, hogy az egyik oldali tartalmazás teljesüljön, és be kell látni, hogy ekkor minden esetben igaz a másik oldali tartalmazás is.

Először jöjjön az ABC akkor A B ¯ C következtetés szemléltetése.

Az első ábrán felvettük az A és B halmazt, és megjelöltük a metszetüket. A második ábrán felvettük a C halmazt, úgy, hogy teljesüljön az ABC reláció.

2-6. ábra2-7. ábra2-8. ábra

A harmadik ábrán pedig, szürkítéssel, megjelöltük a B ¯ C halmaz elemeit. Láthatjuk, hogy az A halmaz minden elemét megjelöltük szürkével, ez jelenti az A B ¯ C tartalmazást.

A fordított irányú következtetéshez induljunk ki egy olyan ábrából, ahol felvettük a B és C halmazokat, és megjelöltük a B ¯ C halmazt. Ezt mutatja a 2-9. ábra.

2-9. ábra

Vegyük ezután fel az A halmazt úgy, hogy teljesüljön az A B ¯ C reláció, tehát A teljes egészében a vízszintesen vonalkázott részbe essen. Persze úgy kell A-t megválasztani, hogy a metszete a B-vel, pontosabban a B vonalkázott részével, ne legyen üres, különben AB= , és ilyenkor az ABC reláció triviálisan teljesül.

Egy ilyen A választást mutat az ötödik ábra, ahol egyből megjelöltük az AB -t is.

2-10. ábra

Láthatjuk, hogy valóban teljesül az ABC reláció.

Jöjjön ezután az ekvivalencia bizonyítása.

Kezdjük az ABC esetén A B ¯ C következtetéssel.

Legyen xA . Ekkor két eset lehetséges. Ha xB -nek is, akkor xAB -nek, ami része C-nek, tehát xC , és akkor pláne igaz, hogy x B ¯ C . Ha xB , akkor x B ¯ és így megint csak következik, hogy x B ¯ C . Ez bizonyítja az A B ¯ C tartalmazást.

Fordítva, tegyük fel, hogy A B ¯ C és lássuk be, hogy ekkor ABC .

Legyen xAB . Ekkor x benne van az A-ban, és így a feltétel miatt x B ¯ C -nek is. De x benne van a B-ben is, tehát x B ¯ , ezért x csak úgy lehet a B ¯ C unióban, hogy benne van C-ben. Ez azt jelenti, hogy ABC , és éppen ezt akartuk belátni.

Ezzel igazoltuk az ekvivalenciát.

6. feladat Igazoljuk, hogy tetszőleges A, B és C halmaz esetén

( ABC )( A ¯ BC )( A B ¯ C )( AB C ¯ )= =( AB )( BC )( CA )

Megoldás: A disztributivitást felhasználva a bal oldali unió első két tagjából kiemelhető a BC halmaz és az első két tag uniója helyett ( A A ¯ )( BC )=BC írható. Hátra emeltünk ki, de ez senkit ne zavarjon meg. Ugyanígy belátható, hogy az első és a harmadik tag uniója AC , az első és a negyedik tag uniója AB . Ezek éppen azok a halmazok, amelyek az egyenlőség jobb oldalán is szerepelnek. Csak ismét az a baj, hogy ha bármelyik kiemelést végrehajtjuk eltűnik az ABC tag, és a többi kiemelés nem hajható végre. Persze most is az a kiút, hogy "hozzáuniózzuk" még kétszer az ABC -t a bal oldalhoz. Ekkor, mindjárt a legcélszerűbb sorrendben írva a tagokat és alkalmas zárójeleket is beírva, a bal oldal így írható:

( ( ABC )( A ¯ BC ) )( ( ABC )( A B ¯ C ) )( ( ABC )( AB C ¯ ) )= =( ( A A ¯ )( BC ) )( ( B B ¯ )( AC ) )( ( C C ¯ )( AB ) )=
( BC )( AC )( AB ) ,

ami az unió és a metszet kommutativitása miatt ugyanaz, mint a bizonyítandó formula jobb oldala.

7. feladat Bizonyítsuk be, hogy tetszőleges A és B halmazok esetén

A( AB )=B .

Megoldás: Rajzoljunk Venn-diagramot. Az első ábrán vízszintesen megvonalkáztuk az A halmaz elemei, függőlegesen az AB=( A\B )( B\A ) halmaz elemeit. Ne feledjük, hogy így az A\B halmaz elemei függőlegesen és vízszintesen is vonalkázásra kerültek!

2-11. ábra

Gondoljuk meg ezután, hogy A( AB )=( A\( ( A\B )( B\A ) ) )( ( ( A\B )( B\A ) )\A ) . Ezt a halmazt grafikusan úgy kapjuk, hogy a vízszintesen vonalkázott elemek közül elhagyjuk a függőlegesen vonalkázottakat, majd a függőlegesen vonalkázottak közül elhagyjuk a vízszintesen vonalkázottakat, és vesszük az így kapott két halmaz unióját.

Ha a vízszintesen vonalkázottak közül elhagyjuk a függőlegesen vonalkázottakat az AB halmaz elemeit kapjuk:

2-12. ábra

: A\( ( A\B )( B\A ) )=AB .

Ha a függőlegesen vonalkázottak közül elhagyjuk a vízszintesen vonalkázottakat a B\A halmaz elemeit kapjuk:

2-13. ábra

: ( ( A\B )( B\A ) )\A=B\A .

Ezek uniója valóban a B halmaz.

Levezetéssel bizonyítsuk is be a feladat állítását. Hogy némileg kevesebb képletet kelljen leírni a szimmetrikus differenciákban szereplő kivonásokat egyből eltüntetjük.

A( AB )=A( ( A B ¯ )( B A ¯ ) )=
=( A [ ( A B ¯ )( B A ¯ ) ] ¯ )( [ ( A B ¯ )( B A ¯ ) ] A ¯ )=

a de Morgan azonosság alapján

=( A ( A B ¯ ) ¯ ( B A ¯ ) ¯ )( [ ( A B ¯ )( B A ¯ ) ] A ¯ )=
=( A( A ¯ B )( B ¯ A ) )( [ ( A B ¯ )( B A ¯ ) ] A ¯ )=

a disztributivitás miatt

=( ( ( A A ¯ )( AB ) )( B ¯ A ) )( ( A B ¯ A ¯ )( B A ¯ A ¯ ) )=

mivel A A ¯ = és A ¯ A ¯ = A ¯

=( ( AB )( B ¯ A ) )( B A ¯ )=

ismét a disztributivitást használva

=( ( AB B ¯ )( ABA ) )( B A ¯ )=

(itt az első három tagú metszet üres, a második pedig AB )

=( AB )( B A ¯ )=( BA )( B A ¯ )=B( A A ¯ )=B .

8. feladat Igazoljuk, hogy tetszőleges A és B halmazok esetén

AB=( AB )\( AB ) .

Megoldás: A szimmetrikus differencia Venn-diagramjának megrajzolása sugallja ezt az összefüggést. A levezetéskor induljunk ki a jobb oldalból.

( AB )\( AB )=( AB ) ( AB ) ¯ =

ez az egyik de Morgan azonosság alapján

=( AB )( A ¯ B ¯ )=

ami, kétszer is felhasználva a disztributivitást

=( ( AB ) A ¯ )( ( AB ) B ¯ )=( ( A A ¯ )( B A ¯ ) )( ( A B ¯ )( B B ¯ ) )=

miután pedig A A ¯ =B B ¯ = ez

=( B A ¯ )( A B ¯ )=( A\B )( B\A )=AB .

9. feladat Bizonyítsuk be, hogy tetszőleges A, B és C halmazok esetén

A( BC )=( AB )( AC ) .

Megoldás: Az alábbi ábra a BC halmaz A-ba eső részét mutatja. Látjuk, hogy ez megkapható úgy is, hogy az AB és AC uniójából elhagyjuk a metszetüket, ( AB )( AC )=ABC -t. Az előző feladatból tudjuk, hogy amit így kapunk az éppen ( AB )( AC ) .

2-14. ábra

A levezetés során először alakítsuk át a bal oldalt. A szimmetrikus differenciát különbségképzés nélkül felírva, és használva a metszet unióra vonatkozó disztributivitását kapjuk, hogy

A( BC )=A( ( B C ¯ )( C B ¯ ) )=
=( AB C ¯ )( AC B ¯ ) .

Nem nagyon látszik, hogy ezt hogyan lehetne tovább egyszerűsíteni, ezért megpróbáljuk átalakítani az eredeti formula jobb oldalát úgy, hogy abból is ezt a kifejezést kapjuk.

Ekkor, az eddigieken túl még az egyik de Morgan azonosságot is felhasználva az adódik, hogy

( AB )( AC )=( ( AB ) ( AC ) ¯ )( ( AC ) ( AB ) ¯ )=
=( ( AB )( A ¯ C ¯ ) )( ( AC )( A ¯ B ¯ ) )=
=[ ( AB A ¯ )( AB C ¯ ) ][ ( AC A ¯ )( AC B ¯ ) ]=
( AB C ¯ )( AC B ¯ ) ,

ami ugyanaz, mint az átalakított bal oldal, (a szögletes zárójeleken belül lévő uniók első tagjai ugyanis az üres halmazzal egyenlők).

Ellenőrző kérdések:

1. kérdés: Tekintsük a H={ 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 } alaphalmaz A={ 3,4,5,8,9,12,13 } , B={ 4,5,6,7,8,9,10,11 } és C={ 1,2,3,4,5,6,7 } részhalmazait. Ekkor A( B ¯ \ C ¯ )=
{ 2,3,4,5,6,7,12,13 } .
{ 1,2,3,4,6,7,9,11,12 } .
{ 1,2,3,4,5,8,9,14,15 } .
{ 1,2,3,4,5,8,9,12,13 } .
2. kérdés: Az A ¯ ( B C ¯ ) ¯ halmaz Venn-diagramja
3. kérdés: Tetszőleges A, B és C halmazok esetén A\( BC )=
( A\B )\C .
( A\B )C .
( AB )( AC ) .
( A\B )( A\C ) .
4. kérdés: Ha ( A\B )B=A , akkor
AB .
A=B .
BA .
AB=A\B .
5. kérdés: Tetszőleges A, B és C halmazok esetén A( AB )=
A\B .
A\ B ¯ .
A ¯ \B .
A ¯ \ B ¯ .
6. kérdés: Tetszőleges A, B és C halmazok esetén ( AB )( AB )=
A B ¯ .
A B ¯ .
AB .
A ¯ B .
7. kérdés: Ha AC=BC , akkor
A= B ¯ .
AC .
A=B .
CA .