02 Výroková logika – met.
Stručný přehled teorie
Výrok
- Oznamovací věta, o které má smysl prohlásit, že je pravdivá (1) nebo že není pravdivá (0).
Hypotéza
- Výrok, jehož pravdivostní hodnotu neznáme, zatím neznáme nebo ani znát nemůžeme.
Kvantifikovaný výrok
- Výrok, který obsahuje některý z kvantifikátorů.
Kvantifikátor
− Existenční –  (existuje aspoň jeden), ! ( existuje právě jeden)
− Obecný –  (pro každý, pro žádný)
− Obsahující konkrétní číselný údaj n (právě n, alespoň n, nejvýš n,…)
Negace
– Negace výroku V je výrok V (V, nebo V‘), který popírá pravdivostní hodnotu výroku V (např. triviální
formou „Není pravda, že …“)
Pravidla pro negování výroků:
Výrok … A Negace výroku … A
… je … … není …
… nevyřešil … … vyřešil …
x:V(x) … čteme: „pro každé x platí V(x)“ x: V(x) …“existuje aspoň jedno x, pro něž V(x) neplatí
x: V(x) … čteme: „existuje x, pro něž platí V(x)“ x: V(x) …“pro žádné x neplatí V(x)“
Aspoň n … je … Nejvýš (n-1) … je …
Nejvýš n … je … Alespoň (n+1) … je …
Složené výroky – souvětí vytvořená spojením jednodušších výroků pomocí logických spojek:
Poznámka
− Obrácená implikace … BA
− Obměněná implikace … BA (je ekvivalentní s výrokem AB)
Konjunkce
(A a B)
A B AB
1 1 1
1 0 0
0 1 0
0 0 0
Disjunkce
(A nebo B)
A B AB
1 1 1
1 0 1
0 1 1
0 0 0
Implikace
(Jestliže A, pak B)
A B AB
1 1 1
1 0 0
0 1 1
0 0 1
Ekvivalence
(A právě tehdy, když B)
A B AB
1 1 1
1 0 0
0 1 0
0 0 1
(𝑇𝐴𝐵𝑈𝐿𝐸) Výroková logika
Výrok je oznamovací věta, o které má smysl prohlásit, že je pravdivá (1) nebo že není pravdivá (0).
Pravdivostní hodnota výroku
Označení výroku: A, B, C, … , X, Y, ….
výrok není výrok
A: Praha je hlavní město ČR. 𝑝(𝐴) = 1 Dobrý den.
B: 𝟑 > 𝟏𝟐 . 𝑝(𝐵) = 0 𝑥 ≥ 8 .
C: √𝟑𝟐𝟒 = 𝟏𝟖 𝑝(𝐶) = 1 Základy výrokové logiky. (nadpis kapitoly)
………….
(𝑇𝐴𝐵𝑈𝐿𝐸)
Hypotéza je výrok, jehož pravdivostní hodnotu zatím neznáme nebo ani znát nemůžeme.
Př.: H: Nejpozději v roce 2040 přistanou lidé na Marsu.
Tautologie
− Složený výrok, jenž je pravdivý bez ohledu na pravdivostní hodnoty výroků, z nichž je složen.
Kontradikce
− Složený výrok, jenž je nepravdivý bez ohledu na pravdivostní hodnoty výroků, z nichž je složen.
Negace složených výroků
V V
AB AB
AB AB
AB AB
AB (AB)( AB)
Kontrola správnosti úsudků – využívá výrokovou logiku:
Met.: Předpokladem úspěšnosti řešení úloh z výrokové logiky je výborná znalost základních operací
s jednoduchými (i kvantifikovanými) a složenými výroky.
Před zápisem do tabulky na tabuli by měl učitel věty vyslovit a pak se studenty na základě definice rozhodovat,
do kterého sloupce věta patří, proč je výrokem, jakou má pravdivostní hodnotu, proč výrokem není …
Následovat by měla krátká diskuse o větách (např.):
X: Před dvěma miliardami let vletělo do Slunce těleso velikostí srovnatelné s Měsícem.
Y: Ve vesmíru existuje kromě Země ještě aspoň jedna planeta, na níž je inteligentní život.
Z: Existuje yetti.
Jsou to výroky? ANO!!!! Každé z vět jednoznačně odpovídá právě jedna ze dvou možných pravdivostních hodnot.
To, že je z nějakého důvodu určení této pravdivostní hodnoty nad lidské síly, nemůže věty vyřadit z rodiny výroků.
Jedná se však o speciální výroky – tzv. hypotézy.
(𝑇𝐴𝐵𝑈𝐿𝐸)
Kvantifikovaný výrok je výrok, který obsahuje některý z kvantifikátorů.
Kvantifikátor
− Existenční –  (existuje aspoň jeden), ! ( existuje právě jeden)
Př.: Existuje aspoň jedno sudé přirozené číslo menší než 3.
− Obecný –  (pro každý, pro žádný)
Př.: V každém trojúhelníku je součet vnitřních úhlů 180°.
− Obsahující konkrétní číselný údaj n (právě n, alespoň n, nejvýš n,…)
Př.: V prověrce budou nejvýš dva obtížné příklady.
Př.: Petr získal aspoň 10 bodů.
(𝑇𝐴𝐵𝑈𝐿𝐸)
Negace výroku A je výrok A, který popírá pravdivostní hodnotu výroku A (např. triviální
formou „Není pravda, že …“)
Pravidla pro negování výroků:
Výrok … A Negace výroku … A
… je … … není …
… vyřešil … … nevyřešil …
x:V(x) … čteme: „pro každé x platí V(x)“ x: V(x) …“existuje aspoň jedno x, pro něž V(x) neplatí
x: V(x) … čteme: „existuje x, pro něž platí V(x)“ x: V(x) …“pro žádné x neplatí V(x)“
Aspoň n … je … Nejvýš (n-1) … je …
Nejvýš n … je … Alespoň (n+1) … je …
0 1 2 3 4 5 6 7 8 ...
Pozn.: Dříve, než se přistoupí k negování výroků, je třeba probrat kvantifikované výroky.
Teprve nyní by se mělo přistoupit k negování výroků.
Negace jednoduchých výroků je následně třeba důkladně procvičit. Negování kvantifikovaných výroků je třeba
vizualizovat!!!
Př.: A: Mám aspoň pět možností.
A: Mám nejvýš čtyři možnosti.
Př. 1 Negujte:
a) Aspoň jednou nelhal.
b) Nic ti nevytýkám.
c) Potřeboval právě 5 pokusů.
d) Je mu nejvýš 10 let.
Met.: Uvedené jednoduché úlohy je třeba důkladně procvičit dřív, než se přejde k řešení složených výroků
a dalších komplikovanějších úloh.
Pozornost je třeba věnovat přepisu zadání 3. d) do tvaru disjunkce a také zadání 3. e) do tvaru
konjunkce. Teprve potom jsou výroky připraveny k negování.
𝑉 ⟹ 𝑀 1
𝑀 1
𝑉 1 (?)
Oba (tedy všechny) předpoklady jsou splněny
na prvním a třetím řádku. Na prvním řádku je
splněn i závěr. Ale na třetím řádku závěr splněn
není. Úsudek proto není správný.
●
●
Př. 2 Vyslovte větu obrácenou, obměněnou a negaci:
a) Budu-li se učit nebo číst, nepůjdu do kina.
b) Když nebude pršet, půjdu ven a nezmoknu.
Př. 3 Negujte výroky. Určete pravdivostní hodnotu zadání.
a) Je-li číslo dělitelné devíti, pak je dělitelné i třemi.
b) Je-li trojúhelník pravoúhlý, pak není ostroúhlý.
c) Trojúhelník je pravoúhlý, právě když pro délky jeho stran platí vzorec 𝑎2
+ 𝑏2
= 𝑐2
.
d) log 1000 ≤ 6 log √10
e) 4 ≤ 5 < 8
Př. 4 Rozhodněte, zda je výrok K tautologií: K = (A B)′ (A′  B) [Ne, kontradikce]
Př. 5 Petr a Pavel čekají na Adama, Pepu a Cyrila.
Pavel říká: „Když přijde Adam a Pepa, přijde i Cyril.“
Petr odpoví: „Když přijde Adam a nepřijde Cyril, nepřijde ani Pepa.“
Pavel odpoví: „Vždyť říkáš totéž, co já.“
Je to pravda? [ano]
Met.: Úlohy 4 a 5 je třeba řešit užitím pečlivě sestavené a pečlivě vyplněné tabulky pravdivostních hodnot
jednotlivých jednoduchých i složených výroků, které se v zadání vyskytují.
Kontrola správnosti úsudků
Úsudek je myšlenkový proces, který na základě předpokladů, jejichž pravdivostní hodnoty známe, formuluje závěry.
Úsudek může být buď správný nebo nesprávný.
Schéma zápisu: Předpoklady
Závěr
Met.: Princip řešení: Sestavíme tabulku pravdivostních hodnot pro výroky a operace, které se v úloze vyskytují.
Najdeme všechny řádky, které odpovídají splněným předpokladům.
• Jestliže je na všech řádcích, kde jsou splněny všechny předpoklady, splněn i závěr, pak je
úsudek správný.
• Jestliže v tabulce existuje byť jen jediný řádek, na kterém jsou splněny všechny předpoklady,
ale není splněn závěr, pak je úsudek nesprávný.
Pozn.: Právě poslední fáze řešení, tedy rozhodnutí o správnosti úsudku, dělá některým studentům
problémy. Pokud některý student „projde úspěšně“ řešením, ale jeho odpověď zní např. „Výrok je
(ne)pravdivý“ namísto „Úsudek je (ne)správný“, svědčí to o nepochopení podstaty řešeného
problému.
Př. 6 Bude-li mít Jana vyznamenání, pojede k moři.
Jana je u moře.
Je správné usoudit, že měla vyznamenání?
Řeš.:
V M 𝑉 ⟹ 𝑀
1 1 1
1 0 0
0 1 1
0 0 1
(¬𝐴 ∨ ¬𝐶) ⟹ 𝐵 1
(𝐴 ∧ 𝐵) ⟹ ¬𝐶 1
¬𝐴 ⟹ 𝐵 1 ?
Př. 7 Výrok říká: Je-li objem krychle větší než 1 cm3
,je její hrana delší než 1 cm.
Měřením bylo zjištěno, že hrana měří 1,2 cm.
Usoudili jsme, že objem této krychle je větší než 1 cm3
. Je náš úsudek správný? [ne]
Př. 8 Víme, že platí dvě následující tvrzení: Když nesvítí A nebo nesvítí C, pak B svítí.
Když svítí A i B, pak nesvítí C.
Rozhodněte, zda je pak správný úsudek: Nesvíti-li A, pak svítí B.
Řeš.:
Oba předpoklady jsou splněny na čtyřech řádcích: druhém, třetím, čtvrtém a šestém. A na všech těchto
řádcích je splněn i závěr. Je tedy možné konstatovat, že daný úsudek je správný.
Pozn.: Jakmile zjistíme, že na některém řádku není splněný některý z předpokladů, řádek nás nezajímá a
nemusíme se na něm zdržovat zjišťováním dalších pravdivostních hodnot.
Př. 9 Negujte: a) A′
⋁(𝐵 ∧ 𝐶)
b) ((A‘  B)  C)  (B‘  C)
[a) 𝐴 ∧ (𝐵′ ∨ 𝐶′
), b) ((A‘B) C‘)  ((B’C‘))(BC))]
Př. 10 Které z následujících vět jsou logicky ekvivalentní větě:
Nemám-li bratra, pak nemám ani sestru.
a) Mám-li bratra, pak mám i sestru.
b) Mám-li sestru, pak mám i bratra.
c) Nemám bratra ani sestru. [Pouze věta b)]
Met.: Tato úloha je určitě vhodná pro to, aby student viděli více různých způsobů řešení. Obsahuje totiž
pouze dva základní výroky (např. B … “Mám bratra” a S … “Mám sestru”), s nimiž se dá jednoduše a
názorně pracovat
1. způsob – užitím tabulky pravdivostních hodnot. Při jejím správném vyplnění bude dobře vidět, že
sloupce výsledných pravdivostních hodnot pro původní větu a pro větu b) jsou stejné.
2. způsob – lze si všimnout, že daná věta a věta b) představují implikaci a k ní obměněnou implikaci.
A ty jsou samozřejmě ekvivalentní.
3. způsob – užitím vhodných diagramů (např. Eulerových nebo Vennových)
A B C ¬𝐴 ¬𝐶 ¬𝐴 ∨ ¬𝐶 (¬𝐴¬𝐶) ⟹ 𝐵 𝐴 ∧ 𝐵 (𝐴 ∧ 𝐵) ⟹ ¬𝐶 ¬𝐴 ⟹ 𝐵
1 1 1 0 0 0 1 1 0
1 1 0 0 1 1 1 1 1 1
1 0 1 0 0 0 1 0 1 1
0 1 1 1 0 1 1 0 1 1
1 0 0 0 1 1 0
0 1 0 1 1 1 1 0 1 1
0 0 1 1 0 1 0
0 0 0 1 1 1 0
B S
8
.
(
T
S
P
2
0
0
8
,
v
a
r.
1
)
K
t
e
r
é
z
n
á
sl
e
d
u
jí
c
í
c
h
v
ě
t
js
o
u
l
o
g
i
c
k
y
e
k
v
i
v
a
Ze zadání evidentně plyne, že pole č.3 odpovídající situaci, kdy mám sestru a nemám bratra,
musí být prázdné. Porovnáním diagramu se situacemi a), b), c) jednoznačně vyplyne, že
ekvivalentní může být pouze věta b).
Př. 11
[d)]
Met.: Úloha je relativně jednoduchá, takže časově nejméně náročné je určitě řešení s náčrtem dvou
schránek a „vyzkoušením“ umístění dopisu do první, respektive do druhé, schránky a posouzením pravdivosti
jednotlivých tvrzení v prvním, respektive v druhém, případě.
Př. 12 Jsou dána tvrzení A a B. A: Jestliže jsem rodič, pak jsem zodpovědný.
B: Nejsem zodpovědný nebo nejsem odvážný.
Čtyři z následujících pěti tvrzení logicky vyplývají z A a B, jedno ne. Které?
a) Jsem rodič nebo jsem odvážný.
b) Jestliže jsem odvážný, pak nejsem rodič.
c) Nejsem odvážný rodič.
d) Jestliže jsem rodič, pak nejsem odvážný.
e) Nejsem rodič nebo nejsem odvážný. [Neplyne a)]
Met.: Časově nejméně náročný je způsob řešení užitím diagramu pro tři množiny
Př. 13 (TSP 2013, var. 1)
Marťanští muži v létě mluví pravdu, po zbytek roku lžou. Marťanské ženy mluví pravdu ve středu, ostatní dny
lžou. Dva obyvatelé Marsu Hélo a Kélo ve stejný den řekli:
Hélo: Kélo je žena a dnes lže.
Kélo: Oba jsme stejného pohlaví.
Vyberte pravdivé tvrzení.
a) Kélo je žena a Hélo je muž.
b) Není středa.
c) Hélo je žena a Kélo muž.
d) Není léto.
e) Je léto. [b)]
Př. 14 Negujte: aQ, bQ: (a < b  cR − Q; a < c < b)
č.1
č.2
č.3