Logika a znalostní systémy: dopředné a zpětné řetězení, rezoluce a expertní systémy

Znalostní báze, vyplývání a kontrola modelů, Hornovy klauzule, dopředné a zpětné řetězení, rezoluce, Prolog a expertní systémy od MYCINu po znalostní grafy — na malém systému, který pozná zvíře.

15 minut Matěj Žalmánek 2026-10-15

Série Základy AI Díl 24 z 83

Celá osnova série 83 z 83 témat hotovo

Co si odnesete

Co znamená, že z báze znalostí něco vyplývá, a proč je kontrola všech možných světů nepoužitelně pomalá.
Jak dopředné a zpětné řetězení odvozují z pravidel „když–pak“ a kdy použít které.
Proč expertní systémy uspěly i narazily a kde ručně psané znalosti žijí dodnes.

Co se hodí znát předem: Logika a důkazy: pravidla, podle kterých se v AI uvažuje

Než se stroje začaly učit z dat, zkoušeli lidé umělou inteligenci naučit ručně: sepsat, co ví odborník, jako pravidla „když–pak“, a nechat počítač, aby z nich vyvozoval závěry. Tak vznikly expertní systémy sedmdesátých a osmdesátých let, které diagnostikovaly infekce nebo sestavovaly počítače na zakázku. Pak narazily na své hranice a přišla zima umělé inteligence. Myšlenky z nich ale nezmizely — žijí v Prologu, v databázích znalostí za vyhledávači i v kontrole toho, co tvrdí jazykové modely.

Navazuje na díl Logika a důkazy, kde najdete spojky, implikaci a modus ponens.

1. Znalostní báze a odvozovací stroj

Definice — znalostní báze

Nechť 𝒫 je konečná množina výrokových symbolů a 𝓛(𝒫) množina všech vět (formulí) výrokové logiky nad 𝒫, tj. výrazů složených ze symbolů 𝒫 spojkami ¬, ∧, ∨, ⇒, ⇔ (viz Logika a důkazy). Znalostní báze je konečná množina vět

KB ⊆ 𝓛(𝒫),

které systém považuje za pravdivé. Systém s ní umí dvě operace:

sdělit větu β ∈ 𝓛(𝒫): KB ← KB ∪ {β};
zeptat se na větu α ∈ 𝓛(𝒫): odpověď je „ano“, právě když z KB vyplývá α (KB ⊨ α, definice v další kapitole), jinak „ne“.

Odvozovací stroj je algoritmus, který na operaci „zeptat se“ odpovídá.

Laicky řečeno

Znalostní báze je sešit, do kterého si zapisujete, co platí: „každé zvíře se srstí je savec“, „tohle zvíře má srst“. Odvozovací stroj je ten, kdo v sešitě listuje a odpovídá na otázky, i když odpověď v sešitě napsaná přímo není.

Tenhle přístup se jmenuje deklarativní. Neprogramujete postup, jak k odpovědi dojít — zapíšete jen, co platí, a postup je pořád stejný odvozovací stroj. Chcete systém naučit něco nového? Připíšete větu, nic nepřepisujete.

Celým dílem nás bude provázet malý expertní systém po vzoru učebnicového ZOOKEEPERu Patricka Winstona: dvanáct pravidel, ze kterých se podle pozorovaných vlastností pozná zvíře. Pozorovali jsme zvíře, které má srst, ostré zuby, drápy, je žlutohnědé a má černé pruhy. Co je to?

2. Vyplývání a modely

Definice — model a vyplývání

Nechť 𝒫 je konečná množina výrokových symbolů. Ohodnocení je funkce m : 𝒫 → {0, 1} (1 = pravda, 0 = nepravda); pravdivostní hodnotu m(α) ∈ {0, 1} rozšíříme na každou větu α ∈ 𝓛(𝒫) obvyklými pravdivostními tabulkami spojek. Ohodnocení m je model věty α, právě když m(α) = 1. Množina modelů věty α a znalostní báze KB ⊆ 𝓛(𝒫) je

M(α) = {m : 𝒫 → {0, 1} : m(α) = 1}, M(KB) = ⋂_{β ∈ KB} M(β)

(pro KB = ∅ je M(KB) množina všech 2^|𝒫| ohodnocení). Z KB vyplývá α, píšeme KB ⊨ α, právě když

M(KB) ⊆ M(α).

Slovy: α platí v každém ohodnocení, ve kterém platí všechny věty báze.

Laicky řečeno

Model je jeden „možný svět“ — jedna kombinace toho, co je pravda a co ne. Vyplývání znamená: ať je svět jakýkoli, pokud v něm platí všechno ze sešitu, platí v něm i α. Nejde o to, co je pravděpodobné, ale co je nevyhnutelné.

KB ⊨ α ⇔ M(KB) ⊆ M(α)

