Sannhetsverdien til formler

Når vi har noen atomære utsagn som vi setter sammen til en formel, kan vi prøve å avgjøre om hele formelen er sann eller usann.

Sannhetsverdien til et utsagn

Først skal vi presisere hva sannhetsverdien til et utsagn er. Når vi har et utsagn p, skal vi kunne avgjøre om det er sant eller usant. Et sant utsagn har sannhetsverdien 1 og et usant utsagn har sannhetsverdien 0.

En sannhetsverdifordeling er så en regel e som gir et gitt utsagn enten 0 eller 1. Når vi skriver e(p), vil vi finne ut om utsagnet p er sant. Hvis p er utsagnet «to ganger to er fire», er e(p) = 1, fordi dette er et sant utsagn. Hvis q er utsagnet «Jakob er en kvinne», er e(q) = 0, fordi Jakob ikke er en kvinne. e er altså en funksjon som forteller oss om et utsagn er sant.

Her er det viktig å være klar over at e ikke er en magisk funksjon som vet alt i verden. Den oppfører seg slik vi sier at den skal. Den vet ikke om Jakob er en mann eller en kvinne. Vi bør i starten av utregningen fastsette hvordan funksjonen skal oppføre seg. Hvis vi sier at Jakob er en kvinne, gir den oss e(q) = 1.

Sannhetsverdien til logiske konnektiver

For å kunne avgjøre sannhetsverdien til en formel må vi vite hvordan vi finner sannhetsverdien til de logiske konnektivene. Altså, når vi kjenner e(p) og e(q), hva blir sannhetsverdien til formlene p ∧ q, p ⇒ q og så videre.

Hvert logisk konnektiv oppfører seg forskjellig og brukes til noe forskjellig, så vi går gjennom hvert konnektiv for seg.

Sannhetsverdien til en konjunksjon

Konjunksjonen skrives p ∧ q og leses «p og samtidig q». Som eksempel kan vi ta formelen «Norge ligger i Nord-Europa og samtidig er hovedstaden Oslo». Når er hele denne setningen sann?

Selve konnektivet «og samtidig» hjelper oss å avgjøre det. Det sier uttrykkelig at begge utsagnene til venstre og til høyre skal være sanne. Hvis begge utsagnene p og q er sanne, altså e(p) = 1 og e(q) = 1, er også hele konjunksjonen sann. I motsatt fall, når enten det ene utsagnet er usant eller begge er usanne, er hele formelen usann.

Et eksempel på en konjunksjon som ikke er sann, er: «Glomma er en elv og samtidig renner Glomma gjennom Russland». Det er riktig at Glomma er en elv, men det er ikke riktig at den renner gjennom Russland, så hele konjunksjonen er ikke sann.

Tabellen nedenfor viser dette oversiktlig:

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

I de to første kolonnene står sannhetsverdiene til utsagnene p og q, og i den tredje står sannhetsverdien til formelen p ∧ q.

Sannhetsverdien til en disjunksjon

Disjunksjonen skrives p ∨ q og leses «p eller q». Eksempel: «Russland ligger i Europa eller i Asia.» Når er hele setningen sann?

For en disjunksjon er det nok at minst ett av alternativene er sant. Konnektivet «eller» gir oss et valg, og det er nok at enten den venstre eller den høyre delen er sann. Den eneste lille forskjellen fra hverdagsspråket er at det logiske eller er sant også når begge utsagnene er oppfylt samtidig. Det er ikke alltid vanlig, for i hverdagsspråket bruker vi ofte «eller» utelukkende, altså «enten … eller …»

Det finnes en klassisk vits om dette: en familie skal kjøpe ny bil hos en bruktbilforhandler. Faren sier til selgeren: «Vi har bestemt oss for å ta en blå eller en rød bil». Selgeren solgte dem begge bilene. Dette illustrerer forskjellen mellom det logiske og det muntlige eller: faren mente trolig at de skulle velge akkurat én av bilene, mens selgeren mente det var en gyldig mulighet å selge dem begge.

Setningen om Russland ovenfor er sann, fordi begge utsagnene er sanne. Setningen «tallet 7 er delelig med 3 eller tallet 7 er et primtall» er sann, fordi sju er et primtall. Det er riktignok ikke delelig med tre, men det gjør ikke noe. Sannhetstabellen:

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

Sannhetsverdien til en implikasjon

Implikasjonen skrives p ⇒ q og leses «hvis p, så q». Et eksempel på en implikasjon er setningen «hvis vi drikker mye vodka, så kaster vi opp». Når er setningen sann?

