Slovník | Vyhledávání | Mapa webu
 
Základy informatiky pro biologyTeoretické základy informatiky Predikátová logika Sémantika predikátové logiky 1. řádu

Logo Matematická biologie

Sémantika predikátové logiky 1. řádu

Budeme se dále zabývat pouze tzv. predikátovou logikou 1. řádu, která formalizuje úsudky o vlastnostech předmětů a vztazích mezi předměty pevně dané předmětné oblasti (univerza). Nebudeme se zabývat formalizací úsudků, které navíc vypovídají i o vlastnostech vlastností a vztahů a o vztazích mezi vlastnostmi a vztahy. Tím se zabývají predikátové logiky druhého a vyšších řádů. Predikátová logika 1. řádu je zobecněním výrokové logiky, kterou můžeme považovat za logiku nultého řádu. Predikátová logika 1. řádu je postačující pro formalizaci mnohých matematických i jiných teorií.

Nyní si ukážeme, jak budeme tvořit výrazy predikátového kalkulu na základě jednoduchých pravidel. Prvně si vyjmenujeme základní komponenty, které budeme používat:

Abeceda predikátové logiky je tvořena:

  1. Individuálními jmény – konstantami - ty budeme označovat malými písmeny ze začátku abecedy: , (budou jim trvale přiřazeny konkrétní předměty, prvku z univerza)
  2. Individuálními proměnnými -  ty budeme označovat malými písmeny z konce abecedy: ... (proměnná neoznačuje konkrétní předmět, ale má svůj definiční obor (univerzum)).
  3. Funkčními symboly - ty budeme označovat také malými písmeny z prostřed abecedy . Funkční symboly přiřazují prvkům z definičního oboru jiné prvky z definičního oboru.
  4. Predikátovými symboly - ty budeme značit velkými písmeny . V případě predikátové logiky s rovností může být použit binární predikátový symbol .
  5. Logickými spojkami - budeme používáme symboly pro spojky, které již známe z výrokové logiky, tj.:.
  6. Kvantifikátory – budeme používat symboly
  7. Závorkami – budeme je používat jako pomocné symboly pro explicitní vyjádření priorit, případně pro lepší čitelnost výrazů. Bude se jednat o symboly , případně i

Poznámka: Ke každému funkčnímu a predikátovému symbolu je přiřazeno nezáporné číslo , tzv. arita, udávající počet individuových proměnných, které jsou argumenty funkce nebo predikátu.

Pouhé základní symboly nám však pro tvorbu výrazů predikátového kalkulu nebudou stačit. Musíme ještě definovat seznam pravidel (tzv. gramatiku), které nám budou dávat předpis, jak výrazy vytvořit. Gramatika jazyka predikátového kalkulu je dána následujícími pravidly:

  1. Každý symbol proměnné je term
  2. jsou-li  termy a je-li f n-ární funkční symbol, pak výraz f(t1,,tn) je term; pro n = 0 se jedná o nulární funkční symbol, neboli zvolení konstanty (konkrétního prveku z univerza)
  3. Jestliže  je -ární predikátový symbol a  jsou termy (nikoli nutně různé), pak výraz  je gramaticky správný výraz  (atomická formule).
  4. Jestliže  je gramaticky správný výraz, potom je rovněž gramaticky správný výraz.
  5. Jestliže ,  jsou správné gramatické výrazy, pak , ,,jsou rovněž gramaticky správné výrazy.
  6. Jestliže  je gramaticky správný výraz a  je individuální proměnná, pak  a   jsou gramaticky správné.
  7. Jen výrazy splňující body a - f jsou gramaticky správné a představují formule predikátového kalkulu.

Poznámka: Zápis formulí můžeme zjednodušit na základě následujících konvencí o vynechávání závorek:

  • Elementární formule a formuli nejvyššího řádu netřeba závorkovat (vnější závorky vynecháváme).
  • Závorky je možné vynechávat v souladu s následující prioritní stupnicí funktorů:
    ,. Každý funktor vlevo od vybraného funktoru váže silněji než vybraný funktor.
  • V případě, že o prioritě vyhodnocení nerozhodnou ani závorky ani prioritní stupnice, vyhodnocujeme formuli zleva doprava.
  • Speciálně vzhledem k asociativitě konjunkce a disjunkce, netřeba při zápisu vícečlenných konjunkcí a disjunkcí užívat žádné závorky.
  • Vedle závorek lze užívat i závorky .

Příklad: Jazyk elementární aritmetiky je případem jazyka predikátové logiky 1. řádu s rovností. Napište, jaké obsahuje funkční symboly a uveďte příklady termů a formulí v tomto jazyce.

Řešení

Tento jazyk má například tyto funkční symboly:

  • nulární symbol: (konstanta nula)
  • unární symbol:  (funkce následník)
  • binární symboly:  (sčítání a násobení)

Příkladem termů jsou například (používáme infixní notaci pro ):

Formulemi jsou například výrazy:

 

 

 
vytvořil Institut biostatistiky a analýz Masarykovy univerzity | | zpětné odkazy | validní XHTML 1.0 Strict