3.1
Booleova algebra a její zákony
Definice
Pojmem algebra označujeme obecně matematický prostor obsahující definice matematických symbolů (prvků), operací a pravidel pro jednoznačnou manipulaci s těmito symboly.
Definice
Booleova algebra je algebra, ve které jsou definovány dva vzájemně různé symboly, logická 1 a logická 0, a která obsahuje tři operace - logický součin, logický součet a negaci. Zahrnuje a definuje pravidla a zákony pro jednoznačné operace s těmito symboly za použití výše uvedených logických funkcí.
Souhrn
Booleova algebra je součástí obecné matematické algebry a zaměřuje se na matematickou logiku.
Zajímavost
Booleova algebra byla pojmenována na počest britského matematika George Boolea (1815-1864), který ve svém díle The Laws of Thought (1854) shrnul a položil základy matematické logiky. Je tak dnes považován za jednoho z prvních zakladatelů informatiky.
+
12. George Boole
Zdroj: George Boole, mathematician, 1815-1864, license Public domain
Obr. 12. George Boole
Základem Booleovy algebry je úplný soubor funkcí obsahující logický součin, logický součet a negaci (soubor tak není minimální) a operující s hodnotami logická 1 a logická 0. Algebra je založena na celkem 16 zákonech:
  1. Asociativita logického součtu – použití závorek při operacích s logickým součtem:
    a∨b∨c=a∨b∨c .
  1. Asociativita logického součinu – použití závorek při operacích s logickým součinem:
    a⋅b⋅c=a⋅b⋅c .
  1. Komutativita logického součtu – nezávislost pořadí při operacích s logickým součtem:
    a∨b=b∨a .
  1. Komutativita logického součinu – nezávislost pořadí při operacích s logickým součinem:
    a⋅b=b⋅a .
  1. Distributivní zákon – distributivita logického součinu vůči logickému součtu:
    a⋅b∨c=a⋅b∨a⋅c ,
    a∨b⋅a∨c=a∨b⋅c .
  1. Zákon o vyloučení třetího – současná platnost či neplatnost proměnné a její negace v případě logického součtu a logického součinu:
    a∨a¯=1 ,
    a⋅a¯=0 .
  1. Zákon agresivity nuly – logický součin proměnné s logickou 0:
    a⋅0=0 .
  1. Zákon agresivity jedničky – logický součet proměnné s logickou 1:
    a∨1=1 .
  1. Zákon neutrálnosti nuly – logický součet proměnné s logickou 0:
    a∨0=a .
  1. Zákon neutrálnosti jedničky – logický součin proměnné s logickou 1:
    a⋅1=a .
  1. Zákon o idempotenci prvků – logický součin i logický součet týchž proměnných:
    a⋅a=a ,
    a∨a=a .
  1. Zákon absorpce negace – absorpce negace logickým součtem i logickým součinem:
    a∨a¯⋅b=a∨b ,
    a¯∨a⋅b=a¯∨b .
  1. Zákon absorpce – absorpce logickým součtem i logickým součinem:
    a⋅a∨b=a ,
    a∨a⋅b=a .
  1. Zákon dvojité negace – sudý stupeň negace:
    a¯¯=a .
  1. Zákon o negaci logického součinu:
    a⋅b¯=a¯∨b¯ .
  1. Zákon o negaci logického součtu:
    a∨b¯=a¯⋅b¯ .
Zajímavost
Poslední dva zákony Booleovy algebry, zákon o negaci logického součinu a zákon o negaci logického součtu, se také často označují jako De Morganovy zákony nebo jako De Morganova pravidla. Jsou pojmenována po britském matematikovi Augustu De Morganovi (1806-1871).
+
13. Augustus De Morgan
Zdroj: Author Sophia Elizabeth De Morgan, Picture of Augustus De Morgan, the mathematician, license Public domain
Obr. 13. Augustus De Morgan
Pravidla a zákony Booleovy algebry slouží nejen pro úpravy logických výrazů a tvarů logických výrazů, ale i pro jejich zjednodušování (tzv. minimalizaci), převody forem a úpravy výrazů pro potřeby jejich vyjádření konkrétní logickou funkcí. K tomu se v praxi nejčastěji využívá poslední trojice zákonů – zákon dvojité negace, zákon o negaci logického součinu a zákon o negaci logického součtu. Uveďme si příklady pro jejich využití.
Příklad
Nalezněte pomocí zákonů Booleovy algebry negaci funkce f:
f=a⋅b∨a⋅b∨c .
Zobrazit řešení
Řešení
Řešení:
Nejprve provedeme negaci obou stran rovnice a budeme tak hledat negaci funkce f:
f¯=a⋅b∨a⋅b∨c¯
Dále budeme upravovat výraz za použití zákonů o negaci logického součtu a negaci logického součinu. Můžeme postupovat po krocích, nezapomeneme doplnit závorky, pokud to pořadí operací vyžaduje:
f¯=a⋅b∨a⋅b∨c¯=a⋅b¯⋅a⋅b∨c¯=a¯∨b¯⋅a¯∨b∨c¯=a¯∨b¯⋅a¯∨b¯⋅c¯
Příklad
Zjednodušte vyjádření funkce f pomocí zákonů Booleovy algebry:
f=a⋅b∨a⋅b¯⋅c∨a⋅c¯¯
Zobrazit řešení
Řešení
Řešení:
Budeme postupně aplikovat jednotlivé zákony a výraz upravovat v krocích:
f=a⋅b∨a⋅b¯⋅c∨a⋅c¯¯=a⋅b∨a⋅b¯⋅c∨a⋅a⋅c¯¯=a⋅b∨a¯∨b∨c¯⋅a¯∨c==a⋅b∨a¯⋅a¯∨a¯⋅c∨a¯⋅b∨b⋅c∨a¯⋅c¯∨c⋅c¯=b⋅a∨a¯∨a¯⋅1∨c∨c¯==b∨a¯