Kapitola 12
Logické funkce

Logickou funkci můžeme vyjádřit několika způsoby: slovně, graficky (pomocí mapy [Svobodova, Karnaughova], vývojovým diagramem), tabulkou (pravdivostní funkcí) nebo algebraitským vzorcem (Booleova algebra).

12.1  Booleova algebra

komutativní zákony    x + y = y + x,   x y = y x

asociativní zákony    (x + y) + z = x + (y + z),   (x y) z = x (y z)

distributivní zákony    (x + y) z = x z + y z,   x y + z = (x + z) (y + z)

zákon o vyloučeném třetím    x + x' = 1,   x x' = 0

zákon o neutrálnosti nuly    x + 0 = x

zákon o neutrálnosti jedničky    x·1 = x

zákon agresivity nuly    x · 0 = 0

zákon agresivity jedničky    x + 1 = 1

zákon o idempotenci prvků    x + x = x,   x · x = x

zákon absorpce    x + x · y = x

zákon absorpce negace    x + x' y = x + y,   x (x' + y) = x y

zákon dvojité negace    (x')' = x

De Morganovy zákony    x' y' = (x + y)',   x' + y' = (x y)'

12.2  Minimalizační metody

12.2.1  Karnaughovy mapy

12.2.2  Quine-McCluskeyho metoda

Tato metoda vychází ze stejných principů jako metoda karnaughových map. Implikantem funkce F(x₁, x₂, …, x_n) budeme nazývat každou konjunkci K(x₁, x₂, …, x_n). Implikant budeme nazývat prostým (minimálním), když vypuštěním kteréhokoliv souboru proměnné přestane být implikantem booleovy funkce. Prostým implikantem je tedy každá konjunkce minimální součtové formy dané funkce. Vlastní minimalizační metoda se uskutečňuje ve dvou etapách. V první etapě se stanoví všechny prosté implikanty. Ve druhé se pak provádí výběr minimálního počtu prostých implikantů, jejichž logický součet tvoří minimální formu.

Stanovení prostých implikantů

Vychází se z pravdivostní tabulky dané booleovy funkce. Dva stavy, kterým odpovídají konjunkce nazýváme sousedními stavy. Sousední stavy odpovídají sousedním políčkům v karnaughově mapě. Tyto dva stavy se pak zobrazují novým zkráceným stavem, kde dvě proměnné, v níž se sousední stavy liší, zapíšeme pomlčkou.

Postup při tvorbě prostých implikantů

Jednotlivé stavy roztřídíme do skupin tak, že každá skupina obsahuje pouze stavy se stejným počtem jedniček v nich obsažených. Poté seřadíme skupiny stavů pod sebe např. podle stoupajícího počtu jedniček a v nich připíšeme příslušný stavový index.

12.2.3  Patrickova metoda

Nechť {a₁, a₂, …, a_i, …, a_p} je množina všech prostých implikantů a {b₁, b₂, …, b_q} množina všech jednotlivých stavů dané funkce. Pak tabulku pokrytí definujeme jako matici TP = (c_ij), kde c_ij = 1, jestliže mezi prvky a_i a b_i je splněn vztah pokrytí. V opačném případě bude c_ij = 0. Matice má p řádků a q sloupců. Platí c_1j = Σ_{i = 1}^q c_ij, c_2j = Σ_{i = 1}^q c_ij. c_1i udává počet stavů, který udává implikant a_i a podobně c_2j udává počet implikantů, které pokrývají stav b_j. Výraz

Z = q Π j = 1  (a1 c1j+a2 c2j+…+ap cpj)

vyjadřuje tvar Patrickovy funkce , která obsahuje q závorek (tj. tolik, kolik je sloupců v tabulce pokrytí). Pro tabulku pokrytí budeme moci zapsat, jestliže prosté implikanty označíme shora dolů a₁, …, a₆