4.6.5.1 - Boolean algebra and simplification

Boolean identities and absorption

An identity is true for every permitted input value, so it can replace part of an expression without changing the circuit's decision.

We use $+$ for OR, $\cdot$ for AND and a bar for NOT. These are Boolean operations on 0 and 1, not ordinary number arithmetic. In particular, $A+A=A$ and $1+1=1$.

Also $\overline{\overline A}=A$. Commutativity allows operands to swap, for example $A+B=B+A$. Associativity allows regrouping the same operation, for example $(A+B)+C=A+(B+C)$. Neither permits replacing AND by OR.

The two distributive forms are

The second form can feel unfamiliar if you expect ordinary arithmetic rules. It is valid because these are Boolean operations. Absorption also has a direct interpretation: in $A+(A\cdot B)$, if A = 1 the whole output is already 1; if A = 0, both terms are 0. B cannot change the answer.

For example,

First factor using distributivity, then apply the complement identity, then the identity value. Giving the reason for each step makes clear that the simplification holds for all A and B.

De Morgan's laws and the extent of negation

Negating a compound condition changes both its operation and the negation of its operands.

The first law says “not both A and B” is true when at least one is false. The second says “neither A nor B” is true only when both are false. To move a bar through brackets, change AND ↔ OR and negate each operand. Merely negating the operands keeps the wrong operation: $\overline{A+B}$ is not $\overline A+\overline B$.

The operands may themselves be expressions. For instance,

Work from the outermost negation inward. Keep parentheses around $\overline B+\overline C$ because the entire OR result is ANDed with $\overline A$. Dropping them could change which inputs affect the output.

If one operand is already negated, double negation can remove its bar:

These laws also connect circuits. NAND of A and B has the same output as OR of NOT A and NOT B; NOR has the same output as AND of their negations. The circuits can have different gate arrangements while remaining logically equivalent. Draw either construction in a notebook using the correct distinctive symbols and label every inversion explicitly.

Simplifying and checking equivalence

A shorter expression is useful only if it preserves the output for every possible input combination.

Consider

Apply De Morgan to the first term, remove double negation and factor the repeated A:

The derivation uses valid identities, and a truth table independently checks it:

The final columns match in all four rows. A table with only one favourable row would not establish equivalence. A mismatching row is enough to disprove it: for example A OR B and A AND B differ at A = 0, B = 1.

Simplification can remove unnecessary gates and connections. This example's output can be supplied by A directly, because B has no effect after simplification. In a more complex real implementation, propagation delay, available gate types and design constraints also matter; fewer written symbols alone do not prove every hardware design is faster.

When working, keep the original expression, make one justified transformation at a time and preserve grouping. A table is especially useful when a tempting change would accidentally negate only part of an expression. It is a semantic check rather than permission to apply ordinary algebra rules to Boolean values.