KB ⊨ α: to, na co se ptáme: plyne α z báze? Symbol ⊨ mluví o pravdě ve světech, ne o tom, jestli umíme něco odvodit
M(KB): světy, které báze připouští — ohodnocení, ve kterých platí všechny její věty najednou (báze je jejich konjunkce); jiné světy nás nezajímají, o těch báze tvrdí, že nenastaly
⊆: inkluze: v žádném připuštěném světě nesmí α chybět; jediný protipříklad by stačil, aby α nevyplývala
M(α): světy, ve kterých platí α; může jich být mnohem víc — α smí platit i tam, kde báze neplatí

Čím víc báze ví, tím méně světů připouští a tím víc z ní vyplývá. Prázdná báze připouští všechny světy, a tak z ní plynou jen tautologie.

Nejpřímočařejší způsob, jak vyplývání ověřit, je kontrola modelů: projít všechna ohodnocení, vybrat ta, ve kterých platí celá báze, a podívat se, jestli v nich platí i otázka. Naše báze má 24 výrokových symbolů („má srst“, „savec“, „tygr“…), takže ohodnocení je 2²⁴ = 16 777 216. Z nich je 13 440 modelů báze — a ve všech platí „tygr“. Odpověď zní ano, jenže za cenu šestnácti milionů řádků pravdivostní tabulky. S každým dalším symbolem se počet zdvojnásobí; u báze se stovkami symbolů to nedoběhne nikdy.

Příklad — kontrola modelů na třech symbolech

Báze KB = {prší ⇒ mokro, mokro ⇒ klouže, prší}, otázka α = klouže. Tři symboly dávají 2³ = 8 ohodnocení (1 = pravda, 0 = nepravda); implikace p ⇒ q je nepravdivá jen pro p = 1, q = 0.

prší	mokro	klouže	prší ⇒ mokro	mokro ⇒ klouže	`KB`
0	0	0	1	1	0
0	0	1	1	1	0
0	1	0	1	0	0
0	1	1	1	1	0
1	0	0	0	1	0
1	0	1	0	1	0
1	1	0	1	0	0
1	1	1	1	1	1

Celá báze platí jen v posledním řádku, takže |M(KB)| = 1. V tom řádku platí i „klouže“ — M(KB) ⊆ M(klouže), a proto KB ⊨ klouže. Algoritmus prošel 8 řádků a v každém vyhodnotil 3 věty báze; obecně stojí kontrola modelů O(2ⁿ · |KB|).

Příklad — odkud se vzalo 13 440 modelů

V každém modelu báze platí pět pozorovaných faktů a pravidla R1, R6 a R9 pak vynutí „savec“, „šelma“ a „tygr“. Těch 8 symbolů je pevně pravdivých. Zbylých 16 se rozpadne na skupiny, které spolu přes pravidla nesouvisejí, a počty jejich ohodnocení se násobí:

„dává mléko“ (R2 je splněné, savec platí) a „jí maso“ (R5 je splněné, šelma platí): libovolně, 2 · 2 = 4;
„má tmavé skvrny“, „gepard“ s pravidlem R8: tři ohodnocení — nesmí platit skvrny bez geparda;
„má kopyta“, „kopytník“, „má dlouhý krk“, „žirafa“, „zebra“ s R7, R10, R11: je-li kopytník nepravda, musí být nepravda i kopyta a zbylé tři symboly jsou volné (8 možností); je-li pravda, musí platit zebra, kopyta jsou volná a krk se žirafou mají 3 možnosti (2 · 3 = 6); celkem 14;
ptačí skupina „má peří“, „létá“, „snáší vejce“, „pták“, „neletí“, „plave“, „tučňák“ s R3, R4, R12: bez ptáka nesmí platit peří ani zároveň létá a vejce (3 možnosti) a poslední tři symboly jsou volné (8): 24; s ptákem je peří volné (2), létá a vejce volné (4) a z osmi ohodnocení „neletí, plave, tučňák“ je zakázané jen 1, 1, 0 (7): 56; celkem 80.

Dohromady 4 · 3 · 14 · 80 = 13 440 — přesně tolik, kolik jich kontrola modelů napočítala. A v každém z nich platí tygr, protože patří mezi pevně pravdivé symboly.

3. Odvozování: korektní a úplné

Místo procházení světů lze s větami manipulovat: z vět, které máme, vyrábět nové podle odvozovacích pravidel, jako je modus ponens. Tak to dělá i člověk.

Definice — odvozování, korektnost, úplnost

Nechť 𝓛 = 𝓛(𝒫) je množina vět a 𝓡 množina odvozovacích pravidel; každé pravidlo určuje, kterou větu smíme odvodit z kterých už odvozených vět (například modus ponens: z β a β ⇒ γ odvoď γ). Nechť KB ⊆ 𝓛 a α ∈ 𝓛. Odvození věty α z KB je konečná posloupnost vět β₁, …, β_k taková, že β_k = α a pro každé i = 1, …, k je β_i ∈ KB, nebo β_i vznikne některým pravidlem z 𝓡 z vět β₁, …, β_i−1. Píšeme

KB ⊢ α ⇔ existuje odvození α z KB.

Odvozovací postup (množina pravidel 𝓡, případně algoritmus, který je používá) je

