Truth Table

Introduction

A truth table is a mathematical table used in logic—particularly in Boolean algebra, digital electronics, and computer science—to systematically represent the output of a logical function or expression for all possible combinations of its input values. It is one of the most fundamental tools for analyzing and designing logical systems, ranging from simple gates to complex combinational and sequential circuits.

Truth tables are used to:

Evaluate logical propositions
Simplify Boolean expressions
Design digital circuits
Analyze logic in software
Validate logical equivalences

Structure of a Truth Table

A truth table lists:

All possible combinations of input variables.
The corresponding output value for each combination.

For n Boolean variables, there are 2ⁿ possible input combinations.

Example: 2-input AND operation

A	B	A AND B
0	0	0
0	1	0
1	0	0
1	1	1

The table shows that the output is 1 only when both A and B are 1.

Basic Logic Gates and Their Truth Tables

1. AND (`⋅` or `∧`)

A	B	A AND B
0	0	0
0	1	0
1	0	0
1	1	1

2. OR (`+` or `∨`)

A	B	A OR B
0	0	0
0	1	1
1	0	1
1	1	1

3. NOT (`¬` or `'`)

A	NOT A
0	1
1	0

4. NAND

A	B	A NAND B
0	0	1
0	1	1
1	0	1
1	1	0

5. NOR

A	B	A NOR B
0	0	1
0	1	0
1	0	0
1	1	0

6. XOR (Exclusive OR)

A	B	A XOR B
0	0	0
0	1	1
1	0	1
1	1	0

7. XNOR (Equivalence)

A	B	A XNOR B
0	0	1
0	1	0
1	0	0
1	1	1

Truth Tables for Complex Expressions

For compound Boolean expressions, construct the table step by step.

Example:

Expression: (A ∧ ¬B) ∨ C

A	B	C	¬B	A ∧ ¬B	Output
0	0	0	1	0	0
0	0	1	1	0	1
0	1	0	0	0	0
0	1	1	0	0	1
1	0	0	1	1	1
1	0	1	1	1	1
1	1	0	0	0	0
1	1	1	0	0	1

Applications of Truth Tables

1. Digital Logic Design

Foundation for creating circuits using gates.
Used to design combinational logic like multiplexers, decoders, adders.

2. Boolean Algebra Simplification

Verify logical equivalence.
Assist in using Karnaugh maps (K-maps) for minimization.

3. Software Testing and Assertions

Test all combinations of conditions in logic-heavy code.
Useful in unit testing and decision coverage.

4. Propositional Logic and AI

Represent knowledge and rules in expert systems or logic solvers.

5. Mathematical Logic

Evaluate truth values of propositions, tautologies, and contradictions.

Special Concepts in Truth Tables

Tautology

An expression that is always true, regardless of input values.

Example:

A ∨ ¬A

A	¬A	A ∨ ¬A
0	1	1
1	0	1

Contradiction

An expression that is always false.

Example:

A ∧ ¬A

A	¬A	A ∧ ¬A
0	1	0
1	0	0

Truth Tables in Programming

Python Example:

from itertools import product

def truth_table(n):
    return list(product([0, 1], repeat=n))

# 2-input example
for row in truth_table(2):
    A, B = row
    output = A and B
    print(f"A={A}, B={B}, A AND B = {output}")

JavaScript Example:

const inputs = [0, 1];
for (let a of inputs) {
  for (let b of inputs) {
    const result = a ^ b;
    console.log(`A=${a}, B=${b}, A XOR B=${result}`);
  }
}

Limitations of Truth Tables

Scalability: For n variables, the table has 2ⁿ rows. Becomes impractical for large n (e.g., 10 variables = 1024 rows).
Storage: Full tables consume space in automated verification tools.
Combinatorial explosion: Makes truth tables less useful in large-scale logic synthesis; symbolic methods or decision diagrams may be better.

Tools That Use Truth Tables

Karnaugh Maps (K-maps): Use truth table rows to form maps for simplification.
SAT Solvers: Internally rely on truth assignments.
Digital Simulation Software: e.g., Logisim, Multisim
Automated Theorem Provers

Summary

Truth tables are a foundational tool in logic, computer science, and digital design. They offer a systematic method for representing all input-output mappings of Boolean expressions or logical circuits. Despite their exponential size for large inputs, they remain invaluable for validation, debugging, learning, and logic verification.

Whether designing a digital gate circuit or proving a propositional logic theorem, truth tables provide clarity and mathematical rigor.