Formule (logika)

Z Wikipedie, otevřené encyklopedie

Formule (také predikátová formule, srov. výroková formule) je v matematice a logice syntaktický pojem reprezentující nějaké (matematické) tvrzení v jisté formální teorii predikátové logiky prvního řádu.

Obsah

1 Definice
2 Podívejte se také na

[editovat] Definice

Nechť L je jazyk. V následující definici uvažujeme pouze dvě logické spojky $\neg$ a $\rightarrow$ a jeden kvantifikátor $\forall$ . Zbylé spojky a kvantifikátor lze zavést definicemi.

[editovat] Term

Termy jazyka L jsou definovány indukcí podle složitosti takto: Množina termů je nejmenší množina splňující:

Každá proměnná je term.
Každý konstantní symbol c jazyka L je term.
Kdykoli F je n-ární funkční symbol jazyka L a $t_1, \ldots, t_n$ jsou termy, pak $F(t_1, \ldots, t_n)$ je term.

[editovat] Atomická formule

Atomická formule jazyka L je výraz tvaru $P(t_1, \ldots, t_n)$ , kde P je n-ární predikátový symbol jazyka L a $t_1, \ldots, t_n$ jsou termy nebo (jde-li o logiku s rovností) tvaru $\,t_1=t_2$ , kde $\,t_1,t_2$ jsou termy.

[editovat] Formule

Formule jazyka L jsou definovány indukcí podle složitosti takto: Množina formulí je nejmenší množina splňující:

Každá atomická formule je formule
Když $\varphi$ je formule, x proměnná, pak $\neg \varphi$ a $(\forall x)(\varphi)$ jsou formule.
Když $\varphi, \psi$ jsou formule, pak $\varphi \rightarrow \psi$ je formule.

[editovat] Uzavřená a otevřená formule

Formule se nazývá otevřená, neobsahuje-li žádný kvantifikátor, a uzavřená, je-li každá proměnná v ní obsažená kvantifikována (tj. je na ni aplikován některý kvantifikátor). Uzavřená formule se nazývá též sentence.

Například: