1 Vyjadrovanı v matematice

1.1 Uvod

Vyjadřuje-li matematik (automechanik, zeměměřič, kuchařka, matematickýstatistik apod.) svoje myšlenky, činí tak pomocí jistého jazyka. Můžeme mlu-vit o jazyku matematiky (automechaniků, zeměměřičů, kuchařek, matematickéstatistiky, kuchařek apod.). Každý z nich má k dispozici zásobu „slov�, z nichžpomocí jistých skladebních pravidel (syntaktických pravidel) skládá „věty�. Slovamají svůj význam a k tomu je také třeba při sestavování věty přihlížet (séma-nická pravidla). Tyto jazyky jsou obvyle součástí jazyka „nadřazeného�, v Českuobvykle jazyka českého.Slova užíváme k označování určitých věcí nebo témat. Vztah slova a věci je

zprostředkován pojmem. Někdy se hovoří o „sémantickém trojúhelníku�:

pojem

���

����

��

��

��

��

slovo (symbol) věc (předmět, téma)

Pojem lze vymezit buď definicí, jež určí nutné specifické vlastnosti, anebovýčtem všech předmětů, které pod tento pojem spadají. Rozlišujeme (1) intenzipojmu (z lat. intendo, napřahuji, mířím), neboli význam pojmu (Bertrand Rus-sell) či jeho obsah – to, co se pojmem míní a (2) extenzi pojmu (z lat. extendo,rozpínám, rozpřahuji) neboli rozsah pojmu – souhrn všech věcí, jež pod tentopojem spadají.Bez pojmů není žádné poznání možné. Ludwig Wittgenstein1) v díle Tracta-

tus Logico-Philosophicus tvrdí: „Hranice mého jazyka znamenají hranice méhosvěta.� „O čem nelze mluvit, o tom se musí mlčet.�

1)Ludwig Josef Johann Wittgenstein [vitg(e)nštajn] (26. 4. 1889 – 29. 4. 1951), rakouskýtechnik, matematik, filosof. Roku 1922 vydal Logisch-philosophische Abhandlung (TractatusLogico-Philosophicus), kde, podle svého názoru, vyřešil všechny problémy filosofie a stáhl sedo ústraní. V roce 1929 se vrátil do Cambridge na Trinity College, roku 1939 se zde stal pro-fesorem. V letech 1947–1949 napsal většinu materiálu později vydaného jako PhilosophischeUntersuchungen (Philosophical Investigations).

3

Z pojmů sestavujeme soudy a ze soudů úsudky. Veškeré prostředky sloužícík vyjadřování, sdělování myšlenek, tj. soudy a úsudky, tvoří jazyk.

K přesnému vymezení jakéhokoliv jazyka je třeba stanovit (1) slovník přísluš-ného jazyka (množina přípustných slov), (2) pravidla umožňující vytváření složi-tějších výrazů (syntaktická pravidla), (3) význam užívaných výrazů (sémantickápravidla).

1.2 Usudky

Úsudkem nazveme neprázdnou konečnou posloupnost jazykových výrazů, kterévyjadřují jednotlivé myšlenky procesu usuzování – posloupnosti na sebe navazu-jících souvisejících myšlenek, vedoucích k jistému závěru.Úsudky můžeme rozdělit na deduktivní a nededuktivní (pravděpodobnostní,

při splnění předpokladů nemusí závěry platit).

Definice 1. Úsudek je logicky správným deduktivním úsudkem tehdy, když vždy,jsou-li pravdivé všechny předpoklady, je pravdivý i závěr. U logicky správnéhodeduktivního úsudku hovoříme o tom, že závěr úsudku vyplývá (plyne nutně)z předpokladů úsudku. (Nemůže nastat případ, že by všechny předpoklady bylypravdivé a přitom byl závěr úsudku nepravdivý.)

K deduktivním úsudkům patří:

Modus ponens:A1 : Jestliže X, pak YA2 : (platí) XB1 : (musí platit) Y

Úsudek úplnou indukcí (pro konečné množiny):

A1 : A = {a1, a2, . . . , an} – konečná, málo početnáA2 : V(a1) – tj. a1 má vlastnost V...An+1 : V(an)B1 : ∀x ∈ A : V(x) (vlastnost V mají všechny prvky A)Úsudek matematickou indukcí:A1 : Platí princip matematické indukceA2 : Dokážeme, že zkoumanou vlastnost má číslo 1A3 : Platí, že má-li zkoumanou vlastnost libovolné n, má ji také n+ 1B1 : Zkoumanou vlastnost má každé přirozené čísloK nededuktivním úsudkům patří:

Úsudek neúplnou indukcí:Je dána neprázdná základní množina A = {a1, a2, . . . , an, . . . }. Zjistíme, že

pro prvky a1, a2, . . . , an platí jistá vlastnost V (symbolicky V(a1), . . . ) a usuzu-jeme, že také platí V(an+1),V(an+2), . . . Tedy i zbývající prvky množiny A mají

4

vlastnost V.A1 : A = {a1, a2, . . . , an, . . . }A2 : V(a1)...An+1 : V(an)B1 : ∀x ∈ A : V(x) – hypotéza

Úsudek neúplnou indukcí má zásadní význam pro přírodní i společenské vědy.Je nezastupitelný. Slouží k formulaci hypotéz. Jejich dokazování je pak úlohoulogiky.

Úsudek z analogie: Je dán objekt a, jehož vlastnosti „známe�. U objektu b zjis-tíme, že má některé ze známých vlastností objektu a. Usuzujeme, že by mohl míti další vlastnosti shodné s objektem a.

A1 : V1(a)...An : Vn(a)An+1 : V1(b)...An+k : Vk(b) k < nB1 : ∀i ∈ {1, 2, . . . , k, . . . , n} : Vi(b)

