Bc. Vojtěch Hordějčuk / Wiki / Kombinační obvody / Logická hradla a Booleova algebra

Logická hradla a jejich výrazy v Booleově algebře

Každé logické hradlo můžeme považovat za určitou logickou funkci v Booleově algebře:

Hradlo NOT (negace)

Hradlo NOT (invertor) vrací na výstupu opačnou hodnotu než na vstupu.

Hradlo AND (logický součin)

Hradlo AND vrací logickou 1 právě tehdy, když je logická 1 na všech vstupech.

$y = a_1 \land a_2 \land ... \land a_n$

Hradlo OR (logický součet)

Hradlo OR vrací logickou 1 právě tehdy, když je logická 1 alespoň na jednom vstupu.

$y = a_1 \lor a_2 \lor ... \lor a_n$

Hradlo XOR (exkluzivní součet)

Hradlo XOR vrací logickou 1 právě tehdy, když je na vstupech lichý počet logických 1.

Nejprve si definujme operaci XOR:

$x \otimes y = (x \land -y) \lor (-x \land y)$

Nyní operaci XOR použijeme ve vzorci pro vyjádření výstupu hradla XOR:

$y = a_1 \otimes a_2 \otimes ... \otimes a_n$

Hradlo NAND (negovaný logický součin, Shefferův funktor)

Hradlo NAND vrací opačnou hodnotu než hradlo AND se stejnými hodnotami na vstupu.

$y = - (a_1 \land a_2 \land ... \land a_n)$

Hradlo NOR (negovaný logický součet, Piercův funktor)

Hradlo NOR vrací opačnou hodnotu než hradlo OR se stejnými hodnotami na vstupu.

$y = - (a_1 \lor a_2 \lor ... \lor a_n)$

Vzájemné nahrazení hradel

Někdy je potřeba nahradit jeden typ hradla jiným – ať už z důvodů ekonomických, výkonnostních či jiných. Naštěstí nám to zákony Booleovy algebry umožňují. Těchto zákonů tedy využijeme a zjistíme, jak nahradit hradlo AND hradlem OR a obráceně.

Nahrazení hradla OR hradlem AND

Vyjdeme z Booleovského výrazu pro hradlo OR.
Použijeme vlastnost dvojité negace.
Výraz upravíme pomocí de Morganových pravidel.

$a \lor b = -(-(a \lor b)) = -(-a \land -b)$

Nahrazení hradla AND hradlem OR

Vyjdeme z Booleovského výrazu pro hradlo AND.
Použijeme vlastnost dvojité negace.
Výraz upravíme pomocí de Morganových pravidel.

$a \land b = -(-(a \land b)) = -(-a \lor -b)$

Obecné poznatky

V obou případech jsou postupy i výsledky dost podobné. Shrneme tedy naše poznatky a zapíšeme si pravidla pro nahrazování hradel AND a OR:

Negujeme všechny vstupy.
Negujeme všechny výstupy.
Změníme typ hradla.

Bc. Vojtěch Hordějčuk

„Kdo byl někdy na horách, ví, co je parciální derivace.” - L. Zajíček

Domů » Wiki » Kombinační obvody » Logická hradla a Booleova algebra