Teoretická informatika Tomáš Foltýnek Úvod do předmětu Formalismus a jeho užití Teorie a axiomy

Teoretická informatika Tomáš Foltýnek [email protected]

Úvod do předmětu Formalismus a jeho užití Teorie a axiomy

Teoretická informatika

Cíle předmětu •  Poskytnout dostatečné teoretické zázemí •  Dát jiný pohled na informatiku •  Odlišit inženýra od „kodéra“ •  Seznámit s otevřenými problémy •  Umožnit použití formalismu v DP

2


Osnova předmětu • 

Matematika a její vztah k informatice –  –  –  – 

• 

Výroková logika Predikátová logika Teorie množin Algebra

Formalizace počítače –  Turingovy stroje –  Rozhodnutelnost problémů

• 

Složitost algoritmů –  Odhad složitosti algoritmů –  Složitostní třídy

• 

Pokročilé datové struktury –  Grafy, stromy –  Algoritmy nad těmito strukturami –  Sítě, toky v sítích

• 

Paralelní programování –  Paralelní systémy, Petriho sítě

3


Studijní materiály •  Vaníček, J.: Teoretické základy informatiky. Praha: Alfa, 2007. ISBN 978-80-903962-4-1 •  Slidy z přednášek •  E-learningová osnova/opora v UIS •  Google, Wikipedia (anglická!) •  Další materiály u jednotlivých celků

4


5

Ukončení předmětu •  5 cvičení => 5 domácích úkolů

–  Na každý úkol možno získat 0-10 bodů –  Celkem tedy 50 bodů

•  Kdo má 30 bodů, má zápočet –  Kdo ne, napíše si písemku

•  písemka může přidat max. 15 bodů

–  Kdo nemá zápočet ani po písemce… 

•  Kdo má zápočet, může jít ke zkoušce –  Zkouška bude ústní –  Teorie (přednášky) i praxe (cvičení)

•  45 bodů z úkolů => zkouška jen teoretická


Prosba: Komunikujte •  Ptejte se na přednáškách, cvičeních •  Chcete-li něco procvičit, pošlete včas e-mail •  Konzultační hodiny po domluvě e-mailem

6


Formalismus a jeho užití v informatice


Formalismus a jeho použití •  Je soubor syntaktických a sémantických pravidel pro popis nějaké reálné skutečnosti •  Formalismus nahrazuje reálný objekt jeho formálním modelem, který poté můžeme zkoumat •  Cílem užití formalismu je obvykle odstranění nejednoznačnosti přirozeného jazyka •  Formalismus umožňuje popis libovolně složitých problémů

8


Proč zavádíme formalismus •  Potřebujeme přesně specifikovat (zapsat) naše myšlenky •  Jde o jednotný jazyk pro popis problémů a jejich řešení –  teoretických i praktických

•  Viz gnoseologický čtyřúhelník

9


Jaký formalismus? •  Existují dva základní druhy: –  matematický (exaktní) –  filozofický (intuitivní)

•  Je možné užít oba principy, výsledné dokazování se však vede exaktně •  Každý problém lze formalizovat •  Ne každý problém lze v daném formalismu rozhodnout –  slepice/vejce

•  Kritéria správnosti závěrů –  empirické vědy: pravda = shoda se skutečností ověřená experimentem –  formální modely: platnost = odvoditelnost z přijatých předpokladů

10


Jak formalismus použít I. • 

Zvolíme formalismus –  existuje více možností pro daný problém –  ne každý formalismus je vhodný –  musíme obvykle ověřit více formalismů

•  •  •  •  •  • 

Formalismus nastudujeme a vyzkoušíme si na modelové situaci Formulujeme 1. intuitivní představu našeho problému užitím formalismu Ověříme formální správnost zápisu Ověříme formulovaný zápis na dostupných modelech problému Zpřesníme formální zápis Iterujeme předchozí trojici kroků až do okamžiku dosažení dostatečné podrobnosti a správnosti zápisu

11


Jak formalismus použít II. •  Formalismus může být nevhodný –  žádný formalismus nenpoíše skutečnost zcela přesně –  je třeba zjednodušovat

•  Pokud jsme dosáhli správné formální specifikace našeho problému, můžeme začít využívat všech vlastností a možností formalismu: –  –  –  – 

hledání odvozených vlastností dokazování vlastností a jejich důsledků klasifikace problémů do tříd hledání úplnosti problémů v třídách

12


Hlavní zásady •  Formalismus není cíl, ale prostředek pro vyjádření myšlenek •  Na správném výběru formalismu závisí úspěch řešení problému •  Je užitečné předložit formulovaný problém k posouzení jiné osobě, která formalismus zná •  S dostatečnými matematickými znalostmi lze zavést libovolně složitý formalismus, jedná se však pouze o sbírku řeckých písmen a značek

