Predikátová logika

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

V matematice a logice se pojmem predikátová logika označuje formální odvozovací systém používaný k popisu matematických teorií a vět.

Predikátová logika je rozšířením výrokové logiky. Na rozdíl od výrokové logiky má bohatší vyjadřovací schopnost. Predikátová logika všímá struktury vět. V každé větě rozlišuje individua o kterých se něco predikuje. Predikát je chápán jako vlastnost nebo vztah.

Vztahy výrokové logiky platí i v rámci predikátové logiky. Do výrokové logiky přidává kvantifikátory a vztah predikát - individuum. Individuum je prvek z nějaké množiny (univerza) a predikát je relace na této množině.

Existuje mnoho druhů predikátové logiky. Predikátová logika prvního řádu obsahuje pouze jeden druh proměnných pro individua. Mohou jimi být přirozená čísla, množiny, prvky, atd.. Jako zvláštní případ logiky prvního řádu existuje také predikátová logika prvního řádu s více druhy proměnných pro individua, jimiž jsou body, přímky,roviny atd.[1]

Dále existuje predikátová logika druhého řádu, která má dva druhy proměnných. Jedny pro pro individua a proměnné pro množiny individuí, predikáty a funkce.

Predikátová logika prvního řádu má dokazovací systémy, které jsou korektní a zároveň úplné. Pro logiky vyšších řádů to neplatí. Korektností se rozumí, že každá formule dokazatelná z axiomů (předpokladů) je tautologií. Úplností se rozumí, že každá tautologie je dokazatelná z axiomů.

Predikátová logika je také bezesporná z čehož plyne její obecná nerozhodnutelnost.

Historie[editovat | editovat zdroj]

Kořeny predikátové logiky lze vystopovat až k Aristotelovo sylogismu, který se datuje do 4 století před naším letopočtem.

Aristotelova logika se zabývá vztahem předpokladů a závěru při dokazování. Předpoklady pak definuje výroky, které přisuzují, nebo upírají jednu věc jiné. Věc, které něco přiřčeno nebo odepřeno, je předmětem věty a to, co je přiřčeno nebo upřeno předmětu, je predikát. Předmět a predikát jsou i tzv. pojmy (termy), které bychom dnes nazvali jmenné věty (přísudek je vyjádřen jménem nebo sponovým slovesem). Prohlášení všech medvědů za obratlovce znamená, že "medvěd" je předmětem a "obratlovci" je predikát.

O vývoj predikátové logiky se zasadil i Euklidés. Jeho hlavním dílem jsou Základy o třinácti dílech, jež začínají stanovením deseti základních postulátů či axiomů geometrie a pak postupují systémem vět a důkazů ke stále složitějším konstrukcím. Právě tento důraz na axiomy se základním kamenem pro další rozvoj.

Další, kdo se zasadil o rozvoj predikátové logiky, byl Angličan Vilém z Sherwoodu, který ve 13. století napsal knihu s názvem Úvod do logiky. Nejpozoruhodnější rys knihy byl způsob jakým se vypořádal s kvantifikátory. Logické výrazy "všichni", "ne", a "někteří", na nichž jsou založeny rozdíly mezi univerzálními a individuálními pojmy v Aristotelovo sylogismu. Vilém z Sherwoodu uznává rovnocennost různých kombinací kvantifikátorů a negací výroky které nejsou uvedeny v Aristotelově Sylogismu: negace univerzálních a jednotlivých pojmů.

V sedmnáctém století německý filozof, vědec, matematik Gottfried Leibniz poskytl jako první systematický výklad predikátové logiky. Prakticky nic z jeho objevů nebylo zveřejněno během jeho celého života - odhalení přišlo až na počátku dvacátého století. Leibniz přišel na to, že logika může být chápána algebraicky v analogii se sčítáním, odčítáním a násobením, což je systematický způsob, jak určit platnost výroků. Zvláštností této logiky byla shopnost interpretace výroků dvěma způsoby. Výroky mohou být chápány intencionálně nebo extensivně, což bylo pojetí, které bylo přijato dalšími generacemi logiků jako predikátová logiku.

Další vývoj na sebe nenechal dlouho čekat. Matematik Leonhard Euler v roce 1768 publikoval způsob, jak reprezentovat vztahy subjektů a predikátů geometricky. Celý systém pak o padesát let později vylepšil Francouz Joseph Diaz Gergonne, a pak Angličan John Venn a Američan Charles Sanders Peirce během pozdního devatenáctého století.

