Logické výrazy

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.

Logické spojky jsou v počítači reprezentovány součástkami, kterým se říká logické brány. Z logických bran se pak dají skládat složitější logické obvody, které dokáží například sčítat nebo násobit čísla.

Příklady logických bran

Negace

Negace se u logických bran značí kolečkem na výstupu. Samotná negace má jeden vstup a jeden výstup, a značí se trojúhelníkem s kolečkem.

Známé spojky and, or a xor mají své vlastní značky a jejich negace se tvoří přidáním kolečka na výstup. Spojka nand značí negaci od and, tedy not and, spojka nor značí negaci od or, tedy not or, a spojka xnor značí negaci od xor, tedy not xor.

Logické spojky jsou v počítači reprezentovány součástkami, kterým se říká logické brány. Z logických bran se pak dají skládat složitější logické obvody, které dokáží například sčítat nebo násobit čísla. Logický obvod je složen z více bran takovým způsobem, že výstup jedné brány je použit jako vstup do jiné brány.

Obvody se dají i kombinovat. Spuštění dvou obvodů zároveň vedle sebe se říká paralelní zapojení obvodů. Spuštění dvou obvodů po sobě tak, že druhý obvod využívá na vstupu výstup z prvního obvodu, se říká sekvenční zapojení obvodů.

Výstup jednoho obvodu může být použit jako vstup více obvodům. Takové posílání vstupu do dvou směrů se značí plným kolečkem.

Příkladem skládání jednoduchých obvodů do většího je sčítání pomocí obvodů, kdy se například obvod pro sčítání čtyřbitového čísla dá složit jako čtyři jednobitové sčítačky v řadě.