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

m
Řádek 1: Řádek 1:
== Predikátová logika nebo-li predikátová logika prvního řádu ==
+
===Predikátová logika nebo-li predikátová logika prvního řádu===
 
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. 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>
  
Predikátová logika je složena ze dvou klíčových částí'''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.
+
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.
  
== Syntax výrokové logiky ==
+
===Syntax výrokové logiky===
á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é.
+
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í.
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í.
 
  
Abeceda je složena z:
 
  
1. logických symbolů
+
'''Abeceda je složena z:'''
a) početné množiny individuálních proměnných: x,y,...,x1,x2,...  
+
 
b) výrokových logických spojek: ¬,∧,∨,⇒,⇔
+
<u>1. logických symbolů</u>
 +
 
 +
a) početné množiny individuálních proměnných: x,y,...,x1,x2,...
 +
 
 +
b) výrokových logických spojek: ¬,∧,∨,⇒,⇔  
 +
 
 
c) obecného kvantifikátoru (každý)  ∀ a existenčního kvantifikátoru (některý) ∃  
 
c) obecného kvantifikátoru (každý)  ∀ a existenčního kvantifikátoru (některý) ∃  
  
2. speciálních symbolů, tj.:
+
<u>2. speciálních symbolů</u>
a) množiny P predikátových symbolů (nesmí být prázdná) b) množiny K konstantních symbolů (může být prázdná)
+
 
 +
a) množiny P predikátových symbolů (nesmí být prázdná)
 +
 
 +
b) množiny K konstantních symbolů (může být prázdná)
 +
 
 
c) množiny F funkčních symbolů (může být prázdná)
 
c) množiny F funkčních symbolů (může být prázdná)
  
3. pomocných symbolů, jako jsou závorky „(, [ ,) ,]􏰀 a čárka ,􏰀.
+
<u>3. pomocných symbolů</u> jako jsou závorky „(, [ ,) ,]􏰀" a čárka ","
 +
 
 +
 
 +
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.
 +
 
 +
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.
  
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éž
+
<br />
'''arita''' predikátového symbolu (stručně predikát)nebo funkčního symbolu.
 
  
Predikáty arity 1 jsou zvány monadické predikáty,
+
===='''FORMULE''' 1, je-li výraz A formule, pak (¬)A je formule. ====
predikáty arity 2 jsou binární predikáty
+
2, jsou-li výrazy A a B formule, pak výrazy  (A ∧ B), (A ∨ B), (A ⇒ B), (A ⇔ B) jsou formule.<br>
predikáty arity n jsou n-ární (polyadické) predikáty.
 
  
==FORMULE==
+
3, je-li x proměnná a  A formule,  pak výrazy ∀xA a ∃xA jsou formule
  
  
1, je-li výraz A formule, pak (negace)A je formule.<br>
+
4, nic jiného není formule
  
2, jsou-li výrazy A a B formule, pak výrazy<br>
+
<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.
  
3, (A  B), (A  B), (A  B), (A  B) jsou formule.<br>
+
Každá atomická formule je formule.
  
4, je-li x proměnná a A formule, pak výrazy x A a x A jsou formule<br>
+
===='''TERMY'''====
  
 +
Základní stavební prvky formulí. Intuitivně představují objekty, individua.
  
'''Atomické formule'''
+
# každý symbol proměnné x, y, ... je term.
je-li P n-ární predikátový symbol a jsou-li t1,...,tn termy, pak výraz P(t1,...,tn) je atomická formule. Každá atomická formule je formule.
+
# 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
  
==TERMY==
 
  
Intuitivně představují objekty, individua.
 
  
Množina termů je definována těmito pravidly:  
+
'''Příklady převedení z přirozeného jazyka:'''
i. Každá individuová proměnná je term.
 
ii. Každá individuová konstanta je term.
 
iii. Nic jiného není term.
 
  
Příklad převodu přirozeného jazyka do predikátové logiky:
+
# Někdo má hudební sluch (S) a někdo nemá hudební sluch. (∃x S(x)) ∧ (∃x ¬S(x))
 +
# Některé děti (D) nerady čokoládu (C).  ∃x (D(x) ∧ ¬C(x))
  
„všichni“, „žádný“, „nikdo“, ... 
+
<br /><references />
„někdo“, „něco“, „někteří“, „existuje“, ... 
 
Větu musíme často ekvivalentně přeformulovat
 
Pozor: v češtině dvojí zápor !
 
Žádný student není důchodce: x [S(x)  D(x)]
 
Ale, „všichni studenti nejsou důchodci“ čteme jako „ne všichni studenti jsou důchodci“:
 
x [S(x)  D(x)]  x [S(x)  D(x)]
 

Verze z 24. 4. 2020, 21:46

Predikátová logika nebo-li predikátová logika prvního řádu

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.[1]

Predikátová logika je složena ze dvou klíčových částí 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.

Syntax výrokové logiky

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í.


Abeceda je složena z:

1. logických symbolů

a) početné množiny individuálních proměnných: x,y,...,x1,x2,...

b) výrokových logických spojek: ¬,∧,∨,⇒,⇔

c) obecného kvantifikátoru (každý) ∀ a existenčního kvantifikátoru (některý) ∃

2. speciálních symbolů

a) množiny P predikátových symbolů (nesmí být prázdná)

b) množiny K konstantních symbolů (může být prázdná)

c) množiny F funkčních symbolů (může být prázdná)

3. pomocných symbolů jako jsou závorky „(, [ ,) ,]􏰀" a čárka ","


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.

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.


FORMULE 1, je-li výraz A formule, pak (¬)A je formule.

2, jsou-li výrazy A a B formule, pak výrazy (A ∧ B), (A ∨ B), (A ⇒ B), (A ⇔ B) jsou formule.

3, je-li x proměnná a A formule, pak výrazy ∀xA a ∃xA jsou formule


4, nic jiného není formule


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.

Každá atomická formule je formule.

TERMY

Základní stavební prvky formulí. Intuitivně představují objekty, individua.

  1. každý symbol proměnné x, y, ... je term.
  2. 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, ...).
  3. jen výrazy dle 1. a 2. jsou termy


Příklady převedení z přirozeného jazyka:

  1. Někdo má hudební sluch (S) a někdo nemá hudební sluch. (∃x S(x)) ∧ (∃x ¬S(x))
  2. Některé děti (D) nerady čokoládu (C). ∃x (D(x) ∧ ¬C(x))