Během devatenáctého století George Boole (viz Booleovská logika) zdokonalil systém logiky, který stavěl na základech původní logiky stoiků. Vytvořil analogii mezi větnými operátory a teorií množin, čímž nabyla na možnostech rozsáhlejší interpretace.

V roce 1879 německý filozof Gottlob Frege publikoval Begriffsschrift (česky pojmové písmo nebo také jazyk formulí), první koherentní systém predikátové logiky. Největší Fregeho pokrok od Aristotelovo sylogismu byl dosažen zejména v obecnost jeho logiky. Ta dostala vyjadřovací schopnosti vyjádřit všechny kombinace kvantifikátorů a negací, stejně jako konjunkce, disjunkce, implikace a dvojité implikace (ekvivalence). Logika také dostala vyjadřovací prostředky pro relace - Aristotelova logika byla omezena na predikáty vztahující se pouze k jednotlivým termům.

Frege byl při tvorbě svého pojetí logiky inspirován z matematického pojetí aditivní funkce. Funkce sčítání o dvou argumentech f : x + y představuje určitou hodnotu. Frege předpokládal, že predikáty můžou zastat argumenty stejně jako v příkladu relace Otec (x,y) (x je otec y), což chová jako funkce. Když jména nahradíme proměnnými, vznikne věta. Takže stejně jako 1 + 2 označuje součet dvou čísel, Otec(Jan.Lucembursky, Karel.IV) (Jan Lucemburský je otcem Karla IV )znamená vztah mezi dvěma lidmi. Použití funkčního zápisu byl významný odklon historického pojetí, který se Fregemu podařilo obhájit.

Tyto změny od do té doby tradiční logiky přinesly pokrok díky zproštění se příliš úzké vázanosti na běžný jazyk a gramatiku. V díle Begriffsschrift pak tvrdí, že záměna konceptu subjektu a predikátu na funkci a její argumenty bude významná změna pro budoucí vývoj, která se zachová do dalších let.

Frege byl ve svých plánech velmi ambiciózní. Plánoval svojí logiku za pomoci několika axiomů a jednoho inferenčního pravilda pro dokazování. Domýšlel se, že s jeho logikou bude možné odvozovat všechny praidla aritmetiky. Tyto představy se později ukázaly jako liché.

Právě Bertrand Russell objevil paradox (Russellův paradox, nebo také Russelova antinomie), kterým dokázal, že Fregeho systém logiky jako celek nebyl konsistentní. "Objevil ho v roce 1901, když pracoval na své knize "Principles of Mathematics" (Principy matematiky) vydané v 1903. Paradox spočívá v definici množiny (symbol označuje "není prvkem množiny")"[2]

V roce 1905 Russell se vydal referát demonstrující vyjadřovací sílu predikátové logiky jako nástroj pro řešení filosofických problémů. Ve článku O označování (On denoting) Russell navrhuje metodu, jak analyzovat výroky zdánlivě přisuzující vlastnosti neexistujícím entitám.

"Nejznámější příklad Russellovy "analytické" metody se týkal použití popisů a vlastních jmen. Ve svém díle "Principles of Mathematics" (Principy matematiky) tvrdil, že každé označení (například "Scott, "modrý", "číslo dvě", "zlatá hora") označuje nebo se vztahuje k existující entitě. V roce 1905 ve svém článku "On Denoting" (O označování) tento extrémní realismus modifikoval a byl přesvědčen, že označování nemusí být teoreticky jednotné. Zatímco logicky vlastní jména (slova jako "tento" nebo "takový", která popisují vjemy, na něž se subjekt bezprostředně soustředil) mají význam odkazů s nimi spojených, deskriptivní fráze (jako "nejmenší číslo menší než pí") lze chápat jako soubor veličin (jako "všichni" nebo "několik") a definiční funkce (jako "" je číslo). Jako takové je nelze chápat jako odkazovací výroky, ale spíše jako "nekompletní symboly". Jinými slovy, lze je chápat jako symboly ve spojení s odpovídajícím kontextem, ale samostatně nemají žádný význam."[2]