Den logiske implikasjonen er det mest lumske av alle konnektivene, og selv i hverdagsspråket blir den ofte misforstått og forvekslet med ekvivalens. La oss prøve å svare på spørsmålet om den omvendte implikasjonen q ⇒ p også gjelder.

Vi vet at hvis vi drikker mye vodka, så kaster vi opp. Gjelder det også at hvis vi kaster opp, så har vi drukket mye vodka? Det gjelder absolutt ikke, vi kan ha drukket en helt annen type alkohol og likevel blitt dårlige, eller vi kan ha blitt dårlige av noe helt annet. Den omvendte implikasjonen trenger altså ikke å gjelde automatisk. Hvis både p ⇒ q og q ⇒ p gjelder, er det en ekvivalens, se nedenfor.

Et annet eksempel: «hvis det regner i morgen, så tar Henrik med seg paraply». Og nå forteller jeg deg at Henrik tok med seg paraply. Spørsmålet er: regnet det den dagen? Mange har en tendens til å si at det selvfølgelig gjorde det, for Henrik tok jo med seg paraply da det skulle regne. Men slik er ikke den opprinnelige setningen bygd opp!

Henrik kan i virkeligheten ha tatt med seg paraply på grunn av noe annet som vi ikke aner noe om. Kanskje tar Henrik alltid med seg paraply når han skal besøke svigermoren, så han kan stikke ut øyet hennes. Eller han bestemte seg for å kjøpe en ny paraply og vil kaste den gamle. Alt dette er lovlige grunner til at Henrik kan ha tatt med seg paraply, selv om det ikke trengte å regne.

Nå kan vi svare på spørsmålet om når implikasjonen er sann. Når begge utsagnene er sanne, er implikasjonen helt sikkert sann: «hvis 42 er et naturlig tall, så er det positivt». Begge utsagnene er sanne, så hele implikasjonen er sann. Et annet eksempel er implikasjonen «hvis 42 er et naturlig tall, så er det negativt». Denne implikasjonen er ikke sann, fordi vi prøver å utlede noe som ikke er sant ut fra noe som er sant.

Til slutt gjenstår tilfellene der det første utsagnet er usant. I så fall er vi ikke lenger interessert i sannhetsverdien til det andre utsagnet. Når vi tar utgangspunkt i noe usant, kan vi si hva vi vil videre. Det er setninger som «hvis 1 er et negativt tall, så er jeg den kinesiske guden for moro» eller «hvis Beatles er et kjent byggefirma, så er solen blå.» I slike tilfeller er implikasjonen automatisk sann, fordi den rett og slett tar utgangspunkt i noe usant. Tabell:

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

Sannhetsverdien til en ekvivalens

Ekvivalensen skrives p ⇔ q og leses «p hvis og bare hvis q». Et eksempel på en ekvivalens er «tallet x er delelig med to hvis og bare hvis det er et partall». Når er hele setningen sann?

For en ekvivalens forventer vi at de to utsagnene henger så tett sammen at enten gjelder begge, eller så gjelder ingen av dem. Altså er tallet x enten et partall og samtidig delelig med to, eller så er det ingen av delene. Det kan ikke skje at x er et partall uten å være delelig med to.

Eksempel: «Lukas leser en bok hvis og bare hvis han sitter på do.» For at ekvivalensen skal være oppfylt, må Lukas lese en bok hver gang han sitter på do. Og samtidig må han sitte på do hver gang han leser en bok. Det kan ikke skje at han leser en bok for eksempel i sengen.

Vi kan uttrykke en ekvivalens ved hjelp av to implikasjoner. Så p ⇔ q kan vi skrive om til p ⇒ q og samtidig q ⇒ p. Tabell:

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

Negasjon

Negasjon er en unær operasjon, og vi skriver den med dette symbolet: ¬p. Negasjonen benekter det opprinnelige utsagnet. Hvis vi har utsagnet «Ingrid er sangerinne», får vi som negasjon utsagnet «Det er ikke sant at Ingrid er sangerinne», eller kortere «Ingrid er ikke sangerinne». Nesten alltid kan vi lage en negasjon ved å sette «Det er ikke sant at …» foran utsagnet.

Negasjonen snur sannhetsverdien, altså gjør den 0 til 1 og 1 til 0. Vi kan skrive ¬0 = 1 og ¬1 = 0.

