Electrical Engineering › Section S · Logic gates and Boolean algebra › Topic S.3

Boolean operations, laws, and DeMorgan's theorems

Boolean algebra is the arithmetic of logic circuits: a small set of laws and rules lets you rewrite any expression, and so any circuit, in a different but equivalent form. This topic states those laws, proves the less obvious rules, and shows how DeMorgan's theorems convert between AND and OR forms.

Variables, literals and terms

A Boolean variable, such as A, stands for a quantity that is 0 or 1. Its complement is written \(\overline{A}\); plain text, as on the flashcards, writes A' for a single variable and NOT(AB) for a bar over a group. Each appearance of a variable or its complement in an expression is a literal. Boolean addition is the OR operation, and a sum term is an OR of literals, such as \(A + \overline{B} + C\); it is 1 when any literal is 1. Boolean multiplication is AND, and a product term is an AND of literals, such as \(A\overline{B}C\); it is 1 only when every literal is 1. So \(A\overline{B}C = 1\) only for \(A = 1\), \(B = 0\), \(C = 1\).

The three laws

Boolean algebra shares three laws with ordinary algebra. Commutative: \(A + B = B + A\) and \(AB = BA\), so the order of gate inputs does not matter. Associative: \(A + (B + C) = (A + B) + C\) and \(A(BC) = (AB)C\), so a 3-input gate equals two 2-input gates chained. Distributive: \(A(B + C) = AB + AC\), which lets you multiply out brackets or factor out a common literal. In circuit terms, an OR of B and C followed by an AND with A does the same job as two ANDs feeding an OR.

Rules with constants and repeats

Nine basic rules follow from the gate definitions, and each can be checked by trying both values of A:

\begin{array}{l|l} \text{OR form} & \text{AND form} \\ \hline A + 0 = A & A \cdot 1 = A \\ A + 1 = 1 & A \cdot 0 = 0 \\ A + A = A & A \cdot A = A \\ A + \overline{A} = 1 & A \cdot \overline{A} = 0 \end{array}

plus double complementation, \(\overline{\overline{A}} = A\). Rows in the table are duals: swap + with · and 0 with 1 and one rule turns into the other. Notice \(A + A = A\), not 2A: there are no coefficients or powers in Boolean algebra.

Three rules that simplify

Three more rules do most of the work of simplification. Absorption: \(A + AB = A\), because factoring gives \(A(1 + B) = A \cdot 1 = A\). Second: \(A + \overline{A}B = A + B\). Third: \((A + B)(A + C) = A + BC\). The third is the distributive law with the operations swapped, which has no counterpart in ordinary arithmetic. To prove it, multiply out: \(AA + AC + AB + BC\). Since \(AA = A\), the first three terms are \(A(1 + C + B) = A\), leaving \(A + BC\). These identities reappear constantly in "Boolean simplification, standard forms, and truth tables".

Worked example: proving a rule two ways

Prove \(A + \overline{A}B = A + B\). Algebra: 1. Replace A by \(A + AB\), allowed by absorption: \(A + AB + \overline{A}B\). 2. Factor B from the last two terms: \(A + B(A + \overline{A})\). 3. Use \(A + \overline{A} = 1\): \(A + B\). Truth table, called perfect induction because it tries every case:

\begin{array}{cc|c|c} A&B&A + \overline{A}B&A + B \\ \hline 0&0&0&0 \\ 0&1&1&1 \\ 1&0&1&1 \\ 1&1&1&1 \end{array}

The two output columns match in all four rows, so the expressions are equal.

DeMorgan's theorems

Augustus De Morgan stated these two theorems for logic in the 19th century:

\overline{XY} = \overline{X} + \overline{Y}
\overline{X + Y} = \overline{X}\,\overline{Y}

In words, the complement of a product is the sum of the complements, and the complement of a sum is the product of the complements. In gate terms, a NAND equals a negative-OR and a NOR equals a negative-AND, the two symbol pairs of "Inverter, AND, OR, NAND, NOR, and XOR gates". A four-row truth table proves each. Both extend to any number of variables: \(\overline{ABC} = \overline{A} + \overline{B} + \overline{C}\) and \(\overline{A + B + C} = \overline{A}\,\overline{B}\,\overline{C}\).