Úsudky neúplnou indukcí a z analogie mají zásadní význam pro přírodní i spole-čenské vědy. Slouží k formulaci hypotéz. Jejich dokazování je pak úlohou logiky.

1.3 Konstanty a promenne

V každém jazyku najdeme symboly, které už v rámci daného jazyka dále nedě-líme (např. =, !, x, 3, ≥, +), jednotlivá slova (Olomouc, Morava) atd. Těmto sym-bolům říkáme jednoduché jazykové výrazy, symbolům složeným aspoň ze dvoujednoduchých říkáme složené jazykové výrazy (XY , 5 = 4 + 1, 22, 6!, Olomoucje na Moravě, bod A leží na přímce p atd.).

Ukázka 1.x−+=y−==z−

každé přirozené číslo

3=+=2===9=

6=<=5=

Praha je nějaké město v Čechách.

V ukázce se vyskytují dva typy jazykových výrazů – jedny označují právějeden objeky, druhé označují libovolný objekt z jakési množiny – budeme jimříkat konstanty a proměnné .

5

Konstanta je jazykový výraz, který označuje právě jeden objekt. Objek ozna-čený konstantou nazveme denotát (designát) konstanty.

Ukázka 2. <, −55, +, nejmenší prvočíslo, Ludolfovo číslo �, =, ≈, Praha hl. n.,Univerzita Palackého,

√3 · 123, Jan Novák, bytem Lhotka 56

Ukázka 3.1. Olomouc je město, kde sídlí Univerzita Palackého.2. Olomouc je město uprostřed Moravy, ležící na řece Moravě.3. 25, 52, dvacet pět, druhá mocnina pěti, pět na kvadrát, 28− 3, XXV.Zatímco konstanta Olomouc v první i druhé větě má týž denotát, výraz Mo-

rava v druhé větě označuje pokaždé jiný objekt. Všechny konstanty ve třetí větěoznačují sice stejný objekt, ale je „ jistý rozdíl� např. mezi výrazy „dvacet pět�a „druhá mocnina pěti�. Člověk neznalý mocnin nemusí vědět, že výraz „druhámocnina pěti� označují stejný objekt jako „dvacet pět�. (Výrazy „25� a „dvacetpět� by ho do rozpaků uvést neměly.) Konstantu tedy nelze jednoznačně cha-rakterizovat pouze jejím denotátem. Konstanty se stejným denotátem se v přiro-zeném jazyku liší něčím, co nazýváme „smysl� konstanty. Smysl nelze, podobnějako např. množinu nebo přímku, explicitně definovat. Lze se pouze pokusit tentopojem co nejvíce ozřejmit:

G. Frege: Smysl daného jazykového výrazu je to co víme, když víme, co danýjazykový výraz znamená.

Definice 2. Jazykový výraz nazveme konstantou, má-li v daném jazyku1) právě jeden denotát,2) právě jeden smysl.

Konstanta je tedy určena trojcí (jméno, denotát, smysl). Jméno konstantyK je jazykový výraz, denotát D je popisovaná realita, smysl S je myšlenkovákategorie.

Definice 3. Jakýkoliv jazykový výraz, když neoznačuje právě jeden objekt, alepodle potřeby může označit libovolný objekt z nějaké aspoň dvouprvkové mno-žiny, nazveme proměnnou. Množinu objektů, které proměnná může označovat,nazveme oborem proměnnosti dané proměnné.

Proměnná nemá denotát, její obor proměnnosti vymezuje množinu možnýchdenotátů. O smyslu proměnné nelze hovořit, proměnné nepřiřazujeme žádný vý-znam. K jednoznačnému určení proměnné stačí uvést pouze její obor proměnnosti.

Zásady užití proměnných

1. Za proměnnou lze dosadit libovolnou konstantu z jejího oboru proměnnostia to tak, že na všech výskytech dané proměnné ve výrazu dosadíme toužkonstantu.

6

2. Pokud to není výslovně zakázáno, lze za dvě různé proměnné, které majínedisjunktní obory proměnnosti, dosadit touž konstantu z jejich průnikuoborů proměnnosti.

3. Za danou proměnnou lze dosadit jinou proměnnou, případně celý složenývýraz, který má význam proměnné. Platí zde ale jisté omezující podmínky,např. záměnou se nesmí změnit obor proměnnosti.

1.4 Vyroky

Definice 4. Výrokem nazveme jakýkoliv jazykový výraz, o němž má smysl uva-žovat, zda je nebo není pravdivý.

Ukázka 4.1. Olomouc je město, kde sídlí Univerzita Palackého.2. Kolik je hodin?3. 25− x = 5, x ∈ R

4. 25− 10 = 55. Pojď sem!6. Možná půjdu do kina.7. Vesmír vznikl jako důsledek narušení vakua o vysoké hustotě energie.8. Martin šel na fotbal a Petra sedí před zrcadlem.9. Venku bude večer pršet.10. Jestliže venku prší, pak na houby nepůjdu.11. Exisuje pravoúhelník, který má strany shodné.12. Pro všechna reálná čísla x platí, že x2 ≥ 0.13. Věta, kterou právě říkám, je nepravdivá.

Je-li výrok pravdivý, říkáme, že jeho pravdivostní hodnota je 1. Je-li výroknepravdivý, říkáme, že jeho pravdivostní hodnota je 0.Všimneme-li si jazykových výrazů uvedených v ukázce, vidíme, že uvažovat

