Logika I. RNDr. Kateˇrina Trlifajov´a PhD. Katedra teoretick´ e informatiky Fakulta informaˇ cn´ıch technologi´ı ˇ e vysok´ Cesk´ e uˇ cen´ı technick´ e v Praze c
Kateˇ rina Trlifajov´ a, 2010
BI-MLO, ZS 2011/12
Evropsk´ y soci´ aln´ı fond. Praha & EU: Investujeme do vaˇs´ı budoucnosti ˇ RNDr. Kateˇrina Trlifajov´ a PhD. (FIT CVUT)
Logika I.
BI-MLO, ZS 2011/12
1 / 36
Logika I. V´yznam, historie, jazyk, formule Formule v´yrokov´e logiky. Pravdivostn´ı tabulky. Tautologie, kontradikce, splnitelnost.
ˇ RNDr. Kateˇrina Trlifajov´ a PhD. (FIT CVUT)
Logika I.
BI-MLO, ZS 2011/12
2 / 36
Literatura ˇ Svejdar, V., Logika - ne´ uplnost, sloˇzitost a nutnost, Academia, Praha, 2002. Sochor, A., Logika pro vˇsechny ochotn´e myslet, Karolinum, Praha, 2011. ˇ Demlov´a, M., Mathematical Logic, CVUT, Praha: Kernberg Publishing, 2008 Mendelson, E. Introduction to Mathematical Logic, Chapman and Hall, 1997. Copi, I.M. Symbolic Logic, The Macmilian Company, London, 1967. Smullyan, R., Jak se jmenuje tahle kn´ıˇzka?, Navˇeky nerozhodnuto, Satan, Cantor a nekoneˇcno, ...
ˇ RNDr. Kateˇrina Trlifajov´ a PhD. (FIT CVUT)
Logika I.
BI-MLO, ZS 2011/12
3 / 36
V´yznam logiky
ˇ RNDr. Kateˇrina Trlifajov´ a PhD. (FIT CVUT)
Logika I.
1
Spr´avn´e logick´e u ´sudky v pˇrirozen´em jazyce.
2
Zkoum´an´ı logick´ych z´akon˚ u
3
Zkoum´an´ı logick´ych syst´em˚ u.
BI-MLO, ZS 2011/12
4 / 36
Jestliˇze jsem nemocn´y, m´am horeˇcku. M´am horeˇcku. Jsem tedy nemocn´y. Ne. Vˇsichni studenti jsou inteligentn´ı. Nˇekteˇr´ı inteligentn´ı lid´e jsou podiv´ıni. Plyne z toho, ˇze nˇekteˇr´ı studenti jsou podiv´ıni? Ne. Jedin´a kniha, kterou jsem kdy ˇcetl, je P´an prsten˚ u. Co je opakem tohoto tvrzen´ı neboli co plat´ı, jestliˇze lˇzu? Neˇcetl jsem ˇz´adnou knihu, nebo jsem ˇcetl jinou knihu, nebo jsem ˇcetl jeˇstˇe dalˇs´ı knihu.
ˇ RNDr. Kateˇrina Trlifajov´ a PhD. (FIT CVUT)
Logika I.
BI-MLO, ZS 2011/12
5 / 36
1
ˇ Antick´e Recko (6. - 3. stol. pˇr. Kr.)
2
Stˇredovˇek (11. - 13. stolet´ı)
3
Modern´ı logika (19. - 20. stolet´ı)
Tam tak´e v Egyptˇe byla poprv´e objevena dialektika. Parmenid´es se vyh´ybal mˇest˚ um a lidem, str´avil dlouhou dobu na sk´ale aby promyslel dialektiku . (Hugo ze St.Victor, 12. stol.) Dialektika (dialegesthai = diskutovat)
ˇ RNDr. Kateˇrina Trlifajov´ a PhD. (FIT CVUT)
Logika I.
BI-MLO, ZS 2011/12
6 / 36
Parmenid´es a Zen´on
Parmenid´ es - nen´ı mnohost, je jen jedno Zen´ on - paradoxy Je-li jsoucen mnoho, je nutno, aby jich bylo tolik, kolik jich jest, ani v´ıce, ani m´enˇe. A je-li jich tolik, kolik jich jest, byla by poˇctem omezena. Je-li jsoucen mnoho, jsou poˇctem neomezena, neboˇt vˇzdy jsou mezi jsoucny jin´a a mezi tˇemi zas jin´a, a tak jsou poˇctem neomezena. Je-li nemoˇzno, aby byla mnohost, a je-li nutno, aby bylo budˇ jedno, nebo mnohost, a nem˚ uˇze-li b´yti mnohost, zb´yv´a, ˇze je jedno.
ˇ RNDr. Kateˇrina Trlifajov´ a PhD. (FIT CVUT)
Logika I.
BI-MLO, ZS 2011/12
7 / 36
Aristotel´es
ˇ RNDr. Kateˇrina Trlifajov´ a PhD. (FIT CVUT)
Z´ akladn´ı z´ akony logiky z´ akon vylouˇcen´ı sporu z´ akon vylouˇcen´eho tˇret´ıho z´ akon identity
Logika I.
BI-MLO, ZS 2011/12
8 / 36
Aristotelsk´e typy soud˚ u S je P. Vˇsechna/nˇekter´a S jsou/nejsou P. Kladn´ e
Z´ aporn´ e
Obecn´ e
A Vˇsechna s jsou p. Vˇsechny koˇcky jsou ˇselmy.
E ˇ Z´adn´a s nejsou p. ˇadn´e koˇcky nejsou ˇselmy. Z´
ˇ asteˇ C´ cn´ e
I Nˇekter´a s jsou p. Nˇekter´e koˇcky jsou ˇselmy.
O Nˇekter´a s nejsou p. Nˇekter´e koˇcky nejsou ˇselmy.
Kontradikce: A a O, E a I. Subsumpce: z A plyne I, z E plyne O. ˇ RNDr. Kateˇrina Trlifajov´ a PhD. (FIT CVUT)
Logika I.
BI-MLO, ZS 2011/12
9 / 36
Sylogistika
Ze dvou soud˚ u (pˇredpoklad˚ u) odvod´ıme tˇret´ı soud (z´avˇer). Kdy je platn´y? Kaˇzd´a koˇcka je ˇselma. Kaˇzd´a ˇselma je zv´ıˇre. Tud´ıˇz kaˇzd´a koˇcka je zv´ıˇre. BARBARA. ˇadn´y ˇclovˇek nen´ı zv´ıˇre. Z´ Nˇekter´e zv´ıˇre je ˇselma. Tud´ıˇz nˇekter´a ˇselma nen´ı ˇclovˇek. FRESISON. Tud´ıˇz nˇekter´y ˇclovˇek nen´ı ˇselma.
ˇ RNDr. Kateˇrina Trlifajov´ a PhD. (FIT CVUT)
Logika I.
BI-MLO, ZS 2011/12
10 / 36
Megarsk´a ˇskola
Eubulides, Diodoros z Kronu, Filo z Megary (4. stol. B.C.) ˇ ek o sobˇe ˇr´ık´a, ˇze lˇze. Mluv´ı pravdu nebo lˇze? Clovˇ ˇ ek, kter´y m´a hlavu porostlou vlasy, nen´ı holohlav´y. Vytrhneme-li Clovˇ mu jeden vlas, nestane se holohlav´ym. Avˇsak pokraˇcujeme-li v tomto procesu, holohlav´ym se ˇcasem stane. Co jsi neztratil, to m´aˇs. Ale neztratil jsi rohy. Tedy je m´aˇs. Tento ˇclovˇek je ˇsvec. Tento ˇclovˇek je dobr´y. Tud´ıˇz tento ˇclovˇek je dobr´y ˇsvec.
ˇ RNDr. Kateˇrina Trlifajov´ a PhD. (FIT CVUT)
Logika I.
BI-MLO, ZS 2011/12
11 / 36
Stoicko-megarsk´a ˇskola
Zen´ on z Kitia, Chrysippos (4. - 3. stol. B.C.) 1
Jestliˇze prv´e, pak druh´e, avˇsak prv´e, tud´ıˇz druh´e.
2
Jestliˇze prv´e, pak druh´e, avˇsak ne druh´e, tud´ıˇz ne prv´e.
3
Ne z´aroveˇ n prv´e a druh´e, avˇsak prv´e, tud´ıˇz ne druh´e.
4
Budˇ jen prv´e, nebo jen druh´e, ale prv´e, tud´ıˇz ne druh´e.
5
Budˇ jen prv´e, nebo jen druh´e, ale ne druh´e, tud´ıˇz prv´e.
ˇ RNDr. Kateˇrina Trlifajov´ a PhD. (FIT CVUT)
Logika I.
BI-MLO, ZS 2011/12
12 / 36
G.W.Leibniz (1646 - 1718)
Mathesis universalis. Univers´aln´ı jazyk characteristica universalis Platn´a odvozovac´ı pravidla calculus ratiocinator Ariadnina niˇt: Calculemus!
ˇ RNDr. Kateˇrina Trlifajov´ a PhD. (FIT CVUT)
Logika I.
BI-MLO, ZS 2011/12
13 / 36
B. Bolzano (1781 - 1848)
A1 : Existuje alespoˇ n jedna pravdiv´a vˇeta. An+1 : Vˇeta An je pravdiv´a. Existuje nekoneˇcnˇe pravdiv´ych vˇet. Vˇedoslov´ı. O logice.
ˇ RNDr. Kateˇrina Trlifajov´ a PhD. (FIT CVUT)
Logika I.
BI-MLO, ZS 2011/12
14 / 36
G. Frege (1848 - 1925) Formalizace jazyka: spojky, kvantifik´atory, promˇenn´e, relace Axiomatick´y syst´em: 6 axiom˚ u + 1 odvozovac´ı pravidlo D˚ ukaz: posloupnost formul´ı. Logicismus. Begrifftschrift, Die Grundlagen der Arithmetik.
ˇ RNDr. Kateˇrina Trlifajov´ a PhD. (FIT CVUT)
Logika I.
BI-MLO, ZS 2011/12
15 / 36
D. Hilbert (1862 - 1943)
Hilbert˚ uv program Formalizace matematick´ych i jin´ych discipl´ın. Pˇreveden´ı do axiomatick´eho tvaru. D˚ ukaz bezespornosti form´aln´ıho syst´emu.
ˇ RNDr. Kateˇrina Trlifajov´ a PhD. (FIT CVUT)
Logika I.
BI-MLO, ZS 2011/12
16 / 36
Kurt G˝odel (1906 - 1978)
Vˇety o ne´ uplnosti. V kaˇzd´e teorii T, kter´a obsahuje aritmetiku, existuje nedokazateln´e tvrzen´ı. Nelze dok´azat bezespornost teorie obsahuj´ıc´ı aritmetiku.
ˇ RNDr. Kateˇrina Trlifajov´ a PhD. (FIT CVUT)
Logika I.
BI-MLO, ZS 2011/12
17 / 36
Neklasick´e logiky
Intuicionistick´ a logika: nepˇrij´ım´ a princip vylouˇcen´eho tˇret´ıho. Konstruktivistick´a matematika. (J.Brouwer) Mod´ aln´ı logika: pˇrid´ av´ a predik´ at “je moˇzn´e, je nutn´e ”. Je moˇzn´e, ˇze P = Nen´ı nutn´e, ˇze ne-P. Je nutn´e, ˇze P = Nen´ı moˇzn´e, ˇze ne-P (Aristotel´es, W.Ockham, J.D. Scottus, Saul Kripke) Fuzzy-logika: pravdivostn´ı hodnota v´ yroku leˇz´ı mezi 0 a 1. (L.Zadeh, J.Lukasiewicz, K.G¨ odel, P.H´ ajek, Pavelka)
ˇ RNDr. Kateˇrina Trlifajov´ a PhD. (FIT CVUT)
Logika I.
BI-MLO, ZS 2011/12
18 / 36
V´yrokov´a logika Definice Prvotn´ı v´yrok je jednoduch´a oznamovac´ı vˇeta, u kter´e m´a smysl se pt´at, zda je ˇci nen´ı pravdiv´a. Prvotn´ı v´yroky oznaˇcujeme velk´ymi tiskac´ımi p´ısmeny A, B, ...A1 , A2 , ..., kter´ym ˇr´ık´ame prvotn´ı formule. A: Je rok 2011. B: 2 + 2 = 5. C : Studuji FIT. P: Prˇs´ı. A1 : Bitva u Hastingsu byla v roce 1066. A2 : Bitva na B´ıl´e hoˇre byla v roce 1621. Mnoˇzina prvotn´ıch v´yrok˚ u: { Je rok 2011., 2 + 2 = 5., ... } Mnoˇzina prvotn´ıch formul´ı: {A, B, C , P, A1 , A2 } ˇ RNDr. Kateˇrina Trlifajov´ a PhD. (FIT CVUT)
Logika I.
BI-MLO, ZS 2011/12
19 / 36
Pravdivostn´ı hodnota Definice Pravdivostn´ı ohodnocen´ı mnoˇziny prvotn´ıch v´yrok˚ u je funkce v z mnoˇziny prvotn´ıch formul´ı do mnoˇziny {0, 1}. V´yroku A pˇriˇrad´ı pravdivostn´ı hodnotu 1, jestliˇze je pravdiv´y, v (A) = 1. V´yroku A pˇriˇrad´ı pravdivostn´ı hodnotu 0, jestliˇze je nepravdiv´y, v (A) = 0. A: Je rok 2011. v (A) = 1. B: 2 + 2 = 5. v (B) = 0. C : Studuji FIT. v (C ) = 1. P: Prˇs´ı. v (P) = 0 (?) K : P˚ ujdu do kina. (?) A1 : Bitva u Hastingsu byla v roce 1066. A2 : Bitva u B´ıl´e hory byla v roce 1621.
ˇ RNDr. Kateˇrina Trlifajov´ a PhD. (FIT CVUT)
Logika I.
v (A1 ) = 1. v (A2 ) = 0.
BI-MLO, ZS 2011/12
20 / 36
1. Negace
¬A: ”Nen´ı pravda, ˇze A.” ”A je nepravdiv´e.” A: Je rok 2011. v (A) = 1 ¬A: Nen´ı pravda, ˇze je rok 2011. Nen´ı rok 2011. B: 2 + 2 = 5. ¬B: 2 + 2 6= 5.
v (¬A) = 0
v (B) = 0 v (¬B) = 1 A 1 0
ˇ RNDr. Kateˇrina Trlifajov´ a PhD. (FIT CVUT)
¬A 0 1
Logika I.
BI-MLO, ZS 2011/12
21 / 36
2. Konjunkce A ∧ B: ”A a B.” A ∧ C : Je rok 2011 a studuji FIT. v (A ∧ C ) = 1 A1 ∧ A2 : Bitva u Hastingsu byla v roce 1066 a bitva na B´ıl´e hoˇre v roce 1621. v (A1 ∧ A2 ) = 0 A 1 1 0 0
ˇ RNDr. Kateˇrina Trlifajov´ a PhD. (FIT CVUT)
B 1 0 1 0
A∧B 1 0 0 0
Logika I.
BI-MLO, ZS 2011/12
22 / 36
3. Disjunkce A ∨ B: ”A nebo B.” A ∨ C : Je rok 2011 nebo studuji FIT. v (A ∨ C ) = 1 A1 ∨ A2 : Bitva u Hastingsu byla v roce 1066 nebo bitva na B´ıl´e hoˇre v roce 1621. v (A1 ∨ A2 ) = 1 A 1 1 0 0
ˇ RNDr. Kateˇrina Trlifajov´ a PhD. (FIT CVUT)
B 1 0 1 0
A∨B 1 1 1 0
Logika I.
BI-MLO, ZS 2011/12
23 / 36
4. Implikace A ⇒ B: ”Z A plyne B.” ”Jestliˇze A, pak B”. ”A implikuje B.” P: Prˇs´ı. K : Jdu do kina. P ⇒ K : Jestliˇze prˇs´ı, pak jdu do kina. Prˇs´ı a jdu do kina.
v (P ⇒ K ) = 1
Neprˇs´ı a jdu do kina.
v (P ⇒ K ) = 1
Prˇs´ı a nejdu do kina.
v (P ⇒ K ) = 0 v (P ⇒ K ) = 1
Neprˇs´ı a nejdu do kina. A 1 1 0 0 ˇ RNDr. Kateˇrina Trlifajov´ a PhD. (FIT CVUT)
B 1 0 1 0
A⇒B 1 0 1 1
Logika I.
BI-MLO, ZS 2011/12
24 / 36
5. Ekvivalence A ⇔ B: ”A pr´avˇe tehdy, kdyˇz B.” ”A tehdy a jen tehdy, kdyˇz B.” ”A je ekvivalentn´ı s B.” P ⇔ K : Jdu do kina pr´avˇe tehdy, kdyˇz prˇs´ı. Jdu do kina vˇzdy, kdyˇz prˇs´ı. Jdu do kina a prˇs´ı. v (P ⇔ K ) = 1 Jdu do kina a neprˇs´ı. v (P ⇔ K ) = 0 Nejdu do kina a prˇs´ı. v (P ⇔ K ) = 0 Nejdu do kina a neprˇs´ı. v (P ⇔ K ) = 1 A 1 1 0 0 ˇ RNDr. Kateˇrina Trlifajov´ a PhD. (FIT CVUT)
B 1 0 1 0
A⇔B 1 0 0 1
Logika I.
BI-MLO, ZS 2011/12
25 / 36
Formule v´yrokov´e logiky Definice Jazyk v´yrokov´e logiky obsahuje: mnoˇzina prvotn´ıch formul´ı A, B, C , ..., logick´e spojky ¬, ∧, ∨, ⇒, ⇔, z´avorky ( , ).
Definice V´yrokov´a formule: I. Prvotn´ı formule je v´yrokov´a formule. II. Jsou-li A, B v´yrokov´e formule, pak jsou i ¬A, (A ∧ B), (A ∨ B), (A ⇒ B), (A ⇔ B) v´yrokov´e formule. III. Kaˇzd´a v´yrokov´a formule vznikne koneˇcn´ym uˇzit´ım pravidel I. a II.
ˇ RNDr. Kateˇrina Trlifajov´ a PhD. (FIT CVUT)
Logika I.
BI-MLO, ZS 2011/12
26 / 36
Pravdivostn´ı hodnota
Definice Je-li d´ano pravdivostn´ı ohodnocen´ı prvotn´ıch formul´ı, pak pravdivostn´ı hodnotu v´yrokov´e formule urˇc´ıme dle n´asleduj´ıc´ı tabulky: A 1 1 0 0
B 1 0 1 0
¬A 0 0 1 1
ˇ RNDr. Kateˇrina Trlifajov´ a PhD. (FIT CVUT)
A∧B 1 0 0 0
A∨B 1 1 1 0
Logika I.
A⇒B 1 0 1 1
A⇔B 1 0 0 1
BI-MLO, ZS 2011/12
27 / 36
Pravdivostn´ı tabulky pro dvˇe prvotn´ı formule A ⇔ (B ∧ ¬A) A 1 1 0 0
B 1 0 1 0 A 1 1 0 0
¬A 0 0 1 1 ⇔ 0 0 0 1
B ∧ ¬A 0 0 1 0 (B 1 0 1 0
(A ⇔ (B ∧ ¬A)) 0 0 0 1 ∧ 0 0 1 0
¬ 0 0 1 1
A) 1 1 0 0
¬A ∧ ¬B ˇ RNDr. Kateˇrina Trlifajov´ a PhD. (FIT CVUT)
Logika I.
BI-MLO, ZS 2011/12
28 / 36
Pravdivostn´ı tabulky pro tˇri prvotn´ı formule
A ⇒ (¬B ∧ C ) A 1 1 1 1 0 0 0 0
ˇ RNDr. Kateˇrina Trlifajov´ a PhD. (FIT CVUT)
⇒ 0 0 1 0 1 1 1 1
(¬ 0 0 1 1 0 0 1 1
Logika I.
B 1 1 0 0 1 1 0 0
∧ 0 0 1 0 0 0 1 0
C) 1 0 1 0 1 0 1 0
BI-MLO, ZS 2011/12
29 / 36
Pravdivostn´ı tabulky pro n prvotn´ıch formul´ı
1 prvotn´ı formule - 2 ˇr´adky tabulky 2 prvotn´ı formule - 4 ˇr´adky tabulky 3 prvotn´ı formule - 8 ˇr´adek tabulky n prvotn´ıch formul´ı - 2n moˇzn´ych ohodnocen´ı - 2n ˇr´adk˚ u tabulky
ˇ RNDr. Kateˇrina Trlifajov´ a PhD. (FIT CVUT)
Logika I.
BI-MLO, ZS 2011/12
30 / 36
Ostrov poctivc˚ u a padouch˚ u Poctivci mluv´ı vˇzdy pravdu, padouˇsi vˇzdy lˇzou. 1
2
Zde m´ame dva obyvatele ostrova A,B. A prohl´as´ı: ”Pokud je B poctivec, pak j´a jsem padouch.” - A ⇔ (B ⇒ ¬A). ˇ j´a jsem padouch nebo je B poctivec.” Tentokr´at A ˇrekne: ”Bud - A ⇔ (¬A ∨ B).
3
Potkal jsem dva, kteˇr´ı odpoˇc´ıvali pod stromem. Zeptal jsem se: ”Je ˇ na svou mezi v´ami poctivec?” Odpovˇedˇel, a j´a znal spr´avnou odpovˇed ot´azku. Kdo byl ten, kter´eho jsem se zeptal? A co ten druh´y?
4
Jste v jeskyni na ostrovˇe poctivc˚ u a padouch˚ u. Z t´eto jeskynˇe vedou dva v´ychody. Jeden v´ychod vede na svobodu, druh´y na smrt. Pˇred kaˇzd´ym z nich stoj´ı domorod´y str´aˇzce. M˚ uˇzete mu poloˇzit pouze jednu ot´azku, abyste se dozvˇedˇel/a, jak se zachr´anit. Jakou?
ˇ RNDr. Kateˇrina Trlifajov´ a PhD. (FIT CVUT)
Logika I.
BI-MLO, ZS 2011/12
31 / 36