Vær oppmerksom på noen lumske ting. La oss ta påstanden «kalk er hvit». Hva er negasjonen? Noen kan komme på at det er «kalk er svart», men det er ikke riktig! Når vi bruker regelen ovenfor, blir negasjonen utsagnet «det er ikke sant at kalk er hvit». Betyr det nødvendigvis at kalk må være svart? Nei, det kan for eksempel være rosa.

Tabell over alle konnektivene

$$\begin{array}{cccccc}p& q& p\wedge q& p\vee q& p\Rightarrow q& p\iff q\\ 1& 1& 1& 1& 1& 1\\ 1& 0& 0& 1& 0& 0\\ 0& 1& 0& 1& 1& 0\\ 0& 0& 0& 0& 1& 1\end{array}$$

Sannhetsverdien til en hel formel

Nå kan vi finne sannhetsverdien til to utsagn som er knyttet sammen med et logisk konnektiv. Hele formelen regner vi ut på helt tilsvarende måte. Hvis vi har formelen (p ⇒ q) ∧ r, får vi i det øyeblikket vi regner ut formelen (p ⇒ q) for eksempel til 1, en vanlig konjunksjon 1 ∧ r, som vi allerede kan løse.

Ved å bruke de enkleste logiske konnektivene etter tur kommer vi frem til sannhetsverdien til hele formelen. Ofte bruker vi til dette den såkalte sannhetstabellmetoden, som er beskrevet nedenfor.

Sannhetstabellmetoden

Sannhetstabellmetoden brukes når vi skal regne ut mer kompliserte formler. I de første n kolonnene skriver vi de n utsagnsvariablene som formelen inneholder, og i de neste kolonnene setter vi etter tur inn delformlene som formelen består av. Det blir tydeligere med et eksempel:

La oss ta formelen (p ∨ q) ∧ (q ⇒ p). I begynnelsen skriver vi alle utsagnsvariablene inn i tabellen, altså p og q, og alle kombinasjoner av sannhetsverdiene deres:

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

Deretter skriver vi inn kolonner for delformlene p ∨ q og q ⇒ p.

$$\begin{array}{cccc}p& q& p\vee q& q\Rightarrow p\\ 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

Nå regner vi ut disse formlene og fyller inn nuller eller enere i kolonnene. I tabellen har vi all informasjonen vi trenger. Når vi regner ut p ∨ q i den første raden, setter vi inn 1 for p og 1 for q. Da får vi uttrykket 1 ∨ 1. Verdien av dette uttrykket er igjen 1, så vi skriver en ener i tabellen:

$$\begin{array}{cccc}p& q& p\vee q& q\Rightarrow p\\ 1& 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

Slik fyller vi etter tur ut hele tabellen:

$$\begin{array}{cccc}p& q& p\vee q& q\Rightarrow p\\ 1& 1& 1& 1\\ 1& 0& 1& 1\\ 0& 1& 1& 0\\ 0& 0& 0& 1\end{array}$$

Nå gjenstår det å regne ut hele formelen. La oss kalle den φ = (p ∨ q) ∧ (q ⇒ p). Vi legger til en kolonne med φ i tabellen og regner den ut, og denne gangen bruker vi de to forrige kolonnene.

$$\begin{array}{ccccc}p& q& p\vee q& q\Rightarrow p& \phi \\ 1& 1& 1& 1& 1\\ 1& 0& 1& 1& 1\\ 0& 1& 1& 0& 0\\ 0& 0& 0& 1& 0\end{array}$$

Tabellen er nå komplett og forteller oss sannhetsverdien til formelen for alle mulige fordelinger. Hvis for eksempel e(p) = 1 og samtidig e(q) = 1, er formelen sann. Hvis e(p) = 0 og e(q) = 1, er formelen ikke sann.

Legg merke til at vi ikke kan si at «formelen er sann». Denne setningen gir ikke mening, for for å kunne si at formelen er sann, må vi si i hvilken fordeling formelen er sann. Vi kan altså si at «formelen φ er sann i fordelingen e₁ og ikke sann i fordelingen e₂».

Det eneste tilfellet der vi kan si at en formel er sann, er hvis den er sann i alle mulige fordelinger. For eksempel er formelen p ∨ ¬p sann i alle fordelinger, så vi kan si at formelen er sann. Tilsvarende gjelder for en formel som er usann i alle fordelinger.

Slike formler har sine egne navn. En formel som er sann i alle fordelinger, kalles en tautologi. En formel som ikke er oppfylt i noen fordeling, kalles en kontradiksjon.