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 2
V´ yrokov´ a logika – pokraˇ cov´ an´ı Logick´ e vypl´ yv´ an´ı ˇ Mˇejme d´any dvˇe formule α, β. Rekneme, ˇze α logicky implikuje β, neboli β logicky vypl´yv´a z α, jestliˇze pˇri jak´emkoliv ohodnocen´ı promˇenn´ ych, pro kter´e je pravdiv´a formule α, je pravdiv´a i formule β. P´ıˇseme α ` β. Pˇ r´ıklad 2.1 Uk´aˇzeme, ˇze plat´ı a ∧ (a → b) ` a ∨ b. Je potˇreba uvaˇzovat vˇsechna ohodnocen´ı promˇenn´ ych formul´ı α = a ∧ (a → b) a β = a ∨ b. Je vidˇet, ˇze jde o tˇri promˇenn´e a, b a c. Nejefektivnˇejˇs´ı zp˚ usob je vypsat tato ohodnocen´ı do tabulky – konkr´etnˇe do pravdivostn´ı tabulky tˇechto dvou formul´ı α a β. Protoˇze m´ame ovˇeˇrit pouze zda je pravdiv´a β za pˇredpokladu pravdivosti α, lze si uˇsetˇrit pr´aci t´ım, ˇze vypoˇc´ıt´ame pravdivostn´ı hodnoty formule α pro vˇsechna ohodnocen´ı promˇenn´ ych, pˇritom pravdivostn´ı hodnoty formule β staˇc´ı vypoˇc´ıtat jen pro takov´a ohodnocen´ı, pro kter´e je α pravdiv´a. Viz tabulku. Vid´ıme, ˇze jsme si uˇsetˇrili a 0 0 1 1
b 0 1 0 1
a→b 1 1 0 1
a ∧ (a → b) 0 0 0 1
a∨b
1
Tabulka 1: Pravdivostn´ı tabulka pro zjiˇstˇen´ı log. vypl´ yv´an´ı dvou formul´ı pr´aci a vypoˇc´ıtali pravdivostn´ı hodnotu formule β pouze pro posledn´ı pravdivostn´ı ohodnocen´ı. Protoˇze ve sloupci napravo se nevyskytuje 0, dost´av´ame, ˇze opravdu α logicky implikuje β. Pokud bychom v tabulce v pˇredchoz´ım pˇr´ıkladu pˇridali sloupec pro pravdivostn´ı hodnotu formule (a ∧ (a → b)) → (a ∨ b), zjistili bychom, ˇze jde o tautologii. To nen´ı n´ahoda. Dokonce obecnˇe plat´ı, ˇze • α ` β pr´avˇe tehdy, kdyˇz je formule α → β tautologie.
Logick´ a ekvivalence ˇ Mˇejme d´any dvˇe formule α, β. Rekneme, ˇze α a β jsou logicky ekvivalentn´ı, jestliˇze pro jak´ekoliv ohodnocen´ı maj´ı formule α i β stejnou pravdivostn´ı hodnotu. P´ıˇseme α ≡ β. Plat´ı 2
• α ≡ β pr´avˇe tehdy, kdyˇz α ↔ β je tautologie, • α ≡ β pr´avˇe tehdy, kdyˇz α ` β a z´aroveˇ n β ` α. Z kapitoly Tautologie z pˇredchoz´ı opory lze z´ıskat n´asleduj´ıc´ı ekvivalence – budeme je naz´ yvat pravidly nahrazen´ı1 : N´azev a zkratka
Ekvivalence
komutativita (Com)
(α ∨ β) ≡ (β ∨ α) (α ∧ β) ≡ (β ∧ α)
asociativita (Assoc)
(α ∨ (β ∨ γ)) ≡ ((α ∨ β) ∨ γ) (α ∧ (β ∧ γ)) ≡ ((α ∧ β) ∧ γ)
distributivita (Dist)
(α ∨ (β ∧ γ)) ≡ ((α ∨ β) ∧ (α ∨ γ)) (α ∧ (β ∨ γ)) ≡ ((α ∧ β) ∨ (α ∧ γ)) ¬(α ∧ β) ≡ (¬α ∨ ¬β) ¬(α ∨ β) ≡ (¬α ∧ ¬β)
De Morganovy z´akony (De M)
α ≡ ¬¬α
dvoj´ı negace (DN) implikace (Impl)
(α → β) ≡ (¬α ∨ β)
obmˇena (Trans)
(α → β) ≡ (¬β → ¬α)
ekvivalence (Equiv)
(α ↔ β) ≡ ((α → β) ∧ (β → α)) (α ↔ β) ≡ ((α ∧ β) ∨ (¬α ∧ ¬β)) (α ∧ β) → γ ≡ α → (β → γ)
spojov´an´ı pˇredpoklad˚ u (Exp)
α∧α≡α α∨α≡α
Tautologie (Taut)
Tyto ekvivalence ˇcasto pouˇz´ıv´ame k u ´pravˇe formul´ı na bud’ jednoduˇsˇs´ı formule, ˇci formule v nˇejak´em vhodn´em tvaru. Budou tak´e potˇreba v d˚ ukazech, viz d´ale.
´ Usudek (argument) ´ Usudkem budeme rozumˇet (koneˇcnou) mnoˇzinu v´ yrok˚ u, kter´ ym budeme ˇr´ıkat pˇredpoklady (premisy), spoleˇcnˇe s dalˇs´ım v´ yrokem, kter´emu budeme ˇr´ıkat z´avˇer. ´ Z´avˇer b´ yv´a uvozen slovy proto plat´ı, ˇze“ nebo pak“ apod. Usudek je takovou ” ” z´akladn´ı jednotku usuzov´an´ı. Pˇ r´ıklad 2.2 Uvaˇzujeme n´asleduj´ıc´ı u ´sudek: Dnes m´a Eva zkouˇsku z fyziky nebo z ” matematiky. Eva dnes nem´a zkouˇsku z fyziky. Proto plat´ı, ˇze Eva m´a dnes zkouˇsku z matematiky“. Premisami jsou dva v´ yroky: Dnes m´a Eva zkouˇsku z fyziky nebo z matematiky. ” Eva dnes nem´a zkouˇsku z fyziky.“ Z´avˇer je v´ yrok: Eva m´a dnes zkouˇsku z matem” atiky“. 1
Nepl´est si s pravidlem nahrazen´ı z pˇredchoz´ı opory.
3
Oznaˇcme F : Dnes m´a Eva zkouˇsku z fyziky.“ ” M : Dnes m´a Eva zkouˇsku z matematiky.“ ” Pak premisy naˇseho u ´sudku lze ps´at jako F ∨ M , ¬F a z´avˇer lze zapsat jako M . Zamysl´ıme-li se nad u ´sudkem z Pˇr´ıkladu 2.2, mohli bychom se shodnout na tom, ˇze je spr´avn´ y“ – budeme ˇr´ıkat platn´y. Tato platnost ovˇsem nen´ı a nesm´ı b´ yt z´avisl´a ” na konkr´etn´ıch v´ yroc´ıch, ale k jej´ı platnosti mus´ıme dospˇet pouze prostˇredky logiky. Abstrahovat od obsahu konkr´etn´ıch v´ yrok˚ u jiˇz um´ıme – m´ısto jednotliv´ ych v´ yrok˚ u budeme uvaˇzovat pˇr´ısluˇsn´e formule. Takto pˇrejdeme od konkr´etn´ıho u ´sudku k pojmu u ´sudkov´a forma.
´ Usudkov´ a forma Srovnejme u ´sudek z Pˇr´ıkladu 2.2 s n´asleduj´ıc´ım u ´sudkem: Premisy jsou Dnes p˚ ujdu ” do kina nebo divadla“, Dnes nep˚ ujdu do kina“ se z´avˇerem Dnes p˚ ujdu do divadla“. ” ” Asi bude opˇet platn´ y. Vid´ıme, ˇze aˇckoliv se v nˇem mluv´ı u ´plnˇe o jin´ ych vˇecech, k intuitivn´ımu ovˇeˇren´ı jeho spr´avnosti jsme doˇsli stejnou logickou u ´vahou. Pˇri usuzov´an´ı je tedy d˚ uleˇzit´a struktura, nikoliv konkr´etn´ı v´ yroky. To n´as vede k zaveden´ı pojmu u ´sudkov´e formy. Ta m´a vztah ke konkr´etn´ımu u ´sudku stejn´ y, jako m´a formule ke konkr´etn´ımu v´ yroku (jeho instanci). ´ Usudkovou formou budeme rozumˇet (koneˇcnou) mnoˇzinu formul´ı, kter´ ym budeme ˇr´ıkat pˇredpoklady (premisy), spoleˇcnˇe s dalˇs´ı formul´ı, kter´e budeme ˇr´ıkat z´avˇer. Dosad´ıme-li do premis a z´avˇeru u ´sudkov´e formy za v´ yrokov´e symboly konkr´etn´ı v´ yroky, dostaneme u ´sudek, kter´emu budeme ˇr´ıkat instance u ´sudkov´e formy. Pˇ r´ıklad 2.3 Uvaˇzujme u ´sudkovou formu s premisami a∨b, ¬a a z´avˇerem b. Dosad´ımeli za promˇenn´e a a b postupnˇe v´ yroky dnes m´a Eva zkouˇsku z fyziky“ a dnes m´a ” ” Eva zkouˇsku z matematiky“, dostaneme u ´sudek z Pˇr´ıkladu 2.2, kter´ y je jeho instanc´ı (jednou z mnoha). N´asleduje d˚ uleˇzit´a definice: ˇ Rekneme, ˇze u ´sudkov´a forma s premisami α1 , α2 , . . . , αn a z´avˇerem β je platn´a, jestliˇze pro kaˇzd´e ohodnocen´ı v´ yrokov´ ych promˇenn´ ych plat´ı, ˇze jsou-li vˇsechny premisy pravdiv´e, je pravdiv´ y i z´avˇer. Pokud tomu tak nen´ı, ˇr´ık´ame, ˇze u ´sudkov´a forma je neplatn´a. Snadno lze nahl´ednout, ˇze u ´sudkov´a forma je platn´a pr´avˇe tehdy, kdyˇz (α1 ∧ α2 ∧ . . . ∧ αn ) ` β, 4
neboli, kdyˇz je formule (α1 ∧ α2 ∧ . . . ∧ αn ) → β tautologi´ı. Nyn´ı m˚ uˇzeme koneˇcnˇe zadefinovat platnost u ´sudku: ˇ Rekneme, ˇze u ´sudek je platn´y, jestliˇze je instanc´ı platn´e u ´sudkov´a formy. Snadno lze ovˇeˇrit, ˇze ((a ∨ b) ∧ ¬a) ` b, tzn. u ´sudek z Pˇr´ıkladu 2.2 je skuteˇcnˇe platn´ y!
Nekonzistentn´ı premisy M˚ uˇze se st´at, ˇze premisy u ´sudkov´e formy jsou takov´e, ˇze nejsou z´aroveˇ n vˇsechny pravdiv´e pˇri ˇza´dn´em pravdivostn´ım ohodnocen´ı – tzn. konjunkce vˇsech premis je kontradikc´ı. To pak ale m´a za n´asledek, ˇze implikace z definice platnosti u ´sudkov´e formy je vˇzdy (tzn. pˇri jak´emkoliv pravdivostn´ım ohodnocen´ı) pravdiv´a. Jinak ˇreˇceno, z takov´ ych premis pak m˚ uˇze vypl´ yvat cokoliv. Pˇ r´ıklad 2.4 Uvaˇzujme napˇr´ıklad u ´sudek s premisami jestliˇze je Michal na dovolen´e, ” pak je na Bermud´ach“, Michal je bud’ v kancel´aˇri nebo na dovolen´e“, Michal nen´ı ” ” v kancel´aˇri a nen´ı ani na Bermud´ach“ a z´avˇerem Michal m´a dovolenou“. Zjist´ıme, ” ˇze tento u ´sudek je platn´ y (proved’te!). Zaj´ımav´e ovˇsem je, ˇze zamˇen´ıme-li v tomto u ´sudku z´avˇer za jeho negaci, tj. Michal nem´a dovolenou“, dostaneme opˇet platn´ y ” u ´sudek (ovˇeˇrte sami)! Dokonce, vezmeme-li za z´avˇer jak´ ykoliv (!) v´ yrok (opravdu jak´ ykoliv, v˚ ubec se nemus´ı t´ ykat Michala), bude u ´sudek opˇet platn´ y. D˚ uvodem je fakt, ˇze konjunkce vˇsech premis pˇr´ısluˇsn´e u ´sudkov´e formy je kontradikce. Jestiˇze konjunkce vˇsech premis dan´e u ´sudkov´e formy je kontradikce, ˇr´ık´ame, ˇze premisy jsou nekonzistentn´ı. Protoˇze z nekonzistentn´ıch premis lze usoudit cokoliv, nebudou n´as takov´e u ´sudkov´e formy (a jejich instance) zaj´ımat!
Form´ aln´ı d˚ ukaz platnosti u ´ sudku Platnost u ´sudku jsme definovali prostˇrednictv´ım platnosti pˇr´ısluˇsn´e u ´sudkov´e formy. Ovˇeˇrit platnost u ´sudkov´e formy pomoc´ı pravdivostn´ı tabulky je tak jednoduch´e, ˇze je to moˇzno prov´est i strojovˇe. Probl´em ovˇsem nast´av´a, kdyˇz je poˇcet v´ yrokov´ ych promˇenn´ ych v u ´sudkov´e formˇe vˇetˇs´ı. Jak lze snadno spoˇc´ıtat, objevuje-li se v u ´sudkov´e formˇe n v´ yrokov´ ych promˇenn´ ych, pak m´a pravdivostn´ı tabulka 2n ˇra´dk˚ u. V praxi se vyskytuj´ıc´ıch u ´sudkov´ ych form´ach by se ale mohly objevovat des´ıtky promˇenn´ ych, coˇz uˇz by ˇcasem nezvl´adaly ani superpoˇc´ıtaˇce. Proto je potˇreba platnost u ´sudku ovˇeˇrit jinak – d˚ ukazem. P˚ ujde o seznam v´ yrok˚ u, kde na zaˇca´tku budou st´at premisy, kaˇzd´ y dalˇs´ı ˇra´dek bude logicky vypl´ yvat z pˇredchoz´ıch ˇra´dk˚ u a na posledn´ım ˇr´adku bude z´avˇer u ´sudku. 5
Budou se pouˇz´ıvat n´asleduj´ıc´ı pravidla odvozov´an´ı2 – jde o platn´e u ´sudkov´e formy. N´azev a zkratka zjednoduˇsen´ı (Simp) souˇcet (Add) konjunkce (Conj) disjunktivn´ı sylogismus (DS) modus ponens (MP) modus tollens (MT) hypotetick´ y sylogismus (HS) absorpce (Abs) konstruktivn´ı dilema (CD)
Premisy
Z´avˇer
a∧b a a, b a ∨ b, ¬a a → b, a a → b, ¬b a → b, b → c a→b (a → b) ∧ (c → d), a ∨ c
a a∨b a∧b b b ¬a a→c a → (a ∧ b) b∨d
Nyn´ı m˚ uˇzeme definovat metodu form´aln´ıho d˚ ukazu u ´sudku. Ta n´am umoˇzn´ı sn´aze pochopit definici d˚ ukazu matematick´e vˇety. Pro dan´ yu ´sudek s premisami P1 , . . . , Pn a z´avˇerem Q, rozum´ıme form´aln´ım d˚ ukazem jeho platnosti seznam v´ yrok˚ u, zaˇc´ınaj´ıc´ım premisami a konˇc´ıc´ı z´avˇerem. Pˇritom pro kaˇzd´ y v´ yrok z tohoto seznamu plat´ı: • je premisa, nebo • m˚ uˇze b´ yt odvozen pomoc´ı pravidel odvozen´ı z pˇredch´azej´ıc´ıch v´ yrok˚ u, nebo • je ekvivalentn´ı – pomoc´ı pravidel nahrazen´ı – s nˇekter´ ym z pˇredch´azej´ıc´ıch v´ yrok˚ u.
Z t´eto definice je vidˇet, ˇze opˇet nez´avis´ı na konkr´etn´ıch v´ yroc´ıch ale struktuˇre premis a z´avˇeru. Proto m´ısto o premis´ach a z´avˇeru m˚ uˇzeme m´ısto o v´ yroc´ıch mluvit o pˇr´ısluˇsn´ ych formul´ıch (jejichˇz jsou instancemi).
Shrnut´ı V t´eto opoˇre jsme si uk´azali, co to znamen´a logick´e vypl´ yv´an´ı formul´ı v´ yrokov´e logiky a co je logick´a ekvivalence dvou formul´ı. Nejd˚ uleˇzitˇejˇs´ımi pojmy t´eto opory byly ´ u ´sudek a jeho d˚ ukaz. Usudek je seznam“ v´ yrok˚ u, kter´ ym ˇr´ık´ame premisy plus v´ yrok ” nav´ıc, kter´emu se ˇr´ık´a z´avˇer. Platnost u ´sudku se ovˇeˇruje takto: 1. Najdeme u ´sudkovou formu jej´ıˇz je u ´sudek instanc´ı. 2. Oznaˇc´ıme-li α1 , . . . , αn premisy u ´sudkov´e formy a β jej´ı z´avˇer (nyn´ı jde o formule!), pak platnost ˇci neplatnost u ´sudkov´e formy z´avis´ı na tom, zda je ˇci nen´ı formule (α1 ∧ . . . ∧ αn ) → β tautologi´ı. 2
Promyslete jejich smysl. Vˇetˇsinu tˇechto pravidel dennˇe pouˇz´ıv´ate automaticky. Zkuste je zaˇc´ıt pouˇz´ıvat vˇedomˇe.
6
´ 3. Usudek je platn´ y ˇci neplatn´ y, pokud je takov´a jeho u ´sudkov´a forma. Na tomto postupu je potˇreba si uvˇedomit fakt, ˇze u ´sudek nejprve pˇrevedeme na u ´sudkovou formu, kter´a nic nev´ı o obsahu jednotliv´ ych v´ yrok˚ u naˇseho u ´sudku, pouze zachycuje vniˇrn´ı logickou strukturu (realizovanou pomoc´ı logick´ ych spojek). Platnost pak z´avis´ı pouze na pravidlech logiky. D´ale jsme si uk´azali dva zp˚ usoby jak ovˇeˇrit platnost u ´sudku: 1. pomoc´ı pravdivostn´ı tabulky (potenci´alnˇe pracn´e, ale bez pˇrem´ yˇslen´ı), 2. pomoc´ı form´aln´ıho d˚ ukazu (potenci´alnˇe m´enˇe pracn´e, ale vyˇzaduj´ıc´ı zkuˇsenost, kreativitu a vhled do probl´emu).
Cviˇ cen´ı ´ Uloha 2.1 Zjistˇete platnost n´asleduj´ıc´ıch u ´sudk˚ u. 1. Jestliˇze Tom´aˇs pˇrijede z´ıtra, sn´ım sv˚ uj klobouk. Tom´aˇs z´ıtra nepˇrijede. Proto nesn´ım sv˚ uj klobouk. 2. Jestliˇze budu hodnˇe pracovat, z´ısk´am dobrou pr´aci. Jestliˇze z´ısk´am dobrou pr´aci, stanu se v´aˇzen´ ym obˇcanem. Proto, kdyˇz budu hodnˇe pracovat, stanu se v´aˇzen´ ym obˇcanem. 3. Jestliˇze budou zbranˇe zak´az´any, budeme ˇz´ıt vˇsichni v m´ıru. Budeme ˇz´ıt v m´ıru nebo lidsk´a rasa vymˇre (pozor, zde je pouˇzito nebo“ ve vyluˇcovac´ım smyslu!). ” Nebudeme ˇz´ıt v m´ıru. Proto budou zbranˇe zak´az´any. 4. Jana pˇrijde na mou p´arty pr´avˇe tehdy, kdyˇz Marek nepˇrijde. Jestliˇze Jana na mou p´arty nepˇrijde, pak Jirka na ni tak´e nepˇrijde. Proto pˇrijde bud’ Jirka nebo Marek ale ne oba souˇcasnˇe. 5. Teplota roste pr´avˇe tehdy, kdyˇz slunce sv´ıt´ı. Slunce nesv´ıt´ı a na obloze jsou mraky. Jestliˇze jsou na obloze mraky, pak teplota roste. Proto dnes nebude prˇset. 6. Jestliˇze si koup´ım nov´e auto, nepojedu na dovolenou. Jestliˇze si nekoup´ım nov´e auto, koup´ım si motocykl. Proto bud’ pojedu na dovolenou nebo si koup´ım motocykl (nebo oboje). (Smyslem t´eto u ´lohy je procviˇcen´ı pˇrepisu sloˇzen´ ych v´ yrok˚ u do jazyka v´ yrokov´e logiky a procviˇcen´ı s´emantiky logick´ ych spojek.) ´ Uloha 2.2 Ovˇeˇrte, ˇze pravidla nahrazen´ı jsou ekvivalence. ´ Uloha 2.3 Ovˇeˇrte, ˇze pravidla odvozov´an´ı jsou platn´e u ´sudkov´a formy. ´ Uloha 2.4 Zkonstruujte d˚ ukazy n´asleduj´ıc´ıch u ´sudk˚ u. 1. Je-li Jarek v Paˇr´ıˇzi, pak je Maruˇska v New Yorku. Jarek je v Paˇr´ıˇzi a Franta je ˇ ımˇe. Proto je Maruˇska v New Yorku. v R´ 7
2. Jestliˇze m´a Marek pravdu, nezamˇestnanost se zv´ yˇs´ı, a jestli m´a Aniˇcka pravdu, bude tuh´a zima. Aniˇcka m´a pravdu. Proto se bude zvyˇsovat nezamˇestnanost, nebo bude tuh´a zima, nebo oboj´ı. 3. Jestliˇze bude l´eto tepl´e, nepojedeme v srpnu na dovolenou. Pojedeme v srpnu na dovolenou nebo si koup´ıme nov´e auto (nebo oboj´ı). Proto plat´ı, ˇze kdyˇz bude l´eto tepl´e, koup´ıme si auto. 4. Jestliˇze bude p´ıt v´ıno nebo j´ıst s´ yr, bude ji bolet hlava. Bude p´ıt v´ıno a j´ıst ˇcokol´adu. Proto ji bude bolet hlava. 5. Vraˇzda byla sp´ach´ana bud’ podezˇrel´ ym A nebo obˇema podezˇrel´ ymi B a C souˇcasnˇe. Jestliˇze A nebo B sp´achali vraˇzdu, pak byla obˇet’ otr´avena. Proto bud’ C sp´achal vraˇzdu nebo byla obˇet’ otr´avena. (Vyˇreˇsen´ım tˇechto cviˇcen´ı si student osvoj´ı pravidla nahrazen´ı a odvozen´ı nezbytn´a pro dalˇs´ı studium.)
8
Pˇ r´ıloha A: Tabulka pravidel nahrazen´ı a odvozov´ an´ı Ekvivalence
N´azev a zkratka komutativita (Com)
(α ∨ β) ≡ (β ∨ α) (α ∧ β) ≡ (β ∧ α)
asociativita (Assoc)
(α ∨ (β ∨ γ)) ≡ ((α ∨ β) ∨ γ) (α ∧ (β ∧ γ)) ≡ ((α ∧ β) ∧ γ)
distributivita (Dist)
(α ∨ (β ∧ γ)) ≡ ((α ∨ β) ∧ (α ∨ γ)) (α ∧ (β ∨ γ)) ≡ ((α ∧ β) ∨ (α ∧ γ)) ¬(α ∧ β) ≡ (¬α ∨ ¬β) ¬(α ∨ β) ≡ (¬α ∧ ¬β)
De Morganovy z´akony (De M)
α ≡ ¬¬α
dvoj´ı negace (DN) implikace (Impl)
(α → β) ≡ (¬α ∨ β)
obmˇena (Trans)
(α → β) ≡ (¬β → ¬α)
ekvivalence (Equiv)
(α ↔ β) ≡ ((α → β) ∧ (β → α)) (α ↔ β) ≡ ((α ∧ β) ∨ (¬α ∧ ¬β)) (α ∧ β) → γ ≡ α → (β → γ)
spojov´an´ı pˇredpoklad˚ u (Exp)
α∧α≡α α∨α≡α
Tautologie (Taut)
Premisy
Z´avˇer
a∧b a a, b a ∨ b, ¬a a → b, a a → b, ¬b a → b, b → c a→b (a → b) ∧ (c → d), a ∨ c
a a∨b a∧b b b ¬a a→c a → (a ∧ b) b∨d
N´azev a zkratka zjednoduˇsen´ı (Simp) souˇcet (Add) konjunkce (Conj) disjunktivn´ı sylogismus (DS) modus ponens (MP) modus tollens (MT) hypotetick´ y sylogismus (HS) absorpce (Abs) konstruktivn´ı dilema (CD)
9
Pˇ r´ıloha B: Metoda d˚ ukazu implikace ˇ Casto se m˚ uˇzeme setkat s u ´sudky, jejichˇz z´avˇery jsou v´ yroky ve tvaru implikace, napˇr. uvaˇzujme u ´sudek s premisami P1 , P2 , . . . , Pn a z´avˇerem ve tvaru P → Q, kde P1 , . . . , Pn , P, Q jsou nˇejak´e v´ yroky. Pˇr´ısluˇsn´ y form´aln´ı d˚ ukaz pak m˚ uˇze vypadat nˇejak takto: ˇ adek R´ 1 2
V´ yrok P1 P2 .. .
n (n + k)
Komen´aˇr premisa premisa
Pn .. .
premisa
P →Q
. . . koment´aˇr . . .
To se m˚ uˇze prakticky uk´azat jako obt´ıˇzn´e. Snazˇs´ı by bylo dokazovat platnost u ´sudku s premisami P1 , . . . , Pn , P a z´avˇerem Q. Uk´aˇzeme si, ˇze p˚ uvodn´ı u ´sudek je platn´ y pr´avˇe tehdy, kdyˇz je platn´ y tento druh´ yu ´sudek. ´ Provedeme n´asleduj´ıc´ı u ´vahu: Usudek s premisami P1 , P2 , . . . , Pn a z´avˇerem ve tvaru P → Q je platn´ y pr´avˇe tehdy, kdyˇz pˇr´ısluˇsn´a u ´sudkov´a forma je platn´a, tzn. formule (p1 ∧ . . . ∧ pn ) → (p → q) je tautologi´ı (kde P1 , . . . , Pn , P, Q jsou instancemi formul´ı p1 , . . . , pn , p, q). S vyuˇzit´ım pravidla spojov´an´ı pˇredpoklad˚ u, tzn. ekvivalence p → (q → r) ≡ (p ∧ q) → r zjiˇstujeme, ˇze je tato formule ekvivalentn´ı s formul´ı (p1 ∧ . . . ∧ pn ∧ p) → q. Posledn´ı formule je ale tautologi´ı pr´avˇe tehdy, kdyˇz u ´sudkov´a forma s premisami p1 , . . . , pn , p a z´avˇerem q je platn´a, tzn. pr´avˇe tehdy kdyˇz je u ´sudek s premisami P1 , . . . , Pn , P a z´avˇerem Q je platn´ y. Form´aln´ı d˚ ukaz u ´sudku s premisami P1 , . . . , Pn , P a z´avˇerem Q budeme zapisovat n´asledovnˇe: ˇ adek R´ 1 2
V´ yrok P1 P2 .. .
n n+1
Pn P .. .
n+k n+k+1
Q P →Q
Komen´aˇr premisa premisa premisa (CP) . . . koment´aˇr . . . (CP), ˇra´dky n + 1 aˇz n + k
Zkratka (CP) znamen´a conditional proof.
10
