Utsagnslogikk: syntaks, semantikk og entailment

Agentene i kapittel 2–10 hadde kunnskapen bygget inn i algoritmen: en heuristikk, en evalueringsfunksjon, en liste med begrensninger. En kunnskapsbasert agent skiller kunnskapen fra resonneringen. Den har en kunnskapsbase (knowledge base, KB), en mengde setninger skrevet i et formelt språk, og en inferensmekanisme som utleder nye setninger fra de gamle.

Agenten snakker med kunnskapsbasen gjennom to operasjoner, TELL og ASK. TELL legger en ny setning inn i KB, for eksempel det agenten nettopp har observert. ASK stiller et spørsmål, for eksempel hvilken handling som er best nå, og svaret må følge av det som er fortalt tidligere. I hvert tidssteg forteller agenten KB hva den oppfatter, spør hva den bør gjøre, og forteller KB hvilken handling den valgte.

Dette kalles den deklarative tilnærmingen: du forteller agenten hva som er sant, og lar inferensen finne ut hva som skal gjøres. Den prosedyrale tilnærmingen er å kode oppførselen direkte. I praksis kombineres de, men en deklarativ KB har en stor fordel: den kan utvides med nye fakta uten at noe annet i agenten skrives om.

Hvorfor logikk og ikke vanlig tekst? Fordi et formelt språk har to ting tekst mangler: en presis grammatikk som sier hva som er en setning, og en presis regel for når en setning er sann. Det er syntaksen og semantikken i de neste stegene, og sammen gjør de det mulig å avgjøre mekanisk om noe følger.

Reglene for hvilke setninger som er velformet, kalles syntaks (syntax). I utsagnslogikk (propositional logic) er byggesteinene utsagnssymboler som $P$, $Q$ og $V$, der hvert symbol står for et utsagn som er sant eller usant. $V$ kan for eksempel stå for «vinduet er åpent». Et symbol alene er en atomær setning (atomic sentence), og det er også konstantene $True$ og $False$.

Sammensatte setninger bygges med fem konnektiver. Hvert logisk konnektiv (logical connective) lager en ny setning av én eller to gamle. For to setninger $\alpha$ og $\beta$ er:

• •$\neg \alpha$ negasjonen, «ikke $\alpha$»,
• •$\alpha \wedge \beta$ konjunksjonen, «$\alpha$ og $\beta$»,
• •$\alpha \vee \beta$ disjunksjonen, «$\alpha$ eller $\beta$» (minst én av dem),
• •$\alpha \Rightarrow \beta$ implikasjonen, «hvis $\alpha$, så $\beta$», med $\alpha$ som premiss og $\beta$ som konklusjon,
• •$\alpha \iff \beta$ bikondisjonalen, «$\alpha$ hvis og bare hvis $\beta$».

Et symbol eller et negert symbol kalles en literal. Uten parenteser binder konnektivene i rekkefølgen $\neg$, $\wedge$, $\vee$, $\Rightarrow$, $\iff$, fra sterkest til svakest. $\neg P\vee Q\wedge R$ betyr altså $(\neg P)\vee (Q\wedge R)$. $P\Rightarrow Q\Rightarrow R$ er derimot tvetydig, fordi de to grupperingene betyr ulike ting, så skriv alltid parenteser der. $A\wedge B\wedge C$ er greit uten, fordi grupperingen ikke endrer betydningen. Når du er i tvil, sett parenteser. Det koster ingenting og fjerner all tvetydighet.

Syntaksen sier bare om en setning er skrevet riktig, ikke om den er sann. $P\wedge \vee Q$ er ikke en setning i det hele tatt, mens $P\wedge \neg P$ er en velformet setning som tilfeldigvis aldri kan være sann.

Setningene får mening gjennom semantikk (semantics), som sier når de er sanne. En modell (model) fastsetter sannhetsverdien til hvert symbol, for eksempel $V=sann$, $P=usann$. Med $n$ symboler finnes ƒantall modeller, $2^n$, fordi hvert symbol kan være sant eller usant uavhengig av de andre.

