- Stahuj zápisky z přednášek a ostatní studijní materiály
- Zapisuj si jen kvalitní vyučující (obsáhlá databáze referencí)
- Nastav si své předměty a buď stále v obraze
- Zapoj se svojí aktivitou do soutěže o ceny
- Založ si svůj profil, aby tě tví spolužáci mohli najít
- Najdi své přátele podle místa kde bydlíš nebo školy kterou studuješ
- Diskutuj ve skupinách o tématech, které tě zajímají
Studijní materiály
Zjednodušená ukázka:
Stáhnout celý tento materiálMatematická logika.
1
– – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – –
Marie Duží, Jaroslav Markl, katedra informatiky VŠB-Technická universita Ostrava.
Obsah
1. Úvod 2
2. Výroková logika 8
2.1. Sémantický výklad výrokové logiky. 8
2.2. Automatické dokazování ve výrokové logice (Rezoluční metoda) 23
2.3. Systém přirozené dedukce výrokové logiky 32
2.4. Axiomatický systém výrokové logiky 40
2.4.a. Obecná charak teristika formálních systémů. 40
2.4.b. For mální systém Hilbertova typu 42
3. Predikátová logika 1. řádu 52
3.1. Sémantický výklad predikátové logiky 52
3.1.1. Tradiční Aristotelova logika 69
3.2. Au tomatické dokazování v predikátové logice (obecná rezoluční metoda) 72
3.3. Systém přirozené dedukce predikátové logiky 93
3.4. Axiomatický systém predikátové logiky 98
3.4.a. Úvodní poznámky: 98
3.4.b. Formální systém Hilbertova typu 98
4. Formalizované teorie 102
4.1. Teorie relací a algebraické teorie. 104
4.2. Vlastnosti a význam formálních teorií – Gödelovy výsledky 113
LITERATURA 127
1. Úvod
Intuitivní, neformální, živé myšlení většiny lidí v naprosté většině případů dodržuje zákony logiky, aniž by lidé tyto zákony nutně znali a jejich používání si explicitně uvědomovali. Podobně lidé dokáží gramaticky správně se vyjadřovat ve svém mateřském jazyce, aniž by nutně znali a uměli formulovat gramatická pravidla, jimiž se používání jazyka řídí. Je však proto znalost logiky nebo gramatiky zbytečná? Nikoliv, a to přinejmenším z těchto důvodů:
1. Intuitivní, podvědomá znalost selhává ve složitějších nebo neobvyklých případech. To se stalo např. v matematice na přelomu 19. a 20. století. V teorii množin, která se měla stát exaktním základem celé matematiky, se objevily logické spory (paradoxy, antinomie), se kterými si intuitivní logika nevěděla rady. Řada podobných logických paradoxů byla formulována již ve starém Řecku. To vedlo k požadavku formálně definovat samotný proces deduktivního myšlení tak, aby jeho korektnost v konkrétních případech mohla být dobře ověřována.
2. Má-li být proces deduktivního myšlení (dokazování a odvozování) přenesen na nevědomý stroj, jak se o to snaží metody umělé inteligence, musí být tento proces nutně formalizován. Stroj (počítač) nemůže být vybaven živým intuitivním myšlením. Toto myšlení lze na počítači nanejvýš simulovat. Podobně také komunikace člověka s počítačem může probíhat pouze na základě formálního jazyka s přesně definovanou formální gramatikou.
Tento text se zabývá základy matematické (formální, symbolické) logiky a jejím vyžitím ve formálních sy stémech. Prvá část je věnována výrokové logice (logice 0-tého řádu), ve které primitivní formule (výrokové symboly) nemají žádnou vnitřní stavbu a jediným jejich atributem je pravdivostní hodnota. Druhá část je věnována predikátové logice 1. řádu, která pracuje s primitivními formulemi (predikáty) vypovídajícími o vlastnostech a vztazích mezi předměty jistého univerza diskursu (individui). Logiky 2. řádu (uvažující vlastnosti vlastností, vlastnosti vztahů, vztahy mezi vlastnostmi a vztahy mezi vztahy) a vyšších řádů se v matematice používají méně často a není zde o nich pojednáváno. Predikátová logika 1. řádu postačuje v běžných případech k formalizaci většiny matematických i jiných teorií.
Dříve však, než přistoupíme k vlastnímu výkladu, pokusme se odpovědět na následující otázky:
O čem je logika? Čím se tato vědecká disciplína zabývá? Kde všude nám může logika pomoci?
Logika nám může pomoci všude tam, kde vstupuje do hry jazyková komunikace, ovšem pouze tehdy, pokud se o výsledku sporu či diskuse apod. roz hoduje silou argumentu a ne argumentem síly. Tato charakteristika nám však zatím příliš nepomohla k tomu, abychom odpověděli na zbylé otázky. Odpovíme tedy jinak. Velice pregnantně řečeno:
Logika je (především) věda o správném usuzování, o umění správné ar gumentace.
Ovšem ani tato odpověď nám příliš nepomůže, pokud nevíme, co je to úsudek, a co je to správný (korektní, platný) logický úsudek, neboli argument.
Obecně můžeme úsudek charakterizovat následujícím schématem:
Na základě pravdivosti výroků (soudů , tvrzení) V 1 , …, V n soudím , že je pravdivý rovněž výrok V.
Zapisujeme schématicky: V 1 , …, V n / V nebo častěji:
V 1
V 2
… předpoklady neboli premisy
V n-1
V n
– – – – – –
V závěr
V praxi používáme různé druhy takovýchto úsudků, ovšem ne všemi se zabývá logika. Např. se obecně nezabývá tzv. pravděpodobnostními úsudky, např.:
Slunce doposud vyšlo každý den.
Tedy ----------------------------------------
Slunce (pravděpodobně) vyjde i zítra.
Podobně se nezabývá úsudky generalizací :
Všechny labutě, které jsme dosud viděli, jsou bílé.
Tedy ------------------------------------------------------------
Všechny labutě jsou bílé.
Takovéto metody odvozování závěru (případně metody zobecnění – indukce, vysvětlení – abdukce, a jiné) jsou předmětem jiných disciplín, např. Umělé inteligence, nebo také tzv. fuzzy logiky a nemonotónní logiky. V těchto případech je závěr spíše jakási hypotéza, a její pravdivost není zaručena pravdivostí premis, neboť z nich logicky nevy plývá.
My se zde budeme zabývat pouze tzv. deduktivními úsudky a definujeme:
Definice 1.1. ( logické vyplývání ):
Úsudek P 1 , …, P n / Z je deduktivně správný (platný) , značíme
P 1 , …, P n |= Z ,
jestliže závěr Z logicky vyplývá z předpokladů P 1 , …, P n , tj. za všech okolností, vždy, pokud jsou pravdivé předpoklady P 1 , …, P n , je pravdivý i závěr Z.
Tedy jinými slovy: Za žádných okolností, nikdy se nemůže stát, aby byly předpoklady
P 1 , … , P n pravdivé a zároveň závěr Z byl nepravdivý.
Deduktivní usuzování v pr aktickém životě všichni více či méně používáme, tedy usuzujeme logicky, aniž bychom si uvědomovali, že přitom používáme logiku. Tak např., jestliže víme, že všechny muchomůrky zelené jsou prudce jedovaté a zjistíme (např. za pomoci atlasu hub), že houba, kterou jsme nalezli, je muchomůrka zelená, pak jistě nebudeme tuto houbu ochutnávat a spolehneme se na logiku, neboť ta nám zaručuje, že houba, kterou jsme našli, je prudce jedovatá.
Příklady (jednoduchých, správných deduktivních úsudků).
1) Všechny kovy se teplem roztahují.
Měď je kov.
------------------------------------------
Měď se teplem roztahuje.
2) V seznamu novodobých římských císařů není žádná žena.
Marie Terezie byla žena.
------------------------------------------------------------------------------------
Není pravda, že Marie Terezie byla římská císařovna.
3) B. Bolzano zavedl jako první pojem množiny do matematiky.
B. Bolzano se narodil v Praze.
--------------------------------------------------------------------------
Jako první zavedl pojem množiny do matematiky rodák z Prahy.
4) Je doma nebo odešel do kavárny.
Je-li doma, pak nás očekává.
--------------------------------------------------------
Jestliže nás neočekává, pak odešel do kavárny.
5) Je-li tento kurs dobrý, pak je užitečný.
Buď je přednášející shovívavý, nebo je tento kurs neužitečný.
Ale přednášející není shovívavý.
--------------------------------------------------------------------------
Tento kurs je špatný.
6) Všechny muchomůrky zelené jsou prudce jedovaté.
Tato tužka je muchomůrka zelená.
---------------------------------------------------------------
Tato tužka je prudce jedovatá.
7) Všichni muži mají rádi fotbal a pivo.
Někteří milovníci piva nemají rádi fotbal.
Xaver má rád pouze milovníky fotbalu a piva.
– – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – –
Některé ženy nemá Xaver rád.
Správnost úsudku ověřujeme bez empirického zkoumání „stavu světa“, tedy pouze tzv. analytickými metodami, neboť správnost úsudku je dána pouze logickou strukturou premis a závěru. Některé úsudky jsou natolik jednoduché a zřejmé, že se zdá, jako bychom žádnou logiku ani nepotřebovali. Ovšem ne vždy tomu tak je. Např. již úsudek ad 5) se nemusí jevit na první pohled zřejmý, i když je poměrně jednoduchý, ověřitelný na základě nejjednoduššího systému výrokové logiky. Rovněž jednoduchý naprosto správný úsudek ad 6) může některé čtenáře překvapit. V praxi (např. v oblasti práva, medicíny, nebo v informatice) se setkáváme s daleko složitějšími úsudky, potřebujeme řešit úlohy typu „co vyplývá z daných předpokladů?“, apod., a pak již často nevystačíme s pouhou intuicí, potřebujeme se opřít o znalost logiky.
Logika tedy rovněž zkoumá skladbu – konstrukci jednotlivých složených výrazů (soudů) z jejich podvýrazů. Jednou z disciplín logiky je proto rovněž tzv. logická analýza jazyka, kter á spočívá v nalezení příslušné logické konstrukce vyjádřené daným výrazem. Ovšem ne všechny deduktivně správné úsudky můžeme ověřit pomocí daného logického systému. Proto hovoříme o expresivní síle logického systému, která je dána tím, do jaké míry podro bnosti můžeme analyzovat jednotlivé výrazy. Ideální logický systém by nám měl umožnit analyzovat premisy do takové hloubky, abychom mohli odvodit všechny závěry, které z těchto premis logicky vyplývají (provést všechny adekvátní inference ) a ověřit všechny správné úsudky. Při nedostatečně jemné a přesné (případně nesprávné) analýze premis pak můžeme dojít k různým paradoxním závěrům (např. známé jsou paradox analýzy, paradox lháře a paradox vševědoucnosti ).
Uvedeme nyní příklady logických systémů podle je jich expresivní síly.
Výroková logika (VL) umožňuje analyzovat pouze do úrovně elementárních výroků, jejichž strukturu již dále nezkoumá.
Predikátová logika 1. řádu (PL1) umožňuje navíc analyzovat elementární výroky do úrovně vlastností jednotlivých objektů zájmu (tzv. individuí – prvků univerza diskursu) a jejich vztahů.
Predikátové logiky vyšších řádů (PLn) umožňují navíc analyzovat vlastnosti vlastností, vlastnosti funkcí, atd.
Jedním z nejexpresivnějších logických systémů je tzv. Transparentní intensionální logika (TIL) , která pracuje s objekty libovolného řádu, umožňuje rozlišovat tzv. intenze a extenze, přesně explikuje pojem logické konstrukce, definuje, co je to pojem, pojmová analýza, atd. TIL je nyní stále populárnějším logickým systémem u nás i ve světě, a je využívána nejen v oblasti logické analýzy jazyka, ale také např. v oblasti konceptuálního modelování. TIL je předmětem samostatného kursu na této fakultě, který vřele doporučujeme.
Z našich příkladů můžeme ověřit na základě výrokové logiky pouze úsudky 4) a 5). Pro analýzu všech ostatních příkladů potřebujeme alespoň predikátovou logiku 1. řádu.
Vlastnosti deduktivních úsudků
Uvědomme si některé důležité vlastnosti deduktivních úsudků. Především, ověříme-li (dokážeme-li) správnost (platnost) úsudku, nedokážeme tím pravdivost závěru ! Závěr je pravdivý pouze za předpokladu pravdivosti premis. Tedy:
1) Platný úsudek může mít nepravdivý závěr.
(V tom případě je ovšem alespoň jedna z premis nepravdivá.) Toto je evidentně případ úsudku ad 6) (ovšem je to logicky platný úsudek!). Ovšem rovněž např. v případě ad 4) správnost úsudku nedokazuje, že dotyčný je v kavárně, jestliže nás neočekává, klidně mohl jít třeba do kina. V tom případě by ovšem zřejmě nebyla pravdivá první premisa.
Pozn.: V anglické litera tuře se někdy rozlišuje valid argument (platný úsudek – dle naší definice) a sound argument (řádný argument – platný úsudek a premisy pravdivé, tedy i závěr pravdivý). Překlad možná není výstižný, avšak toto rozlišení zachycuje případ, kdy jsou premisy (a tedy i závěr) pravdivé.
To ovšem neznamená, že platný úsudek, jehož závěr není pravdivý, by byl „bezcenný“. Vždyť takovýto způsob argumentace běžně používáme, chceme-li demonstrovat, že někdo neříká pravdu. Představme si dialog:
Vy tedy tvrdíte, že X 1,…,X n . Avšak z Vašich tvrzen
Vloženo: 24.04.2009
Velikost: 890,37 kB
Komentáře
Tento materiál neobsahuje žádné komentáře.
Copyright 2024 unium.cz