Predikátová logika prvního řádu Aleš Horák E-mail: hales@fi.muni.cz http://nlp.fi.muni.cz/uui/ Obsah: Připomínka – průběžná písemka Predikátová logika prvního řádu Příklady jiných logik Logika a AI Úvod do umělé inteligence 6/12 1 / 33 Připomínka – průběžná písemka Připomínka – průběžná písemka termín – příští pondělí 4. listopadu, 20:00, D1 a D3 náhradní termín: pro nemocné s omluvenkou, požádejte e-mailem nepřihlašuje se – vaši posluchárnu najdete v ISu u termínu zkoušky test obsahuje 7 otázek, 6 za 3 body a 1 za 2 body, celkem max 20 bodů za nesprávnou odpověď se 0.5 bodu odečítá. celkový čas na vypracování testu je 40 minut. nejsou povoleny žádné materiály, ani prázdné papíry. Otázky nesmíte jakýmkoliv způsobem předávat nebo šířit. příklady (formou testu – odpovědi A, B, C, ...) z látky probrané na prvních pěti přednáškách Úvod do umělé inteligence 6/12 2 / 33 Predikátová logika prvního řádu Predikátová logika 1. řádu Obsah 1 Připomínka – průběžná písemka 2 Predikátová logika prvního řádu Predikátová logika 1. řádu Syntaxe predikátové logiky Sémantika predikátové logiky Kvantifikace Substituce proměnných Normální formy v predikátové logice Báze znalostí v PL1 3 Příklady jiných logik Fuzzy logika Pravděpodobnost Modální logiky Logiky vyšších řádů Temporální logiky a Intenzionální logiky 4 Logika a AI Znalostní inženýrství Logika v AIÚvod do umělé inteligence 6/12 3 / 33 Predikátová logika prvního řádu Predikátová logika 1. řádu Výhody a nevýhody výrokové logiky ⌣ výroková logika je deklarativní: syntaxe přímo koresponduje s fakty Úvod do umělé inteligence 6/12 4 / 33 Predikátová logika prvního řádu Predikátová logika 1. řádu Výhody a nevýhody výrokové logiky ⌣ výroková logika je deklarativní: syntaxe přímo koresponduje s fakty ⌣ výroková logika umožňuje zpracovávat částečné/disjunktivní/negované informace (což je víc, než umí většina datových struktur a databází) Úvod do umělé inteligence 6/12 4 / 33 Predikátová logika prvního řádu Predikátová logika 1. řádu Výhody a nevýhody výrokové logiky ⌣ výroková logika je deklarativní: syntaxe přímo koresponduje s fakty ⌣ výroková logika umožňuje zpracovávat částečné/disjunktivní/negované informace (což je víc, než umí většina datových struktur a databází) ⌣ výroková logika je kompoziční: Úvod do umělé inteligence 6/12 4 / 33 Predikátová logika prvního řádu Predikátová logika 1. řádu Výhody a nevýhody výrokové logiky ⌣ výroková logika je deklarativní: syntaxe přímo koresponduje s fakty ⌣ výroková logika umožňuje zpracovávat částečné/disjunktivní/negované informace (což je víc, než umí většina datových struktur a databází) ⌣ výroková logika je kompoziční: význam P1 ∧ P2 je odvozen z významu P1 a P2 Úvod do umělé inteligence 6/12 4 / 33 Predikátová logika prvního řádu Predikátová logika 1. řádu Výhody a nevýhody výrokové logiky ⌣ výroková logika je deklarativní: syntaxe přímo koresponduje s fakty ⌣ výroková logika umožňuje zpracovávat částečné/disjunktivní/negované informace (což je víc, než umí většina datových struktur a databází) ⌣ výroková logika je kompoziční: význam P1 ∧ P2 je odvozen z významu P1 a P2 ⌣ ve výrokové logice je význam kontextově nezávislý Úvod do umělé inteligence 6/12 4 / 33 Predikátová logika prvního řádu Predikátová logika 1. řádu Výhody a nevýhody výrokové logiky ⌣ výroková logika je deklarativní: syntaxe přímo koresponduje s fakty ⌣ výroková logika umožňuje zpracovávat částečné/disjunktivní/negované informace (což je víc, než umí většina datových struktur a databází) ⌣ výroková logika je kompoziční: význam P1 ∧ P2 je odvozen z významu P1 a P2 ⌣ ve výrokové logice je význam kontextově nezávislý ⌢ výroková logika má velice omezenou expresivitu (narozdíl od přirozeného jazyka) např. nemáme jak říct “Jámy způsobují Vánek ve vedlejších místnostech” jinak, než vyjmenovat odpovídající výrok pro každé pole Úvod do umělé inteligence 6/12 4 / 33 Predikátová logika prvního řádu Predikátová logika 1. řádu Výhody a nevýhody přirozeného jazyka ⌣ většina lidí jazyk běžně používá k vyjádření myšlenek a k vyvozování závěrů Úvod do umělé inteligence 6/12 5 / 33 Predikátová logika prvního řádu Predikátová logika 1. řádu Výhody a nevýhody přirozeného jazyka ⌣ většina lidí jazyk běžně používá k vyjádření myšlenek a k vyvozování závěrů ⌣ v jazyce umíme vyjádřit (nebo aspoň popsat) téměř všechny myšlenky – má velkou expresivitu Úvod do umělé inteligence 6/12 5 / 33 Predikátová logika prvního řádu Predikátová logika 1. řádu Výhody a nevýhody přirozeného jazyka ⌣ většina lidí jazyk běžně používá k vyjádření myšlenek a k vyvozování závěrů ⌣ v jazyce umíme vyjádřit (nebo aspoň popsat) téměř všechny myšlenky – má velkou expresivitu ? jazyk je spíš prostředek komunikace než (jen) reprezentace např. Podívej! (... nad střechou se objevil Superman) věta bez daného kontextu nemusí nést (stejnou) informaci Úvod do umělé inteligence 6/12 5 / 33 Predikátová logika prvního řádu Predikátová logika 1. řádu Výhody a nevýhody přirozeného jazyka ⌣ většina lidí jazyk běžně používá k vyjádření myšlenek a k vyvozování závěrů ⌣ v jazyce umíme vyjádřit (nebo aspoň popsat) téměř všechny myšlenky – má velkou expresivitu ? jazyk je spíš prostředek komunikace než (jen) reprezentace např. Podívej! (... nad střechou se objevil Superman) věta bez daného kontextu nemusí nést (stejnou) informaci ⌢ jazyk má velkou víceznačnost (ambiguity) viz matka, zaječí, travička, ... Úvod do umělé inteligence 6/12 5 / 33 Predikátová logika prvního řádu Predikátová logika 1. řádu Výhody a nevýhody přirozeného jazyka ⌣ většina lidí jazyk běžně používá k vyjádření myšlenek a k vyvozování závěrů ⌣ v jazyce umíme vyjádřit (nebo aspoň popsat) téměř všechny myšlenky – má velkou expresivitu ? jazyk je spíš prostředek komunikace než (jen) reprezentace např. Podívej! (... nad střechou se objevil Superman) věta bez daného kontextu nemusí nést (stejnou) informaci ⌢ jazyk má velkou víceznačnost (ambiguity) viz matka, zaječí, travička, ... ? lidé si pamatují obsah, ale ne přesnou formu Úvod do umělé inteligence 6/12 5 / 33 Predikátová logika prvního řádu Predikátová logika 1. řádu Výhody a nevýhody přirozeného jazyka ⌣ většina lidí jazyk běžně používá k vyjádření myšlenek a k vyvozování závěrů ⌣ v jazyce umíme vyjádřit (nebo aspoň popsat) téměř všechny myšlenky – má velkou expresivitu ? jazyk je spíš prostředek komunikace než (jen) reprezentace např. Podívej! (... nad střechou se objevil Superman) věta bez daného kontextu nemusí nést (stejnou) informaci ⌢ jazyk má velkou víceznačnost (ambiguity) viz matka, zaječí, travička, ... ? lidé si pamatují obsah, ale ne přesnou formu byla první věta předchozího slajdu “Výroková logika je deklarativní – syntaxe přímo koresponduje s fakty”, nebo “Syntaxe výrokové logiky je deklarativní, jelikož přímo vyjadřuje fakta”? Úvod do umělé inteligence 6/12 5 / 33 Predikátová logika prvního řádu Predikátová logika 1. řádu Výhody a nevýhody přirozeného jazyka ⌣ většina lidí jazyk běžně používá k vyjádření myšlenek a k vyvozování závěrů ⌣ v jazyce umíme vyjádřit (nebo aspoň popsat) téměř všechny myšlenky – má velkou expresivitu ? jazyk je spíš prostředek komunikace než (jen) reprezentace např. Podívej! (... nad střechou se objevil Superman) věta bez daného kontextu nemusí nést (stejnou) informaci ⌢ jazyk má velkou víceznačnost (ambiguity) viz matka, zaječí, travička, ... ? lidé si pamatují obsah, ale ne přesnou formu ⌢ konkrétní forma přitom ovlivňuje vyvozování Jakou rychlostí jela auta než nastal kontakt? vs ... než se o sebe roztřískala? Úvod do umělé inteligence 6/12 5 / 33 Predikátová logika prvního řádu Predikátová logika 1. řádu Predikátová logika prvního řádu First-order predicate logic, FOPL/PL1 vyšší expresivita než výroková logika, nižší složitost než přirozený jazyk umožňuje strukturovat jednoduché výroky PJ: Každý člověk je smrtelný a Sokrates je člověk, proto Sokrates je smrtelný. Úvod do umělé inteligence 6/12 6 / 33 Predikátová logika prvního řádu Predikátová logika 1. řádu Predikátová logika prvního řádu First-order predicate logic, FOPL/PL1 vyšší expresivita než výroková logika, nižší složitost než přirozený jazyk umožňuje strukturovat jednoduché výroky PJ: Každý člověk je smrtelný a Sokrates je člověk, proto Sokrates je smrtelný. VL: (Č ∧ So) ⇒ Sm Úvod do umělé inteligence 6/12 6 / 33 Predikátová logika prvního řádu Predikátová logika 1. řádu Predikátová logika prvního řádu First-order predicate logic, FOPL/PL1 vyšší expresivita než výroková logika, nižší složitost než přirozený jazyk umožňuje strukturovat jednoduché výroky PJ: Každý člověk je smrtelný a Sokrates je člověk, proto Sokrates je smrtelný. VL: (Č ∧ So) ̸⇒ Sm Úvod do umělé inteligence 6/12 6 / 33 Predikátová logika prvního řádu Predikátová logika 1. řádu Predikátová logika prvního řádu First-order predicate logic, FOPL/PL1 vyšší expresivita než výroková logika, nižší složitost než přirozený jazyk umožňuje strukturovat jednoduché výroky PJ: Každý člověk je smrtelný a Sokrates je člověk, proto Sokrates je smrtelný. VL: (Č ∧ So) ̸⇒ Sm PL1: (∀x čl(x) ⇒ sm(x) ∧ čl(So)) ⇒ sm(So) Úvod do umělé inteligence 6/12 6 / 33 Predikátová logika prvního řádu Predikátová logika 1. řádu Predikátová logika prvního řádu First-order predicate logic, FOPL/PL1 vyšší expresivita než výroková logika, nižší složitost než přirozený jazyk umožňuje strukturovat jednoduché výroky PJ: Každý člověk je smrtelný a Sokrates je člověk, proto Sokrates je smrtelný. VL: (Č ∧ So) ̸⇒ Sm PL1: (∀x čl(x) ⇒ sm(x) ∧ čl(So)) ⇒ sm(So) výroková logika → svět (ontologie) obsahuje fakty × PL1 předpokládá, že svět obsahuje: • objekty – lidi, domy, teorie, barvy, roky, . . . • relace – červený, kulatý, prvočíselný, bratři, větší než, uvnitř, . . . • funkce – otec někoho, nejlepší přítel, plus jedna, začátek čeho, . . . Úvod do umělé inteligence 6/12 6 / 33 Predikátová logika prvního řádu Predikátová logika 1. řádu Predikátová logika prvního řádu First-order predicate logic, FOPL/PL1 vyšší expresivita než výroková logika, nižší složitost než přirozený jazyk umožňuje strukturovat jednoduché výroky PJ: Každý člověk je smrtelný a Sokrates je člověk, proto Sokrates je smrtelný. VL: (Č ∧ So) ̸⇒ Sm PL1: (∀x čl(x) ⇒ sm(x) ∧ čl(So)) ⇒ sm(So) výroková logika → svět (ontologie) obsahuje fakty × PL1 předpokládá, že svět obsahuje: • objekty – lidi, domy, teorie, barvy, roky, . . . • relace – červený, kulatý, prvočíselný, bratři, větší než, uvnitř, . . . • funkce – otec někoho, nejlepší přítel, plus jedna, začátek čeho, . . . Jedna plus dva rovná se tři: objekty jedna, dva, tři, jedna plus dva; relace rovná se; funkce plus Úvod do umělé inteligence 6/12 6 / 33 Predikátová logika prvního řádu Predikátová logika 1. řádu Predikátová logika prvního řádu First-order predicate logic, FOPL/PL1 vyšší expresivita než výroková logika, nižší složitost než přirozený jazyk umožňuje strukturovat jednoduché výroky PJ: Každý člověk je smrtelný a Sokrates je člověk, proto Sokrates je smrtelný. VL: (Č ∧ So) ̸⇒ Sm PL1: (∀x čl(x) ⇒ sm(x) ∧ čl(So)) ⇒ sm(So) výroková logika → svět (ontologie) obsahuje fakty × PL1 předpokládá, že svět obsahuje: • objekty – lidi, domy, teorie, barvy, roky, . . . • relace – červený, kulatý, prvočíselný, bratři, větší než, uvnitř, . . . • funkce – otec někoho, nejlepší přítel, plus jedna, začátek čeho, . . . Jedna plus dva rovná se tři: objekty jedna, dva, tři, jedna plus dva; relace rovná se; funkce plus Pozice vedle Wumpuse zapáchají: objekty pozice, Wumpus; relace zapáchat, vedle Úvod do umělé inteligence 6/12 6 / 33 Predikátová logika prvního řádu Syntaxe predikátové logiky Syntaxe predikátové logiky Úvod do umělé inteligence 6/12 7 / 33 Predikátová logika prvního řádu Syntaxe predikátové logiky Syntaxe predikátové logiky výroková logika: S → A | C A → True | False | P | Q | R | . . . C → (S) | ¬S | S ∧ S | S ∨ S | S ⇒ S | S ⇔ S základní prvky – konstanty KingJohn, 2, RichardTheLionheart, . . . funktory predikátů Brother, >, . . . funkce Sqrt, LeftLegOf, . . . proměnné x, y, a, b, . . . spojky ∧ ∨ ¬ ⇒ ⇔ rovnost = kvantifikátory ∀ ∃ atomické formule – predikáty Brother(KingJohn, RichardTheLionheart) složené termy > Length LeftLegOf(Richard) , Length LeftLegOf(KingJohn) složené formule – z atomických formulí pomocí spojek a kvantifikátorů ¬S, S1 ∧ S2, S1 ∨ S2, S1 ⇒ S2, S1 ⇔ S2, ∀x P(x), ∃x P(x) např. Sibling(KingJohn, Richard) ⇒ Sibling(Richard, KingJohn) >(1, 2) ∨ ≤(1, 2) >(1, 2) ∧ ¬>(1, 2) SliDo Úvod do umělé inteligence 6/12 8 / 33 Predikátová logika prvního řádu Sémantika predikátové logiky Sémantika predikátové logiky pravdivost formule se určuje vzhledem k modelu a interpretaci model obsahuje ≥ 1 objektů a relace mezi nimi objekty modelu se označují jako doména modelu interpretace definuje vztah mezi syntaxí a modelem – určuje referenty pro: konstantní symboly → objekty predikátové symboly → relace funkční symboly → funkce Úvod do umělé inteligence 6/12 9 / 33 Predikátová logika prvního řádu Sémantika predikátové logiky Příklad modelu a interpretace ve FOPL R J$ levá noha levá noha na hlavˇe bratr bratr osoba osoba král koruna 5 objektů, 2 binární relace, 3 unární relace (osoba, král, koruna) a 1 unární funkce (levá noha). Úvod do umělé inteligence 6/12 10 / 33 Predikátová logika prvního řádu Sémantika predikátové logiky Sémantika predikátové logiky konstanty reprezentují jména objektů (individuí) proměnné zastupují jména objektů, jejich hodnoty se mohou měnit funkce reprezentují složená jména objektů např. add(1, 2) (add(2, 1), add(0, 3), . . . ) jsou složená jména pro konstantu 3 poznámka: konstanty jsou nulární funkce term = výraz složený pouze z funkčních symbolů, konstant a proměnných add(x, mul(y, sub(x, y), 1), z) termy vyjadřují aplikaci funkce na argumenty, hodnoty jsou objekty atomická formule predikát(term1, . . . , termn) je pravdivá ⇔ objekty odkazované pomocí term1, . . . , termn jsou v relaci pojmenované funktorem predikát Úvod do umělé inteligence 6/12 11 / 33 Predikátová logika prvního řádu Sémantika predikátové logiky Předpoklad uzavřeného světa 2 užitečné předpoklady ve spojení s bází znalostí: předpoklad uzavřeného světa (closed world assumption) • cokoliv o čem nevíme, že je pravda → bereme za dané, že je to nepravda • využitý např. v Prologu (negace jako neúspěch) předpoklad jednoznačných pojmenování (unique names assumption) • různá jména označují různé objekty Úvod do umělé inteligence 6/12 12 / 33 Predikátová logika prvního řádu Sémantika predikátové logiky Vázaný a volný výskyt proměnných podformule formule A je libovolná spojitá část A, která je sama formulí ∃x((∀yP(z)) ⇒ R(x, y)) má podformule: ∃x((∀yP(z)) ⇒ R(x, y)), (∀yP(z)) ⇒ R(x, y), ∀yP(z), R(x, y), P(z) výskyt proměnné x ve formuli A je vázaný, je x v A v dosahu svého kvantifikátoru výskyt proměnné je volný, není-li vázaný např. výskyt x v předchozí formuli je vázaný proměnné y a z jsou volné Úvod do umělé inteligence 6/12 13 / 33 Predikátová logika prvního řádu Kvantifikace Univerzální kvantifikace ∀⟨proměnné⟩ ⟨formule⟩ “Každý na FI MU je inteligentní:” ∀x Na(x, FI MU) ⇒ inteligentní(x) ∀x P je pravdivé v modelu m ⇔ P je pravdivá pro x = každý možný objekt z modelu m zhruba odpovídá konjunkci instanciací P Na(Petr, FI MU) ⇒ inteligentní(Petr) ∧ Na(Honza, FI MU) ⇒ inteligentní(Honza) ∧ Na(FI MU, FI MU) ⇒ inteligentní(FI MU) ∧ . . . Úvod do umělé inteligence 6/12 14 / 33 Predikátová logika prvního řádu Kvantifikace Existenční kvantifikace ∃⟨proměnné⟩ ⟨formule⟩ “Někdo na MFF UK je inteligentní:” ∃x Na(x, MFF UK) ∧ inteligentní(x) ∃x P je pravdivé v modelu m ⇔ P je pravdivá pro x = nějaký objekt z modelu m zhruba odpovídá disjunkci instanciací P Na(Petr, MFF UK) ∧ inteligentní(Petr) ∨ Na(Honza, MFF UK) ∧ inteligentní(Honza) ∨ Na(MFF UK, MFF UK) ∧ inteligentní(MFF UK) ∨ . . . Úvod do umělé inteligence 6/12 15 / 33 Predikátová logika prvního řádu Kvantifikace Vlastnosti kvantifikací pozor při použití kvantifikátorů na záměnu ∧ a ⇒: dobře špatně znamenalo by “každý P je Q” ∀x P ⇒ Q ∀x P ∧ Q “každý je P i Q” “někdo P je Q” ∃x (P ∧ Q) ∃x (P ⇒ Q) “někdo není P nebo je Q” Úvod do umělé inteligence 6/12 16 / 33 Predikátová logika prvního řádu Kvantifikace Vlastnosti kvantifikací pozor při použití kvantifikátorů na záměnu ∧ a ⇒: dobře špatně znamenalo by “každý P je Q” ∀x P ⇒ Q ∀x P ∧ Q “každý je P i Q” “někdo P je Q” ∃x (P ∧ Q) ∃x (P ⇒ Q) “někdo není P nebo je Q” ∀x∀y je stejné jako ∀y∀x ∃x∃y je stejné jako ∃y∃x ∃x∀y není stejné jako ∀y∃x ∃x∀y má_rád(x, y) – “Existuje osoba, která má ráda všechny lidi na světě.” ∀y∃x má_rád(x, y) – “Každého na světě má alespoň jedna osoba ráda.” (potenciálně každého jiná) Úvod do umělé inteligence 6/12 16 / 33 Predikátová logika prvního řádu Kvantifikace Vlastnosti kvantifikací pozor při použití kvantifikátorů na záměnu ∧ a ⇒: dobře špatně znamenalo by “každý P je Q” ∀x P ⇒ Q ∀x P ∧ Q “každý je P i Q” “někdo P je Q” ∃x (P ∧ Q) ∃x (P ⇒ Q) “někdo není P nebo je Q” ∀x∀y je stejné jako ∀y∀x ∃x∃y je stejné jako ∃y∃x ∃x∀y není stejné jako ∀y∃x ∃x∀y má_rád(x, y) – “Existuje osoba, která má ráda všechny lidi na světě.” ∀y∃x má_rád(x, y) – “Každého na světě má alespoň jedna osoba ráda.” (potenciálně každého jiná) dualita kvantifikátorů oba mohou být vyjádřeny pomocí druhého ∀x má_rád(x, zmrzlina) ≡ ¬∃x ¬má_rád(x, zmrzlina) ∃x má_rád(x, mrkev) ≡ ¬∀x ¬má_rád(x, mrkev) SliDo Úvod do umělé inteligence 6/12 16 / 33 Predikátová logika prvního řádu Substituce proměnných Substituce proměnných substituce σ = {x/add(2, 1), y/4} definuje dosazení za volné proměnné pro větu S a substituci σ – Sσ označuje výsledek aplikace σ na S: S = chytřejší(x, y) σ = {x/Petr, y/Honza} Sσ = chytřejší(Petr, Honza) Úvod do umělé inteligence 6/12 17 / 33 Predikátová logika prvního řádu Substituce proměnných Substituce proměnných substituce σ = {x/add(2, 1), y/4} definuje dosazení za volné proměnné pro větu S a substituci σ – Sσ označuje výsledek aplikace σ na S: S = chytřejší(x, y) σ = {x/Petr, y/Honza} Sσ = chytřejší(Petr, Honza) term t je substituovatelný za proměnnou x ve formuli A ⇔ nedochází ke kolizi volných proměnných v t a vázaných proměnných v A S = ∃xP(x, y) S{y/z} = ∃xP(x, z) S{y/f (z, z)} = ∃xP(x, f (z, z)) nelze S{y/f (x, x)} = ∃xP(x, f (x, x)) kvůli změně vazby x kolizi lze řešit přejmenováním volných proměnných v termu t Úvod do umělé inteligence 6/12 17 / 33 Predikátová logika prvního řádu Normální formy v predikátové logice Konjunktivní normální forma (CNF) v PL1 CNF v PL1 – prenexová (kvantifikátory na začátku) a Skolemova NF (bez ∃) Algoritmus pro převod každé PL1 formule do CNF: 1. převedeme implikace na disjunkce: P ⇒ Q → ¬P ∨ Q 2. přesuneme ¬ dovnitř k literálům: ¬∀x P → ∃x ¬P 3. přejmenujeme proměnné: ∀x P ∨ ∃x Q → ∀x P ∨ ∃y Q 4. přesuneme kvantifikátory doleva: ∀x P ∨ ∃y Q → ∀x∃y P ∨ Q 5. eliminujeme ∃ pomocí Skolemizace: ∃x P(x) → P(c1) ∀x P(x) ⇒ ∃y Q(y) → ∀x P(x) ⇒ Q(f (x)) 6. “zahodíme” univerzální kvantifikátory 7. roznásobíme ∧ pomocí ∨: (P ∧ Q) ∨ R → (P ∨ R) ∧ (Q ∨ R) Úvod do umělé inteligence 6/12 18 / 33 Predikátová logika prvního řádu Normální formy v predikátové logice Konjunktivní normální forma (CNF) v PL1 – příklad ∀x∃y¬(P(x, y) ⇒ ∀zR(y)) ∨ ¬∃xQ(x) Úvod do umělé inteligence 6/12 19 / 33 Predikátová logika prvního řádu Normální formy v predikátové logice Konjunktivní normální forma (CNF) v PL1 – příklad ∀x∃y¬(P(x, y) ⇒ ∀zR(y)) ∨ ¬∃xQ(x) ∀x∃y¬(¬P(x, y) ∨ ∀zR(y)) ∨ ¬∃xQ(x) (⇒ na ∨) Úvod do umělé inteligence 6/12 19 / 33 Predikátová logika prvního řádu Normální formy v predikátové logice Konjunktivní normální forma (CNF) v PL1 – příklad ∀x∃y¬(P(x, y) ⇒ ∀zR(y)) ∨ ¬∃xQ(x) ∀x∃y¬(¬P(x, y) ∨ ∀zR(y)) ∨ ¬∃xQ(x) (⇒ na ∨) ∀x∃y(P(x, y) ∧ ∃z¬R(y)) ∨ ∀x¬Q(x) (přesun negace 3×) Úvod do umělé inteligence 6/12 19 / 33 Predikátová logika prvního řádu Normální formy v predikátové logice Konjunktivní normální forma (CNF) v PL1 – příklad ∀x∃y¬(P(x, y) ⇒ ∀zR(y)) ∨ ¬∃xQ(x) ∀x∃y¬(¬P(x, y) ∨ ∀zR(y)) ∨ ¬∃xQ(x) (⇒ na ∨) ∀x∃y(P(x, y) ∧ ∃z¬R(y)) ∨ ∀x¬Q(x) (přesun negace 3×) ∀x1∃y(P(x1, y) ∧ ∃z¬R(y)) ∨ ∀x2¬Q(x2) (přejmenování x) Úvod do umělé inteligence 6/12 19 / 33 Predikátová logika prvního řádu Normální formy v predikátové logice Konjunktivní normální forma (CNF) v PL1 – příklad ∀x∃y¬(P(x, y) ⇒ ∀zR(y)) ∨ ¬∃xQ(x) ∀x∃y¬(¬P(x, y) ∨ ∀zR(y)) ∨ ¬∃xQ(x) (⇒ na ∨) ∀x∃y(P(x, y) ∧ ∃z¬R(y)) ∨ ∀x¬Q(x) (přesun negace 3×) ∀x1∃y(P(x1, y) ∧ ∃z¬R(y)) ∨ ∀x2¬Q(x2) (přejmenování x) ∀x1∃y∃z(P(x1, y) ∧ ¬R(y)) ∨ ∀x2¬Q(x2) (posun ∃z doleva) ∀x1∃y∃z∀x2(P(x1, y) ∧ ¬R(y)) ∨ ¬Q(x2) (posun ∀x2 doleva) Úvod do umělé inteligence 6/12 19 / 33 Predikátová logika prvního řádu Normální formy v predikátové logice Konjunktivní normální forma (CNF) v PL1 – příklad ∀x∃y¬(P(x, y) ⇒ ∀zR(y)) ∨ ¬∃xQ(x) ∀x∃y¬(¬P(x, y) ∨ ∀zR(y)) ∨ ¬∃xQ(x) (⇒ na ∨) ∀x∃y(P(x, y) ∧ ∃z¬R(y)) ∨ ∀x¬Q(x) (přesun negace 3×) ∀x1∃y(P(x1, y) ∧ ∃z¬R(y)) ∨ ∀x2¬Q(x2) (přejmenování x) ∀x1∃y∃z(P(x1, y) ∧ ¬R(y)) ∨ ∀x2¬Q(x2) (posun ∃z doleva) ∀x1∃y∃z∀x2(P(x1, y) ∧ ¬R(y)) ∨ ¬Q(x2) (posun ∀x2 doleva) ∀x1∀x2(P(x1, f1(x1)) ∧ ¬R(f1(x1))) ∨ ¬Q(x2) (Skolemizace y a z) Úvod do umělé inteligence 6/12 19 / 33 Predikátová logika prvního řádu Normální formy v predikátové logice Konjunktivní normální forma (CNF) v PL1 – příklad ∀x∃y¬(P(x, y) ⇒ ∀zR(y)) ∨ ¬∃xQ(x) ∀x∃y¬(¬P(x, y) ∨ ∀zR(y)) ∨ ¬∃xQ(x) (⇒ na ∨) ∀x∃y(P(x, y) ∧ ∃z¬R(y)) ∨ ∀x¬Q(x) (přesun negace 3×) ∀x1∃y(P(x1, y) ∧ ∃z¬R(y)) ∨ ∀x2¬Q(x2) (přejmenování x) ∀x1∃y∃z(P(x1, y) ∧ ¬R(y)) ∨ ∀x2¬Q(x2) (posun ∃z doleva) ∀x1∃y∃z∀x2(P(x1, y) ∧ ¬R(y)) ∨ ¬Q(x2) (posun ∀x2 doleva) ∀x1∀x2(P(x1, f1(x1)) ∧ ¬R(f1(x1))) ∨ ¬Q(x2) (Skolemizace y a z) (P(x1, f1(x1)) ∧ ¬R(f1(x1))) ∨ ¬Q(x2) (odstranění ∀) Úvod do umělé inteligence 6/12 19 / 33 Predikátová logika prvního řádu Normální formy v predikátové logice Konjunktivní normální forma (CNF) v PL1 – příklad ∀x∃y¬(P(x, y) ⇒ ∀zR(y)) ∨ ¬∃xQ(x) ∀x∃y¬(¬P(x, y) ∨ ∀zR(y)) ∨ ¬∃xQ(x) (⇒ na ∨) ∀x∃y(P(x, y) ∧ ∃z¬R(y)) ∨ ∀x¬Q(x) (přesun negace 3×) ∀x1∃y(P(x1, y) ∧ ∃z¬R(y)) ∨ ∀x2¬Q(x2) (přejmenování x) ∀x1∃y∃z(P(x1, y) ∧ ¬R(y)) ∨ ∀x2¬Q(x2) (posun ∃z doleva) ∀x1∃y∃z∀x2(P(x1, y) ∧ ¬R(y)) ∨ ¬Q(x2) (posun ∀x2 doleva) ∀x1∀x2(P(x1, f1(x1)) ∧ ¬R(f1(x1))) ∨ ¬Q(x2) (Skolemizace y a z) (P(x1, f1(x1)) ∧ ¬R(f1(x1))) ∨ ¬Q(x2) (odstranění ∀) (P(x1, f1(x1)) ∨ ¬Q(x2)) ∧ (¬R(f1(x1)) ∨ ¬Q(x2)) (roznásobení ∧) Úvod do umělé inteligence 6/12 19 / 33 Predikátová logika prvního řádu Normální formy v predikátové logice Konjunktivní normální forma (CNF) v PL1 – příklad ∀x∃y¬(P(x, y) ⇒ ∀zR(y)) ∨ ¬∃xQ(x) ∀x∃y¬(¬P(x, y) ∨ ∀zR(y)) ∨ ¬∃xQ(x) (⇒ na ∨) ∀x∃y(P(x, y) ∧ ∃z¬R(y)) ∨ ∀x¬Q(x) (přesun negace 3×) ∀x1∃y(P(x1, y) ∧ ∃z¬R(y)) ∨ ∀x2¬Q(x2) (přejmenování x) ∀x1∃y∃z(P(x1, y) ∧ ¬R(y)) ∨ ∀x2¬Q(x2) (posun ∃z doleva) ∀x1∃y∃z∀x2(P(x1, y) ∧ ¬R(y)) ∨ ¬Q(x2) (posun ∀x2 doleva) ∀x1∀x2(P(x1, f1(x1)) ∧ ¬R(f1(x1))) ∨ ¬Q(x2) (Skolemizace y a z) (P(x1, f1(x1)) ∧ ¬R(f1(x1))) ∨ ¬Q(x2) (odstranění ∀) (P(x1, f1(x1)) ∨ ¬Q(x2)) ∧ (¬R(f1(x1)) ∨ ¬Q(x2)) (roznásobení ∧) Úvod do umělé inteligence 6/12 19 / 33 Predikátová logika prvního řádu Báze znalostí v PL1 Báze znalostí v PL1 předpokládejme, že agent ve Wumpusově jeskyni cítí Zápach a Vánek, ale nevidí Třpyt, nenarazil do zdi a nezabil Wumpuse v čase t = 5: tell (KB, percept([zápach, vánek, nic , nic , nic ] , 5)). ?- ask(KB,action(A,5)). % ∃A action(A,5) ? tj. dotaz “Vyplývá nějaká akce z KB v čase t = 5?” Úvod do umělé inteligence 6/12 20 / 33 Predikátová logika prvního řádu Báze znalostí v PL1 Báze znalostí v PL1 předpokládejme, že agent ve Wumpusově jeskyni cítí Zápach a Vánek, ale nevidí Třpyt, nenarazil do zdi a nezabil Wumpuse v čase t = 5: tell (KB, percept([zápach, vánek, nic , nic , nic ] , 5)). ?- ask(KB,action(A,5)). % ∃A action(A,5) ? tj. dotaz “Vyplývá nějaká akce z KB v čase t = 5?” odpověď: true, {a/Výstřel} ← substituce (hodnot proměnným) Úvod do umělé inteligence 6/12 20 / 33 Predikátová logika prvního řádu Báze znalostí v PL1 Báze znalostí v PL1 předpokládejme, že agent ve Wumpusově jeskyni cítí Zápach a Vánek, ale nevidí Třpyt, nenarazil do zdi a nezabil Wumpuse v čase t = 5: tell (KB, percept([zápach, vánek, nic , nic , nic ] , 5)). ?- ask(KB,action(A,5)). % ∃A action(A,5) ? tj. dotaz “Vyplývá nějaká akce z KB v čase t = 5?” odpověď: true, {a/Výstřel} ← substituce (hodnot proměnným) Ask(KB, S) vrací některá/všechna σ takové, že KB |= Sσ Úvod do umělé inteligence 6/12 20 / 33 Predikátová logika prvního řádu Báze znalostí v PL1 Báze znalostí pro Wumpusovu jeskyni v PL1 Vnímání: ∀v, tr, n, w, t Percept([Zápach, v, tr, n, w], t) ⇒ Je_zápach(t) ∀z, v, n, w, t Percept([z, v, Třpyt, n, w], t) ⇒ Máme_zlato(t) Reflex: ∀t Máme_zlato(t) ⇒ Action(Zvednutí, t) Reflex s vnitřním stavem: neměli jsme už zlato? ∀t Máme_zlato(t) ∧ ¬Držím(Zlato, t) ⇒ Action(Zvednutí, t) Držím(Zlato, t) není pozorovatelné ⇒ je důležité držet si informace o vnitřních stavech (např. Mám_šíp(t)) Úvod do umělé inteligence 6/12 21 / 33 Predikátová logika prvního řádu Báze znalostí v PL1 Báze znalostí pro Wumpusovu jeskyni pokrač. Vyvozování skrytých skutečností: vlastnosti pozice: ∀x, t Na_poli(Agent, x, t) ∧ Je_zápach(t) ⇒ Zapáchá(x) ∀x, t Na_poli(Agent, x, t) ∧ Je_vánek(t) ⇒ S_vánkem(x) “V poli vedle Jámy je Vánek:” • diagnostické pravidlo – odvodí příčiny z následku ∀y S_vánkem(y) ⇒ ∃x Jáma(x) ∧ Vedle(x, y) • příčinné pravidlo – odvodí výsledek z premisy ∀x, y Jáma(x) ∧ Vedle(x, y) ⇒ S_vánkem(y) • ani jedno z nich není úplné např. příčinné pravidlo neříká, jestli v poli daleko od Jámy nemůže být Vánek • definice vztahu Vánku a Jámy: ∀y S_vánkem(y) ⇔ [∃x Jáma(x) ∧ Vedle(x, y)] Úvod do umělé inteligence 6/12 22 / 33 Predikátová logika prvního řádu Báze znalostí v PL1 Báze znalostí pro Wumpusovu jeskyni – rozhodování počáteční podmínka v KB: Na_poli(Agent, [1, 1], S0) dotaz Ask(KB, ∃s Držím(Zlato, s)) tj., “V jaké situaci budu držet Zlato?” situace jsou propojeny pomocí funkce Result: Result(a, s) . . . situace, která je výsledkem činnosti a v s odpověď (např. v situaci, kdy hned na vedlejším poli je Zlato) {s/Result(Zvednutí, Result(Krok dopředu, S0))} tj., jdi dopředu a zvedni Zlato Úvod do umělé inteligence 6/12 23 / 33 Predikátová logika prvního řádu Báze znalostí v PL1 Báze znalostí pro Wumpusovu jeskyni – rozhodování počáteční podmínka v KB: Na_poli(Agent, [1, 1], S0) dotaz Ask(KB, ∃s Držím(Zlato, s)) tj., “V jaké situaci budu držet Zlato?” situace jsou propojeny pomocí funkce Result: Result(a, s) . . . situace, která je výsledkem činnosti a v s odpověď (např. v situaci, kdy hned na vedlejším poli je Zlato) {s/Result(Zvednutí, Result(Krok dopředu, S0))} tj., jdi dopředu a zvedni Zlato SliDo PL1 je dostatečně expresivní logika pro bázi znalostí Wumpusovy jeskyně Úvod do umělé inteligence 6/12 23 / 33 Příklady jiných logik Obsah 1 Připomínka – průběžná písemka 2 Predikátová logika prvního řádu Predikátová logika 1. řádu Syntaxe predikátové logiky Sémantika predikátové logiky Kvantifikace Substituce proměnných Normální formy v predikátové logice Báze znalostí v PL1 3 Příklady jiných logik Fuzzy logika Pravděpodobnost Modální logiky Logiky vyšších řádů Temporální logiky a Intenzionální logiky 4 Logika a AI Znalostní inženýrství Logika v AIÚvod do umělé inteligence 6/12 24 / 33 Příklady jiných logik Příklady jiných logik výroková a predikátová logika – přesné vymezení (výroků, objektů, relací, ...) Úvod do umělé inteligence 6/12 25 / 33 Příklady jiných logik Příklady jiných logik výroková a predikátová logika – přesné vymezení (výroků, objektů, relací, ...) v reálném světě existují logicky obtížné otázky: Je Brno velké město? Mají v této restauraci lahodné jídlo? Je tento člověk vysoký? odpověď často “záleží na okolnostech” Úvod do umělé inteligence 6/12 25 / 33 Příklady jiných logik Fuzzy logika Fuzzy logika tvrzení mají míru pravdivosti ∈ [0, 1] Brno je velké město – míra pravdivosti 0.7 Praha je velké město – míra pravdivosti 0.9 Úvod do umělé inteligence 6/12 26 / 33 Příklady jiných logik Fuzzy logika Fuzzy logika tvrzení mají míru pravdivosti ∈ [0, 1] Brno je velké město – míra pravdivosti 0.7 Praha je velké město – míra pravdivosti 0.9 malé střední velké Brno Praha velikost Úvod do umělé inteligence 6/12 26 / 33 Příklady jiných logik Fuzzy logika Fuzzy logika tvrzení mají míru pravdivosti ∈ [0, 1] Brno je velké město – míra pravdivosti 0.7 Praha je velké město – míra pravdivosti 0.9 malé střední velké Brno Praha velikost příliš pomalu pomalu optimálně rychle příliš rychle rychlost Úvod do umělé inteligence 6/12 26 / 33 Příklady jiných logik Pravděpodobnost Pravděpodobnost hodnoty pravdivosti zůstávají true a false liší se pravděpodobnost (míra jistoty), že pravdivost je true (∈ [0, 1]) může vycházet např. z naměřené frekvence hodnot v čase Občané ČR hodnotí Brno jako velké město s pravděpodobností 0.8 rozdíly proti fuzzy logice: fuzzy logika pracuje lépe s jazykovými, subjektivními hodnotami pravděpodobnost zpracovává frekvenční, objektivní data fuzzy logika používá stupně příslušnosti a pravidla pravděpodobnost definuje matematické vztahy a distribuce fuzzy logika umožňuje částečnou pravdivost pravděpodobnost počítá náhodnost pomocí statistiky Úvod do umělé inteligence 6/12 27 / 33 Příklady jiných logik Modální logiky Modální logiky nejistotu vyjadřují pomocí nových operátorů jako: nutnost ϕ – nutně platí ϕ, ϕ je vždy pravda možnost ϕ – možná platí ϕ, ϕ je někdy pravda operátory a jsou vzájemně převoditelné: ϕ ⇔ ¬ ¬ϕ ϕ ⇔ ¬ ¬ϕ Lidé jsou smrtelní, tedy neexistuje nesmrtelný člověk. (∀xčlověk(x) ⇒ smrtelný(x)) ⇒ ¬ (∃xčlověk(x) ∧ ¬smrtelný(x)) umožňuje zachytit filosofické vztahy vědomosti (nějaké tvrzení vím), povinnosti (závazku) nebo příčiny pravdivost se vyhodnocuje ve vztahu k možným světům Úvod do umělé inteligence 6/12 28 / 33 Příklady jiných logik Logiky vyšších řádů Logiky vyšších řádů Kdo lže, ten krade. Krást se nemá. Úvod do umělé inteligence 6/12 29 / 33 Příklady jiných logik Logiky vyšších řádů Logiky vyšších řádů Kdo lže, ten krade. ∀xlže(x) ⇒ krade(x) Krást se nemá. špatná_vlastnost(krade) v logikách vyšších řádů (higher-order logic, HOL) je možné kvantifikovat nejen jednotlivé objekty, ale i predikáty a funkce nejvyšší řád může být dán pevně (aritmetika – logika 2.řádu) nebo induktivně neomezeně HOL mají vyšší expresivitu, ale od 2.řádu pro ně neexistuje úplná inference Úvod do umělé inteligence 6/12 29 / 33 Příklady jiných logik Temporální logiky a Intenzionální logiky Temporální logiky a Intenzionální logiky Petr Pavel je prezident ČR: v roce 2024 true v roce 2020 false temporální logiky pracují s časem jako parametrem pro vyhodnocení pravdivosti Úvod do umělé inteligence 6/12 30 / 33 Příklady jiných logik Temporální logiky a Intenzionální logiky Temporální logiky a Intenzionální logiky Petr Pavel je prezident ČR: v roce 2024 true v roce 2020 false temporální logiky pracují s časem jako parametrem pro vyhodnocení pravdivosti intenzionální logiky (IL) definují extenze (z PL1) jako hodnoty intenzí v daném světě a čase. IL umožňují: rozlišovat tvrzení de re a de dicto Biden je prezident USA. Trump chce být prezidentem USA, tedy Trump chce být Bidenem. Úvod do umělé inteligence 6/12 30 / 33 Příklady jiných logik Temporální logiky a Intenzionální logiky Temporální logiky a Intenzionální logiky Petr Pavel je prezident ČR: v roce 2024 true v roce 2020 false temporální logiky pracují s časem jako parametrem pro vyhodnocení pravdivosti intenzionální logiky (IL) definují extenze (z PL1) jako hodnoty intenzí v daném světě a čase. IL umožňují: rozlišovat tvrzení de re a de dicto Biden je prezident USA. Trump chce být prezidentem USA, tedyneplatí, že Trump chce být Bidenem. Úvod do umělé inteligence 6/12 30 / 33 Příklady jiných logik Temporální logiky a Intenzionální logiky Temporální logiky a Intenzionální logiky Petr Pavel je prezident ČR: v roce 2024 true v roce 2020 false temporální logiky pracují s časem jako parametrem pro vyhodnocení pravdivosti intenzionální logiky (IL) definují extenze (z PL1) jako hodnoty intenzí v daném světě a čase. IL umožňují: rozlišovat tvrzení de re a de dicto Biden je prezident USA. Trump chce být prezidentem USA, tedyneplatí, že Trump chce být Bidenem. rozlišovat postoje Vím, že Petr věří, že Země je plochá. Úvod do umělé inteligence 6/12 30 / 33 Logika a AI Znalostní inženýrství Obsah 1 Připomínka – průběžná písemka 2 Predikátová logika prvního řádu Predikátová logika 1. řádu Syntaxe predikátové logiky Sémantika predikátové logiky Kvantifikace Substituce proměnných Normální formy v predikátové logice Báze znalostí v PL1 3 Příklady jiných logik Fuzzy logika Pravděpodobnost Modální logiky Logiky vyšších řádů Temporální logiky a Intenzionální logiky 4 Logika a AI Znalostní inženýrství Logika v AIÚvod do umělé inteligence 6/12 31 / 33 Logika a AI Znalostní inženýrství Znalostní inženýrství Knowledge engineering 1. identifikovat otázky 2. shromáždit příslušné znalosti (knowledge acquisition) 3. určit slovník predikátů, funkcí a konstant (ontologii) – ovlivňuje efektivitu 4. zakódovat obecné znalosti o doméně 5. zakódovat popis instance problému 6. položit dotazy inferenční proceduře a získat odpovědi 7. ladit a evaluovat bázi znalostí – hledat, jestli jde odvodit nepravdivé nebo nejde odvodit pravdivé závěry Úvod do umělé inteligence 6/12 32 / 33 Logika a AI Logika v AI Logika v AI využití logických principů v AI: strukturní ekvivalence – např. elektronických obvodů, kódů verifikace programů plánování a splňování podmínek konzistenční diagnóza rozhodování na základě pravidel a vstupu zpracování neúplných nebo nejistých znalostí strojové učení: • indukce hypotéz • neuro-symbolické učení Úvod do umělé inteligence 6/12 33 / 33