4. A matematikai logika elemei. Szükséges és elégséges feltételek

Állítások, kvantorok és logikai műveletek

Definíció: A matematikai logikában állításnak (kijelentésnek) nevezünk minden olyan kijelentő mondatot, amelyről egyértelműen eldönthető, hogy igaz (I, vagy 1) vagy hamis (H, vagy 0), de a kettő közül egyszerre csak az egyik. Az állításokat általában nagybetűkkel ($A, B, C...$) jelöljük.

A matematikában gyakran használunk kvantorokat az állítások megfogalmazásakor:

Univerzális kvantor ($\forall$): Jelentése: "minden", "bármely". (Pl.: $\forall x \in \mathbb{R} : x^2 \ge 0$).
Egzisztenciális kvantor ($\exists$): Jelentése: "létezik", "van olyan". (Pl.: $\exists x \in \mathbb{R} : x^3 = -8$).

Alapvető logikai műveletek

Elemi állításokból logikai kötőszavakkal összetett állításokat hozhatunk létre:

Tagadás (Negáció, $\neg A$): Akkor és csak akkor igaz, ha az $A$ állítás hamis.
Konjunkció (És, $A \land B$): Pontosan akkor igaz, ha mindkét állítás igaz.
Diszjunkció (Megengedő vagy, $A \lor B$): Akkor igaz, ha legalább az egyik állítás igaz.
Implikáció (Ha-akkor, $A \Rightarrow B$): Csak akkor hamis, ha az előtag ($A$) igaz, de az utótag ($B$) hamis. (Minden más esetben igaz, még akkor is, ha $A$ hamis!).
Ekvivalencia (Akkor és csak akkor, $A \Leftrightarrow B$): Pontosan akkor igaz, ha $A$ és $B$ logikai értéke megegyezik (mindkettő igaz, vagy mindkettő hamis).

Szükséges és elégséges feltételek, Állítás megfordítása

A matematikai tételek jelentős része implikáció ($A \Rightarrow B$) alakban fogalmazható meg. Például: "Ha egy szám osztható 4-gyel ($A$), akkor osztható 2-vel is ($B$)." Ezt a kapcsolatot többféleképpen is kifejezhetjük a szükséges és elégséges szavakkal:

Elégséges feltétel: Az $A$ állítás elégséges feltétele $B$-nek. (Ha 4-gyel osztható, az bőven elég ahhoz, hogy tudjuk: páros).
Szükséges feltétel: A $B$ állítás szükséges feltétele $A$-nak. (Ahhoz, hogy egy szám 4-gyel osztható lehessen, feltétlenül szükséges, hogy 2-vel osztható legyen).

Az állítás megfordítása

Egy $A \Rightarrow B$ állítás megfordítása a $B \Rightarrow A$ állítás. Kritikus fontosságú: Egy igaz állítás megfordítása nem feltétlenül igaz!
Példa az előzőre: "Ha egy szám osztható 2-vel, akkor osztható 4-gyel." – Ez hamis (pl. a 6).

Ha egy állítás ($A \Rightarrow B$) ÉS annak megfordítása ($B \Rightarrow A$) is igaz, akkor a két állítás logikailag ekvivalens ($A \Leftrightarrow B$). Ilyenkor azt mondjuk, hogy $A$ a $B$-nek szükséges és elégséges feltétele (és fordítva). A tételekben ezt az "akkor és csak akkor" szófordulattal fejezzük ki.

Bizonyítási módszerek a matematikában

A szóbeli vizsgán [cite: 80] emelt szinten ismerni kell az alábbi bizonyítási típusokat, és példát kell tudni mondani rájuk:

Direkt bizonyítás: Készen kapott, már igazolt tételekből, axiómákból, definíciókból logikai következtetések láncolatán keresztül jutunk el a bizonyítandó állításig. (Példa: A másodfokú egyenlet megoldóképletének levezetése teljes négyzetté alakítással).
Indirekt bizonyítás (Ellentmondásra vezetés): Feltételezzük a bizonyítandó állítás tagadásának igazságát. Ebből a feltételezésből helyes logikai lépésekkel haladunk, amíg ellentmondásra nem jutunk egy már ismert ténnyel (axiómával, a feladat feltételeivel stb.). Ebből következik, hogy az eredeti feltételezésünk (a tagadás) hamis volt, tehát az eredeti állítás igaz.
Teljes indukció: Természetes számokra ($\mathbb{N}$) vonatkozó állítások bizonyítására szolgál. Két lépésből áll:
1. Bebizonyítjuk az állítást az első (legkisebb) lehetséges számra (általában $n=1$ vagy $n=0$).
2. Feltételezzük, hogy az állítás igaz $n=k$-ra (indukciós feltevés), majd ennek felhasználásával bebizonyítjuk, hogy igaz a következő, $n=k+1$ számra is. Ezzel dominóelv-szerűen végtelen sok esetre bizonyítunk. (Példa: Számtani sorozat összegképletének igazolása).
Skatulyaelv (Dirichlet-elv): Ha $n+1$ darab (vagy több) tárgyat $n$ darab skatulyába (dobozba) helyezünk el, akkor biztosan lesz legalább egy olyan skatulya, amelyikbe legalább két tárgy kerül. (Példa: Biztosan van Budapesten két ember, akinek hajszálra megegyezik a hajszálainak száma).

