Logika a řešení problémů

Logika se zabývá vyvozováním platných závěrů z daných předpokladů. Logika se používá v důkazech (tzv. matematická logika), ale i v běžném uvažování, kdy z dostupných informací odvozujeme další závěry (tzv. logické myšlení). Na Umíme informatiku se zaměřujeme na rozvoj logického myšlení a využití logiky v informatice. Procvičování zde dělíme do tří témat:

• Logické výroky slovy – určování pravdivosti, vytváření slovně zapsaných výroků (bez formálního značení)
• Logické výrazy – zápis a vyhodnocování výrazů s logickými spojkami používanými v informatice (not, and, or, xor, ⇒, ⇔)
• Logické úlohy – využití logických úvah na řešení různorodých problémů (např. logické úlohy podobné sudoku, kde je potřeba splnit současně řadu podmínek)

Matematickou logiku si můžete procvičit na Umíme matiku. Kombinaci logického a algoritmického myšlení si můžete procvičit v rámci tématu Podmíněné příkazy.

Důležitou součástí logického myšlení je schopnost určit, zda určitý výrok platí, nebo neplatí. Zde procvičujeme tuto dovednost se slovně zapsanými výroky. Toto téma je rozdělené na několik podtémat:

• Určování pravdivosti – Zahrnuje výroky obsahující základní logické spojky (a, nebo, není), kvantifikátory (každý, některý) a nerovnosti (alespoň, nejvýše, stejně, různě). Např. „Mám v ruce alespoň tři esa nebo právě jednoho žolíka.“
• Implikace a ekvivalence – Výroky typu „pokud – pak“ a „právě tehdy, když“, které bývají méně intuitivní. Např. „Pokud nemám eso, pak mám žolíka.“
• Negace tvrzení – Tvorba tvrzení s opačnou pravdivostní hodnotou. Např. „Není pravda, že mám eso i žolíka.“ → „Nemám eso nebo nemám žolíka.“
• Logické důsledky – Vyvozování logického zavěru z dvou výroků. Např. „Pokud mám eso, mám i žolíka. Mám eso. → Mám žolíka.“

Určování pravdivosti výrazů s formálním značením si můžete procvičit v následujícím tématu nazvaném Logické výrazy.

Výrok je věta nebo tvrzení, které je buď pravdivé, nebo nepravdivé. V této sekci se zabýváme právě výroky a jejich jednoduchými kombinacemi a určováním jejich pravdivosti.

Příklady výroků

• „Dnes jsem vstal v osm hodin ráno.“
• „Mám na sobě červené tričko.“
• „Můj bratr je starší než já.“

Příklady vět, které výroky nejsou

• „Bude zítra pršet?“
• „Běž spát!“
• „Proč je tráva zelená?“

Složitější výroky a kombinace výroků

Kromě samotných výroků můžeme také výroky kombinovat. Výsledek takové kombinace je opět buďto pravdivý, nebo nepravdivý.

Výroky se mohou týkat například porovnání množství nebo takzvané kvantifikace, tedy mluvení o všech objektech nebo o existenci objektu.

Podrobnější rozbor negací najdete dále v sekci Negace tvrzení.

Implikace a ekvivalence jsou složitější spojky, kterými je možné spojovat výroky.

Implikace

Implikace jsou tvrzení typu pokud–pak, konkrétněji pokud platí předpoklad, pak platí závěr. Pokud předpoklad neplatí, celé tvrzení je vždy pravdivé. Pokud platí předpoklad, pak je tvrzení pravdivé právě tehdy, když je pravdivý závěr.

Ekvivalence

Ekvivalence jsou tvrzení typu právě tehdy, když, konkrétněji první výrok platí právě tehdy, když platí druhý výrok. Ekvivalence je pravdivá, pokud jsou oba výroky pravdivé, nebo pokud jsou oba výroky nepravdivé. Pokud je jeden z výroků pravdivý a druhý nepravdivý, pak je celé tvrzení nepravdivé.

Čas, místo a příčina

Obecně platí, že pravdivost výroků závisí i na konkrétním čase a místě. Takže například pravdivost výroku „Pokud jsem přišel domů dřív než můj táta, pak jsem přišel před pátou.“ závisí na dni, kdy ho vyhodnocuji. Může se stát, že dnes je pravdivý, ale včera nebyl.

Pokud je někde použita spojka „právě tehdy, když“, je jí myšlen souběh pravdivostí daných událostí. Takže například „Přišel jsem do školy právě tehdy, když tam přišel pan učitel.“ se překládá na „Buď jsme přišli do školy oba, nebo ani jeden z nás.“. Mohli jsme klidně přijít každý v jiný čas, není nutné, abychom vešli do dveří zároveň. Stejně to je i u implikace. Vztah pokud–pak se netýká ani času, ani není část za pak nutně způsobena částí po pokud.

Vyvozování

Při vyvozování závěrů z implikací a ekvivalencí můžeme postupovat více způsoby. Jednou z možností je si vzít hodnoty z vyvozovaného závěru a dosadit je do původní implikace či ekvivalence.

Další možností je upravit si tvrzení na jiné ekvivalentní. K tomu mohou nejvíce pomoci pravidla v sekci úpravy logických výrazů, ale některá si ukážeme i tady. Všechna vyplývají z definic.

Pokud preferujete grafické znázornění, můžete si implikace zobrazovat pomocí diagramů. Část u pokud vyznačíme jako menší kruh a část za pak jako větší okolo toho menšího.

Negace tvrzení je opět tvrzení, avšak s opačnou pravdivostní hodnotou. Jinak řečeno, negace pravdivého tvrzení je tvrzení nepravdivé, a negace nepravdivého tvrzení je tvrzení pravdivé.

Příklady

Negace tvrzení mluví o stejných objektech a jejich vlastnostech jako původní tvrzení, jen obrací jeho pravdivost za všech situací.

Negace tvrzení se spojkami

Zvláštnosti a chytáky

Zvláštností jsou negace takzvaných tvrzení s kvantifikátory. To jsou taková tvrzení, která obsahují slova typu všichni, žádný, alespoň jeden, existuje a podobné.

Dalším typem jsou negace s porovnáváním množství. To jsou taková tvrzení, která obsahují slova typu alespoň, nanejvýš, stejně, více, méně a podobné.

Odvozování logických důsledků z předpokladů je velmi důležitá dovednost. Nejde jen o samotné odvozování, ale i o schopnost rozpoznat, jestli nějaké tvrzení plyne z faktů, které známe.

V této sekci si ukážeme hned několik druhů odvozování.

Řetězení implikací

Kdykoli z prvního faktu plyne druhý, a z druhého plyne třetí, pak z prvního faktu bude plynout i fakt třetí.

Implikace s pravdivým předpokladem

Pokud máme implikaci, která má platný předpoklad, pak nutně platí i její závěr.

Implikace s nepravdivým závěrem

Pokud máme implikaci, která má neplatný závěr, pak nutně nesmí platit její předpoklad. To je proto, že kdyby platil předpoklad, pak by musel platit i závěr, o kterém víme, že neplatí.

V tomto tématu pracujeme s logickými výrazy s formálním značením (např. A or B), přičemž některé logické spojky značíme pomocí anglických slov (and, or, not). Toto značení je v informatice běžné, používá se například v mnohých programovacích jazycích. Téma dělíme na následující podtémata:

• Logické spojky a pravdivostní tabulky – význam jednotlivých logických spojek, přepisování z běžného jazyka do informatické notace (and, or, not, xor, ⇒, ⇔)
• Vyhodnocování logických výrazů – vyhodnocení složených výrazů kombinujících více logických spojek
• Úpravy logických výrazů – přepis na ekvivalentní výraz, který vypadá jinak, ale má vždy stejnou pravdivostní hodnotu
• Logické odvozování s výrazy – odvozování závěrů z předpokladů, kterých může být i více

Práci s logickými výroky si můžete dále procvičit i v různých jiných zápisech:

• Logické výroky slovy – výroky v běžném jazyce
• Logika na Umíme matiku – práce s výroky v matematické notaci (∧,∨,¬)
• Logické výrazy v Pythonu – práce s logickými výrazy v kontextu programování

Pravdivostní hodnoty

V informatice používáme většinou zaměnitelně následující:

• 1 = true = pravda
• 0 = false = nepravda

Logické spojky

Pravdivostní tabulka logických operací

Vyhodnocení logického výrazu si můžeme představit jako zjištění, jestli je pravdivý nebo nepravdivý. U jednoduchého výroku jeho vyhodnocení odpovídá jeho pravdivosti, ale u složitějších výroků s logickými spojkami jde o kombinaci pravdivostí jednotlivých podvýroků pomocí spojek.

