Truth Tables

What is a Truth Table?

A truth table is a structured way to list all possible input combinations and their corresponding outputs for a logic expression or circuit.

Constructing Truth Tables

To build a truth table for a logic circuit or Boolean expression:

  • Identify the number of unique inputs.
  • Generate all possible combinations of 0s and 1s for these inputs.
  • Apply the logical operations row by row to determine outputs.

Truth Table for Basic Logic Gates

Input A Input B A AND B A OR B A XOR B A NAND B A NOR B A XNOR B
00000111
01011100
10011100
11110001

Single Input Gate: NOT

The NOT gate, also known as an inverter, takes a single input and outputs the opposite value.

Input NOT
01
10

Analysing Truth Tables

Truth tables allow us to:

  • Determine how different combinations of inputs affect output.
  • Match Boolean expressions to gate behavior.
  • Simplify logic expressions for more efficient circuit design.

Worked Example: Truth Table for Boolean Expression

Expression: F = (A AND B) OR NOT C

A B C A AND B NOT C F = (A AND B) OR NOT C
000011
011000
100011
111101

Boolean Algebra and Simplification

Using truth tables, Boolean expressions can be simplified through:

  • De Morgan’s Laws: helpful for converting AND/OR gates with NOTs.
Original Expression Equivalent Expression
NOT (A AND B)(NOT A) OR (NOT B)
NOT (A OR B)(NOT A) AND (NOT B)
  • Boolean Identities: core simplification rules that reduce logical expressions.
    • Law Expression Equivalent
    Identity LawA AND 1A
    Identity LawA OR 0A
    Null LawA AND 00
    Null LawA OR 11
    Idempotent LawA AND AA
    Idempotent LawA OR AA
    Inverse LawA AND NOT A0
    Inverse LawA OR NOT A1
    Double NegationNOT (NOT A)A
    Commutative LawA AND BB AND A
    Commutative LawA OR BB OR A
    Associative LawA AND (B AND C)(A AND B) AND C
    Associative LawA OR (B OR C)(A OR B) OR C
    Distributive LawA AND (B OR C)(A AND B) OR (A AND C)
    Distributive LawA OR (B AND C)(A OR B) AND (A OR C)
    Absorption LawA OR (A AND B)A
    Absorption LawA AND (A OR B)A

    Using Identities to simplify expressions

    Expression: (A AND NOT B) OR NOT A

    1. Apply the Distributive Law:
      (A OR NOT A) AND (NOT B OR NOT A)
    2. Simplify using Identity:
      A OR NOT A is always true (1), so:
      1 AND (NOT B OR NOT A)
    3. Final simplified expression:
      NOT B OR NOT A
    A B NOT A NOT B A AND NOT B (A AND NOT B) OR NOT A NOT B OR NOT A
    0011011
    0110011
    1001111
    1100000

    Observation: The output columns for both expressions are identical, confirming their logical equivalence.

  • Karnaugh Maps (K-Maps): visual tools used to simplify Boolean expressions by grouping adjacent cells that represent 1s in the truth table.

Deep Dive: Karnaugh Maps (K-Maps)

K-Maps are especially useful for simplifying logic with 2 to 4 input variables.

Each cell in the K-Map corresponds to a row in a truth table, and grouping 1s in rectangles of sizes 1, 2, 4, 8, etc, allows redundant terms to be eliminated, leading to a minimal expression.

By using K-Maps, designers can reduce the number of gates in a circuit, thus reducing costs, improving efficiency and performance.

  • Each cell corresponds to a row in the truth table.
  • Fill in 1s and 0s based on the function output.
  • Group adjacent 1s in rectangles of size 1, 2, 4, etc. (powers of two); each group eliminates one variable.
  • Each group gives a term in the simplified expression.

This process reduces the number of logic gates needed.

Worked Examples

Simplify F(A,B) = (NOT (A) AND B)) OR (A AND NOT B) OR (A AND B)

Start from the expression: (NOT (A) AND B)) OR (A AND NOT B) OR (A AND B). This output is 1 when the input is 01, 10, or 11.

