Matlogika

0ed; plyne, že A. Z A dále plyne, že B, atd., až dostaneme závěr Z, který je evidentně nepravdivý. Tedy Vy tvrdíte Z, což není pravda. Proto alespoň jedno z Vašich původních tvrzení X i není pravdivé.
2) Monotónnost. Jestliže P 1, …, P n |= Z , pak P 1, …, P n, P n+1 |= Z , pro libovolnou další premisu P n+1.
Pozn .: Tuto vlastnost nemají jiné úsudky, které nejsou deduktivní, např. úsudky generalizací, kdy závěr nevyplývá z předpokladů. Jestliže např. na základě pozorování 10000 bílých labutí usoudíme (generalizujeme), že všechny labutě jsou bílé, a pak přijedeme do Austrálie a spatříme černou labuť (tedy přidáme premisu že Australská labuť je černá), náš závěr je evidentně nepravdivý, i když premisy jsou stále pravdivé. Tedy úsudky generalizací nejsou deduktivní a jsou nemonotónní. Tímto problémem se pak zabývají metody umělé inteligence (využívající tzv. nemonotónní usuzování ) a provádějící tzv. revizi hypotéz („belief revision“).
3) Tranzitivita.
Jestliže P 1, …, P n |= Z a Q 1, …, Q m, Z |= Z’ , pak P 1, …, P n, Q 1, …, Q m |= Z’ .
4) Reflexivita. Je-li B rovna jedné z premis P 1, …, P n, pak P 1, …, P n |= B.
Na závěr zavedeme ještě dva důležité pojmy a jejich značení, a to pojem analytické pravdivosti, a pojem kontradiktorické (sporné) množiny výr oků.
Definice 1.2. (analytická pravdivost, kontradikce)
Výrok V je analyticky pravdivý , značíme |= V, je-li pravdivý za všech okolností, vždy. (Množina předpokladů je prázdná, V nemůže být nepravdivý.)
Množina P 1, …, P n výroků je sporná (kontradiktorická, nesplnitelná) , jestliže nemůže nikdy za žádných okolností nastat případ, že by byly všechny P 1, …, P n pravdivé, značíme
P 1, …, P n |= . ( Tedy z této množiny logicky vyplývá jakýkoli výrok, i nepravdivý, proto musí být vždy alespoň jeden P i nepravdivý.)

Nyní můžeme formulovat ještě jednu důležitou vlastnost deduktivních úsudků:
5) Ze sporné množiny předpokladů vyplývá jakýkoli závěr.

Příklady:
|= 1+1= 2
|= V Praze prší nebo neprší.
Pozn.: Všechny pravdivé matematické výroky jsou analyticky pravdivé. „Běžné“ výroky přirozeného jazyka nejsou analyticky pravdivé (jsou empirické, o „stavu světa“, mohou být někdy pravdivé, jindy ne).
P 1: „Jestliže A, pak B“. P 2: „A a ne B“. P 1, P 2 |= (kde A, B jsou libovolné výroky).

