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

[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:

  • formule x + y = z je otevřená ale ne uzavřená
  • formule (\forall x) (\exists y) (x+y=xy) je uzavřená ale ne otevřená
  • formule (\forall x) (x<y) není ani otevřená ani uzavřená
  • formule 0 + 0 = 0 je otevřená i uzavřená

[editovat] Podívejte se také na

Související články obsahuje:
 Portál Matematika 
V jiných jazycích