Formulák igazságértéke

Ha vannak atomi állításaink, amelyeket formulává állítottunk össze, megpróbálhatjuk eldönteni, hogy az egész formula igaz vagy hamis.

Az állítás logikai értéke

Először pontosítsuk, mi az állítás logikai értéke. Ha van egy p állításunk, el kell tudnunk dönteni, hogy igaz vagy hamis. Az igaz állítás logikai értéke 1, a hamisé 0.

Az értékelés ezután egy olyan e előírás, amely az adott állításhoz 0-t vagy 1-et rendel. Ha azt írjuk, hogy e(p), akkor a p állítás igazságára vagyunk kíváncsiak. Ha p a „kétszer kettő négy” állítás, akkor e(p) = 1, mert ez igaz állítás. Ha q a „Pista nő” állítás, akkor e(q) = 0, mert Pista nem nő. Az e tehát egy függvény, amely megmondja, hogy az állítás igaz-e.

Itt fontos felismerni, hogy az e nem valami varázsfüggvény, amely mindent tud a világon. Úgy viselkedik, ahogy megmondjuk neki. Nem tudja, hogy Pista férfi vagy nő. A számolás elején nekünk kell megadnunk, hogyan viselkedjen az értékelő függvény. Ha azt mondjuk neki, hogy Pista nő, akkor e(q) = 1 lesz az eredmény.

A logikai összekötők igazságértéke

Ahhoz, hogy egy formula logikai értékét meg tudjuk határozni, tudnunk kell, hogyan értékeljük ki a logikai összekötőket. Vagyis ha ismerjük az e(p) és e(q) értékelést, mi lesz a p ∧ q, p ⇒ q stb. formulák logikai értéke.

Minden logikai összekötő másként viselkedik, és másra használjuk, ezért mindegyiket külön megnézzük.

A konjunkció igazságértéke

A konjunkciót p ∧ q jelöli, és így olvassuk: „p és egyben q”. Példaként vegyük a „Magyarország Közép-Európában fekszik, és egyben a fővárosa Budapest” formulát. Mikor igaz ez az egész mondat?

Az igazság eldöntésében segít már maga az „és egyben” összekötő. Ez kifejezetten azt kéri, hogy a bal és a jobb oldali állítás is igaz legyen. Ha tehát a p és a q állítás is igaz, vagyis e(p) = 1 és e(q) = 1, akkor az egész konjunkció is igaz. Ellenkező esetben, ha az egyik állítás hamis, vagy mindkettő hamis, az egész formula hamis.

Példa nem igaz konjunkcióra: „A Tisza folyó, és egyben a Tisza átfolyik Oroszországon”. Igaz, hogy a Tisza folyó, de nem igaz, hogy Oroszországon folyik át, ezért az egész konjunkció nem igaz.

Az alábbi táblázat áttekinthetően mutatja:

$$\begin{array}{ccc}p& q& p\wedge q\\ 1& 1& 1\\ 1& 0& 0\\ 0& 1& 0\\ 0& 0& 0\end{array}$$

Az első két oszlopban a p és q állítás logikai értéke áll, a harmadikban a p ∧ q formula logikai értéke.

A diszjunkció igazságértéke

A diszjunkciót p ∨ q jelöli, és így olvassuk: „p vagy q”. Példa: „Oroszország Európában vagy Ázsiában fekszik.” Mikor igaz az egész mondat?

A diszjunkciónál elég, ha legalább az egyik lehetőség igaz. A „vagy” összekötő választási lehetőséget ad, elég, ha a bal vagy a jobb része igaz. Az egyetlen apró különbség a hétköznapi beszédhez képest, hogy a logikai vagy akkor is igaz, ha mindkét állítás teljesül egyszerre. Ez nem szokás, a hétköznapi beszédben a „vagy”-ot gyakran kizáróan használjuk, vagyis „vagy …, vagy …”.

Erre van egy klasszikus vicc: egy család új autót választ a használtautó-kereskedésben. Az apa azt mondja az eladónak: „úgy döntöttünk, hogy kék vagy piros autót veszünk”. Az eladó mindkét autót eladta nekik. Ez jól mutatja a különbséget a logikai és a beszélt nyelvi vagy között: az apa valószínűleg arra gondolt, hogy a két autó közül pontosan az egyiket választják, az eladó viszont érvényes lehetőségnek tartotta, hogy mindkettőt eladja.

Az előző mondat Oroszországról igaz, mert mindkét állítás igaz. Az „a 7 szám osztható 3-mal, vagy a 7 szám prímszám” mondat igaz, mert a hét prímszám. Igaz, hogy nem osztható hárommal, de ez már nem zavar minket. Az igazságértékek táblázata:

$$\begin{array}{ccc}p& q& p\vee q\\ 1& 1& 1\\ 1& 0& 1\\ 0& 1& 1\\ 0& 0& 0\end{array}$$

Az implikáció igazságértéke