o jejich pravdivosti má smysl pouze v případech 1, 4, 6, 7, 8, 9, 10, 11 a 12.Otázky a příkazy nemohou být výroky. Výrokem není ani výraz 3, který obsahujeproměnnou.Výroky 11 a 12 obsahují proměnnou x a „pravoúhelník�. Tyto proměnné (na

rozdíl od proměnné x ve výroku 3) jsou tzv. vázány výrazem exisuje, resp. provšechna – mluvíme o vázané proměnné (na rozdíl od volné proměnné v 3). Tytozáležitosti studuje predikátová logika.Zajímavá je věta 13, která nemůže být ani pravdivá ani nepravdivá. Vztahuje

se sama k sobě a je typickou ukázkou toho, čemu se v logice musíme vyhnout.Samovztažné věty nebudeme za výroky považovat.

Příklad 1. V jednom městě žije holič, který holí všechny muže z městečka, kteříneholí sami sebe; a neholí ty, co se holí sami. Holí tento holič sám sebe nebo ne?

7

Definice 5. Jazykový výraz obsahující proměnné, který se stane výrokem, dosa-díme-li za tyto proměnné prvky z jejich oborů proměnnosti, se nazývá výrokováforma. Jazykový výraz obsahující proměnné, který se nestane výrokem, dosadíme-li za tyto proměnné prvky z jejich oborů proměnnosti, se nazývá názvová forma.

Výraz 3, který obsahuje proměnnou x, je tedy výrokovou formou, protože25− 3 = 5 je výrok. Výraz 25 ∗ x2 − 5, x ∈ R, který obsahuje proměnnou x, jenázvovou formou, protože 25∗72−5 není výrok. (Algebraické výrazy jsou názvovéformy.)Výroky 7 a 9 jsou zvláštní tím, že přestože má smysl uvažovat o jejich pravdi-

vosti, nejsme schopni hned rozhodnout, zda jsou nebo nejsou pravdivé. Takovýmvýrokům říkáme hypotézy.

Definice 6. Hypotézou nazveme výrok, jehož pravdivostní hodnotu neznáme.

Pravdivostní hodnotu hypotézy lze zjistit dodatečně. Pak říkáme, že hypotézabyla potvrzena (má-li pravdivostní hodnotu 1) nebo vyvrácena.

Ve výrocích 8 a 10 se vyskytují jazykové výrazy, které samy jsou výroky. Tyto„podvýroky� jsou spojeny jazykovými výrazy, kterým budeme říkat výrokovéspojky.

Jazykový výraz, který umožňuje spojovat výroky, přičemž vznikne opět výrok,tzv. složený výrok, se nazývá výroková spojka. Složený výrok obsahuje aspoň jednuvýrokovou spojku, tj. obsahuje souvislý jazykový výraz různý od daného výroku,jenž je sám výrokem (je složen z „jednodušších� výroků). Každý výrok, kterýnení složený, se nazývá jednoduchým výrokem.

Pravdivostní hodnota složeného výroku není dána „zvnějšku�, je určena prav-divostními hodnotami jednoduchých výroků, z nichž je složen, a použitými výro-kovými spojkami. (Nezajímá nás o čem předpoklady (výroky) hovoří, zajímá náspouze, zda jsou či nejsou pravdivé.) Z tohoto pohledu se výroková spojka jevíjako předpis, kterým pravdivostním hodnotám spojovaných výroků přiřadí jednuvýslednou pravdivostní hodnotu – je to pravdivostní (logická) funkce. Spojka takmůže být dána tabulkou, která všem možným kombinacím hodnot spojovanýchvýroků přiřadí hodnotu jednu, např. pravdivostní tabulkou.Nejdůležitější spojky klasické výrokové logiky:

Negace

Definice 7. Negací ¬ nazveme logickou funkci danou tabulkou:P ¬P1 00 1

Slovy: Negace uděluje výroku právě opačnou pravdivostní hodnotu.

8

Značení: ¬pČesky: Není pravda, že . . .

1. Spojku „Není pravda, že . . . � můžeme stručně vyjádřit slovem „ne. . . �. („Nenípravda, že prší.� „Neprší.�) Spojka nevystihuje zcela přesně jen vícenásobnénegace. („Není pravda, že nemohl nevidět tu pohromu.�)

2. Termín negace užíváme jako název pravdivostní funkce (nikoliv spojky) nebok označení výsledného výroku. Je možné říci, že „není pravda, že prší� jenegací výroku „prší�.

3. Věta „Výrok ‘prší’ je nepravdivý� není negací výroku „prší�. Je to výroko pravdivostní hodnotě výroku „prší�.

4. Negaci výroku lze vyjádřit i výrokem, který zahrnuje všechny zbývající mož-nosti, vylučující platnost negovaného výroku. Např. „Není pravda, že Karelje stejně vysoký jako Petr� je výrok rovnocený výrokům „Karel není stejněvysoký jako Petr� nebo „Karel je menší nebo větší než Petr�. Na použitípředpony „ne. . . � je třeba dávat dobrý pozor.

5. Negace může pomoci při rozhodování o tom, zda jazykový výraz je výrokem.Každý výrok musí mít negaci.

Disjunkce

Definice 8. Disjunkcí ∨ nazveme logickou funkci danou tabulkou:P Q P ∨Q1 1 11 0 10 1 10 0 0

resp.∨ 1 01 1 10 1 0

Slovy: Disjunkce je pravdivá, právě když je aspoň jeden z výroků pravdivý.

Značení: p ∨ q (jiné např.: p+ q)Česky: . . . nebo. . .

1. Slovní vyjádření „p nebo q� má v českém jazyku přinejmenším dva základnívýznamy:

a) Možnosti se nevylučují. Může nastat případ, že ph(p) = ph(q) = 1, tj.spojku „nebo� používáme v nevylučovacím smyslu – to odpovídá definici dis-junkce, např. „Koupím si pejska nebo kočičku.� (Pravidla českého pravopisunařizují před nevylučovacím nebo nepsát čárku.)

