Formule (logika)

Z Wikipedie, otevřené encyklopedie
(přesměrováno z Formule predikátové logiky)

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 | editovat zdroj]

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 | editovat zdroj]

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 | editovat zdroj]

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 | editovat zdroj]

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 | editovat zdroj]

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 | editovat zdroj]

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 | editovat zdroj]

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

Související články[editovat | editovat zdroj]

Externí odkazy[editovat | editovat zdroj]

  • Slovníkové heslo formule ve Wikislovníku