Sannheten til en sammensatt setning regnes ut nedenfra, med én regel per konnektiv. Reglene står i sannhetstabellen under, der S betyr sann og U usann. I utregninger skriver vi ofte 1 og 0 i stedet.

De fire første kolonnene er som i dagligtale. Implikasjonen er den som overrasker: $P\Rightarrow Q$ er usann bare når $P$ er sann og $Q$ er usann. Er premisset usant, er implikasjonen sann uansett hva $Q$ er. Tenk på den som et løfte, «hvis det regner, tar jeg med paraply»: løftet er bare brutt hvis det regner og du står uten paraply. Den logiske implikasjonen krever heller ingen årsakssammenheng. «Hvis 2 + 2 = 5, er månen av ost» er sann fordi premisset er usant. Det gir ƒimplikasjonseliminasjon, $\alpha \Rightarrow \beta \equiv \neg \alpha \vee \beta$. Bikondisjonalen er sann når de to sidene har samme sannhetsverdi.

Nå kan vi si presist hva det betyr at noe følger. $\alpha$ er en logisk konsekvens (entailment) av KB, skrevet $KB\models \alpha$, når $\alpha$ er sann i hver modell der KB er sann. Med $M(\alpha )$ for mengden modeller der $\alpha$ er sann gir det ƒlogisk konsekvens som delmengde:

Jo mer KB sier, jo færre modeller har den, og jo mer følger. KB er gjerne en konjunksjon av mange setninger, så hver ny setning med TELL kan bare krympe $M(KB)$.

Den mest direkte måten å avgjøre $\models$ på er modellsjekking (model checking): gå gjennom alle $2^n$ modellene, finn dem der KB er sann, og sjekk $\alpha$ i hver av dem. Finnes en modell der KB er sann og $\alpha$ usann, er det et moteksempel, og $KB/\models \alpha$.

En inferensalgoritme gir sunn inferens (sound inference) hvis den bare utleder setninger som faktisk følger, og fullstendig inferens (complete inference) hvis den kan utlede alt som følger. Skriv $KB⊢\alpha$ når algoritmen avleder $\alpha$. Sunn betyr at $⊢$ gir $\models$, og fullstendig at $\models$ gir $⊢$. Modellsjekking er begge deler, siden den ser på hver eneste modell. Prisen er tiden: $O(2^n)$ med $n$ symboler. Minnet er bare $O(n)$, fordi modellene kan genereres én om gangen. En vanlig måte er rekursiv opplisting: gi første symbol verdien sann og fortsett med resten, gi det så verdien usann og fortsett, og sjekk KB og $\alpha$ når alle symbolene har fått en verdi. Det er det samme treet som backtracking i kapittel 10, bare uten noen begrensninger som kutter grener.

I et smarthus går varmepumpa ($P$) bare når vinduet er lukket. Med $V$ for «vinduet er åpent» blir regelen $P\Rightarrow \neg V$. Er det kaldt ($K$) mens pumpa står, sender appen et varsel ($A$). Det er kaldt nå.

Figuren viser en nyanse. Varselet $A$ følger ikke av KB: i en modell der pumpa går, kan A være usann. Men $V\Rightarrow A$ følger, fordi et åpent vindu stopper pumpa.

Koden under sjekker en annen kunnskapsbase, om vifta på badet, og lar deg legge til symboler som ikke har noe med saken å gjøre.

import itertools

n_symboler = 3  # @param 3..14
vindu_aapent = 1  # @param 0..1

# F: fuktig på badet, L: vifta går, V: vinduet er åpent, X: ekstra symboler
symboler = ["F", "L", "V"] + [f"X{i}" for i in range(1, n_symboler - 2)]
kb = [
    lambda m: not m["F"] or m["L"] or m["V"],  # F ⇒ L ∨ V
    lambda m: not m["V"] or not m["L"],  # V ⇒ ¬L
    lambda m: m["F"],  # F
    lambda m: m["V"] == bool(vindu_aapent),  # V eller ¬V
]
alfa = lambda m: not m["L"]  # α = ¬L