Applying DeMorgan step by step

A handy summary is "break the bar and change the sign": cut a long overbar between two terms and change the operation under the cut, AND to OR or OR to AND. Work from the longest bar inward, one bar at a time. Keep the grouping: if the bar covers \(AB + CD\), breaking it gives \(\overline{AB}\,\overline{CD}\), and breaking the two shorter bars gives \((\overline{A} + \overline{B})(\overline{C} + \overline{D})\), brackets included. Where two bars end up over the same term, they cancel by double complementation. The theorems apply to whole terms, X and Y, not just to single variables.

Worked example: a bar over a product

Simplify \(\overline{(A + \overline{B})C}\) so that bars sit only on single variables. 1. The long bar covers a product of two factors, \(X = A + \overline{B}\) and \(Y = C\). Break it and change AND to OR: \(\overline{A + \overline{B}} + \overline{C}\). 2. The remaining long bar covers a sum; break it and change OR to AND: \(\overline{A}\,\overline{\overline{B}} + \overline{C}\). 3. Cancel the double bar: \(\overline{A}B + \overline{C}\). Check one case, \(A = 0\), \(B = 1\), \(C = 1\): in the original, \(A + \overline{B} = 0\), so \(\overline{0 \cdot 1} = 1\); in the result, \(1 \cdot 1 + 0 = 1\). Both give 1.

Worked example: a bar over a sum

Simplify \(\overline{\overline{AB} + C}\). 1. The outer bar covers a sum of \(X = \overline{AB}\) and \(Y = C\). Break it and change OR to AND: \(\overline{\overline{AB}}\,\overline{C}\). 2. The double bar over AB cancels: \(AB\overline{C}\). 3. Check the meaning: the original is a NOR of a NAND output with C, and the result says the output is 1 only when A and B are both 1 and C is 0. Try \(A = B = 1\), \(C = 0\): \(\overline{AB} = 0\), so the original is \(\overline{0 + 0} = 1\), and \(AB\overline{C} = 1\). Matching.

Common mistakes to avoid

First, treating \(\overline{AB}\) as \(\overline{A}\,\overline{B}\): with \(A = 0\), \(B = 1\), the first is 1 and the second 0. Breaking the bar must also change the operation. Second, forgetting brackets when DeMorgan turns a product of sums into a sum, or the reverse. Third, writing \(A + A = 2A\) or \(AA = A^2\); both are simply A. Fourth, applying the ordinary-algebra habit that \(A + BC\) cannot be factored: it equals \((A + B)(A + C)\). Fifth, breaking a short inner bar before the long outer one, which tangles the grouping.

Key takeaways

OR is Boolean addition and AND is Boolean multiplication; sum terms OR literals and product terms AND them. Commutative, associative and distributive laws hold, along with A + 0 = A, A + 1 = 1, A·0 = 0, A·1 = A, A + A = A, A·A = A, \(A + \overline{A} = 1\), \(A\overline{A} = 0\) and double complementation. Three key simplifiers: A + AB = A, \(A + \overline{A}B = A + B\) and (A + B)(A + C) = A + BC. DeMorgan: \(\overline{XY} = \overline{X} + \overline{Y}\) and \(\overline{X + Y} = \overline{X}\,\overline{Y}\), for any number of terms. Break the longest bar first, change the operation, keep the brackets, and confirm results with a truth table.

Flashcards

Flashcard

Literal

A variable or its complement in an expression

A·B'·C has three literals.

Test your understanding

Question 1 of 5

Which expression is equal to A + AB?

Question 2 of 5

By DeMorgan's theorem, NOT(A + B + C) equals which expression?

Question 3 of 5

Which expression is equal to A + A'·B?

Question 4 of 5

What does NOT(X' + Y) simplify to?

Question 5 of 5

The identity (A + B)(A + C) = A + BC is an example of which kind of rule?

← Previous topicNext topic →