Přednáška 1 — Znalosti

Znalosti

Lidé uvažují na základě existujících znalostí a vyvozují závěry. Reprezentace znalostí a odvozování závěrů z nich se používají také v AI. V této přednášce prozkoumáme, jak takového chování dosáhnout.

Agenti založení na znalostech

Tito agenti uvažují pomocí práce s vnitřními reprezentacemi znalostí.

Co znamená „uvažovat na základě znalostí a dospět k závěru“?

Začněme příkladem z Harryho Pottera. Uvažujme následující tvrzení:

1. Pokud nepršelo, Harry dnes navštívil Hagrida.
2. Harry dnes navštívil Hagrida nebo Brumbála, ale ne oba.
3. Harry dnes navštívil Brumbála.

Na základě těchto tří tvrzení můžeme odpovědět na otázku „Pršelo dnes?“, přestože nám žádné z jednotlivých tvrzení přímo neříká, zda prší. Postupovat můžeme takto: ze třetího tvrzení víme, že Harry navštívil Brumbála. Z druhého víme, že navštívil buď Brumbála, nebo Hagrida. Můžeme tedy vyvodit:

4. Harry nenavštívil Hagrida.

Z prvního tvrzení dále plyne, že kdyby nepršelo, Harry by navštívil Hagrida. Ze čtvrtého však víme, že tomu tak nebylo. Proto můžeme vyvodit:

5. Dnes pršelo.

K tomuto závěru jsme použili logiku. Dnešní přednáška zkoumá, jak AI využívá logiku k odvozování nových závěrů z existujících informací.

Tvrzení

Tvrzení je výpověď o světě v jazyce pro reprezentaci znalostí. Pomocí tvrzení AI ukládá znalosti a používá je k odvozování nových informací.

Výroková logika

Výroková logika je založena na výrocích: tvrzeních o světě, která mohou být pravdivá nebo nepravdivá, jako předchozí tvrzení 1–5.

Výrokové symboly

Výrokové symboly jsou nejčastěji písmena (P, Q, R) používaná k reprezentaci výroků.

Logické spojky

Logické spojky jsou logické symboly propojující výrokové symboly a umožňující složitější uvažování o světě.

• Negace (Not, ¬) obrací pravdivostní hodnotu výroku. Jestliže například P znamená „Prší“, pak ¬P znamená „Neprší“.

  Pravdivostní tabulky porovnávají všechna možná přiřazení pravdivostních hodnot výrokům. Pomáhají nám lépe porozumět výsledkům propojení výroků různými logickými spojkami. Níže je naše první pravdivostní tabulka:

  P	¬P
  nepravda	pravda
  pravda	nepravda

• Konjunkce (And, ∧) spojuje dva různé výroky. Jestliže výroky P a Q spojíme pomocí ∧, je výsledný výrok P ∧ Q pravdivý pouze tehdy, jsou-li pravdivé oba: P i Q.

  P	Q	P ∧ Q
  nepravda	nepravda	nepravda
  nepravda	pravda	nepravda
  pravda	nepravda	nepravda
  pravda	pravda	pravda

• Disjunkce (Or, ∨) je pravdivá, pokud je pravdivý alespoň jeden z jejích argumentů. Pro pravdivost P ∨ Q tedy musí být pravdivý alespoň P, nebo Q.

  P	Q	P ∨ Q
  nepravda	nepravda	nepravda
  nepravda	pravda	pravda
  pravda	nepravda	pravda
  pravda	pravda	pravda

  Existují dva typy „nebo“: inkluzivní a exkluzivní. Exkluzivní „nebo“ je nepravdivé, pokud jsou pravdivé oba výroky současně, tedy P ∧ Q. Vyžaduje pravdivost právě jednoho argumentu, nikoli obou. Inkluzivní „nebo“ je pravdivé, pokud je pravdivé P, Q nebo P ∧ Q. U symbolu ∨ máme na mysli inkluzivní „nebo“.

Dvě doplňující poznámky nad rámec přednášky:

• Rozdíl mezi inkluzivním a exkluzivním „nebo“ může objasnit příklad. Inkluzivní: „Abys dostal moučník, musíš uklidit pokoj nebo posekat trávník.“ Když splníš obě povinnosti, sušenky přesto dostaneš. Exkluzivní: „Jako moučník můžeš mít buď sušenky, nebo zmrzlinu.“ V tomto případě nelze mít obojí.
• Exkluzivní „nebo“ se často zkracuje jako XOR a obvykle se označuje symbolem ⊕.

• Implikace (→) vyjadřuje „jestliže P, pak Q“. Jestliže například P znamená „Prší“ a Q „Jsem uvnitř“, pak P → Q znamená „Pokud prší, jsem uvnitř“. U implikace P → Q označujeme P jako předpoklad (antecedent) a Q jako důsledek (konsekvent).

  Je-li předpoklad pravdivý, je celá implikace pravdivá právě tehdy, je-li pravdivý také důsledek. To je přirozené: pokud prší a jsem uvnitř, tvrzení „Pokud prší, jsem uvnitř“ platí. Je-li předpoklad pravdivý a důsledek nepravdivý, je implikace nepravdivá: pokud jsem při dešti venku, uvedené tvrzení neplatí. Pokud je však předpoklad nepravdivý, implikace je vždy pravdivá, bez ohledu na důsledek. To může být matoucí. Z implikace P → Q nemůžeme zjistit nic, je-li P nepravdivé. V našem příkladu: pokud neprší, implikace neříká nic o tom, zda jsem uvnitř. Mohu být člověk, který téměř nikdy nevychází ven, i když neprší, nebo člověk, který bývá vždy venku, když neprší. Při nepravdivém předpokladu říkáme, že implikace je triviálně pravdivá.

  P	Q	P → Q
  nepravda	nepravda	pravda
  nepravda	pravda	pravda
  pravda	nepravda	nepravda
  pravda	pravda	pravda

• Ekvivalence (↔) je obousměrná implikace. Čteme ji „právě tehdy, když“. P ↔ Q odpovídá současně P → Q a Q → P. Jestliže P znamená „Prší“ a Q „Jsem uvnitř“, pak P ↔ Q znamená „Pokud prší, jsem uvnitř“ i „Pokud jsem uvnitř, prší“. Můžeme tak odvodit více než z prosté implikace. Je-li P nepravdivé, je nepravdivé i Q: pokud neprší, víme, že také nejsem uvnitř.

  P	Q	P ↔ Q
  nepravda	nepravda	pravda
  nepravda	pravda	nepravda
  pravda	nepravda	nepravda
  pravda	pravda	pravda

Model

Model je přiřazení pravdivostní hodnoty každému výroku. Připomeňme, že výroky jsou tvrzení o světě, která mohou být pravdivá nebo nepravdivá. Znalosti o světě reprezentujeme pomocí těchto pravdivostních hodnot. Model je tedy přiřazení pravdivostních hodnot, které poskytuje informaci o světě.

Jestliže například P znamená „Prší“ a Q „Je úterý“, může mít model podobu {P = True, Q = False}. Znamená to, že prší, ale není úterý. Možných modelů je více: například {P = True, Q = True} znamená, že prší a zároveň je úterý. Počet možných modelů je 2 umocněné na počet výroků. Máme zde dva výroky, tedy 2² = 4 možné modely.

Znalostní báze (KB)

Znalostní báze je množina tvrzení známých agentovi založenému na znalostech. AI dostává znalosti o světě v podobě tvrzení výrokové logiky, která může používat k odvozování dalších závěrů o světě.

Logický důsledek (⊨)

Pokud α ⊨ β, tedy z α logicky plyne β, je v každém světě, kde je pravdivé α, pravdivé také β.

Jestliže například α znamená „Je úterý v lednu“ a β „Je leden“, víme, že α ⊨ β. Je-li pravda, že je úterý v lednu, víme také, že je leden. Logický důsledek se liší od implikace. Implikace je logická spojka mezi dvěma výroky. Logický důsledek je naproti tomu vztah: jestliže jsou pravdivé všechny informace v α, jsou pravdivé také všechny informace v β.

Odvozování

Odvozování neboli inference je proces vyvozování nových tvrzení z předchozích.

