Eksempler på utsagnslogikk

I denne artikkelen skal vi se på noen formler og de mulige sannhetsverdifordelingene deres ved hjelp av sannhetstabellmetoden.

Første eksempel

Vi skal finne ut når denne formelen er sann: ϕ = (p ∧ q) ∨ ¬q. Vi skriver utsagnsvariablene p og q inn i tabellen:

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

Deretter skriver vi inn den første delen av formelen, (p ∧ q), negasjonen ¬q og så hele formelen:

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

Nå regner vi ut verdiene for den tredje kolonnen, som er en enkel konjunksjon, og for negasjonen. Der setter vi bare inn de motsatte verdiene av dem som står i den andre kolonnen:

$$\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 slutt regner vi ut verdiene i den siste kolonnen. Den er hele formelen. I tabellen vår regner vi altså ut disjunksjonen «mellom den tredje og den fjerde kolonnen». 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}$$

Andre eksempel

Samme oppgave, en annen formel: ϕ = (p ∧ ¬q) ⇔ (¬p ⇒ q). Vi ser at formelen inneholder utsagnsvariablene p og q og negasjonene deres. Først lager vi derfor en tabell med de to variablene og negasjonene deres:

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

Deretter legger vi til formlene p ∧ ¬q og ¬p ⇒ q. Dem kan vi lett regne ut, for i tabellen har vi både sannhetsverdiene til de enkelte utsagnene og til negasjonene deres. Tabellen ser slik ut:

$$\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 slutt gjenstår det å regne ut hele formelen, som er ekvivalensen mellom de to siste kolonnene:

$$\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 eksemplet blir litt mer komplisert. Vi prøver tre utsagnsvariabler, og det gjør utregningen av tabellen mer omfattende. Formelen ser slik ut: ϕ = (¬(p ⇒ q)) ∧ (r ⇔ (¬p ∨ q)).

Siden vi har tre utsagnsvariabler, blir det totale antallet fordelinger av sannhetsverdier åtte:

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

Videre går vi frem på samme måte som i det forrige eksemplet, og vi regner ut hver kolonne i alle åtte radene. Hele tabellen ser slik ut:

$$\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 eksemplet gir vi ikke som en vanlig formel, men som en tekstoppgave. Tre venner vil gå på en vill fest der toppløse modeller deler ut forfriskninger, men de liker ikke hverandre så godt og stiller vilkår for når de vil komme. De heter Magnus, Jakob og Per. Reglene er slik:

1. Hvis Magnus kommer, så kommer også Jakob.
2. Per kommer på festen, eller, hvis Magnus kommer, kommer ikke Jakob.
3. Per kommer hvis og bare hvis Magnus ikke kommer eller Jakob ikke kommer.

Spørsmålet er om alle kan komme på festen. Hvis ikke, hvem kan komme på festen uten at noen av reglene brytes?

Først må vi skrive om de forrige utsagnene til utsagnsvariabler og formler. La oss kalle utsagnsvariablene M, J og P (Magnus, Jakob, Per). Hver av dem står for et utsagn av typen «Magnus kommer på festen». Den første regelen kan vi skrive om slik: M ⇒ J, «hvis M, så J», altså «hvis Magnus kommer på festen, så kommer Jakob på festen».

Den andre regelen skriver vi om slik. Regelen begynner med setningen «Per kommer på festen, eller …», så vi trenger åpenbart en disjunksjon. Foreløpig skriver vi: P ∨ … Neste del av setningen sier: «hvis Magnus kommer, kommer ikke Jakob». Det er en implikasjon, og på høyre side må vi i tillegg bruke en negasjon. «Jakob kommer ikke» = ¬J. Hele implikasjonen blir slik: M ⇒ ¬J. Den knytter vi til den forrige disjunksjonen: P ∨ (M ⇒ ¬J).

Den tredje regelen skriver vi om slik: vi begynner med «Per kommer hvis og bare hvis». Det betyr en ekvivalens: P ⇔ … Så har vi «Magnus kommer ikke eller Jakob kommer ikke», som vi skriver om slik: ¬M ∨ ¬J. Vi setter sammen: (P ⇔ (¬M ∨ ¬J)).

Nå setter vi alle formlene inn i tabellen og regner ut verdiene:

$$\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ørsmålet var om alle tre guttene kan gå på den ville festen. Svaret finner vi i den første raden. Den svarer til tilfellet der alle guttene kommer, og det vises med tre enere i de tre første kolonnene. Er alle vilkårene oppfylt? Det første er det (fjerde kolonne), det andre også (femte kolonne), men det siste er ikke det (siste kolonne), der står det en null. Det betyr at hvis alle tre kommer, blir ikke det tredje vilkåret oppfylt.

Vi leter altså etter de radene der det står bare enere i kolonnene som svarer til vilkårene (de tre siste kolonnene). En ener betyr at vilkåret er oppfylt. Vi ser at dette skjer i to tilfeller: når Jakob og Per kommer, men ikke Magnus, og når bare Per kommer.

Du kan også regne det ut ved å legge til formelen ϕ i tabellen, som er konjunksjonen av alle tre vilkårene. Den ser slik ut: ϕ = ((M ⇒ J) ∧ (P ∨ (M ⇒ ¬J)) ∧ (P ⇔ (¬M ∨ ¬J))). Den uttrykker det vi vil ha, nemlig at alle formlene (alle vilkårene) er oppfylt. Tabellen ser da slik ut:

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

Noen flere eksempler på sannhetstabellmetoden

Siden jeg har skrevet et program som automatisk kan bygge hele tabellen ut fra en gitt formel, må jeg bruke det ordentlig, og derfor følger det noen flere løste 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}$$