Formule (logika)

konečná posloupnost symbolů reprezentující nějaké matematické tvrzení
(přesměrováno z Atomická formule)

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.

Definice editovat

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.

Term editovat

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

Zde je vhodné poznamenat, jaký význam má ve formuli term. Term je obecně nějaký prvek domény.[pozn. 1] Proto jsou proměnné termy a rovněž funkční symboly jsou termy (funkční symbol reprezentuje relaci zobrazení z domény do domény). Term je ve formuli „vstupem“ predikátového symbolu (v syntaktickém stromu formule se term nacházi pod predikátovým symbolem).

Atomická formule editovat

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.

Formule editovat

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á formule editovat

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á, substituovatelnost editovat

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

Poznámky editovat

  1. „nosič“/doména dané realizace (interpretace) jazyka, universum diskurzu

Související články editovat

Externí odkazy editovat

  •   Slovníkové heslo formule ve Wikislovníku