Nyní uvedeme příklad, který ilustruje vlastnost 5) – ze sporné množiny předpokladů vyplývá cokoliv.
Na schůzi výboru byla projednávána žádost pana X o zařazení do vyšší platové stupnice. Pan X si přál, aby ji mzdová komise doporučila. Ale výbor právě odstupoval a již předtím rozhodl, že doporučí pana X jako nového člena mzdové komise budoucího výboru. Takže by pak pan X byl členem komise, která bude posuzovat jeho vlastní žádost. Rozvinula se diskuse a bylo řečeno:
1. X přešel na kvalifikovanější práci.
2. X dobře rozumí mzdovým otázkám.
3. Jestliž e X přešel na kvalifikovanější práci, pak je správné, aby jeho žádost byla projednána.
4. Jestliže je správné, aby jeho žádost byla v komisi projednána, pak by neměl být členem komise.
5. Rozumí-li výtečně mzdovým otázkám, měl by být členem komise.
Předseda nakonec řekl: „Všechny přednesené příspěvky jsou pravdivé. Teď jde o to, co z toho vyplývá.“ Po chvíli ticha prohlásil mladý zapisovatel (který náhodou studoval logiku na VŠB): „Z toho vyplývá, že můj pes právě hraje doma na piano.“
Vyplývání je tedy základním (veledůležitým) pojmem pro logiku, a je rovněž vysoce ceněno matematiky. Matematikové formulují a dokazují tvrzení. Výsledkem jejich práce je tedy zpravidla (ne-li vždy) nalezení nějakého důkazu. Avšak důkazy a jejich analýza je to, co zajímá logiky, důkaz je rovněž jedním z nejdůležitějších logických pojmů. Co je to důkaz? Obecně řečeno, důkaz tvrzení A z předpokladů P 1 ,…,P n je posloupnost tvrzení B 1 ,…,B m taková, že:
§ B m = A
§ pro každé i m platí, že B i je buď
- jeden z předpokladů P j nebo
- B i vznikne z před chozích B 1 ,…,B i-1 uplatněním nějakého odvozovacího pravidla.
Přitom je samozřejmě žádoucí, aby odvozovací pravidla byla volena tak, že to, co dokážeme, logicky vyplývá z daných předpokladů. Chceme-li tedy charakterizovat určitou vědeckou disciplinu (například v matematice teorii přirozených čísel nebo teorii množin či grup apod.), můžeme se pokusit zvolit jistou množinu předpokladů, kterým říkáme axiómy a o kterých předpokládáme, že jsou pro tuto oblast pravdivé , a za použití vhodných odvozovacích pravidel dokázat mnohá (nebo dokonce v ideálním případě všechna) tvrzení, pravdivá v naší disciplině. (Pokud jsou axiómy analyticky pravdivé, pak tvrzení, která dokážeme, jsou rovněž analyticky pravdivá, tedy vždy, nejen ve zvolené disciplíně.) Takováto množina axiómů a odvozovacích pravidel (formulovaná v jistém formálním jazyce) se pak nazývá logická teorie. Vyhledávání a formulování axiómů a pravidel s cílem vytvořit teorii, která by pak mohla sloužit jako přesný základ pro další práci, by mohlo trvat velmi dlouho nebo dokonce donekonečna. Tato situace není vyloučena, ale typické je to, že nenastane. Např. jedna z nejdůležitějších matematických teorií, Goedel-Bernaysova teorie množin, má přehlednou množinu axiómů pozůstávající ze čtrnácti tvrzení. Můžeme tedy říct, že právě toto je rovněž jedna z okolností, které dělají z logiky přitažlivou disciplinu, a logiku v širším slova smyslu můžeme charakterizovat také jako vědu o vytváření teorií. Formalizovanými teoriemi a jejich vlastnostmi se zabývá kapitola 4. tohoto textu.


2. Výroková logika
2.1. Sémantický výklad výrokové logiky.
Výroková logika analyzuje věty až do úrovně elementárních výroků. Strukturu těchto elementárních výroků již dále nezkoumá. Přitom
Výrok je tvrzení, o němž má smysl prohlásit, zda je pravdivé či nepravdivé.
Tato „definice“ se zdá být až banální, pokud si neuvědomíme, že ne každá věta vyjadřuje výrok. Např. věta Francouzský král je holohlavý nemůže být v současné době (kdy neexistuje francouzský král) ani pravdivá, ani nepravdivá. Kdyby totiž nastal jeden z těchto případů, vyplývala by z ní existence francouzského krále! Klasická výroková logika tedy ctí princip dvojhodnotovosti ( tercium non datur – Chrisipos ze Solov).
Výroky dělíme na jednoduché a složené. Jednoduchý výrok je takové tvrze ní, jehož žádná vlastní část již není výrokem. Složený výrok pak má vlastní části – výroky. Výroková logika zkoumá strukturu těchto složených výroků v tom smyslu, že zkoumá způsob skládání jednoduchých výroků do složených pomocí logických spojek. Je to ted y teorie logických spojek. Přitom ovšem zachovává žádoucí princip skladebnosti (kompozicionality), podle něhož je pravdivostní hodnota složeného výroku jednoznačně určena jen pravdivostními hodnotami jeho složek a povahou spojení těchto složek (tj. logickou povahou spojek).
Příklad. Složené výroky.
V Praze prší a v Brně je hezky.

el. výrok el. výrok
spojka

Není pravda, že v Praze prší.

spojka el. výrok

Jazyk výrokové logiky musí proto o bsahovat symboly zastupující jednotlivé elementární výroky (tzv. výrokové symboly (proměnné), které budou nabývat hodnot pravda, nepravda), symboly pro logické spojky a případné pomocné symboly.
Definice 2.1.1:
Abeceda jazyka výrokové logiky je množina ná sledujících symbolů:
Výrokové symboly: p, q, r, ... /případně s indexy/
Symboly log. spojek /funktorů/: , , , ,
Pomocné symboly /z ávorky/: (, ) /případně [,], , /
Symboly , , , , nazýváme po řadě funktory negace , disjunkce , konjunkce , implikace , ekvivalence .
Gramatika jazyka výrokové logiky rekurzivně definuje formule :
(1) Výrokové symboly jsou formule /báze definice/.
(2) Jsou-li výrazy A, B formule, pak jsou formulemi i výrazy
A , A B , A B , A B , A B
/indukční krok definice/.
(3) Jiných formulí výrokové logiky, než podle bodů (1), (2 ) není
/uzávěr definice/.
Jazyk výrokové logiky je množina všech formulí výrokové logiky.
Formule vzniklé podle bodu (1) nazýváme elementárními /atomárními , primitivními/ formulemi , formule vzniklé podle bodu (2) složenými formulemi . Formule A, B jsou bezprostředními podformulemi formulí . Maximální počet do sebe vnořených závorkových dvojic , vyskytujících se ve formuli udává /hierarchický/ řád formule .

