Formule (logika)

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

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

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 ${\displaystyle t_{1},\ldots ,t_{n}}$ jsou termy, pak ${\displaystyle F(t_{1},\ldots ,t_{n})}$ 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

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

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ž ${\displaystyle \varphi }$ je formule, x proměnná, pak ${\displaystyle \neg \varphi }$ a ${\displaystyle (\forall x)(\varphi )}$ jsou formule.
• Když ${\displaystyle \varphi ,\psi }$ jsou formule, pak ${\displaystyle \varphi \Rightarrow \psi }$ je formule.

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 ${\displaystyle x+y=z}$ je otevřená ale ne uzavřená
• formule ${\displaystyle (\forall x)(\exists y)(x+y=xy)}$ je uzavřená ale ne otevřená
• formule ${\displaystyle (\forall x)(x<y)}$ není ani otevřená ani uzavřená
• formule ${\displaystyle 0+0=0}$ je otevřená i uzavřená

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

Podformulí formule ${\displaystyle \varphi }$ je každá formule, která je částí formule ${\displaystyle \varphi }$.

Říkáme, že proměnná x je vázaná ve formuli ${\displaystyle \varphi }$, jestliže existuje podformule formule ${\displaystyle \varphi }$ ve tvaru ${\displaystyle (\forall x)\psi (x)}$. Říkáme, že proměnná x je volná ve formuli ${\displaystyle \varphi }$, jestliže x má výskyt v nějaké podformuli ${\displaystyle \,\psi }$ formule ${\displaystyle \varphi }$ takové, že ${\displaystyle \,\psi }$ není podformulí žádné formule tvaru ${\displaystyle (\forall x)(\chi (x))}$.

Říkáme, že term t je substituovatelný za proměnnou x do formule ${\displaystyle \varphi }$, jestliže x není volná v žádné podformuli tvaru ${\displaystyle (\forall y)\psi }$, 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 ${\displaystyle \varphi }$ formule, ${\displaystyle \varphi (x/t)}$ značí formuli, která vznikne nahrazením (substitucí) termu t za každý volný výskyt proměnné x v ${\displaystyle \varphi }$.

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

Poznámky

Související články

• Výroková formule
• Predikátová logika prvního řádu

Externí odkazy

• Slovníkové heslo formule ve Wikislovníku