13


Teorie a axiomy

strana 14


Tvrzení a důkazy •  Matematika je deduktivní věda •  Všechny pojmy se vymezují definicí –  složitější pojmy definujeme na základě jednodušších

•  Matematické tvrzení (věta) je výrok, který může být buď pravdivý, nebo nepravdivý –  právě jeden stav

•  Pravdivost nemusí být známa •  Kritériem pravdivosti matematického tvrzení je jeho důkaz


strana 16

•  Otec s dítětem jdou po břehu řeky. Vyskočí krokodýl, sežere dítě a říká: “Vrátím ti dítě, pokud uhodneš, jestli ti vrátím dítě, nebo ne.” –  Otec odpoví: “Nevrátíš ho.” –  Co krokodýl udělá?

•  Právník Corax učí Tisiase. Domluví se, že Tisias mu za hodiny zaplatí, až vyhraje svůj první případ. Poté se právem nezabývá a Corax jej žaluje, aby mu za hodiny zaplatil. –  Tisias: Pokud vyhraju, nemusím ti nic platit (rozhodnutí soudu). Pokud prohraju, nemusím ti nic platit (ještě jsem nevyhrál žádný případ) –  Corax: Pokud vyhraju, musíš mi zaplatit (rozhodnutí soudu). Pokud prohraju, vyhraješ svůj první případ a musíš mi zaplatit. zdroj: e-polis.cz

zdroj: akva-exo.cz

Paradoxy naivní teorie množin I.


strana 17

Paradoxy naivní teorie množin II. •  Paradox lháře: “Teď lžu.” •  Richardův / Berryho paradox –  Nejmenší přirozené číslo, které nelze definovat méně než dvaceti slovy.

•  Grellingův sémantický paradox –  Slovo je autologické ⇔ je samo o sobě pravdivé •  př.: „české“, „krátké“,...

–  Slovo je heterologické ⇔ je samo o sobě nepravdivé •  př.: „německé“, „nejdelší“,...

–  Kam zařadit slovo „heterologické“? A „autologické“?


strana 18

Paradoxy naivní teorie množin III. •  Russelův paradox: {x| x ∉ x} –  Holič holí všechny, kteří se sami neholí –  Katalog katalogů neobsahujících sebe sama

•  V matematice je všechno množina. Je-li teorie množin sporná, pak je sporná celá matematika 


strana 19

Krize matematiky • 

1. krize matematiky – Řecko –  každé číslo lze vyjádřit jako poměr jiných čísel (existují jen racionální čísla) –  matematikové byli spíše “sekta” –  východisko: iracionální čísla

• 

2. krize matematiky – aktuální nekonečno –  infinitezimální a integrální počet –  vágní definice nekonečně malých veličin –  Bolzano, Cauchy, Weierstrass: ε-δ definice limity

• 

3. krize matematiky – paradoxy teorie množin –  částečně vyřešeno axiomatickou výstavbou –  krize přetrvává dodnes


strana 20

Řešení paradoxů •  •  •  •  • 

Axiomatická výstavba teorie Oddělení syntaxe od sémantiky Syntaxe vychází z primitivních pojmů a axiomů Sémantika vychází z modelu Objekty, které nevyhovují axiomům v dané teorii nemohou existovat •  Např. v teorii množin nemůže existovat “množina všech množin”


strana 21

Jazyk matematické teorie •  Abeceda – souhrn znaků užívaných v teorii •  Slova a věty (formule) – povolené řetězce znaků •  Smysluplné formule (z hlediska sémantiky) •  Pravdivé formule (dokazatelné z axiomů) •  Odvozovací pravidla – nezbytná pro dokazatelnost •  Metajazyk – používáme k popisu jazyka teorie (např. mezera je metaznak)


Axiomatická výstavba teorie •  Axiomy jsou výchozí tvrzení dané teorie, která se nedokazují a jejichž platnost se předpokládá –  základní formule jazyka teorie

•  Primitivní pojmy jsou nedefinované pojmy –  jejich vlastnosti jsou určené axiomy –  sémantiky primitivních pojmů je dána modelem teorie

•  Z axiomů se dedukcí odvozují další tvrzení nazývané důsledky –  využití odvozovacích pravidel


strana 23

Model teorie •  Axiomatická teorie je ryze syntaktická záležitost –  dokazování v teorii lze algoritmizovat

•  Představujeme-li si pod primitivními pojmy objekty reálného světa, vytváříme model teorie. •  Modelů lze obecně vytvořit více –  každá množina reálných objektů vyhovující axiomům může být modelem teorie

•  Ve školách se učí model teorie množin, model euklidovské geometrie, atd.