Az implikációt p ⇒ q jelöli, és így olvassuk: „ha p, akkor q”. Példa implikációra: „ha sok vodkát iszunk, akkor hányni fogunk”. Mikor igaz a mondat?

A logikai implikáció az összes összekötő közül a legravaszabb, és a hétköznapi beszédben is gyakran félreértik, és az ekvivalenciával keverik. Próbáljuk megválaszolni a kérdést, hogy érvényes-e egyben a fordított implikáció is: q ⇒ p.

Tudjuk, hogy ha sok vodkát iszunk, akkor hányni fogunk. Igaz-e egyben, hogy ha hányunk, akkor sok vodkát ittunk? Ez biztosan nem igaz, ihattunk egészen másféle alkoholt, és mégis rosszul lehettünk, vagy lehet, hogy valami egészen más miatt vagyunk rosszul. A fordított implikáció tehát nem feltétlenül érvényes. Ha egyszerre igaz a p ⇒ q és a q ⇒ p, akkor ekvivalenciáról van szó, lásd később.

Másik példa: „ha holnap esni fog, akkor Pista magával viszi az esernyőt”. És most azt mondom neked, hogy Pista magával vitte az esernyőt. A kérdés: esett aznap? Sokan hajlamosak azt mondani, hogy természetesen igen, hiszen Pista magával vitte az esernyőt, amikor esni készült. Csakhogy az eredeti mondat nem így van felépítve!

Pista valójában valami más miatt is magával vihette az esernyőt, amiről fogalmunk sincs. Lehet, hogy Pista mindig magával viszi az esernyőt, amikor az anyósát látogatja meg, hogy kiszúrhassa a szemét. Vagy úgy döntött, hogy vesz egy új esernyőt, a régit pedig ki akarja dobni. Ezek mind jogos okok, amiért Pista magával vihette az esernyőt, még ha nem is esett.

Most már megválaszolhatjuk a kérdést, mikor igaz az implikáció. Ha mindkét állítás igaz, akkor az implikáció biztosan igaz: „ha a 42 természetes szám, akkor pozitív”. Mindkét állítás igaz, tehát az egész implikáció igaz. Másik példa lehet a „ha a 42 természetes szám, akkor negatív” implikáció. Ez az implikáció nem igaz, mert az igazból olyasmit próbálunk levezetni, ami nem igaz.

Végül azok az esetek maradtak, amikor az első állítás hamis. Ilyenkor a második állítás igazsága már nem érdekel minket. Ha a hamisból indulunk ki, onnantól azt beszélünk, amit akarunk. Ilyen mondatok például: „ha az 1 negatív szám, akkor én vagyok a kínai császár” vagy „ha a Balaton sivatag, akkor kék a nap”. Az ilyen esetekben az implikáció automatikusan igaz, mert egyszerűen a hamisból indul ki. Táblázat:

$$\begin{array}{ccc}p& q& p\Rightarrow q\\ 1& 1& 1\\ 1& 0& 0\\ 0& 1& 1\\ 0& 0& 1\end{array}$$

Az ekvivalencia igazságértéke

Az ekvivalenciát p ⇔ q jelöli, és így olvassuk: „p akkor és csak akkor, ha q”. Példa ekvivalenciára: „az x szám akkor és csak akkor osztható kettővel, ha páros”. Mikor igaz az egész mondat?

Az ekvivalenciánál azt várjuk, hogy a két állítás olyan szimbiózisban van, hogy vagy mindkettő igaz, vagy egyik sem. Tehát vagy az x szám páros, és egyben osztható kettővel is, vagy egyik sem teljesül. Nem fordulhat elő, hogy az x páros lenne, de nem lenne osztható kettővel.

Példa: „Jenő akkor és csak akkor olvas könyvet, ha a vécén ül.” Ahhoz, hogy az ekvivalencia teljesüljön, mindig, amikor Jenő a vécén ül, könyvet kell olvasnia. És egyben mindig, amikor könyvet olvas, a vécén kell ülnie. Nem fordulhat elő, hogy például az ágyban olvas könyvet.

Az ekvivalenciát kifejezhetjük két implikációval. A p ⇔ q tehát átírható úgy, hogy p ⇒ q és egyben q ⇒ p. Táblázat:

$$\begin{array}{ccc}p& q& p\iff q\\ 1& 1& 1\\ 1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}$$

Negáció

A negáció egyváltozós művelet, jelölhetjük vesszővel p' vagy ezzel a szimbólummal: ¬p. A negáció tagadja az eredeti állítást. Ha van egy „Mari énekesnő” állításunk, akkor a negációja a „Nem igaz, hogy Mari énekesnő” vagy röviden „Mari nem énekesnő”. A negációt gyakorlatilag mindig megalkothatjuk úgy, hogy az állítás elé odaírjuk: „Nem igaz, hogy…”

A negáció megfordítja a logikai értéket, vagyis a 0-ból 1-et csinál, az 1-ből pedig 0-t. Így felírhatjuk: ¬0 = 1 és ¬1 = 0.

