Definice syntaxe a sémantiky Predikátové logiky: Porovnání verzí

m
 
(Není zobrazeno 15 mezilehlých verzí od stejného uživatele.)
Řádek 1: Řádek 1:
−
===Predikátová logika nebo-li predikátová logika prvního řádu===
+
==Predikátová logika==
−
Výroková logika se zabývala pravdivostí jednoduchých tvrzení, která byla spojena logickými operátory (spojkami). Predikátová logika toto trochu rozšiřuje, neboť zkoumá vlastnosti a vztahy prvků daných množin. Pomůže lepšímu a přesnějšímu vyjádření vztahu. Jinými slovy si všímá  i struktury vět samotných.<ref>[http://lucie.zolta.cz/index.php/zaklady-teoreticke-informatiky/19-rezolucni-metoda-a-logicke-programovani/136-predikatova-logika] </ref>
+
Výroková logika se zabývala pravdivostí jednoduchých tvrzení, která byla spojena logickými operátory (spojkami). [[Predikátová logika]] toto trochu rozšiřuje, neboť zkoumá vlastnosti a vztahy prvků daných množin. Jinými slovy si všímá  i struktury vět samotných a obsahuje '''predikáty''' a '''kvantifikátory'''. Rozlišuje individua, o kterých se něco predikuje (tvrdí) a predikát je chápán jako vlastnost nebo vztah.
 +
<ref>Žoltá, L. Predikátová logika 1. řádu ([http://lucie.zolta.cz/index.php/zaklady-teoreticke-informatiky/19-rezolucni-metoda-a-logicke-programovani/136-predikatova-logika] </ref>
  
−
Predikátová logika je složena ze dvou klíčových částí '''[[Syntaxe|syntax]]''' a '''[[sémantika]]'''. Syntax určuje, jaké kolekce (posloupnosti) symbolů jsou legální výrazy predikátové logiky a sémantika hovoří o významu za těmito výrazy.
+
===<u>Syntax predikátové logiky</u>===
 +
Syntax neboli jazyk predikátové logiky se skládá z proměnných, konstant, relačních a funkčních symbolů, predikátů, kvantifikátorů, termů, atomických formulí a predikátových formulí.
  
−
===Syntax výrokové logiky===
+
===='''1.Proměnné'''====
−
Základem každého jazyka je množina symbolů, kterými tento jazyk disponuje, neboli jeho abeceda.Stejně jako ve výrokové logice musí jazyk predikátové logiky obsahovat symboly označující proměnné. Syntax nebo-li jazyk predikátové logiky se skládá z predikátů, proměnných, konstant, relačních a funkčních symbolů, , kvantifikátorů, termů, atomických formulí a predikátových formulí.
+
====Proměnných je neomezeně mnoho. Označují se malými písmenky x,y,z,x<sub>1</sub>,y<sub>1</sub>....Jedná se o klasické chápání proměnných z nižší matematiky.====
 +
===='''2.Symboly pro relace-''' funkční a predikátové====
 +
Každý symbol pro relace má přiřazenu aritu (četnost, čili počet operandů). Hodnota arity představuje počet operandů (tj. kolika operandů se funkční operace, vlastnost nebo vztah týká). Operátory s jedním operandem nazýváme unární, operátory se dvěma operandy binární, se třemi ternární atd.
  
  
−
'''Abeceda je složena z:'''
+
Symboly pro relace lze rozdělit na:
  
−
<u>1. logických symbolů</u>  
+
<u>funkční (operace)</u>  
  
−
a) početné množiny individuálních proměnných: x,y,...,x1,x2,...
+
Vyjadřují operace s objekty daného oboru. Operace mohou být sčítání, násobení aj. Funkční operace mají svojí "aritu", která je nezáporná. Hodnota arity představuje počet operandů (tj. kolika operandů se funkční operace týká). Operátory s jedním operandem nazýváme unární, operátory se dvěma operandy binární, se třemi ternární atd.
  
−
b) výrokových logických spojek: ¬,∧,∨,⇒,⇔
+
<u>predikátové (vztahy a vlastnosti)</u>
  
−
c) obecného kvantifikátoru (každý)  ∀ a existenčního kvantifikátoru (některý) ∃
+
Predikáty se označují predikátovými symboly a vypovídají o vlastnostech a vztazích mezi předměty určeného universa.Stejně jako funkční symboly, mají svoji aritu. Arita predikátových symbolů je vždy menší nebo rovna jedné. Unární predikáty popisují vlastnost, predikáty vyšší arity pak popisují vztahy (ve vztahu je vždy zapotřebí minimálně 2).
  
