Grades 9–12FoundationsPlanned

Propositional logic and truth tables

Truth tables, implication with its converse and contrapositive, logical equivalence and tautologies: the logic of 'and', 'or', 'not' and 'if…then' made exact.

math.found.propositional-logic

Show everything needed to reach this topic

The lesson for this topic has not been written yet. The outline below is part of the curriculum map and has not been reviewed.

Builds on

True, false, and, or, not Set-builder notation, quantifiers and infinite sets

Required prerequisites, all the way down: 4

You will learn to

Build truth tables for compound statements and use them to test logical equivalence.
Distinguish an implication from its converse, inverse and contrapositive.
Negate compound and quantified statements, including implications.

Definition

P → Q is false only when P is true and Q is false.
Two formulas are logically equivalent if they have the same truth value under every assignment of truth values to their variables.
A tautology is a formula that is true under every assignment.

Theorem

P → Q is logically equivalent to its contrapositive ¬Q → ¬P, but not to its converse Q → P.
De Morgan's laws: ¬(P ∧ Q) ≡ ¬P ∨ ¬Q and ¬(P ∨ Q) ≡ ¬P ∧ ¬Q.
¬(P → Q) ≡ P ∧ ¬Q.

Common misconceptions

Thinking an implication with a false hypothesis is false; it is true.
Treating the converse of an implication as equivalent to it.
Reading 'if P then Q' as claiming that P causes Q.

Leads to

Proof: direct, contrapositive, contradiction and induction First steps in Lean First-order logic

Optional discoveries

Computational complexity Deciding whether a propositional formula is satisfiable (SAT) was the first problem proved NP-complete (Cook–Levin theorem).
Type theory and propositions as types In constructive logic and type theory, a proof of P → Q is a method turning proofs of P into proofs of Q, and P ∨ ¬P is not assumed as a law.