Formule (logika)

konečná posloupnost symbolů reprezentující nějaké matematické tvrzení

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.

DefiniceEditovat

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

TermEditovat

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   jsou termy, pak   je term.
  • Nic, co nevzniklo pomocí předchozích pravidel, není term, neboli každý term vznikne konečným použitím tří výše uvedených pravidel

Atomická formuleEditovat

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

FormuleEditovat

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ž   je formule, x proměnná, pak   a   jsou formule.
  • Když   jsou formule, pak   je formule.

Uzavřená a otevřená formuleEditovat

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   je otevřená ale ne uzavřená
  • formule   je uzavřená ale ne otevřená
  • formule   není ani otevřená ani uzavřená
  • formule   je otevřená i uzavřená

Volná a vázaná proměnná, substituovatelnostEditovat

Podformulí formule   je každá formule, která je částí formule  .

Říkáme, že proměnná x je vázaná ve formuli  , jestliže existuje podformule formule   ve tvaru  . Říkáme, že proměnná x je volná ve formuli  , jestliže x má výskyt v nějaké podformuli   formule   takové, že   není podformulí žádné formule tvaru  .

Říkáme, že term t je substituovatelný za proměnnou x do formule  , jestliže x není volná v žádné podformuli tvaru  , kde proměnná y má výskyt v termu t. Tedy, pokud náš term t obsahuje proměnnou y, která je v místě substituce vázaná, musí tam být i x vázaná.

Je-li x proměnná, t term a   formule,   značí formuli, která vznikne nahrazením (substitucí) termu t za každý volný výskyt proměnné x v  .

Otevřené formule nemají vázané proměnné, uzavřené formule nemají volné proměnné.

Související článkyEditovat

Externí odkazyEditovat

  •   Slovníkové heslo formule ve Wikislovníku