−
<u>2. speciálních symbolů</u>
 
  
−
a) množiny P predikátových symbolů (nesmí být prázdná)
+
Příklady predikátů:
  
−
b) množiny K konstantních symbolů (může být prázdná)
+
vlastnost "být kladným číslem"
  
−
c) množiny F funkčních symbolů (může být prázdná)
+
vztah "být větší než"
  
−
<u>3. pomocných symbolů</u> jako jsou závorky „(, [ ,) ,]􏰀" a čárka ","
+
===='''3. Termy'''====
 +
Je výraz jazyka prvního řádu, který má svůj význam- popisuje individua. Jedná se o proměnné, konstanty a výsledky funkcí (operací).
  
 +
Termy v predikátové logice definujeme:
  
−
Pro každý symbol máme dáno přirozené číslo "n" větší nebo rovno 1. Toto číslo nám udává, kolika objektů se daný predikát týká, pro kolik proměnných je funkční symbol dán. Tomuto číslu říkáme četnost nebo též '''arita predikátového symbolu''' (stručně predikát)nebo funkčního symbolu.
+
*Každá proměnná je term
 +
*Každá konstanta je term
 +
*Je-li F funkční symbol četnosti n a jsou-li t<sub>1...</sub> t<sub>n</sub> termy, pak také F(t<sub>1...</sub> t<sub>n</sub>) je term
 +