V předchozím příkladu s Harrym Potterem jsme například odvodili tvrzení 4 a 5 z tvrzení 1, 2 a 3.

Nové znalosti lze z existujících odvozovat několika způsoby. Nejprve se podíváme na algoritmus kontroly modelů (model checking).

• Pro zjištění, zda KB ⊨ α, tedy zda můžeme na základě znalostní báze vyvodit pravdivost α:
  • Vyjmenujte všechny možné modely.
  • Pokud je α pravdivé v každém modelu, kde platí KB, pak z KB plyne α (KB ⊨ α).

Uvažujme následující příklad:

P: Je úterý. Q: Prší. R: Harry půjde běhat.
KB: (P ∧ ¬Q) → R (slovy: P a nikoli Q implikují R), P (P je pravdivé), ¬Q (Q je nepravdivé).
Dotaz: R (Chceme zjistit, zda je R pravdivé, nebo nepravdivé. Platí KB ⊨ R?)

Pro zodpovězení dotazu kontrolou modelů vyjmenujeme všechny možné modely.

Potom projdeme každý model a ověříme, zda v něm platí naše znalostní báze.

Nejprve ze znalostní báze víme, že P je pravdivé. Ve všech modelech, kde P není pravdivé, proto KB neplatí.

Podobně ze znalostní báze víme, že Q je nepravdivé. Ve všech modelech, kde Q je pravdivé, proto KB neplatí.

Nakonec zbývají dva modely. V obou je P pravdivé a Q nepravdivé; v jednom je R pravdivé, ve druhém nepravdivé. Protože KB obsahuje (P ∧ ¬Q) → R, víme, že je-li P pravdivé a Q nepravdivé, musí být R pravdivé. V modelu s nepravdivým R tedy KB neplatí, zatímco v modelu s pravdivým R platí.

V této tabulce existuje jediný model, ve kterém je znalostní báze pravdivá. Vidíme, že je v něm pravdivé také R. Podle definice logického důsledku: pokud je R pravdivé ve všech modelech, kde platí KB, pak KB ⊨ R.

Nyní se podíváme, jak lze znalosti a logiku reprezentovat v kódu.

from logic import *

# Create new classes, each having a name, or a symbol, representing each proposition.
rain = Symbol("rain")  # It is raining.
hagrid = Symbol("hagrid")  # Harry visited Hagrid
dumbledore = Symbol("dumbledore")  # Harry visited Dumbledore

# Save sentences into the KB
knowledge = And(  # Starting from the "And" logical connective, becasue each proposition represents knowledge that we know to be true.

    Implication(Not(rain), hagrid),  # ¬(It is raining) → (Harry visited Hagrid)

    Or(hagrid, dumbledore),  # (Harry visited Hagrid) ∨ (Harry visited Dumbledore).

    Not(And(hagrid, dumbledore)),  # ¬(Harry visited Hagrid ∧ Harry visited Dumbledore) i.e. Harry did not visit both Hagrid and Dumbledore.

    dumbledore  # Harry visited Dumbledore. Note that while previous propositions contained multiple symbols with connectors, this is a proposition consisting of one symbol. This means that we take as a fact that, in this KB, Harry visited Dumbledore.
    )

Pro spuštění algoritmu kontroly modelů potřebujeme následující informace:

• Znalostní bázi, ze které budeme odvozovat závěry
• Dotaz: výrok, u kterého zjišťujeme, zda plyne ze znalostní báze
• Symboly: seznam všech použitých symbolů, tedy atomických výroků (zde jde o rain, hagrid, a dumbledore)
• Model: přiřazení pravdivostních hodnot symbolům

Algoritmus kontroly modelů vypadá takto:

def check_all(knowledge, query, symbols, model):

    # If model has an assignment for each symbol
    # (The logic below might be a little confusing: we start with a list of symbols. The function is recursive, and every time it calls itself it pops one symbol from the symbols list and generates models from it. Thus, when the symbols list is empty, we know that we finished generating models with every possible truth assignment of symbols.)
    if not symbols:

        # If knowledge base is true in model, then query must also be true
        if knowledge.evaluate(model):
            return query.evaluate(model)
        return True
    else:

        # Choose one of the remaining unused symbols
        remaining = symbols.copy()
        p = remaining.pop()

        # Create a model where the symbol is true
        model_true = model.copy()
        model_true[p] = True

        # Create a model where the symbol is false
        model_false = model.copy()
        model_false[p] = False

        # Ensure entailment holds in both models
        return(check_all(knowledge, query, remaining, model_true) and check_all(knowledge, query, remaining, model_false))

