Utsagnslogikk

Utsagnslogikk (matematisk logikk) er et uttrykksmiddel i matematikken, og vi møter det under ulike navn og i alle slags matematiske setninger.

Hva logikk er til for

Logikk er et fagområde som handler om resonnering, sannhet, bevisbarhet og motbevisbarhet. I logikken er det bare formen på en påstand som teller. Vi er ikke opptatt av hva som konkret blir sagt, og heller ikke av psykologiske tolkninger og lignende.

Hvis vi for eksempel har setningen «tallet 2 er et partall og samtidig et oddetall», kan vi slutte at hele setningen er usann, fordi tallet 2 ikke er et oddetall. Slike ting er det logikken i alminnelighet tar seg av.

Utsagn

Grunnlaget for utsagnslogikken er naturlig nok utsagnet. Et utsagn er enhver påstandssetning der vi kan avgjøre sannhetsverdien. Eksempler på enkle utsagn:

• Oslo er hovedstaden i Norge.
• Det naturlige tallet fem er et oddetall.
• HTML er et programmeringsspråk.
• To pluss tre er seks.

Alt dette er utsagn, enten de er sanne (de to første) eller usanne (de to siste). Et spørsmål er for eksempel ikke et utsagn, og det er heller ikke en setning der vi ikke kan avgjøre sannhetsverdien entydig. Her er flere eksempler:

• Blir Bergen den regnfulleste byen i Norge også neste år?
• Grønn er den peneste fargen.

Den første setningen kan ikke være et utsagn, fordi den er et spørsmål. For den andre setningen kan vi ikke avgjøre om den er et sant eller et usant utsagn. En slik setning kalles en hypotese (antakelse).

Klassisk matematisk logikk har vanskelig for å håndtere vage setninger som «Jakob er høy» eller «Emma er en god sanger». Slike utsagn håndteres bedre i for eksempel fuzzy logikk (uklar logikk), som er laget for å takle vaghet.

Atomært utsagn

I det første kapittelet hadde vi et eksempel på et utsagn, «tallet 2 er et partall og samtidig et oddetall». Et slikt utsagn kan vi kalle sammensatt, fordi det egentlig binder sammen to kortere utsagn: «tallet 2 er et partall» og «tallet 2 er et oddetall». Disse to utsagnene er knyttet sammen med konnektivet «og», eller «og samtidig».

Et atomært utsagn er altså et utsagn som vi ikke kan dele opp videre, det er i en viss forstand den enkleste påstanden vi kan komme med. De forrige eksemplene på utsagn var egentlig atomære utsagn:

• Oslo er hovedstaden i Norge.
• Det naturlige tallet fem er et oddetall.
• HTML er et programmeringsspråk.
• To pluss tre er seks.

Atomære utsagn skriver vi videre med små bokstaver fra alfabetet, vanligvis p, q, r, …, og vi kaller dem utsagnsvariabler.

Logiske konnektiver

Matematisk logikk bruker vanligvis et bestemt sett med logiske konnektiver. De fire grunnleggende er binære:

• p ∧ q er konjunksjonen av utsagn, som vi leser «utsagnet p og (samtidig) utsagnet q»
• p ∨ q er disjunksjonen av utsagn, som vi leser «utsagnet p eller utsagnet q»
• p ⇒ q er implikasjonen, som vi leser «hvis utsagnet p, så utsagnet q»
• p ⇔ q er ekvivalensen, som vi leser «utsagnet p hvis og bare hvis utsagnet q»

Konkrete eksempler på logiske konnektiver:

• I sentrum av Bergen regner det og samtidig skinner solen. (konjunksjon)
• I sentrum av Bergen regner det eller skinner solen. (disjunksjon)
• Apple er det kuleste firmaet og Steve Jobs er den kuleste fyren. (konjunksjon)
• Hvis du tar avføringsmiddel, så kommer du snart til å dri… (implikasjon)
• Hvis tallet x er delelig med fire, så er det også delelig med to. (implikasjon)
• Ingrid er pen og samtidig smart. (konjunksjon)
• Sangerinner er suksessrike hvis og bare hvis de er pene. (ekvivalens)
• Hvis det ikke regner, blir vi ikke våte. (implikasjon)
• Hvis katten min kan snakke, så er jeg den kinesiske guden for moro. (implikasjon)

Vi kjenner enda et vanlig konnektiv: negasjon. Negasjon skrives med symbolet ¬p.

Formel

Med utsagnsvariabler (atomære utsagn) og logiske konnektiver kan vi bygge opp mer kompliserte utsagn, som vi kaller formler. Alle eksemplene i den forrige listen med setninger var egentlig formler, for vi hadde to atomære formler, for eksempel «I sentrum av Bergen regner det» og «solen skinner», og knyttet dem sammen med logiske konnektiver. I det første tilfellet brukte vi konnektivet «og samtidig» og fikk formelen «I sentrum av Bergen regner det og samtidig skinner solen», i det andre tilfellet brukte vi «eller» og fikk formelen «I sentrum av Bergen regner det eller solen skinner».

Formelt definerer vi en formel slik:

• Hver utsagnsvariabel (atomært utsagn) er en formel (mer presist kan vi si at den er en atomær formel).
• Hvis A og B er formler, er også ¬A, (A ∧ B), (A ∨ B), (A ⇒ B) og (A ⇔ B) formler.

Definisjonen gir mening: i det første punktet sier vi at hvert atomært utsagn også er en formel. Hvis vi har to atomære utsagn, for eksempel «I sentrum av Bergen regner det» og «solen skinner», har vi altså også to formler. Nå kan vi bruke det andre punktet og bygge en mer sammensatt formel, for eksempel slik:

• I sentrum av Bergen regner det og samtidig skinner solen.
• I sentrum av Bergen regner det eller solen skinner.
• Hvis solen skinner i sentrum av Bergen, så regner det.
• Solen skinner i sentrum av Bergen hvis og bare hvis det regner.

Formler trenger selvfølgelig ikke å være sanne. Nå har vi fått et nytt sett med formler, så vi kan bygge enda mer kompliserte formler. Hvis vi lar A=«I sentrum av Bergen skinner solen eller det regner.» (vi vet allerede at dette er en formel) og B=«det er en regnbue å se» (vi antar at det også er i sentrum av Bergen, så vi slipper å gjenta det hele tiden), kan vi lage flere formler. Parentesene i setningene viser bare hvilke deler konnektivet gjelder for.

• A ∧ B: (I sentrum av Bergen skinner solen eller det regner) og samtidig (det er en regnbue å se).
• A ∨ B: (I sentrum av Bergen skinner solen eller det regner) eller (det er en regnbue å se).
• A ⇒ B: (Hvis solen skinner eller det regner i sentrum av Bergen), så (er det en regnbue å se).
• A ⇔ B: (I sentrum av Bergen skinner solen eller det regner) hvis og bare hvis (det er en regnbue å se).

Dette er alle formler. Så vi kan igjen ta en av disse formlene og knytte en ny formel til den. Slik kan vi for eksempel lage et rart ordmonster som «Hvis solen skinner eller det regner i sentrum av Bergen eller det er en regnbue å se, så skinner solen eller det regner hvis og bare hvis det er en regnbue å se.»

I neste del skal vi se på sannhetsverdien til formler.