Tartalomjegyzék
Matematikai logika
A matematikai logika a matematika egyik fejezete, mely a matematikai rendszereket, bizonyításokat vizsgálja, pontosabban ezek számára nyújt alapot: következtetési sémákat, szabályokat, definíciókat ad.
A naív halmazelmélet paradoxonainak felfedezése késztette a matematikusokat (ld. David Hilbert programja) arra, hogy a matematika minden területét axiómarendszerekre alapozzák, majd ezekből helyes következtetések sorával vezessék le az egyes állításokat. Ehhez a bizonyítások formalizálására volt szükség (formális nyelvek).
A matematikai logika a kétértékű logikára épül. Másképp fogalmazva az {igaz, hamis} logikai halmaz és a rajta értelmezett logikai függvények, műveletek világában mozog.
Kijelentés
A kijelentés (ítélet vagy állítás) olyan jól meghatározott dologra vonatkozó kijelentő mondat, amely vagy igaz, vagy hamis, de nem lehet egyidőben igaz is és hamis is (ellentmondástalanság törvénye), illetve nem lehet ezektől különböző érték sem (kizárt harmadik törvénye). A matematikai logika ezen ágát ezért nevezzük kétértékű logikának.
Jelölés: p, q, r, …, x, y, z, …, ezeket kijelentésváltozóknak nevezzük.
A kijelentés logikai értéke igaz, vagy hamis lehet, de gyakran ezek helyett az 1 (i - igaz), illetve 0 (h - hamis) jeleket használjuk. A p kijelentés logikai értékét |p| jelöli.
Néhány megjegyzés:
- A kijelentés és a kijelentés logikai értéke fenti megadása nem matematikai definíció
- Annak eldöntése, hogy egy kijelentő mondat kijelentés-e, és hogy ez esetben mi a logikai értéke, nem a logika feladata. Ez konkrét tapasztalattal, vagy valamely szaktudomány eredményeivel dönthető el, vagy bizonyos esetekben megállapodás kérdése.
- A kijelentésekre vonatkozó alapvető törvényeket (ellentmondástalanság, illetve kizárt harmadik törvénye) Arisztotelész görög filozófus fogalmazta meg.
- Léteznek az un. többértékű logikák is, ezekkel mi nem foglalkozunk.
Logikai műveletek
Kijelentésekből logikai műveletek segítségével újabb összetett kijelentéseket rakhatunk össze. A logikai műveletek tulajdonképpen egy- vagy többváltozós logikai (az {igaz, hamis} halmazon értelmezett) függvények.
Könnyen belátható, hogy négy egyváltozós (konstans hamis, konstans igaz, identitás, negáció) és 16 kétváltozós logikai művelet van. Ezek közül néhányat gyakran használunk, külön névvel és jelöléssel látjuk el.
Negáció
A p kijelentés negációja (tagadása) a „nem p” kijelentés, ami igaz, ha p hamis, és hamis, ha p igaz.
Jelölés: , vagy ¬p
Megjegyzés: || = 1 + |p| (mod 2)
Konjunkció
Konjunkció vagy logikai „és” művelet. A p és q kijelentések konjunkciója a „p és q” kijelentés, mely akkor, és csak akkor igaz, ha p és q is igaz.
Jelölés:
Megjegyzés: || = |p||q| (mod 2)
Diszjunkció
Diszjunkció vagy logikai „vagy” művelet. A p és q kijelentések diszjunkciója a „p vagy q” kijelentés, mely akkor, és csak akkor igaz, ha p és q közül legalább az egyik igaz. (azaz akkor, és csak akkor hamis, ha p és q is hamis.)
Jelölés:
Megjegyzés: || = |p| + |q| + |p||q| (mod 2)
Implikáció
Implikáció vagy következtetés. A p és q kijelentések implikációja a „p-ből következik q” kijelentés, mely pontosan akkor hamis, ha p igaz és q hamis.
Olvashatjuk így is: „ha p, akkor q”, „p elégséges feltétele q-nak”
Jelölés:
Megjegyzés: || = 1 + |p| + |p||q| (mod 2)
Ekvivalencia
Ekvivalencia vagy egyenértékűség. A p és q kijelentések ekvivalenciája a „p egyenértékű q-val” kijelentés, mely pontosan akkor igaz, ha p és q egyszerre igaz, vagy hamis, tehát |p|=|q|, és hamis, ha p és q különböző értékű (egyik igaz, másik hamis).
Olvashatjuk így is: „p akkor, és csak akkor, ha q”, „p szükséges és elégséges feltétele q-nak”.
Jelölés:
Megjegyzés: || = |p| + |q| + 1 (mod 2)
Antivalencia
Antivalencia, kizáró vagy, XOR, Birkhoff-féle művelet. A p és q kijelentések antivalenciája a „p kizárja q-t” kijelentés, mely akkor igaz, ha p és q közül pontosan az egyik igaz.
Jelölés: p ∇ q
Scheffer-féle művelet
Összeférhetetlenséget kifejező diszjunkció, Scheffer-művelet, összeférhetetlenség, NAND. A p és q kijelentések összeférhetetlensége a „p összeférhetetlen q-val” kijelentés, ami akkor és csak akkor igaz, ha p és q közül legfeljebb az egyik igaz.
Jelölés:
Web-féle művelet
Sem-sem művelet, Web-féle művelet, NOR. A p és q kijelentések „sem-sem” kapcsolata a „sem p, sem q” kijelentés, ami akkor és csak akkor igaz, ha p és q közül egyik sem igaz.
Jelölés:
Bool algebra
Az igazságértékek {igaz, hamis} halmaza a logikai és (, vagy () valamint negáció műveletekkel Bool algebrát alkot.
Műveleti tulajdonságok
Az alábbi műveleti szabályok könnyen bizonyíthatók egyszerű ellenőrzéssel (egy változó esetén két esetet, két változó esetén négy esetet kell ellenőriznünk), igazság-táblázattal.
Kettős tagadás elve
Ha p kijelentés, akkor .
Asszociativitás
A diszjunkció és a konjunkció asszociatív művelet, azaz ha p, q és r tetszőleges kijelentés, akkor: , illetve .
Kommutativitás
A diszjunkció és a konjunkció kommutatív művelet, azaz ha p, és q tetszőleges kijelentés, akkor: , illetve .
Abszorbció
A diszjunkció és a konjunkció abszorbtív művelet egymásra nézve, azaz ha p, és q tetszőleges kijelentés, akkor: , illetve .
Idempotencia
A diszjunkció és a konjunkció idempotens művelet, azaz ha p tetszőleges kijelentés, akkor: , illetve .
Disztributivitás
A diszjunkció és a konjunkció disztributív művelet egymásra nézve, azaz ha p, q és r tetszőleges kijelentés, akkor: , illetve .
de Morgan azonosságok
, illetve
A negáció tulajdonságai
Ekvivalencia és implikáció
Kijelentéslogikai formulák
A kijelentéslogikai formulákban a következő szimbólumokat használhatjuk:
- kijelentésváltozók jelei: p, q, r…
- logikai műveletek jelei:
- zárójelpárok: (, )
Ezek után definiálhatjuk a kijelentéslogikai formula fogalmát:
- A kijelentésváltozók formulák.
- Ha A és B formulák, akkor is formula.
- Minden formula előáll véges sok lépésben az (1) és (2) segítségével.
Helyettesítés
Helyettesítésről beszélünk, ha egy A formulában valamely p kijelentésváltozó vagy R részformula helyére egy C formulát írunk.
Szöveges interpretáció
Különböző kijelentéseknek lehet azonos szerkezete. Egy-egy ilyen kijelentést a szerkezetet leíró formula szöveges interpretációjának nevezzük.
Például a következő kijelentések a formula szöveges interpretációi:
- „Ha TV-t nézek vagy strandolok, akkor nem dolgozom.”
- „Ha egy szám osztható 4-gyel, vagy 6-tal, akkor nem páratlan.”
Formula interpretációi
Ha egy formulában megadjuk a kijeletésváltozók logikai értékét, akkor ezt a formula egy interpretációjának nevezzük.
Egy n változós formulának 2n interpretációja van.
Ha egy formulát minden interpretációja igazzá tesz, akkor azt azonosan igaz formulának vagy tautológiának nevezzük. Az A formula azonosan hamis vagy kontradikció, ha minden interpretációja hamissá teszi. Ha egy formulának van olyan interpretációja, ami igazzá teszi, akkor kielégíthetőnek nevezzük, ellenkező esetben kielégíthetetlennek.
A pontosan akkor tautológia, ha negáltja kontradikció.
Kijelentéslogikai formulák ekvivalenciája
Az A és B formulák egyenértékűek vagy ekvivalensek, ha A ↔ B tautológia, azaz az A-ban és B-ben szereplő összes kijelentésváltozó minden interpretációjára |A| = |B|. Ezt sokszor úgy mondjuk, hogy:
- „A szükséges és elégséges feltétele B-nek”
- „A akkor és csak akkor, ha B”
- „A pontosan akkor, ha B”
- „A és B ekvivalensek”
Jelölés: A ⇔ B
A formulák körében értelmezett ⇔ ekvivalencia reláció, azaz
- reflexív (A ⇔ A)
- szimmetrikus (A ⇔ B, akkor B ⇔ A)
- tranzitív (A ⇔ B, B ⇔ C, akkor A ⇔ C)
Megjegyzés: Az „A egyenértékű B-vel” (⇔) tehát egy a formulák halmazán értelmezett reláció, míg az implikáció (↔) egy kijelentéslogikai művelet, mely kijelentésekből, vagy formulákból újabb kijelentést, illetve formulát állít elő.
Ha logikailag ekvivalens formulákban a kijelentésváltozókat tetszőleges formulákkal helyettesítjük, akkor ismét logikailag ekvivalens formulákhoz jutunk.
Kijelentéslogikai következtetések
A logikai következtetés egy vagy több feltételből, más néven premisszából, és egy állításból (következmény, vagy konklúzió) áll.
Abban az esetben, ha egy premissza van, akkor azt mondjuk, hogy A formulából következik B, ha A → B tautológia. Jelölés: A ⊨ B, esetleg A ⇒ B
A kijelentéslogikai formulák körében értelmezett ⊨ reláció
- reflexív
- tranzitív
- nem szimmetrikus (A ⊨ B esetén általában nem következik, hogy B ⊨ A)
- A ⊨ B és B ⊨ A, akkor A ⇔ B
Következtetési sémák
- Leválasztási szabály (modus ponens): A → B, A ⊨ B
- Indirekt bizonyítás (modus tollens): A → B, ¬B ⊨ ¬A
- Lehetetlenre való visszavezetés (redukció ad abszurdum): A → B, A → ¬B ⊨ ¬A
- Kontrapozíció: A → B ⊨ ¬B → ¬A
- Diszjunktív szillogizmus (modus tollendo ponens): A B, ¬B ⊨ A
- Láncszabály (feltételes szillogizmus): A → B, B → C ⊨ A → C
Levezetések
Kijelentésloggikai levezetésnek, vagy dedukciónak nevezzük következtetési szabályok olyan rendszerét, melynek alapján eldöntehető, hogy teljesül-e az A1, …, An ⊨ B.
Pontosabban: Legyenek A1, …, An, B (n0) adott kijelentéslogikai formulák és legyen T tautológiák egy halmaza. Az E1, E2, …, Ek formulasorozatot a B formulának az A1, …, An premisszákból a T segítségével történő levezetésének nevezzük, ha
- Ek = B
- minden esetén
- Ei egy premissza, vagy
- Ei valamely T-beli tautilógiából helyettesítéssel keletkezik, vagy
- vannak az E1, E2, …, Ek sorozatban az Ei-t megelőző formulák, hogy egy T-beli tautológiából helyettesítéssel áll elő.
Belátható (teljes indukcióval), hogy ha B kijelentéslogikai formula levezethető A1,…,An premisszákból T segítségével, akkor A1, …, An ⊨ B, tehát B következménye A1, …, An-nek.
G. Frege (német matematikus) bizonyította, hogy megadható tautológiák olyan T halmaza, hogy tetszőleges formulák esetén, ha A1, …, An ⊨ B, akkor B levezethető az A1, …, An premisszákból T segítségével.
J. Lukasiewicz (lengyel matematikus) adott meg egy ilyen, alkalmas T halmazt:
- A → (B → A)
- (A → (B → C)) → ( (A →B) → (A → C))
- (¬B → ¬A) → (A → B)
- A, A → B ⇒ B (Modus Ponens)
Normálformák
A normálformák olyan szerepet töltenek be a kijelentéslogikában, mint a polinomok az algebrában. A polinomoknál megszokot összeadás és szorzás helyett itt konjunkciót és diszjunkciót használunk.
Teljes diszjunktív normál forma
Minden kijelentéslogikai formula felírható konjunkciók diszjunkciójaként. Az ilyen alakot diszjunktív normál formának nevezzük. Ha a konjunkciós tagokban minden kijelentésváltozó szerepel (negálva vagy negálatlanul), akkor teljes diszjunktív normál formáról beszélünk.
Példa:
Teljes konjunktív normál forma
Minden kijelentéslogikai formula felírható diszjunkciók konjunkciójaként. Az ilyen alakot konjunktív normál formának nevezzük. Ha a diszjunkciós tagokban minden kijelentésváltozó szerepel (negálva vagy negálatlanul), akkor teljes konjunktív normál formáról beszélünk.
Példa:
Predikátum
Predikátumoknak nevezzük az olyan kijelentő mondatokat, amelyek egy vagy több változótól függenek és amelyek ezen változók minden megengedett rögzített értékeire egy kijelentést adnak. A változok valamilyen halmaz elemei, például számok lehetnek.
Jelölés: ahol x, y, x1, …, xn individumváltozók
Ha egy predikátum nulla változós, akkor az kijelentés. Az egy és több változós predikátumokat szokás nyitott mondatoknak is nevezni.
Predikátumok és kijelentések
Tekintsük az alábbi következtetést:
A1: A paralelogrammák átlói felezik egymást
A2: A négyzet paralelogramma
B: A négyzet átlói felezik egymást.
Ha fel akarjuk írni ennek a következtetésnek a sémáját, akkor azt tapasztaljuk, hogy egyiket sem tudjuk felbontani kijelentéslogikai műveletekkel, így a séma a következő:
A1: p
A2: q
B: r
Ebben a sémában p, q, r egymástól független kijelentések, így az ezek közti összefüggést nem képes kifejezni a séma, holott a következtetést jogosnak érezzük. A kijelentéslogika ugyanis nem alkalmas az ilyen és ehhez hasonló következtetések vizsgálatára, csak az állítások durvaszerkezetét tárja fel.
Nézzük ugyanezt predikátumlogikai formulákkal:
Vegyük a következő predikátumokat a sikbeli négyszögek halmazán:
P(x): x paralelogramma
F(x): x átlói felezik egymást
N(x): x négyzet
Ekkor a fenti következtetés sémája:
A1:
A2:
B:
Műveletek predikátumokkal
A kijelentésekre vonatkozó műveletek segítségével értelmezhetünk műveleteket predikátumok között is:
Ha P és Q predikátumok és minden megengedett helyettesítés esetén igaz, akkor azt mondjuk, hogy P-ből következik Q.
Jelölés:
Ha P és Q predikátumok és minden megengedett helyettesítés esetén igaz, akkor azt mondjuk, hogy P és Q egyenértékűek, vagy ekvivalensek.
Jelölés:
Predikátum igazsághalamaz
Az n változós halmazon értelmezett P(x_1, …, x_n) predikátum igazsághalmaza azon elemek halmaza, melyekre P igaz. Jelölés: I(P)
Minden predikátumot egyértelműen meghatároz az igazsághalmaza.
A predikátumokkal végzett műveletek is átfogalmazhatók az igazsághalmazok segítségével:
Továbbá átfogalmazása , illetve pontosan akkor teljesül, ha .
Kvantorok
Univerzális kvantor
A „minden x-re” kifejezést univerzális kvantornak nevezzük. Jele: .
Ha P az A halmazon értelmezett predikátum, akkor egy kijelentés, melynek értéke
Egzisztenciális kvantor
A „van olyan x, melyre” kifejezést egzisztenciális kvantornak nevezzük. Jele: .
Ha P az A halmazon értelmezett predikátum, akkor egy kijelentés, melynek értéke
Műveletek kvantorokkal
Predikátumlogikai formulák
Predikátum változók a következő képp adhatók meg:
- A kijelentésválltozók formulák
- Ha P egy n változós predikátum és x1,…,xn individumváltozók, vagy individumnevek, akkor P x1…xn és x1 ≡ x2 formulák.
- Ha A és B formulák, akkor is formula.
- Ha A formula és x egy individum változó, akkor és is formulák.
- más jelsorozat nem formula
Az ≡ („azonosság”) predikátum egy kitüntetett szerepű. kétváltozós predikátum.
Észrevehető, hogy a 2. és 4. pontot elhagyva a kijelentéslogikai formulák definíciójához jutunk.