Vigyázz néhány alattomos dologra. Legyen az állítás „a mész fehér”. Mi a negációja? Valakinek eszébe juthat, hogy „a mész fekete”, de ez nem igaz! Ha az előző szabályt alkalmazzuk, a negáció a „nem igaz, hogy a mész fehér” állítás. Ez szükségszerűen azt jelenti, hogy feketének kell lennie? Nem jelenti, lehet például rózsaszín is.

Az összes összekötő táblázata

$$\begin{array}{cccccc}p& q& p\wedge q& p\vee q& p\Rightarrow q& p\iff q\\ 1& 1& 1& 1& 1& 1\\ 1& 0& 0& 1& 0& 0\\ 0& 1& 0& 1& 1& 0\\ 0& 0& 0& 0& 1& 1\end{array}$$

A teljes formula igazságértéke

Most már ki tudjuk értékelni két, logikai összekötővel összekapcsolt állítás logikai értékét. A teljes formulát teljesen analóg módon értékeljük ki. Ha van egy (p ⇒ q) ∧ r formulánk, akkor abban a pillanatban, amikor a (p ⇒ q) formulát például 1-re kiértékeltük, megkapjuk a klasszikus 1 ∧ r konjunkciót, amelyet már meg tudunk oldani.

A legegyszerűbb logikai összekötők fokozatos alkalmazásával eljutunk a teljes formula végső logikai értékéhez. Erre gyakran az úgynevezett táblázatos módszert használjuk, amelyet a továbbiakban ismertetünk.

Táblázatos módszer

A táblázatos módszert az összetettebb formulák kiértékelésére használjuk. Az első n oszlopba beírjuk a formulában szereplő n ítéletváltozót, a további oszlopokba pedig sorban elhelyezzük a formula részformuláit. Egy példán jobban érthető:

Legyen adott a (p ∨ q) ∧ (q ⇒ p) formula. Először beírjuk a táblázatba az összes ítéletváltozót, vagyis a p-t és a q-t, valamint az értékeik összes kombinációját:

$$\begin{array}{cc}p& q\\ 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

Ezután hozzáírjuk az egyes részformulák oszlopait: p ∨ q és q ⇒ p.

$$\begin{array}{cccc}p& q& p\vee q& q\Rightarrow p\\ 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

Most ezeket a formulákat kiértékeljük, és az oszlopokba nullákat vagy egyeseket írunk. A táblázatban megvan minden szükséges információ. Úgy haladunk, hogy amikor az első sorban a p ∨ q-t értékeljük ki, p helyére 1-et helyettesítünk, q helyére szintén 1-et. Így megkapjuk az 1 ∨ 1 kifejezést. Ennek kiértékelése ismét 1, ezért a táblázatba egyest írunk:

$$\begin{array}{cccc}p& q& p\vee q& q\Rightarrow p\\ 1& 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

Így fokozatosan kitöltjük az egész táblázatot:

$$\begin{array}{cccc}p& q& p\vee q& q\Rightarrow p\\ 1& 1& 1& 1\\ 1& 0& 1& 1\\ 0& 1& 1& 0\\ 0& 0& 0& 1\end{array}$$

Most már csak ki kell értékelni az egész formulát. Jelöljük például φ = (p ∨ q) ∧ (q ⇒ p)-vel. Hozzáadunk a táblázathoz egy φ oszlopot, és kiértékeljük, miközben a kiértékeléshez már az előző két oszlopot használjuk.

$$\begin{array}{ccccc}p& q& p\vee q& q\Rightarrow p& \phi \\ 1& 1& 1& 1& 1\\ 1& 0& 1& 1& 1\\ 0& 1& 1& 0& 0\\ 0& 0& 0& 1& 0\end{array}$$

A táblázat kész, és megadja a formula logikai értékét az összes lehetséges értékelésben. Például ha e(p) = 1 és egyben e(q) = 1, akkor a formula igaz. Ha e(p) = 0 és e(q) = 1, akkor a formula nem igaz.

Figyeld meg, hogy nem mondhatjuk, hogy „a formula igaz”. Ennek a mondatnak nincs értelme, mert ahhoz, hogy azt mondhassuk, a formula igaz, meg kellene mondanunk, melyik értékelésben igaz. Mondhatjuk tehát, hogy „a φ formula igaz az e₁ értékelésben, és nem igaz az e₂ értékelésben”.

Az egyetlen eset, amikor azt mondhatnánk, hogy a formula igaz, az, ha minden lehetséges értékelésben igaz. Például a p ∨ ¬p formula minden értékelésben igaz, ezért mondhatjuk, hogy a formula igaz. Hasonlóan arra az esetre, amikor a formula minden értékelésben hamis.

Az ilyen formuláknak külön nevük van. Azt a formulát, amely minden értékelésben igaz, tautológiának nevezzük. Azt a formulát, amely egyetlen értékelésben sem teljesül, ellentmondásnak (kontradikciónak) nevezzük.