Tartalomjegyzék

Matematikai logika

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 deﬁní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 ﬁlozó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: overline{p} , vagy ¬p

Megjegyzés: | overline{p} | = 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: p logicaland q

Megjegyzés: | p logicaland q | = |p| cdot |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: p logicalor q

Megjegyzés: | p logicalor q | = |p| + |q| + |p| cdot |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: p right q

Megjegyzés: | p right q | = 1 + |p| + |p| cdot |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: p leftright q

Megjegyzés: | p leftright q | = |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: p | q

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: p || q

Bool algebra

Az igazságértékek {igaz, hamis} halmaza a logikai és ( logicaland , vagy ( logicalor ) 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 delim{|}{overline{overline{p}}}{|}=delim{|}{p}{|} .

Asszociativitás

A diszjunkció és a konjunkció asszociatív művelet, azaz ha p, q és r tetszőleges kijelentés, akkor: delim{|}{(p logicaland q) logicaland r}{|} = delim{|}{p logicaland (q logicaland r)}{|} , illetve delim{|}{(p logicalor q) logicalor r}{|} = delim{|}{p logicalor (q logicalor r)}{|} .

Kommutativitás

A diszjunkció és a konjunkció kommutatív művelet, azaz ha p, és q tetszőleges kijelentés, akkor: delim{|}{p logicaland q}{|} = delim{|}{q logicaland p}{|} , illetve delim{|}{p logicalor q}{|} = delim{|}{q logicalor p}{|} .

Abszorbció

A diszjunkció és a konjunkció abszorbtív művelet egymásra nézve, azaz ha p, és q tetszőleges kijelentés, akkor: delim{|}{p logicaland (p logicalor q)}{|} = delim{|}{p}{|} , illetve delim{|}{p logicalor (p logicaland q)}{|} = delim{|}{p}{|} .

Idempotencia

A diszjunkció és a konjunkció idempotens művelet, azaz ha p tetszőleges kijelentés, akkor: delim{|}{p logicaland p}{|} = delim{|}{p}{|} , illetve delim{|}{p logicalor p}{|} = delim{|}{p}{|} .

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: delim{|}{p logicaland (q logicalor r)}{|} = delim{|}{(p logicaland q) logicalor (p logicaland r)}{|} , illetve delim{|}{p logicalor (q logicaland r)}{|} = delim{|}{(p logicalor q) logicaland (p logicalor r)}{|} .

de Morgan azonosságok

delim{|}{overline{p logicalor q}}{|} = delim{|}{overline{p} logicaland overline{q}}{|} , illetve delim{|}{overline{p logicaland q}}{|} = delim{|}{overline{p} logicalor overline{q}}{|}

A negáció tulajdonságai

delim{|}{p logicalor overline{p}}{|} = 1

delim{|}{p logicaland overline{p}}{|} = 0

Ekvivalencia és implikáció

delim{|}{p leftright q}{|} = delim{|}{(p right q) logicaland (q right p)}{|}

delim{|}{p right q}{|} = delim{|}{overline{p} logicalor q}{|}

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 (t logicalor s) right overline{d} 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 2ⁿ 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 A₁, …, A_n ⊨ B.

Pontosabban: Legyenek A₁, …, A_n, B (n0) adott kijelentéslogikai formulák és legyen T tautológiák egy halmaza. Az E₁, E₂, …, E_k formulasorozatot a B formulának az A₁, …, A_n premisszákból a T segítségével történő levezetésének nevezzük, ha

E_k = B
minden $i in \{1, 2, ..., k\}$ esetén
- E_i egy premissza, vagy
- E_i valamely T-beli tautilógiából helyettesítéssel keletkezik, vagy
- vannak az E₁, E₂, …, E_k sorozatban az E_i-t megelőző formulák, hogy $(E_{i_1} logicaland E_{i_2} logicaland cdots logicaland E_{i_s}) right E_i$ egy T-beli tautológiából helyettesítéssel áll elő.

Belátható (teljes indukcióval), hogy ha B kijelentéslogikai formula levezethető A₁,…,A_n premisszákból T segítségével, akkor A₁, …, A_n ⊨ B, tehát B következménye A₁, …, A_n-nek.

G. Frege (német matematikus) bizonyította, hogy megadható tautológiák olyan T halmaza, hogy tetszőleges formulák esetén, ha A₁, …, A_n ⊨ B, akkor B levezethető az A₁, …, A_n 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: (p logicaland q logicaland ¬r) logicalor (p logicaland ¬q logicaland r) logicalor (¬p logicaland q logicaland r)

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: (¬p logicalor ¬q logicalor r) logicaland (¬p logicalor q logicalor ¬r) logicaland (p logicalor ¬q logicalor ¬r)

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: P(x), P(x,y), P(x_1,x_2, ..., x_n) ahol x, y, x₁, …, x_n 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:

A₁: A paralelogrammák átlói felezik egymást
A₂: 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ő:

A₁: p
A₂: 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:

A₁: forall x(P(x) right F(x))
A₂: forall x(N(x) right P(x))

B: forall x(N(x) right F(x))

Műveletek predikátumokkal

A kijelentésekre vonatkozó műveletek segítségével értelmezhetünk műveleteket predikátumok között is:

$overline{P}(x_1, ..., x_n) = overline(P(x_1, ..., x_n))$

Ha P és Q predikátumok és minden megengedett helyettesítés esetén P(x_1, ..., x_n) right Q(x_1, ..., x_n) igaz, akkor azt mondjuk, hogy P-ből következik Q.

Jelölés: P doubleright Q

Ha P és Q predikátumok és minden megengedett helyettesítés esetén P(x_1, ..., x_n) leftright Q(x_1, ..., x_n) igaz, akkor azt mondjuk, hogy P és Q egyenértékűek, vagy ekvivalensek.

Jelölés: P doubleleftright Q

Predikátum igazsághalamaz

Az n változós A=A_1 * cdots * A_n halmazon értelmezett P(x_1, …, x_n) predikátum igazsághalmaza azon (a_1, ..., a_n) in A 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á P doubleright Q átfogalmazása I(P) subset I(Q) , illetve P doubleleftright Q pontosan akkor teljesül, ha I(P) = I(Q) .

Kvantorok

Univerzális kvantor

A „minden x-re” kifejezést univerzális kvantornak nevezzük. Jele: forall x .

Ha P az A halmazon értelmezett predikátum, akkor forall x P(x) egy kijelentés, melynek értéke
delim{|}{forall x P(x)}{|} = delim{lbrace}{matrix{2}{1}{{1, ha minden a in A esetén delim{|}{P(a)}{|}=1} {0, ha van olyan a in A, melyre delim{|}{P(a)}{|}=0}}}{}

Egzisztenciális kvantor

A „van olyan x, melyre” kifejezést egzisztenciális kvantornak nevezzük. Jele: exists x .

Ha P az A halmazon értelmezett predikátum, akkor exists x P(x) egy kijelentés, melynek értéke
delim{|}{exists x P(x)}{|} = delim{lbrace}{matrix{2}{1}{{0, ha minden a in A esetén delim{|}{P(a)}{|}=0} {1, ha van olyan a in A, melyre delim{|}{P(a)}{|}=1 }}}{}

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 x₁,…,x_n individumváltozók, vagy individumnevek, akkor P x₁…x_n és x₁ ≡ x₂ 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.

Hivatkozások

http://www.ttk.pte.hu/matek/ltoth/A%20matematikai%20logika%20alapjai,%202005.pdf