12

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