b) Možnosti se vylučují. (v pět hodin půjdu do kina, nebo na pojedu nakoncert.) Nesmí nastat případ, že ph(p) = ph(q) = 1, tj. spojku „nebo�používáme ve vylučovacím smyslu (pravidla českého pravopisu nařizují předvylučovacím nebo psát čárku). Vylučovací „nebo� raději vyjadřujeme spojkou„buď. . . , anebo�, resp. „buď. . . , nebo�.

9

2. Termín disjunkce užíváme jako název pravdivostní funkce (nikoliv spojky)nebo k označení výsledného výroku.

3. Disjunkce se nazývá též alternativa či logický součet (odtud p+ q). Z tabulkyje vidět, že disjunkce je komutativní.

4. Užíváme i tzv. zobecněnou disjunkci : „platí aspoň jedna z uvedených mož-ností�.

Konjunkce

Definice 9. Konjunkcí ∧ nazveme logickou funkci danou tabulkou:P Q P ∧Q1 1 11 0 00 1 00 0 0

resp.∧ 1 01 1 00 0 0

Slovy: Konjunkce je pravdivá, právě když jsou oba výroky pravdivé.

Značení: p ∧ q (jiné např.: p · q)Česky: . . . a zároveň. . .

1. Kromě vyjádření „p a zároveň q� se velmi často používá i kratší verze „p aq�. Analogický význam mají i spojky: i, a současně.

Uvedené spojky vystihují konjunkci dosti přesně, jako obvykle však majív českém jazyku i jiný význam. Potíže činí obzváště krátká verze „a�. Např.:„Vstoupil dovnitř a pověsil klobouk na lustr� – zde je spojkou „a� vyjádřenačasová následnost, spojka není komutativní. „Byla chytrá a hezká� také zna-mená něco jiného než „Byla hezká a chytrá�. Výraz „a� také nemusí spojovatvýroky: „Petra a Andula se vzájemně podobají� – zde se jedná o jednodu-chý výrok, nemá smysl věta „Petra se vzájemně podobá� nebo „Andula sevzájemně podobá�. Výraz „a� se někdy užívá i v jiném významu: „Vlak ne-jede v neděli a ve svátek�, „Kočkám a psům vstup zakázán� – neexistujenedělosvátek nebo kočkopes, spojka v tomto případě vyjadřuje disjunkci.

2. Termín konjunkce užíváme jako název pravdivostní funkce (nikoliv spojky)nebo k označení výsledného výroku.

3. Konjunkce se nazývá též logický součin (odtud p · q). Z tabulky je vidět, žekonjunkce je komutativní.

4. Užíváme i tzv. zobecněnou konjunkci : „platí současně�. Aby byla zobecněnákonjunkce pravdivá, musí být všechny výroky pravdivé.

10

Implikace

Definice 10. Implikací ⇒ nazveme logickou funkci danou tabulkou:P Q P ⇒ Q1 1 11 0 00 1 10 0 1

resp.⇒ 1 01 1 00 1 1

Slovy: Implikace je nepravdivá, právě když „nepravda� implikuje „pravdu�.

Značení: p⇒ q (jiné např.: p→ q)

Česky: Jestliže. . . , pak. . .

1. Z tabulky je vidět, že implikace není komutativní. Proto ve výroku p ⇒ qrozlišujeme mezi p a q. Výrok p se nazývá předpoklad (antecedent) a výrok qse nazývá tvrzení (konsekvent).

Je-li předpoklad nepravdivý, je implikace pravdivá. Je-li tvrzení pravdivé, jeimplikace pravdivá.

2. Zatímco spojka „nebo� poměrně přesně vystihovala disjunkci a spojka „a�konjunkci, nemá český jazyk (ani anglický) vhodnou spojku, která by vyjad-řovala implikaci tak, jak je definována. Proto z nedostatku vhodných spojekužíváme spojku „jestliže. . . , pak. . . �, resp. její analogie „ je-li. . . , pak. . . �,„když. . . , pak. . . �. Všechny tyto spojky mají základní nevýhodu, poukazujítotiž na určitou souvislost tvrzení s předpokladem.

Další problém činí řádek 3 definiční tabulky ph(0⇒ 1) = 1. Řádky 1 a 2 jsoupro spojku „jestliže . . . , pak . . . � zřejmé. Stejně tak řádek 4 (ph(0⇒ 0) = 1).Např. výrok „jestliže to dokážeš, pak sním svůj klobouk� se považuje zapravdivý, když on to nedokázal a já svůj klobouk nesnědl. Řádek 3 ovšempožaduje, aby tento výrok platil, když on to nedokázal a já svůj klobouksnědl (!).

Prvním řešením těchto problémů je užívání výrazu „implikuje� pro vyjádřeníimplikace nebo v chápání spojky „jestliže . . . , pak . . . � ve významu danémtabulkou implikace, i když se nám to nelíbí. V tomto případě můžeme snadnodefinovat „vyplývání� jako pravdivou implikaci. Každé vyplývání je pak im-plikací, nikoliv obráceně.

Z tabulky implikace vidíme, že je-li pravdivá implikace i předpoklad, nutněmusí tvrzení platit, pravdivost předpokladu k tomu postačuje, ale není nutnéaby předpoklad platil – řádky 1 (postačuje) a 3 (není nutné) v tabulce, řádky2 (neplatí implikace) a 4 (neplatí předpoklad) neuvažujeme. Je-li pravdiváimplikace i tvrzení, může i nemusí předpoklad platit – řádky 1 a 3 (nepo-stačuje) – ale je-li implikace pravdivá a tvrzení nepravdivé, pak předpokladneplatí – řádek 4 (je tedy nutná).

11

Například: „Jestliže prší, pak jsou na obloze mraky.� K tomu, aby na oblozebyly mraky postačuje, aby pršelo. K tomu aby pršelo je nutné, aby na oblozebyly mraky, ale nestačí to.

2. Termín implikace užíváme jako název pravdivostní funkce (nikoliv spojky)nebo k označení výsledného výroku.

3. Užíváme následující terminologii:

p⇒ q – implikaceq ⇒ p – implikace obrácená¬q ⇒ ¬p – implikace obměněná

4. Je-li p⇒ q pravdivá, říkáme, že z p logicky vyplývá q.

Je-li p⇒ q pravdivá a zároveň q ⇒ p pravdivá, říkáme, že p a q jsou logickyekvivalentní.

Ekvivalence

Definice 11. Implikací ⇔ nazveme logickou funkci danou tabulkou:P Q P ⇔ Q1 1 11 0 00 1 00 0 1

resp.⇔ 1 01 1 00 0 1

Slovy: Ekvivalence je pravdivá, mají-li oba výroky stejnou pravdivostní hodnotu.

Význam: Ekvivalence vyjadřuje logickou rovnocennost ve výrokové logice.

Značení: p⇔ q (jiné např.: p ≡ q, p↔ q)

Česky: . . . , právě když. . .

1. Kromě vyjádření „p, právě když q� se často používá „p je ekvivalentní q�,„p tehdy a jen tehdy, když q�, „ jestliže p, pak q a naopak�.

2. Termín ekvivalence užíváme jako název pravdivostní funkce (nikoliv spojky)nebo k označení výsledného výroku.

3. Z tabulky je vidět, že ekvivalence je komutativní.

4. Později dokážeme, že p⇔ q je ekvivalentní (p⇒ q) ∧ (q ⇒ p). Můžeme tedyekvivalenci definovat pomocí implikace a konjunkce – ekvivalence je druhotnáspojka.

5. Existuje-li mezi výroky p a q souvislost a p⇔ q je pravdivá, potom pravdivostp se nazývá podmínka nutná a postačující pro pravdivost q, viz tabulka. Stejnětak, vzhledem ke komutativitě ekvivalence, je pravdivost q podmínka nutná apostačující pro pravdivost p.

7. Je-li p⇔ q pravdivá, říkáme, že p a q jsou logicky ekvivalentní.

12

System vsech jednoargumentovych pravdivostnıch funkcı

P Φ11 Φ12 Φ13 Φ141 1 1 0 00 1 0 1 0verum opakování negace falzumP ⇒ P P ¬P ¬(P ⇒ P )¬P ∨ P P ∨ P ¬¬¬P P ∧ ¬P

P ∧ P

System vsech dvouargumentovych pravdivostnıch funkcı

P Q Φ21 Φ22 Φ

23 Φ

24 Φ

25 Φ

26 Φ

27 Φ

28 Φ

29 Φ

210 Φ

211 Φ

212 Φ

213 Φ

214 Φ

215 Φ

216

1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 01 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 00 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 00 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0

Φ21 – verum dvouargumentové, true (dvouargumentové)

Φ22 – disjunkce

Φ23 – obrácená implikace (Q implikuje P )

Φ24 – druhé opakování P

Φ25 – implikace (P implikuje Q)

Φ26 – druhé opakování Q

Φ27 – ekvivalence

Φ28 – konjunkce

Φ29 – antikonjunkce, Sheffer (Shefferův operátor)

Φ210 – antivalence

Φ211 – druhé opakování ¬QΦ212 – antiimplikace, inhibice (nemá českou spojku)

Φ213 – druhé opakování ¬PΦ214 – obrácená inhibice

Φ215 – antidisjunkce, Peircův operátor

Φ216 – falzum dvouargumentové, false (dvouargumentové)

1.5 Slozene vyroky

Dohodneme se, že složené výroky budeme zapisovat analogicky jako matema-tické výrazy, např.:

((a ∨ b ∧ c)⇒ c)⇔ (a⇒ ¬c)

13

1.5.1 Vyhodnocovanı formulı

Složený výrok (formule) je složen jen z konečného počtu jednoduchých výrokůspojených výrokovými spojkami Máme-li zjistit, co je daný složený výrok zač,stačí ho prozkoumat pro všechny možné pravdivostní hodnoty v něm se vyskytu-jících jednoduchých výroků, zastoupených obvykle symboly a, b, c atd. A těchto„všech možných pravdivostních hodnot� je pro n proměnných jenom 2n.Pro lepší přehlednost můžeme zaznamenat hodnoty proměnných, podformulí

zkoumané formule i formule samotné do tabulky.

Příklad 2. Rozhodněte o pravdivosti formule

ϕ = (C ∧ (A⇒ B))⇔ ((C ∧ ¬A) ∨ (C ∧ B)).

Řešení:

A B C ¬A A⇒ B C ∧ (A⇒ B) (C ∧ ¬A) (C ∧B) (C ∧ ¬A) ∨ (C ∧B) ϕ1 1 1 0 1 1 0 1 1 11 1 0 0 1 0 0 0 0 11 0 1 0 0 0 0 0 0 11 0 0 0 0 0 0 0 0 10 1 1 1 1 1 1 1 1 10 1 0 1 1 0 0 0 0 10 0 1 1 1 1 1 0 1 10 0 0 1 1 0 0 0 0 1

Zkoumaná formule je vždy pravdivá, je to tzv. tautologie (logický zákon).

Příklad 3. Rozhodněte o pravdivosti formule A⇒ (B ⇒ A).

Řešení: Vyplníme tabulku