korektní, právě když pro všechna KB ⊆ 𝓛 a α ∈ 𝓛 platí KB ⊢ α ⇒ KB ⊨ α — odvodí jen to, co opravdu vyplývá;
úplný, právě když pro všechna KB ⊆ 𝓛 a α ∈ 𝓛 platí KB ⊨ α ⇒ KB ⊢ α — odvodí všechno, co vyplývá.

Korektnost a úplnost se často tvrdí jen pro užší třídu bází a otázek (například báze z Hornových klauzulí a otázky tvaru jediného symbolu); pak se kvantifikátory „pro všechna“ berou jen přes tuto třídu.

Laicky řečeno

Symbol ⊨ je „je to tak“, symbol ⊢ je „umím to odvodit“. Korektní stroj nikdy nevymyslí nepravdu. Úplný stroj nic nepřehlédne. Chceme obojí — a pro obecnou logiku je to drahé, pro jednodušší tvar pravidel naopak levné.

Definice — Hornova klauzule

Nechť 𝒫 je množina výrokových symbolů. Literál je symbol p ∈ 𝒫 (kladný literál) nebo jeho negace ¬p (záporný literál). Klauzule je disjunkce konečně mnoha literálů ℓ₁ ∨ … ∨ ℓ_m, m ≥ 0 (pro m = 0 prázdná klauzule □, která je vždy nepravdivá). Klauzule je

Hornova, právě když z jejích literálů je nejvýš jeden kladný;
určitá, právě když z jejích literálů je právě jeden kladný.

Určitou klauzuli ¬p₁ ∨ … ∨ ¬p_k ∨ q (k ≥ 0, p₁, …, p_k, q ∈ 𝒫) zapisujeme jako pravidlo

p₁ ∧ p₂ ∧ … ∧ p_k ⇒ q,

kde p₁, …, p_k jsou předpoklady a q závěr. Pro k = 0 je to fakt q. (Že jde o tutéž větu, ukazuje rozbor níže.)

Laicky řečeno

Hornova klauzule je pravidlo „když platí tohle a tohle a tohle, pak platí tamto“. Žádné „nebo“ v závěru, žádné „není“ v předpokladech. Zní to jako velké omezení, ale většina odborných pravidel takový tvar má — a odvozování z nich je rychlé.

Proč je „disjunkce s nejvýš jedním kladným literálem“ totéž co pravidlo? Implikace A ⇒ q je ekvivalentní ¬A ∨ q a podle De Morganova zákona je ¬(p₁ ∧ … ∧ p_k) totéž co ¬p₁ ∨ … ∨ ¬p_k:

¬p₁ ∨ … ∨ ¬p_k ∨ q ≡ (p₁ ∧ … ∧ p_k) ⇒ q

¬p₁ ∨ … ∨ ¬p_k: záporné literály klauzule; dohromady říkají „některý předpoklad neplatí“ — a to je přesně negace konjunkce předpokladů
(p₁ ∧ … ∧ p_k): předpoklady pravidla — z disjunkce záporných literálů se staly podmínkou díky De Morganovi; žádný z nich nesmí být záporný, jinak by v pravidle stálo „když neplatí …“
q: jediný kladný literál, závěr; kdyby byly kladné dva, dostali bychom „pak q nebo r“ a odvozovací stroj by nevěděl, který z nich přidat
⇒: klauzule je pravdivá, když neplatí některý předpoklad nebo platí závěr — to je definice implikace; tvar pravidla jen jinak čte tutéž disjunkci

Například R6, savec ∧ má ostré zuby ∧ má drápy ⇒ šelma, je klauzule ¬savec ∨ ¬má ostré zuby ∨ ¬má drápy ∨ šelma.

4. Dopředné řetězení

Algoritmus — dopředné řetězení

Vstup: konečná množina KB určitých Hornových klauzulí nad 𝒫 — fakty F ⊆ 𝒫 a pravidla r s množinou předpokladů P(r) ⊆ 𝒫, |P(r)| ≥ 1, a závěrem z(r) ∈ 𝒫.
Výstup: množina Známé ⊆ 𝒫 všech odvozených symbolů.

Pro každé pravidlo r nastav počítadlo chybí(r) ← |P(r)| (kolik jeho předpokladů ještě není známo). Nastav Známé ← ∅ a do agendy (fronty) vlož všechny fakty z F.
Je-li agenda prázdná, skonči a vrať Známé.
Vyjmi z agendy symbol p. Je-li p ∈ Známé, pokračuj krokem 2; jinak Známé ← Známé ∪ {p}.
Každému pravidlu r s p ∈ P(r) sniž chybí(r) o 1. Klesne-li na 0, pravidlo vystřelí: vlož z(r) do agendy. Pokračuj krokem 2.

Zastavení: krok 4 proběhne pro každý symbol nejvýš jednou a každé pravidlo vystřelí nejvýš jednou, takže do agendy přibude jen konečně mnoho symbolů.

Věta. Nechť KB je konečná množina určitých Hornových klauzulí nad 𝒫 a q ∈ 𝒫. Pak dopředné řetězení odvodí q (tj. q ∈ Známé), právě když KB ⊨ q; je tedy pro výrokové symboly korektní i úplné. Počet jeho kroků je lineární v součtu délek klauzulí báze.

Laicky řečeno

Vyjdete z toho, co víte, a díváte se, které pravidlo se tím „odemklo“. Každý nový závěr může odemknout další pravidlo — jako domino. Skončíte, až už nic nového nepadne. Říká se tomu odvozování řízené daty.

Dopředné řetězení: fakty v pořadí zpracování, odvozené zeleně kroků: 8

Hned první pozorování „má srst“ odemkne pravidlo R1, které přidá „savec“ na konec agendy. Zbylá čtyři pozorování zatím nic nespustí, ale snižují počítadla. Když na řadu přijde savec, odemkne R6 (ostré zuby a drápy už známe) — vznikne „šelma“. Šelma odemkne R9 a máme tygra. Za osm kroků, žádné miliony řádků. Pravidlo R5 („savec, který jí maso, je šelma“) nevystřelilo nikdy: že zvíře jí maso, nevíme — a nepotřebujeme to vědět.

def dopredne(fakta, pravidla):
    chybi = {r.id: len(r.kdyz) for r in pravidla}
    zname, agenda = set(), list(fakta)
    while agenda:
        p = agenda.pop(0)
        if p in zname:
            continue
        zname.add(p)
        for r in pravidla:
            if p in r.kdyz:
                chybi[r.id] -= 1
                if chybi[r.id] == 0:          # všechny předpoklady známe
                    agenda.append(r.pak)
    return zname

Srdcem algoritmu je počítadlo u každého pravidla r s předpoklady P(r):

chybí(r) = |P(r)| − |P(r) ∩ Známé|

chybí(r): kolik předpokladů ještě nevíme; při chybí(r) = 0 pravidlo vystřelí — díky číslu to stroj pozná bez procházení seznamu předpokladů
|P(r)|: počáteční hodnota: na začátku nevíme nic, chybí všechny předpoklady
|P(r) ∩ Známé|: předpoklady, které už jsou zpracované; každý zpracovaný symbol sníží počítadlo o 1 u každého pravidla, kde se vyskytuje — a zpracuje se jen jednou, proto se nic nezapočítá dvakrát

Každý symbol se zpracuje nejvýš jednou a každý výskyt předpokladu sníží počítadlo nejvýš jednou — odtud lineární čas: počet kroků je úměrný součtu délek pravidel.

Jak počítadla chybí(r) během našeho běhu klesají (po zpracování symbolu v daném řádku; tučně nula, tedy výstřel). V řádku 0 je ještě chybí(r) = |P(r)| (barvy podle vzorce výše):

krok	zpracovaný symbol	R1	R5	R6	R9	R8
0	—	1	2	3	3	3
1	má srst	0	2	3	3	3
2	má ostré zuby	0	2	2	3	3
3	má drápy	0	2	1	3	3
4	je žlutohnědá	0	2	1	2	2
5	má černé pruhy	0	2	1	1	2
6	savec	0	1	0	1	2
7	šelma	0	1	0	0	1
8	tygr	0	1	0	0	1

R5 se zastaví na jedničce (chybí „jí maso“) a R8 pro geparda také (chybí „má tmavé skvrny“). Ostatní pravidla v tabulce nejsou; jejich předpoklady se v běhu buď vůbec neobjevily, nebo jen zčásti.

Věta — dopředné řetězení je korektní a úplné (důkaz)

Nechť KB je konečná množina určitých Hornových klauzulí nad 𝒫 a Známé výstup dopředného řetězení. Pak pro každé q ∈ 𝒫 platí q ∈ Známé ⇔ KB ⊨ q.

Korektnost (⇒). Každý odvozený symbol vznikl výstřelem pravidla, jehož všechny předpoklady už byly známé. V každém modelu báze platí fakty a (indukcí podle pořadí odvození) i dříve odvozené symboly, takže podle pravidla platí i nový závěr — je to modus ponens.

Úplnost (⇐). Po skončení vezměme ohodnocení m: pravda pro odvozené symboly (a fakty), nepravda pro všechny ostatní. To je model báze: kdyby nějaké pravidlo p₁ ∧ … ∧ p_k ⇒ q v m neplatilo, byly by všechny p_i odvozené a q ne — jenže pak by počítadlo pravidla kleslo na nulu a q by se odvodilo. Vyplývá-li tedy q z báze, platí v modelu m, a tedy bylo odvozeno. ∎

Model m je ten „nejskromnější“: věří jen tomu, co musí. Na naší bázi je to ohodnocení, kde platí právě 5 pozorování, savec, šelma a tygr.

5. Zpětné řetězení

Algoritmus — zpětné řetězení

Vstup: konečná množina KB určitých Hornových klauzulí nad 𝒫 (fakty F ⊆ 𝒫 a pravidla), cíl q ∈ 𝒫 a množina C ⊆ 𝒫 cílů, které se právě dokazují výš ve stromu (na začátku C = ∅).
Výstup: „dokázáno“, nebo „nedokázáno“.