Ve výroku "Současný král Francie je plešatý." definiční popis "současný král Francie" hraje zcela odlišnou roli od vlastního jména "Scott" ve výroku "Scott je plešatý." Jestliže symbolem K označíme predikát je současným králem Francie a symbolem B predikát "je plešatý", pak Russell přiřazuje výroku logickou formu

Existuje x takové, že         (a)  Kx

(b) Jestliže pro nějaké y  je Ky , pak  y=x       (c) Bx

V zápisu predikátového počtu máme  x[(Kx \wedge y(Ky y=x)) \wedge Bx] První výrok má naprosto odlišný tvar od výroku druhého. Pokud symbolem s označíme jméno "Scott", pak druhý výrok má logickou formu Bs
. Rozdíl mezi různými logickými formami umožnil Russellovi objasnit tři důležité záhady. První záhada se týkala působení zákona vyloučení třetího. Podle tohoto zákona totiž musí platit buď výrok "Současný král Francie je plešatý" nebo výrok "Současný král Francie není plešatý". Avšak oba výroky předpokládají existenci krále Francie, což je nežádoucí výsledek. Pokud se však použije logická analýza v podobě predikátového počtu, je jasné, že první výrok lze odmítnout bez vazby na existenci současného krále Francie, konkrétně pravdivým výrokem "Není pravda, že existuje současný král Francie, který je plešatý".[2]

Druhá záhada se týkala zákona identity. Přestože je pravdivý výrok "Scott je autorem Waverley", neznamená to, že predikát "je Scott" a "je autorem Waverley" jsou v každé situaci zaměnitelné. Například výrok "král Jiří IV. chtěl vědět, zda Scott je autorem Waverlay" má smysl, ale výrok "král Jiří IV. chtěl vědět, zda Scott je Scott" nedává smysl. Russell rozlišoval mezi formami, které používají vlastní jména a konkrétním popisem.[2]

Označme symbolem '' jméno "Scott", symbolem '' jméno "Waverley" a symbolem '' binární predikát "je autorem". Výrok s=s jistě není ekvivalentní s výrokem  x[(Axw \wedge y(Ayw y=x)) \wedge x=s]

 Třetí záhada se týkala pravdivosti negace existenciálního výroku, jako je tvrzení "Zlatá hora neexistuje." Russell znovu rozlišoval mezi logickou formou a vlastním jménem. Například výrok, že "Scott neexistuje", je nepravdivý, protože výrok \sim x(x=s) je vnitřně sporný. Musí existovat nejméně jeden subjekt, který je identický '', protože vždy platí, že . Na rozdíl od tohoto však výrok "Zlatá hora neexistuje" může být pravdivý. Označme '' predikát "je zlatý" a '' predikát "je hora". Pak v následujícím výroku neexistuje žádný rozpor \sim x(Gx\wedge Mx)

 Po značné námaze tedy Russell dovedl najít řešení svého paradoxu. S řešením paradoxu se opět navrátil k Fregeho práci, na které dále stavěl. To vyústilo v dílo Principia Mathematica o třech částech. které napsal společně s Alfredem Northem Whiteheadem vydávaném od roku 1910. V díle se snaží odvodit veškeré matematické pravdy ze sady axiomů a odvozovacích pravidel zapsaných za pomoci symbolické logiky. Vytvořili propracovanou sadu konceptů, ve které má každý reálný matematický objekt přiřazen svůj vlastní koncept. Typy jsou uspořádány do hierarchie a množiny mohou obsahovat pouze objekty nižšího typu. Vytvořili tak jakousi ontologii. Svazek Principia Mathematica je považován za jedno z nejdůležitějších děl z oboru matematické logiky a filosofie od dob Aristotela. Všechny tyto události mají za následek, že se problematika predikátové logiky dostala do popředí zájmu filosofického myšlení té doby.

Během vývoje predikátové logiky zůstala otevřena otázka úplnosti používaných systémů. Úplná logika znamená, že každá pravdivá věta systému může být i prokázána. Tou dobou se při zkoumání úplnosti zkoumala na platnost tvrzení, nikoliv zda-li jsou použity platné inference.

Ve své disertační práci z roku 1930 Kurt Gödel dokázal, že všechna platná tvrzení (tautologie) v systému předchůdců Russella a Whiteheada jsou dokazatelná z axiomů, a tak je možno o takové logice referovat jako o úplné.

