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 v rámci předmětu matematika – 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.

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

Bitové operace spojují logiku s binárním zápisem čísel. Provádějí logické úkony přímo nad jednotlivými bity binárních čísel, podle čehož také dostaly svůj název. Na rozdíl od běžné aritmetiky zde neexistuje žádný „přenos do vyššího řádu“ (carry). Každá pozice v čísle se zpracovává izolovaně. Bitové operace se vyznačují také tím, že nepracují jen s jedním bitem, ale s celou posloupností bitů najednou.

Logické operace

Logické operace jsou typickou ukázkou bitových operací. Mezi nejčastěji používané patří bitová negace (NOT), konjunkce neboli součin (AND), disjunkce neboli součet (OR) a neekvivalence (XOR). Více se logickým spojkám věnuje sekce logiky.

Posuny

Dalším častým druhem operací jsou posuny. Posun, neboli shift, se převádí přidáním nuly na začátek, případně na konec, sekvence bitů a odebráním jednoho bitu z druhé strany řetězce. Posun doprava (>>) tedy přidá nulu na začátek a odebere poslední bit, což pro binární čísla odpovídá celočíselnému dělení dvěma. Posun doleva (<<) naopak přidá nulu na konec řetězce a odebere první bit, což pro binární čísla odpovídá násobení dvěma.

Využití

Díky izolovanosti provádění operace na každém bitu zvlášť je v počítači často možné provádět více bitových operací paralelně. Následkem toho je práce s bitovými operacemi velmi rychlá, rychlejší než například sčítání nebo odčítání.

Bitové operace je možné používat na libovolné binární řetězce, nejen na čísla. Například do osmi bitů se dá místo osmibitového čísla uložit 8 indikátorů, takzvaných flagů, nesoucích binární informaci (s hodnotami true nebo false). S těmito flagy je pak možné manipulovat zároveň pomocí binárních operací.