Výroková logika a FOPL
ISKM89 Organizace dat - sémantický web | podzim 2023
Zuzana Nevěřilová | Centrum zpracování přirozeného jazyka
Tim Berners-Lee vynalezl web.
je tvrzení.
Tvrzení má pravdivostní hodnotu.
Co to znamená?
Příklad tvrzení
Sémantický web je propojení objektů na internetu tak, aby mu “rozuměli” lidé i počítačové
programy.
Počítačové programy potřebují formalizaci.
Výroková logika a predikátová logika prvního řádu jsou příkladem formalizace tvrzení, včetně
zkoumání pravdivostních hodnot.
● Tim Berners-Lee vynalezl web.
● Tim Berners-Lee vynalezl sémantický
web.
Formalizace tvrzení
Entity
● Tim Berners-Lee
● Web
● Sémantický web
Relace
● Vynalézt
Pravdivostní hodnota
● NE/Pravda (v čase a místě)
Množiny
Sdružují prvky podle vlastnosti
(celá čísla, měsíce v roce,
britští spisovatelé)
Prvky jsou si rovny
Operace nad množinami
● průnik
● sjednocení
Množiny a relace
Relace
(některé) prvky kartézského součinu
A × B = {(a, b) : a ∈ A and b ∈ B}
Př.: A = {1,2,7}, B = {4,5}
R< = {(1,4), (1,5), (2,4), (2,5)}
Vlastnosti relací
reflexivita, symetrie, tranzitivita,
antisymetrie, ekvivalence, uspořádání…
Výrok
cokoli, co může mít pravdivostní hodnotu
(oznamovací věta, která tvrdí fakta)
Co není výrok:
● ahoj
● kolik to stojí?
● růžová je nejkrásnější barva
● kéž by už byl konec
● prohlašuji vaše manželství za
uzavřené
Výroková logika (propositional logic/calculus)
Operátory (výrokové spojky): ⋀, ⋁, ¬, ⇒
p = “Alice maluje pokoj”
q = “Bob maluje Monu Lisu”
¬p – Alice nemaluje pokoj.
¬p ⋀ q
– Alice nemaluje pokoj a/ale
Bob maluje Monu Lisu
⇒ implikace p⇒q = (p ⋀ q)⋁¬p
Formule, atomická formule
Výrok je atomická formule. Atomická formule je formule.
Výroky spojené logickými spojkami jsou formule.
Výroková logika (propositional logic/calculus)
Pravdivostní ohodnocení
Atomické formule:
● matematicky
e(“2 je sudé číslo”) = 1
● empiricky
e(“Mt. Everest je nejvyšší hora”) = 1
Výroková logika, pravdivostní hodnoty
Pravdivostní ohodnocení
Složené formule
Pravdivostní tabulky
p q p ⋀ q ¬(p ⋀ q)
0 0 0 1
0 1 0 1
1 0 0 1
1 1 1 0
Predikát P(t) – pro objekt reprezentovaný
t platí P. t nazýváme term.
malovat(x)
– x maluje. (x je proměnná)
malovat(Alice)
– Alice maluje. (Alice je konstanta.)
Arita: n-ární predikát P(x_1,x_2,…x_n)
malovat(Alice, pokoj)
– Alice maluje pokoj.
Predikátová logika prvního řádu (First-order predicate logic, FOPL)
Operátory (stejné jako ve VL): ⋀, ⋁, ¬
¬malovat(Alice, pokoj)
– Alice nemaluje pokoj.
¬malovat(Alice, pokoj) ⋀ malovat(Bob,MonaLisa).
– Alice nemaluje pokoj a/ale Bob
maluje Monu Lisu..
Kvantifikátory ∀, ∃
∀x:¬malovat(x)
– nikdo nemaluje
Věty v přirozeném jazyce lze převést na formule FOPL (a naopak).
Tim Berners-Lee vynalezl web. → vynalézt(TimBerners-Lee, Web)
Typicky je vhodné určit přísudek věty jako predikát.
Kvantifikátory FOPL jen někdy odpovídají kvantifikátorům v přirozeném jazyce.
Každý používá web → ∀x: používat(x, Web)
Někdo web nepoužívá → ∃x: ¬používat(x, Web)
Skoro všichni web používají → ?x: používat(x, Web)
Predikátová logika a přirozený jazyk
Výhodou FOPL je možnost vyjadřovat se o objektech (konstantách) a proměnných.
Také můžeme odvozovat znalosti pomocí dedukce.
Tim Berners-Lee vynalezl web.
Tim Berners-Lee vynalezl sémantický web.
Kdo něco vynalezne, je vynálezce.
Tim Berners-Lee něco vynalezl.
Tim Berners-Lee je vynálezce.
Predikátová logika a odvozování
Některým víceznačným větám v přirozeném jazyce rozumíme díky své znalosti:
Jeden Američan každou hodinu zemře na rakovinu.
→ ∃a∀h: zemřít(a, h)
→ ∀h∃a: zemřít(a, h)
Predikátová logika a přirozený jazyk, limity
FOPL neumí popsat sekvence:
Honza kopnul a míč přistál v brance. → kopnout(Honza)⋀přistát(míč, branka)
kopnout(Honza)⋀přistát(míč, branka) = přistát(míč, branka)⋀kopnout(Honza)
přistát(míč, branka)⋀kopnout(Honza) → Míč přistál v brance a Honza kopnul.
Predikátová logika a přirozený jazyk, limity
FOPL nerozlišuje tvrzení o třídě a o individuu.
Český prezident je volen na 5 let.
Český prezident rád jezdí na motorce.
Problémy s odvozováním
Petr Pavel je českým prezidentem.
Andrej Babiš se chtěl stát českým prezidentem.
Andrej Babiš se chtěl stát Petrem Pavlem.
Predikátová logika a přirozený jazyk, limity
FOPL nerozlišuje tvrzení o slově (označení) a o konceptu.
Mus syllaba est. Syllaba autem caseum non rodit; mus ergo caseum non rodit.
(Myš je slabika. Ale slabika sýr nekouše; myš tedy sýr nekouše.)
Predikátová logika a přirozený jazyk, limity
Ve FOPL argumentem predikátu nemůže být predikát.
P, Q, x, y. P(x) ✅ P(x)⋀Q(y)✅ P(Q) ❌
Andrej Babiš lhal. → lhát(AndrejBabiš) ✅
Lhát se nesmí. → ¬smět(lhát) ❌ není predikát prvního řádu
Predikátová logika a přirozený jazyk, co je první řád?