V té době existují i jiné úspěšné pokusy té o nalezení způsobu dokazování úplnosti predikátové logiky. Mezi významné patří pokusy Leona Henkina.

V 30. letech 20 století se o rozvoj predikátové logiky zasadil polský logik Alfred Tarski. Byl to právě on, kdo poskytl formální výklad predikátové logiky. Až do tohoto bodu byly systémy predikátové logiky axiomatické.To znamenalo, že se utvořil malý souboru axiómů a inferencí, ze kterých byly tvořeny teorémy za pomoci odvozování. Tarski však našel obecnou metodu, která byla založena na konceptu pravdivosti vět s kvantifikátory.

Tarského formální definice pravdy má následující strukturu:[3]

Nechť L je jazyk, Mjeho interpretace, e pravdivostní ohodnocení a A je formule jazyka L.

Říkáme pak, že A je splněna v Mpři ohodnocení e a píšeme M A [e], podle složitostiA

  • A je atomická formule: A≡ p(t_1,...t_n), kde p
není rovnost. 
    • Potom M A [e], jestliže (t_1[e],...t_n[e]) \in\ p_m 
  • A je atomická formule, A≡ t_1=t_2 a t_1[e]=t_n[e] 
  • A je tvaru \neg B a  M| \ne B [e] 
  • A je tvaru C a  M| \ne B [e] nebo M  C [e] 
  • Je-li e ohodnocení proměnných, x je proměnná a m je prvek z domény M, je pozměněné ohodnocení e(\frac x m) definujeme: 

e(\frac x m) (y) = \left\{\begin{matrix} m,  \mbox{   pokud }y\equiv{ x} \\ e(y),  
         \mbox{   pokud   }y{\not \equiv}x\mbox{ }\end{matrix}\right.  

  • A je tvaru( \forall x)B
a MB
[e(\frac x m)]
pro každé m \in\ M
  • A je tvaru( \exists x)B a MB
[e(\frac x m)]
pro nějaké m \in\ M

Říkáme, že formule A
je pravdivá v M
a píšeme MA, je-li A
splněná v M
při každém ohodnocení proměnných.

  • Podobně jako u termů, splnění formule při nějakémohodnocení e
závisí jen na ohodnocení e(x) konečně mnoha proměnných.
  • Pokud má proměnná jen vázané výskyty, potom splnění formule nezávisí na ohodnocení této formule.
  • Je-li formule uzavřená, potom její splnění je pro všechna ohodnocení stejné. Stačí ověřit zda je splněna, či nesplněna při jednom ohodnocení.
  • Je-li uzavřená formule splněna při alespoň jednom ohodnocení, je pravdivá.
    • Říkáme, že formule je validní nebo logicky pravdivá a píšeme A pro každou interpretaci M.

Odvozovací pravidla[editovat | editovat zdroj]

\neg \bigwedge_x P(x) \Leftrightarrow \bigvee_x \neg P(x)
\neg \bigwedge_x \neg P(x) \Leftrightarrow \bigvee_x P(x)
\neg \bigvee_x P(x) \Leftrightarrow \bigwedge_x \neg P(x)
\neg \bigvee_x \neg P(x) \Leftrightarrow \bigwedge_x P(x)
\bigwedge_x \bigwedge_y P(x,y) \Leftrightarrow \bigwedge_y \bigwedge_x P(x,y)
\bigvee_x \bigvee_y P(x,y) \Leftrightarrow \bigvee_y \bigvee_x P(x,y)
\bigvee_x \bigwedge_y P(x,y) \Rightarrow \bigwedge_y \bigvee_x P(x,y)
\bigwedge_x P(x) \Rightarrow P(x)
P(x) \Rightarrow \bigvee_x P(x)

Místo \bigvee_x (resp. \bigwedge_x) se často používá \exists x (resp. \forall x), kde \exists je existenční kvantifikátor a \forall je univerzální kvantifikátor.

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

Externí odkazy[editovat | editovat zdroj]

  1. ŠTĚPÁNEK, Petr. Výroková a predikátová logika [online]. . Dostupné online.  
  2. a b c d JIŘÍ, Svršek. Filozofové vědy 20. století [online]. . Dostupné online.  
  3. PETR PAJAS. Základy logiky a teorie množin [online]. . Dostupné online.