Složené výroky 1
Základní pojmy
Výrok. Výrokem rozumíme oznamovací větu, u které má smysl rozhodovat o její pravdivostní hodnotě.
Tato pravdivostní hodnota je jednou ze dvou typů - pravda (značíme ji 1) a nepravda (značíme ji 0).
Určit pravdivostní hodnotu výroku nemusí být jednoduché. V matematice existuje celá řada tvrzení,
jejichž pravdivostní hodnotu dosud neznáme. Říkáme jim hypotézy.
Z jednoduchých výroků lze skládat složitější výroky - tzv. složené výroky. Obvykle se setkáme se čtyřmi
základními typy složených výroků - konjunkcí, disjunkcí, implikací a ekvivalencí.
Negace výroku. Výrok A utvořený z výroku A tak, že má opačnou pravdivostní hodnotu než původní
výrok, nazýváme negací výroku A.
Negacím výroků se budeme podrobněji věnovat v jiném textu.
Konjunkce (logický součin). Konjunkcí výroků A a B rozumíme složený výrok, který je pravdivý právě
tehdy, když jsou pravdivé oba výroky A i B. Píšeme A ∧ B. Ke slovnímu vyjádření konjunkce používáme
spojku a (i).
Disjunkce (alternativa, logický součet). Disjunkcí výroků A a B rozumíme složený výrok, který je
pravdivý právě tehdy, když je pravdivý alespoň jeden z výroků A, B. Píšeme A ∨ B. Ke slovnímu vyjádření
disjunkce používáme spojku nebo, kterou nechápeme ve vylučovacím smyslu.
Implikace. Implikací výroků A a B rozumíme složený výrok, který je nepravdivý právě tehdy, když je
pravdivý výrok A a nepravdivý výrok B. Píšeme A ⇒ B. Ke slovnímu vyjádření implikace používáme
spojení jestliže ... pak (pokud ... potom; když ... tak; je-li ...; ...).
Implikace tedy vyjadřuje skutečnost, že je-li splněn výrok A, pak musí být pravdivý také výrok B. Často
proto A nazýváme dostatečnou podmínkou k tomu, aby platilo B a B označujeme jako podmínku nutnou
k tomu, aby platilo A.
Ekvivalence (oboustranná implikace). Ekvivalencí výroků A a B rozumíme složený výrok, který je
pravdivý právě tehdy, když mají výroky A a B stejnou pravdivostní hodnotu. Píšeme A ⇔ B. Ke slovnímu
vyjádření ekvivalence používáme spojení právě tehdy, když, (tehdy a jen tehdy; když a jen když; ...).
Tabulka pravdivostních hodnot složených výroků.
A B A ∧ B A ∨ B A ⇒ B A ⇔ B
1 1 1 1 1 1
1 0 0 1 0 0
0 1 0 1 1 0
0 0 0 0 1 1
Výrokové formule. Výraz sestavený z výrokových proměnných, logických spojek a závorek nazýváme
výrokovou formulí.
U výrokových formulí zpravidla pomocí tabulky zkoumáme jejich pravdivostní hodnoty ve všech případech,
které mohou nastat (tabulka má pak 2n
řádků, kde n značí počet výrokových proměnných).
Výrokovou formuli, která vždy nabývá pravdivostní hodnoty 1 (resp. 0) nazýváme tautologií (resp. kon-
tradikcí).
1
Případné náměty k tomuto textu prosím adresujte na e-mail akob@jaroska.cz. Děkuji Aleš Kobza (autor materiálu).
1
Úlohy
Zadání
1. Rozhodněte, zda se jedná o výroky.
(a) Prší?
(b) Otevřete si sešity.
(c) Číslo 5 je jednociferné.
(d) Existuje kosodélník, jehož úhlopříčka leží na ose jeho vnitřního úhlu.
(e) Každé sudé číslo větší než 2 lze vyjádřit jako součet dvou prvočísel.
(f) Číslo f je kladné.
2. Dokažte, že následující formule jsou tautologie
(a) (A ⇒ B) ⇔ (B ⇒ A ),
(b) (A ⇔ B) ⇔ [(A ⇒ B) ∧ (B ⇒ A)],
(c) (A ⇔ B) ⇔ (A ⇔ B ),
(d) (A ⇔ B ) ⇔ [(B ∧ A) ∨ (A ∧ B)].
3. Napište tabulku pravdivostních hodnot výrokových formulí a rozhodněte, která z nich je tautologie či
kontradikce
(a) [(X ⇒ Y ) ∧ X ] ⇒ Y ,
(b) [A ∧ (B ∨ C)] ⇔ [(A ∧ B) ∨ (A ∧ C)],
(c) A ⇒ (B ∧ C) ∨ [A ∨ (B ⇒ C)] ,
(d) [(X ∧ Y ) ⇒ Z ] ⇒ Y .
4. Udejte příklad
(a) tautologie,
(b) kontradikce,
o alespoň čtyřech výrokových proměnných.
5. Na lánech A, B, C, D se má sklidit obilí. Postup prací je zachycen výrokovou formulí
[(A ∨ B) ⇒ C ] ∧ [(A ∨ C) ⇒ D ] ∧ [(B ∨ D) ⇒ A ]
Je možné zahájit práci na dvou lánech současně?
6. Logická spojka |, definovaná následující tabulkou pravdivostních hodnot
A B A | B
1 1 0
1 0 1
0 1 1
0 0 1
,
se nazývá Shefferův2
symbol. Dokažte, že pomocí Shefferova symbolu lze vyjádřit každou z logických
spojek , ∧, ∨, ⇒, ⇔.
2
Henry M.Sheffer (1882 - 1964) - americký logik
2
Návody, výsledky a komentáře
1. Výrokem musí být oznamovací věta, proto (a), (b) výroky nejsou. Věty (c) - (e) již výroky jsou, a to
(c) pravdivý, (d) nepravdivý, (e) je hypotézou (tzv. Goldbachovou3
), jejíž pravdivostní hodnota není
známa. Věta (f) není výrokem, ale je tzv. výrokovou formou. Z výrokové formy získáme výrok pomocí
kvantifikátorů (obecného ∀, existenčního ∃ či zesíleného existenčního ∃!) či dosazením konkrétních
výroků za jednotlivé proměnné.
2. Důkaz provedete snadno tabulkou o čtyřech řádcích. Význam formulí je tento:
(a) implikace A ⇒ B i B ⇒ A mají stejný logický význam (jsou logicky ekvivalentní); implikaci
B ⇒ A nazýváme obměnou implikace A ⇒ B,
(b) ekvivalence A ⇔ B vyjadřuje totéž, co konjunkce implikací A ⇒ B a B ⇒ A, je tedy oboustrannou
implikací.
(c) + (d) formule A ⇔ B, A ⇔ B a (B ∧ A) ∨ (A ∧ B) jsou logicky ekvivalentní - každá z nich
vyjadřuje totéž; v dalším ukážeme, že se jedná o negace ekvivalence A ⇔ B.
3. Výroková forma
(a) je ekvivalentní s formou Y ⇒ X, není tedy ani tautologií ani kontradikcí,
(b) je tautologií,
(c) je kontradikcí,
(d) není ani tautologií ani kontradikcí (právě ve třech řádcích vychází 0).
4. Rozmyslete, že při dopsání „čehokoliv” do libovolného schématu typu
(A ∨ A ) ∨ [. . .] , (A ∧ A ) ⇒ [. . .]
dostanete tautologii, např. do schématu typu
(A ⇔ A ) ∧ [. . .]
získáte kontradikci. Vytvořte sami podobná schémata.
5. Tabulka pravdivostních hodnot má 16 řádků. Pravdivostní hodnota 1 vychází právě na šesti z nich nezačne
se pracovat vůbec, začne se pracovat na právě jednom lánu a to zcela libovolném nebo se začne
současně pracovat na lánech B a D.
6. Shefferův symbol je tedy negací A ∧ B. Zápis A | A odpovídá A , například A | (A | B) vyjadřuje
A ⇒ B, (A | B) | (A | B) znamená A ∧ B. Dalším rozepisováním vyjádříme i disjunkci a ekvivalenci.
Z uvedeného vyplývá, že bychom v principu vystačili s jedinou logickou spojkou (a nepotřebovali jich
tedy 5, které jsme si uvedli), bylo by to však nepraktické, protože řada vyjádření by byla dlouhá a
nepřehledná. Dodejme, že podobně lze uvedené provést se spojkou definovanou jako negace alternativy
A ∨ B.
3
Christian Goldbach (1690 - 1764) - německý právník, politik a matematický samouk toto tvrzení zformuloval roku 1742
v dopise L.Eulerovi. Přes značné úsilí řady matematiků toto tvrzení do dnešního dne není dokázáno ani vyvráceno.
3