ZÁKLADY MATEMATICKÉ LOGIKY (Provizorní text)
1. Úvod, výroková logika Logika je v da o správném usuzování, o um ní správné argumentace. Obecn m žeme úsudek charakterizovat následujícím schématem: Na základ pravdivosti tvrzení v1, …, vn usoudíme, že je pravdivý i výrok v. Zapisujeme schématicky: v1 v2 …
p edpoklady neboli premisy
vn –––––– v
záv r
V praxi používáme r zné druhy takovýchto úsudk , ovšem ne všemi se zabývá logika. Nap . se obecn nezabývá tzv. pravd podobnostními úsudky, nap .: Slunce doposud vyšlo každý den.
Slunce (pravd podobn ) vyjde i zítra.
Podobn se nezabývá úsudky generalizací: Všechny labut , které jsme dosud vid li, jsou bílé.
Všechny labut jsou bílé.
V t chto p ípadech je záv rem jen hypotéza (tvrzení, jehož pravdivost nemáme ov enou), tato metoda vytvá ení hypotéz se nazývá neúplná indukce. Intuitivní, neformální, živé myšlení v tšiny lidí v tšinou dodržuje zákony logiky, aniž by lidé tyto zákony nutn znali a jejich používání si explicitn uv domovali. Podobn lidé dokáží gramaticky správn se vyjad ovat ve svém mate ském jazyce, aniž by nutn znali a um li formulovat gramatická pravidla, jimiž se používání jazyka ídí. P irozený jazyk je nenahraditelným nástrojem b žné komunikace, má však své slabiny,které vyniknou, chceme-li formulovat v decké poznatky. Mezi typické rysy p irozeného jazyka pat í významová nejednozna nost jeho mnohých termín (nap . slova „velký,“ „dobro,“ apod.). Homonymie: jedno a totéž slovo nabývá více význam (nap . „zámek,“ ... ). Synonymie: jediný nositel – denotát – je ozna ován r znými termíny, nap . „Venuše,“ „Jit enka“ a „Ve ernice“ jsou r zná ozna ení téže planety. V logice užíváme formální jazyky, které využívají symbol vymezených pravidel. -1-
a jejich z et zení podle p esn
Výrok je každé srozumitelné sd lení, o kterém má smysl íci, že je bu pravdivé a nebo nepravdivé. (Není d ležité, zda to mohu rozhodnout práv te , ale zda má smysl o pravdivosti rozhodovat.) 1.1. P íklady výrok : Venku padá sníh. Baví m matematika. Na Marsu existují živé organismy. Zítra bude v eských Bud jovicích pršet. íslo 7 je d litelné 4. Výroky ozna ujeme výrokovými prom nnými, používáme malá písmena: a, b, p, q, r, ..... Výroková prom nná je symbol, který zastupuje n jaký možný jednoduchý výrok. Výroková konstanta je symbol, kterým zapisujeme konkrétní jednoduchý výrok. Výroky mohou být bu pravdivostní hodnotu.
pravdivé nebo nepravdivé. Jednotlivým výrok m p i adíme jejich
Výrok pravdivý má pravdivostní hodnotu 1 Výrok nepravdivý má pravdivostní hodnotu 0 Ke každému výroku lze vytvo it jeho negaci. Je-li p p vodní výrok , pak jeho negaci zna íme ¬ p a definujeme pomocí pravdivostní tabulky: ¬p 0 1
p 1 0
Negace výroku je výrok, který je nepravdivý, je-li výrok p pravdivý, a který je pravdivý, je-li výrok p nepravdivý. Negování výroku znamená, že z výroku p utvo íme výrok ¬ p. Je to unární operace s výrokem p. 1.2. a) Pro každý ádek tabulky rozhodn te, zda je výrok v pravém sloupci negací výroku v levém sloupci. Není-li tomu tak, zformulujte správnou negaci. Prší. Aspo t i žáci dnes chybí.
Svítí slunce. Aspo t i žáci dnes nechybí.
Dané íslo je záporné. Všichni lžou. P ijdu nejpozd ji v deset hodin. N kdo k i í.
Dané íslo je kladné. Nikdo nelže. P ijdu nejd íve v 11 hodin. N kdo nek i í.
Dané dv p ímky v rovin jsou rovnob žné. Dané dv p ímky v prostoru jsou rovnob žné.
Dané dv p ímky v rovin jsou r znob žné. Dané dv p ímky v prostoru jsou r znob žné.
b) Co lze zjistit o Kré anech, jestliže Kré an ekne: „Nev te Kré an m, všichni Kré ané lžou.“ Jestliže dva výroky spojíme v jediný pomocí vhodné logické spojky, hovo íme o binární operaci s výroky. Analogicky definujeme ternární operaci pro t i výroky, obecn pak m-ární operaci pro m výrok . Složené výroky tedy vznikají ze dvou a více výrok pomocí logických spojek (výrokotvorných funktor ). -2-
p 1 1 0 0
Konjunkce: ∧ teme: p a q. Konjunkce výrok p, q je výrok, který je pravdivý pouze tehdy, jsou-li pravdivé oba výroky p, q.
Disjunkce: ∨
q 1 0 1 0
p∧q 1 0 0 0
teme: p nebo q.
Disjunkce výrok p, q : Výrok, který je pravdivý práv tehdy, když je alespo jeden z výrok p, q pravdivý. Ostrá disjunkce: ∨
teme: Bu p nebo q.
Ostrá disjunkce výrok p, q : Výrok, který je pravdivý práv tehdy, když je pravdivý práv jeden z výrok p, q. p 1 1 0 0
q 1 0 1 0
p 1 1 0 0
p∨q 1 1 1 0
q 1 0 1 0
p∨q 0 1 1 0
Význam spojek „a“ a „nebo“ se m že v hovorovém jazyce lišit od významu ve výrokové logice! Nap íklad: V ty „Petr se ude il do hlavy a upadl“ a „Petr upadl a ude il se do hlavy“ znamenají ve výrokové logice totéž, kdežto v hovorovém jazyce je mezi nimi rozdíl. (První v tu si v hovorovém jazyce vyložíme tak, že Petr se nejprve ude il do hlavy a v d sledku toho upadl. Podle druhé v ty však Petr nejprve upadl a v d sledku toho se ude il do hlavy.)
Implikace: =>
teme: Jestliže p, pak q nebo: p implikuje q nebo: platí-li p, pak platí q Výrok q n kdy ozna ujeme jako p edpoklad, výrok q jako záv r. íkáme také, že z p edpokladu p plyne záv r q. Implikace je však výrok . Nem li bychom ji ztotož ovat s úsudkem o vyplývání.
P 1 1 0 0
q 1 0 1 0
p q 1 0 1 1
Implikace výrok p, q : Výrok, který je nepravdivý pouze tehdy, když je výrok p pravdivý a výrok q nepravdivý. (Z nepravdivého p edpokladu plyne jakýkoliv záv r.) 1.3. a) Pomocí pravdivostní tabulky dokažte, že z následujících úsudk jsou správné jen ty, které jsou vytišt né tu n . p platí p q platí q platí
p neplatí p q platí q neplatí
q platí p q platí p platí -3-
q neplatí p q platí p neplatí
b) Sv dek vyslovil výrok „Jestliže je vinen obžalovaný A, pak je vinen i obžalovaný B.“ Ve kterých z následujících ty možných situací m l sv dek pravdu? ) A je vinen a B je vinen, ) A je vinen a B není vinen, ) A není vinen a B je vinen, ) A není vinen a B není vinen. c) Úlohy o padouších a poctivcích. Na jednom ostrov žijí jen padouši a poctivci. Padouši za všech okolností lžou, poctivci vyslovují vždy jen pravdivé výroky. Uvažujme libovolné dva obyvatele ostrova, ozna me je A, B. ) [S 109] A íká: „Pokud jsem poctivec, pak B je taky poctivec.“ Lze jednozna n ur it, co je A a co je B? ) [S 110] Zeptáte se A: „Jste poctivec?“ A odpoví: „Když jsem poctivec, tak sním sv j klobouk!“ Dokažte, že A musí sníst sv j klobouk. ) [S 111] A ekne: „Jestliže jsem poctivec, pak dv a dv jsou ty i.“ Je to poctivec, nebo padouch? ) [S 112] A ekne: „Jestliže jsem poctivec, pak dv a dv je p t.“ Je to poctivec, nebo padouch? ) [S 113] A ekne: „Pokud je B poctivec, tak já jsem padouch.“ Co je A a co je B? ) [S 115] Máme t i obyvatele ostrova: A, B a C. A ekne „B je poctivec“ a B íká: „Pokud je A poctivec, tak je poctivec i C.“ Dá se ur it, co jsou A, B a C za ? c) Logika a láska. ) [S 116] Víme,že jsou pravdivé výroky: (1) Miluji B tku nebo miluji Janu. (2) Pokud miluji B tku, pak miluji Janu. Vyplývá z nich, že miluji B tku? Vyplývá z nich, že miluji Janu? ) [S 117] Dejme tomu, že se m kdosi zeptá: "Je to vážn pravda, že pokud miluješ B tku, pak taky miluješ Janu?" Odpovím mu podle pravdy: "Jestliže je to pravda, tak miluji B tku." Vyplývá z toho, že miluji B tku? Vyplývá z toho, že miluji Janu? ) [S 118] Tentokrát máme dv dívky, Evu a Markétu. N kdo se m zeptá: "Je to vážn pravda, že pokud miluješ Evu, miluješ i Markétu?" Odpovím mu podle pravdy: "Jestliže je to pravda, miluji Evu, a jestliže miluji Evu, je to pravda." Kterou z dívek miluji? ) [S 119] Tentokrát máme t i dívky, lvu, Marii a Danu. Situace je složitá: (1) Miluji aspo jednu z t ch t í dívek. (2) Pokud miluji lvu, ale ne Danu, pak miluji Marii. (3) Bu miluji Danu i Marii, nebo nemiluji ani jednu z nich. (4) Pokud miluji Danu, pak taky miluji lvu. Kterou z dívek miluji? -4-
Ekvivalence: <=>
p 1 1 0 0
teme: p práv tehdy, když q p, práv když q p tehdy a jen tehdy, když q p je ekvivalentní s q
q 1 0 1 0
p⇔q 1 0 0 1
Ekvivalence výrok p, q : Výrok, který je pravdivý pouze v p ípadech, kdy oba výroky p, q mají stejnou pravdivostní hodnotu. Všimn te si, že ekvivalenci lze chápat jako „oboustrannou implikaci“. p 1 1 0 0
q 1 0 1 0
p q 1 0 1 1
q p 1 1 0 1
(p q)∧(q p) 1 0 0 1
Abeceda výrokové logiky ur uje, jaké symboly m žeme používat k vytvá ení složit jších výrok . 1) Znaky pro výrokové prom nné p, q, r, s, .......... 2) Znaky pro funktory ∧,∨, ∨, , ⇔, ¬ 3) Pomocné znaky ( ), [ ], { } ................. závorky
Pomocí t chto znak m žeme tvo it výrokové formule. Nap íklad: ¬ (p ∧ q) ¬ (p∨)
r
je výroková formule není výroková formule (Jsou použity znaky z abecedy výrokové logiky, ale nejsou uspo ádány podle daných pravidel.)
Následující definice ur uje, kdy užitím znak výrokové logiky vznikne výroková formule. Výroková formule: a) Každá výroková prom nná p, q, r,...... je výrokovou formulí. b) Jestliže n jaké výrazy α, β jsou výrokovými formulemi, potom i výrazy ¬ α, α ∧ β, α ∨ β, α ∨ β, α β a α ⇔ β jsou výrokové formule. c) Žádné jiné výrazy nejsou výrokové formule. -5-
Aby byly složené výrokové formule jednozna n ur eny, používáme v zápisech závorky. Tyto zápisy lze zjednodušit podle t chto pravidel: 1. Spojka ¬ má p ednost p ed všemi ostatními logickými spojkami. 2. Znaky ∧, ∨ jsou rovnocenné a mají p ednost p ed rovnocennými znaky , ⇔.
Pravdivostní ohodnocení výrokové formule Podle definice každá výroková formule obsahuje výrokové prom nné. Nap íklad formule (¬ p ∨ q) (¬ q ∧ p) obsahuje prom nné p, q. Provedeme pravdivostní ohodnocení výrokové formule, prom nným p i adíme možné pravdivostní hodnoty. Všechny vzájemné možnosti pravdivostního ohodnocení uvedeme v tabulce. Jestliže výroková formule obsahuje n prom nných, bude mít tabulka 2n ádk . p 1 1 0 0
q 1 0 1 0
¬p ¬q 0 0 0 1 1 0 1 1
¬p∨ q 1 0 1 1
¬q∧ p 0 1 0 0
(¬ p ∨ q)
0 1 0 0
(¬ q ∧ p)
P i vyhodnocení mohou nastat 3 možnosti: a) Pro všechny pravdivostní hodnoty výrokových prom nných vznikne z výrokové formule výrok za všech okolností pravdivý. Taková výroková formule se nazývá tautologie. b) Pro všechny pravdivostní hodnoty výrokových prom nných vznikne z výrokové formule výrok za všech okolností nepravdivý. Taková výroková formule se nazývá kontradikce. c) Pro n které pravdivostní hodnoty vznikne výrok pravdivý a pro n které nepravdivý. Taková výroková formule se nazývá splnitelná formule. Jaký typ formule je uveden v p íkladu? Pro které hodnoty výrokových prom nných dostaneme pravdivý výrok? 1.4 Zjist te, zda jsou následující výrokové formule tautologie, kontradikce i splnitelné formule. a) ¬ (¬ ¬a) ⇔a, d) (¬ ¬a∨¬ ¬b)
b) (a ∧b)
(a ∨b),
¬ (¬ ¬a∨b),
g) a∨(b∧c) ⇔ (a∨b) ∧(a∨c) i) {a
(b∧c)} ⇔ {(a b) ∧(a c)}
c) (¬ ¬a
b) ⇔(a∨b),
e) a∨(b∨c) ⇔ (a∨b)∨c
f) a∧ (b∧c) ⇔ (a∧b) ∧c
h) a∧ (b∨c) ⇔ (a∧b) ∨ (a∧c) j) {a
(b∨c) } ⇔ { (a b) ∨ (a c)} -6-
k) {a
(b c)} ⇔ {(a∧b)
c}
m) {a
(b⇔ ⇔c) } ⇔ {(a b) ⇔ (a c)}
Ozna íme-li po ad písmeny u, v formule v levém sloupci a pravém sloupci libovolného ádku p edchozí tabulky, pak u ⇔ v je tautologie. íkáme též, že u a v jsou logicky ekvivalentní formule. Definice. ekneme, že výrokové formule p, q jsou logicky ekvivalentní, když platí: (a) Každá výroková prom nná, která se vyskytuje v p, se vyskytuje i ve q a každá výroková prom nná, která se vyskytuje v q, se vyskytuje i v p. (b) Zadáme-li libovoln pravdivostní hodnoty všech výrokových prom nných, které se ve formulích p, q, vyskytují, platí p ⇔ q. Jsou-li formule p, q, logicky ekvivalentní, píšeme
p q.
Logicky ekvivalentní výroky m žeme navzájem zam ovat. Pro libovolnou výrokovou formuli lze mechanicky sestrojit tabulku pravdivostních hodnot této formule. Dále ukážeme, že platí i obrácené tvrzení: Nech n je p irozené íslo. Pak existuje 2n navzájem r zných n- lenných posloupností utvo ených z nul a jedni ek. Jestliže uspo ádáme všechny tyto posloupnosti do tabulky o 2n ádcích a n sloupcích a p idáme k takto vzniklé tabulce ješt jeden sloupec libovoln utvo ený z nul a jedni ek. Jestliže prvním n sloupc m tabulky p i adíme výrokové prom nné p1 , p1 , pn , pak lze z t chto prom nných a logických spojek zkonstruovat výrokovou formuli, jejíž pravdivostní hodnoty jsou jednozna n ur eny vzniklou tabulkou. Tato výroková formule není ur ena jednozna n .
P íklady P1. Pro n = 1 máme pro p1 ≡ p tabulku o dvou ádcích a jednom sloupci. P idáme druhý sloupec, pro n jž máme celkem ty i možnosti volby nul a jedni ek jako pravdivostních hodnot. Pro jednotlivé situace lze nap íklad zvolit q následujícím zp sobem: p
q
p
q
p
q
p
q
1
1
1
1
1
0
1
0
0
1
0
0
0
1
0
0
q: p∨ ∨¬p
q: ¬p
q: p⇔p
-7-
q: p∧ ∧¬p
P2. Pro n = 2 máme pro p1 a p2 tabulku o ty ech ádcích a dvou sloupcích. P idáme t etí sloupec, pro n jž máme celkem 16 možností volby nul a jedni ek jako pravdivostních hodnot. Pro jednoduchost uvádíme p ehled všech možností do jediné tabulky, v níž pro formule odpovídající p idaným sloupc m p i azujeme ozna ení q1 až q16. p1
p2
q1
q2
q3
q4
q5
q6
q7
q8
q9
q10
q11
q12
q13
q14
q15
q16
1
1
1
1
1
1
0
1
1
1
0
0
0
1
0
0
0
0
1
0
1
1
1
0
1
1
0
0
1
1
0
0
1
0
0
0
0
1
1
1
0
1
1
0
1
0
1
0
1
0
0
1
0
0
0
0
1
0
1
1
1
0
0
1
0
1
1
0
0
0
1
0
N které formule již známe: q2: p1∨p2, q4: p1
p2, q8: p1⇔p2, q12: p1∧p2, : q9: p1∨p2
Abychom nalezli postup, jak nalézt obecný postup vyjád ení formule qi pomocí formulí p1 a p2 , povšimn me si, že formule u: (¬a∧ ∧b) ∨( a∧ ∧c) sestavená z prom nných a, b, c, má tuto vlastnost: Pokud a neplatí, je u
b, pokud a platí, je u
c.
Tvrzení je z ejmé z tabulky pravdivosti: a
b
c
¬a∧ ∧b
a∧ ∧c
u: (¬a∧ ∧b) ∨( a∧ ∧c)
1
1
1
0
1
1
1
1
0
0
0
0
1
0
1
0
1
1
1
0
0
0
0
0
0
1
1
1
0
1
0
1
0
1
0
1
0
0
1
0
0
0
0
0
0
0
0
0
Pomocí tvrzení (v) nyní ukážeme postup vyjád ení formule q5 pomocí formulí p1 a p2 .
-8-
(v)
Formule q5 je definována tabulkou:
p1 p2 q5
P emístíme v ní ádky
p1 p2 q5 1
0
1
0
0
1
1
1
1
0
1
0
1
1
1
1
0
1
0
1
0
1
0
0
a vybarvíme:
Dále si p edstavíme p2 jako formuli a z v ty (v) a formule b, c budou dány tabulkami pravdivosti sestavenými z vybarvených sloupc : p1 1 0 Z P1 již víme
b 1 1
b: ¬ p1 ∨ p1
p1 1 0 a
c 0 1
c: ¬ p1
Položme ješt u ≡ q5 . Podle (1) platí q5 : ( ¬ p2 ∧ (¬ p1 ∨ p1 ) ) ∨ ( p2 ∧ ¬p1 ) .
Nalezenou formuli m žeme zjednodušit na tvar q5 : ¬ p2 ∨ ( p2 ∧ ¬ p1 ) . Je totiž ¬ p1 ∨ p1 tautologie,
proto mají formule ¬ p2 ∧ (¬p1 ∨ p1 ) a ¬ p2 za stejných podmínek stejnou pravdivostní hodnotu. Stejným zp sobem postupujeme p i vyjad ování kterékoliv jiné formule qi (definované tabulkou v horní ásti p edchozí stránky) pomocí formulí p1 a p2 . Tímto zp sobem dokážeme postupn vyjád it všechny formule q1, q2, ..., q16. Když tak u iníme, m žeme analogicky sestavit tabulku pravdivosti všech možností pro p1 , p2 , p3 , a vyjad ovat tabulkou definované formule jako formule vytvo ené z p1 , p2 a p3 pomocí výrokotvorných funktor .
1.5. Vyjád ete q13 a q3, resp. další zbývající formule qi z tabulky jako formule složené z formulí p1 a p2 .
Negace složených výrok Pro každý ádek tabulky dokažte, že výrok pravém sloupci je negací výroku v levém sloupci.
-9-
p∧q
¬p∨ ¬q
p∨q
¬p∧¬q
p∨q
p⇔q
p q
p∧¬q
p⇔q
p∨q , resp. (p∧¬q) ∨ (¬p∧q)
1.6 Podle pravidel p edchozí tabulky vyslovte negace výrok : a: P ijde Petr nebo Pavel. b: Jestliže p ijde Jana, p ijde i Michal. c: Karel p ijde práv tehdy, když p ijde Jan. d: P ijde Anna a Hana. p: Koupím si pomeran e a banány. q: Jestliže bude pršet, z stanu doma. r: Mám hlad a nemám žíze . s: Dané íslo je d litelné šesti, práv když je d litelné dv ma a t emi. t: P jdeme dál, jestliže nikdo není unaven. u: P ijde nejvýše jeden z dvojice Petr, Pavel. v: Jana nepojede bez Hany. m: Milan pojede, pojede-li Honza.
Obm na a obrácení implikace. Obrácením implikace p q nazýváme implikaci q Obm nou implikace p q nazýváme implikaci ¬q
p. ¬p.
Dokažte, že
Implikace a její obm na jsou logicky ekvivalentní: (p Implikace a její obrácení nejsou logicky ekvivalentní. - 10 -
q)
(¬q
¬p).
1.7 Vyslovte obm nu, obrácení a negaci t chto výrok : a) Je-li p irozené íslo d litelné šesti, pak je sudé. b) Jestliže budík nezazvoní, nep ijdu do školy v as. c) Jestliže je p irozené íslo n složené a není druhou mocninou, pak má aspo
ty i d litele.
d) Jestliže má ty úhelník ABCD aspo t i strany stejn dlouhé a jeho úhlop í ky se p lí, pak je to koso tverec nebo tverec. Následující tabulka obsahuje p ehled n kterých d ležitých tautologií výrokové logiky. erveným symbolem ⇔ jsou definovány logicky ekvivalentní výroky.
p⇔p
zákon totožnosti
p ∨¬ p
zákon vylou ení t etího
p je bu pravdivé, nebo nepravdivé, neexistuje t etí možnost.
(2)
¬ (p ∧ ¬ p)
zákon sporu, kontradikce
není možné, aby výrok a jeho negace byly zárove pravdivé
(3)
¬ (¬ p) ⇔ p
zákon dvojí negace
dvojitá negace dává p vodní výrok
(¬p
reductio ad absurdum (Claviat v zákon)
(p
p)
p ¬p
p¬)
(p∧¬p)
zákon Dunce Scotta
q
(1)
(4)
(5) z nemožného plyne cokoliv
(6)
p)
zákon simplifikace
(7)
(p q) (¬q ¬ p)
zákon kontrapozice
(8)
spojování p edpoklad
(9)
hypotetický sylogismus (tranzitivita implikace)
(10)
p∧q⇔q∧p
komutativnost konjunkce
(11)
p∨q⇔q∨p
komutativnost disjunkce
(12)
(p ∧ q) ∧ r ⇔ p ∧ (q ∧ r)
asociativnost konjunkce
(13)
(p ∨ q) ∨ r ⇔ p ∨ (q ∨ r)
asociativnost disjunkce
(14)
p [p
(q
(q r)]⇔ ⇔ (p∧q r)
[(p q) ∧ (q r)]
(p r)
p ∧ (q ∨ r) ⇔ (p ∧ q) ∨ (p ∧ r) p ∨ (q ∧ r) ⇔ (p ∨ q) ∧ (p ∨ r)
vzájemná distributivnost konjunkce a disjunkce
(15) (16)
(p ∧ p) ⇔ p
idempotence konjunkce
(17)
(p ∨ p) ⇔ p
idempotence disjunkce
(18)
[(p p
q) [q
p
(19)
(p ∧ q)]
(20)
p]
- 11 -
Zjistili jsme, že logické spojky ∧,∨, ∨, , ⇔, ¬ nám umož ují zkonstruovat libovoln komplikované výrokové formule. Možná jste si již uv domili, že by na totéž sta ily
jen funktory ∧,∨ a ¬. Formuli a ∨ b je totiž možno nahradit ekvivalentní formulí (a ∧ ¬b) ∨ (¬a ∧ b), b je možno nahradit ekvivalentní formulí ¬ a ∨ b
formuli a
a formuli a ⇔ b je možno nahradit ekvivalentní formulí (¬a ∨ b) ∧ (a ∨¬ b).
Dokonce vysta íme jen s funktory ∧, ¬ , protože (a ∨ b)
¬ (¬a ∧ b). (P esv d te se vypln ním pravdivostní tabulky.)
Definujme nyní funktory Funktor
a
pravdivostní tabulkou
se nazývá Shefferova spojka
a sta í k vyjád ení jakéhokoliv složeného výroku, nebo platí: 1.
¬a
2.
a∧b
a
a
(a
b)
a b a
b a
b
1 1
0
0
1 0
1
0
0 1
1
0
0 0
1
1
(a b)
1.8 Výrokový kalkul lze tedy vybudovat užitím pouze Schefferovy spojky. Ov te poslední dva vztahy a dokažte, že analogicky umož uje výrokový kalkul také vybudovat pouze užitím tak zvané Pierceovy spojky .
- 12 -
ešení složit jších slovních logických úloh pomocí pravdivostní tabulky Z ešení n kterých výše uvedených úloh plyne tento postup: I. Na základ analýzy textu úlohy zvolíme výrokové prom nné a vyjád íme slovní podmínky úlohy pomocí výrokových formulí. II. Sestavíme pravdivostní tabulku, jejím vypln ním vy ešíme úlohu. III. Vyjád íme výsledek v termínech slovní úlohy.
P íklad 1. V díln jsou t i stroje, které pracují podle t chto podmínek: a) pracuje-li první stroj, pracuje i druhý, b) pracuje druhý nebo t etí stroj nebo pracují oba tyto stroje, c) nepracuje-li první stroj, nepracuje ani t etí. Jaké jsou možnosti pro práci stroj ? I. Základní výrokové formule: a: Pracuje první stroj. b: Pracuje druhý stroj. c: Pracuje t etí stroj. Z textu úlohy víme, že platí: a
(b∨c) ∨(b∧c),
b,
¬a
¬c
II. Tabulka: (b∨c) ∨(b∧c)
¬a
1
1
1
0
1
1
1
1
0
0
1
1
1 0 0
0
0
0
0
1
0 1 1
1
1
1
1
0
0 1 0
1
0
1
1
1
0 0 1
1
0
1
1
0
0 0 0
0
0
1
0
1
a b c
b∨c b∧c
a
1 1 1
1
1
1 1 0
1
1 0 1
b
III. Záv r. M že nastat práv jedna z t chto t í situací: 1. Pracují všechny t i stroje sou asn . 2. Pracují jen první dva stroje 3. Pracuje jen druhý stroj
- 13 -
¬c
P íklad 2. Architekt má vypracovat návrh st ny do obývacího pokoje z element sektorové sestavy. Ve st n má být za azena knihovni ka a prádelník nebo se v ní musí vyskytovat zásuvková sk í a likérník. Zákazník si nep eje, aby ve st n byly spole n knihovni ka a zásuvková sk í ka, práv tak by se mu nelíbilo za azení knihovni ky a likérníku. Architekt navrhl st nu, v níž je krom jiných element za azen prádelník, zásuvková sk í a likérník, není za azena knihovni ka. Splnil všechny zákazníkovy požadavky? M l ješt jiné možnosti pro sestavení st ny, aby p itom vyhov l všem zákazníkovým požadavk m? ešení. I. Zvolíme základní formule: k: Do st ny bude náležet knihovni ka. p: Do st ny bude náležet prádelník. z: Do st ny bude náležet zásuvková sk í . l: Do st ny bude náležet likérník. Požadavky: Má platit (k∧p) ∨(z∧l) a sou asn k∨z a k∨l. II. Tabulka: k
p
z
l
a: k∧p
b: z∧l
a∨b
k∨z
k∨l
1
1
1
1
1
1
1
0
0
1
1
1
0
1
0
1
0
1
1
1
0
1
1
0
1
1
0
1
1
0
0
1
0
1
1
1
1
0
1
1
0
1
1
0
0
1
0
1
0
0
0
0
0
1
1
0
0
1
0
0
0
1
0
1
0
0
0
0
0
0
1
1
0
1
1
1
0
1
1
1
1
0
1
1
0
0
0
0
1
0
0
1
0
1
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
1
1
0
1
1
1
1
0
0
1
0
0
0
0
1
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
III. Záv r. Architekt zákazníkovy požadavky splnil, jak vidíme z devátého (zelen vybarveného) ádku tabulky. Žlut vybarvené ádky ukazují další dv možnosti vyhovující požadavk m zákazníka. - 14 -
1.9 Cvi ení 1) Jan, Petr Jan, Karel a Petr se dohodli, že se zú astní výletu, za t chto podmínek a) P jde-li na výlet Karel, p jde i Petr. b) Nep jde-li Jan, nep jde ani Petr. c) Na výlet p jde Jan nebo Karel Jaké jsou možnosti ú asti chlapc na výletu? 2) Jana se chystá na maturitní ples. Práv prob hla porada o dopl cích k šat m. Hlavní rádci jsou dv tety a matka. První teta: Doporu uji brož nebo náhrdelník. Druhá teta: Nejlépe by bylo vzít si náramek nebo brož. Matka: Já jsem pro náhrdelník nebo náramek. Jana se na plese objevila s náramkem, náhrdelníkem i broží, i když se jí zdálo, že je p íliš „ov šena“. Cht la však ud lat matce i ob ma tetám radost. Splnila skute n všechna jejich p ání? Musela si vzít všechny t i dopl ky, aby všem vyhov la? 3) I do m sta Kocourkova pronikl v poslední dob turistický ruch. M stská rada projednávala, jak co nejvíce zvýšit p íliv turist . Byly p edloženy tyto návrhy: vybudovat na nám stí kašnu, postavit pomník zakladateli m sta, vystav t vyhlídkovou v ž. M stská pokladna však není p íliš plná, a tak se radní dohodli realizovat nejvýše dva z p edložených návrh . V diskusi vystoupili t i radní. První radní: „Jsem pro jakékoliv ešení, nebudu souhlasit jenom s rozhodnutím stav t pomník a nestav t v ž.“ Druhý radní: „Budu protestovat jenom tehdy, kdybychom v našem m st stav li kašnu a nepostavili pomník.“ vyhlídková T etí radní: „Mn by nevyhovovalo jedin to ešení, kdyby v našem m st stála 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 Kocourkov postaví? 4) Zájemkyn o zájezd do St edomo í má velmi náro né a pon kud podivínské požadavky na výb r dopravních prost edk . Cht la by let t letadle, nebo jet lodí, ale nechce použít obou dopravních prost edk . Navíc by cht la jet lodí a p itom už necestovat vlakem nebo by si p ála jet vlakem a p itom už nelet t letadlem. Zoufalý ú edník edoku jí nabídl dva zájezdy. V prvním byla pouze jízda lodí a vlakem, v druhém pouze let letadlem. Paní si vzala spokojen druhý z nabídnutých zájezd . Spl oval všechna její p ání? Vyhovoval by první z nabídnutých zájezd všem jejím požadavk m? 5) Petr je lenem školních družstev v házené, kopané, košíkové a lehké atletice. Vzhledem k tomu, že není schopen stihnout své povinnosti ve škole a jeho prosp ch není práv nejlepší, rozhodl se, že alespo jedno z družstev opustí. Nez stane již lenem t í družstev, tj. košíkové, kopané a lehké atletiky, ale aspo v jednom z nich bude. I nadále z stane lenem družstva házené nebo družstva košíkové, ale v obou zárove nez stal. Navíc ješt odešel z družstva košíkové nebo opustil družstvo lehké atletiky. Dnes je Petr ve t ech školních družstvech z t ch, jejichž lenem byl p vodn . Která to jsou, p edpokládáme-li, že splnil všechna svá p edsevzetí? Jaké možnosti by se mu naskýtaly, kdyby cht l hrát jenom ve dvou z nich a p itom splnil svá p edsevzetí? 6) Rozhodn te, kte í žáci ze tve ice A, B, C, D pojedou na výlet, mají-li být dodrženy tyto zásady: Pojede aspo jeden z dvojice B, D, nejvýše jeden z dvojice A, C, aspo jeden z dvojice A, D a nejvýše jeden z dvojice B, C. Dále je jisto, že B nepojede bez A a že C pojede, pojede-li D. - 15 -
7) Trenér chce postavit štafetu na 4x 100 m. Z p vodn uvažovaných atlet p ichází do úvahy atleti A, B, C, D p i sou asném spln ní t chto podmínek: a) pob ží práv jeden z dvojice A,B a práv jeden z dvojice A,C b) závodník B nepob ží bez D c) atleti A, D nebudou uvoln ni oba sou asn d) jistá je ú ast alespo jednoho z atlet C,D 8) P i stavb silnice, která má spojovat dv m sta se rozhodovalo, kterými obcemi A, B, C, D má cesta vést. Musí být spln ny následující podmínky: a)Silnice povede obcí B, jestliže povede obcí A. b)Obcemi A a C silnice povede, jestliže povede obcí D. c)Silnice povede alespo jednou z obcí B a C d)Obcemi C a D povede bu sou asn nebo žádnou z nich. Jak silnice povede, aby byly spln ny všechny podmínky?
Výsledky. 1) Všechny podmínky jsou spln ny v t chto p ípadech: (a) Na výlet p jdou všichni t i spole n . (b) P jde Jan s Petrem a Karel nep jde. (c) P jde jenom Jan. 2) Jana všechny požadavky splnila. Jsou i jiné varianty, ke pln ní všech požadavk sta í vzít libovolné dva dopl ky. 3) Tabulka pravdivosti vyhovuje všem požadavk m jen v prvním a posledním ádku. Nepostavili tedy nic (vzhledem k tomu, že na spln ní všech t í projekt nemají dost pen z). 4) Všechny požadavky spl uje pouze první z nabídnutých zájezd . 5) Je v družstvu házené, fotbalu a atletiky. Možné dvojice: basketbal a fotbal, fotbal a házená, atletika a házená. 6) Dv možnosti: pojede bu A s B, nebo C s D. 7) Závodníci pob ží takto: pob ží B, C, D + 1 náhradník. 8) M že nastat n která z t chto situací: (a) Cesta povede všemi obcemi A,B,C,D (b) Cesta povede obcemi jen A a B. (c) Cesta povede jen obcí B.
2. Základní poznatky z predikátové logiky Na rozdíl od výrokové logiky si predikátová logika všímá struktury v t samotných. Rozlišuje v každé v t individuum, resp. individua, o n mž, resp. o nichž, se n co vypovídá (predikuje) - predikát intuitivn chápeme jako vlastnost nebo vztah. V školské matematice se pro predikát užívá termín výroková forma. Je to tvrzení, které obsahuje individuové prom nné, p i emž po dosazení individuových konstant za prom nné se toto tvrzení m že stát výrokem.
Predikátový symbol je výraz, ozna ující predikát, tedy vlastnost nebo vztah, který lze predikovat (vypovídat) o individuu, nebo individuích. Jako predikátové symboly budeme volit velká písmena abecedy, abychom je rozlišili od symbol pro individuální prom nn a konstanty, jež budeme zna ovat malými písmeny. Obor prom nných O(U ) výrokové formy U je množina všech hodnot (individuových) prom nných, které dosazujeme do U. Obor prom nné je bu p edem dán, nebo si jej zvolíme. - 16 -
Defini ní obor D(U ) výrokové formy U je množina všech konstant z oboru prom nné, po jejichž dosazení do U dostáváme výrok (pravdivý nebo nepravdivý). 0bor pravdivosti P (U ) výrokové formy U je množina všech konstant z oboru prom nné, po jejichž dosazení do U dostáváme pravdivý výrok. P íklady výrokových forem jedné prom nné 1. U(x): Osoba x se narodila v Protivín . Zvolíme O(U ) = D(U ) jako množinu všech lidí, kte í žijí, nebo žili na Zemi. P(U ) je množina všech lidí, kte í se narodili v Protivín . 2. V(x):
x ≤ 2, ( x ∈ R). O(V ) = R, D (V ) = 0, ∞ ) , nebo pro záporná ísla není výraz
definován a proto nemá smysl tvrdit, že je nerovnost
x
x ≤ 2 pravdivá nebo nepravdivá. P (V ) = 0, 4 .
P íklady výrokových forem dvou prom nných 1. Na obrázku je schéma rodiny Novákových, Jan a Marie jsou manželé, Petr, Karel, Iva, Hana a Dana jejich d ti. V zájmu stru nosti budeme ozna íme každou osobu i po áte ním písmenem jejího jména. Množina rodiny Novákových je tedy M = { j , m, p , k , i , h , d } . Výrokovou formou je nap íklad tvrzení U(x, y): x je syn y. Množinou O(U ) a zárove i množinou D(U ) je množina všech uspo ádaných dvojic z množiny M:
D(U ) = O(U ) = {[ x, y ] , x ∈ M ∧ y ∈ M } .
Oborem pravdivosti je P (U ) = {[ p, j ] , [ p, m ] , [ k , j ] , [ k , m ]} .
Ur ete vý tem obory pravdivosti výrokových forem a) V(x, y): x je sestra y, b) H(x, y): y je matka x.
2. A( x, y ) :
( x) +( y) 2
2
= 1, kde x, y ∈ R. Ur ete O( A), D( A) a v kartézské soustav sou adnic
znázorn te P( A). Termínem kvantifikátory obecn ozna ujeme údaje o po tu, pat í mezi n ísla, slova a slovní spojení jako mnoho, málo, n kolik, aspo dva, žádný, všichni, libovolný, n kde, n jak, jakkoliv ... . V matematice a logice nej ast ji užíváme dva základní kvantifikátory:
Obecný kvantifikátor ∀, který p edstavuje slovní spojení „pro každé ... platí“ a kterému se také n kdy íká velký kvantifikátor, a Existen ní ( áste ný, malý) kvantifikátor ∃, který p edstavuje slovní spojení „existuje aspo jedno ... pro které platí“ .
P idáním obecného i existen ního kvantifikátoru se z výrokové formy stává výrok.
- 17 -
Abeceda predikátové logiky 1) Symboly pro individuové prom nné x, y, z, ... 2) Symboly pro individuové konstanty a, b, c, ... 3) Symboly pro predikáty U, V, ... 4) Znaky pro funktory ∧,∨, ∨, , ⇔, ¬ 5) Znaky pro obecný a áste ný kvantifikátor ∀, ∃ 6) Pomocné znaky ( ), [ ], { } ................. závorky
Výrokotvorné funktory se v predikátové logice užívají stejným zp sobem jako ve výrokové logice.
Pozor na negace výrokových forem s kvantifikátory:
Výroková forma
Její negace
∀x : U ( x)
∃x : ¬U ( x)
∃x : U ( x)
∀x : ¬U ( x)
Úlohy (n které jsou i s ešením, ostatní vy ešte) 1. Napište formule predikátové logiky odpovídající následujícím v tám. (Zave te si nejprve vhodné symboly.) Rozhodn te také, zda jde o výrok, nebo výrokovou formu. a) N které d ti nerady okoládu. ešení. Tvrzení je výrok, slovo „n které“ je zde ve významu existen ního kvantifikátoru - „existují“. Nech D je množina všech d tí a C ( x) : „x má rád okoládu“ je výroková forma. Pak má dané tvrzení tvar ∃x ∈ D: ¬C ( x). Jiné ešení. Zavedeme formule: D( x) : „x je dít “ C ( x) : „x má rád okoládu“. Pak lze p vodní tvrzení zapsat ve tvaru: ∃x : ( D ( x) ∧ ¬C ( x) ) . b) P irozené íslo je d litelné šesti, práv když je d litelné dv ma a t emi. ešení. Tvrzení je výroková forma (teprve po p idání obecného, resp. existen ního kvantifikátoru by se stalo výrokem), defini ní obor i obor pravdivosti je množina všech p irozených ísel. - 18 -
Poznamenejme, že auto i u ebnic obvykle takto formulovaná tvrzení uvádí jako matematické v ty, t ebaže by se m li vyjad ovat p esn ji. V našem p ípad nap íklad takto: „Pro každé p irozené íslo platí, že je d litelné šesti, práv když je d litelné dv ma a t emi.“ Ozna me N množinu všech p irozených ísel a pro tvrzení „x d lí y“ zavedeme obvyklý zápis x|y. Pak lze dané tvrzení zapsat ve tvaru: ( x ∈ N ∧ 6 | x ) ⇔ ( x ∈ N ∧ 2 | x ∧ 3 | x ) .
c) Jestliže je libovoln zvolené p irozené íslo d litelné devíti, pak je d litelné t emi. d) Nikdo, kdo nebyl pou en o bezpe nosti práce, nesmí pracovat v laborato i. e) V n kterých jiho eských m stech jsou cenné historické stavby. f) N kdo má hudební sluch a n kdo nemá hudební sluch. g) Žádný rybník neobsahuje istou vodu. 2. Utvo te negace všech tvrzení z úlohy 1 (p vodních slovních formulací i výsledných formulí). 3. Pro následující v ty uve te predikáty, konstantní symboly a funk ní symboly, které pot ebujete k formalizaci a napište formule odpovídajících v t. a) Eva mluví anglicky i francouzsky. b) Každý, kdo mluví n mecky, mluví i anglicky. c) Každý mluví anglicky nebo n mecky. d) N kdo mluví anglicky i n mecky. e) N kte í studenti neumí ani n mecky ani anglicky. 4. Pro následující v ty uve te predikáty, konstantní symboly a funk ní symboly, které pot ebujete k formalizaci a napište formule odpovídajících v t. a) Karel vid l Shakespearovu hru Hamlet. b) Karel vid l n kterou Shakespearovu hru. c) N kdo vid l Shakespearovu hru Hamlet. d) N kdo vid l n kterou Shakespearovu hru. e) Ne každý vid l n kterou Shakespearovu hru. f) Karel vid l pouze hry od Shakespeara. g) Lucernu nenapsal Shakespeare.
ešení. Objekty jsou lidé a hry. Pro první ty i v ty by sta ila tato formalizace: Máme jeden predikátový ternární symbol V (x; y; z), který má význam „osoba x vid la hru y od autora z.“ (Na druhém místì trojice (x; y; z) musí být hra, na prvním a t etím musí být osoba.) Dále máme t i konstanty k pro osobu Karla, h pro hru Hamlet a s pro autora Shakespeara. Formule mají tvar: a) V (k; h; s); b) ∃y : V (k; y; s); c) ∃x : V (x; h; s); d) ∃x : V (x; y; s). Chceme-li popsat všechny v ty, zavedeme jiné predikátové symboly: Objekty jsou op t lidé a hry. Máme unární predikáty H: „být hrou“, O: „být osobou“, binární predikáty V (x; y): „osoba x vid la hru y“ a N(x; y): „osoba x napsala hru y“ a ty i konstantní symboly - 19 -
k: „Karel“, h: „Hamlet“, s: „Shakespeare“ a l: „Lucerna“. Zápisy formulí prove te sami.
5. Zave te vhodné predikátové symboly, funk ní symboly a konstanty, pak zformalizujte následující v ty. a) Druhá mocnina libovolného lichého ísla je vždy liché íslo. b) Je-li libovolné íslo d litelné šesti, je d litelné i dv ma. c) Existují ísla a, b, c taková, že sou et tverc
ísel a a b je roven tverci ísla c.
d) Každý ty úhelník, jehož úhlop í ky se p lí, je rovnob žník.
6. Jsou dány predikátové symboly P, Q a funk ní symboly f, g. Dále je dána interpretace D, I, kde obor prom nné D je množina všech lidí, f odpovídá otci, tj. I(f(x)) p i azuje osob x jejího otce, g odpovídá matce, tj. I(g(x)) p i azuje osob x její matku, P odpovídá vlastnosti „hrát na piano“, Q odpovídá vlastnosti „hrát na kytaru“. Napište slovy v ty, kterým v této interpretaci odpovídají následující formule: a) ∀x : ( P ( f ( x) ) ∨ Q ( g ( x) ) ) , b) ∀x : ( P ( g ( x) ) ∧ Q ( f ( x) ) ) ,
(
c) ∀x : ( P ( f ( x) ) ∨ Q ( g ( x) ) )
(
( P ( x) ∨ Q ( x) ) ) ,
)
d) ∃x : P ( g ( f ( x) ) ) ,
(
)
e) ∃z : P ( z ) ∧ ¬Q ( f ( g ( z ) ) ) . 7. Speciální symboly jazyka predikátové logiky jsou tyto: Predikátové symboly P a Q, funk ní symboly f, g a konstantní symboly a; b; c, kde P a f jsou unární a Q a g binární. Je dána interpretace N, I, kde N je množina p irozených ísel; I (a) = 0, I (b) = 1, I (c) = 3, I ( f ) : n → n 2 , tj. f odpovídá umocn ní na druhou, I ( g ) : [ m, n ] → m + n, tj. g odpovídá sou tu, I ( P ) = {2n, n ∈ N } , tj. P odpovídá vlastnosti „být sudým“, I (Q) = {[ m, n ] , m je d litelem ísla n,} tj. Q odpovídá relaci „d litelnosti“. Rozhodn te o pravdivosti nebo nepravdivosti následujících sentencí: a) P(c), b) P(f(a)), c) P ( g ( a, f (b) ) ) , d) Q ( a, f (b) ) , e) Q ( f (b), a ) , f) ∀x : Q ( x, x ) , g) ∃x : Q ( f ( x), x ) , - 20 -
h) ∀x : ( Q ( c, x )
Q ( b, x ) ) ,
i) ∀x : ( Q ( b, x )
Q ( c, x ) ) ,
j) ∃x : P ( f ( x) ∧ P ( x) ) , k) ∃x∃y : ( P ( x) ∧ P ( y ) ∧ P ( g ( x, y ) ) ) , l) ∃x∃y : ( ¬P ( x) ∧ ¬P ( y ) ∧ P ( g ( x, y ) ) ) ,
Výsledky. a) Nepravdivá, b) pravdivá, c) nepravdivá, d) nepravdivá, e) pravdivá, f) nepravdivá; g) pravdivá, h) pravdivá, i) nepravdivá, j) pravdivá, k) pravdivá, l) pravdivá.
- 21 -
Literatura [SE] Šedivý J.: O modernizaci školské matematiky [S] Smullyan R. M.: Jak se jmenuje tahle knížka? http://www.uloz.to/xkD8FtR/smullyan-jak-se-jmenuje-tahle-knizka-pdf
Pravidla Omluvy z neú asti na p ednášce nechci slyšet. Podmínkou zápo tu je úsp šn napsat záv re nou písemnou práci, v níž lze získat maximáln 100 bod . Základní hranice úsp šnosti 65 bod . Tato hranice se za každou neú ast na p ednášce zvyšuje o 2 body. Na za átku tém každé p ednášky bude krátký test z dosud probraného u iva. Za úsp šn napsaný test snižuji hranici záv re ného testu o 1 až 2 body. Za neúsp šn napsaný test zvyšuji hranici záv re ného testu o bod.
- 22 -