sjekket = sanne = 0
moteksempel = None
for verdier in itertools.product([True, False], repeat=n_symboler):
    m = dict(zip(symboler, verdier))
    sjekket += 1
    if all(f(m) for f in kb):
        sanne += 1
        if not alfa(m) and moteksempel is None:
            moteksempel = m

print(f"Modeller sjekket: {sjekket}")
print(f"Modeller der KB er sann: {sanne}")
print(f"KB ⊨ α: {'nei' if moteksempel else 'ja'}")
if moteksempel:
    tekst = ", ".join(f"{s} = {int(moteksempel[s])}" for s in "FLV")
    print(f"Moteksempel: {tekst}")
else:
    print("Moteksempel: ingen")

Tre begreper beskriver en setning ut fra hvor mange modeller som gjør den sann:

• •En gyldig setning (valid sentence), eller tautologi, er sann i alle modeller, som $P\vee \neg P$.
• •En oppfyllbar setning (satisfiable sentence) er sann i minst én modell. Problemet med å avgjøre om en setning er oppfyllbar, kalles SAT, og det var det første problemet som ble vist å være NP-komplett.
• •En uoppfyllbar setning er sann i ingen modeller, som $P\wedge \neg P$.

Hver gyldig setning er oppfyllbar, men ikke omvendt. $\alpha$ er gyldig nøyaktig når $\neg \alpha$ er uoppfyllbar.

To setninger er ekvivalente, $\alpha \equiv \beta$, når de er sanne i nøyaktig de samme modellene. Forholdet kalles logisk ekvivalens (logical equivalence). Det er det samme som at hver av dem følger av den andre, ƒlogisk ekvivalens. $P\Rightarrow Q$ og $\neg Q\Rightarrow \neg P$ er ekvivalente, mens $P\Rightarrow Q$ og $Q\Rightarrow P$ ikke er det.

Begrepene henger sammen med $\models$ på to måter som brukes hele tiden i kapittel 12. Det første er deduksjonsteoremet (deduction theorem): $\alpha \models \beta$ hvis og bare hvis implikasjonen $\alpha \Rightarrow \beta$ er gyldig, ƒdeduksjonsteoremet. Og et bevis ved motsigelse (proof by refutation) bygger på ƒbevis ved motsigelse: $\alpha \models \beta$ hvis og bare hvis $\alpha \wedge \neg \beta$ er uoppfyllbar. Vil du vise at noe følger, kan du altså anta det motsatte og vise at det ikke finnes noen modell for KB sammen med denne antagelsen.

Eksamen ber ofte om å oversette en tekst til logikk. Arbeidet har to deler. Først velger du symboler og skriver hva hvert av dem betyr: «F: ferga går», ikke bare «F». Så oversetter du setning for setning, og her ligger fellene i småordene.

«X bare hvis Y» er den klassiske fella. Den sier at X ikke kan skje uten Y, altså $X\Rightarrow Y$, og ikke $Y\Rightarrow X$. «Du får billett bare hvis du betaler» betyr at billett krever betaling, ikke at betaling gir billett. «X hvis Y» er derimot $Y\Rightarrow X$. «X med mindre Y» betyr at X holder når Y ikke gjør det: $\neg Y\Rightarrow X$, som er ekvivalent med $X\vee Y$. «Eller» er inkluderende i logikken. Mener teksten «enten X eller Y, men ikke begge», skriv $(X\vee Y)\wedge \neg (X\wedge Y)$. «Y er nødvendig for X» betyr det samme som «X bare hvis Y», altså $X\Rightarrow Y$, mens «X er tilstrekkelig for Y» også er $X\Rightarrow Y$. «Verken X eller Y» er $\neg X\wedge \neg Y$, som etter De Morgan er det samme som $\neg (X\vee Y)$.

Når teksten er tvetydig, si hvilken lesning du velger. Det gir poeng, mens en stille feiltolkning ikke gjør det.