Logický agent, výroková logika
Aleš Horák
E-mail: hales@fi.muni.cz
http://nlp.fi.muni.cz/uui/
Obsah:
Logický agent
Logika
Výroková logika
Úvod do umělé inteligence 5/12 1 / 36
Logický agent
Logický agent
znalosti prohledávání stavového prostoru – jen zadané funkce (přechodová
funkce, cílový test,. . . )
potřeba obecné formy umožňující kombinace znalostí
Úvod do umělé inteligence 5/12 2 / 36
Logický agent
Logický agent
znalosti prohledávání stavového prostoru – jen zadané funkce (přechodová
funkce, cílový test,. . . )
potřeba obecné formy umožňující kombinace znalostí
→ znalosti logického agenta
Úvod do umělé inteligence 5/12 2 / 36
Logický agent
Logický agent
znalosti prohledávání stavového prostoru – jen zadané funkce (přechodová
funkce, cílový test,. . . )
potřeba obecné formy umožňující kombinace znalostí
→ znalosti logického agenta
logický agent = agent využívající (formálně zadané) znalosti
(knowledge-based agent)
Úvod do umělé inteligence 5/12 2 / 36
Logický agent
Příklad využití znalostí
Pokud X + Y = 10 a X − Y = 4, kolik je X?
jak řešit?
Úvod do umělé inteligence 5/12 3 / 36
Logický agent
Příklad využití znalostí
Pokud X + Y = 10 a X − Y = 4, kolik je X?
jak řešit?
prohlédavat prostor všech možných hodnot např. do šířky
cíl = platnost obou omezujících podmínek
Úvod do umělé inteligence 5/12 3 / 36
Logický agent
Příklad využití znalostí
Pokud X + Y = 10 a X − Y = 4, kolik je X?
jak řešit?
prohlédavat prostor všech možných hodnot např. do šířky
cíl = platnost obou omezujících podmínek
problém s omezujícími podmínkami, proměnné X a Y
Úvod do umělé inteligence 5/12 3 / 36
Logický agent
Příklad využití znalostí
Pokud X + Y = 10 a X − Y = 4, kolik je X?
jak řešit?
prohlédavat prostor všech možných hodnot např. do šířky
cíl = platnost obou omezujících podmínek
problém s omezujícími podmínkami, proměnné X a Y
sečíst obě rovnice a vydělit 2
Úvod do umělé inteligence 5/12 3 / 36
Logický agent
Příklad využití znalostí
Pokud X + Y = 10 a X − Y = 4, kolik je X?
jak řešit?
prohlédavat prostor všech možných hodnot např. do šířky
cíl = platnost obou omezujících podmínek
problém s omezujícími podmínkami, proměnné X a Y
sečíst obě rovnice a vydělit 2
pravidla:
• if ((A = B) ∧ (C = D)) then tell((A + C) = (B + D))
• if (n · X = B) then tell(X = B/n)
řešení: X + Y + X − Y = 10 + 4
2 · X = 14
X = 7
Úvod do umělé inteligence 5/12 3 / 36
Logický agent
Příklad využití znalostí
Pokud X + Y = 10 a X − Y = 4, kolik je X?
jak řešit?
prohlédavat prostor všech možných hodnot např. do šířky
cíl = platnost obou omezujících podmínek
problém s omezujícími podmínkami, proměnné X a Y
sečíst obě rovnice a vydělit 2
pravidla:
• if ((A = B) ∧ (C = D)) then tell((A + C) = (B + D))
• if (n · X = B) then tell(X = B/n)
řešení: X + Y + X − Y = 10 + 4
2 · X = 14
X = 7
Použili jsme operace zachovávající pravdivost
tj. odvozování založené na logice, logickou inferenci
Úvod do umělé inteligence 5/12 3 / 36
Logický agent Báze znalostí
Báze znalostí
báze znalostí (Knowledge Base, KB) =
množina vět (formulí, tvrzení, sentences)
vyjádřených v jazyce reprezentace znalostí
Reprezentace
Svět
Věty VětaKB:
důsledek
Aspekty reálného
světa
Aspekt reálného
světa
sémantika
sémantika
vnímání
vyplývá
Úvod do umělé inteligence 5/12 4 / 36
Logický agent Báze znalostí
Báze znalostí
2 koncepty:
– reprezentace znalostí (knowledge representation)
– vyvozování znalostí (knowledge reasoning) → inference
Úvod do umělé inteligence 5/12 5 / 36
Logický agent Báze znalostí
Báze znalostí
2 koncepty:
– reprezentace znalostí (knowledge representation)
– vyvozování znalostí (knowledge reasoning) → inference
obecné znalosti – důležité v částečně pozorovatelných prostředích
(partially observable environments)
flexibilita logického agenta: schopnost řešit i nové úkoly
možnost učení nových znalostí
úprava stávajících znalostí podle stavu
prostředí
logický agent může odpovědět v principu na libovolnou otázku (podle KB)
na rozdíl od prohledávacích algoritmů, kde otázka je přímo zakódovaná
v zadání
Úvod do umělé inteligence 5/12 5 / 36
Logický agent Návrh logického agenta
Návrh logického agenta
agent musí umět: reprezentovat stavy, akce, . . .
zpracovat nové vstupy z prostředí
aktualizovat svůj vnitřní popis světa
odvodit skryté informace o stavu světa
odvodit vlastní odpovídající akce
Úvod do umělé inteligence 5/12 6 / 36
Logický agent Návrh logického agenta
Návrh logického agenta
agent musí umět: reprezentovat stavy, akce, . . .
zpracovat nové vstupy z prostředí
aktualizovat svůj vnitřní popis světa
odvodit skryté informace o stavu světa
odvodit vlastní odpovídající akce
přístupy k tvorbě agenta – deklarativní × procedurální (kombinace)
Úvod do umělé inteligence 5/12 6 / 36
Logický agent Návrh logického agenta
Návrh logického agenta
agent musí umět: reprezentovat stavy, akce, . . .
zpracovat nové vstupy z prostředí
aktualizovat svůj vnitřní popis světa
odvodit skryté informace o stavu světa
odvodit vlastní odpovídající akce
přístupy k tvorbě agenta – deklarativní × procedurální (kombinace)
co je potřeba pro návrh agenta:
znalostní hledisko – tvorba agenta → zadání znalostí pozadí, znalostí
domény a cílového požadavku
např. automatické taxi
• znalost mapy, dopravních pravidel, . . .
• požadavek – dopravit zákazníka na FI MU Brno
implementační hledisko – jaké datové struktury KB obsahuje +
algoritmy, které s nimi manipulují
Úvod do umělé inteligence 5/12 6 / 36
Logický agent Komponenty agenta
Komponenty agenta
komponenty logického agenta:
inferenční stroj (inference engine)
báze znalostí (knowledge base)
algoritmy nezávislé na doméně
znalosti o doméně
Úvod do umělé inteligence 5/12 7 / 36
Logický agent Komponenty agenta
Komponenty agenta
komponenty logického agenta:
inferenční stroj (inference engine)
báze znalostí (knowledge base)
algoritmy nezávislé na doméně
znalosti o doméně
obsah báze znalostí:
na začátku – tzv. znalosti pozadí (background knowledge)
axiom – tvrzení/pravidlo, které je dáno (ne vyvozeno)
průběžně doplňované znalosti → metoda tell(KB, Sentence)
Úvod do umělé inteligence 5/12 7 / 36
Logický agent Komponenty agenta
Komponenty agenta
komponenty logického agenta:
inferenční stroj (inference engine)
báze znalostí (knowledge base)
algoritmy nezávislé na doméně
znalosti o doméně
obsah báze znalostí:
na začátku – tzv. znalosti pozadí (background knowledge)
axiom – tvrzení/pravidlo, které je dáno (ne vyvozeno)
průběžně doplňované znalosti → metoda tell(KB, Sentence)
akce logického agenta:
function KB-AgentAction(KB, ATime, Percept, Action) # vrací akci a nový čas
PSentence ← make_percept_sentence(Percept, ATime)
tell (KB, PSentence) # přidáme výsledky pozorování do KB
Query ← make_action_query(ATime),
Action ← ask(KB, Query) # zeptáme se na další postup
ASentence ← make_action_sentence(Action, ATime)
tell (KB, ASentence) # přidáme informace o akci do KB
return Action, ATime + 1
Úvod do umělé inteligence 5/12 7 / 36
Logický agent Wumpusova jeskyně
Popis světa – PEAS
zadání světa rozumného agenta:
míra výkonnosti (Performance measure)
plus body za dosažené (mezi)cíle, pokuty za nežádoucí následky
prostředí (Environment)
objekty ve světě, se kterými agent musí počítat, a jejich vlastnosti
akční prvky (Actuators)
možné součásti činnosti agenta, jeho akce se skládají z použití těchto prvků
senzory (Sensors)
zpětné vazby akcí agenta, podle jejich výstupů se tvoří další akce
Úvod do umělé inteligence 5/12 8 / 36
Logický agent Wumpusova jeskyně
Popis světa – PEAS
zadání světa rozumného agenta:
míra výkonnosti (Performance measure)
plus body za dosažené (mezi)cíle, pokuty za nežádoucí následky
prostředí (Environment)
objekty ve světě, se kterými agent musí počítat, a jejich vlastnosti
akční prvky (Actuators)
možné součásti činnosti agenta, jeho akce se skládají z použití těchto prvků
senzory (Sensors)
zpětné vazby akcí agenta, podle jejich výstupů se tvoří další akce
např. zmiňované automatické taxi:
míra výkonnosti
prostředí
akční prvky
senzory
Úvod do umělé inteligence 5/12 8 / 36
Logický agent Wumpusova jeskyně
Popis světa – PEAS
zadání světa rozumného agenta:
míra výkonnosti (Performance measure)
plus body za dosažené (mezi)cíle, pokuty za nežádoucí následky
prostředí (Environment)
objekty ve světě, se kterými agent musí počítat, a jejich vlastnosti
akční prvky (Actuators)
možné součásti činnosti agenta, jeho akce se skládají z použití těchto prvků
senzory (Sensors)
zpětné vazby akcí agenta, podle jejich výstupů se tvoří další akce
např. zmiňované automatické taxi:
míra výkonnosti doprava na místo, vzdálenost, bezpečnost, bez přestupků,
komfort, . . .
prostředí
akční prvky
senzory
Úvod do umělé inteligence 5/12 8 / 36
Logický agent Wumpusova jeskyně
Popis světa – PEAS
zadání světa rozumného agenta:
míra výkonnosti (Performance measure)
plus body za dosažené (mezi)cíle, pokuty za nežádoucí následky
prostředí (Environment)
objekty ve světě, se kterými agent musí počítat, a jejich vlastnosti
akční prvky (Actuators)
možné součásti činnosti agenta, jeho akce se skládají z použití těchto prvků
senzory (Sensors)
zpětné vazby akcí agenta, podle jejich výstupů se tvoří další akce
např. zmiňované automatické taxi:
míra výkonnosti doprava na místo, vzdálenost, bezpečnost, bez přestupků,
komfort, . . .
prostředí ulice, křižovatky, účastníci provozu, chodci, počasí, . . .
akční prvky
senzory
Úvod do umělé inteligence 5/12 8 / 36
Logický agent Wumpusova jeskyně
Popis světa – PEAS
zadání světa rozumného agenta:
míra výkonnosti (Performance measure)
plus body za dosažené (mezi)cíle, pokuty za nežádoucí následky
prostředí (Environment)
objekty ve světě, se kterými agent musí počítat, a jejich vlastnosti
akční prvky (Actuators)
možné součásti činnosti agenta, jeho akce se skládají z použití těchto prvků
senzory (Sensors)
zpětné vazby akcí agenta, podle jejich výstupů se tvoří další akce
např. zmiňované automatické taxi:
míra výkonnosti doprava na místo, vzdálenost, bezpečnost, bez přestupků,
komfort, . . .
prostředí ulice, křižovatky, účastníci provozu, chodci, počasí, . . .
akční prvky řízení, plyn, brzda, houkačka, blinkry, komunikátory, . . .
senzory
Úvod do umělé inteligence 5/12 8 / 36
Logický agent Wumpusova jeskyně
Popis světa – PEAS
zadání světa rozumného agenta:
míra výkonnosti (Performance measure)
plus body za dosažené (mezi)cíle, pokuty za nežádoucí následky
prostředí (Environment)
objekty ve světě, se kterými agent musí počítat, a jejich vlastnosti
akční prvky (Actuators)
možné součásti činnosti agenta, jeho akce se skládají z použití těchto prvků
senzory (Sensors)
zpětné vazby akcí agenta, podle jejich výstupů se tvoří další akce
např. zmiňované automatické taxi:
míra výkonnosti doprava na místo, vzdálenost, bezpečnost, bez přestupků,
komfort, . . .
prostředí ulice, křižovatky, účastníci provozu, chodci, počasí, . . .
akční prvky řízení, plyn, brzda, houkačka, blinkry, komunikátory, . . .
senzory kamera, tachometr, počítač kilometrů, senzory motoru,
GPS, . . .
Úvod do umělé inteligence 5/12 8 / 36
Logický agent Wumpusova jeskyně
Wumpusova jeskyně
You are in room 3.
Tunnels lead to 2, 4, 12.
Shoot or Move (S-M)? M
Where to? 12
You are in room 12.
I smell a Wumpus.
Tunnels lead to 3, 11, 13.
Shoot or Move (S-M)? S
Room? 13
AHA! You got the mumpus!
HEE HEE HEE The Wumpus’ll
get you next time!!
Same setup (Y-N)? Y
původně textová adventure hra
Hunt the Wumpus
Gregory Yob, 1973
poměrně oblíbená, šířená i komerčně
jeden z prvních příkladů her
typu survival horror
1975 zveřejněný zdrojový kód
hra vyžaduje logické uvažování
Úvod do umělé inteligence 5/12 9 / 36
Logický agent Wumpusova jeskyně
Wumpusova jeskyně
PEAS zadání Wumpusovy jeskyně:
P – míra výkonnosti
zlato +1000, smrt -1000, -1 za krok, -10 za
užití šípu
E – prostředí
Místnosti vedle Wumpuse zapáchají.
V místnosti vedle jámy je vánek.
V místnosti je zlato ⇔ je v ní třpyt.
Výstřel zabije Wumpuse, pokud jsi obrácený
k němu.
Výstřel vyčerpá jediný šíp, který máš.
Zvednutím vezmeš zlato ve stejné místnosti.
Položení odloží zlato v aktuální místnosti.
A – akční prvky
Otočení vlevo, Otočení vpravo, Krok dopředu,
Zvednutí, Položení, Výstřel
S – senzory
Vánek, Třpyt, Zápach, Náraz do zdi,
Chroptění Wumpuse
Vánek Vánek
Vánek
Vánek
Vánek
Zápach
Zápach
Vánek
JÁMA
JÁMA
JÁMA
1 2 3 4
1
2
3
4
START
Trpyt
Zápach
Úvod do umělé inteligence 5/12 10 / 36
Logický agent Wumpusova jeskyně
Vlastnosti problému Wumpusovy jeskyně
pozorovatelné
deterministické
episodické
statické
diskrétní
více agentů
Úvod do umělé inteligence 5/12 11 / 36
Logický agent Wumpusova jeskyně
Vlastnosti problému Wumpusovy jeskyně
pozorovatelné ne, jen lokální vnímání
deterministické
episodické
statické
diskrétní
více agentů
Úvod do umělé inteligence 5/12 11 / 36
Logický agent Wumpusova jeskyně
Vlastnosti problému Wumpusovy jeskyně
pozorovatelné ne, jen lokální vnímání
deterministické ano, přesně dané výsledky
episodické
statické
diskrétní
více agentů
Úvod do umělé inteligence 5/12 11 / 36
Logický agent Wumpusova jeskyně
Vlastnosti problému Wumpusovy jeskyně
pozorovatelné ne, jen lokální vnímání
deterministické ano, přesně dané výsledky
episodické ne, sekvenční na úrovni akcí (složitější)
statické
diskrétní
více agentů
Úvod do umělé inteligence 5/12 11 / 36
Logický agent Wumpusova jeskyně
Vlastnosti problému Wumpusovy jeskyně
pozorovatelné ne, jen lokální vnímání
deterministické ano, přesně dané výsledky
episodické ne, sekvenční na úrovni akcí (složitější)
statické ano, Wumpus a jámy se nehýbou
diskrétní
více agentů
Úvod do umělé inteligence 5/12 11 / 36
Logický agent Wumpusova jeskyně
Vlastnosti problému Wumpusovy jeskyně
pozorovatelné ne, jen lokální vnímání
deterministické ano, přesně dané výsledky
episodické ne, sekvenční na úrovni akcí (složitější)
statické ano, Wumpus a jámy se nehýbou
diskrétní ano
více agentů
Úvod do umělé inteligence 5/12 11 / 36
Logický agent Wumpusova jeskyně
Vlastnosti problému Wumpusovy jeskyně
pozorovatelné ne, jen lokální vnímání
deterministické ano, přesně dané výsledky
episodické ne, sekvenční na úrovni akcí (složitější)
statické ano, Wumpus a jámy se nehýbou
diskrétní ano
více agentů ne, Wumpus je spíše vlastnost prostředí
Úvod do umělé inteligence 5/12 11 / 36
Logický agent Wumpusova jeskyně
Průzkum Wumpusovy jeskyně
1
OK
OK OK
A
A = Agent
V = Vánek
T = Třpyt
OK = bezpečí
J = Jáma
Z = Zápach
X = navštíveno
W = Wumpus
Úvod do umělé inteligence 5/12 12 / 36
Logický agent Wumpusova jeskyně
Průzkum Wumpusovy jeskyně
2
OK
OK OK
A
X
V
J?
J?
A = Agent
V = Vánek
T = Třpyt
OK = bezpečí
J = Jáma
Z = Zápach
X = navštíveno
W = Wumpus
Úvod do umělé inteligence 5/12 12 / 36
Logický agent Wumpusova jeskyně
Průzkum Wumpusovy jeskyně
3
OK
OK OK
X
X
V
J?
J?
A
Z
A = Agent
V = Vánek
T = Třpyt
OK = bezpečí
J = Jáma
Z = Zápach
X = navštíveno
W = Wumpus
Úvod do umělé inteligence 5/12 12 / 36
Logický agent Wumpusova jeskyně
Průzkum Wumpusovy jeskyně
4
OK
OK OK
V
J?
J?
A
Z
X
X
OK
J
W
A = Agent
V = Vánek
T = Třpyt
OK = bezpečí
J = Jáma
Z = Zápach
X = navštíveno
W = Wumpus
Úvod do umělé inteligence 5/12 12 / 36
Logický agent Wumpusova jeskyně
Průzkum Wumpusovy jeskyně
5
OK
OK OK
X
X
X
V
Z
OK
J
W
A
A = Agent
V = Vánek
T = Třpyt
OK = bezpečí
J = Jáma
Z = Zápach
X = navštíveno
W = Wumpus
Úvod do umělé inteligence 5/12 12 / 36
Logický agent Wumpusova jeskyně
Průzkum Wumpusovy jeskyně
6
OK
OK OK
X
X
X
V
Z
OK
J
W
A
OK
OK
A = Agent
V = Vánek
T = Třpyt
OK = bezpečí
J = Jáma
Z = Zápach
X = navštíveno
W = Wumpus
Úvod do umělé inteligence 5/12 12 / 36
Logický agent Wumpusova jeskyně
Průzkum Wumpusovy jeskyně
7
OK
OK OK
X
X
X
X
V
Z
OK
J
W
OK
OK
A
VTZ
A = Agent
V = Vánek
T = Třpyt
OK = bezpečí
J = Jáma
Z = Zápach
X = navštíveno
W = Wumpus
Úvod do umělé inteligence 5/12 12 / 36
Logický agent Wumpusova jeskyně
Průzkum Wumpusovy jeskyně
8
OK
OK OK
X
X
X
X
V
Z
OK
J
W
OK
OK
A
VTZ
ZVEDNI!
A = Agent
V = Vánek
T = Třpyt
OK = bezpečí
J = Jáma
Z = Zápach
X = navštíveno
W = Wumpus
Úvod do umělé inteligence 5/12 12 / 36
Logický agent Wumpusova jeskyně
Průzkum Wumpusovy jeskyně – problémy
Obtížné situace:
V OK
OK OKV
A
J?
J?
J?
J?
Vánek v (1, 2) i v (2, 1) ⇒ žádná bezpečná akce
Při předpokladu uniformní distribuce děr
→ díra v (2, 2) má pravděpodobnost 0.86, na krajích
0.31
Úvod do umělé inteligence 5/12 13 / 36
Logický agent Wumpusova jeskyně
Průzkum Wumpusovy jeskyně – problémy
Obtížné situace:
V OK
OK OKV
A
J?
J?
J?
J?
Vánek v (1, 2) i v (2, 1) ⇒ žádná bezpečná akce
Při předpokladu uniformní distribuce děr
→ díra v (2, 2) má pravděpodobnost 0.86, na krajích
0.31
A
Z
Zápach v (1, 1) ⇒ nemůže se pohnout
je možné použít donucovací strategii (strategy of coercion):
1. Výstřel jedním ze směrů
2. byl tam Wumpus ⇒ je mrtvý (poznám podle Chroptění) ⇒
bezpečné
3. nebyl tam Wumpus (žádné Chroptění) ⇒ bezpečný směr
Úvod do umělé inteligence 5/12 13 / 36
Logika
Obsah
1 Logický agent
Báze znalostí
Návrh logického agenta
Komponenty agenta
Wumpusova jeskyně
2 Logika
Historie logiky
Některé vlastnosti logik
Důsledek
Model
Inference
3 Výroková logika
Sémantika výrokové logiky
Logická ekvivalence
Platnost a splnitelnost
Normální forma
Tvrzení pro Wumpusovu jeskyni
Úvod do umělé inteligence 5/12 14 / 36
Logika
Co je Pravda?
Francis Bacon (1561–1626)
No pleasure is comparable to the
standing upon the
vantage-ground of truth.
Thomas H. Huxley (1825–1895)
Irrationally held truths may be
more harmful than reasoned
errors.
John Keats (1795–1821)
Beauty is truth, truth beauty;
that is all ye know on earth, and
all ye need to know.
Blaise Pascal (1623–1662)
We know the truth, not only
by the reason, but also by the
heart.
François Rabelais (1490–1553)
Speak the truth and shame
the Devil.
Daniel Webster (1782–1852)
There is nothing so powerful as
truth, and often nothing so
strange.
Úvod do umělé inteligence 5/12 15 / 36
Logika
Co je Pravda?
Francis Bacon (1561–1626)
No pleasure is comparable to the
standing upon the
vantage-ground of truth.
Thomas H. Huxley (1825–1895)
Irrationally held truths may be
more harmful than reasoned
errors.
John Keats (1795–1821)
Beauty is truth, truth beauty;
that is all ye know on earth, and
all ye need to know.
Blaise Pascal (1623–1662)
We know the truth, not only
by the reason, but also by the
heart.
François Rabelais (1490–1553)
Speak the truth and shame
the Devil.
Daniel Webster (1782–1852)
There is nothing so powerful as
truth, and often nothing so
strange.
Úvod do umělé inteligence 5/12 15 / 36
Logika
Logika
Logika = syntaxe a sémantika formálního jazyka pro reprezentaci znalostí
umožňující vyvozování závěrů
Syntaxe definuje všechny dobře utvořené věty jazyka
Sémantika definuje “význam” vět ⇒ definuje pravdivost vět v jazyce
(v závislosti na možném světě)
Úvod do umělé inteligence 5/12 16 / 36
Logika
Logika
Logika = syntaxe a sémantika formálního jazyka pro reprezentaci znalostí
umožňující vyvozování závěrů
Syntaxe definuje všechny dobře utvořené věty jazyka
Sémantika definuje “význam” vět ⇒ definuje pravdivost vět v jazyce
(v závislosti na možném světě)
např. jazyk aritmetiky:
x + 2 ≥ y je dobře utvořená věta; x2 + y > není věta
Úvod do umělé inteligence 5/12 16 / 36
Logika
Logika
Logika = syntaxe a sémantika formálního jazyka pro reprezentaci znalostí
umožňující vyvozování závěrů
Syntaxe definuje všechny dobře utvořené věty jazyka
Sémantika definuje “význam” vět ⇒ definuje pravdivost vět v jazyce
(v závislosti na možném světě)
např. jazyk aritmetiky:
x + 2 ≥ y je dobře utvořená věta; x2 + y > není věta
x + 2 ≥ y je pravda ⇔ číslo x + 2 není menší než číslo y
Úvod do umělé inteligence 5/12 16 / 36
Logika
Logika
Logika = syntaxe a sémantika formálního jazyka pro reprezentaci znalostí
umožňující vyvozování závěrů
Syntaxe definuje všechny dobře utvořené věty jazyka
Sémantika definuje “význam” vět ⇒ definuje pravdivost vět v jazyce
(v závislosti na možném světě)
např. jazyk aritmetiky:
x + 2 ≥ y je dobře utvořená věta; x2 + y > není věta
x + 2 ≥ y je pravda ⇔ číslo x + 2 není menší než číslo y
x + 2 ≥ y je pravda ve světě, kde x = 7, y = 1
Úvod do umělé inteligence 5/12 16 / 36
Logika
Logika
Logika = syntaxe a sémantika formálního jazyka pro reprezentaci znalostí
umožňující vyvozování závěrů
Syntaxe definuje všechny dobře utvořené věty jazyka
Sémantika definuje “význam” vět ⇒ definuje pravdivost vět v jazyce
(v závislosti na možném světě)
např. jazyk aritmetiky:
x + 2 ≥ y je dobře utvořená věta; x2 + y > není věta
x + 2 ≥ y je pravda ⇔ číslo x + 2 není menší než číslo y
x + 2 ≥ y je pravda ve světě, kde x = 7, y = 1
x + 2 ≥ y je nepravda ve světě, kde x = 0, y = 6
Úvod do umělé inteligence 5/12 16 / 36
Logika
Logika
Logika = syntaxe a sémantika formálního jazyka pro reprezentaci znalostí
umožňující vyvozování závěrů
Syntaxe definuje všechny dobře utvořené věty jazyka
Sémantika definuje “význam” vět ⇒ definuje pravdivost vět v jazyce
(v závislosti na možném světě)
např. jazyk aritmetiky:
x + 2 ≥ y je dobře utvořená věta; x2 + y > není věta
x + 2 ≥ y je pravda ⇔ číslo x + 2 není menší než číslo y
x + 2 ≥ y je pravda ve světě, kde x = 7, y = 1
x + 2 ≥ y je nepravda ve světě, kde x = 0, y = 6
zápis na papíře v libovolné syntaxi → v KB se jedná o konfiguraci (částí)
agenta
vlastní vyvozování → generování a manipulace s těmito konfiguracemi
Úvod do umělé inteligence 5/12 16 / 36
Logika Historie logiky
Historie logiky
náhledy na logiku:
filozofická logika
• Thalés z Milétu – geometrické věty a důkazy
• Aristoteles – první formální systém, princip sporu, princip vyloučení třetího
• Euklides – axiomy, věty, první axiomatický systém
• stoikové 3.stol. př.n.l. – základy výrokové logiky
počátky symbolické logiky (13.–19. století)
• J. Duns Scotus – z dvou odporujících si tvrzení plyne cokoliv
• W. Ockham – odlišil tvrzení a odvozovací pravidlo
• G. W. Leibniz – idea logického kalkulu pro exaktní vědy
• B. Bolzano – operace odvoditelnosti, kvantifikátory
• G. Boole – Booleova algebra, fomální logika v moderním slova smyslu
Úvod do umělé inteligence 5/12 17 / 36
Logika Historie logiky
20. století
matematická logika
• G. Frege, přelom století – axiomatizace výrokové logiky
• B. Russell, 1918 – objasnění paradoxu lháře
• C.S.Lewis, J.Lukasiewicz – neklasické logiky
• D. Hilbert, W. Ackermann – axiomatizace predikátového počtu
• úplnost výrokové (Post 1921) a predikátové (Goedel 1930) logiky
• K. Goedel – neúplnost systémů obsahujících aritmetiku, omezená možnost
důkazu bezespornosti
• A.Church, 1936 – nerozhodnutelnost predikátové logiky
• A. Turing, 1937 – pojem vyčíslitelnosti, Turingův stroj
logika v informatice, v AI, výpočtová logika
• verifikace programů
• deskriptivní logika
• znalostní systémy
• logické programování
• bayesovské sítě
• ...
Úvod do umělé inteligence 5/12 18 / 36
Logika Některé vlastnosti logik
Některé vlastnosti logik
formální – co je poznané, definované; metody odvozování
neformální – mentální, co je poznatelné; zdravý selský rozum,
komunikace mezi lidmi, heuristické odvozování
Formální logika
dvouhodnotová – true, false; i vícehodnotová
extenzionální – pravdivost formule závisí jen na pravdivosti jejich složek
intenzionální – nejen na pravdivosti složek, také na “okolnostech” (čas,
možný svět, ...)
Úvod do umělé inteligence 5/12 19 / 36
Logika Některé vlastnosti logik
Některé vlastnosti logik
Dvouhodnotová extenzionální logika zde
výroková
Jestliže bude pěkně a nebudu učit, půjdu hrát tenis
p ∧ ¬q ⇒ r
predikátová
• 1. řádu
Není pravda, že všichni lidé jsou spokojení
¬∀x : člověk(x) ⇒ spokojený(x)
• 2. řádu
Existuje vlastnost, kterou mají všichni lidé
∃P∀x : člověk(x) ⇒ P(x)
Úvod do umělé inteligence 5/12 20 / 36
Logika Důsledek
Důsledek
Důsledek (vyplývání, entailment) – jedna věc logicky vyplývá z druhé (je
jejím důsledkem):
KB |= α
Z báze znalostí KB vyplývá věta α ⇔ α je pravdivá ve všech světech,
kde je KB pravdivá
Úvod do umělé inteligence 5/12 21 / 36
Logika Důsledek
Důsledek
Důsledek (vyplývání, entailment) – jedna věc logicky vyplývá z druhé (je
jejím důsledkem):
KB |= α
Z báze znalostí KB vyplývá věta α ⇔ α je pravdivá ve všech světech,
kde je KB pravdivá
např.:
KB obsahuje věty – “Češi vyhráli”
– “Slováci vyhráli”
z KB pak vyplývá – “Češi vyhráli nebo Slováci vyhráli”
Úvod do umělé inteligence 5/12 21 / 36
Logika Důsledek
Důsledek
Důsledek (vyplývání, entailment) – jedna věc logicky vyplývá z druhé (je
jejím důsledkem):
KB |= α
Z báze znalostí KB vyplývá věta α ⇔ α je pravdivá ve všech světech,
kde je KB pravdivá
např.:
KB obsahuje věty – “Češi vyhráli”
– “Slováci vyhráli”
z KB pak vyplývá – “Češi vyhráli nebo Slováci vyhráli”
z x + y = 4 vyplývá 4 = x + y
Úvod do umělé inteligence 5/12 21 / 36
Logika Důsledek
Důsledek
Důsledek (vyplývání, entailment) – jedna věc logicky vyplývá z druhé (je
jejím důsledkem):
KB |= α
Z báze znalostí KB vyplývá věta α ⇔ α je pravdivá ve všech světech,
kde je KB pravdivá
např.:
KB obsahuje věty – “Češi vyhráli”
– “Slováci vyhráli”
z KB pak vyplývá – “Češi vyhráli nebo Slováci vyhráli”
z x + y = 4 vyplývá 4 = x + y
Důsledek je vztah mezi větami (syntaxe), který je založený na sémantice.
SliDo
Úvod do umělé inteligence 5/12 21 / 36
Logika Model
Model
možný svět = model . . . formálně strukturovaný (abstraktní) svět,
umožňuje vyhodnocení pravdivosti
říkáme: m je model věty α ⇔ α je pravdivá v m
Úvod do umělé inteligence 5/12 22 / 36
Logika Model
Model
možný svět = model . . . formálně strukturovaný (abstraktní) svět,
umožňuje vyhodnocení pravdivosti
říkáme: m je model věty α ⇔ α je pravdivá v m
M(α) . . . množina všech modelů věty α
KB |= α ⇔ M(KB) ⊆ M(α)
např.:
KB = “Češi vyhráli” ∧ “Slováci vyhráli”
α = “Češi vyhráli”
M(α)
M(KB)
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x x
xx
x
x
x
x
x
x
x x
x
x
x
x
x
x
x
x
x
x
x
x
Úvod do umělé inteligence 5/12 22 / 36
Logika Inference
Inference
Vyvozování požadovaných důsledků – inference
KB ⊢i α . . . věta α může být vyvozena z KB pomocí (procedury) i
(i odvodí α z KB)
všechny možné důsledky KB jsou “kupka sena”; α je jehla
vyplývání = jehla v kupce sena; inference = její nalezení
Bezespornost: i je bezesporná ⇔ ∀KB ⊢i α ⇒ KB |= α
Úplnost: i je úplná ⇔ ∀KB |= α ⇒ KB ⊢i α
Úvod do umělé inteligence 5/12 23 / 36
Logika Inference
Inference
Vyvozování požadovaných důsledků – inference
KB ⊢i α . . . věta α může být vyvozena z KB pomocí (procedury) i
(i odvodí α z KB)
všechny možné důsledky KB jsou “kupka sena”; α je jehla
vyplývání = jehla v kupce sena; inference = její nalezení
Bezespornost: i je bezesporná ⇔ ∀KB ⊢i α ⇒ KB |= α
Úplnost: i je úplná ⇔ ∀KB |= α ⇒ KB ⊢i α
Vztah k reálnému světu:
Pokud je KB pravdivá v reálném světě ⇒ ∀ věta α vyvozená z KB
pomocí bezesporné inference je také pravdivá ve skutečném světě
Jestliže máme sémantiku “pravdivou” v reálném světě → můžeme
vyvozovat závěry o skutečném světě pomocí logiky
Úvod do umělé inteligence 5/12 23 / 36
Výroková logika
Obsah
1 Logický agent
Báze znalostí
Návrh logického agenta
Komponenty agenta
Wumpusova jeskyně
2 Logika
Historie logiky
Některé vlastnosti logik
Důsledek
Model
Inference
3 Výroková logika
Sémantika výrokové logiky
Logická ekvivalence
Platnost a splnitelnost
Normální forma
Tvrzení pro Wumpusovu jeskyni
Úvod do umělé inteligence 5/12 24 / 36
Výroková logika
Výroková logika
Výroková logika – nejjednodušší logika, ilustruje základní myšlenky
Syntaxe
výrokové symboly P1, P2, . . . jsou věty
negace – S je věta ⇒ ¬S je věta
konjunkce – S1 a S2 jsou věty ⇒ S1 ∧ S2 je věta
disjunkce – S1 a S2 jsou věty ⇒ S1 ∨ S2 je věta
implikace – S1 a S2 jsou věty ⇒ S1 ⇒ S2 je věta
ekvivalence – S1 a S2 jsou věty ⇒ S1 ⇔ S2 je věta
Úvod do umělé inteligence 5/12 25 / 36
Výroková logika
Úplný systém logických spojek
Existuje minimální dostatečná množina spojek?
prostřednictvím systému spojek {¬, ∧, ∨} dokážeme vyjádřit libovolnou
spojku
množina spojek s touto vlastností – úplný systém logických spojek
Úvod do umělé inteligence 5/12 26 / 36
Výroková logika
Úplný systém logických spojek
Existuje minimální dostatečná množina spojek?
prostřednictvím systému spojek {¬, ∧, ∨} dokážeme vyjádřit libovolnou
spojku
množina spojek s touto vlastností – úplný systém logických spojek
další úplné systémy např. {¬, ∨}, {¬, ∧}, {¬, ⇒}
(a ⇒ b) ≡ (¬a ∨ b), (a ∧ b) ≡ ¬(¬a ∨ ¬b)
(a ∨ b) ≡ ¬(¬a ∧ ¬b)
Úvod do umělé inteligence 5/12 26 / 36
Výroková logika
Úplný systém logických spojek
Existuje minimální dostatečná množina spojek?
prostřednictvím systému spojek {¬, ∧, ∨} dokážeme vyjádřit libovolnou
spojku
množina spojek s touto vlastností – úplný systém logických spojek
další úplné systémy např. {¬, ∨}, {¬, ∧}, {¬, ⇒}
(a ⇒ b) ≡ (¬a ∨ b), (a ∧ b) ≡ ¬(¬a ∨ ¬b)
(a ∨ b) ≡ ¬(¬a ∧ ¬b)
jednoprvkové úplné systémy: Shefferova funkce NAND (negace
konjunkce), Nicodova funkce NOR (negace disjunkce)
např. (p ∨ q) ≡ ((p | p) | (q | q))
Úvod do umělé inteligence 5/12 26 / 36
Výroková logika Sémantika výrokové logiky
Sémantika výrokové logiky
každý model musí určit pravdivostní hodnoty výrokových symbolů
např.: m1 = {P1 = false, P2 = false, P3 = true}
Úvod do umělé inteligence 5/12 27 / 36
Výroková logika Sémantika výrokové logiky
Sémantika výrokové logiky
každý model musí určit pravdivostní hodnoty výrokových symbolů
např.: m1 = {P1 = false, P2 = false, P3 = true}
pravidla pro vyhodnocení pravdivosti složených výroků pro model m:
¬S je true ⇔ S je false
S1 ∧ S2 je true ⇔ S1 je true a S2 je true
S1 ∨ S2 je true ⇔ S1 je true nebo S2 je true
S1 ⇒ S2 je true ⇔ S1 je false nebo S2 je true
tj. je false ⇔ S1 je true a S2 je false
S1 ⇔ S2 je true ⇔ S1 ⇒ S2 je true a S2 ⇒ S1 je true
Úvod do umělé inteligence 5/12 27 / 36
Výroková logika Sémantika výrokové logiky
Sémantika výrokové logiky
každý model musí určit pravdivostní hodnoty výrokových symbolů
např.: m1 = {P1 = false, P2 = false, P3 = true}
pravidla pro vyhodnocení pravdivosti složených výroků pro model m:
¬S je true ⇔ S je false
S1 ∧ S2 je true ⇔ S1 je true a S2 je true
S1 ∨ S2 je true ⇔ S1 je true nebo S2 je true
S1 ⇒ S2 je true ⇔ S1 je false nebo S2 je true
tj. je false ⇔ S1 je true a S2 je false
S1 ⇔ S2 je true ⇔ S1 ⇒ S2 je true a S2 ⇒ S1 je true
rekurzivním procesem vyhodnotíme lib. větu:
¬P1 ∧ (P2 ∨ P3) = true ∧ (false ∨ true) = true ∧ true = true
Úvod do umělé inteligence 5/12 27 / 36
Výroková logika Sémantika výrokové logiky
Sémantika výrokové logiky
každý model musí určit pravdivostní hodnoty výrokových symbolů
např.: m1 = {P1 = false, P2 = false, P3 = true}
pravidla pro vyhodnocení pravdivosti složených výroků pro model m:
¬S je true ⇔ S je false
S1 ∧ S2 je true ⇔ S1 je true a S2 je true
S1 ∨ S2 je true ⇔ S1 je true nebo S2 je true
S1 ⇒ S2 je true ⇔ S1 je false nebo S2 je true
tj. je false ⇔ S1 je true a S2 je false
S1 ⇔ S2 je true ⇔ S1 ⇒ S2 je true a S2 ⇒ S1 je true
rekurzivním procesem vyhodnotíme lib. větu:
¬P1 ∧ (P2 ∨ P3) = true ∧ (false ∨ true) = true ∧ true = true
pravdivostní tabulka:
P Q ¬P P ∧ Q P ∨ Q P ⇒ Q P ⇔ Q
false false true false false true true
false true true false true true false
true false false false true false false
true true false true true true true
Úvod do umělé inteligence 5/12 27 / 36
Výroková logika Sémantika výrokové logiky
Sémantika výrokové logiky a přirozený jazyk
Rozdíly v chápání logických spojek v jazyce:
rozdíl OR a XOR – v jazyce spíš XOR
Viděl jsem na večírku Petra nebo Pavla.
Korunujeme Jana nebo Richarda?
Úvod do umělé inteligence 5/12 28 / 36
Výroková logika Sémantika výrokové logiky
Sémantika výrokové logiky a přirozený jazyk
Rozdíly v chápání logických spojek v jazyce:
rozdíl OR a XOR – v jazyce spíš XOR
Viděl jsem na večírku Petra nebo Pavla.
Korunujeme Jana nebo Richarda?
implikace – v jazyce chybí část “z neplatné premisy plyne cokoliv,”
naopak se přidává presupozice, že mezi premisou a závěrem existuje
příčinný vztah
P ⇒ Q ⇔ ¬P ∨ Q
Úvod do umělé inteligence 5/12 28 / 36
Výroková logika Sémantika výrokové logiky
Sémantika výrokové logiky a přirozený jazyk
Rozdíly v chápání logických spojek v jazyce:
rozdíl OR a XOR – v jazyce spíš XOR
Viděl jsem na večírku Petra nebo Pavla.
Korunujeme Jana nebo Richarda?
implikace – v jazyce chybí část “z neplatné premisy plyne cokoliv,”
naopak se přidává presupozice, že mezi premisou a závěrem existuje
příčinný vztah
P ⇒ Q ⇔ ¬P ∨ Q
5 je sudá a z toho plyne, že AZ Tower je nejvyšší budova na světě.
Úvod do umělé inteligence 5/12 28 / 36
Výroková logika Sémantika výrokové logiky
Sémantika výrokové logiky a přirozený jazyk
Rozdíly v chápání logických spojek v jazyce:
rozdíl OR a XOR – v jazyce spíš XOR
Viděl jsem na večírku Petra nebo Pavla.
Korunujeme Jana nebo Richarda?
implikace – v jazyce chybí část “z neplatné premisy plyne cokoliv,”
naopak se přidává presupozice, že mezi premisou a závěrem existuje
příčinný vztah
P ⇒ Q ⇔ ¬P ∨ Q
5 je sudá a z toho plyne, že AZ Tower je nejvyšší budova na světě.
5 je lichá a z toho plyne, že Praha je hlavní město ČR.
Úvod do umělé inteligence 5/12 28 / 36
Výroková logika Logická ekvivalence
Logická ekvivalence
Dva výroky jsou logicky ekvivalentní právě tehdy, když jsou pravdivé ve
stejných modelech:
α ≡ β ⇔ α |= β a β |= α
(α ∧ β) ≡ (β ∧ α) komutativita ∧
(α ∨ β) ≡ (β ∨ α) komutativita ∨
((α ∧ β) ∧ γ) ≡ (α ∧ (β ∧ γ)) asociativita ∧
((α ∨ β) ∨ γ) ≡ (α ∨ (β ∨ γ)) asociativita ∨
¬(¬α) ≡ α eliminace dvojí negace
(α ⇒ β) ≡ (¬β ⇒ ¬α) kontrapozice
(α ⇒ β) ≡ (¬α ∨ β) eliminace implikace
(α ⇔ β) ≡ ((α ⇒ β) ∧ (β ⇒ α)) eliminace ekvivalence
¬(α ∧ β) ≡ (¬α ∨ ¬β) de Morgan
¬(α ∨ β) ≡ (¬α ∧ ¬β) de Morgan
(α ∧ (β ∨ γ)) ≡ ((α ∧ β) ∨ (α ∧ γ)) distributivita ∧ nad ∨
(α ∨ (β ∧ γ)) ≡ ((α ∨ β) ∧ (α ∨ γ)) distributivita ∨ nad ∧
Úvod do umělé inteligence 5/12 29 / 36
Výroková logika Logická ekvivalence
Logická ekvivalence – příklad
(A ∧ (A ⇒ B)) ⇒ B
Úvod do umělé inteligence 5/12 30 / 36
Výroková logika Logická ekvivalence
Logická ekvivalence – příklad
(A ∧ (A ⇒ B)) ⇒ B
≡ (A ∧ (¬A ∨ B)) ⇒ B
Úvod do umělé inteligence 5/12 30 / 36
Výroková logika Logická ekvivalence
Logická ekvivalence – příklad
(A ∧ (A ⇒ B)) ⇒ B
≡ (A ∧ (¬A ∨ B)) ⇒ B
≡ ¬(A ∧ (¬A ∨ B)) ∨ B
Úvod do umělé inteligence 5/12 30 / 36
Výroková logika Logická ekvivalence
Logická ekvivalence – příklad
(A ∧ (A ⇒ B)) ⇒ B
≡ (A ∧ (¬A ∨ B)) ⇒ B
≡ ¬(A ∧ (¬A ∨ B)) ∨ B
≡ (¬A ∨ ¬(¬A ∨ B)) ∨ B
Úvod do umělé inteligence 5/12 30 / 36
Výroková logika Logická ekvivalence
Logická ekvivalence – příklad
(A ∧ (A ⇒ B)) ⇒ B
≡ (A ∧ (¬A ∨ B)) ⇒ B
≡ ¬(A ∧ (¬A ∨ B)) ∨ B
≡ (¬A ∨ ¬(¬A ∨ B)) ∨ B
≡ (¬A ∨ (¬¬A ∧ ¬B)) ∨ B
Úvod do umělé inteligence 5/12 30 / 36
Výroková logika Logická ekvivalence
Logická ekvivalence – příklad
(A ∧ (A ⇒ B)) ⇒ B
≡ (A ∧ (¬A ∨ B)) ⇒ B
≡ ¬(A ∧ (¬A ∨ B)) ∨ B
≡ (¬A ∨ ¬(¬A ∨ B)) ∨ B
≡ (¬A ∨ (¬¬A ∧ ¬B)) ∨ B
≡ (¬A ∨ (A ∧ ¬B)) ∨ B
Úvod do umělé inteligence 5/12 30 / 36
Výroková logika Logická ekvivalence
Logická ekvivalence – příklad
(A ∧ (A ⇒ B)) ⇒ B
≡ (A ∧ (¬A ∨ B)) ⇒ B
≡ ¬(A ∧ (¬A ∨ B)) ∨ B
≡ (¬A ∨ ¬(¬A ∨ B)) ∨ B
≡ (¬A ∨ (¬¬A ∧ ¬B)) ∨ B
≡ (¬A ∨ (A ∧ ¬B)) ∨ B
≡ ((¬A ∨ A) ∧ (¬A ∨ ¬B)) ∨ B
Úvod do umělé inteligence 5/12 30 / 36
Výroková logika Logická ekvivalence
Logická ekvivalence – příklad
(A ∧ (A ⇒ B)) ⇒ B
≡ (A ∧ (¬A ∨ B)) ⇒ B
≡ ¬(A ∧ (¬A ∨ B)) ∨ B
≡ (¬A ∨ ¬(¬A ∨ B)) ∨ B
≡ (¬A ∨ (¬¬A ∧ ¬B)) ∨ B
≡ (¬A ∨ (A ∧ ¬B)) ∨ B
≡ ((¬A ∨ A) ∧ (¬A ∨ ¬B)) ∨ B
≡ (True ∧ (¬A ∨ ¬B)) ∨ B
Úvod do umělé inteligence 5/12 30 / 36
Výroková logika Logická ekvivalence
Logická ekvivalence – příklad
(A ∧ (A ⇒ B)) ⇒ B
≡ (A ∧ (¬A ∨ B)) ⇒ B
≡ ¬(A ∧ (¬A ∨ B)) ∨ B
≡ (¬A ∨ ¬(¬A ∨ B)) ∨ B
≡ (¬A ∨ (¬¬A ∧ ¬B)) ∨ B
≡ (¬A ∨ (A ∧ ¬B)) ∨ B
≡ ((¬A ∨ A) ∧ (¬A ∨ ¬B)) ∨ B
≡ (True ∧ (¬A ∨ ¬B)) ∨ B
≡ (¬A ∨ ¬B) ∨ B
Úvod do umělé inteligence 5/12 30 / 36
Výroková logika Logická ekvivalence
Logická ekvivalence – příklad
(A ∧ (A ⇒ B)) ⇒ B
≡ (A ∧ (¬A ∨ B)) ⇒ B
≡ ¬(A ∧ (¬A ∨ B)) ∨ B
≡ (¬A ∨ ¬(¬A ∨ B)) ∨ B
≡ (¬A ∨ (¬¬A ∧ ¬B)) ∨ B
≡ (¬A ∨ (A ∧ ¬B)) ∨ B
≡ ((¬A ∨ A) ∧ (¬A ∨ ¬B)) ∨ B
≡ (True ∧ (¬A ∨ ¬B)) ∨ B
≡ (¬A ∨ ¬B) ∨ B
≡ ¬A ∨ (¬B ∨ B)
Úvod do umělé inteligence 5/12 30 / 36
Výroková logika Logická ekvivalence
Logická ekvivalence – příklad
(A ∧ (A ⇒ B)) ⇒ B
≡ (A ∧ (¬A ∨ B)) ⇒ B
≡ ¬(A ∧ (¬A ∨ B)) ∨ B
≡ (¬A ∨ ¬(¬A ∨ B)) ∨ B
≡ (¬A ∨ (¬¬A ∧ ¬B)) ∨ B
≡ (¬A ∨ (A ∧ ¬B)) ∨ B
≡ ((¬A ∨ A) ∧ (¬A ∨ ¬B)) ∨ B
≡ (True ∧ (¬A ∨ ¬B)) ∨ B
≡ (¬A ∨ ¬B) ∨ B
≡ ¬A ∨ (¬B ∨ B)
≡ ¬A ∨ True
Úvod do umělé inteligence 5/12 30 / 36
Výroková logika Logická ekvivalence
Logická ekvivalence – příklad
(A ∧ (A ⇒ B)) ⇒ B
≡ (A ∧ (¬A ∨ B)) ⇒ B
≡ ¬(A ∧ (¬A ∨ B)) ∨ B
≡ (¬A ∨ ¬(¬A ∨ B)) ∨ B
≡ (¬A ∨ (¬¬A ∧ ¬B)) ∨ B
≡ (¬A ∨ (A ∧ ¬B)) ∨ B
≡ ((¬A ∨ A) ∧ (¬A ∨ ¬B)) ∨ B
≡ (True ∧ (¬A ∨ ¬B)) ∨ B
≡ (¬A ∨ ¬B) ∨ B
≡ ¬A ∨ (¬B ∨ B)
≡ ¬A ∨ True
≡ True
Úvod do umělé inteligence 5/12 30 / 36
Výroková logika Platnost a splnitelnost
Platnost a splnitelnost
Výrok je platný (valid) ⇔ je pravdivý ve všech modelech
také tautologie, např.: true, A ∨ ¬A, A ⇒ A,
(A ∧ (A ⇒ B)) ⇒ B
Platnost je spojena s vyplýváním pomocí věty o dedukci:
KB |= α ⇔ (KB ⇒ α) je platný výrok
Úvod do umělé inteligence 5/12 31 / 36
Výroková logika Platnost a splnitelnost
Platnost a splnitelnost
Výrok je platný (valid) ⇔ je pravdivý ve všech modelech
také tautologie, např.: true, A ∨ ¬A, A ⇒ A,
(A ∧ (A ⇒ B)) ⇒ B
Platnost je spojena s vyplýváním pomocí věty o dedukci:
KB |= α ⇔ (KB ⇒ α) je platný výrok
Výrok je splnitelný (satisfiable) ⇔ je pravdivý v některých modelech
např.: A ∨ B, C
Výrok je nesplnitelný ⇔ je nepravdivý ve všech modelech
také kontradikce, např.: A ∧ ¬A
SliDo
Úvod do umělé inteligence 5/12 31 / 36
Výroková logika Platnost a splnitelnost
Platnost a splnitelnost – problém SAT
problém SAT:
Je daná formule Φ s n výrokovými symboly splnitelná?
problém SAT je NP-uplný
např. hledání řešení problému s omezujícími podmínkami = problém SAT
na daných podmínkách
SAT solver – algoritmus zaměřený na efektivní řešení problémů s velkým
množstvím symbolů
Splnitelnost je spojena s vyplýváním pomocí důkazu α sporem (reductio ad
absurdum):
KB |= α ⇔ (KB ∧ ¬α) je nesplnitelný
Úvod do umělé inteligence 5/12 32 / 36
Výroková logika Normální forma
Normální forma
Konjunktivní normální forma, Conjunctive Normal Form, CNF
klauzule – disjunkce symbolů nebo jejich negací (tzv. literálů)
KB v CNF – konjunkce klauzulí
(¬D ∨ ¬B ∨ C)
∧ (B ∨ ¬A ∨ ¬C)
∧ (¬C ∨ ¬B ∨ E)
∧ (E ∨ ¬D ∨ B)
∧ (B ∨ E ∨ ¬C)
literály ¬D, ¬B a C
pět klauzulí spojených konjunkcí ∧
každou formuli lze převést do normální formy
Úvod do umělé inteligence 5/12 33 / 36
Výroková logika Normální forma
Konjunktivní normální forma
příklad V1,1 ⇔ (J1,2 ∨ J2,1):
1. eliminujeme ⇔: nahradíme α ⇔ β přepisem (α ⇒ β) ∧ (β ⇒ α)
(V1,1 ⇒ (J1,2 ∨ J2,1)) ∧ ((J1,2 ∨ J2,1) ⇒ V1,1)
2. eliminujeme ⇒: nahradíme α ⇒ β přepisem ¬α ∨ β
(¬V1,1 ∨ J1,2 ∨ J2,1) ∧ (¬(J1,2 ∨ J2,1) ∨ V1,1)
3. negaci přesuneme k symbolům aplikací pravidel logické ekvivalence
(dvojí negace a de Morgan)
(¬V1,1 ∨ J1,2 ∨ J2,1) ∧ ((¬J1,2 ∧ ¬J2,1) ∨ V1,1)
4. “roznásobíme” závorky pomocí distributivity
(¬V1,1 ∨ J1,2 ∨ J2,1) ∧ (¬J1,2 ∨ V1,1) ∧ (¬J2,1 ∨ V1,1)
Výsledná věta je logicky ekvivalentní původní větě a je v CNF nachystaná
pro důkaz s využitím rezoluce
Úvod do umělé inteligence 5/12 34 / 36
Výroková logika Normální forma
Hornovy klauzule
syntakticky vymezená logika Hornových klauzulí – efektivnější vyvozování
Hornova klauzule:
klauzule, kde nejvýše jeden symbol je pozitivní
¬P1,1 ∨ ¬Vánek ∨ V1,1 (odpovídá P1,1 ∧ Vánek ⇒ V1,1)
bez pozitivního symbolu – dotaz, cíl
¬P1,1 ∨ ¬Vánek (odpovídá P1,1 ∧ Vánek ⇒?)
pouze s jedním pozitivním symbolem – fakt
Vánek (odpovídá True ⇒ Vánek)
s jedním pozitivním a několika negovanými symboly – pravidlo
Úvod do umělé inteligence 5/12 35 / 36
Výroková logika Normální forma
Hornovy klauzule
syntakticky vymezená logika Hornových klauzulí – efektivnější vyvozování
Hornova klauzule:
klauzule, kde nejvýše jeden symbol je pozitivní
¬P1,1 ∨ ¬Vánek ∨ V1,1 (odpovídá P1,1 ∧ Vánek ⇒ V1,1)
bez pozitivního symbolu – dotaz, cíl
¬P1,1 ∨ ¬Vánek (odpovídá P1,1 ∧ Vánek ⇒?)
pouze s jedním pozitivním symbolem – fakt
Vánek (odpovídá True ⇒ Vánek)
s jedním pozitivním a několika negovanými symboly – pravidlo
vlastnosti logiky Hornových klauzulí:
snadná interpretace klauzulí, vede k logickému programování
dokazování pomocí jednoduchých algoritmů dopředného a zpětného
řetězení v lineárním čase (k velikosti KB)
Úvod do umělé inteligence 5/12 35 / 36
Výroková logika Tvrzení pro Wumpusovu jeskyni
Tvrzení pro Wumpusovu jeskyni
Definujeme výrokové symboly Ji,j je pravda ⇔ Na [i, j] je Jáma.
a Vi,j je pravda ⇔ Na [i, j] je Vánek.
Úvod do umělé inteligence 5/12 36 / 36
Výroková logika Tvrzení pro Wumpusovu jeskyni
Tvrzení pro Wumpusovu jeskyni
Definujeme výrokové symboly Ji,j je pravda ⇔ Na [i, j] je Jáma.
a Vi,j je pravda ⇔ Na [i, j] je Vánek.
báze znalostí KB:
– pravidlo pro [1, 1]: R1: ¬J1,1
– pozorování: R2: ¬V1,1, R3: V2,1
– pravidla pro vztah Jámy a Vánku:
“Jámy způsobují Vánek ve vedlejších místnostech”
R′
4: J1,2 ⇒ (V1,1 ∧ V2,2 ∧ V1,3)
R′
5: J2,2 ⇒ (V2,1 ∧ V3,2 ∧ V2,3 ∧ V1,2) A
V
?
?
?
Úvod do umělé inteligence 5/12 36 / 36
Výroková logika Tvrzení pro Wumpusovu jeskyni
Tvrzení pro Wumpusovu jeskyni
Definujeme výrokové symboly Ji,j je pravda ⇔ Na [i, j] je Jáma.
a Vi,j je pravda ⇔ Na [i, j] je Vánek.
báze znalostí KB:
– pravidlo pro [1, 1]: R1: ¬J1,1
– pozorování: R2: ¬V1,1, R3: V2,1
– pravidla pro vztah Jámy a Vánku:
“Jámy způsobují Vánek ve vedlejších místnostech”
R′′
4: V1,1 ⇐ (J1,2 ∨ J2,1)
R′′
5: V2,1 ⇐ (J1,1 ∨ J2,2 ∨ J3,1) A
V
?
?
?
Úvod do umělé inteligence 5/12 36 / 36
Výroková logika Tvrzení pro Wumpusovu jeskyni
Tvrzení pro Wumpusovu jeskyni
Definujeme výrokové symboly Ji,j je pravda ⇔ Na [i, j] je Jáma.
a Vi,j je pravda ⇔ Na [i, j] je Vánek.
báze znalostí KB:
– pravidlo pro [1, 1]: R1: ¬J1,1
– pozorování: R2: ¬V1,1, R3: V2,1
– pravidla pro vztah Jámy a Vánku:
“Jámy způsobují Vánek ve vedlejších místnostech”
R′′
4: V1,1 ⇐ (J1,2 ∨ J2,1)
R′′
5: V2,1 ⇐ (J1,1 ∨ J2,2 ∨ J3,1) A
V
?
?
?
“V poli je Vánek právě tehdy, když je ve vedlejším poli Jáma.”
R4: V1,1 ⇔ (J1,2 ∨ J2,1)
R5: V2,1 ⇔ (J1,1 ∨ J2,2 ∨ J3,1)
Úvod do umělé inteligence 5/12 36 / 36
Výroková logika Tvrzení pro Wumpusovu jeskyni
Tvrzení pro Wumpusovu jeskyni
Definujeme výrokové symboly Ji,j je pravda ⇔ Na [i, j] je Jáma.
a Vi,j je pravda ⇔ Na [i, j] je Vánek.
báze znalostí KB:
– pravidlo pro [1, 1]: R1: ¬J1,1
– pozorování: R2: ¬V1,1, R3: V2,1
– pravidla pro vztah Jámy a Vánku:
“Jámy způsobují Vánek ve vedlejších místnostech”
R′′
4: V1,1 ⇐ (J1,2 ∨ J2,1)
R′′
5: V2,1 ⇐ (J1,1 ∨ J2,2 ∨ J3,1) A
V
?
?
?
“V poli je Vánek právě tehdy, když je ve vedlejším poli Jáma.”
R4: V1,1 ⇔ (J1,2 ∨ J2,1)
R5: V2,1 ⇔ (J1,1 ∨ J2,2 ∨ J3,1)
– KB = R1 ∧ R2 ∧ R3 ∧ R4 ∧ R5 SliDo
Úvod do umělé inteligence 5/12 36 / 36