Eksempler på udsagnslogik

I denne artikel viser vi nogle formler og deres mulige værdisætninger ved hjælp af sandhedstabeller.

Første eksempel

Vi prøver at finde ud af, hvornår denne formel er sand: ϕ = (p ∧ q) ∨ ¬q. Vi skriver udsagnsvariablene p og q i en tabel:

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

Dernæst skriver vi den første del af formlen i tabellen: (p ∧ q), negationen ¬q og så hele formlen:

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

Nu udregner vi værdierne i den tredje kolonne, det er en simpel konjunktion, og samtidig også for negationen — der indsætter vi bare de omvendte værdier af dem, der står i den anden kolonne:

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

Til sidst udregner vi værdierne i den sidste kolonne. Det er hele formlen. Ud fra vores tabel regner vi altså en disjunktion »mellem den tredje og den fjerde kolonne«. Resultat:

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

Andet eksempel

Samme opgave, en anden formel: ϕ = (p ∧ ¬q) ⇔ (¬p ⇒ q). Vi ser, at formlen indeholder udsagnsvariablene p og q og deres negationer. Først laver vi derfor en tabel med de to symboler og deres negationer:

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

Dernæst tilføjer vi formlerne p ∧ ¬q og ¬p ⇒ q, som vi allerede let kan vurdere, fordi vi i tabellen har både værdisætningen af de enkelte udsagn og af deres negationer. Tabellen ser sådan ud:

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

Til sidst mangler vi at vurdere hele formlen, som er en biimplikation mellem de to sidste kolonner:

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

Tredje eksempel

Det tredje eksempel bliver lidt sværere, vi prøver med tre udsagnsvariable, hvilket gør udregningen af tabellen mere omfattende. Formlen ser sådan ud: ϕ = (¬(p ⇒ q)) ∧ (r ⇔ (¬p ∨ q)).

Fordi vi har tre udsagnsvariable, er det samlede antal værdisætninger otte:

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

Derefter går vi frem på samme måde som i det foregående tilfælde, og vi udfylder hver kolonne i alle otte rækker. Hele tabellen ser sådan ud:

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

Fjerde eksempel

Dette eksempel giver vi ikke som en almindelig formel, men som en tekstopgave. Tre venner, som vil med til en vild fest, hvor topløse modeller deler snacks ud, kan ikke helt lide hinanden og stiller betingelser for, hvornår de vil komme til festen. De hedder Magnus, Jakob og Peter. Reglerne er følgende:

1. Hvis Magnus kommer, så kommer Jakob også.
2. Til festen kommer Peter, eller, hvis Magnus kommer, så kommer Jakob ikke.
3. Peter kommer, hvis og kun hvis Magnus ikke kommer eller Jakob ikke kommer.

Spørgsmålet er, om de alle sammen kan komme til festen? Hvis ikke, hvem kan så komme til festen uden at overtræde nogen af reglerne?

Først skal vi omskrive de foregående udsagn med ord til udsagnsvariable og formler. Lad os betegne udsagnsvariablene M, J og P (Magnus, Jakob, Peter), og de vil altid betyde et udsagn af typen »Magnus kommer til festen«. Den første regel kunne vi omskrive sådan her: M ⇒ J — »hvis M, så J«, altså »hvis Magnus kommer til festen, så kommer Jakob til festen«.

Den anden regel omskriver vi sådan her. Reglen begynder med sætningen »Til festen kommer Peter, eller…«, så vi har åbenbart brug for en disjunktion. Foreløbig skriver vi dette: P ∨ … Den næste del af sætningen siger: »hvis Magnus kommer, så kommer Jakob ikke«. Det er en implikation, hvor vi desuden skal bruge en negation på højre side. »Jakob kommer ikke« = ¬J. Hele implikationen ville se sådan ud: M ⇒ ¬J. Den knytter vi til den foregående disjunktion: P ∨ (M ⇒ ¬J).

Den tredje regel omskriver vi sådan her: Vi starter med »Peter kommer hvis og kun hvis«. Det betyder en biimplikation: P ⇔ … Dernæst har vi »Magnus kommer ikke, eller Jakob kommer ikke«, hvilket vi omskriver sådan her: ¬M ∨ ¬J. Vi sætter det sammen: (P ⇔ (¬M ∨ ¬J)).

Nu sætter vi alle formlerne ind i tabellen og udregner værdierne:

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

Spørgsmålet lød, om alle tre drenge kan tage til den vilde fest. Svaret finder vi i den første række. Den svarer til det tilfælde, hvor alle drengene kommer — det signaleres af de tre ettaller i de første tre kolonner. Er alle betingelserne opfyldt? Den første ja (fjerde kolonne), den anden også (femte kolonne), men den sidste ikke (sidste kolonne), dér er der et nul. Det betyder, at hvis alle tre kommer, så er den tredje betingelse ikke opfyldt.

Vi leder derfor efter de rækker, hvor der kun står ettaller på de pladser, der symboliserer betingelserne (altså de sidste tre kolonner). Et ettal betyder, at betingelsen er opfyldt. Vi ser, at det sker i to tilfælde. Når Jakob og Peter kommer, men Magnus ikke, og så når kun Peter kommer.

Du kan også regne det ud ved at føje formlen ϕ til tabellen, som er konjunktionen af alle tre betingelser. Den ser altså sådan ud: ϕ = ((M ⇒ J) ∧ (P ∨ (M ⇒ ¬J)) ∧ (P ⇔ (¬M ∨ ¬J))). Den viser det, vi vil have — at alle formlerne (alle betingelserne) er opfyldt. Tabellen ville så se sådan ud:

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

Nogle eksempler på sandhedstabeller

Fordi jeg har skrevet et program, som ud fra en given formel automatisk kan opstille hele tabellen, må jeg også udnytte det ordentligt, og derfor følger der nu et par løste formler mere:

Formel: ((a ∧ ¬b) ∨ (b ∧ (b ⇒ a))). Tabel:

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

Formel: (a ∨ ¬a) ⇔ (b ∧ ¬b). Tabel:

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

Formel: ¬(a ∨ b) ⇔ (¬b ∧ ¬a). Tabel:

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

Formel: ϕ = (¬p ⇔ (q ∧ r)) ⇒ (p ∨ ¬(p ∧ q)). Tabel:

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

Formel: ϕ = ¬(p ⇔ ¬q) ∧ (r ⇒ ¬p) ∧ (p ∨ r). Tabel:

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