Exempel på satslogik

I den här artikeln visar vi några formler och deras möjliga värderingar med hjälp av sanningstabellen.

Första exemplet

Vi ska ta reda på när den här formeln är sann: ϕ = (p ∧ q) ∨ ¬q. Vi skriver in satsvariablerna p och q i tabellen:

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

Sedan lägger vi till den första delen av formeln: (p ∧ q), negationen ¬q och därefter hela formeln:

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

Nu beräknar vi värdena för den tredje kolumnen, som är en enkel konjunktion, och samtidigt för negationen — där sätter vi bara in de omvända värdena mot dem i den andra kolumnen:

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

Till sist beräknar vi värdena i den sista kolumnen. Det är hela formeln. Med vår tabell beräknar vi alltså disjunktionen ”mellan den tredje och den fjärde kolumnen”. 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}$$

Andra exemplet

Samma uppgift, en annan formel: ϕ = (p ∧ ¬q) ⇔ (¬p ⇒ q). Vi ser att formeln innehåller satsvariablerna p och q och deras negationer. Först gör vi därför en tabell med de två symbolerna och deras 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}$$

Sedan lägger vi till formlerna p ∧ ¬q och ¬p ⇒ q, som vi nu enkelt kan värdera, eftersom vi i tabellen har både värderingen av de enskilda utsagorna och av deras negationer. Tabellen ser ut så här:

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

Till sist återstår att värdera hela formeln, som är en ekvivalens mellan de två sista kolumnerna:

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

Det tredje exemplet blir lite svårare, vi prövar tre satsvariabler, vilket gör beräkningen av tabellen mer omfattande. Formeln ser ut så här: ϕ = (¬(p ⇒ q)) ∧ (r ⇔ (¬p ∨ q)).

Eftersom vi har tre satsvariabler blir det totala antalet möjliga värderingar åtta:

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

Därefter går vi tillväga på samma sätt som i det förra fallet, vi värderar varje kolumn i alla åtta rader. Hela tabellen ser ut så här:

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

Fjärde exemplet

Det här exemplet ger vi inte som en vanlig formel, utan som en textuppgift. Tre kompisar vill gå på en vild fest där toplösa modeller delar ut förfriskningar. De gillar inte varandra så värst mycket och ställer villkor för när de följer med. De heter Martin, Jakob och Per. Reglerna är följande:

1. Om Martin går, så går också Jakob.
2. Per kommer till festen eller, om Martin kommer dit, så kommer Jakob inte dit.
3. Per kommer om och endast om Martin inte kommer eller Jakob inte kommer.

Frågan lyder: kan alla komma till festen? Om inte, vem kan gå på festen utan att bryta mot någon regel?

Först måste vi skriva om de ovanstående utsagorna till satsvariabler och formler. Vi kallar satsvariablerna M, J och P (Martin, Jakob, Per), och var och en betyder en utsaga av typen ”Martin går på festen”. Den första regeln kan vi skriva så här: M ⇒ J — ”om M, så J”, alltså ”om Martin går på festen, så går Jakob på festen”.

Den andra regeln skriver vi så här. Regeln börjar med meningen ”Per kommer till festen eller …”, så vi behöver uppenbarligen en disjunktion. Tills vidare skriver vi: P ∨ … Nästa del av meningen säger: ”om Martin kommer dit, så kommer Jakob inte dit”. Det är en implikation, där vi dessutom måste använda en negation i högerledet. ”Jakob kommer inte” = ¬J. Hela implikationen blir: M ⇒ ¬J. Den kopplar vi på den förra disjunktionen: P ∨ (M ⇒ ¬J).

Den tredje regeln skriver vi så här: vi börjar med ”Per kommer om och endast om”. Det betyder en ekvivalens: P ⇔ … Sedan har vi ”Martin kommer inte eller Jakob kommer inte”, vilket vi skriver som ¬M ∨ ¬J. Vi sätter ihop det: (P ⇔ (¬M ∨ ¬J)).

Nu sätter vi in alla formler i tabellen och beräknar värdena:

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

Frågan var om alla tre killarna kan gå på den vilda festen. Svaret hittar vi i den första raden. Den motsvarar fallet då alla killar går — det visas av de tre ettorna i de tre första kolumnerna. Är alla villkor uppfyllda? Det första är det (den fjärde kolumnen), det andra också (den femte kolumnen), men det sista inte (den sista kolumnen), där står en nolla. Det betyder att om alla tre går, blir inte det tredje villkoret uppfyllt.

Vi söker alltså de rader där det på de positioner som motsvarar villkoren (alltså de tre sista kolumnerna) bara står ettor. En etta betyder att villkoret är uppfyllt. Vi ser att det inträffar i två fall. När Jakob och Per går men inte Martin, och sedan när bara Per går.

Du kan också räkna ut det genom att lägga till formeln ϕ i tabellen, som är konjunktionen av alla tre villkor. Den blir alltså: ϕ = ((M ⇒ J) ∧ (P ∨ (M ⇒ ¬J)) ∧ (P ⇔ (¬M ∨ ¬J))). Den visar det vi vill ha — att alla formler (alla villkor) är uppfyllda. Tabellen skulle då se ut så här:

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

Några exempel med sanningstabeller

Eftersom jag har skrivit ett program som automatiskt kan bygga hela tabellen av en given formel, måste jag förstås utnyttja det ordentligt, och därför följer ytterligare några lösta formler:

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

$$\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). Tabell:

$$\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). Tabell:

$$\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)). Tabell:

$$\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). Tabell:

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