A B B ⇒ A A⇒ (B ⇒ A)1 1 1 11 0 1 10 1 0 10 0 1 1

Zkoumaná formule je vždy pravdivá.

Nabudeme-li s vyhodnocovíním formulí zkušenosti, není třeba uvádět podfor-mule. Tabulku není ani nutné vyplňovat úplně, lze využít znalostí o pravdivost-ních funkcích.

Příklad 4. Rozhodněte o pravdivosti (C ∧ (A⇒ B))⇒ ((C ∧A)⇒ (C ∧B)).

14

Řešení:A B C (C ∧ (A⇒ B)) ⇒ ((C ∧ A) ⇒ (C ∧ B))1 1 1 1 1 1 1 1 1 11 1 0 0 0 11 0 1 1 0 0 11 0 0 0 0 10 1 1 1 1 1 1 0 10 1 0 0 0 10 0 1 1 1 1 1 0 10 0 0 0 0 1

Zkoumaná formule je vždy pravdivá, je to tzv. tautologie (logický zákon).

V příkladu jsme použili tzv. tabulkovou metodu, která také umožňuje vždyrozhodnout o správnosti úsudku výrokové logiky, tj. zda je daný úsudek logickysprávným deduktivním úsudkem.

Příklad 5. Rozhodněte o správnosti úsudku:

X ⇒ YXY

Řešení: Vyplníme tabulku

X Y X X ⇒ Y1 1 1 1 •1 0 1 00 1 0 10 0 0 1

Oba předpoklady úsudku jsou splněny pouze v prvním řádku tabulky, kde nabýváY hodnotu 1, tedy tento úsudek je logicky správným deduktivním úsudkem.

Tabulková metoda slouží také k hledání neznámých pravdivostních hodnotvýrokových proměnných.

Příklad 6. Víme, že platí (A ∨B)⇒ ¬C a (A ∧ ¬C)⇔ B. Máme zjistit, jakétrojce hodnot může trojce proměnných (A,B,C) nabývat.

Řešení: Vyplníme tabulku úsporným způsobem (zjistíme-li, že některý z výrokůneplatí, nemusíme v příslušném řádku dál pokračovat).

15

A B C (A ∨ B) ⇒ ¬C (A ∧ ¬C) ⇔ B1 1 1 1 0 01 1 0 1 1 1 1 11 0 1 1 0 01 0 0 1 1 1 1 00 1 1 1 0 00 1 0 1 1 1 0 00 0 1 0 1 0 0 10 0 0 0 1 1 0 1

Z tabulky vidíme, že oba výroky platí pro trojice (1, 1, 0), (0, 0, 1) a (0, 0, 0).

1.5.2 Tautologie

Představíme si nyní některé logické zákony.

a) základní zákony klasické výrokové logiky

1. Tranzitivita implikace: ((ϕ⇒ ψ) ∧ (ψ ⇒ χ))⇒ (ϕ⇒ χ)

2. Hypotetický sylogismus: (ϕ⇒ ψ)⇒ ((ϕ⇒ ψ)⇒ (ϕ⇒ ψ))

3. Zákon kontrapozice (transpozice): (ϕ⇒ ψ)⇔ (¬ψ ⇒ ¬ϕ)4. Zákon vyloučení třetí možnosti (tercium non datur): ϕ ∨ ¬ϕNěkteří logikové nepovažují tuto formuli za tautologii, ale jen za splnitelnouformuli. Pro konečné množiny formulí platí, ale pro nekonečné množiny?Pak také samozřejmě neuznávají důkaz sporem.

5. Zákon sporu: ¬(ϕ ∧ ¬ϕ)Kdyby tento zákon neplatil, mohl by mít výrok současně dvě pravdivostníhodnoty. Pro teorii, v níž platí ϕ a současně ¬ϕ, to znamená katastrofu, jetzv. sporná.

6. Zákon dvojí negace: (¬¬ϕ)⇔ ϕ

b) algebraicko-logické zákony klasické výrokové logiky

7. Komutativitakonjunkce: (ϕ ∧ ψ)⇔ (ψ ∧ ϕ)disjunkce: (ϕ ∨ ψ)⇔ (ψ ∨ ϕ)ekvivalence: (ϕ⇔ ψ)⇔ (ψ ⇔ ϕ)

8. Asociativitakonjunkce: (ϕ ∧ (ψ ∧ χ))⇔ ((ϕ ∧ ψ) ∧ χ)disjunkce: (ϕ ∨ (ψ ∨ χ))⇔ ((ϕ ∨ ψ) ∨ χ)ekvivalence: (ϕ⇔ (ψ ⇔ χ))⇔ ((ϕ⇔ ψ)⇔ χ)

16

9. Distributivita∨ vzhledem k ∧: (ϕ ∨ (ψ ∧ χ))⇔ ((ϕ ∨ ψ) ∧ (ϕ ∨ χ))∧ vzhledem k ∨: (ϕ ∧ (ψ ∨ χ))⇔ ((ϕ ∧ ψ) ∨ (ϕ ∧ χ))implikace: (ϕ⇒ (ψ ⇒ χ))⇔ ((ϕ⇒ ψ)⇒ (ϕ⇒ χ))

10. de Morganův zákon prokonjunkci: ¬(ϕ ∧ ψ)⇔ (¬ϕ ∨ ¬ψ)disjunkci: ¬(ϕ ∨ ψ)⇔ (¬ϕ ∧ ¬ψ)c) zákony postihující vlastnosti implikace

11. Zákon Dunse Scota: (ϕ ∧ ¬ϕ)⇒ ψ

Kontradikce je explozivní, implikuje cokoliv.

12. Zákon odloučení (modus ponens): ((ϕ⇒ ψ) ∧ ϕ)⇒ ψ

13. Zákon zjednodušení (simplifikace): ϕ⇒ (ψ ⇒ ϕ)

14. Zákon totožnosti: ϕ⇒ ϕ

Tento zákon ukazuje základní vlastnost každého logického zákona, a sice ženepřináší nic zásedně nového.

d) zákony charakterizující ekvivalenci:

15. Antisymetrie implikace: ((ϕ⇒ ψ) ∧ (ψ ⇒ ϕ))⇔ (ϕ⇔ ψ)(zákon ekvivalence)

16. Tranzitivita ekvivalence: ((ϕ⇔ ψ) ∧ (ψ ⇔ χ))⇔ (ϕ⇔ χ)

17. Zákon negování ekvivalence: (ϕ⇔ ψ))⇔ (¬ϕ⇔ ¬ψ)e) další zákony vyjadřující vztah mezi logickými funkcemi:

18. Vztah implikace a disjunkce: (ϕ⇒ ψ)⇔ (¬ϕ ∨ ψ)19. Vztah implikace a konjunkce (negace implikace): ¬(ϕ⇒ ψ)⇔ (ϕ ∧ ¬ψ)20. (ϕ ∨ ψ)⇔ ((ϕ⇒ ψ)⇒ ψ)

vzhledem ke komutativitě disjunkce: (ϕ ∨ ψ)⇔ ((ψ ⇒ ϕ)⇒ ϕ)

Na základě známých tautologií a věty o nahrazení můžeme s formulemi na-kládat obdobně jako s algebraickými výrazy v matematice.

17

1.6 Kvantifikatory

Z výrokové formya+ b = 5, a, b ∈ R

se může stát výrok, dosadíme-li za proměnnou prvek jejího oboru proměnnosti

2.14 + 7.3 = 5

nebo vázáním proměnné tím, že k ní vztáhneme údaj o počtu, tzv. kvantifikátor.

ke každému a ∈ R existuje b ∈ R tak, že a + b = 5.

Standardní interpretace a čtení:(∀x)(P (x)) – pro každé x (ze základní množiny) platí P (x), (pro všechna x,

pro libovolné x, pro jakékoliv x).(∀x)(¬P (x)) – pro žádné x (ze základní množiny) neplatí P (x) (neříkáme

„pro každé x neplatí P (x)�).V hovorové řeči často nebývá kvantifikátor uveden: Ryba je obratlovec. (Každá

ryba je obratlovec.)

(∃x)(P (x)) – existuje (aspoň jedno) x (z neprázdné základní množiny), prokteré platí P (x). Nevylučujeme tím ale, že to platí pro všechna x.

Pro negování výrazů s kvantifikátory platí DeMorganovy zákony:I. ¬((∀x) (P (x))) ⇐⇒ (∃x) (¬P (x))II. ¬((∃x) (P (x))) ⇐⇒ (∀x) (¬P (x))Číselné kvantifikátory nelze negovat „mechanicky�. Pomáháme si graficky čí-

selnou poloosou nezáporných celých čísel. Negace musí zahrnovat všechny zbýva-jící možnosti:

¬ nejvýš n ⇐⇒ aspoň n+ 1¬ aspoň n ⇐⇒ nejvýš n− 1

18

Příklady k přednášce 1

1. Rozhodněte, zda se jedná o výroky, své rozhodnutí zdůvodněte:

1. Dnes je středa.

2. Některé květiny mají žluté květy.

3. Po silnici jede červené auto.

4. Zítra je neděle.

5. Trojúhelník je pravoúhlý.

6. 10 � 357. Přímky jsou rovnoběžné.

8. Kolik je hodin?

9. x < 4

10. Dvě přímky nakreslené na tabuli jsou rovnoběžné.

11. Na Marsu existoval život.

12. Pojď sem!

13. Narýsuj trojúhelník, jsou-li dány jeho strany.

14. 11 > 12

15. Sousední strany pravoúhelníka jsou shodné.

16. Daný pravoúhelník má strany shodné.

17. Exisuje pravoúhelník, který má strany shodné.

18. Žádný pravoúhelník nemá strany shodné.

19. (x+ 1)2 = x2 + 2x+ 1

20. Stříhali dohola malého chlapečka.

2. Rozhodněte, ve kterých dvojicích jde o výrok a jeho negaci:

1. Dnes je sobota. – Dnes je neděle.

2. Máme psa. – Máme křečka.

3. Máme dobrmana – Máme labradora.

4. Dané dvě přímky v rovině jsou rovnoběžné. – Dané dvě přímky v rovinějsou různoběžné.

5. Dané dvě přímky v prostoru jsou rovnoběžné. – Dané dvě přímkyv prostoru jsou různoběžné.

6. Dané číslo je záporné. – Dané číslo je kladné.

7. Dané přirozené číslo je prvočíslo. – Dané přirozené číslo je číslo složené.

8. Prší. – Neprší.

9. Prší a sněží. – Neprší a nesněží.

19

3. Zformulujte co nejstručněji negaci následujících výroků:

1. Otec je starší než matka.

2. Číslo 7 se rovná číslu 8.

3. Večer půjdu do divadla.

4. Stůl má čtyři nohy.

5. Čert nikdy nespí.

6. Vltava teče přes Prahu.

7. 11 > 12

8. Daný pravoúhelník má strany shodné.

9. Exisuje pravoúhelník, který má strany shodné.

10. Žádný pravoúhelník nemá strany shodné.

11. Není pravda, že neovládám logiku.

4. Víte-li, že v označuje výrok „Byl tady Vilém�, h označuje výrok „Byl tadyHynek� a j označuje výrok „Byla tady Jarmila�, co znamená:

1. (v ∧ j) ∨ (h ∨ ¬j)2. v ⇒ j

