# 22 — Booleova algebra > [!abstract] O tématu > ==**Booleova algebra**== = ==**nauka o operacích na množině {0, 1}**==, využívá ==**pouze tři operace: AND, OR, NOT**==. Základ pro **digitální elektroniku** a **logické obvody v PC**. Definoval ==**George Boole (1815–1864)**==, irský matematik, ==**vymyšleno 1854, používáno až od 1938**==. > [!info] Maturitní otázka > **a)** Definice · **b)** Operace · **c)** Způsoby zápisu logické funkce · **d)** Minimalizace · **e)** Obvodové znázornění · **f)** Vzorce · **g)** Technologie reálných obvodů --- ## a) Definice Booleovy algebry ==**Booleova algebra**== je ==**nauka o operacích na množině {0, 1}**== — pracuje s proměnnými, které nabývají jen 2 hodnot: ==**0 (nepravda)**== nebo ==**1 (pravda)**==. Využívá pouze ==**tři základní operace**==: ==**logický součin (AND)**==, ==**logický součet (OR)**== a ==**negaci (NOT)**==. > [!info] Logický vs. aritmetický součet > Logická operace ==**nepoužívá žádné přenosy do vyššího řádu**== — žádný řád čísla nemá vliv na ostatní řády (oproti aritmetickému `+`). ### Základní pojmy - ==**Logická proměnná**== (A, B, C, X, Y) — nabývá hodnoty 0 nebo 1 - ==**Logická funkce**== — funkce, jejíž výstup závisí na vstupech (jen 0/1) - ==**Pravdivostní tabulka**== — zachycuje výstup pro všechny kombinace vstupů --- ## b) Operace v Booleově algebře ### Základní operace | Operace | Symbol | Význam | Zápis | |---|---|---|---| | ==**AND**== (logický součin) | · nebo ∧ | **a zároveň** | A·B nebo AB nebo A∧B | | ==**OR**== (logický součet) | + nebo ∨ | **nebo** | A+B nebo A∨B | | ==**NOT**== (negace) | ¯ nebo ¬ | **ne** | Ā nebo ¬A | ### Pravdivostní tabulky základních operací #### AND (A · B) | A | B | A·B | |---|---|---| | 0 | 0 | 0 | | 0 | 1 | 0 | | 1 | 0 | 0 | | 1 | 1 | **1** | #### OR (A + B) | A | B | A+B | |---|---|---| | 0 | 0 | 0 | | 0 | 1 | 1 | | 1 | 0 | 1 | | 1 | 1 | 1 | #### NOT (Ā) | A | Ā | |---|---| | 0 | 1 | | 1 | 0 | ### Složené operace | Operace | Význam | Vzorec | |---|---|---| | ==**NAND**== | NOT AND | ¬(A·B) | | ==**NOR**== | NOT OR | ¬(A+B) | | ==**XOR**== (exclusive OR) | „buď A nebo B, ale ne oba" | A⊕B = A·¬B + ¬A·B | | ==**XNOR**== | NOT XOR | ¬(A⊕B) | > [!info] Univerzální hradla > ==**NAND a NOR jsou univerzální**== — pomocí kombinace samotných NAND (nebo samotných NOR) lze postavit **jakoukoliv logickou funkci**. --- ## c) Způsoby zápisu logické funkce Učitel uvádí ==**5 způsobů zápisu**==: pravdivostní tabulka, Vennovy diagramy, logická funkce, N-rozměrná krychle, Karnaughova mapa. ### 1. Pravdivostní tabulka ==**Tabulka všech pravdivostních ohodnocení**== — pro každou kombinaci vstupů uvedena výstupní hodnota. | Výhody | Nevýhody | |---|---| | jednoduché určení konkrétní hodnoty funkce | pro více proměnných nepřehledná | | zapsána veškerá pravdivostní hodnocení | ==**chybí minimalizace**== | | | nevhodná pro realizaci obvodů | ### 2. Vennovy diagramy ==**Grafické znázornění v rovině**== (kolečka pro množiny). | Výhody | Nevýhody | |---|---| | názorné grafické znázornění | ==**maximálně 3 proměnné**== | | | chybí minimalizace | | | nepoužitelné pro realizaci obvodů | ### 3. Logická funkce (algebraický zápis) ==**Funkce zapsaná pomocí AND, OR, NOT**==. Lze ji pomocí ==**matematických úprav (axiomy)**== převést na ==**minimalizovaný stav**== — ten, který už **nelze dále zjednodušit**. > Příklad: F = A·B + ¬A·C | Výhody | Nevýhody | |---|---| | ==**lze minimalizovat**== | složitá a nepřehledná minimalizace | | použitelné pro realizaci integrovaných obvodů | jednotlivé úpravy ne vždy vedou k cíli | | | zdlouhavé | ### 4. N-rozměrná krychle ==**Grafické znázornění v prostoru**== — vrcholy krychle ohodnocené hodnotami funkce. Stejně ohodnocené body se spojují. | Výhody | Nevýhody | |---|---| | vhodná pro směrovací algoritmy | pro vyšší počet proměnných nepřehledná | | minimalizace pomocí grafových algoritmů | pro člověka zdlouhavá realizace | | vhodná pro zpracování počítačem | | ### 5. Karnaughova mapa ==**Speciální mřížka pro minimalizaci**== (viz [d]) — nejvhodnější pro realizaci integrovaných obvodů. ### Doplňkové formy (mintermy / maxtermy) - ==**Mintermy (úplná DNF)**== — součet (OR) součinů, jeden minterm pro každý řádek, kde F = 1 - ==**Maxtermy (úplná KNF)**== — součin (AND) součtů, jeden maxterm pro každý řádek, kde F = 0 --- ## d) Minimalizace logických funkcí ==**Minimalizace**== = ==**zjednodušení booleovského výrazu**== → méně hradel → levnější obvod. ### Karnaughova mapa (K-mapa) — POSTUP 1. ==**Vytvoř pravdivostní tabulku**== dané funkce 2. ==**Nakresli mapu**== — počet políček = počet řádků tabulky (vždy mocnina dvou) 3. ==**Políčka očísluj Grayovým kódem**== (sousední se liší jen v 1 bitu) 4. Do políček ==**vlož ohodnocení z pravdivostní tabulky**== 5. ==**Vytvoř smyčky**== spojováním sousedních jedniček: - ==**počet jedniček ve smyčce musí být mocnina 2**== (1, 2, 4, 8…) - ==**jedničky musí tvořit čtverec nebo obdélník**== 6. Z jednotlivých smyček ==**minimalizuj funkci**==: - ==**každá smyčka = jeden součinový člen**== - ve členu se objeví **jen proměnná, která pro celou smyčku nemění hodnotu** - pokud je smyčka v nulové části proměnné → **proměnná negovaná** - pokud je smyčka v jedničkové části proměnné → **proměnná bez negace** - proměnné, které se ve smyčce mění, ==**se ve výsledku neobjeví**== - ==**proměnné se ve členu oddělují součinem, jednotlivé smyčky součtem**== ### Pravidla pro skupiny - ==**Co největší skupiny**== (eliminují víc proměnných) - ==**Mohou se překrývat**== - ==**Mohou „obíhat" hrany mapy**== (krajní buňky sousedí) | Výhody K-mapy | Nevýhody K-mapy | |---|---| | ==**lze minimalizovat (jednoznačně a opravdu minimálně)**== | používá Grayův kód | | vhodná i pro vyšší počet proměnných | (lze odstranit použitím Svobodovy mapy) | | ==**nejvhodnější pro realizaci integrovaných obvodů**== | | --- ## e) Obvodové znázornění logických operací ### Standardní značky hradel Každé hradlo má svůj **grafický symbol** (US/IEC): | Hradlo | Tvar | Funkce | |---|---|---| | ==**AND**== | „D" tvar (zaoblený vpravo) | logický součin | | ==**OR**== | „štít" (vyhloubený vlevo, špičatý vpravo) | logický součet | | ==**NOT**== | trojúhelník s **kolečkem na výstupu** | negace | | ==**NAND**== | AND + **kolečko na výstupu** | negovaný součin | | ==**NOR**== | OR + **kolečko na výstupu** | negovaný součet | | ==**XOR**== | OR s **dvojitým obloukem vlevo** | exkluzivní součet | > [!info] Pravidlo kolečka > ==**Malé kolečko (puntík) na výstupu hradla = negace**==. Proto NAND = AND + puntík, NOR = OR + puntík. ### Pravidla obvodového znázornění (dle učitele) - ==**vstupy vlevo, výstupy vpravo**== - ==**spoje vždy rovnoběžně s okraji**== - ==**hradla se nesmí otáčet**== - ==**hradla stejně velká**== - spoje by se neměly křížit ### Stavba složitých obvodů Libovolná logická funkce → schéma z hradel → realizace na čipu. --- ## f) Vzorce Booleovy algebry ### Axiomy (nedokazují se, jsou součástí definice) | Zákon | Vzorec | |---|---| | ==**Zákon o neutralitě 0 a 1**== | A + 0 = A; A · 1 = A | | ==**Zákon o agresivitě 0 a 1**== | A · 0 = 0; A + 1 = 1 | | **Komutativní** | A + B = B + A; A · B = B · A | | **Asociativní** | A · (B · C) = (A · B) · C; A + (B + C) = (A + B) + C | | ==**Zákon o vyloučení třetího**== | A · ¬A = 0; A + ¬A = 1 | | **Zákon dvojí negace** | ¬(¬A) = A | | **Idempotence** | A · A = A; A + A = A | | **Distributivní** | A · (B + C) = A·B + A·C; A + (B · C) = (A+B) · (A+C) | | ==**De Morganův zákon**== | ¬(A · B) = ¬A + ¬B; ¬(A + B) = ¬A · ¬B | ### Odvozené vzorce (vycházejí z axiomů) | Zákon | Vzorec | |---|---| | ==**Absorpce**== | A · (A + B) = A; A + (A · B) = A | | ==**Absorpce negace**== | A · (¬A + B) = A · B; A + (¬A · B) = A + B | ### De Morganovy zákony — KLÍČOVÉ > [!quote] Augustus De Morgan (1806–1871), britský matematik, navázal na Booleovu algebru > ==**¬(A · B) = ¬A + ¬B**== > ==**¬(A + B) = ¬A · ¬B**== > > *Negace součinu = součet negací. Negace součtu = součin negací.* --- ## g) Technologie reálných logických obvodů ==**Reálná hardwarová realizace hradel**== — historický vývoj logických rodin: | Technologie | Princip | Poznámka | |---|---|---| | ==**DL**== (diodová logika) | jen diody | ==**nelze vytvořit negaci**== — chybí aktivní prvek (malý logický zdvih) | | ==**DTL**== (diodo-tranzistorová) | diody + tranzistor | ==**odstraňuje nevýhody DL**== | | ==**RTL**== (odporo-tranzistorová) | odpory + tranzistory | starší rodina | | ==**TTL**== (tranzistoro-tranzistorová) | bipolární tranzistory na vstupu i výstupu | ==**řada 74xx**==, +5 V | | ==**CMOS**== (Complementary MOS) | ==**dva unipolární tranzistory NMOS + PMOS**== | ==**nižší spotřeba než bipolární**==, řada 40xx | --- ## Shrnutí > [!summary] Co si pamatovat > **a) Definice:** ==**nauka o operacích na množině {0,1}**==, George Boole (1854). Tři operace: AND, OR, NOT. > **b) Operace:** ==**AND, OR, NOT**== + ==**NAND, NOR, XOR**==. ==**NAND/NOR jsou univerzální**==. > **c) Zápis:** ==pravdivostní tabulka, Vennovy diagramy, logická funkce, N-rozměrná krychle, K-mapa==. > **d) Minimalizace:** ==**Karnaughova mapa**== — Grayův kód, smyčky mocnin 2, čtverec/obdélník, smyčky se sčítají, proměnné v členu se násobí. > **e) Schéma:** vstupy vlevo, výstupy vpravo, kolečko na výstupu = negace. > **f) Vzorce:** axiomy (neutralita, agresivita, vyloučení třetího, idempotence, distributivita), odvozené (absorpce, absorpce negace), ==**De Morgan: ¬(A·B) = ¬A + ¬B**==. > **g) Technologie:** ==**DL → DTL → RTL → TTL (74xx) → CMOS (40xx)**==.