Predikátová logika l.řádu
Teorie logického programování
JS> PROLOG: PROgramming in LOGic, Část predikátové logiky l.rádu
A fakta: rodic(petr,petrik), VXa(X)
klauzule: VXVY rodic(X,Y) => predek(X,Y)
Hana Rudová, Logické programování I, 22. března 2011
2
Teorie logického programování
Teorie logického programování
JS> PROLOG: PROgramming in LOGic, Část predikátové logiky l.rádu
A fakta: rodic(petr,petrik), VXa(X)
klauzule: VXVY rodic(X,Y) => predek(X,Y)
& Predikátová logika I. rádu (PL1)
3 soubory objektu: lidé, Čísla, body prostoru, ...
-** syntaxe PL1, sémantika PL1, pravdivost a dokazatelnost
Hana Rudová, Logické programování I, 22. března 2011
2
Teorie logického programování
Teorie logického programování
JS> PROLOG: PROgramming in LOGic, cást predikátové logiky 1. rádu
A fakta: rodic(petr,petrik), VXa(X)
klauzule: VXVY rodic(X,Y) => predek(X,Y)
& Predikátová logika I. rádu (PL1)
3 soubory objektu: lidé, Čísla, body prostoru, ...
-** syntaxe PL1, sémantika PL1, pravdivost a dokazatelnost
-í* Rezoluce ve výrokové logice, v PL1 A dokazovací metoda
ií> Rezoluce v logickém programování C- Backtracking, r ez, negace vs. rezoluce
Hana Rudová, Logické programování I, 22. b řezná 2011
2
Teorie logického programování
Predikátová logika I. řádu (PL1)
Abeceda A jazyka L PLI se skládá ze symbolů:
JS> proměnné X, Y, ... oznaCůjí libovolný objekt z daného oborů
Hana Rudová, Logické programování I, 22. března 2011
3
Predikátová logika
Predikátová logika I. řádu (PL1)
Abeceda A jazyka L PL1 se skládá ze symbolů:
JS> proměnné X, Y, ... oznaCůjí libovolný objekt z daného oborů
& funkční symboly f, g, ... oznaCůjí operace (príklad: +, x )
-i- arita = poCet argumentů, n-ární symbol, znaCíme f/n
nůlární fůnkCní symboly - konstanty: oznaCůjí význaCné objekty (príklad: 0, 1, ...)
Hana Růdová, LogiCké programování I, 22. března 2011
3
Predikátová logika
Predikátová logika I. řádu (PL1)
Abeceda A jazyka L PL1 se skládá ze symbolů:
JS> proměnné X, Y, ... oznaCůjí libovolný objekt z daného oborů
& funkční symboly f, g, ... oznaCůjí operace (príklad: +, x )
-i- arita = poCet argumentů, n-ární symbol, znaCíme f/n
nůlární fůnkCní symboly - konstanty: oznaCůjí význaCné objekty (príklad: 0, 1, ...)
& predikátové symboly p,q, ... pro vyjádření vlastností a vztahů mezi objekty arita = poCet argůmentů, n-ární symbol, znaCíme p/n      príklad: <, g
Hana Růdová, LogiCké programování I, 22. brezna 2011
3
Predikátová logika
Predikátová logika I. řádu (PL1)
Abeceda A jazyka L PL1 se skládá ze symbolů:
JS> proměnné X, Y, ... oznaCůjí libovolný objekt z daného oborů
& funkční symboly f, g, ... oznaCůjí operace (príklad: +, x )
-i- arita = poCet argumentů, n-ární symbol, znaCíme f/n
nůlární fůnkCní symboly - konstanty: oznaCůjí význaCné objekty (príklad: 0, 1, ...)
& predikátové symboly p,q, ... pro vyjádření vlastností a vztahů mezi objekty arita = poCet argůmentů, n-ární symbol, znaCíme p/n      príklad: <, g
& logické spojky a, v,     =>, =
Hana Růdová, LogiCké programování I, 22. brezna 2011
3
Predikátová logika
Predikátová logika I. řádu (PL1)
Abeceda A jazyka L PLI se skládá ze symbolů:
JS> proměnné X, Y, ... oznaCůjí libovolný objekt z daného oborů
& funkční symboly f, g, ... oznaCůjí operace (príklad: +, x )
-i- arita = poCet argůmentů, n-ární symbol, znaCíme f/n
nůlární fůnkCní symboly - konstanty: oznaCůjí význaCné objekty (príklad: 0, 1, ...)
& predikátové symboly p,q, ... pro vyjádření vlastností a vztahů mezi objekty arita = poCet argůmentů, n-ární symbol, znaCíme p/n      príklad: <, g
& logické spojky a, v,     =>, =
JS> kvantifikátory V, 3
± logika I. rádů poůžívá kvantifikaci pouze pro individua (odlišnost od logik vyššího rádů) v logiCe 1. rádů nelze: v R : V A c R, Vf : R - R
Hana Růdová, LogiCké programování I, 22. brezna 2011
3
Predikátová logika
Predikátová logika I. řádu (PL1)
Abeceda A jazyka L PL1 se skládá ze symbolu:
JS> proměnné X, Y, ... oznacují libovolný objekt z daného oboru
& funkční symboly f, g, ... oznacují operace (príklad: +, x )
-i- arita = pocet argumentu, n-ární symbol, znacíme f/n
nulární funkcní symboly - konstanty: oznacují význacné objekty (príklad: 0, 1, ...)
& predikátové symboly p,q, ... pro vyjádrení vlastností a vztahů mezi objekty arita = pocet argumentů, n-ární symbol, znacíme p/n      príklad: <, g
& logické spojky a, v,     =>, =
JS> kvantifikátory V, 3
± logika I. rádu používá kvantifikaci pouze pro individua (odlišnost od logik vyššího rádu) v logice 1. rádu nelze: v R : V A c R, Vf : R - R
& závorky: ),(
Hana Rudová, Logické programování I, 22. brezna 2011 3 Predikátová logika
Jazyky PLI
Specifikace jazyka L je definována funkčními a predikátovými symboly symboly tedy určují oblast, kterou jazyk popisuje
Jazyky s rovností: obsahují predikátový symbol pro rovnost „="
Hana Rudová, Logické programování I, 22. března 2011
4
Predikátová logika
Jazyky PL1
Specifikace jazyka L je definována funkčními a predikátovými symboly symboly tedy určují oblast, kterou jazyk popisuje
& Jazyky s rovností: obsahují predikátový symbol pro rovnost „=" Příklady
C jazyk teorie uspořádání
J* jazyk s =, binární prediátový symbol <
Hana Rudová, Logické programování I, 22. brezna 2011
4
Predikátová logika
Jazyky PL1
Specifikace jazyka L je definována funkčními a predikátovými symboly symboly tedy urcují oblast, kterou jazyk popisuje
& Jazyky s rovností: obsahují predikátový symbol pro rovnost „=" Príklady
C jazyk teorie usporádání
J* jazyk s =, binární prediátový symbol <
JS* jazyk teorie množin
-i- jazyk s =, binární predikátový symbol g
Hana Rudová, Logické programování I, 22. b rezna 2011
4
Predikátová logika
Jazyky PL1
SpeCifikaCe jazyka L je definována fůnkCními a predikátovými symboly symboly tedy ůrCůjí oblast, kteroů jazyk popisůje
& Jazyky s rovností: obsahují predikátový symbol pro rovnost „=" Příklady
C jazyk teorie ůsporádání
& jazyk s =, binární prediátový symbol <
JS* jazyk teorie množin
-i- jazyk s =, binární predikátový symbol g
& jazyk elementární aritmetiky
jazyk s =, nůlární fůnkCní symbol 0 pro nůlů, ůnární fůnkCní symbol s pro operaCi následníka, binární fůnkCní symboly pro sCítání + a násobení x
Hana Růdová, LogiCké programování I, 22. brezna 2011 4 Predikátová logika
Term, atomická formule, formule
Term nad abecedou A
Jť každá promenná z A je term
je-li f/n z A a t\,...,tn jsou termy, pak f(t\, ...,tn) je také term -i- každý term vznikne konečným počtem užití prechozích kroku f( X, g(X,0))
Hana Rudová, Logické programování I, 22. března 2011
5
Predikátová logika
Term, atomická formule, formule
Term nad abecedou A
Jť každá promenná z A je term
je-li f/n z A a t1,...,tn jsou termy, pak f(t\, ...,tn) je také term -i- každý term vznikne konecným poctem užití p r echozích kroku f( X, g(X,0))
& Atomická formule (atom) nad abecedou A
-fc je-li p/n z A a t1,...,tn jsou termy, pak p(t1,. ..,tn) je atomická formule     f(X) < g(X,0)
Hana Rudová, Logické programování I, 22. b rezna 2011
5
Predikátová logika
Term, atomická formule, formule
Term nad abeCedoů A
Jť každá promenná z A je term
je-li f/n z A a t1,...,tn jsoů termy, pak f(t1, ...,tn) je také term -i- každý term vznikne koneCným poCtem ůžití preChozíCh kroků f( X, g(X,0))
& Atomická formule (atom) nad abeCedoů A
je-li p/n z A a t1,...,tn jsoů termy, pak p(ti,...,tn) je atomiCká formůle     f(X) < g(X,0)
& Formule nad abeCedoů A
A každá atomiCká formůle je formůle
J> jsoů-li F a G formůle, pak také (-F), (F a G), (F v G), (F == G), (F = G) jsoů formůle & je-li X promenná a F formůle, pak také (VX F) a (3X F) jsoů formůle
každá formůle vznikne koneCným poCtem ůžití preChozíCh kroků     (3X ((f(X) = 0) a p(0)))
Hana Rudová, Logické programování I, 22. března 2011
5
Predikátová logika
Interpretace
Interpretace I jazyka L nad abeCedoů A je dána
neprázdnoů množinoů D (také znaCíme jlj, nazývá se univerzum) a & zobrazením, které
každé konstante c e A priradí nejaký prvek D
každémů fůnkCnímů symbolů f in e A priradí n-ární operaci nad D
každémů predikátovémů symbolů p in e A priradí n-ární relaci nad D
Hana Růdová, LogiCké programování I, 22. brezna 20ll
6
Predikátová logika
Interpretace
Interpretace I jazyka L nad abecedou A je dána
a neprázdnou množinou D (také znaCíme      nazývá se univerzum) a 3» zobrazením, které
každé konstante c g A priradí nejaký prvek D
každému funkCnímu symbolu f/n g A priradí n-ární operaci nad D
každému predikátovému symbolu p/n g A priradí n-ární relaci nad D
Príklad: usporádání na R
a jazyk: predikátový symbol mensi/2
& interpretace: univerzum R; zobrazení: mensi(x,y) := x < y
Hana Rudová, Logické programování I, 22. b rezna 2011
6
Predikátová logika
Interpretace
& Interpretace I jazyka L nad abecedou A je dána
a neprázdnou množinou D (také znaCíme      nazývá se univerzum) a a zobrazením, které
každé konstante c g A priradí nejaký prvek D
každému funkCnímu symbolu f/n g A priradí n-ární operaci nad D
každému predikátovému symbolu p/n g A priradí n-ární relaci nad D
-í* Príklad: uspořádání na R
a jazyk: predikátový symbol mensi/2
& interpretace: univerzum R; zobrazení: mensi(x,y) := x < y
Ü* Príklad: elementární aritmetika nad množinou N (vCetne 0)
-fc jazyk: konstanta zero, funCní symboly s/1, plus/2 J* interpretace:
univerzum N; zobrazení: zero := 0,   s(x) := 1 + x,   plus(x,y) := x + y
Hana Rudová, Logické programování I, 22. brezna 2011 6 Predikátová logika
Sémantika formulí
Ohodnocení proměnné qp(X): každé promenné X je prirazen prvek |1|
Hodnota termu qp(t): každému termu je prirazen prvek univerza
príklad: necht' qp(X) := 0 qp(plus(s(zero),X)) =
Hana Rudová, Logické programování I, 22. b rezna 2011
7
Predikátová logika
Sémantika formulí
Ohodnocení proměnné qp(X): každé promenné X je prirazen prvek |1|
Hodnota termu qp(t): každémů termů je prirazen prvek ůniverza
príklad: neCht' qp(X) := 0
qp (plus (s (zero), X)) = qp(s(zero)) + qp(X) =
Hana Růdová, LogiCké programování I, 22. b rezna 2011
7
Predikátová logika
Sémantika formulí
Ohodnocení proměnné qp(X): každé promenné X je prirazen prvek |1| Hodnota termu qp(t): každémů termů je prirazen prvek ůniverza
príklad: neCht' qp(X) := 0
qp (plus (s (zero), X)) = qp(s(zero)) + qp(X) = (1 + qp(zero)) + 0 =
Hana Růdová, LogiCké programování I, 22. b rezna 2011
7
Predikátová logika
Sémantika formulí
Ohodnocení proměnné qp(X): každé promenné X je prirazen prvek |1| Hodnota termu op(t): každémů termů je prirazen prvek ůniverza
príklad: neCht' qp(X) := 0
q (plus (s (zero), X)) = cp(s(zero)) + q>(X) = (1 + op(zero)) + 0 = (1 + 0) + 0 = 1
Hana Růdová, LogiCké programování I, 22. b rezna 2011
7
Predikátová logika
Sémantika formulí
Ohodnocení promenné q(X): každé promenné X je p r i razen prvek |1| Hodnota termu q(t): každému termu je p r i razen prvek univerza
p r íklad: necht' qp(X) := 0
q (plus (s (zero), X)) = q(s(zero)) + q(X) = (i + q(zero)) + 0 = (i + 0) + 0 = i
Každá dobre utvorená formule oznacuje pravdivostní hodnotu (pravda, nepravda) v závislosti na své struktu r e a interpretaci
Pravdivá formule I     q: formule q oznacena pravda Neravdivá formule I Nq? Q: formule Q oznacena nepravda
Hana Rudová, Logické programování I, 22. b rezna 2011
7
Predikátová logika
Sémantika formulí
Ohodnocení proměnné qp(X): každé promenné X je prirazen prvek |1| Hodnota termu op(t): každémů termů je prirazen prvek ůniverza
príklad: neCht' qp(X) := 0
qp (plus (s (zero), X)) = qp(s(zero)) + qp(X) = (1 + qp(zero)) + 0 = (1 + 0) + 0 = 1
Každá dobre utvorená formule oznaCůje pravdivostní hodnotu (pravda, nepravda) v závislosti na své strůktůre a interpretaCi
Pravdivá formule I Nq q: formůle q oznaCena pravda Neravdivá formule I     Q: formůle Q oznaCena nepravda
-fc príklad: p/1 predikátový symbol, tj. p ^ |1|      p := {(1), (3), (5),...} I N p (zero) a p (s (zero))
Hana Růdová, LogiCké programování I, 22. b rezna 2011
7
Predikátová logika
Sémantika formulí
Ohodnocení proměnné qp(X): každé proměnné X je přiřazen prvek |1| Hodnota termu op(t): každému termu je přiřazen prvek univerza
príklad: necht' qp(X) := 0
q (plus (s (zero), X)) = qp(s(zero)) + qp(X) = (1 + qp(zero)) + 0 = (1 + 0) + 0 = 1
Každá dobre utvorená formule oznaCuje pravdivostní hodnotu (pravda, nepravda) v závislosti na své strukture a interpretaci
Pravdivá formule I Nq q: formule q oznaCena pravda Neravdivá formule I ^ q: formule Q oznaCena nepravda
-fc príklad: p/1 predikátový symbol, tj. p ^ |1|      p := {(1), (3), (5),...} I N p(zero) a p(s(zero)) iff I N p(zero) a I N p(s(zero))
Hana Rudová, Logické programování I, 22. brezna 2011
7
Predikátová logika
Sémantika formulí
Ohodnocení proměnné qp(X): každé proměnné X je přiřazen prvek |1| Hodnota termu op(t): každému termu je přiřazen prvek univerza
príklad: necht' qp(X) := 0
q (plus (s (zero), X)) = qp(s(zero)) + qp(X) = (1 + qp(zero)) + 0 = (1 + 0) + 0 = 1
Každá dobre utvorená formule oznaCuje pravdivostní hodnotu (pravda, nepravda) v závislosti na své strukture a interpretaci
Pravdivá formule I Nq q: formule Q oznaCena pravda Neravdivá formule I Nq q: formule Q oznaCena nepravda
-fc príklad: p/1 predikátový symbol, tj. p ^ |1|      p := {(1), (3), (5),...} I N p(zero) a p(s(zero)) iff I N p(zero) a I N p(s(zero))
iff  (qp(zero)) g p a (qp(s(zero))) g p
Hana Rudová, Logické programování I, 22. brezna 2011
7
Predikátová logika
Sémantika formulí
Ohodnocení proměnné qp(X): každé proměnné X je přiřazen prvek |1| Hodnota termu op(t): každému termu je přiřazen prvek univerza
príklad: necht' qp(X) := 0
q (plus (s (zero), X)) = qp(s(zero)) + qp(X) = (1 + qp(zero)) + 0 = (1 + 0) + 0 = 1
Každá dobre utvorená formule oznaCuje pravdivostní hodnotu (pravda, nepravda) v závislosti na své strukture a interpretaci
Pravdivá formule I Nq q: formule Q oznaCena pravda Neravdivá formule I Nq q: formule Q oznaCena nepravda
Jt príklad: p/1 predikátový symbol, tj. p ^ |1|      p := {(1), (3), (5),...} I N p(zero) a p(s(zero)) iff I N p(zero) a I N p(s(zero))
iff  (qp(zero)) g p a (qp(s(zero))) g p iff  (qp(zero)) g p a ((1 + qp(zero)) g p
Hana Rudová, Logické programování I, 22. brezna 2011
7
Predikátová logika
Sémantika formulí
Ohodnocení proměnné qp(X): každé proměnné X je přiřazen prvek |1| Hodnota termu op(t): každému termu je přiřazen prvek univerza
príklad: necht' qp(X) := 0
q (plus (s (zero), X)) = qp(s(zero)) + qp(X) = (1 + qp(zero)) + 0 = (1 + 0) + 0 = 1
Každá dobre utvorená formule oznaCuje pravdivostní hodnotu (pravda, nepravda) v závislosti na své strukture a interpretaci
Pravdivá formule I Nq q: formule Q oznaCena pravda Neravdivá formule I Nq Q: formule Q oznaCena nepravda
& príklad: p/1 predikátový symbol, tj. p ^ |1|      p := {(1), (3), (5),...} I N p(zero) a p(s(zero)) iff I N p(zero) a I N p(s(zero))
iff  (qp(zero)) g p a (qp(s(zero))) g p iff  (qp(zero)) g p a ((1 + qp(zero)) g p iff  (0) g p a (1) g p (1) g p ale (0) G p, tedy formule je nepravdivá v I
Hana Rudová, Logické programování I, 22. brezna 2011
7
Predikátová logika
Model
InterpretaCe se nazývá modelem formůle, je-li v ní tato formůle pravdivá
interpretaCe množiny N s obvyklými operaCemi je modelem formůle ( 1 + s(0) = s(s(0))) Jt interpretaCe, která se liší prirazením s/1: s(x):=x není modelem této formůle
Hana Růdová, LogiCké programování I, 22. b rezna 2011
8
Predikátová logika
Model
Interpretace se nazývá modelem formule, je-li v ní tato formule pravdivá
interpretace množiny N s obvyklými operacemi je modelem formule ( 1 + s(0) = s(s(0))) interpretace, která se liší prirazením s/1: s(x):=x není modelem této formule
Teorie T jazyka L je množina formulí jazyka L, tzv. axiomů
- s(X) = 0 je jeden z axiomu teorie elementární aritmetiky
Hana Rudová, Logické programování I, 22. b rezna 2011
8
Predikátová logika
Model
Interpretace se nazývá modelem formule, je-li v ní tato formule pravdivá
interpretace množiny N s obvyklými operacemi je modelem formule ( 1 + s(0) = s(s(0))) interpretace, která se liší prirazením s/1: s(x):=x není modelem této formule
Teorie T jazyka L je množina formulí jazyka L, tzv. axiomů
- s(X) = 0 je jeden z axiomu teorie elementární aritmetiky
Model teorie: libovolná interpretace, která je modelem všech jejích axiomů J* všechny axiomy teorie musí být v této interpretaci pravdivé
Hana Rudová, Logické programování I, 22. b rezna 2011
8
Predikátová logika
Model
Interpretace se nazývá modelem formule, je-li v ní tato formule pravdivá
interpretace množiny N s obvyklými operacemi je modelem formule ( 1 + s(0) = s(s(0))) interpretace, která se liší prirazením s/1: s(x):=x není modelem této formule
Teorie T jazyka L je množina formulí jazyka L, tzv. axiomů
- s(X) = 0 je jeden z axiomu teorie elementární aritmetiky
Model teorie: libovolná interpretace, která je modelem všech jejích axiomů J* všechny axiomy teorie musí být v této interpretaci pravdivé
Pravdivá formule v teorii T = F: pravdivá v každém z modelů teorie T
A ríkáme také formule platí v teorii nebo je splnena v teorii
± formule 1 + s(0) = s(s(0))je pravdivá v teorii elementárních císel
Hana Rudová, Logické programování I, 22. brezna 2011
8
Predikátová logika
Model
InterpretaCe se nazývá modelem formůle, je-li v ní tato formůle pravdivá
& interpretaCe množiny N s obvyklými operaCemi je modelem formůle ( 1 + s(0) = s(s(0))) interpretaCe, která se liší prirazením s/1: s(x):=x není modelem této formůle
JS> Teorie T jazyka L je množina formůlí jazyka L, tzv. axiomů
- s(X) = 0 je jeden z axiomů teorie elementární aritmetiky
-i* Model teorie: libovolná interpretaCe, která je modelem všeCh jejíCh axiomů J* všeChny axiomy teorie můsí být v této interpretaCi pravdivé
& Pravdivá formule v teorii T = F: pravdivá v každém z modelů teorie T
A ríkáme také formůle platí v teorii nebo je splnena v teorii
± formůle 1 + s(0) = s(s(0))je pravdivá v teorii elementárníCh Císel
JS> Logicky pravdivá formule = F: libovolná interpretaCe je jejím modelem
S> nebo-li F je pravdivá v každém modelů libovolné teorie
formůle G v - G je logiCky pravdivá, formůle 1 + s(0) = s(s(0)) není logiCky pravdivá
Hana Růdová, LogiCké programování I, 22. brezna 2011 8 Predikátová logika
Zkoumání pravdivosti formulí
Zjištení pravdivosti provádíme dukazem
Důkaz: libovolná posloupnost Fi,..., Fn formulí jazyka L, v níž každé Fi je bud' axiom teorie jazyka L nebo lze Fi odvodit z predchozích Fj (j < i) použitím urcitých odvozovacích pravidel
Hana Rudová, Logické programování I, 22. brezna 2011
9
Predikátová logika
Zkoumání pravdivosti formulí
Zjištení pravdivosti provádíme dukazem
Důkaz: libovolná posloupnost Fi,..., Fn formulí jazyka L, v níž každé Fi je bud' axiom teorie jazyka L nebo lze Fi odvodit z predchozích Fj (j < i) použitím urcitých odvozovacích pravidel
JS> Odvozovací pravidla - príklady
A pravidlo modus ponens: z formulí F a F => G lze odvodit G
Hana Rudová, Logické programování I, 22. brezna 2011
9
Predikátová logika
Zkoumání pravdivosti formulí
Zjištení pravdivosti provádíme dukazem
Důkaz: libovolná posloupnost F1,..., Fn formulí jazyka L, v níž každé Fi je bud' axiom teorie jazyka L nebo lze Fi odvodit z předchozích Fj (j < i) použitím urcitých odvozovacích pravidel
JS> Odvozovací pravidla - príklady
A pravidlo modus ponens: z formulí F a F => G lze odvodit G i* rezolucní princip: z formulí F v A, G v -A odvodit F v G
Hana Rudová, Logické programování I, 22. brezna 2011
9
Predikátová logika
Zkoumání pravdivosti formulí
Zjištení pravdivosti provádíme dukazem
Důkaz: libovolná posloupnost F1,..., Fn formulí jazyka L, v níž každé Fi je bud' axiom teorie jazyka L nebo lze Fi odvodit z predchozích Fj (j < i) použitím urcitých odvozovacích pravidel
JS> Odvozovací pravidla - príklady
A pravidlo modus ponens: z formulí F a F == G lze odvodit G i* rezolucní princip: z formulí F v A, G v -A odvodit F v G
& F je dokazatelná z formulí A1f • • • ,An A1t • • • ,An h F
existuje-li důkaz F z A1, • • • ,An
Hana Rudová, Logické programování I, 22. brezna 2011
9
Predikátová logika
Zkoumání pravdivosti formulí
Zjištení pravdivosti provádíme dukazem
Důkaz: libovolná posloupnost      .., Fn formulí jazyka L, v níž každé Fi je bud' axiom teorie jazyka L nebo lze Fi odvodit z predchozích Fj (j < i) použitím urcitých odvozovacíčh pravidel
JS> Odvozovací pravidla - príklady
A pravidlo modus ponens: z formulí F a F => G lze odvodit G i* rezoluční princip: z formulí F v A, G v -A odvodit F v G
& F je dokazatelná z formulí A1, • • • ,An A1, • • • ,An h F
existuje-li důkaz F z A1, • • • ,An
& Dokazatelné formule v teorii T nazýváme teorémy teorie T
Hana Rudová, Logické programování I, 22. brezna 2011
9
Predikátová logika
Korektnost a úplnost
Uzavrená formule: neobsahůje volnoů promennoů (bez kvantifikaCe)
VY ((0 < Y) a ( 3X (X < Y))) je ůzavrená formůle iľ ( 3X (X < Y)) není ůzavrená formůle
Hana Růdová, LogiCké programování I, 22. b rezna 2011
10
Predikátová logika
Korektnost a úplnost
Uzavrená formule: neobsahůje volnoů promennoů (bez kvantifikaCe)
VY ((0 < Y) a ( 3X (X < Y))) je ůzavrená formůle iľ ( 3X (X < Y)) není ůzavrená formůle
M Množina odvozovadCh pravidel se nazývá korektní, jestliže pro každoů množinů ůzavrenýCh formůlí P a každoů ůzavrenoů formůli F platí:
jestliže P h F pak P N F       (jestliže je neCo dokazatelné, pak to platí)
Hana Růdová, LogiCké programování I, 22. brezna 2011
10
Predikátová logika
Korektnost a úplnost
Uzavřená formule: neobsahuje volnou promennou (bez kvantifikace)
VY ((0 < Y) a ( 3X (X < Y))) je uzavrená formule iľ ( 3X (X < Y)) není uzavrená formule
M Množina odvozovacích pravidel se nazývá korektní, jestliže pro každou množinu uzavrených formulí P a každou uzavrenou formuli F platí:
jestliže P h F pak P N F       (jestliže je neco dokazatelné, pak to platí)
Odvozovací pravidla jsou úplná, jestliže
jestliže P N F pak P h F       (jestliže neco platí, pak je to dokazatelné)
Hana Rudová, Logické programování I, 22. brezna 2011
10
Predikátová logika
Korektnost a úplnost
Uzavřená formule: neobsahuje volnou promennou (bez kvantifikace)
VY ((0 < Y) a ( 3X (X < Y))) je uzavrená formule iľ ( 3X (X < Y)) není uzavrená formule
M Množina odvozovacích pravidel se nazývá korektní, jestliže pro každou množinu uzavrených formulí P a každou uzavrenou formuli F platí:
jestliže P h F pak P N F       (jestliže je neco dokazatelné, pak to platí)
Odvozovací pravidla jsou úplná, jestliže
jestliže P N F pak P h F       (jestliže neco platí, pak je to dokazatelné)
-í* PL1: úplná a korektní dokazatelnost, tj.
pro teorii T s množinou axiomu A platí:   T i= F práve když Ah F
Hana Rudová, Logické programování I, 22. brezna 2011
10
Predikátová logika