3. (v ∧ j)⇒ ¬h3. (v ∧ j)⇒ ¬h4. v ∧ (j ⇒ ¬h)5. h ∧ (j ∨ ¬v)6. v ⇔ j

7. (h ∧ ¬j) ∨ (¬h ∧ v)8. h ∨ v ∨ j

5. Zapište pomocí symbolů výrokové logiky:

1. Přijde Petr i Pavel.

2. Přijde-li Petr, přijde také Pavel.

3. Petr přijde, právě když přijde Pavel.

4. Jestliže přijde Pavel, pak přijde Petr.

5. Pavel přijde tehdy a jen tehdy, když přijde Petr

6. Z dvojice Petr a Pavel přijde alespoň jeden.

7. Z dvojice Petr a Pavel přijde právě jeden.

8. Z dvojice Petr a Pavel přijde nejvýše jeden.

9. Oba nepřijdou.

10. Žádný nepřijde.

11. Oba přijdou.

20

6. Víte-li, že a označuje výrok „Přišel Adam� a e označuje výrok „Přišla Eva�,zapište symbolicky:

1. Přišel Adam a nepřišla Eva.

2. Přišel nejvýše jeden z nich, ale Adam to nebyl.

3. Nepřišel ani Adam ani Eva.

4. Neřišel Adam nebo přišla Eva s Adamem.

5. Eva přišla až když přišel Adam.

6. Adam přišel společně s Evou.

7. Rozhodněte o pravdivosti výroků:

1. (p⇒ q)⇔ ¬p ∨ q2. (p⇒ q) ∨ ¬(¬p ∨ q)3. ¬(p ∧ q)⇔ (¬p ∨ ¬q)4. (p ∨ q)⇔ (¬p ∧ ¬q)5. ((p⇒ q) ∧ (q ⇒ p))⇔ (p⇔ q)

6. ¬(p ∧ q ∧ r)⇔ (¬p ∨ ¬q ∨ ¬r)7. p⇒ (q ⇒ p)

8. Dokažte, že:

1. ¬(a ∧ b)⇔ (¬a ∨ ¬b)2. (a⇒ b)⇔ (¬a ∨ b)3. ¬(a ⇒ b)⇔ (a ∧ ¬b)

9. Vyjádřete stručně pomocí složených výroků, s využitím předcházejícího pří-kladu negace těchto výroků:

1. Máme pivo a minerálky.

2. Osvěžíme se čajem nebo kávou.

3. Jestliže budu obědvat vepřové, budu pít pivo.

4. Nemám hlad a nemám žízeň.

5. Nemám hlad a mám žízeň.

6. Budou-li ke koupi čekanka, nekoupím salát.

7. Doma nebudu tehdy a jen tehdy, když nebude pršet.

10. Rozhodněte, zda jsou uvedené úsudky logicky správné:

A1 : A ∨B ∨ CA2 : ¬AA3 : A⇒ CB1 : B

21

A⇒ BC ⇒ DA ∨ C¬(B ∧D)B ⇒ A

11. K uvedeným výrokovým formám utvořte existenční a obecné výroky a roz-hodněte o jejich pravdivosti:

1. A(x) : x > −x (Z = Z),

2. B(x) : x | x (Z = N),

3. C(x) : x2 + 5x− 4 = 0 (Z = Z),

4. D(x) : x2 − 8x+ 7 < 0 (Z = R).

12. Zformulujte negace následujících výroků. Definičním oborem je množinavšech diváků na jistém představení.

1. Všichni lidé mají slavnostní oblečení.

2. Odešlo už alespoň 5 lidí.

3. Nikdo neusnul.

4. Nejstaršímu divákovi je právě 60 let.

5. Kdokoliv může odejít.

6. Někdo zakašlal.

7. Ani jeden divák nešustí sáčkem s bonbóny.

13. Nechť K(x) znamená, že x je kočka, M(x) znamená, že x je myš a L(x, y)znamená, že x loví y. Vyjádřete co nejlépe česky formule:

1. (∀x)(K(x)⇒ ¬M(x))2. (∃x∀y)(K(x) ∧ ¬L(x, y) ∧M(y))3. (∃x∃y)(K(x) ∧ ¬L(x, y) ∧M(y))4. (∀x∀y)((K(x) ∧K(y))⇒ ¬L(x, y))

14. I do města Kocourkova pronikl turistický ruch. Městská rada projednávala,jak ještě více zvýšit příliv turistů. Byly předloženy tyto návrhy: vybudovatna náměstí kašnu, postavit pomník zakladateli města, vystavět vyhlídkovouvěž. Městská pokladna však není příliš plná, a tak se radní dohodli realizovatnejvýše dva z předložených návrhů.

V diskuzi vystoupili tři radní.První radní: „Jsem pro jakékoliv řešení, nebudu souhlasit jenom s rozhod-nutím stavět pomník a nestavět vyhlídkovou věž.�Druhý radní: „Budu protestovat jenom tehdy, kdybychom v našem městěstavěli kašnu a nepostavili pomník.�

22

Třetí radní: „Mně by nevyhovovalo jedině to řešení, kdyby v našem městěstála vyhlídková věž a chyběla kašna.�

Městská rada usoudila, že všem třem radním je třeba vyhovět. Co asi v Ko-courkově postaví?

15. V okamžiku, kdy na chodbě dozírající učitel uslyšel řinkot skla, byli vetřídě tři žáci: A, B, C. Při vyšetřování se zjistilo, že u okna byl nejvýšejeden z žáků A, B. Žák C byl u okna právě tehdy, když tam nebyl žák A.Když žák B nebyl u okna, nebyl tam ani žák A. Je možné určit pachatelev případě, že byl jenom jeden?

23