Zajímají nás pouze modely, ve kterých je KB pravdivá. Pokud KB neplatí, v takových modelech nenastávají podmínky, o kterých víme, že jsou pravdivé. Proto jsou pro náš případ nepodstatné.

Příklad nad rámec přednášky: nechť P znamená „Harry hraje chytače“, Q „Oliver hraje brankáře“ a R „Nebelvír vyhraje“. Naše KB uvádí P, Q a (P ∧ Q) → R. Víme tedy, že P je pravdivé: Harry hraje chytače; Q je pravdivé: Oliver hraje brankáře; a jsou-li pravdivé P i Q, je pravdivé také R: Nebelvír vyhraje zápas. Nyní si představme model, kde Harry místo chytače hraje odrážeče, tedy ¬P. V takovém případě nás nezajímá, zda Nebelvír vyhrál, tedy zda je R pravdivé: v KB totiž máme informaci, že Harry hrál chytače, nikoli odrážeče. Zajímají nás pouze modely, kde jsou stejně jako v našem případě pravdivé P a Q.

Funkce check_all navíc pracuje rekurzivně. Vybere jeden symbol a vytvoří dva modely: v jednom je symbol pravdivý, v druhém nepravdivý. Potom zavolá samu sebe znovu, nyní pro modely lišící se přiřazenou hodnotou tohoto symbolu. Postup opakuje, dokud všechny symboly nemají přiřazené pravdivostní hodnoty a seznam symbols není prázdný. Jakmile je prázdný, což pozná podle if not symbols, každá instance funkce pro svůj model ověří pravdivost KB. Pokud KB v modelu platí, ověří funkce pravdivost dotazu, jak jsme popsali výše.

Znalostní inženýrství

Znalostní inženýrství je hledání způsobu, jak v AI reprezentovat výroky a logiku.

Procvičme si znalostní inženýrství na hře Clue.

Ve hře určitá osoba spáchala vraždu, určitým nástrojem a na určitém místě. Osoby, nástroje i místa reprezentují karty. Z každé kategorie se náhodně vybere jedna karta a vloží se do obálky. Úkolem hráčů je zjistit, kdo čin spáchal. Odhalují karty a z těchto vodítek odvozují, co musí být v obálce. K rozluštění záhady použijeme předchozí algoritmus kontroly modelů. Položky, o kterých víme, že souvisejí s vraždou, v modelu označujeme True, ostatní False.

Předpokládejme pro náš příklad tři osoby: Mustard, Plum a Scarlet; tři nástroje: nůž (knife), revolver (revolver) a klíč (wrench); a tři místa: taneční sál (ballroom), kuchyň (kitchen) a knihovnu (library).

Znalostní bázi začneme vytvářet přidáním pravidel hry. Víme jistě, že vrahem je jedna osoba, byl použit jeden nástroj a vražda se stala na jednom místě. Výrokovou logikou to lze vyjádřit takto:

(Mustard ∨ Plum ∨ Scarlet)

(knife ∨ revolver ∨ wrench)

(ballroom ∨ kitchen ∨ library)

Na začátku hry každý hráč vidí jednu osobu, jeden nástroj a jedno místo. Ví proto, že tyto položky s vraždou nesouvisejí. Hráči si obsah svých karet nesdělují. Předpokládejme, že náš hráč dostane karty Mustard, kuchyň a revolver. Víme tedy, že tyto položky s vraždou nesouvisejí, a do KB můžeme přidat:

¬(Mustard)

¬(kitchen)

¬(revolver)

Jindy můžeme ve hře vyslovit odhad určité kombinace osoby, nástroje a místa. Předpokládejme odhad, že Scarlet spáchala čin klíčem v knihovně. Pokud je chybný, můžeme do KB odvodit a přidat:

(¬Scarlet ∨ ¬library ∨ ¬wrench)

Předpokládejme nyní, že nám někdo ukáže kartu Plum. Můžeme tedy přidat:

¬(Plum)

do naší KB.

V tuto chvíli můžeme odvodit, že vrahem je Scarlet. Musí totiž jít o jednu z osob Mustard, Plum nebo Scarlet a máme důkazy, že první dvě to nejsou.

Přidání jediné další informace, například že místem nebyl taneční sál, může odhalit více. Nejprve aktualizujeme KB:

¬(ballroom)

Nyní můžeme z více předchozích údajů odvodit, že Scarlet spáchala vraždu nožem v knihovně. Knihovna plyne z toho, že místem musí být sál, kuchyň nebo knihovna a první dvě místa jsme vyloučili. Odhad Scarlet, knihovna, klíč byl však chybný. Alespoň jedna položka tohoto tvrzení proto musí být nepravdivá. Protože víme, že Scarlet i knihovna jsou správně, chybným prvkem je klíč. Použit musel být jeden ze tří nástrojů; jelikož to nebyl klíč ani revolver, můžeme odvodit, že to byl nůž.

Takto bychom informace přidali do znalostní báze v Pythonu:

# Add the clues to the KB
knowledge = And(

    # Start with the game conditions: one item in each of the three categories has to be true.
    Or(mustard, plum, scarlet),
    Or(ballroom, kitchen, library),
    Or(knife, revolver, wrench),

    # Add the information from the three initial cards we saw
    Not(mustard),
    Not(kitchen),
    Not(revolver),

    # Add the guess someone made that it is Scarlet, who used a wrench in the library
    Or(Not(scarlet), Not(library), Not(wrench)),

    # Add the cards that we were exposed to
    Not(plum),
    Not(ballroom)
)

Podívejme se i na jiné logické hádanky. Čtyři různé osoby — Gilderoy, Pomona, Minerva a Horace — jsou přiřazeny do čtyř různých kolejí: Gryffindor, Hufflepuff, Ravenclaw a Slytherin. V každé koleji je právě jedna osoba. Reprezentace podmínek výrokovou logikou je těžkopádná. Nejprve musíme každé možné přiřazení vyjádřit samostatným výrokem: MinervaGryffindor, MinervaHufflepuff, MinervaRavenclaw, MinervaSlytherin, PomonaGryffindor… Potom pro každou osobu potřebujeme disjunkci všech možných kolejí, abychom vyjádřili, že osoba do nějaké koleje patří:

(MinervaGryffindor ∨ MinervaHufflepuff ∨ MinervaRavenclaw ∨ MinervaSlytherin); opakujte pro každou osobu.

Abychom vyjádřili, že osoba zařazená do jedné koleje není zařazena do ostatních, zapíšeme:

(MinervaGryffindor → ¬MinervaHufflepuff) ∧ (MinervaGryffindor → ¬MinervaRavenclaw) ∧ (MinervaGryffindor → ¬MinervaSlytherin) ∧ (MinervaHufflepuff → ¬MinervaGryffindor)…

a tak dále pro všechny koleje a osoby. Řešení této neefektivnosti nabízí část o predikátové logice. Při dostatku vodítek však lze tento typ hádanky vyřešit kterýmkoli z obou typů logiky.

Výrokovou logikou lze řešit i hru Mastermind. První hráč uspořádá barvy do určitého pořadí a druhý je musí uhodnout. V každém tahu druhý hráč vysloví odhad a první vrátí číslo udávající počet správně umístěných barev. Simulujme hru se čtyřmi barvami. Druhý hráč navrhne toto pořadí:

První hráč odpoví „dvě“. Víme tedy, že dvě barvy jsou na správných pozicích a další dvě na nesprávných. Na základě této informace druhý hráč zkusí prohodit dvě barvy.

Nyní první hráč odpoví „nula“. Druhý tedy ví, že prohozené barvy byly původně umístěny správně; dvě nedotčené byly umístěny špatně. Prohodí je.

První hráč řekne „čtyři“ a hra končí.