Vlastnosti axiomatické teorie •  Nezávislost axiomů – žádný axiom není důsledkem zbývajících axiomů –  byl by zbytečný

•  Bezespornost – důsledkem nemůže být tvrzení a současně jeho negace •  Úplnost – každé tvrzení lze v dané teorii dokázat, anebo vyvrátit


strana 25

Euklidovská geometrie 1.  Máme-li dány dva body, existuje jedna přímka, která jimi prochází. 2.  Konečnou přímou čáru (úsečku) můžeme prodloužit tak, že vznikne opět úsečka. 3.  Je možné nakreslit kružnici s libovolným středem a poloměrem. 4.  Všechny pravé úhly jsou si rovny. 5.  K dané přímce a bodu, který na ní neleží, lze sestrojit právě jednu rovnoběžku, která prochází daným bodem.


strana 26

Neeuklidovské geometrie •  1829 N.I. Lobačevskij •  Neplatí 5. axiom •  Rovnoběžek může daným bodem procházet více, nebo žádná •  Modely neeuklidovské geometrie –  sférická geometrie –  hyperbolická geometrie

zdroj: wikipedia


Formalizace matematiky •  Snaha o řešení paradoxů naivní teorie množin •  Zermelo-Fraenkelova axiomatická teorie množin je vystavěna nad logikou •  Obavy ze vzniku dalších paradoxů (otázka bezespornosti) vede ke snahám o formalizaci matematiky •  Dokazování bezespornosti silných matematických teorií prováděno pomocí kombinatorických manipulací s formulemi (Hilbertův program f.m.) •  Kurt Gödel roku 1931 formuloval a dokázal věty o neúplnosti, jejichž důsledkem bylo dokázání, že Hilbertův program nelze uskutečnit


1. Gödelova věta o neúplnosti Každá bezesporná matematická teorie, obsahující jako svoji součást aritmetiku nad přirozenými čísly, není úplná.


Důkaz I: Malá Gödelova čísla •  Každý symbol teorie dostane po řadě číslo 1, 2, 3, … •  Malé Gödelovo číslo formule je dáno jako součin prvních prvočísel umocněných na číslo symbolu •  Např.: –  označení symbolů (=1, )=2, x=3, y=4, z=5, ⇔=6, ∧=7 –  g(„(x∧y)⇔z“) = 21 · 33 · 57 · 74 · 112 · 136 · 175 •  Označme G množinu všech Gödelových čísel korektně utvořených formulí. –  Vlastní podmnožina N. –  Pro každé n∈N umíme rozhodnout, zda n∈G. –  Tvrzení „ n∈G“ je tedy aritmetické tvrzení


Důkaz II: Velká Gödelova čísla •  Nechť ϕ1, ϕ2, … ϕn je důkaz formule ϕn. •  Velkým Gödelovým číslem tohoto důkazu nazveme číslo 2g(ϕ1) · 3g(ϕ2) · … · png(ϕn) •  Opět tedy můžeme zavést množinu všech velkých Gödelových čísel H⊂N. •  Označme dem(y,x) tvrzení, že y je velké Gödelovo číslo důkazu formule s malým Gödelovým číslem x. –  dem je relace na N2

•  Tvrzení o dokazatelnosti formule ψ jsme tedy převedli na pravdivost/nepravdivost aritmetického tvrzení (∃y∈H): dem(y,g(ψ))


Důkaz III: Spor nebo neúplnost •  Existuje číslo k∈G takové, že –  g(χ) = k –  χ = ¬(∃y∈H): dem(y,k)

•  Formule χ je dokazatelná ⇒ Nelze dokázat formuli s Gödelovým číslem k ⇒ Nelze dokázat formuli χ •  Formule χ není dokazatelná ⇒ Lze tedy dokázat formuli s Gödelovým číslem k ⇒ Lze dokázat formuli χ •  Jsme-li v bezesporné teorii, pak je χ nerozhodnutelná formule.


2. Gödelova věta o neúplnosti

Žádný formální systém zahrnující alespoň aritmetiku přirozených čísel nemůže dokázat vlastní bezespornost


strana 33

Shrnutí •  •  •  •  •  •  • 

Co je to formalismus a co je jeho cílem? Formulujte Russelův paradox naivní teorie množin V čem spočívaly tzv. krize matematiky? Jak se buduje axiomatická teorie? Jaký je rozdíl mezi teorií a jejím modelem? Co je to neeuklidovská geometrie? Co je to nezávislost, úplnost a bezespornost axiomatického systému? •  Formulujte Gödelovy věty o neúplnosti

Teoretická informatika Tomáš Foltýnek Úvod do předmětu Formalismus a jeho užití Teorie a axiomy

Recommend Documents