Példák az ítéletlogikára

Ebben a cikkben néhány formulát és azok lehetséges értékeléseit mutatjuk meg a táblázatos módszer segítségével.

Első példa

Próbáljuk meg kideríteni, mikor igaz ez a formula: ϕ = (p ∧ q) ∨ ¬q. Írjuk be a táblázatba a p és q ítéletváltozókat:

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

Ezután írjuk be a táblázatba a formula első részét: (p ∧ q), a ¬q negációt, majd az egész formulát:

$$\begin{array}{ccccc}p& q& p\wedge q& \mathrm{\neg }q& \varphi \\ 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

Most kiszámítjuk a harmadik oszlop értékeit, ez egyszerű konjunkció, és ugyanígy a negációét is – oda csak a második oszlop értékeinek ellentettjét írjuk:

$$\begin{array}{ccccc}p& q& p\wedge q& \mathrm{\neg }q& \varphi \\ 1& 1& 1& 0\\ 1& 0& 0& 1\\ 0& 1& 0& 0\\ 0& 0& 0& 1\end{array}$$

Végül kiszámítjuk az utolsó oszlop értékeit. Ez az egész formula. A táblázatunk alapján tehát a „harmadik és a negyedik oszlop közötti” diszjunkciót számoljuk ki. Az eredmény:

$$\begin{array}{ccccc}p& q& p\wedge q& \mathrm{\neg }q& \varphi \\ 1& 1& 1& 0& 1\\ 1& 0& 0& 1& 1\\ 0& 1& 0& 0& 0\\ 0& 0& 0& 1& 1\end{array}$$

Második példa

Ugyanaz a feladat, másik formula: ϕ = (p ∧ ¬q) ⇔ (¬p ⇒ q). Látjuk, hogy a formulában szerepel a p és a q ítéletváltozó és azok negációja. Először tehát készítünk egy táblázatot a két ítéletváltozóval és a negációikkal:

$$\begin{array}{cccc}p& q& \mathrm{\neg }p& \mathrm{\neg }q\\ 1& 1& 0& 0\\ 1& 0& 0& 1\\ 0& 1& 1& 0\\ 0& 0& 1& 1\end{array}$$

Ezután hozzáadjuk a p ∧ ¬q és a ¬p ⇒ q formulát, amelyeket már könnyen ki tudunk értékelni, mert a táblázatban megvan az egyes állítások és a negációik értékelése is. A táblázat így néz ki:

$$\begin{array}{cccccc}p& q& \mathrm{\neg }p& \mathrm{\neg }q& (p\wedge \mathrm{\neg }q)& (\mathrm{\neg }p\Rightarrow q)\\ 1& 1& 0& 0& 0& 1\\ 1& 0& 0& 1& 1& 1\\ 0& 1& 1& 0& 0& 1\\ 0& 0& 1& 1& 0& 0\end{array}$$

Utolsóként az egész formulát kell kiértékelnünk, ami a két utolsó oszlop közötti ekvivalencia:

$$\begin{array}{ccccccc}p& q& \mathrm{\neg }p& \mathrm{\neg }q& (p\wedge \mathrm{\neg }q)& (\mathrm{\neg }p\Rightarrow q)& \varphi \\ 1& 1& 0& 0& 0& 1& 0\\ 1& 0& 0& 1& 1& 1& 1\\ 0& 1& 1& 0& 0& 1& 0\\ 0& 0& 1& 1& 0& 0& 1\end{array}$$

Harmadik példa

A harmadik példa már kicsit bonyolultabb lesz, három ítéletváltozóval próbálkozunk, amitől a táblázat kiszámítása bonyolultabbá válik. A formula így néz ki: ϕ = (¬(p ⇒ q)) ∧ (r ⇔ (¬p ∨ q)).

Mivel három ítéletváltozónk van, az értékelések variációinak száma összesen nyolc:

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

Ezután ugyanúgy haladunk, mint az előző esetben, minden oszlopot kiértékelünk mind a nyolc sorban. A teljes táblázat így fog kinézni:

$$\begin{array}{ccccccccc}p& q& r& \mathrm{\neg }p& (p\Rightarrow q)& (\mathrm{\neg }p\vee q)& \mathrm{\neg }(p\Rightarrow q)& (r\iff (\mathrm{\neg }p\vee q))& \varphi \\ 1& 1& 1& 0& 1& 1& 0& 1& 0\\ 1& 1& 0& 0& 1& 1& 0& 0& 0\\ 1& 0& 1& 0& 0& 0& 1& 0& 0\\ 1& 0& 0& 0& 0& 0& 1& 1& 1\\ 0& 1& 1& 1& 1& 1& 0& 1& 0\\ 0& 1& 0& 1& 1& 1& 0& 0& 0\\ 0& 0& 1& 1& 1& 1& 0& 1& 0\\ 0& 0& 0& 1& 1& 1& 0& 0& 0\end{array}$$

Negyedik példa

Ezt a példát már nem egyszerű formulaként adjuk meg, hanem szöveges feladatként. Három barát, akik el szeretnének menni egy vad bulira, ahol topless modellek szolgálják fel a frissítőt, nem igazán kedvelik egymást, és feltételeket szabnak, amelyek mellett elmennek a buliba. A nevük Márton, János és Péter. A szabályok a következők:

1. Ha Márton elmegy, akkor János is elmegy.
2. Péter eljön a buliba, vagy ha Márton odamegy, akkor János nem megy el.
3. Péter akkor és csak akkor jön el, ha Márton nem jön el, vagy János nem jön el.

A kérdés: elmehet-e mindenki a buliba? Ha nem, ki mehet el úgy, hogy egyetlen szabályt se szegjen meg?

Először a fenti szöveges állításokat át kell írnunk ítéletváltozókra és formulákra. Jelöljük tehát az ítéletváltozókat M, J és P betűvel (Márton, János, Péter), és ez mindig a „Márton elmegy a buliba” típusú állítást jelenti. Az első szabályt átírhatjuk így: M ⇒ J – „ha M, akkor J”, vagyis „ha Márton elmegy a buliba, akkor János is elmegy a buliba”.

A második szabályt így írnánk át. A szabály így kezdődik: „Péter eljön a buliba, vagy…”, tehát nyilván diszjunkcióra lesz szükségünk. Egyelőre ezt írjuk le: P ∨ … A mondat következő része azt mondja: „ha Márton odamegy, akkor János nem megy el”. Ez implikáció, a jobb oldalán pedig még negációt kell használnunk. „János nem megy el” = ¬J. A teljes implikáció így nézne ki: M ⇒ ¬J. Ezt hozzákapcsoljuk az előző diszjunkcióhoz: P ∨ (M ⇒ ¬J).

A harmadik szabályt így írjuk át: kezdjük azzal, hogy „Péter akkor és csak akkor jön el”. Ez ekvivalenciát jelent: P ⇔ … Aztán jön a „Márton nem jön el, vagy János nem jön el”, amit így írunk át: ¬M ∨ ¬J. Összerakjuk: (P ⇔ (¬M ∨ ¬J)).

Most az összes formulát betesszük a táblázatba, és kiszámítjuk az értékeket:

$$\begin{array}{cccccc}M& J& P& (M\Rightarrow J)& (P\vee (M\Rightarrow \mathrm{\neg }J))& (P\iff (\mathrm{\neg }M\vee \mathrm{\neg }J))\\ 1& 1& 1& 1& 1& 0\\ 1& 1& 0& 1& 0& 1\\ 1& 0& 1& 0& 1& 1\\ 1& 0& 0& 0& 1& 0\\ 0& 1& 1& 1& 1& 1\\ 0& 1& 0& 1& 1& 0\\ 0& 0& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 0\end{array}$$

A kérdés az volt, hogy mehet-e mind a három fiú a vad buliba. A választ az első sorban találjuk. Ez arra az esetre vonatkozik, amikor mindhárom fiú elmegy – ezt jelzi a három egyes az első három oszlopban. Teljesül minden feltétel? Az első igen (negyedik oszlop), a második is (ötödik oszlop), de az utolsó nem (utolsó oszlop), ott nulla áll. Ez azt jelenti, hogy ha mindhárman elmennek, a harmadik feltétel nem teljesül.

Azokat a sorokat keressük tehát, amelyekben a feltételeket jelképező helyeken (vagyis az utolsó három oszlopban) csupa egyes áll. Az egyes azt jelenti, hogy a feltétel teljesül. Látjuk, hogy ez két esetben fordul elő. Amikor János és Péter megy, de Márton nem, és amikor csak Péter megy.

Ezt úgy is kiszámíthatod, hogy a táblázathoz hozzáadsz egy ϕ formulát, amely mindhárom feltétel konjunkciója. Így fog kinézni:ϕ = ((M ⇒ J) ∧ (P ∨ (M ⇒ ¬J)) ∧ (P ⇔ (¬M ∨ ¬J))). Ez azt fejezi ki, amit akarunk – hogy az összes formula (az összes feltétel) teljesüljön. A táblázat ekkor így nézne ki:

$$\begin{array}{ccccccc}M& J& P& (M\Rightarrow J)& (P\vee (M\Rightarrow \mathrm{\neg }J))& (P\iff (\mathrm{\neg }M\vee \mathrm{\neg }J))& \varphi \\ 1& 1& 1& 1& 1& 0& 0\\ 1& 1& 0& 1& 0& 1& 0\\ 1& 0& 1& 0& 1& 1& 0\\ 1& 0& 0& 0& 1& 0& 0\\ 0& 1& 1& 1& 1& 1& 1\\ 0& 1& 0& 1& 1& 0& 0\\ 0& 0& 1& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 0& 0\end{array}$$

Még néhány példa a táblázatos módszerre

Mivel írtam egy programot, amely egy adott formulából automatikusan össze tudja állítani a teljes táblázatot, rendesen ki kell használnom, ezért következik még néhány megoldott formula:

Formula: ((a ∧ ¬b) ∨ (b ∧ (b ⇒ a))). Táblázat:

$$\begin{array}{ccccc}a& b& (a\wedge \mathrm{\neg }b)& (b\wedge (b\Rightarrow a))& ((a\wedge \mathrm{\neg }b)\vee (b\wedge (b\Rightarrow a)))\\ 1& 1& 0& 1& 1\\ 1& 0& 1& 0& 1\\ 0& 1& 0& 0& 0\\ 0& 0& 0& 0& 0\end{array}$$

Formula: (a ∨ ¬a) ⇔ (b ∧ ¬b). Táblázat:

$$\begin{array}{ccccc}a& b& (a\vee \mathrm{\neg }a)& (b\wedge \mathrm{\neg }b)& ((a\vee \mathrm{\neg }a)\iff (b\wedge \mathrm{\neg }b))\\ 1& 1& 1& 0& 0\\ 1& 0& 1& 0& 0\\ 0& 1& 1& 0& 0\\ 0& 0& 1& 0& 0\end{array}$$

Formula: ¬(a ∨ b) ⇔ (¬b ∧ ¬a). Táblázat:

$$\begin{array}{ccccc}a& b& \mathrm{\neg }(a\vee b)& (\mathrm{\neg }b\wedge \mathrm{\neg }a)& (\mathrm{\neg }(a\vee b)\iff (\mathrm{\neg }b\wedge \mathrm{\neg }a))\\ 1& 1& 0& 0& 1\\ 1& 0& 0& 0& 1\\ 0& 1& 0& 0& 1\\ 0& 0& 1& 1& 1\end{array}$$

Formula: ϕ = (¬p ⇔ (q ∧ r)) ⇒ (p ∨ ¬(p ∧ q)). Táblázat:

$$\begin{array}{cccccccc}p& q& r& (q\wedge r)& \mathrm{\neg }(p\wedge q)& (\mathrm{\neg }p\iff (q\wedge r))& (p\vee \mathrm{\neg }(p\wedge q))& \varphi \\ 1& 1& 1& 1& 0& 0& 1& 1\\ 1& 1& 0& 0& 0& 1& 1& 1\\ 1& 0& 1& 0& 1& 1& 1& 1\\ 1& 0& 0& 0& 1& 1& 1& 1\\ 0& 1& 1& 1& 1& 1& 1& 1\\ 0& 1& 0& 0& 1& 0& 1& 1\\ 0& 0& 1& 0& 1& 0& 1& 1\\ 0& 0& 0& 0& 1& 0& 1& 1\end{array}$$

Formula: ϕ = ¬(p ⇔ ¬q) ∧ (r ⇒ ¬p) ∧ (p ∨ r). Táblázat:

$$\begin{array}{ccccccc}p& q& r& \mathrm{\neg }(p\iff \mathrm{\neg }q)& (r\Rightarrow \mathrm{\neg }p)& (p\vee r)& \varphi \\ 1& 1& 1& 1& 0& 1& 0\\ 1& 1& 0& 1& 1& 1& 1\\ 1& 0& 1& 0& 0& 1& 0\\ 1& 0& 0& 0& 1& 1& 0\\ 0& 1& 1& 0& 1& 1& 0\\ 0& 1& 0& 0& 1& 0& 0\\ 0& 0& 1& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 0& 0\end{array}$$