Begreper & referanser
Alle nøkkelbegrepene, formlene og referansene fra Førsteordens logikk, samlet på én side. Bruk denne som oppslag når du leser, øver flashcards eller tar quiz.
Begreper
Sentrale begreper fra kapittelet med korte definisjoner.
Det et logisk språk antar at verden består av. Utsagnslogikk antar bare fakta som er sanne eller usanne; førsteordens logikk antar objekter, relasjoner mellom dem og funksjoner (ontological commitment).
En ting i verden som setningene handler om, for eksempel en person, en tur eller en hytte. En modell har minst ett objekt (object).
Et symbol for en relasjon eller egenskap, som eller . Brukt på termer gir det en setning som er sann eller usann (predicate symbol).
Et symbol som gir nøyaktig ett objekt for objektene det brukes på, som , personen som guidet turen . Brukt på termer gir det en ny term, ikke en setning (function symbol).
Et navn på ett bestemt objekt, som eller . Navn skrives med stor forbokstav, variabler med liten (constant symbol).
Et uttrykk som peker på et objekt: en konstant, en variabel eller et funksjonssymbol brukt på termer, som . En term er aldri sann eller usann (term).
Et predikat brukt på termer, som , eller en likhet . Den er sann når relasjonen holder for objektene termene peker på (atomic sentence).
Koblingen som sier hvilket objekt hver konstant peker på, hvilke tupler hver relasjon holder for og hva hver funksjon gir. Modellen og tolkningen avgjør sammen om en setning er sann (interpretation).
Kvantoren : setningen etter er sann for hvert objekt kan stå for. Den hører naturlig sammen med (universal quantifier).
Kvantoren : setningen etter er sann for minst ett objekt. Den hører naturlig sammen med (existential quantifier).
Flere kvantorer etter hverandre, som . Like kvantorer kan bytte plass, men en og en kan generelt ikke byttes uten at betydningen endres (nested quantifiers).
Symbolet mellom to termer: er sann når de peker på samme objekt. Uten likhet kan du ikke si «minst to» eller «nøyaktig én» (equality).
En del av databasesemantikken: to ulike konstanter peker alltid på ulike objekter. I vanlig førsteordens logikk kan og være samme objekt (unique-names assumption).
En del av databasesemantikken: en atomær setning som ikke står i KB og ikke følger av den, er usann (closed-world assumption).
En del av databasesemantikken: det finnes ikke andre objekter enn dem konstantsymbolene navngir (domain closure).
Prosessen med å bygge en kunnskapsbase for et domene: avgrense oppgaven, samle kunnskap, velge vokabular, kode generelle regler og forekomsten, stille spørsmål og feilsøke (knowledge engineering).
Formler
Hver formel: hva den heter, hvordan den ser ut, og hva symbolene betyr.
Dualiteten mellom kvantorene
Flytter en negasjon forbi en kvantor ved å bytte kvantoren. Brukes når du negerer en setning og i CNF for førsteordens logikk. Vanlig feil: å flytte inn uten å bytte kvantor.
Mønsteret «alle P er Q»
Universell kvantor med implikasjon: for hvert objekt, hvis det er P, er det Q. Vanlig feil: , som sier at alt er både P og Q.
Mønsteret «noen P er Q»
Eksistensiell kvantor med konjunksjon: det finnes et objekt som er både P og Q. Vanlig feil: , som er sann så snart ett objekt ikke er P.
Minst to
To variabler kan peke på samme objekt, så trengs. Uten den sier formelen bare «minst én».
Nøyaktig én
Første del sier at det finnes ett objekt med egenskapen, andre del at ethvert objekt med egenskapen er det samme. Uten andre del sier formelen «minst én».
Kodesnutter
Kodesnutter fra kapittelet, vist literal.
Kvantorrekkefølge i tilfeldige modeller
import random antall_personer = 4 # @param 2..6seed = 3 # @param 0..20 random.seed(seed)personer = ["Ane", "Bo", "Cato", "Dina", "Eli", "Frid"][:antall_personer]# En modell er bare en tabell: hvert par (x, y) er med eller ikke, også (x, x).kjenner = {(x, y) for x in personer for y in personer if random.random() < 0.45} alle_kjenner_noen = all(any((x, y) in kjenner for y in personer) for x in personer)noen_kjent_av_alle = any(all((x, y) in kjenner for x in personer) for y in personer) print(f"Par i Kjenner: {len(kjenner)} av {len(personer) ** 2}")print(f"∀x ∃y Kjenner(x, y): {'sann' if alle_kjenner_noen else 'usann'}")print(f"∃y ∀x Kjenner(x, y): {'sann' if noen_kjent_av_alle else 'usann'}")if not alle_kjenner_noen: x = next(x for x in personer if not any((x, y) in kjenner for y in personer)) print(f"Moteksempel: {x} kjenner ingen, så ∀x ∃y faller")elif not noen_kjent_av_alle: mangler = [f"{y} (ikke av {next(x for x in sorted(personer, key=lambda x: x == y) if (x, y) not in kjenner)})" for y in personer] print(f"Moteksempel: ingen kjennes av alle: {', '.join(mangler)}")else: y = next(y for y in personer if all((x, y) in kjenner for x in personer)) print(f"Moteksempel: ingen; alle kjenner {y}, så begge er sanne")Prøv: sett seed til 4 og se at linja ∃y ∀x Kjenner(x, y): blir sann, og legg merke til at linja ∀x ∃y Kjenner(x, y): er sann i hver modell der den andre er det.
Telling med likhet
antall_ledere = 2 # @param 0..4 personer = ["Ane", "Bo", "Cato", "Dina", "Eli"]leder = set(personer[:antall_ledere]) def L(x): return x in leder # ∃x ∃y (L(x) ∧ L(y) ∧ ¬(x = y))minst_to = any(L(x) and L(y) and x != y for x in personer for y in personer)# Samme formel uten ¬(x = y): x og y kan være samme objektuten_likhet = any(L(x) and L(y) for x in personer for y in personer)# ∃x (L(x) ∧ ∀y (L(y) ⇒ y = x))noyaktig_en = any(L(x) and all(not L(y) or y == x for y in personer) for x in personer) ja = lambda b: "sann" if b else "usann"print(f"Ledere i modellen: {', '.join(sorted(leder)) or 'ingen'}")print(f"Minst to ledere: {ja(minst_to)}")print(f"Minst to uten ¬(x = y): {ja(uten_likhet)}")print(f"Nøyaktig én leder: {ja(noyaktig_en)}")Prøv: sett antall_ledere til 1 og se at Minst to uten ¬(x = y): blir sann, mens Minst to ledere: er usann og Nøyaktig én leder: sann.
Læringsmål
Hva du skal kunne etter å ha lest kapittelet.
- 01Formaliser norske setninger i førsteordens logikk med et oppgitt vokabular, eller lag vokabularet selv
- 02Skill mellom konstanter, predikater, funksjoner, termer og atomære setninger
- 03Avgjør om en formel er sann i en endelig modell ved å regne ut termene og lete etter moteksempler og vitner
- 04Forklar hvorfor rekkefølgen på og endrer betydningen, og negér kvantifiserte setninger med kvantordualiteten
- 05Bruk likhet til å uttrykke «minst to» og «nøyaktig én», og forklar hva de tre antagelsene i databasesemantikk gir
- 06Beskriv stegene i kunnskapsingeniørarbeid for et eget domene