- 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álČást II. Matematická logika
Materiál je zpracován podle čtyř publikací:
Brabec, J.: Matematická logika. ČVUT Praha.
Ochranová, R.: Logika. MU Brno.
Janák, V.: Základy formální logiky. SPN Praha.
Jauris, M.: Logika. SPN Praha.
Učební cíle pro část II.
Seznámit se
s exaktním pojetím matematických struktur algebra a teorie a na příkladech jejich konkrétního použití pochopit účelnost zavedení a použití v práci informatika,
s příklady použití výrokového a predikátového kalkulu.
Znát
Základy klasického výrokového kalkulu.
Základy klasického predikátového kalkulu.
Umět, mít dovednosti
VÝROKOVÝ KALKUL: zapisovat formule, sestrojit pravdivostní funkci a pravdivostní tabulku formule, sestrojit disjunktní formu ze zadané pravdivostní tabulky formule, pracovat s tautologiemi a kontradikcemi, převádět logické spojky, získat negaci složité formule, zjistit zda úsudek je správný, konstruovat úsudky z jednoduchých formulí.
PREDIKÁTOVÝ KALKUL: zapisovat formule a zjistit jejich pravdivost, zjistit zda je úsudek správný.
Úvod
Logiku je zvykem charakterizovat jako analýzu metod lidského myšlení či uvažování, což odpovídá i smyslu slova logika. Často také slyšíme slovo logika s různými přívlastky, mluví se o formální logice, matematické logice, symbolické logice, ale také o pravděpodobnostní logice či vícehodnotové logice. V poslední době se mluví i o tzv. fuzzy logice. Vedle toho se slovo logika vyskytuje i v hovorové řeči, např. – to nemá logiku, ženská logika apod.
Shrneme-li všechny filosofické, i jiné úvahy o logice, můžeme logiku charakterizovat jako vědu o formách a zákonech vědomě odůvodněného myšlení.
My se budeme zabývat tzv. matematickou logikou. Tento pojem lze chápat jako označení pro formální a symbolickou logiku. Je to "matematizace" a formalizace zákonů vědomě odůvodněného myšlení.
Počátky logiky jako vědní discipliny sahají až do staré Číny a Indie (kolem 6. století př. n. l.). Podle dochovaných materiálů jde o pokusy rozpoznat objektivní zákonitosti myšlenkových operací. Nelze pochybovat, že tato zákonitost byla objevena na základě praxe, tj. neustálého styku s objektivní realitou. Praxe se stala prostředkem ověření a kontroly oprávněnosti poznatků o myšlenkových operacích.
V antickém Řecku byla zákonům lidského myšlení věnována velká pozornost a byla vytvořena logika, kterou dnes označujeme jako tradiční logiku. Hlavním představitelem této logiky byl Aristoteles (384 -321 př.n.l.). Aristotelova logika zkoumala formální stránku takových jevů lidského myšlení, jako jsou pojmy, soudy a úsudky. Aristoteles vytvořil učení o tzv. kategorickém sylogismu (Jestliže A platí o každém B a B platí o každém c, potom je nutno, aby platilo A o každém c), které bylo později doplněno učením o hypotetickém sylogismu (Je-li výrok A pravdivý a víme-li, že je pravdivý výrok "Jestliže A, pak B", potom můžeme usoudit na pravdivost výroku B).
Filosofie a matematika novověku přinesly nová pravidla a zpřesnění tradiční logiky. aparát tradiční logiky již nestačil ke zkoumání vztahů a k vyjádření zákonitostí, kterými jsou danými vztahy k sobě vázány objekty.
V devatenáctém století se logika dostává do nového období, období matematizace logiky. Teprve v XIX. století podal irský matematik G. Boole algebru logiky, která se nazývá po něm Booleova algebra. S dalšími příspěvky k rozvoji myšlenek G. Boole přišli A. de Morgan, G. Frege, A. Peano, D. Hilbert, B. Russel, K. Gödel a další. Dali tak základy směru označovaného jako matematická logika nebo formální, symbolická logika.
V obrovském rozsahu problémů, které zkoumá matematická logika, se postupně formovaly tyto oddíly matematické logiky:
Formalizovaná teorie.
Výrokový kalkul (počet).
Predikátový kalkul.
Teorie tříd a relací.
Teorie definice.
Teorie vyčíslitelných funkcí a algoritmů.
matematická logika je velmi těsně spjata se současným vývojem informatiky. Teorie vyčíslitelných funkcí a algoritmů vedla k prvním strojům ke zpracování dat, realizátorům algoritmů – automatům (Turingův a Postův automat). Automaty se staly základem číslicových počítačů.
Zkoumáme-li nějakou strukturu (třeba matematickou, která jak uvidíme později může být modelem jistého objektu reality), postupujeme tak, že formulujeme o ní platná tvrzení, která ji dobře vystihují. Pak na základě jistých pravidel odvozujeme tvrzení další. Postupně tak tvoříme tzv. kalkul. Mezi nejlépe prozkoumané kalkuly patří výrokový a predikátový kalkul.
Kvůli metodičnosti dalšího výkladu začneme oddílem "Formalizovaná teorie". To nám umožní upřesnit intuitivní chápání teorie a vyložit podstatu Výrokového a Predikátového kalkulu v obecnějším nadhledu:
Na základě pojetí formalizované teorie si ukážeme její variantu – formální výrokový/predikátový kalkul.
Potom na základě dvouhodnotové interpretace obou formálních kalkulů se dostaneme ke klasickému výrokovému/predikátovému kalkulu. To ale provedeme jen pro formální výrokový kalkul
Pokusme se teď zdůvodnit proč je znalost výrokového a predikátového kalkulu tak relevantní pro inteligentního informatika. Stačí uvést tento obecný důvod:
Obecně je uznáváno, že výrokový a predikátový kalkul jsou důležité pro správnou logickou mluvu a správné logické myšlení v každé poznatkové oblasti, tedy i v informatice.
Je proto hlavním cílem části II – Matematická logika pěstovat u studentů návyky pro správně formulovanou odbornou řeč v oblasti ekonomické informatiky. Toho lze dosáhnout na základě formování následujících znalostí, dovedností a návyků:
Umět formulovat v hovorové češtině nejen výroky (elementární, složené a zobecněné), ale i predikáty a výrazy z predikátů a převádět je do formálního zápisu, tj. formulí, v souladu s pravidly k jejich tvorbě.
naučit se číst a používat nejen jednoduché, ale i složitější formule výrokového a predikátového počtu.
Navyknout si vytvářet výrokové nebo predikátové formule o vztazích a vlastnostech předmětných objektů jako existenčně nebo obecně platné formule.
umět využívat odborné termíny z dané předmětné oblasti (např. algoritmizace, ...) a vytvářet na jejich základě správné odborné formulace ve tvaru výrokových nebo predikátových formulích, které popisují jisté vlastnosti a vztahy předmětných objektů a jejich kvantifikaci.
mít schopnost formulovat o předmětných objektech sekvence pravdivých výrokových nebo predikátových formulí a na jejich základě vytvářet o možných nových vlastnostech a vztazích předmětných objektů jisté soudy – závěry a potvrzovat jejich správnost.
Získat schopnost formulovat pro předmětnou oblast závěrečné bakalářské nebo magisterské práce jisté existenční nebo obecné hypotézy a znát a umět uplatnit metody dokazování jejich správnosti.
Uvedené znalosti, dovednosti a návyky lze dosáhnout jen spojeným úsilím přednášek, cvičení a samostudia podle e-learningových opor.
Uveďme teď přehled relevantních termínů z oblasti výrokového kalkulu:
elementární – atomický výrok
logické spojky, symbolická reprezentace
formalizace elementárních výroků
složené výroky
formule výrokového počtu
Lukasiewiczova notace formule
Pravdivostní funkce výrokové formule
Pravdivostní tabulka výrokové formule
Tautologie
Operace nad tautologiemi
Seznam tautologií
Vztahy mezi logickými spojkami, systémy spojek,
Peirceova a Schefferova spojka
Disjunktivní a konjunktivní normální formy
Negace výrokových formulí
Deduktivní soustava výrokového počtu
Ověření správnosti úsudku
Deduktivní pravidla
Nepřímý důkaz
Pojetí formalizované teorie
Intuitivní přístup k teorii
O teorii jsme již uvedli, že je vyšší matematickou strukturou než algebra, protože algebru v sobě obsahuje. Teorie má svůj jazyk, jehož částí je i jazyk algebry. Stěžejní komponentou teorie jsou axiomy – tvrzení, která jsou apriori pravdivá a nedokazují se.
Z axiomů teorie se vyvozují i všechny operace algebry. Teorie disponuje ve své logice vlastním odvozovacím a dokazovacím systémem nových tvrzení. Nic jsme zatím nemluvili o samotné podstatě logiky teorie. Tomu budeme muset věnovat v dalším textu velkou pozornost.
Formalizovaná teorie a její složení
Definice
Formalizovaná teorie T se skládá z
jazyka teorie J
logiky teorie ℒ
množiny axiomů A
Jazyk teorie
Pokud budeme o tomto jazyku mluvit volně, tak je zřejmé, že je vybudován nad jistou abecedou ( základních znaků. Nad touto abecedou lze tvořit řetězce, které mohou a nemusí být z jazyka J. Ze znaků abecedy se musí vytvořit jména objektů teorie, proměnné, znaky operací, konstanty, …
Definice jazyka může být provedena tradičním postupem, který nejdříve definuje elementární termy a potom na základě jistých pravidel vrchol jazyka - formule. Tento způsob je pro názornost sice dostatečný, formálně ale není v souladu s moderní teorií jazyků.
Moderní formalizace jazyka teorie je poněkud jiná a spočívá v nalezení gramatiky G = ( V, P, ( ) jazyka J, kde V = N ( ( je množina terminálů z abecedy ( a nonterminálů z množiny N. P je množina pravidel, pomocí kterých lze jazyk J odvodit. ((N je výchozí nonterminál. Základní operací při vyvození vět jazyka J je tzv. substituce, kdy za nonterminály dosazujeme pravidla, která je definují. Proces postupných substitucí se nazývá derivace. Cílem derivace je vyvodit z výchozího nonterminálu ( platnou větu x jazyka J. To se dá zapsat notací J = { x (x((* and ( (* x },
kde (* je množina všech řetězců nad množinou (.
Obecně se mluví o tom, že jazyk J je generován gramatikou G, což píšeme ve tvaru J = J ( G ). Jestliže je možno řetězec x((* derivovat z výchozího nonterminálu, je to důkaz, že x( J. Pro takovou větu jazyka J se často používá v jeho volném zavedení označení formule.
Příklad
Ukažme způsob generování jednoduchého jazyka identifikátorů pomocí gramatiky G. Použijeme následující definice abecedy, nonterminálů a pravidel:
Abeceda ( ={a,A,b,B,c,C, … , 0,1,2, …,9}
Nonterminály N = { < číslice>, < písmeno>, < identifikátor> }
Pravidla P : := 0(1(2(….(9
< písmeno> := a(A(b(B.…..z(z
< identifikátor> := < písmeno>(< identifikátor> < písmeno> ( < identifikátor> < číslice>
Výchozí je třetí pravidlo (modré). Např. derivace řetězce ab3 má následující tvar:
< identifikátor> := < identifikátor> < číslice> → < identifikátor>3 →
< identifikátor> < písmeno>3 → < identifikátor> b3 → < písmeno>b3 → ab3
→ je znak substituce.
Platí tedy < identifikátor> (* ab3 , což čteme následovně: „z výchozího nonterminálu < identifikátor> je v gramatice G derivován řetězec ab3. Je tedy tento řetězec z jednoduchého jazyka identifikátorů.
Co bude požadováno:
Znalosti:
Co je formalizovaná teorie, jaký je její zápis a stručně o významu komponent zápisu?
Jaká je běžná definice jazyka teorie?
Jaká je definice jazyka teorie podle matematické teorie formálních jazyků?
Dovednosti: žádné
Pojetí logiky teorie
Logika ℒ teorie T je druhou její strukturální komponentou. Bude vybudovaná nad množinou formulí spolu se speciální relací důsledku . Pomocí této relace budeme moci logicky odvozovat další správná tvrzení. Logika ℒ je budována počínaje definicí 2-1.
Nechť je již vybudován jazyk J teorie T . Označme symbolem ℱ množinu všech formulí jazyka J. Podmnožiny množiny všech formulí ℱ budeme označovat symboly (, (', ('', … Systém všech podmnožin množiny ℱ (potence množiny) označíme symbolem ℙ (ℱ).
Definice
Logikou ℒ teorie T nazveme množinu ℱ formulí spolu s jistou relací mezi ℙ (ℱ ) a ℱ , kterou nazveme relací důsledku. Logiku ℒ můžeme považovat za strukturu ℒ = [ℙ (ℱ ) x ℱ , ] , kde je jistá unární relace na ℙ (ℱ ) x ℱ.
Notaci ( a budeme číst jako "formule a je důsledkem množiny formulí obsažených v (. Všimněte si, že kartézský součin ℙ (ℱ ) x ℱ je množinou dvojic ((,y), kde ( je množina formulí a y jediná formule. Nevylučuje se ani ( = (. Definujme teď relaci .
Buď a(ℱ běžná formule množiny ℱ všech formulí a (, (' buďte podmnožiny množiny ℱ. Potom na relaci budeme klást tyto obecné definiční požadavky (ODPo):
{a} a pro každou formuli a(ℱ ……reflexivita relace
Jestliže ( a , pak (((' a pro každou množinu (' ( ℱ .
Jestliže ( a pro každou formuli a((' a jestliže (' b , pak ( b ….tranzitivita relace
Jestliže ( a , pak existuje konečná podmnožina ('( ( taková, že (' a ….finitnost dedukce.
Existuje neprázdná množina ℱL ( ℱ taková, že a(ℱL právě tehdy, když ( a . Formule a je univerzálně platná, tj. nepotřebujeme žádnou množinu ( premis, jejichž důsledkem by byla formule a.
Jestliže ( a , potom platí rovněž a , kde je permutace množiny (.
Jestliže {a}, ( b , potom a, ( b ……redukce notace.
Poznámka:
Zkratku OPi budeme používat v kalkulech jako adresaci na obecný požadavek.
Jestliže ( a , pak formule množiny ( nazýváme premisami (hypotézami), formuli a nazýváme konkluzí (závěrem). Říkáme, že "formule a je důsledkem formulí množiny (".
Formule množiny ℱL nazýváme logickými teorémy.
Jestliže ( = {a1, a2, …, an}, kde a1, a2, …, an jsou formule, pak místo {a1, a2, …, an} a budeme psát jen a1, a2, …, an a . Místo ( a budeme psát jen a , tj. formule a je logický teorém (v klasickém výrokovém kalkulu to budou např. tautologie).
Vlastnostmi 1-5 není relace jednoznačně určena. takových relací je mnoho (vše upřesňuje interpretace relace).
Příklad
Je zde uvedena ukázka interpretace relace důsledku. Představme si, že pracujeme s jistými jevy a množina ℱ je potom množinou výroků o jevech náležících právě prováděnému pokusu. ( je potom množinou výroků ohodnocujících jisté jevy. Je-li A jev, potom platnost ( A říká, že jev A je důsledkem jevů z (. Z množinového hlediska je vlastně A( Pro takové pojetí relace platí vlastnosti 1-3 a vlastnost 4 plyne z konečného charakteru našich úvah. Platí rovněž vlastnost 5, protože zcela jistě existují jevy univerzálně platné.
Deduktivní soustava, odvozování
Schéma odvozování (dedukce) v rámci tzv. deduktivní soustavy nám umožní interpretovat relaci důsledku přesněji. Pochopitelně, důsledky daných výroků – předpokladů odvozujeme z těchto předpokladů na základě jistých deduktivních pravidel a jistých výroků, které se považují za logicky správné a nazývají se logické axiomy. Deduktivní pravidla jsme si , my lidé, vytvořili během našeho rozumového vývoje. Obecně víme, že odvozování v matematice je velmi složitý proces. Máme na mysli to, že cesta od předpokladů k závěrům není vždy jen jednoduché použití jistých výroků, ale i použití mnoha pomocných odvození (lemma), která musí být předem připravena. Takovéto přirozené odvozování by šlo obtížně formalizovat. proto ve formalizované teorii definujeme tzv. formální odvozování na bázi jistých pravidel a logických axiomů, které dohromady tvoří deduktivní soustavu jazyka J. Definujme teď deduktivní odvozovací soustavu a bezprostřední důsledek.
Definice
Deduktivní soustava jazyka J je uspořádaná dvojice (AL, R), kde
AL je neprázdná množina tzv. logických axiomů, R je neprázdná množina odvozovacích pravidel zapisovaných ve tvaru a1, a2,…, an b .
Každé pravidlo r(R je jistá n-ární operace (zpravidla r =1,2), která každým n formulím a1, a2,…, an z jisté třídy formulí jazyka J, přiřadí právě jednu formuli b , kterou nazýváme bezprostředním důsledkem formulí a1, a2,…, an . Toto přiřazení, zachycené obecnou notací ℱn ( ℱ , zapisujeme také ve tvaru .
Odvozovací pravidla R jsou zvolena tak, aby z intuitivního hlediska z platnosti formulí a1,…, an plynula platnost formule b.
Teď svážeme bezprostřední důsledek s relací .
Jestliže platí , tj. formule b je bezprostředním důsledkem formulí a1, a2,…, an při použití jistého odvozovacího pravidla r(R, pak a1, a2, …, an b .
Pravidla odvození tedy umožní konstruovat nejjednodušší důsledky, z nichž každý se dá utvořit pomocí tzv. formálního odvození, které hned definujeme.
Vzájemný vztah logických teorémů (( a ) a logických axiomů (role formulí v odvozování) je takový, že logické teorémy budeme moci jistě použít v roli logických axiomů.
Definice
Formálním odvozením poslední formule cm (dále jen odvozením) z množiny formulí ( (může to být i prázdná množina) v deduktivní soustavě (AL, R) rozumíme každou konečnou posloupnost formulí c1, c2,…, cm m(1, kde každé ci je buď:
formule z (
nebo logický axiom z AL
nebo je bezprostředním důsledkem (použitím jistého odvozovacího pravidla z R) některých předchozích formulí ci1, ci2,…, cin , ik(i pro k=1,2,…, n .
Význam formule b, odvoditelné z množiny formulí ( v deduktivní soustavě, zavádí následující definice.
Definice
Řekneme, že formule b je odvoditelná z množiny ( v deduktivní soustavě (AL, R), tj. platí ( b, existuje-li takové odvození z množiny ( v soustavě (AL, R), že b je posledním členem tohoto odvození. Formuli, která je odvoditelná z prázdné množiny (, nazýváme dokazatelnou.
Dokazatelné jsou všechny logické teorémy. Aplikujme teď poznatky o relaci v obecné odvozovací soustavě (AL, R).
Definice
Říkáme, že ( b (tj. b je důsledkem formulí z () vzhledem k deduktivní soustavě (AL, R) právě tehdy, když b je odvoditelné v této soustavě z množiny formulí (.
Takto definovaná relace na ℙ (ℱ ) x ℱ, tj. mezi ℙ (ℱ ) a ℱ , má všechny vlastnosti 1-5. Navíc je AL(ℱL , kde ℱL je množina logických teorémů.
Závěr:
Až provedeme interpretaci obecných vlastností formálního odvození např. do klasického dvouhodnotového výrokového kalkulu dostaneme i známá odvozovací pravidla v množině R.
Axiomy teorie
Je nám již známo, že jde o množinu A axiomů – axiomatickou soustavu. Každý axiom je apriori pravdivý a nedokazuje se. Nejde zde o tzv. logické axiomy, které byly zavedeny v pojetí formálního odvození, ale o skutečné – pravé axiomy (viz např. později Teorii množin).
Formule odvoditelné z axiomů se nazývají věty-teorémy. Odvození věty z axiomů je důkazem její správnosti.
Definice
Je-li množina A=(, potom teorii (J, ℒ, A=() nazýváme formálním kalkulem neboli deduktivní teorií.
Takovými kalkuly budou "Formální Výrokový kalkul" a "Formální Predikátový kalkul". Nejsou to tedy teorie v plném slova smyslu. V kalkulech se za "jakoby" axiomy považují logické axiomy. Pro formální kalkuly se komponenty dvojice (J, ℒ) definují samostatně, protože jde o specifický jazyk a logiku.
Provedeme-li tzv. dvouhodnotovou interpretaci (pravda-lež true-false 0-1) formálního výrokového kalkulu dostaneme klasický dvouhodnotový výrokový kalkul. Podobné tvrzení o interpretaci platí i pro formální predikátový kalkul.
Formule odvoditelné z množiny A axiomů nazýváme teorémy – větami teorie. Odvození teorému z množiny a axiomů nazýváme formálním důkazem teorému.
Poznámka:
V teorii, která není kalkulem, tj. A ( (, zpravidla nevolíme za axiomy množiny A logické teorémy.
Další postup
Náš další postup může jít několika směry:
Vydefinovat celý formální výrokový/predikátový kalkul a potom jejich důsledně popsanou interpretací se dostat ke klasickému výrokovému/predikátovému kalkulu. Tím vlastně dojde k jejich popisu.
Jen stručně charakterizovat formální výrokový/predikátový kalkul a jeho interpretaci do klasického výrokového/predikátového kalkulu a rychle přejít k popisování klasického výrokového/predikátového kalkulu.
Nezabývat se vůbec interpretací formálního výrokového/predikátového kalkulu a rovnou začít popisování klasického výrokového/predikátového kalkulu.
My si vybereme druhou možnost, protože dává dostatečný přehled nejen o skladbě formálního výrokového/predikátového kalkulu, ale i o podstatě jejich dvouhodnotové interpretace do klasického výrokového/predikátového kalkulu. Tuto možnost ale uplatníme jen na výrokový kalkul.
Co bude požadováno:
Znalosti:
Jak je definována logika teorie?
Jaké jsou požadavky na relaci ?
Co jsou logické teorémy?
Jak je definována deduktivní soustava odvozování, co je bezprostřední důsledek, co je formální odvození?
Co jsou axiomy teorie?
Jak je definován formální kalkul?
Dovednosti: žádné
Základy formálního výrokového ka
Vloženo: 5.02.2012
Velikost: 961,77 kB
Komentáře
Tento materiál neobsahuje žádné komentáře.
Mohlo by tě zajímat:
Skupina předmětu TZI - Teoretické základy informatiky
Reference vyučujících předmětu TZI - Teoretické základy informatiky
Podobné materiály
Copyright 2024 unium.cz