A B NOT A [C] NOT B [D] C AND B [E] A AND D [F] A AND B [G] F = E OR F OR G
0 0 1 1 0 0 0 0
0 1 1 0 1 0 0 1
1 0 0 1 0 1 0 1
1 1 0 0 0 0 1 1

Only the combinations 01, 10, and 11 produce output 1. Now plot them on the 2-variable K-Map:

A\B 0 1
0 0 1
1 1 1

We can group the three 1s in two different ways to get equivalent but structurally different intermediate expressions:

Option 1:

A\B 0 1
0 0 1
1 1 1

Group of two ⇒ B Single ⇒ A AND NOT B

  • Single cell: A AND NOT B (cell 10)
  • Group of two: B (cells 01 and 11)

Expression: F = B OR (A AND NOT B)

Option 2:

A\B 0 1
0 0 1
1 1 1

Group of two ⇒ A Single ⇒ NOT A AND B

Expression: F = A OR (NOT A AND B)

  • Group of two: A (cells 10 and 11)
  • Single cell: B AND NOT A (cell 01)

Expression: F = A OR (B AND NOT A)

Both expressions are logically equivalent. Using Boolean algebra (Distributive and Inverse laws) you can simplify either further to:

Final simplified expression: F = A OR B

Challenge: Try building truth tables for each form to convince yourself they all produce the same outputs.

Before we start, here's a little 'Boolean expression' hack: if we know the behaviour of the function - ie we know when the output is 0 or 1 - we can simply write the expression as a Function.

For our mysterious (inefficient) function, imagine we know the Output is 1 for inputs 1, 3, 5, and 7 ... or in binary 001, 011, 101, and 111).

We can simply the expression as a Boolean function: F(A, B, C) = Σ(1, 3, 5, 7)

A B C Decimal F(A, B, C)
00000
00111
01020
01131
10040
10151
11060
11171

Just as with 2 inputs: fill the truth table, then plot the 3-variable K-Map (2 rows × 4 columns in Gray code order).
Note: Gray code order is an ordering system where two successive values differ in only one bit (binary digit). e.g. 00 and 01 differ by only 1 bit; whereas 01 and 10 differ by 2 bits (a 0 has become a 1, and a 1 has become a 0). It is not the denary value that matters; it is the number of bits that are different. Gray Code reference.

A\BC 00 01 11 10
0 0 1 1 0
1 0 1 1 0

We have four 1s at cells 001, 011, 101, 111. There are two ways to group them:

Option 1: where A does not affect the output.

A\BC 00 01 11 10
0 0 1 1 0
1 0 1 1 0

Group 1 (vertical): (NOT B) AND C Group 2 (vertical): B AND C

  • Group of two (vertical): cells 001 & 101 → term: (NOT B) AND C.
  • Group of two (vertical): cells 011 & 111 → term: B AND C.

Intermediate expression: F = ((NOT B) AND C) OR (B AND C)

Option 2: where B does not affect the output.

A\BC 00 01 11 10
0 0 1 1 0
1 0 1 1 0

Row A=0 group ⇒ (NOT A) AND C Row A=1 group ⇒ A AND C

  • Group of two (horizontal wrap): cells 011 & 001 → term: (NOT A) AND C.
  • Group of two (horizontal wrap): cells 111 & 101 → term: A AND C.

Intermediate expression: F = (NOT A AND C) OR (A AND C)

Both options simplify further (by factoring) to the same minimal form:

Final simplified expression: F = C

Challenge: verify by truth table that all forms are equivalent.

 Key Takeaways

  • A truth table lists all possible input combinations and their corresponding outputs for a given Boolean expression or logic circuit.
  • Truth tables are essential tools for predicting behaviour, verifying logic, and matching Boolean expressions to logic gates.
  • Logic gates like AND, OR, NOT, XOR, NAND, NOR, and XNOR can be analysed using structured truth tables.
  • Boolean algebra enables the simplification of logic expressions using identities such as Identity, Null, Inverse, Absorption, and De Morgan’s Laws.
  • Karnaugh Maps (K-Maps) provide a visual method of simplifying Boolean expressions by grouping adjacent 1s to minimise gate usage.
  • Simplified logic reduces hardware complexity, power consumption, and improves performance in digital circuits.