Symbolsk logik
Michael Genesereth
Computer Science Department
Stanford University
Og selv om det er muligt at undervise i logik udelukkende på engelsk, er dette problematisk. Sætninger på naturligt sprog kan være komplekse, de kan være tvetydige, og hvis man ikke forstår betydningen af en sætning, kan det føre til fejl i ræsonnementet.
Selv meget enkle sætninger kan være besværlige. Her ser vi to grammatisk set lovlige sætninger. De er ens på nær det sidste ord, men deres struktur er helt forskellig. I den første er hovedverbet blomstrer, mens blomstrer i den anden er et navneord, og hovedverbet er sank.
Kirsebærblomsterne blomstrer i foråret.
Kirsebærblomsterne i foråret sank.
Som et andet eksempel på grammatisk kompleksitet kan vi se på følgende uddrag fra University of Michigans lejekontrakt. Sætningen i dette tilfælde er tilstrækkelig lang og den grammatiske struktur tilstrækkelig kompleks til, at folk ofte skal læse den flere gange for at forstå præcis, hvad den siger.
Universitetet kan opsige denne lejekontrakt, når lejeren, efter at have ansøgt om og underskrevet denne lejekontrakt forud for indskrivningen, ikke er berettiget til at indskrive sig eller undlader at indskrive sig på universitetet eller forlader universitetet på et hvilket som helst tidspunkt før udløbet af denne lejekontrakt, eller for overtrædelse af nogen bestemmelser i denne lejekontrakt, eller for overtrædelse af nogen af universitetets regler vedrørende kollegier eller af helbredsmæssige årsager, ved at give den studerende skriftlig meddelelse om denne opsigelse 30 dage før opsigelsens ikrafttrædelsesdato, medmindre liv, lemmer eller ejendom er i fare, lejeren sælger eller køber kontrollerede stoffer i strid med føderal, statslig eller lokal lovgivning, eller lejeren ikke længere er indskrevet som studerende, eller lejeren bruger eller er i besiddelse af skydevåben, sprængstoffer, brændbare væsker, fyrværkeri eller andre farlige våben i bygningen eller giver falsk alarm, i hvilke tilfælde et varsel på højst 24 timer vil være tilstrækkeligt.
Som et eksempel på tvetydighed, lad os antage, at jeg skriver sætningen Der er en pige i rummet med et teleskop. Se figur 6 for to mulige betydninger af denne sætning. Siger jeg, at der er en pige i et rum, der indeholder et teleskop? Eller siger jeg, at der er en pige i rummet, og at hun har et teleskop i hånden?
Figur 6 – Der er en pige i rummet med et teleskop.
Sådanne kompleksiteter og tvetydigheder kan undertiden være humoristiske, hvis de fører til fortolkninger, som forfatteren ikke havde til hensigt. Se eksemplerne nedenfor for nogle berygtede avisoverskrifter med flere fortolkninger. Ved at bruge et formelt sprog elimineres sådanne utilsigtede tvetydigheder (og på godt og ondt undgås også enhver utilsigtet humor).
|
Mængder, der styrter hen for at se paven, tramper 6 ihjel Journal Star, Peoria, 1980
|
||||
|
||||
|
||||
|
Fried Chicken Cooked in Microwave Wins Trip The Oregonian, Portland, 1981
|
Som illustration af de fejl, der opstår, når man ræsonnerer med sætninger i naturligt sprog, kan man se på følgende eksempler. I det første bruger vi transitiviteten af den bedre relation til at udlede en konklusion om den relative kvalitet af champagne og sodavand ud fra den relative kvalitet af champagne og øl og den relative kvalitet eller øl og sodavand. Så langt så godt.
Champagne er bedre end øl.
Øl er bedre end sodavand.
Derfor er champagne bedre end sodavand.
Se nu, hvad der sker, når vi anvender den samme transitivitetsregel i det tilfælde, der er illustreret nedenfor. Argumentets form er den samme som før, men konklusionen er noget mindre troværdig. Problemet i dette tilfælde er, at brugen af nothing her syntaktisk ligner brugen af beer i det foregående eksempel, men på engelsk betyder det noget helt andet.
Dårlig sex er bedre end ingenting.
Ingen ting er bedre end god sex.
Derfor er dårlig sex bedre end god sex.
Symbolsk logik eliminerer disse vanskeligheder ved hjælp af et formelt sprog til kodning af information. I betragtning af syntaksen og semantikken i dette formelle sprog kan vi give en præcis definition af begrebet logisk konklusion. Desuden kan vi opstille præcise ræsonnementsregler, der producerer alle og kun logiske konklusioner.
I denne henseende er der en stærk analogi mellem metoderne i formel logik og metoderne i gymnasial algebra. For at illustrere denne analogi kan man overveje følgende algebraopgave.
Xavier er tre gange så gammel som Yolanda. Xaviers alder og Yolandas alder summerer til tolv. Hvor gamle er Xavier og Yolanda?
Typisk er det første skridt i løsningen af et sådant problem at udtrykke oplysningerne i form af ligninger. Hvis vi lader x repræsentere Xaviers alder og y repræsentere Yolandas alder, kan vi indfange de væsentligste oplysninger om problemet som vist nedenfor.
x – 3y = 0
x + y = 12
Ved hjælp af algebraens metoder kan vi derefter manipulere disse udtryk for at løse problemet. Først trækker vi den anden ligning fra den første.
x – 3y = 0
x + y = 12
-4y = -12
Næst dividerer vi hver side af den resulterende ligning med -4 for at få en værdi for y. Ved at substituere tilbage i en af de foregående ligninger får vi så en værdi for x.
x = 9
y = 3
Se nu på følgende logiske problem.
Hvis Mary elsker Pat, så elsker Mary Quincy. Hvis det er mandag og det regner, så elsker Mary Pat eller Quincy. Hvis det er mandag og regner, elsker Mary så Quincy?
Som med algebraproblemet er det første skridt formalisering. Lad p repræsentere muligheden for, at Mary elsker Pat; lad q repræsentere muligheden for, at Mary elsker Quincy; lad m repræsentere muligheden for, at det er mandag; og lad r repræsentere muligheden for, at det regner.
Med disse forkortelser kan vi repræsentere de væsentlige oplysninger i dette problem med følgende logiske sætninger. Den første siger, at p indebærer q, dvs. at hvis Mary elsker Pat, så elsker Mary også Quincy. Den anden siger, at m og r indebærer p eller q, dvs. at hvis det er mandag og regner, så elsker Mary Pat eller Mary elsker Quincy.
| p | ⇒ | q | |
| m ∧ r | ⇒ | p ∨ q |
Sådan som med Algebra, Formel logik definerer visse operationer, som vi kan bruge til at manipulere udtryk. Den operation, der er vist nedenfor, er en variant af det, der kaldes Propositional Resolution. Udtrykkene over linjen er reglens præmisser, og udtrykket nedenunder er konklusionen.
| p1 ∧ …. ∧ pk | ⇒ | q1 ∨ … ∨ ql |
| r1 ∧ … ∧ rm | ⇒ | s1 ∨ … ∨ sn |
| p1 ∧ … ∧ pk ∧ r1 ∧ … ∧ rm | ⇒ | q1 ∨ … ∨ ql ∨ s1 ∨ … ∨ sn |
Der findes to uddybninger af denne operation. (1) Hvis en sætning på venstre side af den ene sætning er den samme som en sætning på højre side af den anden sætning, er det i orden at droppe de to symboler, med det forbehold, at kun ét sådant par kan droppes. (2) Hvis en konstant gentages på samme side af en enkelt sætning, kan alle forekomsterne, undtagen én, slettes.
Vi kan bruge denne operation til at løse problemet med Marys kærlighedsliv. Når vi ser på de to præmisser ovenfor, bemærker vi, at p forekommer på venstre side i den ene sætning og på højre side i den anden. Følgelig kan vi annullere p og dermed udlede konklusionen, at hvis det er mandag og regner, så elsker Mary Quincy eller Mary elsker Quincy.
| p | ⇒ | q | ||
| m ∧ r | ⇒ | p ∨ q | ||
| m ∧ r | ⇒ | q ∨ q | ||
Drop det gentagne symbol ud i højre side, kommer vi frem til den konklusion, at hvis det er mandag og regner, så elsker Mary Quincy.
| m ∧ r | ⇒ | q ∨ q | |
| m ∧ r | ⇒ | q | |
Dette eksempel er interessant, fordi det viser vores formelle sprog til kodning af logisk information. Som med algebra bruger vi symboler til at repræsentere relevante aspekter af den pågældende verden, og vi bruger operatorer til at forbinde disse symboler for at udtrykke information om de ting, som disse symboler repræsenterer.
Eksemplet introducerer også en af de vigtigste operationer i formel logik, nemlig resolution (i dette tilfælde en begrænset form af resolution). Resolution har den egenskab at være komplet for en vigtig klasse af logiske problemer, dvs. at det er den eneste operation, der er nødvendig for at løse ethvert problem i klassen.