Procedura ZPĚT(q, C):

Je-li q ∈ F, vrať „dokázáno“.
Je-li q ∈ C, vrať „nedokázáno“ (cíl by dokazoval sám sebe — cyklus).
Pro každé pravidlo p₁ ∧ … ∧ p_k ⇒ q z KB: zavolej postupně ZPĚT(p_i, C ∪ {q}) pro i = 1, …, k; vrátí-li všechna volání „dokázáno“, vrať „dokázáno“ (u prvního neúspěchu toto pravidlo opusť).
Neuspělo-li žádné pravidlo, vrať „nedokázáno“.

Zastavení: každé vnořené volání má C větší o jeden symbol a 𝒫 je konečná, takže hloubka rekurze je nejvýš |𝒫|.

Věta. Nechť KB je konečná množina určitých Hornových klauzulí nad 𝒫 a q ∈ 𝒫. Pak ZPĚT(q, ∅) vrátí „dokázáno“, právě když KB ⊨ q. Zpětné řetězení je tedy korektní a úplné a zkoumá jen symboly, které s cílem souvisejí přes pravidla.

Laicky řečeno

Začnete otázkou „je to tygr?“ a ptáte se, co by to potvrdilo: tygr je žlutohnědá šelma s černými pruhy. Je to šelma? Šelma je savec, který jí maso, nebo savec s ostrými zuby a drápy. Je to savec? … Dokud nedojdete k tomu, co víte. Tomu se říká odvozování řízené cílem.

def zpetne(cil, fakta, pravidla, cesta=()):
    if cil in fakta:
        return True                           # víme to přímo
    if cil in cesta:
        return False                          # cyklus: cíl dokazuje sám sebe
    for r in pravidla:
        if r.pak == cil:                      # NEBO: stačí jedno pravidlo
            if all(zpetne(p, fakta, pravidla, cesta + (cil,))
                   for p in r.kdyz):          # A: musí vyjít všechny předpoklady
                return True
    return False                              # nevíme, jak to dokázat

Funkce all se zastaví u prvního předpokladu, který nevyjde — proto se u R5 po neúspěchu s „jí maso“ už nic dalšího nezkoumá. Seznam cesta hlídá, aby se pravidla jako „a ⇒ b, b ⇒ a“ nezacyklila.

Zpětné řetězení pro cíl „tygr“: čísla pod uzly jsou pravidla

Algoritmus prozkoumal 11 cílů. Šelmu zkusil nejdřív dokázat pravidlem R5 — savce dokázal, ale na „jí maso“ narazil: to nevíme, a tak se R5 vzdal a zkusil R6, které vyšlo. Tady je zpětné řetězení silné: ví, co mu chybí. Expertní systém se v takové chvíli zeptá uživatele: „Jí to zvíře maso?“ Celý rozhovor s expertním systémem je tak vlastně zpětné řetězení nahlas.

Kdy co použít? Dopředné řetězení se hodí, když přicházejí data a chcete vědět, co z nich plyne — třeba monitorování výroby. Zpětné, když máte konkrétní otázku — diagnóza, dotaz do databáze. Kdybychom se zeptali „je to zebra?“, zpětné řetězení by to vyvrátilo po prozkoumání pouhých 5 cílů: zebra je kopytník a kopyta naše zvíře nemá.

6. Rezoluce: odvozování pro celou logiku

Hornovy klauzule nestačí na všechno. Věta „zvíře je savec nebo pták“ má v závěru „nebo“ a pravidlem ji nezapíšete. Pro libovolné výroky existuje jediné pravidlo, které stačí na všechno.

Definice — rezoluce

Nechť 𝒫 je množina výrokových symbolů. Věta je v konjunktivní normální formě (KNF), právě když je konjunkcí konečně mnoha klauzulí K₁ ∧ … ∧ K_s (klauzule viz definice Hornovy klauzule); klauzuli přitom chápeme jako množinu jejích literálů, takže opakovaný literál se počítá jednou.

Rezoluční pravidlo. Nechť p ∈ 𝒫, ℓ ∈ {p, ¬p} je literál, ¬ℓ literál k němu opačný (¬¬p chápeme jako p) a A, B klauzule (i prázdné). Z klauzulí (A ∨ ℓ) a (B ∨ ¬ℓ) smíme odvodit jejich rezolventu

(A ∨ ℓ), (B ∨ ¬ℓ) ⊢ (A ∨ B).

Věta γ je nesplnitelná, právě když nemá žádný model (M(γ) = ∅); totéž pro množinu vět.

Věta (důkaz sporem). Nechť KB ⊆ 𝓛(𝒫) a α ∈ 𝓛(𝒫). Pak KB ⊨ α, právě když je KB ∪ {¬α} nesplnitelná.

Věta (Robinson, 1965). Nechť S je konečná množina klauzulí. Pak S je nesplnitelná, právě když z S lze opakovaným použitím rezolučního pravidla odvodit prázdnou klauzuli □.

