Digital Logic Design: Boolean Algebra

What is Boolean algebra?

We’ve been doing arithmetic on base-10 numbers since grade school. We learned a few primitive operators—addition, subtraction, multiplication, division—and used them to manipulate operands. Digital logic follows the same idea in the base-2 realm. We can perform complex operations, like binary arithmetic, by chaining the primitive operators:

De Morgan’s Laws

It’s often convenient to reduce complex expressions–such as inverting a long sequence of logical statements–to ones that only invert input values. De Morgan’s laws make such simplifications possible.

\overline{x + y} = \bar{x} \cdot \bar{y} — *De Morgan’s Laws were developed by the British mathematician Augustus de Morgan in the 19th century*

\overline{1 + 1} = \bar{1} \cdot \bar{1} = 0 — *De Morgan’s Laws were developed by the British mathematician Augustus de Morgan in the 19th century*

Conveniently, De Morgan’s Laws allow us to express gates in terms of each other. $\overline{x + y}$ and $\overline{x \cdot y}$ are the NOR and NAND gates, respectively. This means that NOR is the result of ANDing the inverted operands, and NAND is the result of ORing the inverted operands. In fact, by inverting the operands and the output, we can derive AND in terms of OR.

$\overline{\overline{x} + \overline{y}} = x \cdot y$

(This follows from the identity $\overline{\overline{x}} = x$ )

Challenge Problem

This problem was taken from this public ECE 2020 practice set.

$\text {Simplify } \overline{\overline{(\overline{(\overline{A} + B)} + C)} + \overline{(D + \overline{(E + \overline{F})})}}$

Use De Morgan’s Laws to eliminate the outermost two bars and replace the inner OR operation with AND.

$(\overline{(\overline{A} + B)} + C) \cdot (D + \overline{(E + \overline{F})})$

Then, apply De Morgan’s twice to simplify the $\overline{(\overline{A} + B)}$ and $\overline{(E + \overline{F})}$ terms.

$(A\overline{B} + C)(D + \overline{E}F)$

Operator	Operator Type	Rule	Examples	Algebraic Representation
NOT	Unary	Invert the input	NOT 1 = 0 NOT 0 = 1
AND	Binary	True only if both operands are true; otherwise, false	1 AND 1= 1 1 AND 0 = 0
OR	Binary	True if at least one of the operands is true; otherwise, false	1 OR 1 = 1 1 OR 0 = 1	$x + y$
NAND	Binary	Invert AND	1 NAND 1 = 0 1 NAND 0 = 1	$\overline{x \cdot y}$
NOR	Binary	Invert OR	1 NOR 1 = 0 1 NOR 0 = 0	$\overline{x + y}$

Expression	Example
$\overline{x + y} = \bar{x} \cdot \bar{y}$	$\overline{1 + 1} = \bar{1} \cdot \bar{1} = 0$
$\overline{x \cdot y} = \bar{x} + \bar{y}$	$\overline{1 \cdot 1} = \bar{1} + \bar{1} = 0$