Skip to content
Tutorials Center
My learning

Topics

Lesson 5 of 37 ยท Propositional Logic

Connectives and Truth Tables

Master truth tables for negation, conjunction, disjunction, implication and the biconditional, generate them with Python, and learn why implication is false only once.

A truth table lists every possible combination of truth values for a formula's variables and shows the formula's value in each case. Because the truth value of a compound statement depends only on its parts, a truth table completely defines a connective. In this lesson you will learn the standard tables, understand the odd-looking implication, and write a program that prints a table for any formula.

The five standard tables

Using T for true and F for false:

p q ยฌp p โˆง q p โˆจ q p โ†’ q p โ†” q
T T F T T T T
T F F F T F F
F T T F T T F
F F T F F T T

Reading guide:

  • ยฌp flips the value.
  • p โˆง q is true only when both are true.
  • p โˆจ q is false only when both are false (inclusive or).
  • p โ†’ q is false only for the row p true, q false.
  • p โ†” q is true when the two agree.

Why is "false implies anything" true?

New learners find the last two rows of p โ†’ q suspicious. Think of p โ†’ q as a promise: "if you pass the exam (p), I will buy you lunch (q)". When do I break the promise? Only if you pass and I do not buy lunch. If you fail, the promise says nothing, so I cannot be accused of breaking it whatever I do. Logic therefore calls the implication true when the hypothesis is false. This is called vacuous truth, and it is not a trick: it is the only choice that makes laws such as "p โ†’ q is equivalent to ยฌp โˆจ q" and "โˆ€x (P(x) โ†’ Q(x)) holds when nothing satisfies P" work.

Implication as a promise

Pass, lunch bought Promise kept: true
Pass, no lunch Promise broken: false
Fail, lunch bought Not broken: true
Fail, no lunch Not broken: true

False only when the promise is broken

1 / 2

Generating truth tables with code

The function below builds the rows for any formula given as a Python function of keyword arguments, and prints them as T/F. Since n variables need 2**n rows, it is only for small n.

Python A truth table printer

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The second formula comes out true on every row, which makes it a tautology: if both hold, then certainly at least one holds.

Building tables column by column

By hand, you build a table for a compound formula by adding a column for each sub-formula, working from the inside out. For (p โ†’ q) โˆง (q โ†’ p):

p q p โ†’ q q โ†’ p (p โ†’ q) โˆง (q โ†’ p)
T T T T T
T F F T F
F T T F F
F F T T T

The final column equals the table of p โ†” q. That is no accident: "if and only if" literally means "implies in both directions".

Derived connectives and functional completeness

There are 16 possible two-input truth tables. Beyond the five above, important ones include XOR (p โŠ• q, differ), NAND (ยฌ(p โˆง q)) and NOR (ยฌ(p โˆจ q)). A set of connectives is functionally complete if it can express every truth table. {ยฌ, โˆง} is complete, {ยฌ, โˆจ} is complete, and remarkably NAND alone is complete. This is why digital hardware can be built from a single gate type.

Python NAND can build everything

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Counting truth tables

With 2 variables there are 4 rows, and each row's output is T or F independently, so there are 2**4 = 16 distinct two-variable connectives. With n variables there are 2**(2**n) possible Boolean functions: 256 for three variables, 65,536 for four. This is also why exhaustively searching for a circuit quickly becomes infeasible.

Common mistakes

  • Writing T/F rows in a different order each time. Fix a convention (all T first) and keep it.
  • Forgetting that p โˆจ q is true when both are true.
  • Believing p โ†’ q and q โ†’ p mean the same thing. They are different; the second is the converse.
  • Confusing p โ†’ q with p โ†” q. The first is one direction only.

Starting from p โ†’ q you can form three relatives:

Name Formula Equivalent to the original?
Converse q โ†’ p No
Inverse ยฌp โ†’ ยฌq No
Contrapositive ยฌq โ†’ ยฌp Yes

The contrapositive equivalence is one of the most useful facts in proofs (see contrapositive and contradiction). A four-row table confirms it, as the next lesson does.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In how many rows of its truth table is p โ†’ q false?

    Only the row with p true and q false makes the implication false.
  2. 2. How many rows does the truth table of a formula with 5 variables have?

    2^5 = 32 rows.
  3. 3. Which pair of statements is equivalent?

    An implication and its contrapositive have identical truth tables.
  4. 4. Which single connective is functionally complete?

    NAND (and NOR) can express negation, conjunction and disjunction, so any truth table.

Summary

  • A truth table lists all assignments and defines a connective completely.
  • Implication is false only when the hypothesis is true and the conclusion false; otherwise it is vacuously true.
  • Build compound tables column by column, from the inside out.
  • NAND alone can express every Boolean function (functional completeness).
  • An implication equals its contrapositive but not its converse or inverse.

Next: Tautologies, Contradictions and Equivalences