Rezoluční důkaz KB ⊨ α proto převede KB ∪ {¬α} do KNF a odvozuje rezolventy, dokud nevznikne □ (spor nalezen, α vyplývá), nebo dokud nepřibývají nové klauzule (α nevyplývá; nad konečnou 𝒫 je klauzulí konečně mnoho, takže to nastane). Postup je korektní a pro vyvracení úplný.

Laicky řečeno

Když platí „prší nebo je sucho“ a zároveň „není sucho nebo fouká“, pak „prší nebo fouká“ — sucho se vyruší (barvy podle vzorce níže). Rezoluce dokazuje sporem: předpokládá opak toho, co chce dokázat, a krátí klauzule tak dlouho, až zbude prázdná — spor. Opak tedy neplatí.

( A ∨ ℓ ), ( B ∨ ¬ℓ ) ⊢ ( A ∨ B )

ℓ, ¬ℓ: doplňkové literály — v každém světě je pravdivý právě jeden z nich, takže jednu z klauzulí nesplní; ta musí být splněná svým zbytkem. Proto ℓ ve výsledku chybí
A: zbytek první klauzule: platí, kdykoli je ℓ nepravda (pak první klauzuli drží jen A)
B: zbytek druhé klauzule: platí, kdykoli je ℓ pravda (pak ¬ℓ neplatí a druhou klauzuli drží B)

Ať je ℓ jakékoli, jeden ze zbytků platit musí — to je celý důkaz, že rezoluce je korektní. Z (ℓ) a (¬ℓ) vznikne prázdná klauzule, kterou nesplní nic: spor.

Algoritmus — převod do konjunktivní normální formy

Vstup: věta φ ∈ 𝓛(𝒫). Výstup: věta v KNF, která má stejné modely jako φ. Každý krok se opakuje, dokud ho jde použít; každý zachovává modely a skončí, protože odstraní či posune konečně mnoho spojek.

Odstraň ekvivalence: α ⇔ β nahraď (α ⇒ β) ∧ (β ⇒ α).
Odstraň implikace: α ⇒ β nahraď ¬α ∨ β.
Posuň negace až k symbolům: ¬¬α ≡ α, ¬(α ∧ β) ≡ ¬α ∨ ¬β, ¬(α ∨ β) ≡ ¬α ∧ ¬β (De Morgan).
Roznásob ∨ přes ∧: α ∨ (β ∧ γ) ≡ (α ∨ β) ∧ (α ∨ γ).

Příklad: (prší ∨ sněží) ⇒ mokro

krok 2: ¬(prší ∨ sněží) ∨ mokro

krok 3: (¬prší ∧ ¬sněží) ∨ mokro

krok 4: (¬prší ∨ mokro) ∧ (¬sněží ∨ mokro) — dvě klauzule, obě dokonce Hornovy.

Roznásobování ve 4. kroku může formuli exponenciálně prodloužit; řešiče proto v praxi používají Tseitinovu transformaci s pomocnými symboly, která dává jen lineárně delší výsledek (splnitelný právě tehdy, když původní formule).

Příklad: báze {prší ⇒ mokro, mokro ⇒ klouže, prší}, otázka „klouže“. V normální formě a s přidanou negací otázky:

(¬prší ∨ mokro), (¬mokro ∨ klouže), (prší), (¬klouže)

(prší) a (¬prší ∨ mokro) dají (mokro); (mokro) a (¬mokro ∨ klouže) dají (klouže); (klouže) a (¬klouže) dají prázdnou klauzuli □. Spor — „klouže“ z báze vyplývá. (Barvy podle rozboru rezolučního pravidla výše: v každém kroku je A prázdná, ℓ, ¬ℓ se vyruší a zbude B.)

Rezoluce je univerzální, ale obecně drahá: pro výrokovou logiku je problém splnitelnosti (SAT) NP-úplný. Moderní SAT řešiče přesto zvládají miliony proměnných — o nich byla řeč v dílu o omezujících podmínkách.

7. Pravidla s proměnnými a Prolog

Výroková logika má vadu: „Rex je savec“ a „Micka je savec“ jsou pro ni dva nesouvisející symboly. Pravidlo o všech savcích by se muselo opsat pro každé zvíře zvlášť. Predikátová logika z dílu o logice a důkazech to řeší proměnnými: ∀x : má_srst(x) ⇒ savec(x).

Definice — unifikace

Nechť jsou dány množiny proměnných (X, Y, …), konstant (jan, petr, …) a funkčních a predikátových symbolů. Term je proměnná, konstanta, nebo f(t₁, …, t_k) pro funkční symbol f a termy t₁, …, t_k; atomická formule je P(t₁, …, t_k) pro predikátový symbol P. Obojí souhrnně nazýváme výrazy.

Substituce (dosazení) je konečná množina θ = {X₁ / t₁, …, X_n / t_n}, kde X₁, …, X_n jsou navzájem různé proměnné a t_i ≠ X_i termy; zápis X / t čteme „za X dosaď t“ (není to dělení). Pro výraz E je Eθ výraz, který vznikne současným nahrazením každého výskytu X_i termem t_i.