Například spojka and se vyhodnotí na pravdu (true, 1) právě tehdy, když jsou oba výroky pravdivé.

Tedy 1 and 1 = 1, ale například 1 and 0 = 0.

Pravdivostní tabulka logických operací

Úpravy logických výrazů je vhodné provádět například tehdy, když chceme určit pravdivost daného výroku nebo porovnat, jestli jsou dva výroky shodné. K tomu se hodí základní přepisová pravidla.

Přepis základních logických spojek

Přepis implikace, ekvivalence a operace xor

Analogické zákony jako při počítání s čísly

Pro logické operace and a or také platí komutativní (1. a 2. řádek následující tabulky), asociativní (3. a 4. řádek) a distributivní zákony (5. a 6. řádek):

Další cvičení s trochu jinou notací najdete i na umíme matiku.

Logické odvozování s pomocí logických výrazů je formální varianta odvozování logických důsledků slovy.

Jde o proces, kdy dostaneme několik logických výrazů (faktů) a odvozujeme z nich jiný výraz (závěr). Nemusíme ale nutně jen odvozovat nové závěry, můžeme se i například pokoušet rozhodnout, jestli nějaký dodaný výrok plyne z jiných.

Říkáme, že výraz se dá odvodit (tedy vyplývá) ze zadaných výrazů právě tehdy, když platí ve všech případech, kdy platí všechny zadané výrazy.

Příklady

• Z výrazu X \text{ and } Y můžeme odvodit X, protože kdykoli platí X \text{ and } Y, musí platit X i Y, a tím spíš musí platit i samotné X.
• Z výrazů X \text{ or } Y a \text{not } X můžeme odvodit Y. Aby bylo splněno X \text{ or } Y, musí platit X nebo Y, ale X platit nemůže. Proto platí Y.
• Z výrazů X \Leftrightarrow Y a X můžeme odvodit Y. Výraz X \Leftrightarrow Y říká, že Y má vždy stejnou hodnotu jako X. Z pravdivosti X tak můžeme odvodit pravdivost Y.

V tomto tématu si můžete procvičit schopnost řešit různorodé logické úlohy:

• Splňování podmínek – úlohy trénující schopnost splnit řadu zadaných omezení současně (jako např. v sudoku)
• Deduktivní úlohy – úlohy trénující schopnost zkombinovat související informace a odvodit z nich platný logický závěr
• Bludiště a hledání cest – úlohy trénující schopnost najít cestu do cíle (např. různá netradiční bludiště včetně skákání a prokopávání zdí)
• Plánování – úlohy trénující schopnost najít posloupnost kroků k dosažení požadovaného stavu

V těchto úlohách si procvičíte schopnost splnit řadu zadaných omezení současně.

Zde najdete úlohy, kde musíte ze zadaných informací vyvodit správné závěry za použití logických úvah. Takovému vyvozování závěrů z daných pravdivých předpokladů se říká právě dedukce.

Pracovní listy

Kromě interaktivních úloh jsou k dispozici i pracovní listy na vytištění (s tématem pravdomluvců a lhářů):

• Poctivci a padouši: dvojice – pracovní list + řešení
• Poctivci a padouši: trojice – pracovní list + řešení

Bludiště jsou tvořena spletí chodeb a cest, ve kterých typicky hledáme cestu od startu k cíli. Lidé jsou bludišti fascinováni již od dávných dob. Historicky známá bludiště zahrnují například legendární Minotaurovo bludiště z řecké mytologie nebo bludiště v zámeckých zahradách (např. slavné bludiště v Hampton Court v Anglii).

Bludiště slouží nejen k zábavě, ale také k rozvoji informatického a algoritmického myšlení. Řešení bludišť vyžaduje schopnost logického myšlení, plánování a strategického rozhodování, což jsou klíčové dovednosti pro programování a řešení složitějších algoritmických problémů.

Kromě níže uvedených interaktivních úloh jsou k dispozici i následující pracovní listy na vytištění:

Neprůchodné bludiště	Bludiště se zákazem odbočení vlevo
řešení	řešení

V těchto úlohách si procvičíte schopnost najít posloupnost kroků k dosažení požadovaného stavu.