Tulajdonságok és De Morgan

Először is határozzuk meg a bal oldalt:

\( A \cup B = \{1, 2, 3, 5, 7, 9\} \)

Ennek komplementere az alaphalmazra nézve: \( \overline{A \cup B} = \{4, 6, 8, 10\} \)

Most nézzük a jobb oldalt. Számítsuk ki külön a komplementereket:

\( \overline{A} = \{2, 4, 6, 8, 10\} \)

\( \overline{B} = \{1, 4, 6, 8, 9, 10\} \)

Ezek metszete: \( \overline{A} \cap \overline{B} = \{4, 6, 8, 10\} \)

Mivel mindkét oldal eredménye azonos, az azonosság erre a példára teljesül.

Szimbólumokkal: \( \overline{A \cap B} = \overline{A} \cup \overline{B} \)

Szavakkal: Két halmaz metszetének a komplementere egyenlő a halmazok komplementereinek az uniójával. Vagy logikai megközelítésben: Egy "és" (konjunkció) tagadása egyenértékű a tagadások "vagy" (diszjunkció) kapcsolatával.

Alkalmazzuk a disztributív tulajdonságot visszafelé (kiemeljük az \(A\)-t):

\[ (A \cap B) \cup (A \cap \overline{B}) = A \cap (B \cup \overline{B}) \]

Tudjuk, hogy egy halmaznak és a komplementerének az uniója maga az alaphalmaz (\(U\)):

\[ B \cup \overline{B} = U \]

Bármely \(A\) halmaz és az alaphalmaz metszete visszaadja az \(A\) halmazt:

\[ A \cap U = A \]

Tehát a kifejezés egyszerűsített alakja: \(A\).

A halmazok különbségének definíciója szerint az \( A \setminus B \) halmaz elemei pontosan azok az \(x\) elemek, amelyekre igaz, hogy \( x \in A \) ÉS \( x \notin B \).

A komplementer halmaz definíciója szerint, ha \( x \notin B \), akkor az pontosan azt jelenti, hogy \( x \in \overline{B} \).

Ezt behelyettesítve kapjuk, hogy keressük azokat az elemeket, amelyekre \( x \in A \) ÉS \( x \in \overline{B} \).

A metszet definíciója pontosan ez a logikai ÉS kapcsolat, tehát ez a halmaz nem más, mint az \( A \cap \overline{B} \). Ezzel az állítást beláttuk.

A De Morgan azonosság értelmében az unió komplementere egyenlő a komplementerek metszetével: \( \overline{X \cup Y} = \overline{X} \cap \overline{Y} \).

Legyen most \( X = A \) és \( Y = \overline{B} \). Helyettesítsük be:

\[ \overline{A \cup \overline{B}} = \overline{A} \cap \overline{\overline{B}} \]

Tudjuk, hogy a dupla komplementer az eredeti halmazt adja vissza (\( \overline{\overline{B}} = B \)). Így:

\[ \overline{A} \cap B \]

Ezt másképp is felírhatjuk: a metszet kommutatív, tehát \( B \cap \overline{A} \), ami definíció szerint megegyezik a \( B \setminus A \) halmazzal.

Az \(A\) és \(B\) halmazok uniója felbontható a csak \(A\)-hoz tartozó, a csak \(B\)-hez tartozó, és a mindkettőhöz tartozó elemek halmazaira.

Ezek a halmazok: \( A \setminus B \), \( B \setminus A \), és \( A \cap B \).

Tehát az állítás: \( A \cup B = (A \setminus B) \cup (A \cap B) \cup (B \setminus A) \).

Bizonyítás: Fejezzük ki a különbséget metszettel: \( A \setminus B = A \cap \overline{B} \), és fejezzük be disztributivitással.

Nézzük a jobb oldal első két tagját:
\( (A \cap \overline{B}) \cup (A \cap B) = A \cap (\overline{B} \cup B) = A \cap U = A \)

Ezután adjuk hozzá a harmadik tagot:
\( A \cup (B \setminus A) = A \cup (B \cap \overline{A}) \)

Disztributív szabállyal felbontva:
\( (A \cup B) \cap (A \cup \overline{A}) = (A \cup B) \cap U = A \cup B \).

A három halmaz páronkénti metszete üres, tehát a felbontás valóban diszjunkt halmazok uniója.

Használjuk a halmazok tulajdonságait és a disztributív törvényt. Írjuk át a különbséget metszetté:

\[ (A \cap \overline{B}) \cup (A \cap B) \cup (\overline{A} \cap B) \]

Csoportosítsuk az első két tagot, és emeljünk ki \(A\)-t:

\[ [A \cap (\overline{B} \cup B)] \cup (\overline{A} \cap B) \]

Mivel \( \overline{B} \cup B = U \) (alaphalmaz), és \( A \cap U = A \), a kifejezés a következőre egyszerűsödik:

\[ A \cup (\overline{A} \cap B) \]

Alkalmazzuk ismét a disztributív törvényt (ezúttal uniót terjesztünk metszetre):

\[ (A \cup \overline{A}) \cap (A \cup B) \]

Mivel \( A \cup \overline{A} = U \), és bármely halmaz metszete az alaphalmazzal önmaga:

\[ U \cap (A \cup B) = \mathbf{A \cup B} \]

A bal oldali halmaz elemei azok az \(x\)-ek, amelyekre:

\[ x \in A \land \neg(x \in (B \cup C)) \]

Alkalmazzuk a De Morgan azonosságot logikai kijelentésekre az unió tagadására:

\[ \neg(x \in B \lor x \in C) \iff \neg(x \in B) \land \neg(x \in C) \]

Így a kifejezésünk:

\[ x \in A \land (x \notin B \land x \notin C) \]

A logikai "és" (konjunkció) asszociatív és idempotens, tehát többször is felhasználhatjuk az \(x \in A\) feltételt:

\[ (x \in A \land x \notin B) \land (x \in A \land x \notin C) \]

Ezek pontosan a definíciói a különbség halmazoknak:

\[ x \in (A \setminus B) \land x \in (A \setminus C) \]

Ami a metszet definíciója szerint egyenlő a jobb oldallal: \( (A \setminus B) \cap (A \setminus C) \).

Írjuk át a különbségeket metszetre és komplementerre:

\[ A \setminus (A \cap \overline{B}) \]

Alkalmazzuk újra a definíciót a külső különbségre:

\[ A \cap \overline{(A \cap \overline{B})} \]

Bontsuk fel a belső tagot a De Morgan azonosság alapján:

\[ A \cap (\overline{A} \cup \overline{\overline{B}}) = A \cap (\overline{A} \cup B) \]

Alkalmazzuk a disztributív törvényt:

\[ (A \cap \overline{A}) \cup (A \cap B) \]

Mivel \( A \cap \overline{A} = \emptyset \) (üres halmaz), az unió eredménye egyszerűen:

\[ \emptyset \cup (A \cap B) = \mathbf{A \cap B} \]

Számoljuk ki az első oldal elemeit. Először az uniót:

\( A \cup B = [-2; 5[ \cup [3; 8] = [-2; 8] \)

Ennek komplementere a valós számok halmazán:

\( \overline{A \cup B} = \mathbf{]-\infty; -2[ \cup ]8; \infty[} \)

Számoljuk ki a második oldal elemeit. Külön-külön a komplementerek:

\( \overline{A} = ]-\infty; -2[ \cup [5; \infty[ \)

\( \overline{B} = ]-\infty; 3[ \cup ]8; \infty[ \)

Képzeletbeli számegyenesen vagy logikai ellenőrzéssel megnézzük a metszetet (közös részt):

\( ]-\infty; -2[ \) mindkettőben benne van, hiszen \(-2 < 3\).

A pozitív ágon pedig a \( [5; \infty[ \) és a \( ]8; \infty[ \) közös része a \( ]8; \infty[ \).

Tehát a metszet: \( \mathbf{]-\infty; -2[ \cup ]8; \infty[} \). Az egyenlőség fennáll.

A definíció szerint a szimmetrikus differencia pont azokat az elemeket tartalmazza, amelyek pontosan egy halmazban vannak benne. Ez rögtön kiadja az \( (A \setminus B) \cup (B \setminus A) \) alakot, ahol a két tag diszjunkt (nincs közös elemük).

Induljunk ki a második formából, és jussunk el az elsőhöz:

\[ (A \cup B) \setminus (A \cap B) = (A \cup B) \cap \overline{(A \cap B)} \]

Alkalmazzuk a De Morgan azonosságot a második tagra:

\[ (A \cup B) \cap (\overline{A} \cup \overline{B}) \]

Bontsuk fel a zárójeleket a disztributív szabály alapján:

\[ (A \cap \overline{A}) \cup (A \cap \overline{B}) \cup (B \cap \overline{A}) \cup (B \cap \overline{B}) \]

Az \(A \cap \overline{A}\) és \(B \cap \overline{B}\) tagok üres halmazt (\(\emptyset\)) adnak, amiket elhagyhatunk az unióban:

\[ (A \cap \overline{B}) \cup (B \cap \overline{A}) \]

Ez pedig pontosan a különbségek definíciója: \( (A \setminus B) \cup (B \setminus A) \). Az állítást igazoltuk.

Általánosan igaz minden halmazra, hogy a metszet részhalmaza az uniónak: \( (A \cap B) \subseteq (A \cup B) \).

Az egyenlőséghez az is kell, hogy \( (A \cup B) \subseteq (A \cap B) \) fennálljon. Ez azt jelenti, hogy minden elem, ami benne van legalább az egyik halmazban, annak benne kell lennie mindkettőben.

Ha \(x \in A\), akkor az unióban is benne van, így a metszetben is benne kell lennie, amiből következik, hogy \(x \in B\) is. Ugyanígy fordítva.

A feltétel tehát az, hogy a két halmaznak minden eleme meg kell egyezzen, azaz: \( A = B \).

1. \( \overline{A \cup B} \): Az \( A \cup B \) azokat a háromszögeket tartalmazza, amelyek vagy derékszögűek, vagy egyenlő szárúak (esetleg mindkettő). A komplementer ezt tagadja, tehát a halmaz azon háromszögeket tartalmazza, amelyek se nem derékszögűek, se nem egyenlő szárúak. (Általános tompa- vagy hegyesszögű háromszögek). De Morgan szerint ez az \(\overline{A} \cap \overline{B}\).

2. \( \overline{A} \cup \overline{B} \): Ez a halmaz a De Morgan azonosság szerint megegyezik a \( \overline{A \cap B} \)-vel. A metszet (\( A \cap B \)) az egyenlő szárú derékszögű háromszögeket jelenti. Így a \( \overline{A} \cup \overline{B} \) tartalmaz minden olyan háromszöget, ami nem egyenlő szárú derékszögű háromszög. Ide tartozik pl. egy általános derékszögű, vagy egy szabályos háromszög is.

Alkalmazzuk a disztributív törvényt (kiemelés) párosával az első két, illetve a második két tagra.

Az első két tag: \( (A \cup B) \cup C \) és \( (A \cup B) \cup \overline{C} \).
A kiemelés után: \( (A \cup B) \cup (C \cap \overline{C}) = (A \cup B) \cup \emptyset = A \cup B \).

A harmadik és negyedik tag: \( (A \cup \overline{B}) \cup C \) és \( (A \cup \overline{B}) \cup \overline{C} \).
A kiemelés után: \( (A \cup \overline{B}) \cup (C \cap \overline{C}) = (A \cup \overline{B}) \cup \emptyset = A \cup \overline{B} \).

Most az egyszerűsített kifejezésünk így néz ki: \( (A \cup B) \cap (A \cup \overline{B}) \).

Emeljünk ki újra \(A\)-t (disztributivitás): \( A \cup (B \cap \overline{B}) \).

Mivel \( B \cap \overline{B} = \emptyset \), a végeredmény \(A\).

Az állítás hamis. Ez a műveletek helytelen asszociálása disztributivitás helyett.

A valós (disztributív) azonosság: \( A \cup (B \cap C) = (A \cup B) \cap (A \cup C) \).

Ellenpélda: Legyen \( A = \{1, 2\} \), \( B = \{2, 3\} \), \( C = \{4\} \).

Bal oldal: \( B \cap C = \emptyset \). Majd \( A \cup \emptyset = \{1, 2\} \).

Jobb oldal: \( A \cup B = \{1, 2, 3\} \). Majd \( \{1, 2, 3\} \cap C = \emptyset \).

Mivel \( \{1, 2\} \neq \emptyset \), az egyenlőség nem áll fenn általánosan.

A formula: \( |A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C| \)

Amikor összeadjuk a három halmaz elemszámát (\(|A| + |B| + |C|\)), akkor azokat a területeket, amelyek két halmazba tartoznak, kétszer számoltuk. A közös részt pedig háromszor.

Ezért ki kell vonnunk a páronkénti metszeteket. Így viszont a mindhárom halmazba tartozó elemeket (\(A \cap B \cap C\)) pontosan háromszor adtuk hozzá, és háromszor vontuk ki, azaz jelenleg egyáltalán nem számoljuk őket.

Ezért a képlet végén vissza kell adni ezt a részt, így érve el, hogy az eredetileg felírt 7 diszjunkt részhalmaz mindegyikének elemszáma pontosan egyszer legyen beszámítva.

A különbség definíciója alapján a bal oldalról elveszünk minden olyan elemet, ami az \(A\) halmaznak is eleme.

Ha a kivonás után az \(X\) halmaz elemszáma és tartalma változatlan marad, az csak úgy lehetséges, ha az \(A\) halmaznak nincs közös eleme az \(X\) halmazzal.

Vagyis a feltétel: \( X \cap A = \emptyset \) (az \(X\) és \(A\) halmazok diszjunktak).

1. Lépés: A különbség \( A \setminus B \) felírása metszetként: \( A \cap \overline{B} \).

2. Lépés: Helyettesítsük ezt be az eredeti kifejezésbe: \( A \setminus (A \cap \overline{B}) \).

3. Lépés: Alkalmazzuk ismét a különbség átírását: \( A \cap \overline{(A \cap \overline{B})} \).

4. Lépés: De Morgan azonosság alkalmazása a zárójelen belülre: \( A \cap (\overline{A} \cup \overline{\overline{B}}) = A \cap (\overline{A} \cup B) \).

5. Lépés: Disztributív törvény: \( (A \cap \overline{A}) \cup (A \cap B) \).

6. Lépés: Mivel \( A \cap \overline{A} = \emptyset \), az eredmény \( \emptyset \cup (A \cap B) = A \cap B \).

A bizonyítás teljes.

Kezdjük az első két taggal: \( (A \cup B) \cap (\overline{A} \cup B) \).

A metszet és az unió kommutatív, így látható, hogy a \(B\) mindkét zárójelben ott van unióval. Alkalmazzuk a disztributivitást "visszafelé" (emeljünk ki \(B\)-t):

\[ B \cup (A \cap \overline{A}) = B \cup \emptyset = B \]

Most az egyszerűsített részt metsszük össze a harmadik taggal:

\[ B \cap (A \cup \overline{B}) \]

Alkalmazzuk a disztributív szabályt:

\[ (B \cap A) \cup (B \cap \overline{B}) = (B \cap A) \cup \emptyset = A \cap B \]

Az eredmény az \(A\) és \(B\) metszete.

Az általánosított (kiterjesztett) De Morgan azonosságok a következők:

Ezek az azonosságok a matematikai indukció módszerével bizonyíthatók a két halmazra vonatkozó alapazonosságokból kiindulva.