Reprezentace výrokovou logikou by vyžadovala (počet barev)² atomických výroků. Pro čtyři barvy bychom měli výroky red0, red1, red2, red3, blue0… reprezentující barvu a pozici. Poté bychom výrokovou logikou vyjádřili pravidla: na každé pozici je jen jedna barva a barvy se neopakují; pravidla bychom přidali do KB. Nakonec přidáme všechna získaná vodítka. Zde víme, že první odhad měl dvě pozice správně a dvě špatně a druhý neměl správnou žádnou. Kontrola modelů nám na základě této znalosti může dát řešení.

Pravidla odvozování

Kontrola modelů je neefektivní, protože před odpovědí musí zvažovat každý možný model. Připomeňme, že dotaz R je pravdivý, pokud platí ve všech modelech, tedy přiřazeních pravdivostních hodnot, ve kterých platí KB. Pravidla odvozování umožňují vytvářet nové informace z existujících znalostí bez zvažování všech modelů.

Pravidla odvozování se obvykle znázorňují vodorovnou čarou: nahoře je premisa, dole závěr. Premisu tvoří známé informace; závěr je znalost, kterou z nich lze vyvodit.

V tomto příkladu tvoří premisu následující výroky:

• Pokud prší, Harry je uvnitř.
• Prší.

Na jejich základě většina rozumně uvažujících lidí vyvodí:

• Harry je uvnitř.

Modus ponens

Použité pravidlo se nazývá modus ponens. Tento název znamená, že pokud víme, že platí implikace a její předpoklad, platí také její důsledek.

Eliminace konjunkce

Je-li konjunkce pravdivá, je pravdivý každý z jejích atomických výroků. Pokud například víme, že Harry je přítelem Rona a Hermiony, můžeme odvodit, že Harry je přítelem Hermiony.

Eliminace dvojité negace

Dvakrát negovaný výrok je pravdivý. Uvažujme například „Není pravda, že Harry neudělal test“. Rozložme to na „Není pravda, že (Harry neudělal test)“, tedy „¬(Harry neudělal test)“, a nakonec „¬(¬(Harry udělal test))“. Obě negace se navzájem zruší a označí výrok „Harry udělal test“ za pravdivý.

Eliminace implikace

Implikace odpovídá disjunkci negovaného předpokladu a důsledku. Například „Pokud prší, Harry je uvnitř“ je ekvivalentní s „(Neprší) nebo (Harry je uvnitř)“.

To může být trochu matoucí. Podívejme se však na tuto pravdivostní tabulku:

Protože P → Q a ¬P ∨ Q mají stejná přiřazení pravdivostních hodnot, jsou logicky ekvivalentní. Jiný pohled je, že implikace platí při splnění jedné ze dvou podmínek. Zaprvé je při nepravdivém předpokladu triviálně pravdivá, jak jsme vysvětlili v části o implikaci. To vyjadřuje negované P v ¬P ∨ Q: je-li P nepravdivé, celý výrok je pravdivý. Zadruhé je při pravdivém předpokladu implikace pravdivá pouze s pravdivým důsledkem. Pokud jsou pravdivé P i Q, platí ¬P ∨ Q. Pokud P platí a Q ne, je ¬P ∨ Q nepravdivé.

Eliminace ekvivalence

Ekvivalence odpovídá implikaci a její obrácené implikaci spojeným konjunkcí. Například „Prší právě tehdy, když je Harry uvnitř“ odpovídá „Pokud prší, Harry je uvnitř“ a současně „Pokud je Harry uvnitř, prší“.

De Morganův zákon

Konjunkci lze za určitých podmínek převést na disjunkci. Uvažujme výrok „Není pravda, že Harry i Ron udělali test“. Z něj můžeme odvodit „Není pravda, že Harry udělal test“ nebo „Není pravda, že Ron udělal test“. Aby předchozí výrok platil, musí tedy platit alespoň jeden z výroků této disjunkce.

Podobně můžeme postupovat opačným směrem. Výrok „Není pravda, že Harry nebo Ron udělali test“ lze přeformulovat na „Harry neudělal test“ a současně „Ron neudělal test“.

Distributivita

Výrok se dvěma prvky seskupenými konjunkcí nebo disjunkcí lze distribuovat, tedy rozložit na menší jednotky obsahující konjunkce a disjunkce.

Znalosti a vyhledávací úlohy

Odvozování můžeme chápat jako vyhledávací úlohu s následujícími vlastnostmi:

• Počáteční stav: výchozí znalostní báze
• Akce: pravidla odvozování
• Přechodový model: nová znalostní báze po odvození
• Test cíle: ověření, zda je dokazované tvrzení ve znalostní bázi
• Funkce ceny cesty: počet kroků důkazu

Vidíme tak všestrannost vyhledávacích algoritmů: umožňují odvozovat nové informace z existujících znalostí pomocí pravidel inference.

Rezoluce

Rezoluce je silné pravidlo odvozování: pokud je jeden ze dvou atomických výroků disjunkce nepravdivý, druhý musí být pravdivý. Například z „Ron je ve Velké síni“ nebo „Hermiona je v knihovně“ a zároveň „Ron není ve Velké síni“ můžeme vyvodit „Hermiona je v knihovně“. Formálně lze rezoluci definovat takto:

Rezoluce využívá komplementární literály: dva stejné atomické výroky, z nichž jeden je negovaný a druhý nikoli, například P a ¬P.

Rezoluci lze dále zobecnit. Kromě „Ron je ve Velké síni“ nebo „Hermiona je v knihovně“ můžeme vědět také „Ron není ve Velké síni“ nebo „Harry spí“. Rezolucí můžeme odvodit „Hermiona je v knihovně“ nebo „Harry spí“. Formálně:

Komplementární literály umožňují vytvářet nová tvrzení odvozováním pomocí rezoluce. Algoritmy inference proto hledají komplementární literály, aby získaly nové znalosti.

Klauzule je disjunkce literálů, tedy výrokových symbolů nebo jejich negací, například P a ¬P. Disjunkce spojuje výroky pomocí „nebo“ (P ∨ Q ∨ R); konjunkce je spojuje pomocí „a“ (P ∧ Q ∧ R). Klauzule umožňují převést libovolné logické tvrzení do konjunktivní normální formy (CNF), tedy konjunkce klauzulí, například (A ∨ B ∨ C) ∧ (D ∨ ¬E) ∧ (F ∨ G).

Kroky převodu výroků do konjunktivní normální formy

• Odstraňte ekvivalence
  • Převeďte (α ↔ β) na (α → β) ∧ (β → α).
• Odstraňte implikace
  • Převeďte (α → β) na ¬α ∨ β.
• Pomocí De Morganových zákonů posouvejte negace dovnitř, dokud nejsou negovány pouze literály, nikoli klauzule.
  • Převeďte ¬(α ∧ β) na ¬α ∨ ¬β

Příklad převodu (P ∨ Q) → R do konjunktivní normální formy:

• (P ∨ Q) → R
• ¬(P ∨ Q) ∨ R /odstranění implikace
• (¬P ∧ ¬Q) ∨ R /De Morganův zákon
• (¬P ∨ R) ∧ (¬Q ∨ R) /distributivita

Nyní lze spustit algoritmus inference nad konjunktivní normální formou. Při rezoluci někdy vznikne klauzule obsahující tentýž literál dvakrát. Použije se pak faktorizace, při které se duplicita odstraní. Z (P ∨ Q ∨ S) ∧ (¬P ∨ R ∨ S) například rezolucí získáme (Q ∨ S ∨ R ∨ S). Duplicitní S lze odstranit a získat (Q ∨ R ∨ S).

Rezolucí literálu a jeho negace, tedy ¬P a P, vznikne prázdná klauzule (). Prázdná klauzule je vždy nepravdivá; nemohou totiž platit současně P i ¬P. Algoritmus rezoluce této vlastnosti využívá.

• Pro zjištění, zda KB ⊨ α:
  • Ověřte: je (KB ∧ ¬α) spor?
    • Pokud ano, pak KB ⊨ α.
    • Jinak logický důsledek neplatí.

Důkaz sporem se v informatice používá často. Je-li naše KB pravdivá a odporuje ¬α, znamená to, že ¬α je nepravdivé, a tedy α musí být pravdivé. Přesněji by algoritmus postupoval takto:

• Pro zjištění, zda KB ⊨ α:
  • Převeďte (KB ∧ ¬α) do konjunktivní normální formy.
  • Opakovaně ověřujte, zda lze rezolucí vytvořit novou klauzuli.
  • Pokud vytvoříme prázdnou klauzuli, tedy False, dospěli jsme ke sporu a dokázali KB ⊨ α.
  • Pokud však ke sporu nedojdeme a další klauzule už nelze odvodit, logický důsledek neplatí.

Následující příklad ukazuje, jak algoritmus může fungovat:

• Plyne A z (A ∨ B) ∧ (¬B ∨ C) ∧ (¬C)?
• Pro důkaz sporem nejprve předpokládejme, že A je nepravdivé. Získáme (A ∨ B) ∧ (¬B ∨ C) ∧ (¬C) ∧ (¬A).
• Nyní můžeme vytvářet nové informace. Jelikož C je nepravdivé (¬C), může být (¬B ∨ C) pravdivé pouze při nepravdivém B. Do KB tedy přidáme ¬B.
• Protože víme ¬B, může být (A ∨ B) pravdivé pouze při pravdivém A. Do KB tedy přidáme A.
• Naše KB nyní obsahuje komplementární literály A a ¬A. Jejich rezolucí dostaneme prázdnou klauzuli (). Ta je z definice nepravdivá, takže jsme dospěli ke sporu.

Predikátová logika

Predikátová logika, označovaná také jako logika prvního řádu, umožňuje vyjádřit složitější myšlenky stručněji než výroková logika. Používá dva typy symbolů: konstanty a predikáty. Konstanty reprezentují objekty; predikáty představují vlastnosti nebo vztahy přijímající argumenty a vracející pravdivostní hodnotu.

Vraťme se k hádance s osobami a jejich kolejemi v Bradavicích. Konstantami jsou osoby a koleje, například Minerva, Pomona, Gryffindor a Hufflepuff. Predikáty vyjadřují pravdivé či nepravdivé vlastnosti konstant. Například „Minerva je osoba“ zapíšeme jako Person(Minerva) a „Gryffindor je kolej“ jako House(Gryffindor). Všechny logické spojky fungují stejně jako dříve; například ¬House(Minerva) říká, že Minerva není kolej. Predikát může mít i dva nebo více argumentů a vyjadřovat vztah mezi nimi. BelongsTo například spojuje osobu a její kolej; příslušnost Minervy k Nebelvíru vyjádříme jako BelongsTo(Minerva, Gryffindor). Stačí tak jeden symbol pro každou osobu a jeden pro každou kolej. Je to stručnější než výroková logika, kde bychom pro každé přiřazení osoby ke koleji potřebovali samostatný symbol.

Univerzální kvantifikace

Kvantifikace v predikátové logice umožňuje vyjadřovat tvrzení bez konkrétní konstanty. Univerzální kvantifikace používá symbol ∀ a znamená „pro všechny“. Například ∀x. BelongsTo(x, Gryffindor) → ¬BelongsTo(x, Hufflepuff) říká, že pro každý symbol platí: patří-li do Nebelvíru, nepatří do Mrzimoru.

Existenční kvantifikace

Existenční kvantifikace je obdobou univerzální kvantifikace. Univerzální kvantifikace vytváří tvrzení platná pro všechna x; existenční kvantifikace vyjadřuje tvrzení platné alespoň pro jedno x. Používá symbol ∃. Například ∃x. House(x) ∧ BelongsTo(Minerva, x) znamená, že existuje alespoň jeden symbol, který je kolejí a do kterého Minerva patří. Jinými slovy: Minerva patří do nějaké koleje.

Oba typy kvantifikace lze použít v jednom tvrzení. Například ∀x. Person(x) → (∃y. House(y) ∧ BelongsTo(x, y)) znamená: jestliže x je osoba, existuje alespoň jedna kolej y, do které tato osoba patří. Každá osoba tedy patří do nějaké koleje.

Existují i jiné typy logiky. Spojuje je snaha reprezentovat informace. Jde o systémy, kterými v naší AI reprezentujeme znalosti.