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.

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.

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