Boolean algebra and identities

Why it exists

A digital circuit is built from switches that are on or off. Boolean algebra is the arithmetic of such two-valued signals. It lets you take a description of what a circuit must do, rewrite it into the cheapest equivalent expression, prove that two circuits behave identically, and convert between gate types. Almost every other topic in this subject is an application: Karnaugh maps and Quine-McCluskey are systematic simplification, adders and multiplexers are built by writing the function and simplifying it, and flip-flop inputs are Boolean functions of the current state.

GATE asks three kinds of questions here: simplify an expression to a given form, decide whether two expressions are equal (or whether an identity holds), and count or characterise functions.

Prerequisites

None. This is a starting point.

None. Familiarity with the bitwise operators of C helps: &, |, ^ and ~ on single bits behave exactly like AND, OR, XOR and NOT.

Precise definitions

Boolean values and operations. A Boolean variable takes the value 0 or 1. The three basic operations are

Precedence. NOT first, then AND, then OR, unless parentheses say otherwise. So $A + BC$ means $A + (BC)$, and $A'B$ means $(A')\cdot B$.

Boolean function. A function $f : \{0,1\}^n \to \{0,1\}$. It is completely described by its truth table with $2^n$ rows. Two expressions are equal exactly when their truth tables are equal. Consequently the number of different Boolean functions of $n$ variables is $2^{2^n}$: 4 for $n = 1$, 16 for $n = 2$, 256 for $n = 3$, 65536 for $n = 4$.

Basic laws. For all $x, y, z$ (each law has an AND form and an OR form):

Note that the OR-over-AND distributive law, $x + yz = (x+y)(x+z)$, has no counterpart in ordinary arithmetic.

De Morgan for many variables. $(x_1 x_2 \cdots x_n)' = x_1' + x_2' + \cdots + x_n'$ and $(x_1 + x_2 + \cdots + x_n)' = x_1' x_2' \cdots x_n'$.

Complement of a function. To complement an expression, swap AND with OR and complement every literal (apply De Morgan repeatedly). Do not forget to keep the grouping. For $F = AB' + AC + A'B$ the complement is $F' = A'B' + ABC'$ (checked in example 4).

Dual. The dual $F^d$ of an expression is obtained by swapping AND with OR and 0 with 1, leaving the literals alone. As a function, $F^d(x_1,\dots,x_n) = \big(F(x_1',\dots,x_n')\big)'$. The duality principle: if two expressions are equal, their duals are equal. A function with $F = F^d$ is self-dual; the number of self-dual functions of $n$ variables is $2^{2^{n-1}}$ (4 for $n = 2$, 16 for $n = 3$).

Complement is not dual. The dual of $F = AB + C'$ is $(A+B)C'$, but its complement is $(A'+B')C$.

XOR and XNOR. $x \oplus y = xy' + x'y$ is 1 when the inputs differ. $x \odot y = (x \oplus y)' = xy + x'y'$ is 1 when they are equal. Properties: commutative, associative, $x \oplus 0 = x$, $x \oplus 1 = x'$, $x \oplus x = 0$, $x \oplus x' = 1$, $x(y \oplus z) = xy \oplus xz$, and $x + y = x \oplus y \oplus xy$. An $n$-input XOR is 1 exactly when an odd number of inputs are 1 (the parity function), so it is 1 on half of the rows ($2^{n-1}$). Complementing one input complements the output: $(x \oplus y)' = x' \oplus y = x \oplus y'$.

Shannon expansion. For any function and variable $x$: $f = x \cdot f(x{=}1) + x' \cdot f(x{=}0)$. It is the basis of multiplexer implementations.

No cancellation. From $x + y = x + z$ you cannot conclude $y = z$, and likewise for $xy = xz$ (take $x = 1$ for the first, $x = 0$ for the second). Only if both hold can you cancel.

How it works

There is no hidden mechanism here: an identity is true if and only if its truth table is the same on both sides, so any claim can be checked mechanically. The program below checks four identities by looping over all assignments, exactly as a truth table does.

#include <stdio.h>
 