Nechť E₁, E₂ jsou výrazy. Substituce θ je jejich unifikátor, právě když

E₁θ = E₂θ.

Unifikátor θ je nejobecnější, právě když pro každý unifikátor σ výrazů E₁, E₂ existuje substituce λ taková, že Eσ = (Eθ)λ pro každý výraz E — každý jiný unifikátor je jen jeho dalším zpřesněním. Například rodič(jan, Y) a rodič(X, petr) unifikuje (a nejobecněji) substituce {X / jan, Y / petr}. Algoritmus unifikace (níže) najde nejobecnější unifikátor, pokud nějaký unifikátor existuje, a jinak ohlásí neúspěch.

Laicky řečeno

Unifikace je „najdi, co dosadit, aby to sedělo“. Když pravidlo mluví o nějakém x a vy se ptáte na Rexe, unifikace dosadí x = Rex a pravidlo se dá použít. Řetězení pak funguje stejně jako ve výrokové logice, jen s dosazováním.

def unifikuj(a, b, s):                    # s: dosud nalezené dosazení (slovník)
    if s is None:
        return None                           # už dřív selhalo
    a, b = dosad(a, s), dosad(b, s)           # použij, co už víme
    if a == b:
        return s
    if je_promenna(a):
        return None if vyskytuje_se(a, b) else {**s, a: b}
    if je_promenna(b):
        return None if vyskytuje_se(b, a) else {**s, b: a}
    if slozeny(a) and slozeny(b) and a.jmeno == b.jmeno and len(a.args) == len(b.args):
        for x, y in zip(a.args, b.args):      # argumenty jeden po druhém
            s = unifikuj(x, y, s)
        return s
    return None                               # různé konstanty nebo predikáty

Na příkladu rodič(jan, Y) a rodič(X, petr): predikáty se shodují, takže se porovnají argumenty. jan a X dají {X / jan}, Y a petr přidají Y / petr. Naopak rodič(jan, Y) a rodič(petr, eva) neunifikují — jan a petr jsou různé konstanty. Kontrola vyskytuje_se brání dosazení typu X / f(X), které by vedlo k nekonečnému výrazu. (Prolog ji kvůli rychlosti standardně vynechává.)

Na zpětném řetězení s unifikací stojí Prolog (Alain Colmerauer, Marseille, 1972) — jazyk, ve kterém program je znalostní báze a spuštění programu je dotaz:

rodic(jan, petr).
rodic(petr, eva).

prarodic(X, Z) :- rodic(X, Y), rodic(Y, Z).

?- prarodic(jan, Kdo).
Kdo = eva.

Prolog se k cíli prarodic(jan, Kdo) dopracuje přesně jako náš strom u tygra: najde pravidlo, unifikuje X = jan, dokazuje rodic(jan, Y), najde Y = petr a pak rodic(petr, Z) s výsledkem eva.

8. Expertní systémy

Expertní systém je znalostní báze sepsaná s odborníkem a odvozovací stroj, obvykle se zpětným řetězením a s možností vysvětlit, proč k závěru došel — stačí přečíst strom, který jsme nakreslili výše. Nejznámější byly tři:

DENDRAL (Stanford, od roku 1965) určoval strukturu molekul z údajů hmotnostního spektrometru — první systém, který dělal práci vědců podle jejich vlastních pravidel.
MYCIN (Stanford, 70. léta) diagnostikoval bakteriální infekce krve a doporučoval antibiotika. Měl kolem šesti set pravidel a v hodnocení z roku 1979 obstály jeho návrhy stejně dobře jako návrhy stanfordských specialistů nebo lépe. V nemocnici se přesto nikdy nepoužíval.
XCON (firma DEC, od roku 1980) sestavoval konfigurace počítačů VAX podle objednávky. Měl tisíce pravidel a podle firmy šetřil desítky milionů dolarů ročně.

Medicína ale málokdy zná jistotu. MYCIN proto ke každému pravidlu připojil číslo, jak moc mu odborník věří:

Definice — faktor jistoty

Faktor jistoty tvrzení je číslo CF ∈ [−1, 1], které vyjadřuje míru důvěry v tvrzení: CF = 1 jistě platí, CF = −1 jistě neplatí, CF = 0 nevíme. Není to pravděpodobnost — přiřazuje ho odborník.

Nechť dvě různá pravidla podporují tentýž závěr s faktory CF₁, CF₂ ∈ (0, 1]. Výsledný faktor závěru je

CF = CF₁ + CF₂ · (1 − CF₁).

Pro záporné a smíšené faktory má MYCIN jiné kombinační vzorce, které v tomto dílu nepotřebujeme.

Laicky řečeno

Jedno vodítko vás přesvědčí na 0,6, druhé nezávislé na 0,5. Dohromady 0,6 + 0,5 · 0,4 = 0,8 (barvy podle vzorce níže) — druhé vodítko ubere polovinu ze zbývající nejistoty. Faktory jistoty nejsou pravděpodobnosti a nesplňují Bayesovu větu; později je nahradily bayesovské sítě, které mají v osnově vlastní díl.

