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: 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 Poznámka - Obrácená implikace … BÞA - Obměněná implikace … ØBÞØA (je ekvivalentní s výrokem AÞB) 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. 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. Dobrý den. B: . . C: Základy výrokové logiky. (nadpis kapitoly) …………. 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. 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. 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ů. 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 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 … 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í. 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 . d) e) 4 ≤ 5 < 8 Př. 4 Rozhodněte, zda je výrok K tautologií: [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. 1 1 (?) 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í? 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ý. Řeš.: V M 1 1 1 1 0 0 0 1 1 0 0 1 ● ● Př. 7 Výrok říká: Je-li objem krychle větší než 1 cm^3,^ 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 cm^3. 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. 1 1 1 ? Řeš.: 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 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) b) [a) , b) 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) Textové pole: S8. (TSP 2008, var. 1) 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)] Textové pole: B Textové pole: č.1 Textové pole: č.2 Textové pole: č.3 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: