Predikátová logika

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. +more Predikátová logika si 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. +more 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. +more 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.

Dále existuje predikátová logika druhého řádu, která má dva druhy proměnných: jedny pro individua a druhé 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í. +more 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.

Predikátová logika je exaktní věda

Každá formální logika (matematická logika), a tak i predikátová logika je postavena jako exaktní věda, její jazyk je umělý formální jazyk s exaktní interpretací, a jinou mít nesmí. Formální jazyk je schopen popisovat (reprezentovat) pouze entity exaktního světa. +more Pokud má popisovat entity reálného světa, je nutno použít prostředníka, který to umožňuje, a tím je veličina viz Věda . Rozhodnutelnost (pravda, nepravda) je vlastností exaktního světa. Nelze ji uplatnit v neodstranitelné mlze vágnosti významů přirozeného jazyka s vágní, subjektivní, emocionální, a v čase se měnící interpretací, které říkáme konotace.

V minulosti si tyto okolnosti někteří logici neuvědomovali a v logice používali přirozený jazyk v úloze objektového jazyka (někdy ve směsi s formálním jazykem), tak znehodnocovali čistotu její výstavby. Ze shora uvedeného tedy plyne, že logika postavená nad přirozeným jazykem nemůže existovat, a to ani ve své neformální podobě (není schopná zajistit rozhodnutelnost), ani ve formální podobě (přirozený jazyk nemůže být součástí exaktního světa). +more Existuje pouze formální logika, která je postavená na umělém formálním jazyce, a je schopna operovat pouze s objekty exaktního světa.

Aristotelovu logiku a „slovní“ logiky navazujících autorů je nutno považovat pouze za předobraz logiky, i když jistě cenný.

Historie

Kořeny predikátové logiky lze vystopovat až k Aristotelově sylogismu, který se datuje do +more_n. _l. '>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é. +more Věc, které je 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. +more 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 stal 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. +more Nejpozoruhodnější rys knihy byl způsob, jakým se vypořádal s kvantifikátory. Použil 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 Aristotelově 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í. +more 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 schopnost 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á logika.

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. +more 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ž logika 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 Aristotelova sylogismu byl dosažen zejména v obecnosti jeho logiky. +more 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. +more Frege předpokládal, že predikáty mohou 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 logiky do té doby tradiční přinesly pokrok tím, že se zprostily příliš úzké vázanosti na běžný jazyk a gramatiku. V díle Begriffsschrift pak Frege tvrdí, že záměna konceptu subjektu a predikátu na funkci a její argumenty bude významnou změnou pro budoucí vývoj, která se zachová do dalších let.

Frege byl ve svých plánech velmi ambiciózní. Plánoval svoji logiku za pomoci několika axiomů a jednoho inferenčního pravidla pro dokazování. +more Domníval se, že s jeho logikou bude možné odvozovat všechna pravidla 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. +more Paradox spočívá v definici množiny (symbol označuje "není prvkem množiny")".

V roce 1905 Russell 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ě. +more 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 větší 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. ".

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ý. +more" 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. +more 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ý".

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é. +more 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.

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. +more 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. +more 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. +more Tou dobou se při zkoumání úplnosti zkoumala na platnost tvrzení, nikoliv zdali 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. +more 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:

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. +more  ** 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 M⊨B [e(\frac x m)] pro každé m \in\ M * A je tvaru( \exists x)B a M⊨B [e(\frac x m)] pro nějaké m \in\ M Říkáme, že formule A je pravdivá v M a píšeme M⊨A, 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ém ohodnocení e závisí jen na ohodnocení e(x) konečně mnoha proměnných. +more * 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

:\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. +more \forall x), kde \exists je existenční kvantifikátor a \forall je obecný kvantifikátor.

Související články

Predikátová logika prvního řádu * Predikátová logika druhého řádu

Reference

Externí odkazy

[url=http://www. martinvseticka. +moreeu/skola/vyrokova_logika/predikatova-logika-cviceni-josef-mlcek. pdf]Řešené příklady z predikátové logiky[/url] * [url=http://plato. stanford. edu/index. html]Stanford Encyclopedia of Philosophy[/url] * [url=http://books. google. cz/books. id=f3uMdwDVvL8C&lpg=PA27&dq=history%20of%20logic%20predicate&hl=cs&pg=PA3#v=onepage&q=history%20of%20logic%20predicate&f=false]William of Sherwood's Introduction to Logic[/url].

Kategorie:Matematická logika