*Každý term vznikne konečný počtem aplikací předchozích pravidel (tedy nic jiného není term)[https://is.mendelu.cz/eknihovna/opory/zobraz_cast.pl?cast=9920]
  
−
Predikáty arity 1 jsou zvány monadické predikáty, predikáty arity 2 jsou binární predikátypredikáty arity n jsou n-ární (polyadické) predikáty.
+
===='''4. Atomické formule'''====
 +
Atomická formule je predikátový symbol P aplikovaný na tolik termů, kolik je jeho arita. Jinými slovy, je-li arita predikátového symbolu
  
−
<br />
+
P číslo n a t1, t2,...,tn je n-tice termů, pakP(t1,t2,...,tn) je atomická formule.<ref>Demlová, M. Diskrétní matematika a logika (2005)[http://math.feld.cvut.cz/demlova/teaching/dml/pred03.pdf]</ref>
  
−
===='''FORMULE''' 1, je-li výraz A formule, pak (¬)A je formule. ====
+
===='''5. Formule'''====
−
2, jsou-li výrazy A a B formule, pak výrazy  (A ∧ B), (A ∨ B), (A ⇒ B), (A ⇔ B) jsou formule.<br>
+
Jsou tvrzení o individuích a jsou definovány induktivně těmito pravidly:
  
−
3, je-li x proměnná a A formule, pak výrazy ∀xA a ∃xA jsou formule
+
*Každá atomická formule je formule
 +
*Jsou-li P a Q formule, pak také (¬P),(P∧Q),(P∨Q),(P⇒Q),(P⇔Q) jsou opět formule.
 +
*Je-li x proměnná a P formule, pak ( ∃x)P a (∀x)P jsou formule
 +
*Konečná posloupnost symbolů jazyka predikátové logiky je formule. Nic, co nevzniklo pomocí konečně mnoha použití bodů 1 až 3, není formule.
  
 +
Díky induktivnímu definování,  lze tvořit libovolně složité formule tak, že opakovaně aplikujeme uvedená pravidla.
  
−
4, nic jiného není formule
+
Formule může být '''otevřená''' a '''uzavřená'''. Pokud je formule otevřená, tak neobsahuje žádný kvantifikátor. Uzavřená je v případě, je-li každá proměnná, která v ní je obsazená kvantifikována (je na ní aplikován kvantifikátor  ∃ nebo ∀).  Uzavřená formule se také označuje jako sentence, výrok.
  
−
<br>'''Atomické formule''' je-li P n-ární predikátový symbol a jsou-li t1,...,tn termy, pak výraz P(t1,...,tn) je atomická formule.
+
Například:
  
−
Každá atomická formule je formule.
+
*formule  x+y= z je otevřená ale ne uzavřená
 +
*formule (∀x) ( ∃y) (x+y=xy) je uzavřená ale ne otevřená
 +
*formule (∀x) (x<y) není ani otevřená ani uzavřená
 +
*formule  0+0= 0 je otevřená i uzavřená<ref>Formule[https://cs.wikipedia.org/wiki/Formule_(logika)#Atomick%C3%A1_formule]</ref>
  
−
===='''TERMY'''====
+
===<u>Sémantika predikátové logiky</u>===
  
−
Základní stavební prvky formulí. Intuitivně představují objekty, individua.
+
Sémantika neboli význam formulí a jejich pravdivost je dána interpretací. Pokud například chceme vědět, jestli je daná formule pravdivá nebo ne, musíme vědět co formule znamená/jak je interpretována.  
  
−
# každý symbol proměnné x, y, ... je term.
+
Interpretace formule spočívá v ustanovení "o čem mluvíme". Důležité je tedy stanovení '''universa''' (tedy o jaké předmětné oblasti mluvíme) s jeho prvky- '''individui'''.  
−
# jsou-li t1,...,tn (n  0) termy a je-li f n-ární funkční symbol, pak výraz '''f(t1,...,tn)''' je  term; pro n = 0 se jedná o individuovou konstantu (značíme a, b, c, ...).
 
−
# jen výrazy dle 1. a 2. jsou termy
 
  
 +
Interpretační pravidla jsou v predikátové logice poněkud složitější; zatímco ve výrokové logice je potřeba interpretovat jen logické spojky a výrokové proměnné, v predikátové logice musíme interpretovat - specifikovat význam pro:
  
 +
*logické spojky     ¬,⇒, ⇔,∧,∨
 +
*individuální proměnné x, y... (Individuálním proměnným je přiřazena neprázdná množina "n" individuí jako jejich definiční obor hodnot. Všechny individuální proměnné mají tutéž interpretaci.)
 +
*predikátové proměnné - symboly P  <sup>1</sup>(x), Q  <sup>2</sup>(x, y)... (Predikátové proměnné jsou interpretovány tak, že je jim přiřazena, jako obor hodnot, jistá neprázdná třída logických funkcí)
 +
*kvantifikátory  ∀ ,   ∃
  
−
'''Příklady převedení z přirozeného jazyka:'''
 
  
−
# Někdo má hudební sluch (S) a někdo nemá hudební sluch. (∃x S(x)) ∧ (∃x ¬S(x))
+
<u>Interpretační pravidla</u> sémantických interpretačních pravidel, které dávají návod, jak správně interpretovat a vypočíst hodnotu.
−
# Některé děti (D) nerady čokoládu (C).  ∃x (D(x) ∧ ¬C(x))
 
  
−
<br /><references />
+
#Individuálním proměnným je přiřazena neprázdná množina "n" individuí jako jejich definiční obor hodnot. Všechny individuální proměnné mají tutéž interpretaci.
 +
#Individuální proměnná x má hodnotu, kterou po jejím udělení,  zapíšeme ve tvaru a  →v
 +
#Jestliže A má hodnotu 1, pak ¬A má hodnotu 0 a obráceně. Dále platí následující interpretace zbývajících logických spojek:
 +
 
 +
{| class="wikitable"
 +
|+
 +
|''A''
 +
|''B''
 +
|''A∧B''
 +
|''A∨B''
 +
|''A⇒B''
 +
|''A⇔B''
 +
|-
 +
|0
 +
|0
 +
|0
 +
|0
 +
|1
 +
|1
 +
|-
 +
|1
 +
|0
 +
|0
 +
|1
 +
|0
 +
|0
 +
|-
 +
|0
 +
|1
 +
|0
 +
|1
 +
|1
 +
|0
 +
|-
 +
|1
 +
|1
 +
|1
 +
|1
 +
|1
 +
|1
 +
|}
 +
4.  Jestliže výraz A neobsahuje žádný volný výskyt proměnné, potom výrazy (∀ ) A , ( ) A mají pro dané udělení hodnot tutéž hodnotu, kterou má pro toto udělení výraz A sám.
 +
 
 +
5. Nechť x  je individuální proměnná a A libovolný výraz. Kvantifikátor ( ∀x ) A má pro dané udělení hodnot volným proměnným výrazu A hodnotu pravda, právě když (pro toto udělení hodnot) má výraz A hodnotu pravda pro všechny hodnoty proměnné x .
 +
 
 +
6. Nechť x je individuální proměnná a A libovolný výraz. Kvantifikátor (∃x) A má pro dané udělení hodnot volným proměnným výrazu A hodnotu pravda, právě když (pro toto udělení hodnot) má výraz A hodnotu pravda aspoň pro některou hodnotu proměnné x.
 +
 
 +
7. Jestliže výraz A neobsahuje žádný volný výskyt proměnné x , potom výrazy (∀x) A , (∃x) A mají pro dané udělení hodnot tutéž hodnotu, kterou má pro toto udělení výraz A sám.<ref>Predikátová logika [https://is.mendelu.cz/eknihovna/opory/zobraz_cast.pl?cast=681]</ref><blockquote><br />'''Reference'''</blockquote><references /><blockquote>'''Doporučená literatura'''</blockquote>
 +
 
 +
*Drobíková, B., Římanová, R., Souček, J., & Souček, M. (2018). ''Teoretická východiska informační vědy: využití konceptuálního modelování v informační vědě''. Univerzita Karlova, nakladatelství Karolinum.
 +
*Raclavský, J. (2015). ''Úvod do logiky: klasická predikátová logika''. Masarykova univerzita.
 +
*Kolman, V., & Punčochář, V. (2015). ''Formy jazyka: úvod do logiky a její filosofie''. Filosofia.
 +
 
 +
<blockquote>'''Související články''' </blockquote>
 +
[[Logika]]<br>
 +
[[Popište, co je to sémantika výrokové logiky]]<br>
 +
[[Popište, co je to syntaxe výrokové logiky]]
 +
 
 +
<blockquote>'''Klíčová slova''' </blockquote>
 +
Predikátová logika, Relace, Syntax, Sémantika, Kvantifikátory, Formule

Aktuální verze z 20. 5. 2020, 19:40

Predikátová logika

Výroková logika se zabývala pravdivostí jednoduchých tvrzení, která byla spojena logickými operátory (spojkami). Predikátová logika toto trochu rozšiřuje, neboť zkoumá vlastnosti a vztahy prvků daných množin. Jinými slovy si všímá i struktury vět samotných a obsahuje predikáty a kvantifikátory. Rozlišuje individua, o kterých se něco predikuje (tvrdí) a predikát je chápán jako vlastnost nebo vztah. 

[1]

Syntax predikátové logiky

Syntax neboli jazyk predikátové logiky se skládá z proměnných, konstant, relačních a funkčních symbolů, predikátů, kvantifikátorů, termů, atomických formulí a predikátových formulí.

1.Proměnné

Proměnných je neomezeně mnoho. Označují se malými písmenky x,y,z,x1,y1....Jedná se o klasické chápání proměnných z nižší matematiky.

2.Symboly pro relace- funkční a predikátové

Každý symbol pro relace má přiřazenu aritu (četnost, čili počet operandů). Hodnota arity představuje počet operandů (tj. kolika operandů se funkční operace, vlastnost nebo vztah týká). Operátory s jedním operandem nazýváme unární, operátory se dvěma operandy binární, se třemi ternární atd.


Symboly pro relace lze rozdělit na:

funkční (operace)

Vyjadřují operace s objekty daného oboru. Operace mohou být sčítání, násobení aj. Funkční operace mají svojí "aritu", která je nezáporná. Hodnota arity představuje počet operandů (tj. kolika operandů se funkční operace týká). Operátory s jedním operandem nazýváme unární, operátory se dvěma operandy binární, se třemi ternární atd.

predikátové (vztahy a vlastnosti)

Predikáty se označují predikátovými symboly a vypovídají o vlastnostech a vztazích mezi předměty určeného universa.Stejně jako funkční symboly, mají svoji aritu. Arita predikátových symbolů je vždy menší nebo rovna jedné. Unární predikáty popisují vlastnost, predikáty vyšší arity pak popisují vztahy (ve vztahu je vždy zapotřebí minimálně 2).


Příklady predikátů:

vlastnost "být kladným číslem"

vztah "být větší než"

3. Termy

Je výraz jazyka prvního řádu, který má svůj význam- popisuje individua. Jedná se o proměnné, konstanty a výsledky funkcí (operací).

Termy v predikátové logice definujeme:

  • Každá proměnná je term
  • Každá konstanta je term
  • Je-li F funkční symbol četnosti n a jsou-li t1... tn termy, pak také F(t1... tn) je term
  • Každý term vznikne konečný počtem aplikací předchozích pravidel (tedy nic jiného není term)[5]

4. Atomické formule

Atomická formule je predikátový symbol P aplikovaný na tolik termů, kolik je jeho arita. Jinými slovy, je-li arita predikátového symbolu

P číslo n a t1, t2,...,tn je n-tice termů, pakP(t1,t2,...,tn) je atomická formule.[2]

5. Formule

Jsou tvrzení o individuích a jsou definovány induktivně těmito pravidly:

  • Každá atomická formule je formule
  • Jsou-li P a Q formule, pak také (¬P),(P∧Q),(P∨Q),(P⇒Q),(P⇔Q) jsou opět formule.
  • Je-li x proměnná a P formule, pak ( ∃x)P a (∀x)P jsou formule
  • Konečná posloupnost symbolů jazyka predikátové logiky je formule. Nic, co nevzniklo pomocí konečně mnoha použití bodů 1 až 3, není formule.

Díky induktivnímu definování, lze tvořit libovolně složité formule tak, že opakovaně aplikujeme uvedená pravidla.

Formule může být otevřená a uzavřená. Pokud je formule otevřená, tak neobsahuje žádný kvantifikátor. Uzavřená je v případě, je-li každá proměnná, která v ní je obsazená kvantifikována (je na ní aplikován kvantifikátor ∃ nebo ∀). Uzavřená formule se také označuje jako sentence, výrok.

Například:

  • formule  x+y= z je otevřená ale ne uzavřená
  • formule (∀x) ( ∃y) (x+y=xy) je uzavřená ale ne otevřená
  • formule (∀x) (x<y) není ani otevřená ani uzavřená
  • formule  0+0= 0 je otevřená i uzavřená[3]

Sémantika predikátové logiky

Sémantika neboli význam formulí a jejich pravdivost je dána interpretací. Pokud například chceme vědět, jestli je daná formule pravdivá nebo ne, musíme vědět co formule znamená/jak je interpretována.

Interpretace formule spočívá v ustanovení "o čem mluvíme". Důležité je tedy stanovení universa (tedy o jaké předmětné oblasti mluvíme) s jeho prvky- individui.

Interpretační pravidla jsou v predikátové logice poněkud složitější; zatímco ve výrokové logice je potřeba interpretovat jen logické spojky a výrokové proměnné, v predikátové logice musíme interpretovat - specifikovat význam pro:

  • logické spojky     ¬,⇒, ⇔,∧,∨
  • individuální proměnné x, y... (Individuálním proměnným je přiřazena neprázdná množina "n" individuí jako jejich definiční obor hodnot. Všechny individuální proměnné mají tutéž interpretaci.)
  • predikátové proměnné - symboly P  1(x), Q  2(x, y)... (Predikátové proměnné jsou interpretovány tak, že je jim přiřazena, jako obor hodnot, jistá neprázdná třída logických funkcí)
  • kvantifikátory  ∀ ,   ∃


Interpretační pravidla sémantických interpretačních pravidel, které dávají návod, jak správně interpretovat a vypočíst hodnotu.

  1. Individuálním proměnným je přiřazena neprázdná množina "n" individuí jako jejich definiční obor hodnot. Všechny individuální proměnné mají tutéž interpretaci.
  2. Individuální proměnná x má hodnotu, kterou po jejím udělení, zapíšeme ve tvaru a  →v
  3. Jestliže A má hodnotu 1, pak ¬A má hodnotu 0 a obráceně. Dále platí následující interpretace zbývajících logických spojek:
A B A∧B A∨B A⇒B A⇔B
0 0 0 0 1 1
1 0 0 1 0 0
0 1 0 1 1 0
1 1 1 1 1 1

4. Jestliže výraz A neobsahuje žádný volný výskyt proměnné, potom výrazy (∀ ) A , ( ) A mají pro dané udělení hodnot tutéž hodnotu, kterou má pro toto udělení výraz A sám.

5. Nechť x  je individuální proměnná a A libovolný výraz. Kvantifikátor ( ∀x ) A má pro dané udělení hodnot volným proměnným výrazu A hodnotu pravda, právě když (pro toto udělení hodnot) má výraz A hodnotu pravda pro všechny hodnoty proměnné x .

6. Nechť x je individuální proměnná a A libovolný výraz. Kvantifikátor (∃x) A má pro dané udělení hodnot volným proměnným výrazu A hodnotu pravda, právě když (pro toto udělení hodnot) má výraz A hodnotu pravda aspoň pro některou hodnotu proměnné x.

7. Jestliže výraz A neobsahuje žádný volný výskyt proměnné x , potom výrazy (∀x) A , (∃x) A mají pro dané udělení hodnot tutéž hodnotu, kterou má pro toto udělení výraz A sám.[4]


Reference

  1. ↑ Žoltá, L. Predikátová logika 1. řádu ([1]
  2. ↑ Demlová, M. Diskrétní matematika a logika (2005)[2]
  3. ↑ Formule[3]
  4. ↑ Predikátová logika [4]

Doporučená literatura

  • Drobíková, B., Římanová, R., Souček, J., & Souček, M. (2018). Teoretická východiska informační vědy: využití konceptuálního modelování v informační vědě. Univerzita Karlova, nakladatelství Karolinum.
  • Raclavský, J. (2015). Úvod do logiky: klasická predikátová logika. Masarykova univerzita.
  • Kolman, V., & Punčochář, V. (2015). Formy jazyka: úvod do logiky a její filosofie. Filosofia.

Související články

Logika
Popište, co je to sémantika výrokové logiky
Popište, co je to syntaxe výrokové logiky

Klíčová slova

Predikátová logika, Relace, Syntax, Sémantika, Kvantifikátory, Formule

Citováno z „https://wikisofia.cz/w/index.php?title=Definice_syntaxe_a_sémantiky_Predikátové_logiky&oldid=60265“