Čeština
Angličtina
Informatika
Biologie
Umíme to
Němčina
Zeměpis
Chemie
Dějepis
Fyzika
Aritmetika
Zlomky, procenta
Geometrie
Elementární algebra
Funkce
Jednotky, míry
Diskrétní matematika
Finanční gramotnost
Rozhodovačka
Pexeso
Krok po kroku
Psaná odpověď
Grafař
Porozumění
Přesouvání
Mřížkovaná
Rozdělovačka
Rozbitá kalkulačka
Roboti
Střílečka
Příšerky
Závody
Územíčka
Tipovačka
Týmovka
Logika
Logika zkoumá způsoby, jak vyvozujeme závěry z předpokladů. Logika původně vznikla jako součást filosofie, později se výrazně rozvinula v matematice. Dnes má důležité uplatnění i v informatice.
Základ matematického pojetí logiky je výroková logika, ve které pracujeme s výroky (tvrzení, která jsou buď pravdivá, nebo nepravdivá) a logickými spojkami (a zároveň, nebo, negace). Rozšířením výrokové logiky je predikátová logika, ve které navíc používáme kvantifikátory (existuje, pro každý).
Přehled témat o logice dostupných na Umíme matiku:
| téma | obsah |
|---|---|
| Logické výroky | slovní zápis logických výroků |
| Logika: pojmy a značení | zápis výroků pomocí logických spojek \wedge, \vee, \neg, \Rightarrow, \Leftrightarrow |
| Vyhodnocování logických výrazů | vyhodnocování pravdivosti logických výrazů zapsaných pomocí logických operací |
| Úpravy logických výrazů | úprava a zjednodušení logického výrazu podle pravidel práce s logickými operacemi |
| Kvantifikátory | obohacení logických výrazů o existenční a obecný kvantifikátor \exists, \forall |
| Důkazy | exaktní matematické postupy, jak ověřit platnost logických výroků |
V rámci systémů Umíme najdete logiku také na informatice: logika na Umíme informatiku. Tam je důraz kladen na logické spojky používané při programování a na řešení logických úloh.
Logika: pojmy a značení
Výroky
Výrok je sdělení, u kterého má smysl otázka, zda je pravdivý, nebo nepravdivý, přičemž může nastat jen jedna z těchto možností.
Příklady výroků:
- Město Brno leží v České republice. (pravdivý výrok)
- Brno je hlavní město České republiky. (nepravdivý výrok)
- Na Marsu je zakopán poklad. (výrok, jehož pravdivost neznáme)
Příklady vět, které nejsou výroky: Máš hlad? Běž do obchodu pro vajíčka.
Logické spojky
| Zápis | Název | Význam |
|---|---|---|
| \neg A | negace | neplatí A |
| A \wedge B | konjunkce, a zároveň | A a B platí současně |
| A \vee B | disjunkce, nebo | platí alespoň jedno z A a B |
| A \Rightarrow B | implikace, jestliže-pak | pokud platí A, pak platí i B |
| A \Leftrightarrow B | ekvivalence, právě když | A platí právě tehdy, když platí B |
Tautologie a kontradikce
Tautologie je výroková formule, která je vždy pravdivá. Příklady:
- A \vee \neg A (zákon vyloučení třetího)
- (A \Rightarrow B) \Leftrightarrow (\neg B \Rightarrow \neg A)
Kontradikce je výroková formule, která je vždy nepravdivá. Příkladem je formule A \wedge \neg A (zákon sporu).
Formule je splnitelná pokud není kontradikcí.
Vyhodnocování logických výrazů
Pravdivostní tabulka logických operací
| A | B | A \vee B | A \wedge B | A \Rightarrow B | A \Leftrightarrow B |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 |
Úpravy logických výrazů
Přepis implikace a ekvivalence
| Výrok | Ekvivalentní výrok | |
|---|---|---|
| A\Rightarrow B | \neg A\vee B | |
| A\Rightarrow B | \neg B\Rightarrow \neg A | |
| A\Leftrightarrow B | (A\wedge B)\vee (\neg A \wedge \neg B) |
Negování složených výroků
| Výrok | Ekvivalentní výrok | |
|---|---|---|
| \neg (\neg A) | A | |
| \neg (A\vee B) | \neg A\wedge \neg B | |
| \neg (A\wedge B) | \neg A\vee \neg B | |
| \neg (A\Rightarrow B) | A\wedge \neg B | |
| \neg (A\Leftrightarrow B) | (\neg A\wedge B)\vee(A \wedge \neg B) |
Pravidla pro negaci disjunkce a konjunkce (2. a 3. řádek tabulky) se nazývají De Morganovy zákony.
Analogické zákony jako při počítání s čísly
Pro logické operace \wedge, \vee také platí komutativní (1. a 2. řádek následující tabulky), asociativní (3. a 4. řádek) a distributivní zákony (5. a 6. řádek):
| Výrok | Ekvivalentní výrok | |
|---|---|---|
| A \wedge B | B \wedge A | |
| A \vee B | B \vee A | |
| (A \wedge B) \wedge C | A \wedge (B \wedge C) | |
| (A \vee B) \vee C | A \vee (B \vee C) | |
| A \wedge (B \vee C) | (A \wedge B) \vee (A \wedge C) | |
| A \vee (B \wedge C) | (A \vee B) \wedge (A \vee C) |
Kvantifikátory
Kvantifikátory
| Značení | Pojem | Význam |
|---|---|---|
| \exists x | existenční kvantifikátor | existuje x, takové že... |
| \forall x | obecný (univerzální) kvantifikátor | pro každé x platí... |
Příklady výroků s kvantifikátory
Vlastnost Číslo x je sudé. můžeme vyjádřit jako Existuje celé číslo k takové, že x = 2\cdot k. To můžeme zapsat jako \exists k \in \mathbb{Z}: x = 2\cdot k.
Výrok Ponorky (P) nemohou létat (L). můžeme zapsat jako \forall x: P(x) \Rightarrow \neg L(x).
U složitejších výroků s více kvantifikátory musíme dávat na pořadí kvantifikátorů:
- \exists x\in M\ \forall y \in M: y \leq x – existuje prvek v množině M, který je větší roven všem ostatním prvkům v M, tj. výrok říká, že množina má největší prvek.
- \forall x\in M\ \exists y \in M: y \leq x – pro každý prvek v množině M existuje prvek x, který je menší nebo roven X. Protože klidně můžeme vybrat y=x, je to splněno pro každou množinu (pro pokročilé: tedy pouze pokud uvažujeme množiny čísel a \leq jako běžné uspořádání na číslech).
Negace výroků s kvantifikátory
Při negování výroků s kvantifikátory měníme existenční kvantifikátor na obecný (a naopak) a posouváme negaci „dovnitř“. Příklad:
- Není pravda, že všechny kočky (K) jsou černé (C).
- \neg (\forall x: K(x) \Rightarrow C(x))
- Změníme obecný kvantifikátor na existenční a znegujeme výrok.
- \exists x: \neg(K(x) \Rightarrow C(x))
- Nyní znegujeme implikaci pomocí pravidla \neg(A \Rightarrow B) \Leftrightarrow (A \wedge \neg B).
- \exists x: K(x) \wedge \neg C(x)
- Existuje kočka, která není černá.
