Halmazok, logikai műveletek, bizonyítási módszerek
Ennek a témakörnek a képletei
Letöltöm az egész kurzus összes képletét:
LetöltömLetöltöm ennek a témakörnek a képleteit:
LetöltömVálogass kedvedre a témakör képletei között:
Halmazműveletek
Vannak az $A$ és $B$ halmazok.
Az $A$ és $B$ halmazok uniója: Azon elemek halmaza, amelyek legalább az egyik halmazban benne vannak.
Jele: $A \cup B$
Az $A$ és $B$ halmazok metszete: Azon elemek halmaza, amelyek mindkét halmazban benne vannak.
Jele: $A \cap B$
Az $A$ és $B$ halmazok különbsége: Azon elemek halmaza, amelyek az $A$ halmazba benne vannak, de a $B$ halmazba nem.
Jele: $A \setminus B$
Az $A$ halmaz komplementere a $H$ alaphalmazon nézve: Az alaphalmaz azon elemeinek halmza, amelyek nincsenek benne az $A$-ban.
Jele: $ \overline{A}$
Logikai szita formula
A logikai szita formula két halmazra:
\( \mid A \cup B \mid = \mid A \mid + \mid B \mid - \mid A \cap B \mid \)
A logikai szita formula három halmazra:
\( \mid A \cup B \cup C \mid = \mid A \mid + \mid B \mid + \mid C \mid - \mid A \cap B \mid - \mid A \cap C\mid - \mid B \cap C \mid + \mid A \cap B \cap C \mid \)
De Morgan azonosságok halmazokra
Az első De Morgan azonosság azt mondja, hogy a metszet komplementere pont megegyezik a komplementrek uniójával:
\( \overline{ A \cap B} = \overline{A} \cup \overline{B} \)
A második De Morgan azonosság pedig azt mondja, hogy az unió komplementere éppen megegyezik a komplementerek metszetével:
\( \overline{ A \cup B } = \overline{A} \cap \overline{B} \)
Hatványhalmaz
Egy halmaz összes részhalmazainak halmazát hatványhalmaznak nevezzük.
Pl.: az $A=\{x,y,z \}$ halmaz hatványhalmaza: $P(A)=\left\{ \emptyset. \{ x \}, \{ y \}, \{ z \}, \{ x, y \}, \{ x, z \}, \{ y, z \}, \{ x,y,z \} \right\} $
Szimmetrikus differencia
Az $A$ és $B$ halmazok szimmetrikus differenciája:
\( A \triangle B = \left( A \setminus B \right) \cup \left( B \setminus A \right) = ( A \cup B ) \setminus ( A \cap B) \)
Érdemes megjegyezni, hogy $A \triangle A = \emptyset$ és $A \triangle \emptyset= A $
Értékkészlet
Adott az $f: A \mapsto B$ függvény. A függvény értékkészlete azoknak az elemeknek a halmaza a $B$ halmazban, amelyek hozzá vannak rendelve valamely $A$ halmazbeli elemekhez.
Az értékkészlet jele az angol range szó alapján, ami azt jelenti, hogy kiterjedés: $R_f$ vagy az akadálymentesített jelölése: É.K.
Értelmezési tartomány
Egy kifejezés értelmezési tartományán azt a legbővebb halmazt értjük, ahol értelmezve van.
Függvény esetén azokat a szerencsés $x$-eket, amelyekhez a függvény hozzárendel egy $y$ számot, a függvény értelmezési tartományának nevezzük.
A következőket érdemes megjegyezni:
\( \sqrt[ \text{páros}]{ \text{ez itt} \geq 0} \quad \sqrt[ \text{páratlan} ]{ \text{ez itt bármi}} \quad \log{ \left( \text{ez itt} > 0 \right)} \quad \text{ tört nevező} \neq 0 \)
pl.: $ f(x)=\frac{4x}{(x-3)^4} $ értelmezési tartománya $ \forall x \in R \setminus \{ -3 \} $, mert nincs gyök és nincs logaritmus, de tört van, tehát a nevező nem lehet nulla ($x \neq 3$)
Univerzális kvantor
Az univerzális kvantor egy jelölése a "minden" kifejezésnek.
Jele: $\forall$
Egzisztenciális kvantor
Az egzisztenciális kvantor egy jelölése a "létezik" vagy "van olyan" kifejezésnek.
Jele: $\exists$
Logikai műveletek | Negáció
Az állítás negációja (vagy tagadása) egy egyváltozós művelet. Egy $A$ kijelentés negációja az a kijelentés, amely akkor igaz, ha $A$ hamis és akkor hamis, ha $A$ igaz.
Állítás
Az állítás (vagy kijelentés) olyan kijelentő mondat, amelyről egyértelműen eldönthetjük, hogy az igaz vagy hamis.
Logikai műveletek | Konjunkció
A konjunkció két állítás közti logikai művelet. Két kijelentés konjunkciója pontosan akkor igaz, ha mindkét kijelentés igaz, különben hamis.
Jele: $ A \land B$
Logikai műveletek | Diszjunkció
A diszjunkció két állítás közti logikai művelet. Két kijelentés diszjunkciója pontosan akkor igaz, ha legalább az egyik kijelentés igaz, különben hamis.
Jele: $ A \lor B$
Logikai műveletek | Implikáció
A "ha $A$, akkor $B$" kapcsolatnak megfelelő logikai műveletet nevezzük implikációnak. Az implikáció akkor hamis, ha $A$ igaz és $B$ hamis, minden más esetben igaz.
Jele: $A \Rightarrow B$
Logikai műveletek | Ekvivalencia
Az ekvivalencia egy olyan logikai művelet, amikor $A \Rightarrow B$ és $A \Leftarrow B$. Az ekvivalencia akkor igaz, ha $A$ és $B$ logikai értéke azonos, különben hamis.
Jele: $A \Leftrightarrow B$
Logikai De Morgan azonosságok
\( \neg \left( A \land B \right ) = \neg A \lor \neg B \)
\( \neg \left( A \lor B \right ) = \neg A \land \neg B \)
\( \neg \left( A \Rightarrow B \right ) = A \land \neg B \)
\( \neg \left( A \Leftrightarrow B \right ) = A \Leftrightarrow \neg B \)
Diszjunktív normálforma
A diszjunktív normálforma, röviden DNF egy olyan alakja egy logikai formuláknak, ahol a művelet a változóinak vagy negáltjainak konjunkcióinak diszjunkciója.
Teljes indukció
A teljes indukció olyan állítások bizonyítására alkalmas, melyek $n$ pozitív egész számtól függenek.
A teljes indukciós bizonyítás lépései:
1. lépés: Igazoljuk, hogy az állítás $n=1$ esetén vagy az első néhány $n$-re igaz.
2. lépés: Igazoljuk, hogy ha az állítás $n$-re igaz, akkor $n+1$ esetén is igaz.
Ezzel az állítást minden $n$ pozitív egész számra belátjuk.
Ennek a témakörnek a feladatai
Letöltöm az egész kurzus összes feladatát:
LetöltömLetöltöm ennek a témakörnek a feladatait:
LetöltömVálogass kedvedre a témakör feladatai között:
Adottak az $A$ és $B$ halmazok:
\( A= \{ 1, 2, 3, 4, 7, 8 \} \quad B= \{ 1,3,4,5,6 \} \)
Határozzuk meg...
a két halmaz metszetét!
a két halmaz unióját!
$ B\setminus A $-t!
Az $A$ halmaz legyen a $[2,6]$ zárt intervallum, a $B$ halmaz pedig az $]1,4[$ nyílt intervallum.
Határozzuk meg ezeket:
\( A \cap B \quad A \cup B \quad A \setminus B \)
a) Egy osztályban 12-en utálják a matekot és 18-an a fizikát. Összesen 20-an vannak, akik a kettő közül legalább az egyiket utálják. Hányan utálják mindkettőt?
b) Egy osztályba 20 tanuló jár. Az osztály összes tanulója közül 9-en szeretik a matekot és közülük 5 lány. Tudjuk még, hogy 5 fiú nem szereti a matekot. Hány lány jár az osztályba?
Egy osztályba 20-an járnak. Közülük 16-an vannak, akik a matekot és a fizikát is utálják. Hányan vannak, akik legalább az egyik tantárgyat szeretik?
Adottak a $G$ és $H$ halmazok:
\( G= \{ 1,2,3,4,6,12 \} \quad H= \{ 1,2,4,8,16 \} \)
Határozzuk meg a $G \cap H$ és $G \setminus H $ halmazokat!
Az $A$ halmaz elemei a 28 pozitív osztói, a $B$ halmaz elemei a 49 pozitív osztói. Adjuk meg az $A \cap B$ és $B \setminus A$ halmazokat elemeik felsorolásával!
Egy városban 60 étterem, 56 bár és 36 reggeliző hely üzemel. Olyan, ami étterem és bár is egyben 16 darab van, ami reggelizőként és bárként is üzemel, olyanból 20 darab van, és ami reggeliző és étterem is, olyan 11 darab van. 4 olyan hely van, ami reggelizőként, étteremként és bárként egyszerre működik. Hány olyan bár működik a városban, ami nem étterem és nem reggeliző hely?
Van három halmaz, $A=\{ 2, 3, 5, 7, 11 \}$, $B=\{x \in Z^+ | 1 \leq x^2 \leq 24 \}$ és $C$ pedig a 15 pozitív osztóinak halmaza. Ábároljuk ezeket a halmazokat és adjuk meg elemeinek felsorolásával az $A\cup B \cap C$ és az $A \cap B \setminus C$ halmazokat.
a) Egyenlő-e ez a két halmaz?
\( A= \{ 4; 6; 5;7 \} \quad B = \{ 7, 6, 5, 4 \} \)
b) Soroljuk fel az $A=\{ x, y, z \}$ halmaz összes részhalmazát.
c) Hány elemű lesz $B$-nek a hatványhalmaza?
\( B= \{ 5, 6, 7, 8 \} \)
Bizonyítsuk be, hogy
a) \( (A \cup \overline{B}) \cap B = A \cap B \)
b) \( (A \setminus (B \setminus A) = ( A \cap B) \cup (A \setminus B ) \)
c) \( A \Delta ((B \cup A) \Delta A ) \Delta B = (A\cap B) \Delta (A \setminus B) \)
a) Hogyha $A$ és $B$ halmazokról tudjuk, hogy $A\cap B = A \cup B$, akkor vajon igaz-e, hogy $A \Delta B = A \setminus B$?
b) Hogyha $A$ és $B$ halmazokról tudjuk, hogy $A \Delta B = B$, akkor vajon igaz-e, hogy $ (A \cup B) \Delta (A \cap B)= B \setminus A$?
c) Bizonyítsuk be, hogy tetszőleges $A$ és $B$ halmazokra teljesül, hogy:
\( (A \cup \overline{B} ) \cap B \subseteq (A \cup B) \setminus (B \setminus A) \)
d) Bizonyítsuk be, hogy tetszőleges $A$, $B$ és $C$ halmazokra teljesül, hogy:
\( (A \cup B) \setminus (C \cap (B \setminus A)) = A \cup (B \setminus C) \)
Adjuk meg az $A=\{ 1,2 \}$ és $B=\{ a,b,c \}$ halmazok Descartes-szorzatát.
Végezzük el az alábbi feladatokat:
a) Egy vonaton 400-an utaznak. Bizonyítsuk be, hogy utazik rajta két olyan utas, akiknek ugyanazon a napon van a születésnapja.
b) Mi történik, ha felszáll újabb 333 utas?
c) És ha 1200-an utaznak a vonaton?
a) Egy 5 kocsiból álló vonaton 460-an utaznak. Bizonyítsuk be, hogy van olyan kocsi, amiben legalább 80 utas van.
b) Egy másik vonat szintén 5 kocsiból áll. Legalább hányan utaznak a vonaton, ha tudjuk, hogy biztosan van olyan kocsi, amiben legalább 40-en utaznak?
c) Az egyik kocsiban egy 10 tagú társaság utazik. Mindenki a társaságból legalább 7 másik embert ismer. Bizonyítsuk be, hogy bármely 3 embernek van közös ismerőse.
Van itt ez az állítás: "Minden mamut sárga."
Válasszuk ki innen azokat, amik az állítás tagadása:
Egyik mamut sem sárga.
Van olyan mamut, ami sárga.
Van olyan mamut, ami nem sárga.
A legtöbb mamut nem sárga.
Nem minden mamut sárga.
Dontsük el az alábbi állításokról, hogy igazak, vagy hamisak.
a) Esik az eső és a mamut piros.
b) Esik az eső vagy a mamut piros.
c) Ha esik az eső, akkor a mamut piros.
Készítsük el az alábbi állítások igazságtábláit.
a) \( \neg A \wedge \neg B \)
b) \( A \wedge \neg B \)
c) \( \left( A \lor B \right) \Rightarrow \left( A \wedge B \right) \)
d) \( \neg A \Rightarrow \left( A \wedge B \right) \)
e) \( \neg A \wedge \left( A \lor B \right) \)
a) Van itt két láda. Az egyikben arany van, a másik üres, a ládákon lévő feliratok pedig lehetnek igazak vagy hamisak is. Anélkül, hogy hozzárénénk a ládákhoz, meg tudjuk-e mondani, hogy melyikben van az arany?
A ládák feliratai: "Ha a másik ládában van az arany, akkor mindkét ládában hamis felirat van." és "Az arany nem ebben a ládában van."
b) Ezúttal már három láda van. Az egyikben arany van, a másik kettő üres, a ládákon lévő feliratok pedig lehetnek igazak vagy hamisak is.
A ládák feliratai:
"A másodikon ládán a felirat igaz."
"Az arany ebben a ládában van és az első ládán a felirat hamis."
"Az arany olyan ládában van, amin a felirat hamis."
c) Most pedig tegyünk egy kört a lovagok és lókötők szigetén. Ezen a szigeten kétféle ember él, akik külsejük alapján teljesen egyformák. Csak éppen a lovagok mindig igazat mondanak, a lókötők pedig mindig hazudnak. Találkozunk két szigetlakóval.
X azt mondja: "Ha Y lovag, akkor én lókötő vagyok.". Y nem mond semmit. Milyen típusú X és Y?
d) Egy másik alkalommal három szigetlakóval találkozunk, akik ezt mondják:
X: "Y lókötő és Z lovag."
Y: "Lókötő vagyok és Z lovag."
Milyen típusú X, Y és Z?
e) Végü legy újabb esetben ismét három szigetlakóval találkozunk, akik ezt mondják:
X: Y lovag.
Y: X lókötő és Z lovag.
Milyen típusú X, Y és Z?
Tagadjuk a következő állítást:
"Az áldozat a szobában van, és ha nem találják meg, akkor holnap is ott lesz."
Mi a teljes diszjunktív normálformája?
a) \( A \Rightarrow \left( B \wedge C \right) \)
b) \( \left( A \Leftrightarrow B \right) \wedge \neg A \)
c) \( \left( A \Rightarrow B \right) \wedge \left( A \vee B \right) \)
Bizonyítsuk be, hogy $1+3+5+\dots + 2n-1 = n^2$ minden pozitív egész $n$ esetén.
Igazoljuk teljes indukcióval, hogy minden $n$ pozitív egész számra
\( 1\cdot 4 + 2\cdot 7 + \dots + n\cdot (3n+1) = n \cdot (n+1)^2 \)
Igazoljuk teljes indukcióval, hogy minden $n$ pozitív egész számra
\( \frac{1}{1\cdot 2} + \frac{1}{3 \cdot 4} + \dots + \frac{1}{(2n-1)2n)} = \frac{1}{n+1} + \frac{1}{n+2} + \frac{1}{n+3} + \dots + \frac{1}{2n} \)
Igazoljuk teljes indukcióval, hogy minden $n$ pozitív egész számra
\( 1\cdot 2 + 2\cdot 3 + \dots + n (n+1) = \frac{ n(n+1)(n+2)}{3} \)
Igazoljuk teljes indukcióval, hogy minden $n$ pozitív egész számra
\( \left( 1- \frac{1}{4} \right) \cdot \left( 1- \frac{1}{9} \right) \cdot \left( 1- \frac{1}{16} \right) \cdot \dots \cdot \left( 1 - \frac{1}{n^2} \right) = \frac{n+1}{2n} \)
Igazoljuk teljes indukcióval, hogy $n$ db. egyenes a síkot legfeljebb $ \frac{n^2+n+2}{2}$ részre osztja.
a) Írd fel a ${2; 3; 4}$ halmaznak azon részhalmazait, melyeknek a 2 eleme, és a 4 nem eleme!
b) Az $A$ és $B$ halmazokról a következőket tudjuk:
\( A \cap B = \{ 1;2 \} \quad A \cup B = \{ 1;2;3;4;5;6;7 \} \quad A \setminus B = \{ 5;7 \} \)
c) Adottak a következő halmazok:
\( A= \{ 2;3;5;7;11;13;17;19 \} \)
\( B= \{ 1;4;7;10;13;16;19 \} \)
\( C= \{ 1;2;3;5;8;13 \} \)
Elemeik felsorolásával adjuk meg a $ C \setminus A$ és az $(A \cup B ) \cap C$ halmazt!
Egy osztályban a következő háromféle sportkört hírdették meg: kosárlabda, foci és röplabda. Az osztály 30 tanulója közül kosárlabdára 14, focira 19, röplabdára 14 tanuló jelentkezett. Ketten egyik sportra sem jelentkeztek. Három gyerek kosárlabdázik és focizik, de nem röplabdázik, hatan fociznak és röplabdáznak, de nem kosaraznak, ketten pedig kosárlabdáznak és röplabdáznak, de nem fociznak. Négyen mind a három sportot űzik. Készítsünk halmazábrát!
Anett és Berta egy írott szöveget figyelmesen átolvasott. Anett 24 hibát talált benne, Berta 30-at. Ezek között 12 hiba volt csak, amit mindketten észrevettek. Később Réka is átnézte ugyanazt a - javítatlan - szöveget, és ő is 30 hibá talált. Réka az Anett által megtalált hibákból 8-at vett észre, a Berta által észleltekből 11-et. Mindössze 5 olyan hiba volt, amit mind a hárman észrevettek.
a) Együtt összesen a szöveg hány hibáját fedezték fel?
b) A megtalált hibák hány százalékát vették észre legalább ketten?
a) Egy biztosítóhoz az egyik hónapban 24 autós biztosítási kárigény érkezett, és ezek közül 8-an más kárigényt is benyújtottak. Lakásbiztosításra 7 igény érkezett, és egyéb igény 17. 30 olyan ügyfél volt, aki csak egy igényt nyújtott be, 1-1 olyan ügyfél volt, aki a lakáson kívül még pontosan egy kárigényt nyújtott be és nem volt olyan, aki mindhármat. Készítsünk ábrát, és állapítsuk meg, hogy hányan vannak, akik pontosan két kárigényt nyújtottak be!
b) Egy középiskolába 700 tanuló jár. Közülük 10% sportol rendszeresen a két iskolai egyesület közül legalább az egyikben. Az atlétikai egyesületnek 36 tanuló tagja, és pontosan 22 olyan diák van, aki az atlétika és a kosárlabda egyesületnek is tagja.
1) Ábrázoljuk az egyesületekben sportoló diákok megoszlását halmazokkal.
2) Hányan sportolnak a kosárlabda egyesületben?
Egy város 18 étterme közül 11-ben reggelit, 11-ben vegetáriánus menüt lehet kapni, és 10-ben van felszolgálás. Mind a 18 étteremben legalább egy szolgáltatást nyújt az előző három közül. Öt étteremben adnak reggelit, de nincs vegetáriánus menü. Azok közül az éttermek közül, ahol reggelizhetünk, ötben van felszolgálás. Csak egy olyan étterem van, ahol mindhárom szolgáltatás megtalálható.
a) Hány étteremben lehet vegetáriánus menüt kapni, de reggelit nem?
b) Hány olyan étterem van, ahol felszolgálnak vegetáriánus menüt?
Halmazok, metszet, unió, és egyebek
Van itt egy A halmaz
aminek a komplementere ez. Minden ami körülötte van.
A helyzet akkor válik izgalmasabbá, ha kerítünk az A halmaz mellé
egy B halmazt is.
A halmaz komplementere:
Az a rész, ami mindkettőben benne van az A és B halmazok metszete.
A és B halmazok metszete:
Ez pedig az A és B halmazok uniója.
A és B halmazok uniója:
Ha pedig fogunk egy ollót és szépen kivágjuk az A halmazból azt a részt
ami a B-ben is benne van, nos amit így kapunk az a két halmaz különbsége.
A és B halmazok különbsége:
És most lássuk, mi az a részhalmaz.
A-nak egy részhalmaza például a páros számok halmaza:
Vagy éppen részhalmaza a páratlan számok halmaza is:
És részhalmaza mondjuk a 3-mal osztható számok halmaza is:
Adottak az A és B halmazok:
Határozzuk meg…
a két halmaz metszetét!
a két halmaz unióját!
a B\V-t!
Egy biztosítóhoz az egyik hónapban 24 autós biztosítási kárigény érkezett, és ezek közül
8-an más kárigényt is benyújtottak. Lakásbiztosításra 7 igény érkezett, és egyéb igény 17.
30 olyan ügyfél volt, aki csak egy igényt nyújtott be, 1-1 olyan ügyfél volt, aki a lakáson
kívül még pontosan egy kárigéényt nyújtott be és nem volt olyan, aki mindhármat.
Készítsünk ábrát, és állapítsuk meg, hogy hányan vannak, akik pontosan két kárigényt
nyújtottak be!
Akik pontosan két kárigényt nyújtottak be:
Végül itt jön még egy nagyon érdekes mese bárányokról és számhalmazokról…
Beszélgessünk egy kicsit a számokról.
Ez itt például 3.
Ez pedig 4.
És néha sajnos szükség van negatív számokra is.
Így jutunk el az egész számok halmazáig, amit Z-vel jelölünk.
Aztán fölmerülhet az igény olyan számokra is,
amelyek arányokat fejeznek ki.
Ezeket racionális számoknak nevezzük.
Mondjuk ennek az egyenletnek
a megoldása:
A racionális számokat Q-val jelöljük.
Vannak aztán olyan egyenletek, amiknek
a megoldásai nem racionális számok.
Ilyen például ez az egyenlet:
És így megjelennek az irracionális számok,
amik feltöltik a racionális számok közötti
hézagokat a számegyenesen.
A racionális és az irracionális számok
alkotják együttesen a valós számokat.
Hogyha a számegyenest felszeleteljük részekre…
akkor intervallumokat kapunk.
Ez itt például az 1 és 5 közötti intervallum.
Az 1 és az 5 az intervallum végpontjai.
Olyankor, amikor a végpontok nincsenek benne az intervallumban…
az intervallumot nyílt intervallumnak hívjuk.
NYÍLT INTERVALLUM
Ha mindkét végpont benne van, akkor az a neve, hogy zárt intervallum.
ZÁRT INTERVALLUM
Előfordulhat az is, hogy az intervallum egyik vége nyílt, a másik pedig zárt.
BALRÓL NYÍLT, JOBBRÓL ZÁRT INTERVALLUM:
Az A halmaz
Most pedig nézzük, mi történik, hogyha két intervallumnak vesszük a metszetét…
vagy épp az unióját.
Az intervallumok
Az A halmaz legyen a [2,6] zárt intervallum, a B halmaz pedig az ]1,4[ nyílt intervallum.
Határozzuk meg ezeket:
Úgy tűnik, hogy a 4 nincs benne B-ben…
Így aztán amikor a B halmazt kivonjuk az A halmazból…
akkor a 4-et nem vonjuk ki, az benne marad A-ban.
És ezáltal egy mindkét végén zárt intervallumot kapunk.
Hát, ennyit az intervallumokról.
Próbáljuk meg eldönteni, hogy vajon egyenlő-e ez a két halmaz.
Két halmaz akkor egyenlő, hogyha ugyanazok az elemeik.
Nézzük meg…
Úgy néz ki, egyenlők.
Most lássuk mi a helyzet ezekkel:
Na, itt van egy kis gond.
Ezek az elemek nem ugyanazok.
Azért nem, mert az egyik maga is egy halmaz.
Így aztán C és D nem egyenlők.
Vannak tehát olyan halmazok, aminek az elemei is halmazok.
Mint amilyen például ez:
Ennek a halmaznak három eleme van.
Az egyik eleme egy egyelemű halmaz…
a másik eleme egy kételemű halmaz…
a harmadik eleme egy háromelemű halmaz.
És létezik olyan halmaz is, aminek egyáltalán nincsen eleme…
Ezt a halmazt üreshalmaznak nevezzük.
Az üreshalmaz jele egy ilyen áthúzott nulla.
Van itt egy A halmaz, és soroljuk föl az összes részhalmazát.
Itt jönnek az egyelemű részhalmazok.
Aztán vannak kételemű részhalmazok…
Bármelyik két elemet kiválaszthatjuk…
Így ezekből is három van.
És az egész halmaz is részhalmaznak számít…
De van itt mégvalami.
Az üreshalmaz is A-nak részhalmaza.
Ez így összesen 8 darab részhalmaz:
Hogyha ezeket most betesszük szépen egy újabb halmazba…
Akkor ezt az újabb halmazt az eredeti A halmaz hatványhalmazának nevezzük.
Az A hatványhalmazának 8 eleme van, és maguk az elemek is mind halmazok.
Próbáljuk meg kideríteni, hogy vajon hány elemű halmaz lesz B-nek a hatványhalmaza.
A hatványhalmaz elemei B részhalmazai.
Éppen itt is jönnek...
Az egyik ilyen részhalmaz maga a B…
Hogyha a 8-ast nem tesszük bele…
akkor egy újabb részhalmazt kapunk.
Aztán az is lehet, hogy a 7-est nem tesszük bele…
A 8-ast pedig vagy igen, vagy nem.
Lesz olyan részhalmaz is, amiben a 6-os nincs benne…
A 7-es pedig vagy benne van, vagy nem.
És így szép lassan kirajzolódik az összes lehetőség.
Az eredeti B halmaz minden eleménél két eset van: vagy kiválasztjuk, vagy nem.
Az összes lehetőség így
Az ilyen szorzatoknak van valami speciális neve…
Meg is van, úgy hívják, hogy hatványozás.
A 4 itt nem véletlen…
Ez a B halmaz elemszáma.
Egy H halmaz hatványhalmazának az elemszáma tehát:
Remek, hogy ezt is megtudtuk…
Van itt még egy halmazművelet, ami úgy működik, hogy két halmaz uniójából kivágja…
a metszetüket.
Ezt a műveletet szimmetrikus differenciának nevezzük, és így jelöljük:
Érdemes megjegyezni, hogy
És azt is, hogy
Most pedig lásuk, hogy a szimmetrikus differencia vajon asszociatív-e, tehát igaz-e, hogy:
Az ilyen halmazokkal kapcsolatos állítások igazolására az egyik módszer a rajzolgatás.
Készítünk egy Venn diagramot.
Nézzünk aztán, hogy igaz-e például ez:
Megint jön a Venn diagram.
Hát, ezt most egy kicsit végig kell gondolni.
Ezeknek kell vennünk az unióját…
és aztán kivonjuk a metszetüket.
Hopp, ez éppen a B halmaz.
Ez a Venn diagramos rajzolgatás hatalmas vizuális élményt nyújt.
De már ennél a rövid kis feladatnál is könnyű belezavarodni.
Jobb lenne tehát valamilyen megbízhatóbb módszer.
A megbízhatóbb módszer az lesz, hogy használjuk a halmazműveletekre vonatkozó azonosságokat.
Ennél a konkrét esetnél például azt, hogy a szimmetrikus differencia kommutatív és asszociatív:
Most pedig lássuk, hogy milyen halmazműveleti azonosságok vannak még…
Elérkezett az idő, hogy készítsünk egy listát a halmazokkal kapcsolatos azonosságokról.
Van néhány alap azonosság, mint például ezek itt:
Aztán itt vannak még a De Morgan azonosságok is:
Meg van ez a szimmetrikus differencia…
És most lássunk néhány feladatot. Bizonyítsuk be, hogy
Hogyha nagyon szeretünk rajzolgatni…
Ez itt a B halmaz komplementere…
Ez pedig az uniója az A-val.
Hogyha most még vesszük ennek a metszetét B-vel…
De létezik egy teljesen rajzmentes megoldás is.
Készítünk egy táblázatot, nullákkal és egyesekkel.
Az alaphalmaz minden eleme négy tulajdonság közül pontosan az egyikkel rendelkezik.
Vagy nem eleme sem A-nak, sem B-nek…
vagy A-nak eleme de B-nek nem…
vagy A-nak nem eleme de B-nek igen…
vagy A-nak és B-nek is eleme.
Más lehetőség nincs.
Most pedig szépen kitöltjük a táblázatot.
A komplementer úgy működik, hogy a 0-ból 1-et és az 1-ből 0-t csinál.
Aztán az unió a szokásos…
Olyan elemek vannak benne, amelyek legalább az egyik halmaznak eleme.
Végül vesszük ennek a metszetét B-vel.
Az egyenlőség másik oldalán egy sima A metszet B van.
És most hasonlítsuk össze a sorokat…
Ha mindegyik sor egyezik, akkor egyenlők.
Nézzünk meg egy másikat is. Igazoljuk, hogy fennáll ez az egyenlőség:
Hát, itt rajzolni már nem fogunk…
Jöhet a táblázat.
És most hasonlítsuk össze a sorokat…
Ha mindegyik sor egyezik, akkor egyenlők.
Végül itt jön még egy:
Hát, ez nem néz ki túl jól…
Kezdjük egy kis átalakítással.
Ezek csak olyankor egyenlők, hogyha A és B metszete üres.
És most megpróbálunk választ adni néhány nagyon nyugtalanító kérdésre.
Olyanokra, mint amilyen ez, hogyha A és B halmazokról tudjuk, hogy
akkor vajon igaz-e, hogy
Készítsünk ehhez egy rajzot.
Ezek olyankor egyenlők, hogyha A minden eleme B-ben is benne van…
és B minden eleme A-ban is benne van.
Röviden, ha A=B.
Hogyha A=B, akkor itt mindenhol a B-t lecseréljük…
És hopp, így minden sokkal egyszerűbbé válik.
Úgy néz ki, hogy ez tényleg igaz.
Nézzünk meg még egy ilyet…
Hogyha A és B halmazokról tudjuk, hogy
akkor vajon igaz-e, hogy
Kicsit rajzolgatunk…
Íme, a szimmetrikus differencia.
Ez olyankor lesz B-vel egyenlő, hogyha A nincs is…
Mármint, hogyha A az üreshalmaz.
a \
Bizonyítsuk be, hogy tetszőleges A és B halmazokra teljesül, hogy
Megint jön a szokásos táblázat.
Aztán megyünk szépen tovább.
Az unióban olyan elemek vannak, amelyek legalább az egyik halmaznak eleme.
És így szép lassan kitöltjük a táblázatot.
Most pedig hasonlítsuk össze a sorokat…
X akkor részhalmaza Y-nak…
ha minden elem, ami benne van X-ben, az benne van Y-ban is.
Lássuk, mi a helyzet itt.
.
X-ben csak ilyen típusú elemek vannak.
És ezek mind benne vannak Y-ban is.
A jelek szerint tehát .
Itt jön aztán egy rondább ügy. Igazoljuk, hogy tetszőleges A, B és C halmazokra teljesül, hogy
Megint jön a táblázat…
Adottak a G és H halmazok:
Határozzuk meg a …. és … halmazokat!
Az A halmaz elemei a 28 pozitív osztói, a B halmaz elemei a 49 pozitív osztói.
Adjuk meg az … és … halmazokat elemeik felsorolásával!
28 pozitív osztói: 49 pozitív osztói:
Hány kételemű részhalmaza van a (2, 3, 5, 7, 11) halmaznak?
Egy városban 60 étterem, 56 bár és 36 reggeliző hely üzemel. Olyan, ami étterem és bár is egyben 16 darab van, ami reggelizőként és bárként is üzemel, olyanból 20 darab van, és ami reggeliző és étterem is, olyan 11 darab van. 4 olyan hely van, ami reggelizőként, étteremként és bárként egyszerre működik. Hány olyan bár működik a városban, ami nem étterem és nem reggeliző hely?
Mindig a közös metszettel érdemes kezdeni.
A jelek szerint 24 olyan bár működik a városban, ami nem étterem és nem reggeliző hely.
Van három halmaz, , és pedig a 12 pozitív osztóinak halmaza.
Ábrázoljuk ezeket a halmazokat és adjuk meg elemeinek a felsorolásával az és az halmazokat.
Lássuk, milyen számok vannak a B halmazban.
És itt jön a C halmaz.
Van itt ez a két halmaz.
És vannak olyan helyzetek, amikor szükség lenne arra, hogy összepárosítsuk az elemeiket…
Ezeket a párokat rendezett pároknak nevezzük.
A rendezett párok maguk is halmazok, a pontos definícióhoz pedig itt jön most egy kis unalmas elméleti bűvészkedés.
Az x és y által alkotott rendezett pár egy halmaz.
Ez a halmaz itt:
Az y és x által alkotott rendezett pár pedig egy másik halmaz.
A definíció nagyon ravasz, mert a régóta használt halmaz fogalomra vezeti vissza a rendezett pár fogalmát…
Közben pedig benne van a rendezett párnak az a tulajdonsága is, hogy a két elem sorrendje számít.
És most készítsük el az összes olyan rendezett párt, aminek az első eleme az A halmazból van, a második eleme pedig a B-ből…
Hát, még jó sok van…
A hét minden napjához tartozik 4 lehetőség:
Ez összesen 28 darab rendezett pár.
Na, még írjuk ide az utolsót…
És most a rendezett párokat betesszük szépen egy halmazba…
Ezt a halmazt hívjuk az A és B halmazok Descartes-szorzatának.
Vannak, akik úgy hívják, hogy direkt-szorzat. Ezt könnyebb leírni…
Az A és B halmazok Descartes-szorzata tehát úgy működik, hogy elkészítjük az összes lehetséges rendezett párt, aminek az első elemét A-ból vesszük, a másodikat pedig B-ből.
Hogyha például itt vannak ezek a halmazok…
akkor a Descartes-szorzatuk…
Az A és B halmazok Descartes-szorzatának elemszáma mindig a két halmaz elemszámának a szorzata.
Van itt ez az A halmaz…
És nézzük meg, mi történik akkor, hogyha megszorozzuk önmagával.
Hogyha az A halmazba betesszük még a 4-et is…
Akkor a helyzet már valahogy így néz ki.
Valahonnan mintha már ismerős lenne ez…
Ja meg is van, hogy honnan.
Hogyha az A halmaz éppen a valós számok halmaza, vagyis R…
akkor az RxR Descartes szorzat épp a koordinátarendszert adja.
Most pedig lássuk, mire használhatnánk a Descartes-szorzatot, jóra vagy rosszra…
Ha meg szeretnénk mondani, hogy egy héten milyen lesz az idő…
akkor szükségünk lesz hét darab rendezett párra.
Ezeket a rendezett párokat az A és B halmazok Descartes-szorzatából választjuk ki.
Minden napra csak egy elemet választhatunk.
Ezt jó lenne valahogy megüzenni a meteorológusoknak is…
Hogyha ugyanis mondjuk keddre két elemet is választunk…
na, akkor most esernyőt vigyünk vagy fürdőruhát?
A jó előrejelzés titka az, hogy ugyanarra a napra nem jósol két különböző időjárást…
Vagyis, ha van egy és egy akkor szükségképpen .
Hogyha ez varázslatos dolog teljesül, azt úgy nevezzük, hogy függvény.
Az f halmazt függvénynek nevezzük, ha minden eleme rendezett pár, és ha és akkor szükségképpen .
Ha keddre két elemet is választunk, akkor ez nem függvény.
Hogyha viszont csak egyet, akkor igen.
Ez azt jelenti, hogy a hét minden napjához hozzárendelünk valamilyen időjárást.
És ezzel eljutottunk az általános iskolából ismert függvény-ábrához.
Ez jó jel, ezek szerint, amit általános iskolában tanulunk, annak van értelme.
Rögtön folytatjuk.
Van itt ez a két halmaz…
Hogyha az egyik halmaz elemeihez hozzárendeljük a másik halmaz elemeit…
Akkor kiderül, hogy milyen idő lesz a héten.
Az is megeshet, hogy több nap is ugyanolyan lesz az idő…
Ezzel nincsen semmi baj.
De ha szombathoz például két különböző elemet is rendelünk…
Na, akkor most esernyőt vigyünk vagy fürdőruhát?
Hát igen, ez így nem túl egyértelmű…
Egy hozzárendelést egyértelműnek nevezünk, ha minden elemhez pontosan egy másik elemet rendel hozzá.
Teljesen mindegy, hogy melyiket…
egyedül az a fontos, hogy csak egyet.
Ez a hozzárendelés most egyértelmű.
Az egyértelmű hozzárendeléseket úgy hívjuk, hogy függvény.
Az ilyen egyértelmű hozzárendeléseknek az a neve, hogy függvény.
Adott az és nem üres halmaz.
Ha az A halmaz bizonyos elemeihez egyértelműen hozzárendeljük a B halmaz bizonyos elemeit, akkor ezt a hozzárendelést függvénynek nevezzük.
Simán előfordulhat, hogy az A halmaznak csak néhány eleméhez rendeljük hozzá…
a B halmaznak néhány elemét.
És az sem okoz problémát, ha több elemhez is ugyanazt rendeljük.
Egyedül az lenne baj, ha egy elemhez rendelnénk hozzá több elemet.
ÉRTELMEZÉSI TARTOMÁNY
ÉRTÉKKÉSZLET
Az értelmezési tartomány azoknak az elemeknek a halmaza az A halmazban… amikhez a függvény hozzárendel B halmazbeli elemeket.
Az értékkészlet pedig azoknak az elemeknek a halmaza a B halmazban…
amelyek hozzá vannak rendelve valamely A halmazbeli elemekhez.
Az értelmezési tartományt a domain szó alapján, ami egyébként azt jelenti, hogy tartomány így jelöljük:
De a gyengébb idegzetűek kedvéért szokás úgy is jelölni, hogy É.T.
Az értékkészlet jele pedig a range szó alapján, ami azt jelenti, hogy kiterjedés:
Ennek is van egy akadálymentesített jelölése, ami így szól, hogy É.K.
Egy hozzárendelést kölcsönösen egyértelműnek nevezünk, hogyha nem csak az egyik irányba egyértelmű…
hanem a másik irányba is.
Esetünkben ez most nem mondható el.
Az eső ugyanis pénteken és szombaton is esik.
Így aztán a visszafelé irányban az esőhöz a pénteket és a szombatot is hozzárendeljük.
Talán, ha pénteken sütne egy kicsit a nap…
az minden problémát megoldana.
Ez most egy kölcsönösen egyértelmű hozzárendelés.
És most lássuk, mire is használhatnánk ezeket a függvényeket, jóra vagy rosszra…
Az függvény kölcsönösen egyértelmű, ha akkor .
Vagyis különbözö x-ekhez mindig különböző y-okat rendel.
A kölcsönösen egyértelmű függvények az injektív függvények.
Itt jön aztán egy másik izgalmas tulajdonság is.
Egy függvény szürjektív, hogyha az egész B halmaz előáll képként, vagyis B minden eleme hozzá van rendelva valamelyik A-beli elemhez.
Hát ez most éppen nem mondható el, a napsütés ugyanis kimarad…
Hogyha mondjuk csütörtökön sütne egy kicsit a nap…
Na, az segítene a dolgon.
Ez a függvény így már szürjektív.
És így is szürjektív.
Hogyha ráadásul még injektív is lenne…
Ehhez egy kicsit változatosabb időjárásra lesz szükség…
Akkor ez egy injektív és szürjektív függvény, amit úgy hívunk, hogy bijektív.
Egy vonaton 400-an utaznak. Bizonyítsuk be, hogy utazik rajta két olyan utas, akiknek ugyanazon a napon van a születésnapja.
Hát, ez így elsőre elég furán hangzik…
Mégis honnan kéne tudnunk, hogy kinek mikor van a születésnapja…
De pont ez a lényeg, hogy nem kell tudni.
Itt van például Bob.
És itt van 365 darab doboz, mert egy évben 365 nap van.
Sőt, legyen 366, mert néha szökőév is van.
Azt kell bizonyítani, hogy van két ember ugyanabban a dobozban.
Betesszük Bobot abba a dobozba, amelyik napon született.
Tegyük be, mondjuk ide.
Aztán itt van a következő utas.
Hogyha ugyanazon a napon született, mint Bob…
akkor meg is van a két ember ugyanabban a dobozban.
Ha viszont más napon született…
Hát igen, akkor még nem vagyunk kész.
Itt jönnek sorban az utasok.
Ha mindegyik utas más napon született, mint a többi…
akkor mindegyiket külön-külön dobozban helyezzük el.
Most járunk 366 darab utasnál.
És ekkor megjelenik a 367-edik utas…
Hová is tegyük?
Már nincsen üres doboz, tehát mindegy mikor született…
valakivel így is úgyis közös dobozba kerül.
Egészen biztos, hogy 367 darab utas nem fér el 366 dobozban.
Csak úgy, hogyha valamelyik dobozban ketten vannak.
Ezt a nem túl bonyolult gondolatot hívjuk skatulya-elvnek.
A skatulya a doboz régies elnevezése.
És ezt az elvet elég régen találták ki…
Ha a vonaton 367 ember, vagy ennél több utazik, akkor biztosan lesz két olyan utas, akik ugyanazon a napon születtek.
Most nézzük, mi történik akkor, hogyha fölszáll újabb 333 utas.
Ekkor a vonaton éppen 733-an utaznak.
A 733 pedig egy mágikus szám:
utast még éppen el tudunk úgy helyezni, hogy minden dobozban csak ketten legyenek.
De a plusz egy ember miatt valahol már biztosan hárman lesznek.
Hogyha 733 ember utazik a vonaton, egészen biztosan van köztük 3, akik ugyanazon a napon születtek.
És ha 1200-an utaznak a vonaton…
Ennyi utas már ki sem fér ide.
Szerencsére az ilyen esetekre is van egy matematikai módszer, amit úgy hívunk, hogy indirekt bizonyítás.
Rögtön folytatjuk…
Ha van öt darab labda és négy doboz…
Akkor a labdákat nem tudjuk úgy betenni a dobozokba, hogy mindegyikben csak egy labda legyen.
Valamelyik dobozban biztosan legalább két labda lesz.
Röviden összefoglalva erről szól a skatulya-elv.
Most pedig lássuk, mi ez az indirekt bizonyítás.
Egy 5 kocsiból álló vonaton 460-an utaznak. Bizonyítsuk be, hogy van olyan kocsi, amiben legalább 80 utas van.
Az indirekt bizonyítás lényege, hogy elképzeljük, mi történne, hogyha az állítás nem lenne igaz.
Vagyis tegyük föl, hogy mindegyik kocsiban 80-nál kevesebb utas van.
Ha minden kocsiban 80-nál kevesebb utas van, akkor lássuk csak, 
tehát az egész vonaton 400-nál kevesebben lennének.
De ez lehetetlen, hiszen a vonaton 460-an vannak.
Vagyis lennie kell olyan kocsinak, ahol legalább 80-an vannak.
Egy másik vonat szintén öt kocsiból áll. Legalább hányan utaznak a vonaton, ha tudjuk, hogy biztosan van olyan kocsi, amiben legalább 40-en utaznak?
Hát, ez is valami skatulya-elvnek tűnik…
Csak most valahogy fordítva.
Hogyha mondjuk 100-an utaznak a vonaton, az valószínű kevés, mert simán lehet kocsinként 20 ember.
A 200 már határozottan biztatóbb.
Ha 200-an utaznak a vonaton, akkor biztosan van olyan kocsi, amiben legalább 40-en vannak.
Mert ha nem lenne, tehát minden kocsiban 40-nél kevesebben lennének, akkor az egész vonaton is 200-nál kevesebben lennének.
A 200 utas tehát már elég.
De a kérdés úgy szólt, hogy legalább hányan utaznak a vonaton, és előfordulhat, hogy már 200-nál kevesebb utas is jó lehet.
Ha 195-en utaznak a vonaton, akkor még előfordulhat, hogy minden kocsiban csak 39-en vannak.
De ha 196-an…
Akkor már kell lennie olyan kocsinak, amiben legalább 40-en vannak.
Hiszen, ha minden kocsiba csak 39-en lennének, akkor az egész vonaton is csak 195-en.
Tehát a válasz…
A vonaton legalább 196-an kell, hogy utazzanak.
Az egyik kocsiban egy 10 tagú társaság utazik. Mindenki a társaságból legalább 7 másik embert ismer. Bizonyítsuk be, hogy bármely 3 embernek van közös ismerőse.
Na, ez már egy izgalmasabb ügy.
Megint indirekten bizonyítunk, vagyis tegyük föl, hogy van 3 olyan ember, akiknek nincs közös ismerőse.
Hát, ha nincs közös ismerős, akkor itt bizony csak két ismertség lehet…
Sőt az is lehet, hogy kevesebb…
De az biztos, hogy legfeljebb kettő.
És itt is legfeljebb kettő…
Meg mindenhol.
Ebből a 7 emberből így legfeljebb 14 ismertség indulhat ki.
Mivel a társaságban mindenki legalább 7 másik embert ismer, hogyha embereink egymást ismerik...
akkor is még fejenként legalább 5 ismerősre van szükségük.
Így aztán legalább 15 ismertség indul ki innen.
Ez lehetetlen, mert azok ott heten legfeljebb 14 ismertséggel rendelkeznek.
Tehát ellentmondásra jutottunk.
Nem fordulhat elő, hogy van 3 ember, akinek nincs közös ismerőse.
Vagyis bármely 3 embernek van közös ismerőse.
Most, hogy ezt is megtudtuk, már csak egyetlen nyugtalanító kérdésre keressük a választ.
Arra, hogy mégis mit keres itt ez a rengeteg darázs?
Nem, valójában mégsem ez a kérdés…
Ez túlzottan életszerű lenne.
A kérdés úgy szól, hogy van itt ez a 7x7-es sakktábla és mindegyik mezőn egy darázs.
Egy adott pillanatban minden darázs átmászik valamelyik szomszédos mezőre.
A sarkuknál találkozó mezők nem számítanak szomszédosnak.
Lehetséges-e, hogy ekkor megint mindegyik mezőn pontosan egy darázs álljon?
Tegyük fel, hogy ez lehetséges.
Ez azt jelenti, hogy minden fekete mezőn álló darázsnak át kell másznia egy szomszédos fehér mezőre.
Fekete mezőből 25 darab van, fehérből meg csak 24 darab.
Nem tud a 25 darab fekete mezőn álló darázs átmászni a 24 fehér mezőre, csak úgy, ha lesz olyan mező, amin több darázs is van.
A nagy darázscserélő akció tehát lehetetlen.
A kvantorok. Hogy mik?
Minden ember utálja a matekot…
Azért ez így nem teljesen igaz, itt van ugyanis például Bob.
És Bob szereti a matekot.
Ez az állítás, hogy „Minden ember utálja a matekot.” tehát hamis.
Azért hamis, mert „Van olyan ember, aki szereti”.
Az egészből elég annyit megjegyezni, hogy Bobnak nehéz gyerekkora volt.
Nem, valójában ne ezt jegyezzük meg.
Hanem azt, hogy ez a két állítás egymás tagadása.
Nézzünk erre még egy példát és rögtön minden érthető lesz.
Itt van például ez az állítás:
Minden mamut piros.
Ennek az állításnak a tagadása:
Nem minden mamut piros.
Van olyan mamut, ami nem piros.
Tehát annak a tagadása, hogy „minden”…
így szól, hogy „van olyan, ami nem”.
A matematikában ezek a kifejezések meglehetősen gyakran előfordulnak.
Így aztán külön jelölés van rájuk forgalomban.
Ezt a jelet úgy hívják, hogy univerzális kvantor.
Ezt a másikat pedig úgy, hogy egzisztenciális kvantor.
Ezeknek a jeleknek a segítségével komplett kis titkosírásokat hozhatunk létre.
Ez például azt jelenti, hogy minden x-re létezik olyan y, hogy x+y=1.
A dolog igaznak tűnik, tényleg mindig létezik ilyen y.
Vagy itt van például egy másik:
Ami azt jelenti, hogy létezik olyan x, hogy minden y-ra x+y=1.
Na, ez már sajnos nem igaz.
Nem létezik olyan x szám, ami azt tudná, hogy bármilyen y-t adunk hozzá 1-et kapunk.
De visszatérve egy kicsit a mamutokra…
Van itt ez az állítás:
Minden mamut sárga.
Válasszuk ki innen azokat, amik az állítás tagadása:
Egyik mamut sem sárga.
Van olyan mamut, ami sárga.
Van olyan mamut, ami nem sárga.
A legtöbb mamut nem sárga.
Nem minden mamut sárga.
Hogyha még emlékszünk Bobra…
akkor talán rémlik valami, hogy a „minden” tagadása így szól: „van olyan, ami nem”.
Ez tehát biztosan jó.
Ez a másik pedig csak megtévesztésből van itt…
Hiányzik belőle a „nem” szócska.
Ócska kis trükk…
Aztán nyilván ez is az eredeti állítás tagadása…
Hiszen a mágikus „nem” szócskát őseink éppen a tagadás kifejezésére fejlesztették ki.
Ezek pedig nem tagadásai az eredeti állításnak, csak rá kell nézni itt lent a mamutokra és kiderül.
Próbáljuk meg eldönteni, hogy vajon igaz vagy hamis a következő állítás:
Esik az eső és a mamut piros.
Hát, eléggé hamisnak tűnik.
gy néz ki egyáltalán nem.
A mondat első fele sem igaz…
és a másik fele sem.
Ha mondjuk az eső legalább esne…
Az állítás ettől továbbra is hamis maradna.
Egyetlen egy esetben lenne igaz…
Ha mindkét fele igaz.
Készítsünk ebből egy kis táblázatot.
igaz
hamis
Végülis a mamutokra és az esőre nincs is szükség.
Az „és”-re pedig bevezetünk egy jelölést.
Itt jön aztán egy másik állítás:
Esik az eső vagy a mamut piros.
Készítsünk erről is egy táblázatot.
Hogyha mindkét rész hamis…
akkor az egész állítás is hamis.
Ha a két rész közül valamelyik igaz…
akkor az egész állítás is igaz.
Hogyha pedig mindkét rész igaz…
Ilyen esetekben az emberek hétköznapi logikája nem nagyon tudja értelmezni a „vagy” szócskát.
A matematika viszont igen, és az állítás ebben az esetben is igaz.
A „vagy”-ra is létezik egy matematikai jelölés…
Éppen itt is van.
Egy ősi népi megfigyelés szerint:
Ha esik az eső, akkor a mamut piros.
Nézzük, mikor lesz ez az állítás igaz.
Nos, olyankor, amikor süt a nap…
teljesen mindegy, hogy milyen színű a mamut.
Hiszen csak olyankor kell pirosnak lennie, ha esik.
Ezt az állítást matematikailag így jelöljük:
Olyankor, amikor a kiinduló feltevés hamis, már bármi történhet…
Maga az állítás igaz lesz.
És olyankor is igaz lesz, ha mindkét rész igaz.
Egyetlen egy esetben lesz az állítás hamis.
Amikor esik az eső, de a mamut mégsem piros.
Ezek itt valójában ugyanolyan műveletek, mint az algebrában az összeadás vagy a szorzás.
És ugyanúgy nevük is van.
KONJUNKCIÓ
DISZJUNKCIÓ
IMPLIKÁCIÓ
Vannak aztán még további műveletek is.
Az egyik az ekvivalencia.
Az ekvivalencia jeléből is látszik, hogy ez egy olyan művelet, amikor
Tehát A-ból következik B és B-ből is következik A.
A dolog valójában még ennél is egyszerűbb, az egész azt jelenti, hogy A pontosan akkor igaz, amikor B.
Ezek a műveletek mind kétváltozós műveletek, vagyis kell hozzá egy A és egy B is.
Itt jön aztán egy olyan logikai művelet is, ami egyváltozós.
Ez a művelet a tagadás, vagyis a „nem A”.
Olyan, mint az algebrában az ellentett…
A művelet neve negáció.
Jók ezek a táblázatok, csak hát rémesen sok helyet foglalnak.
Kénytelenek leszünk egy kicsit egyszerűsíteni őket:
Na, így már sokkal jobb.
Most nézzünk egy izgalmas feladványt, ami azt tesztelte, hogy a hétköznapi emberek mennyire fogékonyak a matematikai logika iránt.
A teszt során az derült ki, hogy nem különösebben…
De lássuk a feladványt.
Van itt ez a négy darab kártya. Az egyik oldalán mindegyiknek egy szám áll, a másik oldalon pedig egy betű.
És van itt ez az állítás:
Ha a kártya egyik oldalán magánhangzó van, akkor a másik oldalán páros szám áll.
A kérdés az, legfeljebb hány kártyát kell megfordítanunk ahhoz, hogy kiderüljön igaz-e az állítás?
A tipikus rossz válaszokat bárki megtudhatja, hogyha elmondja ezt a kis feladványt ismerőseinek…
És most lássuk a jó választ.
Ez az állítás tulajdonképpen mindig igaz, kivéve egyetlen esetben.
Egyedül az okozza a bajt, amikor A igaz, de B hamis.
Ez megtörténhet itt, ha a túloldalon páratlan szám van…
És itt, ha a másik oldalon magánhangzó van.
A többi esetben vagy eleve A hamis, és akkor már mindegy…
vagy B igaz és akkor is mindegy.
Ezt a két kártyát kell tehát megfordítani.
Itt jön néhány állítás, és fogalmazzuk meg ezek tagadását.
Az ég kék és a fű zöld.
Az állítás tagadásának a táblázata úgy kell, hogy kinézzen…
hogy itt mindenhol 0 helyett 1 és 1 helyett pedig 0 van.
Hát, ilyen éppen van…
Csak A-t és B-t is tagadni kellene.
Ha esetleg elsőre ez kicsit zavarosnak tűnik, az teljesen normális...
Nézzük meg szépen lépésről lépésre, és minden ki fog derülni.
Az állítás tagadásában tehát „vagy”-nak kell lennie…
És úgy fog stimmelni a táblázat, ha külön-külön A-t és B-t is tagadjuk.
Valahogy így:
Az ég nem kék vagy a fű nem zöld.
Lássuk a táblázatot.
Úgy tűnik ez meg is van.
A táblázat utolsó oszlopában minden épp a fordítottja lett annak, ami eredetileg volt.
Ez tehát valóban az eredeti állítás tagadása.
Végül nézzünk meg még egyet.
Ha az ég kék, akkor a fű zöld.
Megint megnézzük a táblázatot…
és keresünk egy ezzel ellentéteset.
Ami itt 0 volt…
az ebben 1.
Most hasonlítsuk össze ezt a két sort.
Csak a B-nél van változás, így most csak a B-t kell tagadni.
Az eredeti állítás tagadásában tehát „és” fog szerepelni és 
.
Az ég kék és a fű nem zöld.
Az utolsó oszlop épp a fordítottja annak, mint ami eredetileg volt.
Ez tehát az állítás tagadása.
Most pedig őrülten izgalmas dolgokat fogunk csinálni.
Elkészítjük néhány állítás igazságtáblázatát.
Épp itt is van az első:
edu10
Hát, ez kész is.
És ami azt illeti, élénken emlékeztet az A vagy B tagadására.
Sőt ez maga az A vagy B tagadása.
Hogyha most elkészítenénk az igazságtáblázatát…
akkor az derülne ki, hogy az pedig A és B tagadása.
Lássuk aztán, mi a helyzet ezzel:
Már jön is az igazságtáblázat…
A jelek szerint ez éppen az tagadása.
Az ekvivalencia tagadása pedig ez volna…
Most pedig lássuk, mi a tagadása ennek a nagyon egyszerű mondatnak:
Ha az ég kék, akkor a fű zöld és a mamut piros.
Beazonosítjuk a szereplőket.
És íme, az állítás:
Ez pedig a tagadása…
Hát ez megvolna.
Az ég kék, és a fű nem zöld vagy a mamut nem piros.
Végül vannak itt ezek az állítások:
És készítsük el az igazságtáblázatukat.
Ez a táblázat élénken emlékeztet az ekvivalencia igazságtáblázatára…
Annyira emlékeztet, hogy az is.
A jelek szerint ez éppen A.
Ez leginkább erre emlékeztet…
Egy kis módosítással.
Csodás.
Van itt ez a két láda. Az egyikben arany van, a másik üres, a ládákon lévő feliratok pedig lehetnek igazak vagy hamisak is.
Anélkül, hogy hozzáérnénk a ládákhoz, meg tudjuk-e mondani, hogy melyikben van az arany?
Ha a másik ládában van az arany, akkor mindkét ládán hamis felirat van.
Az arany nem ebben a ládában van.
Kezdjük az első ládán szereplő felirattal.
Ez a felirat csak abban az esetben hamis…
ha az arany a másik ládában van…
és nem mindkét ládán van hamis felirat.
Mivel ez a felirat hamis, így a másik ládán lévőnek kell igaznak lennie.
De ez lehetetlen, hiszen az arany abban a ládában van.
Az első ládán lévő felirat tehát nem lehet hamis.
Lássuk, mi van akkor, ha az első ládán a felirat igaz.
Ha az arany mégis a másik ládában van…
akkor ennek a résznek is igaznak kéne lennie.
De ez lehetetlen.
Csak úgy lehet az első ládán igaz felirat, hogy az állítás első fele hamis.
És ekkor a másik láda üres ugyan, de a rajta lévő felirat igaz.
Ezúttal már három láda van. Az egyikben arany van, a másik kettő üres, a ládákon lévő feliratok pedig lehetnek igazak vagy hamisak is.
Anélkül, hogy hozzáérnénk a ládákhoz, meg tudjuk-e mondani, hogy melyikben van az arany?
A második ládán a felirat igaz.
Az arany ebben a ládában van és az első ládán a felirat hamis.
Az arany olyan ládában van, amin a felirat hamis.
Az első két láda felirata egy kicsit ellentmond egymásnak.
Az első ládán a felirat biztosan nem lehet igaz.
Így aztán a második ládán is hamis felirat van.
De ennek a második fele igaz…
tehát az első felének mindenképp hamisnak kell lennie.
Most nézzük a harmadik ládát.
Ha ez a felirat hamis, akkor az aranynak olyan ládában kell lennie, amin a felirat igaz.
Csakhogy nincs ilyen láda, mert ebben az esetben mindegyik felirat hamis.
A harmadik láda felirata csak igaz lehet.
És az arany nem lehet ebben a ládában.
Az arany az első ládában van.
Hát, ennyit a ládákról. Most pedig tegyünk egy kört a lovagok és lókötők szigetén.
Ezen a szigeten kétféle ember él, akik külsejük alapján teljesen egyformák.
Csak éppen a lovagok mindig igazat mondanak, a lókötők pedig mindig hazudnak.
Találkozunk két szigetlakóval.
X azt mondja:
Ha Y lovag, akkor én lókötő vagyok.
Y nem mond semmit.
Milyen típusú X és Y?
Kezdjük azzal, hogy mi van akkor, ha X hazudik.
Ez csak úgy lehetséges, ha Y lovag…
és X is lovag.
De ez lehetetlen, hiszen akkor X nem hazudhat.
X-nek mindenképpen igazat kell mondania.
X tehát lovag.
És Y nem lehet lovag…
mert akkor X-nek lókötőnek kéne lennie.
Vagyis Y lókötő.
Egy másik alkalommal három szigetlakóval találkozunk, akik ezt mondják:
X: Y lókötő és Z lovag.
Y: Lókötő vagyok és Z lovag.
Milyen típusú X, Y és Z?
Kezdjük azzal, hogy lovag ilyet nem mondhat…
Y tehát biztosan lókötő, mivel pedig az állítás első fele igaz…
a második felének mindenképpen hamisnak kell lennie.
Eddig tehát ott tartunk, hogy Y és Z is lókötő.
Ez azt jelenti, hogy X hazudik.
Így aztán X is lókötő.
Egy újabb esetben ismét három szigetlakóval találkozunk, akik ezt mondják:
Kezdjük azzal a lehetőséggel, hogy Y hazudik.
Ekkor annak a résznek is hazugságnak kell lenni, hogy lókötő vagyok.
De az a rész éppen igaz, ez tehát ellentmondás.
Y csak lovag lehet, és így ez a rész biztosan igaz.
És a jelek szerint X is igazat mond.
Vagyis mindhárman lovagok.
Végül egy újabb esetben ismét három szigetlakóval találkozunk, akik ezt mondják:
Ha X igazat mond és Y lovag…
akkor X-nek lókötőnek kéne lennie.
Ez ellentmondás.
X tehát hazudik, így X és Y is lókötő.
Hogyha Y lókötő, akkor neki is hazudnia kell, de mivel az állítás első fele igaz…
a második fele nem lehet igaz.
Tehát Z-nek lókötőnek kell lennie.
Van itt ez az állítás:
Az áldozat a szobában van, és ha nem találják meg, akkor holnap is ott lesz.
Lássuk, mi lesz ennek a tagadása.
Ehhez egy kicsit formalizáljuk:
A tagadás pedig a mi kis képleteink segítségével…
Ez valahogy így szól, hogy:
Az áldozat nincs a szobában, vagy nem találják meg és holnap nem lesz ott.
Ezeket a képleteket De Morgan azonosságoknak hívják.
Voltak már ilyenek a halmazoknál is…
De ezek most a logikai De Morgan azonosságok.
Azon kívül, hogy segítenek nekünk leírni egy állítás tagadását még rengeteg mágikus dolgot tudnak.
Nézzük meg például ezt:
Ha most ezt újra tagadjuk…
A dupla tagadás éppen kiejti egymást.
Itt pedig használhatjuk ezt.
És ezzel egy „Ha akkor” típusú állítást le tudtunk írni egy tagadás és egy „vagy” segítségével.
Ezzel az új kis képletünkkel az eredeti állítás egész jól átalakítható…
Az állítás pedig így szól…
Az áldozat a szobában van, és megtalálják vagy holnap is ott lesz.
De nem csak a „Ha akkor” típusú állításokat tudjuk lecserélni…
A De Morgan azonosságokkal ugyanis képesek vagyunk az „és”-t átalakítani „vagy”-ra és fordítva.
Nézzük meg például, hogyan nézne ki egy olyan világ, amiben csak tagadás meg „vagy” létezik:
Itt túl sok dolgunk nincsen…
És az ekvivalencia…
Na, itt még szükség van egy kis trükkre.
Az ekvivalencia azt jelenti, hogy A és B is egyszerre igaz…
vagy egyszerre hamis.
Ezzel fogjuk folytatni.
Egy ügyes kis trükk segítségével minden kifejezés feldarabolható teljesen különálló részekre.
Itt van például az ekvivalencia, ami azt jelenti, hogy A és B is egyszerre igaz…
vagy egyszerre hamis.
Az implikációnál pedig…
Vagy A és B is egyszerre igaz…
vagy A hamis és B igaz…
vagy A hamis és B is hamis.
A „vagy”-gyal elválasztott részek csak tagadást meg „és”-t tartalmaznak, így mindegyik ilyen rész pontosan egyféleképpen lehet igaz.
Az eredeti kifejezésnek ezt a felírását úgy hívjuk, hogy teljes diszjunktív normálforma.
Nézzük meg, hogy mi lesz például a teljes diszjunktív normálformája ennek:
Azzal kezdjük, hogy elkészítjük a szokásos igazságtáblázatot.
Aztán kiválogatjuk azokat az eseteket, amikor az egész kifejezés igaz.
Ezeket felírjuk szépen egymás után…
És hopp, már kész is a teljes diszjunkt normálforma.
Minden nem azonosan hamis kifejezésnek van teljes diszjunktív normálformája.
És éppen így kell elkészíteni, ahogy az előbb csináltuk.
Nézzük, mi lesz a teljes diszjunktív normálformája ennek itt:
Na, itt túl sok dolgunk nem lesz…
Lássunk még egyet.
Pompás.
Teljes
diszjunktív
normálformák