int main(void) {
    int de_morgan = 1, absorb = 1, simplify = 1, distribute = 1;
    printf("A B | A+A'B  A+B | AB+AB'  A\n");
    for (int a = 0; a < 2; a++) {
        for (int b = 0; b < 2; b++) {
            int lhs = a || (!a && b);
            int rhs = a || b;
            int c1 = (a && b) || (a && !b);
            printf("%d %d |   %d      %d  |   %d      %d\n", a, b, lhs, rhs, c1, a);
            if (lhs != rhs) simplify = 0;
            if (c1 != a) absorb = 0;
            if (!(a && b) != (!a || !b)) de_morgan = 0;
            for (int c = 0; c < 2; c++)
                if ((a || (b && c)) != ((a || b) && (a || c))) distribute = 0;
        }
    }
    printf("De Morgan %d, combining %d, A+A'B=A+B %d, OR distributes over AND %d\n", de_morgan, absorb, simplify, distribute);
    return 0;
}

A B | A+A'B  A+B | AB+AB'  A
0 0 |   0      0  |   0      0
0 1 |   1      1  |   0      0
1 0 |   1      1  |   1      1
1 1 |   1      1  |   1      1
De Morgan 1, combining 1, A+A'B=A+B 1, OR distributes over AND 1

The columns for $A + A'B$ and $A + B$ are identical, which proves the simplification law. The columns $AB + AB'$ and $A$ are identical, which proves the combining law.

Step through three identities and one non-identity. Each table fills in one input row at a time, with the sub-expressions as separate columns, and the last step compares the two sides. Every cell is computed by a script, not typed in.

The last table shows why "dual" and "complement" must not be confused: the dual of $F = AB + C'$ (swap the operators, keep the literals) is a different function from its complement, even though the dual does equal the complement of $F$ evaluated at complemented inputs.

Method for simplification by algebra. Look for, in this order: common factors (distribute and combine), the pattern $x + x'y$ (replace by $x + y$), absorption $x + xy$, the consensus term $yz$ in $xy + x'z + yz$ (delete it), then De Morgan to push complements down to single variables. If a result is not obviously minimal, switch to a Karnaugh map; algebra is quick when a pattern is visible and unreliable otherwise.

Worked examples

Cheat box

Traps and GATE patterns

Connections

The expressions here become circuits in logic gates; the sum-of-products and product-of-sums forms built from minterms and maxterms are in SOP, POS, minterms and maxterms; systematic simplification is the Karnaugh map; and the statement that NAND (or NOR) alone is enough is in functional completeness and duality. The operators &, |, ^, ~ in C are this algebra applied to every bit of a word, see C types and operators.

PYQs

Consider the Boolean expression

F(P, Q) = (P̅ + Q) ⊕(P̅Q).
Which
of
the
following expressions is equivalent to F?

Which one of the following options is not a property
of Boolean Algebra?

Which of the following Boolean algebraic
equation(s) is/are CORRECT?

Let X be a 3-variable Boolean function that produces
output as '1' when at least two of the         input
variables are '1'. Which of the following statement(s)
is/are CORRECT, where a, b, c, d, e are Boolean
variables?

For a Boolean variable x, which of the following
statements is/are FALSE?

Consider the following Boolean expression.

F = (X + Y + Z)(X̅ + Y)(Y̅ + Z)

Which of the following Boolean expressions is/are
equivalent to F̅ (complement of F)?

Which one of the following is NOT a valid
identity?

Let ⊕ and ⊙ denote the Exclusive OR and
Exclusive NOR operations, respectively. Which one
of the following is NOT CORRECT?

If w, x, y, z are Boolean variables, then which one of
the following is INCORRECT?

Let, x1 ⊕ x2 ⊕ x3 ⊕ x4 = 0 where x1, x2, x3, x4 are
Boolean variables, and ⊕ is the XOR operator.
Which one of the following must always be TRUE?

Consider the Boolean operator # with the following
properties:
         x # 0 = x
         x # 1 = x̅
         x # x = 0
         x # x̅ = 1

Then x # y is equivalent to

Let ⊕ denote the exclusive OR (XOR) operation.
Let '1' and '0' denote the binary constants. Consider
the following Boolean expression for F over two
variables P and Q:

F(P, Q) = ((1 ⊕ P) ⊕ (P ⊕ Q)) ⊕ ((P ⊕ Q) ⊕ (Q
⊕ 0))

The equivalent expression for F is

If P, Q, R are Boolean variables, then

(P + Q̅)(P·Q̅ + P·R)(P̅·R + Q̅) simplifies to

Define the connective * for the Boolean variables X
and Y as:
            X * Y = XY + X'Y'.

Let Z = X * Y. Consider the following expressions
P, Q and R.
                P: X = Y * Z,
                Q: Y = X * Z,
                R: X * Y * Z = 1

Which of the following is TRUE?

Which of the following expressions is equivalent
to (A ⊕ B) ⊕ C ?

Self-check

Revision card

References