Tétel és Bizonyítás (Indirekt módszerrel)

Az indirekt bizonyítás klasszikus és az emelt szintű érettségin [cite: 82] kifejezetten elvárt példája a $\sqrt{2}$ irracionalitásának igazolása.

Tétel: A $\sqrt{2}$ irracionális szám ($\sqrt{2} \notin \mathbb{Q}$)

Bizonyítás (Indirekt úton):

Feltételezzük az állítás ellenkezőjét: tegyük fel, hogy a $\sqrt{2}$ racionális szám. Ha racionális, akkor felírható két egész szám hányadosaként (törtként). A törtet egyszerűsítsük le egészen addig, amíg a számláló és a nevező relatív prímek nem lesznek (legnagyobb közös osztójuk 1).

$$ \sqrt{2} = \frac{p}{q} $$

Ahol $p, q \in \mathbb{Z}$, $q \neq 0$, és $(p, q) = 1$ (relatív prímek).

Emeljük mindkét oldalt négyzetre:

$$ 2 = \frac{p^2}{q^2} $$

Szorozzunk be $q^2$-tel:

$$ 2q^2 = p^2 $$

A bal oldal a 2-es szorzó miatt biztosan páros egész szám. Ebből következik, hogy a jobb oldalnak, vagyis $p^2$-nek is párosnak kell lennie. Ha egy négyzetszám páros, akkor maga a szám ($p$) is páros. Tehát felírhatjuk $p$-t a következő alakban: $p = 2k$ (ahol $k \in \mathbb{Z}$).

Helyettesítsük ezt be az előző egyenletbe $p$ helyére:

$$ 2q^2 = (2k)^2 $$ $$ 2q^2 = 4k^2 $$

Osztva 2-vel kapjuk:

$$ q^2 = 2k^2 $$

Ebből az egyenletből pedig az látszik, hogy $q^2$ is páros szám, ami azt jelenti, hogy $q$ is páros. Tehát $p$ és $q$ is páros számok. Ez azonban ellentmondás (abszurdum), hiszen a kiinduláskor kikötöttük, hogy $p$ és $q$ relatív prímek (nem lehetnek mindketten párosak, mert akkor 2-vel lehetne egyszerűsíteni a törtet).

Mivel a helyes logikai lépések során ellentmondásra jutottunk, az eredeti feltételezésünk volt hibás. Ezzel bizonyítottuk, hogy a $\sqrt{2}$ nem írható fel két egész szám hányadosaként, azaz irracionális. Q.E.D.

Alkalmazások és Matematikatörténet

A szóbeli felelet lezárásaként (a pontozási útmutató alapján) [cite: 250] érdemes rávilágítani a téma tudománytörténeti és gyakorlati fontosságára.

Matematikatörténet:

A formális logika alapjait az ókori görög filozófus, Arisztotelész fektette le a szillogizmusok elméletével (például: "Minden ember halandó. Szókratész ember. Tehát Szókratész halandó.").
A modern, szimbólumokkal operáló matematikai logikát a 19. században George Boole angol matematikus alkotta meg (róla kapta a nevét a Boole-algebra), aki a logikai kijelentéseket algebrai egyenletekké formálta (1-es és 0-s értékekkel).
A bizonyításban szereplő $\sqrt{2}$ irracionalitását feltételezések szerint Püthagorasz egyik tanítványa, a metapontumi Hippaszosz fedezte fel. A legenda szerint a felfedezést a püthagoreusok (akik hittek abban, hogy a világon minden kifejezhető egész számok arányaként) akkora eretnekségnek tartották, hogy Hippaszoszt a tengerbe dobták érte.

Gyakorlati alkalmazások:

Informatika és hardvertervezés: A mai számítógépek működése teljes egészében a Boole-algebrán alapul. A processzorok tranzisztorai logikai kapukat (AND, OR, NOT, XOR) alkotnak. Két szám összeadását például a processzor kizáró vagy (XOR) és logikai és (AND) kapuk megfelelő hálózatba (félösszeadó, teljes összeadó) kötésével végzi el.
Programozás: A szoftverfejlesztés alapkövei a logikai feltételek. Az "if-else" (ha-akkor-különben) szerkezetek, a "while" (amíg) ciklusok kilépési feltételei mind logikai állítások, amelyeket gyakran De Morgan-azonosságokkal kell egyszerűsíteni az optimális és átlátható kód érdekében.
Jogi és szerződéses nyelv: A jogszabályok, biztosítási kötvények értelmezésében elengedhetetlen a "szükséges és elégséges" feltételek, az "és/vagy" kötőszavak hajszálpontos logikai elkülönítése a kiskapuk és félreértelmezések elkerülése végett.