Modernizace studijn´ıho programu Matematika na PˇrF Univerzity Palack´eho v Olomouci CZ.1.07/2.2.00/28.0141
KMA/MDS Matematick´ e d˚ ukazy a jejich struktura
Semin´aˇr 1
C´ılem tohoto semin´aˇre je efektivn´ı uveden´ı do matematick´eho uvaˇzov´an´ı, zejm´ena matematick´eho dokazov´an´ı. Studenti matematiky zpravidla b´ yvaj´ı seznamov´ani s d˚ ukazy za pochodu“. Je jim ” pˇredn´aˇsena ta kter´a matematick´a teorie vˇcetnˇe d˚ ukaz˚ u a oˇcek´av´a se, ˇze student ˇcasem vnikne do matematick´eho uvaˇzov´an´ı, a s´am se nauˇc´ı d˚ ukazy ˇc´ıst1 , modifikovat i tvoˇrit. Jin´eho n´azoru byli p´anov´e Rowan Garnier a John Taylor, kteˇr´ı napsali skvˇelou knihu 100% Mathematical Proof ([3]), jej´ıˇz hlavn´ı c´ıl je sezn´amen´ı ˇcten´aˇre s hlavn´ımi principy axiomatick´e metody, kter´a je matematice vlastn´ı, a zejm´ena pˇredstaven´ı struktury d˚ ukaz˚ u, jejich typ˚ u a tvorby. Kniha je ps´ana velmi pˇr´ıstupn´ ym zp˚ usobem a pomalu a systematicky uv´ad´ı ˇcten´aˇre do t´eto problematiky. Je ji schopen ˇc´ıst kaˇzd´ y maturant. Moˇzn´a vhodnˇejˇs´ı knihou je How to prove it : a structured approach od D. Vellemana [7], kde je d˚ uraz kladen na nauˇcen´ı student˚ u tvoˇrit vlastn´ı d˚ ukazy. Jsou tam uk´az´any r˚ uzn´e tipy a strategie pˇri dokazov´an´ı konkr´etn´ıch i typov´ ych tvrzen´ı. Obˇe tyto knihy naleznete v univerzitn´ı knihovnˇe. Zmiˇ nme jeˇstˇe do ˇceˇstiny pˇreloˇzenou knihu Matematick´e d˚ ukazy od nˇemeck´eho autora R. Thieleho ([4]), kde je sp´ıˇs vˇedecko-popul´arn´ım zp˚ usobem ˇcten´aˇr sezn´amen se z´akladn´ımi principy matematiky. M˚ uˇze se zde dovˇedˇet spoustu zaj´ımavost´ı, kter´e se na matematick´e pˇredn´aˇsce nedozv´ı, ale kter´e by vˇedˇet mohl/mˇel. Pozornosti by ´ v´am nemˇelo uniknout ani skriptum Uvod do matematiky od M. Z´avodn´eho [8]. Lze jen konstatovat, ˇze ˇcesky psan´e literatury vˇenovan´e princip˚ um matematick´eho dokazov´an´ı pˇr´ıliˇs mnoho nen´ı. Zato v angliˇctinˇe je jich cel´a ˇrada (staˇc´ı napsat v nˇejak´em internetov´em vyhled´avaˇci kl´ıˇcov´a slova proof, mathematical proof, mathematical thinking, mathematical proving, apod.). Hlavn´ım n´astrojem pouˇz´ıvan´ ym pˇri usuzov´an´ı je matematick´a logika. Pro naˇse potˇreby bude staˇcit pˇreˇc´ıst ˇca´st prvn´ı kapitoly elektronick´eho skripta [1] nebo tˇreba u ´vod a prvn´ı paragrafy prvn´ı kapitoly knihy [5]. Student˚ um, kter´e logika zaujala, je moˇzno doporuˇcit tˇreba posledn´ı kapitolu skripta [2], stejnˇe jako knihy [5] a [6] (vˇse je v ˇceˇstinˇe). Veˇsker´a zde zm´ınˇen´a literatura je dostupn´a v univerzitn´ı nebo vˇedeck´e knihovnˇe.
Axiomatick´ a metoda – z´ akladn´ı pojmy Ve zkratce zmiˇ nme princip axiomatick´e metody, na kter´e je zaloˇzena kaˇzd´a modern´ı matematick´a teorie. Z´akladem kaˇzd´e matematick´e teorie je tzv. axiomatick´y syst´em. Axiomatick´ y syst´ em je souhrn z´akladn´ıch pojm˚ u (tzv. primitiv ) a axiom˚ u. Z´ akladn´ı pojem neboli primitivum je objekt axiomatick´eho syst´emu, popˇr. vlastnost objektu, vztah mezi objekty nebo operace nad nimi, kter´ y stoj´ı na zaˇ c´ atku teorie a je ponech´ an bez vysvˇ etlen´ı. Axiom je tvrzen´ı o z´akladn´ıch pojmech (popˇr. o pojmech odvozen´ych – viz d´ale), kter´e opˇet stoj´ı na poˇ c´ atku teorie a jsou povaˇ zov´ ana za pravdiv´ a. Dˇr´ıve se axiomy ch´apaly jako nˇeco natolik zˇrejm´eho, ˇze to nebylo potˇreba dokazovat. Dnes jsou ch´ap´any jako pˇredpoklady pˇr´ısluˇsn´e teorie. 1ˇ
Cten´ım d˚ ukazu se rozum´ı jeho pochopen´ı.
2
Matematick´ a teorie kromˇe axiomatick´eho syst´emu obsahuje definovan´e/odvozen´e pojmy a vˇety. Definovan´ y/odvozen´ y pojem je pojem odvozen´ y ze z´akladn´ıch pojm˚ u, nebo pojm˚ u jiˇz dˇr´ıve definovan´ ych. Pojem je uveden v ˇzivot“ v tzv. definici. ” Vˇ eta je pravdiv´e tvrzen´ı o z´akladn´ıch nebo definovan´ ych pojmech, jej´ıˇz pravdivost logicky plyne z axiom˚ u ˇci jin´ ych vˇet. Demonstraci pravdivosti se ˇr´ık´a d˚ ukaz. Tvrzen´ı o kter´em nev´ıme, zda je v dan´e teorii pravdiv´e, ˇr´ık´ame hypot´eza. Tento popis je velmi struˇcn´ y. V n´asleduj´ıc´ıch semin´aˇr´ıch vˇsechny pojmy postupnˇe zpˇresn´ıme. Z´akladn´ım prostˇredkem vyjadˇrov´an´ı a dokazov´an´ı bude v´yrokov´y a zejm´ena predik´atov´y poˇcet. Form´aln´ı zp˚ usob vyjadˇrov´an´ı byl zvolen proto, abychom se nemuseli zab´ yvat r˚ uzn´ ymi logick´ ymi paradoxy. Z didaktick´ ych d˚ uvod˚ u se prvn´ıch p´ar pˇredn´aˇsek budeme bavit (jednoduˇsˇs´ım) v´ yrokov´ ym poˇctem, zpˇresn´ıme pojmy jako tvrzen´ı, logicky plyne nebo d˚ ukaz atp.
V´ yrokov´ y poˇ cet – z´ akladn´ı pojmy N´asleduje such´ y popis potˇrebn´ ych pojm˚ u. Pro potˇreby tohoto semin´aˇre je p´ar vˇec´ı zamlˇceno a zjednoduˇseno. Pro korektnˇejˇs´ı v´ yklad je vˇrele doporuˇcena prvn´ı kapitola skript [1].
V´ yrok V´ yrok budeme ch´apat jako tvrzen´ı/vˇetu, o kter´e m´a smysl uvaˇzovat, zda je pravdiv´e ˇci nepravdiv´e. Pˇritom v´ yrok nen´ı pravdiv´ y ani nepravdiv´ y souˇcasnˇe.
Pravdivostn´ı hodnota v´ yroku Kaˇzd´emu v´ yroku lze pˇriˇradit tzv. pravdivostn´ı hodnotu. A to bud’ pravda – zkr´acenˇe 1 – pokud je v´ yrok pravdiv´ y, nebo nepravda – zkr´acenˇe 0 – pokud je v´ yrok nepravdiv´ y.
Logick´ e spojky Ve v´ yrokov´e logice n´as budou zaj´ımat logick´e spojky a jejich pouˇzit´ı pˇri vytv´aˇren´ı nov´ ych v´ yrok˚ u. Budou n´as zaj´ımat pouze ty nejzn´amˇejˇs´ı spojky a to un´arn´ı spojka negace a bin´arn´ı spojky konjunkce, disjunkce, implikace a ekvivalence.
Negace Jde o tzv. un´arn´ı spojku, protoˇze nepracuje s v´ıce v´ yroky ale pouze s jedn´ım. Negace se znaˇc´ı symbolem ¬“ a pouˇz´ıv´a se n´asledovnˇe. Je-li A v´ yrok, pak jeho negace se ” znaˇc´ı ¬A a ˇcte neplat´ı A“. Napˇr. negaci v´ yroku prˇs´ı“ m˚ uˇzeme ˇc´ıst jako neplat´ı, ” ” ” ˇze prˇs´ı“ nebo neprˇs´ı“. ” Pravdivostn´ı hodnoty negace: Je-li v´ yrok A pravdiv´ y, pak ¬A je nepravdiv´ y. 3
Je-li v´ yrok A nepravdiv´ y, pak ¬A je pravdiv´ y. Pˇrehlednˇe tato fakta m˚ uˇzeme zobrazit v tzv. pravdivostn´ı tabulce: A 0 1
¬A 1 0
Konjunkce Konjunkce je tzv. bin´arn´ı spojka, protoˇze spojuje dva v´ yroky. Konjunkce se znaˇc´ı symbolem ∧ a pouˇz´ıv´a se n´asledovnˇe. Jsou-li A, B v´ yroky, pak jejich konjunkce se znaˇc´ı A ∧ B a ˇcte plat´ı A a (souˇcasnˇe) plat´ı B“. Napˇr. konjunkci v´ yrok˚ u mˇel jsem ” ” na obˇed knedl´ık“ a mˇel jsem na obˇed zel´ı“ m˚ uˇzeme ˇc´ıst jako mˇel jsem na obˇed ” ” knedl´ık a zel´ı“. Pravdivostn´ı hodnoty konjunkce: V´ yrok A ∧ B je pravdiv´ y pouze v pˇr´ıpadˇe, ˇze jsou pravdiv´e oba dva v´ yroky A a B. Pravdivostn´ı tabulka: A 0 0 1 1
A∧B 0 0 0 1
B 0 1 0 1
Disjunkce Disjunkce se znaˇc´ı symbolem ∨ a pouˇz´ıv´a se n´asledovnˇe. Jsou-li A, B v´ yroky, pak jejich disjunkce se znaˇc´ı A ∨ B a ˇcte plat´ı A nebo plat´ı B“. Napˇr. disjunkci v´ yrok˚ u ” mˇel jsem na obˇed knedl´ık“ a mˇel jsem na obˇed zel´ı“ m˚ uˇzeme ˇc´ıst jako mˇel jsem ” ” ” na obˇed knedl´ık nebo zel´ı“. Pravdivostn´ı hodnoty disjunkce: V´ yrok A ∨ B je nepravdiv´ y pouze v pˇr´ıpadˇe, ˇze jsou nepravdiv´e oba dva v´ yroky A a B. Pravdivostn´ı tabulka: A 0 0 1 1
A∨B 0 1 1 1
B 0 1 0 1
U t´eto spojky je nutn´e zd˚ uraznit, ˇze se nepouˇ z´ıv´ a ve smyslu vyluˇ covac´ım, jak tomu vˇetˇsinou b´ yv´a pˇri pouˇz´ıv´an´ı v bˇeˇzn´e ˇreˇci. Napˇr. je-li v´ yrok mˇel jsem na obˇed ” knedl´ık nebo zel´ı“, znamen´a to, ˇze jsem mohl m´ıt oboje – bˇeˇznˇe bychom tento v´ yrok pochopili tak, ˇze jsem na obˇed nemˇel tyto dvˇe j´ıdla souˇcasnˇe.
Implikace Implikace se znaˇc´ı symbolem → a pouˇz´ıv´a se n´asledovnˇe. Jsou-li A, B v´ yroky, pak jejich implikace se znaˇc´ı A → B a ˇcte plat´ı-li A, pak plat´ı i B“ nebo jestliˇze A, pak ” ” B“. Dokonce se nˇekdy ˇr´ık´a plat´ı B, jestliˇze plat´ı A“. Napˇr. implikaci v´ yrok˚ u mˇel ” ” 4
jsem na obˇed knedl´ık“ a mˇel jsem na obˇed zel´ı“ m˚ uˇzeme ˇc´ıst jako jestliˇze jsem mˇel ” ” na obˇed knedl´ık, pak jsem mˇel (na obˇed) i zel´ı“. Pravdivostn´ı hodnoty implikace: V´ yrok A → B je nepravdiv´ y pouze v pˇr´ıpadˇe, ˇze A je pravdiv´ y a B je nepravdiv´ y. Tuto definici si lze pamatovat pomoc´ı hesla pravda ” nem˚ uˇze implikovat nepravdu, ale nepravda m˚ uˇze implikovat cokoliv“. Pravdivostn´ı tabulka: A 0 0 1 1
B 0 1 0 1
A→B 1 1 0 1
Narozd´ıl od pˇredchoz´ıch spojek je implikace pro zaˇca´teˇcn´ıka pomˇernˇe obt´ıˇznou spojkou. Je potˇreba si uvˇedomit, ˇze pravdivost v´ yroku A → B nic neˇ r´ık´ a o pravdivosti v´ yrok˚ u A a B ale pouze o vztahu jejich pravdivostn´ıch hodnot. Zejm´ ena nic neˇ r´ık´ a o platnosti v´ yroku A! V implikaci A → B se v´ yroku A ˇr´ık´a pˇredpoklad (premisa) a v´ yroku B z´avˇer. D´ale, plat´ı-li implikace A → B, pak se ˇr´ık´a, ˇze v´ yrok A je postaˇcuj´ıc´ı podm´ınkou v´ yroku B a tak´e, ˇze v´ yrok B je nutnou podm´ınkou v´ yroku A.
Ekvivalence Ekvivalence se znaˇc´ı symbolem ↔ a pouˇz´ıv´a se n´asledovnˇe. Jsou-li A, B v´ yroky, pak jejich ekvivalence se znaˇc´ı A ↔ B a ˇcte plat´ı A pr´avˇe tehdy, kdyˇz plat´ı B“. Napˇr. ” ekvivalenci v´ yrok˚ u mˇel jsem na obˇed knedl´ık“ a mˇel jsem na obˇed zel´ı“ m˚ uˇzeme ” ” ˇc´ıst jako Mˇel na obˇed knedl´ık pr´avˇe tehdy, kdyˇz jsem mˇel zel´ı“. ” Pravdivostn´ı hodnoty ekvivalence: V´ yrok A ↔ B je pravdiv´ y pouze v pˇr´ıpadˇe, ˇze A a B maj´ı stejnou pravdivostn´ı hodnotu. Pravdivostn´ı tabulka: A 0 0 1 1
B 0 1 0 1
A↔B 1 0 0 1
Stejnˇe jako u implikace, pravdivost v´ yroku A ↔ B nic neˇ r´ık´ a o pravdivosti v´ yrok˚ u A a B ale pouze o vztahu jejich pravdivostn´ıch hodnot. Zaj´ımav´e je, ˇze u ekvivalence nem´a tolik lid´ı probl´em s pochopen´ım, jako u implikace.
Jednoduch´ y versus sloˇ zen´ y v´ yrok V´ yroky typu mˇel jsem na obˇed knedl´ık“ budeme ch´apat jako jednoduch´e v´ yroky. ” V´ yroky poskl´adan´e z takov´ ych jednoduch´ ych v´ yrok˚ u pomoc´ı logick´ ych spojek budeme naz´ yvat sloˇzen´ymi, napˇr. v´ yrok mˇel jsem na obˇed knedl´ık a zel´ı“ lze ch´apat jako ” sloˇzen´ y v´ yrok vytvoˇren´ y pomoc´ı kojunkce z jednoduch´ ych v´ yrok˚ u mˇel jsem na obˇed ” knedl´ık“ a mˇel jsem na obˇed zel´ı“. ” 5
V´ yrokov´ a forma Ve v´ yrokov´e logice n´as nebude zaj´ımat smysl ani pravdivost jednoduch´ ych v´ yrok˚ u, ale jen tvar (forma) sloˇ zen´ ych v´ yrok˚ u. Napˇr´ıklad z hlediska v´ yrokov´e logiky pro n´as n´asleduj´ıc´ı v´ yroky maj´ı stejn´ y tvar: Jestliˇze jsem mˇel na obˇed knedl´ıky a zel´ı, pak ” 2+2 = 4“ a Jestliˇze vˇcera sv´ıtilo slunce a prˇselo, pak je sn´ıh ˇcerven´ y“. Evidentnˇe jde ” ou ´plnˇe r˚ uzn´e v´ yroky mluv´ıc´ı o r˚ uzn´ ych vˇecech, kter´e mohou m´ıt r˚ uznou pravdivostn´ı hodnotu. Nˇeco maj´ı ovˇsem spoleˇcn´e – a to tvar (formu). Oba se daj´ı zapsat ve tvaru (A ∧ B) → C, kde v prvn´ım pˇr´ıpadˇe jsme oznaˇcili p´ısmenem A v´ yrok mˇel jsem na obˇed knedl´ıky“, ” p´ısmenem B v´ yrok mˇel jsem na obˇed zel´ı“, p´ısmenem C v´ yrok 2 + 2 = 4“, a v ” ” druh´em pˇr´ıpadˇe jsme oznaˇcili p´ısmenem A v´ yrok vˇcera sv´ıtilo slunce“, p´ısmenem B ” ˇ ık´ame v´ yrok vˇcera sv´ıtilo slunce a prˇselo“, p´ısmenem C v´ yrok sn´ıh je ˇcerven´ y“. R´ ” ” pak, ˇze ty dva uveden´e v´ yroky jsou instancemi v´yrokov´e formy (a ∧ b) → c, kde p´ısmen˚ um a, b, c se ˇr´ık´a v´yrokov´e promˇenn´e. Dost´av´ame se tak k pojmu formalizuj´ıc´ı pojem v´ yrok ve v´ yrokov´em poˇctu. V´ yrokov´a forma bude ˇretˇezec symbol˚ u poskl´adan´ ych z tzv. symbol˚ u v´yrokov´e logiky, coˇz jsou • v´yrokov´e symboly, napˇr. a, b, p, q, . . ., • symboly v´yrokov´ych spojek, a to ¬, ∧, ∨, →, ↔, • pomocn´e symboly, coˇz jsou kulat´e z´avorky (, ), popˇr. pro zv´ yˇsen´ı pˇrehlednosti lze pouˇz´ıt i hranat´e. V´yrokov´a forma neboli formule v´yrokov´eho poˇctu – nebo jen formule – je bud’ • v´ yrokov´ y symbol (tzv. v´yrokov´a promˇenn´a ), nebo • jsou-li α, β v´ yrokov´e formy, pak jsou v´ yrokov´ ymi formami i v´ yrazy ¬α, (α ∧ β), (α ∨ β), (α → β), (α ↔ β), pˇritom vnˇejˇs´ı z´avorky formule lze vynechat. Napˇr´ıklad ˇretˇezec symbol˚ u (a ∧ b) → c je v´ yrokovou formou. A to z toho d˚ uvodu, ˇze 1. a, b jsou v´ yrokov´e symboly, tedy i v´ yrokov´e formy, 2. pak (a ∧ b) je tak´e v´ yrokov´e forma, 3. c je v´ yrokov´ y symbol, tedy i v´ yrokov´a forma, 4. pak ((a ∧ b) → c) je v´ yrokov´a forma 5. a odebr´an´ım vnˇejˇs´ıch z´avorek dost´av´ame, ˇze i (a ∧ b) → c je v´ yrokov´a forma.
6
Nutno podotknout, ˇze symboly v´ yrokov´e logiky jsou opravdu jen symboly. Nejde tedy o logick´e spojky ale o jejich oznaˇcen´ı. Podrobnosti viz [1]. Popsali jsme tedy, jak vypad´a v´ yrokov´a forma – tj. popsali jsme jej´ı syntaxi. Nyn´ı se pod´ıv´ame na 2 s´emantiku v´ yrokov´ ych forem. K tomu je potˇreba pojem pravdivostn´ı ohodnocen´ı. T´ım budeme intuitivnˇe rozumˇet pˇriˇrazen´ı pravdivostn´ıch hodnot 1 a 0 k v´ yrokov´ ym promˇenn´ ym. Detaily opˇet najdete v [1]. Pˇri dan´em pravdivostn´ım ohodnocen´ı lze spoˇc´ıtat pravdivostn´ı hodnotu dan´e formule a to podle jiˇz definovan´ ych pravdivostn´ıch tabulek. Tzn. pro v´ yrokov´e formule a, b definujeme a 0 1
a 0 0 1 1
¬a 1 0
b 0 1 0 1
a∧b 0 0 0 1
a∨b 0 1 1 1
a→b 1 1 0 1
a↔b 1 0 0 1
Mˇejme napˇr´ıklad formuli (a ∧ b) → c o tˇrech v´ yrokov´ ych promˇenn´ ych. Jedn´ım z pravdivostn´ıch ohodnocen´ı je napˇr., ˇze symbolu a pˇriˇrad´ıme 1, symbolu b pˇriˇrad´ıme 0 a symbolu c pˇriˇrad´ıme 1. Pak podle v´ yˇse uveden´e tabulky m´a formule (a ∧ b) ohodnocen´ı 0 a podle stejn´e tabulky m´a formule (a ∧ b) → c ohodnocen´ı 1. To lze pˇrehlednˇe zapsat do tabulky: a 1
b 0
c 1
a∧b 0
(a ∧ b) → c 1
Do formule lze za v´ yrokov´e promˇenn´e dosazovat jin´e formule. Dost´av´ame tak dalˇs´ı formuli. Znaˇ cen´ı: V´ yroky budeme znaˇcit velk´ ymi p´ısmeny (tj. A, B, C, . . .), v´ yrokov´e promˇenn´e mal´ ymi p´ısmeny (a, b, . . ., p, q, . . .) a v´ yrokov´e formy mal´ ymi p´ısmeny ˇreck´e abecedy (α, β, . . ., ϕ, η, . . .). Pokud by n´am doˇsly symboly, budeme pouˇz´ıvat doln´ı indexy (napˇr. A1 , A2 , . . .).
Pravidlo nahrazen´ı Mˇejme formuli α s v´ yrokov´ ymi promˇenn´ ymi a1 , . . . , an a formule β1 , . . . , βn . Pak nahrazen´ım vˇsech v´ yskyt˚ u promˇenn´ ych a1 , . . . , an ve formuli α postupnˇe formulemi β1 , . . . , βn vznikne opˇet formule.
Instance v´ yrokov´ e formy Dosad´ıme–li do v´ yrokov´e formy za v´ yrokov´e promˇenn´e konkr´etn´ı v´ yroky, vznikl´emu (sloˇzen´emu) v´ yroku ˇr´ık´ame instance v´yrokov´e formy.
Pravdivostn´ı tabulka v´ yrokov´ e formy Tato tabulka – podobnˇe jako pravdivostn´ı tabulky logick´ ych spojek – d´av´a pravdivostn´ı hodnoty jak´ekoliv formule pˇri vˇsech moˇzn´ ych pravdivostn´ıch ohodnocen´ıch. Napˇr. pravdivostn´ı tabulka formule (a ∧ b) → c vypad´a takto 2
Zhruba ˇreˇceno, syntaxe je o z´ apisu a s´emantika je o v´ yznamu/smyslu.
7
a b c 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1
a∧b 0 0 0 0 0 0 1 1
(a ∧ b) → c 1 1 1 1 1 1 0 1
V posledn´ım sloupci jsou pˇrehlednˇe shrnuty pravdivostn´ı hodnoty formul´ı pˇri odpov´ıdaj´ıc´ım pravdivostn´ım ohodnocen´ı v´ yrokov´ ych promˇenn´ ych (ve stejn´em ˇra´dku). Ostatn´ı sloupce napravo od rozdˇelovac´ı ˇc´ary jsou pouze pomocn´e.
Tautologie Tautologie je v´ yrokov´a forma, kter´a je pravdiv´ a pˇ ri kaˇ zd´ em pravdivostn´ım ohodnocen´ı. Prakticky to lze ovˇeˇrit snadno. Staˇc´ı sestavit pravdivostn´ı tabulku t´eto formule. Formule je pak tautologi´ı pr´avˇe tehdy, kdyˇz ve sloupci t´eto formule jsou sam´e jedniˇcky. Tautologi´ım se tak´e ˇr´ık´a logick´e z´akony. Budou pro n´as z´akladn´ım n´astrojem pˇri dokazov´an´ı. Zde je seznam nˇekter´ ych d˚ uleˇzit´ ych tautologi´ı. 1. (p ∨ q) ↔ (q ∨ p) 2. (p ∧ q) ↔ (q ∧ p) 3. (p ∨ (q ∨ r)) ↔ ((p ∨ q) ∨ r) 4. (p ∧ (q ∧ r)) ↔ ((p ∧ q) ∧ r) 5. (p ∨ (q ∧ r)) ↔ ((p ∨ q) ∧ (p ∨ r)) 6. (p ∧ (q ∨ r)) ↔ ((p ∧ q) ∨ (p ∧ r)) 7. ¬(p ∧ q) ↔ (¬p ∨ ¬q) 8. ¬(p ∨ q) ↔ (¬p ∧ ¬q) 9. p ↔ ¬¬p 10. (p → q) ↔ (¬p ∨ q) 11. (p → q) ↔ (¬q → ¬p) 12. (p ∧ (p → q)) → q 13. (¬q ∧ (p → q)) → ¬p 14. (p ↔ q) ↔ ((p → q) ∧ (q → p)) Ovˇeˇren´ı, ˇze jde skuteˇcnˇe o tautologie, je dobr´ ym cviˇcen´ım na pr´aci s pravdivostn´ımi tabulkami formul´ı. 8
Kontradikce Naopak kontradikce je v´ yrokov´a forma, kter´a je nepravdiv´ a pˇ ri kaˇ zd´ em pravdivostn´ım ohodnocen´ı. Zˇrejmˇe plat´ı, ˇze negace tautologie je kontradikce a naopak. Jeˇstˇe je nutno dodat, ˇze vznikne-li formule z jin´e nahrazen´ım vˇsech v´ yskyt˚ u jej´ıch promˇenn´ ych formulemi, je tautologi´ı (resp. kontradikc´ı), jestliˇze p˚ uvodn´ı formule byla tautologi´ı (resp. kontradikc´ı).
Splniteln´ a formule Splniteln´a formule je takov´a, kter´a je pravdiv´ a pˇ ri alespoˇ n jednom pravdivostn´ım ohodnocen´ı. Plat´ı, ˇze formule je splniteln´a pr´avˇe tehdy, kdyˇz nen´ı kontradikce.
Cviˇ cen´ı N´asleduj´ıc´ı cviˇcen´ı jsou povˇetˇsinou pˇrevzaty (popˇr. pˇreloˇzeny) z doporuˇcen´e literatury, kde je jich moˇzno naj´ıt v´ıce. ´ Uloha 1.1 Vypoˇctˇete, kolik existuje un´arn´ıch a kolik bin´arn´ıch spojek. ´ Uloha 1.2 Necht’ A, B jsou v´ yroky. Odpovˇezte na n´asleduj´ıc´ı ot´azky (pˇri ˇreˇsen´ı je moˇzno s v´ yhodou pouˇz´ıt pravdivostn´ı tabulky pˇr´ısluˇsn´ ych spojek): 1. Zn´ame-li pravdivostn´ı hodnotu v´ yroku ¬A, co lze ˇr´ıct o pravdivostn´ı hodnotˇe v´ yroku A? 2. Je-li v´ yrok A ∨ B pravdiv´ y a B nepravdiv´ y, co lze ˇr´ıct o pravdivosti v´ yroku A? 3. Je-li v´ yrok A ∨ B pravdiv´ y a B pravdiv´ y, lze nˇeco ˇr´ıct o pravdivosti v´ yroku A? 4. Je-li v´ yrok A ∧ B nepravdiv´ y a B pravdiv´ y, co lze ˇr´ıct o pravdivosti v´ yroku A? 5. Je-li v´ yrok A ∧ B nepravdiv´ y a B nepravdiv´ y, lze nˇeco ˇr´ıct o pravdivosti v´ yroku A? 6. Je-li v´ yrok A → B pravdiv´ y a A pravdiv´ y, co lze ˇr´ıct o pravdivosti v´ yroku B? 7. Je-li v´ yrok A → B nepravdiv´ y a B nepravdiv´ y, co lze ˇr´ıct o pravdivosti v´ yroku A? Odpovˇedi na ot´azky je potˇreba zaˇz´ıt (ale ne nabiflovat!), abyste je mohli kdykoliv v budoucnu bez pˇrem´ yˇslen´ı pouˇz´ıt. (Toto cviˇcen´ı slouˇz´ı k osvojen´ı s´emantiky z´akladn´ıch spojek, zejm´ena implikace.) ´ Uloha 1.3 Uvaˇzujme n´asleduj´ıc´ı v´ yroky: C: Budu m´ıt v´ıce ˇcasu. K: Nauˇc´ım se hr´at na klav´ır. P : Zdvojn´asob´ım si plat. 9
Zapiˇste pomoc´ı symbol˚ u C, K, P a logick´ ych spojek n´asleduj´ıc´ı v´ yroky: 1. Jestliˇze budu m´ıt v´ıc ˇcasu, zdvojn´asob´ım si plat, ale nebudu se uˇcit hr´at na klav´ır. 2. Jestliˇze budu m´ıt v´ıc ˇcasu, pak se budu uˇcit hr´at na klav´ır, a kdyˇz budu m´ıt v´ıce ˇcasu, pak si zdvojn´asob´ım plat. 3. Jestliˇze se budu uˇcit hr´at na klav´ır, pak nebudu m´ıt v´ıce ˇcasu a ani si nezdvojn´asob´ım plat. 4. Jestliˇze si zdvojn´asob´ım plat a nauˇc´ım se hr´at na klav´ır, nebudu m´ıt v´ıce ˇcasu. 5. Jestliˇze budu m´ıt v´ıce ˇcasu, nauˇc´ım se hr´at na klav´ır, a jestli se nauˇc´ım hr´at na klav´ır, zdvojn´asob´ım si plat. (Toto cviˇcen´ı slouˇz´ı k tomu, aby student byl schopen okamˇzitˇe pˇrekl´adat z bˇeˇzn´e ˇreˇci do form´aln´ıho jazyka v´ yrokov´e logiky.) ´ Uloha 1.4 Uvaˇzujme n´asleduj´ıc´ı v´ yroky: S: Slunce sv´ıt´ı. V : V´ıtr fouk´a. D: Prˇs´ı. T : Teplota roste. Proved’te: 1. Napiˇste ˇcesky n´asleduj´ıc´ı sloˇzen´e v´ yroky: (a) V → (¬S ∨ D), (b) (V ∧ D) ↔ ¬S, (c) (V ∨ D) ∧ ¬T , (d) ¬(S ∧ V ) → (D ∨ ¬T ). 2. Za pˇredpokladu, ˇze v´ yroky S, V , D, T jsou vˇsechny pravdiv´e, zjistˇete, kter´a n´asleduj´ıc´ı sloˇzen´e v´ yroky jsou pravdiv´e a kter´e ne: (a) (S → V ) ∧ (¬D ∧ T ), (b) (S ∧ ¬D) ↔ (T ∨ ¬V ), (c) ¬((D ∨ T ) ∧ (V → S)). ˇ ast 1. tohoto cviˇcen´ı slouˇz´ı k tomu, aby student byl schopen okamˇzitˇe pˇrekl´adat z (C´ form´aln´ıho jazyka v´ yrokov´e logiky do bˇeˇzn´e ˇreˇci.) ´ Uloha 1.5 Pomoc´ı pravdivostn´ı tabulky ovˇeˇrte, ˇze formule v ˇca´sti Tautologie jsou opravdu vˇsechny tautologiemi. (Toto cviˇcen´ı je zamˇeˇreno k procviˇcen´ı urˇcov´an´ı pravdivostn´ıch hodnot logick´ ych spojek a tak´e k zapamatov´an´ı d˚ uleˇzit´ ych tautologi´ı, kter´e budou hr´at v dalˇs´ım v´ yznamnou roli.) 10
Reference [1] Bˇelohl´avek, R., Vychodil, V., Diskr´etn´ı matematika pro informatiky I., UP Olomouc, 2004. [dostupn´e online: http://belohlavek.inf.upol.cz/vyuka/dm1.pdf ] [2] Bˇelohl´avek, R., Vychodil, V., Diskr´etn´ı matematika pro informatiky II., UP Olomouc, 2004. [dostupn´e online: http://belohlavek.inf.upol.cz/vyuka/dm2.pdf ] [3] Garnier, R., Taylor, J., 100% Mathematical Proof, John Wiley & Sons, Chichester, 1996. [4] Thiele, R., Matematick´e d˚ ukazy, SNTL, Praha, 1986. [5] Sochor, A., Klasick´a matematick´a logika, Karolinum, Praha, 2001. ˇ [6] Svejdar, V., Logika: ne´ uplnost, sloˇzitost a nutnost, Academia, Praha, 2002. [dostupn´e tak´e online: http://www1.cuni.cz/ svejdar/book/LogikaSve2002.pdf ] [7] Velleman, D.J., How to prove it : a structured approach, Cambridge University Press, New York, 2006. ´ [8] Z´avodn´ y, M., Uvod do matematiky, Pˇr´ırodovˇedeck´a fakulta, UP v Olomouci, Olomouc, 2013.
11
