Logika

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

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 \neq A (zákon sporu).

Formule je splnitelná pokud není kontradikcí.

Pravdivostní tabulka logických operací

Přepis implikace a ekvivalence

Negování složených výroků

Pravidla pro negaci disjunkce a konjunkce (2. a 3. řádek tabulky) se nazývají De Morganovy zákony.

Kvantifikátory

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á.