CF = CF₁ + CF₂ · (1 − CF₁)

CF₁: důvěra z prvního pravidla; druhé pravidlo ji nemůže snížit, jen přidat
CF₂: jakou část zbývající nejistoty druhé pravidlo odstraní; kdyby se prostě sčítalo, dvě vodítka po 0,6 by dala nesmyslných 1,2
1 − CF₁: nejistota, která po prvním pravidle zbyla; jen z ní se ještě dá ubírat, a proto výsledek nikdy nepřekročí 1

Ekvivalentně 1 − CF = (1 − CF₁) · (1 − CF₂): zbylé nejistoty se násobí. Proto na pořadí pravidel nezáleží.

Příklad — tři vodítka a pravidlo s nejistými předpoklady

Tři vodítka 0,6, 0,5 a 0,5: nejdřív 0,6 + 0,5 · (1 − 0,6) = 0,8, pak 0,8 + 0,5 · (1 − 0,8) = 0,9 (barvy podle vzorce výše). Kontrola přes nejistoty: 1 − 0,4 · 0,5 · 0,5 = 0,9.

Nejisté předpoklady. V MYCINu (Shortliffe a Buchanan, 1975) dostane konjunkce předpokladů faktor svého nejslabšího článku a závěr pravidla faktor pravidla krát tento minimální faktor (pravidlo se přitom použije, jen když minimum přesáhne 0,2): CF(závěr) = CF(pravidlo) · min_i CF(p_i). Pravidlo s faktorem 0,7, jehož předpoklady mají faktory 0,9 a 0,6, tak přispěje závěru 0,7 · min(0,9; 0,6) = 0,42.

Koncem osmdesátých let se ukázaly hranice. Získávání znalostí bylo úzké hrdlo: odborník své know-how často neumí vyslovit jako pravidla a každé pravidlo stálo hodiny rozhovorů. Systémy byly křehké: o krok mimo svou oblast nevěděly nic a nevěděly ani, že nic nevědí. A tisíce pravidel se špatně udržovaly — nové pravidlo mohlo tiše odporovat starému. Trh s expertními systémy se zhroutil a přišla druhá zima umělé inteligence. Odpověď, která přišla potom, je opačná: znalosti nesepisovat, ale naučit se je z dat.

9. Znalosti v dnešní umělé inteligenci

Znalostní grafy. Google od roku 2012 odpovídá na mnoho dotazů ze znalostního grafu — sítě faktů typu (Praha, hlavní město, Česko). Volně dostupná Wikidata mají přes sto milionů položek. Je to znalostní báze, jen místo pravidel převažují fakta.
Pravidla tam, kde se musí dát zkontrolovat. Daňové výpočty, pojistné podmínky, schvalování úvěrů nebo bezpečnostní politiky se dodnes píšou jako pravidla: každé rozhodnutí jde vysvětlit a obhájit.
Jazykové modely a znalosti. Jazykový model má obrovské množství znalostí, ale rozprostřených ve vahách sítě — nedají se přečíst ani opravit po jednom a model si občas sebejistě vymýšlí. Proto se k němu připojují vyhledávání ve znalostní bázi (RAG) nebo nástroje a odvozovací stroje, které výsledek ověří.
Neurosymbolická AI spojuje obojí: síť rozpozná, co vidí, a logika z toho odvodí, co plyne. Příkladem jsou systémy, které hledají matematické důkazy: model navrhne krok a formální nástroj ho mechanicky zkontroluje.

10. Shrnutí

Znalostní báze je množina vět; KB ⊨ α znamená, že α platí ve všech modelech báze. Kontrola modelů to ověří, ale za cenu 2ⁿ ohodnocení.
Odvozování (⊢) pracuje s větami místo světů. Chceme, aby bylo korektní (nic nevymyslí) a úplné (nic nepřehlédne).
Pro Hornovy klauzule stačí dopředné řetězení (od faktů, řízené daty) nebo zpětné (od cíle, řízené otázkou); dopředné běží v lineárním čase, zpětné zkoumá jen to, co s cílem souvisí.
Pro celou výrokovou logiku je tu rezoluce a důkaz sporem; pro pravidla s proměnnými unifikace a Prolog.
Expertní systémy ukázaly sílu i hranice ručně psaných znalostí — a připravily půdu pro učení z dat.

Chcete si to osahat? Nechte AI agenta napsat expertní systém se zpětným řetězením, který se ptá na chybějící fakty — a vymyslete si vlastní pravidla pro něco, čemu rozumíte.

Máte na to jiný názor? Napište na support@coden-app.com.

Logika a znalostní systémy: dopředné a zpětné řetězení, rezoluce a expertní systémy

1. Znalostní báze a odvozovací stroj

2. Vyplývání a modely

3. Odvozování: korektní a úplné

4. Dopředné řetězení

5. Zpětné řetězení

6. Rezoluce: odvozování pro celou logiku

7. Pravidla s proměnnými a Prolog

8. Expertní systémy

9. Znalosti v dnešní umělé inteligenci

10. Shrnutí

Agent na vašem počítači, ovládaný z telefonu