Poznámky 2.1.1:
1. Symboly A, B použité v indukčním kroku definice nejsou formulemi /nevyskytují se jako symboly v abecedě jazyka/, ale metasymboly sloužící k označení formulí.
2. Používání závorek v zápisu formulí můžeme omezit přijetím následujících konvencí:
Složenou formuli nejvyššího řádu netřeba závorkovat.
Logické spojky uspořádáme do prioritní stupnice , , , , . Ze dvou funktorů váže silněji ten, který je v uvedené stupnici umístěn více vlevo.
Pozn. : Tuto konvenci však příliš „nezneužíváme“ a závorky raději použijeme vždy, když chceme vyznačit strukturu formule.
V případě, že o prioritě vyhodnocení nerozhodnou ani závorky ani prioritní stupnice, vyhodnocujeme formuli zleva doprava. Tak např. formuli p q r s vyhodnocujeme tak, jakoby byla zapsána ((p q) r) s.
U vícečlenných konjunkcí nebo disjunkcí není třeba (vzhledem k jejich asociativitě - viz dále) uvádět závorky, tj. např. místo p q r nebo p q r lze psát pouze p q r. Tato kon vence souvisí s předchozí konvencí (na pořadí vyhodnocování nezáleží a tedy lze standardně vyhodnocovat zleva doprava).
3. Symbolika není v literatuře jednotná. Následující tabulka udává alternativní značení spojek:

Symbol pro spojku Alternat. Symboly & , ,
Příklad 2.1.1:
Následující posloupnost formulí ilustruje postup konstrukce složené formule podle bodů (1) a (2). V prvém sloupci je zobrazen postup konstrukce složené formule striktně podle definice a v druhém s maximálním využitím konvencí šetřících závorky. V třetím sloupci je uveden hierarchický řád formulí uvedených v daném řádku.




Podle definice S využitím konvencí Hier.řád p, q p, q 0 ( p), ( q), (p q) p, q, p q 1 (( p) ( q)), ( (p q)) p q, (p q) 2 ((( p) ( q)) ( (p q))) p q (p q) 3 Definice 2.1.2:
Pravdivostní ohodnocení (valuace) výrokových symbolů je zobrazení v , které ke každému výrokovému symbolu přiřazuje pravdivostní hodnotu, tj. hodnotu z množiny 1,0 , která kóduje množinu pravd a, nepravda .
Pravdivostní ohodnocení všech výrokových symbolů jazyka definuje model jazyka výrokové logiky .
Pravdivostní funkce formule výrokové logiky je funkce w , která ke každému pravdivostnímu ohodnocení výrokových symbolů přiřazuje pravdivostní hodnotu celé formule. Tato hodnota je určena takto:
(1) Pravdivostní hodnota elementární formule je rovna pravdivostní hodnotě výrokového symbolu, tj.
w p = v p pro všechny výrokové proměnné p.
(2) Jsou-li dány pravdivostní funkce formulí A, B, pak pravdivostní funkce formulí A, A B, A B, A B, A B jsou dány následující tabulkou 2.1:

w (A) w (B) w ( A) w (A B) w (A B) w (A B) w (A B) 1 1 0 1 1 1 1 1 0 0 0 1 0 0 0 1 1 0 1 1 0 0 0 1 0 0 1 1
Tab. 2.1.
Převod z přirozeného jazyka do symbolického ja zyka výrokové logiky:
Výrokově logická analýza.
Analýza na základě výrokové logiky nám umožňuje studovat strukturu vět z hlediska skládání jednoduchých výroků do složených výroků pomocí logických spojek. Elementární výroky zde považujeme za nestrukturované „cihly“, které skládáme do strukturovaných bloků. Elementární výroky vstupují do spojení jen svou pravdivostní hodnotou a jsou navzájem zcela nezávislé. V dané větě proto označíme jednotlivé elementární výroky různými výrokovými symboly a místo spojek př irozeného jazyka použijeme odpovídající výrokové symboly pro spojky.
Výrokové spojky jsou zpřesněnou analogií příslušných spojek přirozeného jazyka (zejména v případě disjunkce a implikace), a to:
1. Spojka negace odpovídá „ není pravda, že “
Je to uná rní spojka, nespojuje dva výroky.
Příklad: „Není pravda, že Praha je velkoměsto“ (analyzujeme ) p
2. Spojka konjunkce odpovídá „ a “
Je to binární, komutativní sp