Propositiologiikan esimerkkejä

Tässä artikkelissa katsomme muutamaa kaavaa ja niiden mahdollisia totuusarvojen asetuksia totuustaulun avulla.

Ensimmäinen esimerkki

Yritetään selvittää, milloin tämä kaava on tosi: ϕ = (p ∧ q) ∨ ¬q. Kirjoitetaan taulukkoon propositiosymbolit p ja q:

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

Lisätään taulukkoon seuraavaksi kaavan ensimmäinen osa (p ∧ q), negaatio ¬q ja sitten koko kaava:

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

Lasketaan nyt arvot kolmanteen sarakkeeseen, joka on yksinkertainen konjunktio, ja samalla negaation sarakkeeseen. Siihen kirjoitetaan toisen sarakkeen arvojen vastakohdat:

$$\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}$$

Lopuksi lasketaan arvot viimeiseen sarakkeeseen. Se on koko kaava. Taulukkomme kannalta lasketaan siis disjunktio ”kolmannen ja neljännen sarakkeen välillä”. Tulos:

$$\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}$$

Toinen esimerkki

Sama tehtävä, eri kaava: ϕ = (p ∧ ¬q) ⇔ (¬p ⇒ q). Näemme, että kaavassa on propositiosymbolit p ja q sekä niiden negaatiot. Tehdään siis ensin taulukko, jossa on kaksi symbolia ja niiden negaatiot:

$$\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}$$

Lisätään sitten kaavat p ∧ ¬q ja ¬p ⇒ q, jotka osaamme jo helposti arvioida, koska taulukossa on sekä väitteiden että niiden negaatioiden totuusarvot. Taulukko näyttää tältä:

$$\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}$$

Viimeiseksi jää arvioitavaksi koko kaava, joka on ekvivalenssi kahden viimeisen sarakkeen välillä:

$$\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}$$

Kolmas esimerkki

Kolmas esimerkki on jo hieman monimutkaisempi. Kokeillaan kolmea propositiosymbolia, jolloin taulukon laskeminen mutkistuu. Kaava on tämä: ϕ = (¬(p ⇒ q)) ∧ (r ⇔ (¬p ∨ q)).

Koska symboleja on kolme, totuusarvojen asetusten yhteismäärä on kahdeksan:

$$\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}$$

Tästä eteenpäin etenemme samoin kuin edellisessä tapauksessa ja arvioimme jokaisen sarakkeen kaikilla kahdeksalla rivillä. Koko taulukko näyttää tältä:

$$\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}$$

Neljäs esimerkki

Tämän esimerkin annamme tavallisen kaavan sijaan sanallisena tehtävänä. Kolme kaveria haluaa mennä villeihin bileisiin, joissa tarjoillaan ilmaista pizzaa. He eivät oikein pidä toisistaan ja asettavat ehtoja, joilla he tulevat bileisiin. Heidän nimensä ovat Matti, Jussi ja Pekka. Säännöt ovat seuraavat:

1. Jos Matti tulee, niin myös Jussi tulee.
2. Bileisiin tulee Pekka tai, jos Matti tulee, niin Jussi ei tule.
3. Pekka tulee jos ja vain jos Matti ei tule tai Jussi ei tule.

Kysymys kuuluu: voivatko kaikki tulla bileisiin? Jos eivät, ketkä voivat tulla rikkomatta yhtään sääntöä?

Ensin meidän täytyy kirjoittaa edelliset sanalliset väitteet propositiosymboleiksi ja kaavoiksi. Merkitään propositiosymboleja M, J ja P (Matti, Jussi, Pekka), ja kukin tarkoittaa aina väitettä tyyppiä ”Matti tulee bileisiin”. Ensimmäisen säännön voisi kirjoittaa näin: M ⇒ J eli ”jos M, niin J”, toisin sanoen ”jos Matti tulee bileisiin, niin Jussi tulee bileisiin”.

Toisen säännön kirjoittaisimme näin. Sääntö alkaa lauseella ”Bileisiin tulee Pekka tai…”, joten tarvitsemme selvästi disjunktion. Kirjoitetaan toistaiseksi: P ∨ … Lauseen seuraava osa kuuluu: ”jos Matti tulee, niin Jussi ei tule”. Se on implikaatio, ja oikealla puolella tarvitaan vielä negaatio. ”Jussi ei tule” = ¬J. Koko implikaatio olisi siis M ⇒ ¬J. Liitetään se edelliseen disjunktioon: P ∨ (M ⇒ ¬J).

Kolmannen säännön kirjoitamme näin: aloitamme sanoilla ”Pekka tulee jos ja vain jos”. Se tarkoittaa ekvivalenssia: P ⇔ … Sitten meillä on ”Matti ei tule tai Jussi ei tule”, jonka kirjoitamme näin: ¬M ∨ ¬J. Kootaan yhteen: (P ⇔ (¬M ∨ ¬J)).

Nyt laitamme kaikki kaavat taulukkoon ja laskemme arvot:

$$\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}$$

Kysymys oli, voivatko kaikki kolme poikaa tulla villeihin bileisiin. Vastauksen löydämme ensimmäiseltä riviltä. Se vastaa tapausta, jossa kaikki pojat tulevat, mistä kertovat kolme ykköstä kolmessa ensimmäisessä sarakkeessa. Täyttyvätkö kaikki ehdot? Ensimmäinen täyttyy (neljäs sarake), toinenkin (viides sarake), mutta viimeinen ei (viimeinen sarake), siellä on nolla. Se tarkoittaa, että jos kaikki kolme tulevat, kolmas ehto ei täyty.

Etsimme siis rivit, joilla ehtoja kuvaavissa sarakkeissa (eli kolmessa viimeisessä) on pelkkiä ykkösiä. Ykkönen tarkoittaa, että ehto täyttyy. Näemme, että niin käy kahdessa tapauksessa: kun Jussi ja Pekka tulevat mutta Matti ei, sekä kun vain Pekka tulee.

Voit laskea tämän myös lisäämällä taulukkoon kaavan ϕ, joka on kaikkien kolmen ehdon konjunktio. Se näyttää tältä: ϕ = ((M ⇒ J) ∧ (P ∨ (M ⇒ ¬J)) ∧ (P ⇔ (¬M ∨ ¬J))). Se ilmaisee sen, mitä haluamme: että kaikki kaavat (kaikki ehdot) täyttyvät. Taulukko olisi silloin tällainen:

$$\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}$$

Muutama esimerkki totuustaulusta

Koska olen kirjoittanut ohjelman, joka osaa koota koko taulukon annetusta kaavasta automaattisesti, minun täytyy käyttää sitä kunnolla. Siksi seuraavaksi on vielä muutama ratkaistu kaava:

Kaava: ((a ∧ ¬b) ∨ (b ∧ (b ⇒ a))). Taulukko:

$$\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}$$

Kaava: (a ∨ ¬a) ⇔ (b ∧ ¬b). Taulukko:

$$\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}$$

Kaava: ¬(a ∨ b) ⇔ (¬b ∧ ¬a). Taulukko:

$$\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}$$

Kaava: ϕ = (¬p ⇔ (q ∧ r)) ⇒ (p ∨ ¬(p ∧ q)). Taulukko:

$$\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}$$

Kaava: ϕ = ¬(p ⇔ ¬q) ∧ (r ⇒ ¬p) ∧ (p ∨ r). Taulukko:

$$\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}$$