Propositional Logic — Mathematics Knowledge System

Overview

Propositional logic (also called statement logic, sentential calculus, or propositional calculus) is a branch of classical logic that studies propositions — statements that are either true or false — and the ways they combine into compound statements. Compound propositions are built from simpler ones using logical connectives: negation (not), conjunction (and), disjunction (or), implication (if...then), and biconditional (if and only if). Propositional logic is 'zeroth-order' in the sense that it treats propositions as indivisible units, without looking inside them at objects, predicates, or quantifiers — that refinement is the job of predicate logic.

Intuition

Think of each simple proposition as a light switch that is either on (true) or off (false), with no in-between. Connectives are like circuits wiring switches together: AND is two switches in series (both must be on for current to flow), OR is two switches in parallel (either being on suffices), and NOT flips a switch. Once you have wired a compound circuit, its truth value is completely determined by the truth values of the switches feeding it — that's exactly what a truth table computes, row by row, for every possible on/off combination.

Formal Definition

Definition

A propositional language starts with a set of atomic propositions p, q, r, ... and closes them under the connectives ¬ (negation), ∧ (conjunction), ∨ (disjunction), → (implication), and ↔ (biconditional). Each connective is defined by its truth function: it maps the truth values of its inputs to a truth value for the output, independent of what the propositions actually mean.

p \land q \text{ is true} \iff p \text{ is true and } q \text{ is true}

Conjunction

p \lor q \text{ is true} \iff p \text{ is true or } q \text{ is true (or both)}

Disjunction

p \to q \iff \lnot p \lor q

Implication (material conditional)

p \leftrightarrow q \iff (p \to q) \land (q \to p)

Biconditional

Notation

Notation	Meaning
$\lnot p$	Negation — 'not p'Also written: ~p, !p
$p \land q$	Conjunction — 'p and q'Also written: p·q, p && q
$p \lor q$	Disjunction — 'p or q' (inclusive)Also written: p \|\| q
$p \to q$	Material conditional — 'if p then q'Also written: p ⊃ q
$p \leftrightarrow q$	Biconditional — 'p if and only if q'Also written: p ≡ q
$\vDash$	Semantic entailment — the conclusion is true whenever the premises are

Properties

Commutativity

p \land q \iff q \land p, \quad p \lor q \iff q \lor p

Associativity

(p \land q) \land r \iff p \land (q \land r)

De Morgan's laws

\lnot(p \land q) \iff \lnot p \lor \lnot q, \quad \lnot(p \lor q) \iff \lnot p \land \lnot q

Double negation

\lnot \lnot p \iff p

Contrapositive equivalence

p \to q \iff \lnot q \to \lnot p

Applications

Boolean logic gates (AND, OR, NOT) in digital circuit design directly implement propositional connectives; CPU logic is built from these primitives.

Worked Examples

The conditional is false only when the antecedent is true and the consequent is false; it is true in every other case.
$\begin{array}{cc|c} p & q & p\to q \\ \hline T&T&T \\ T&F&F \\ F&T&T \\ F&F&T \end{array}$

Answer: p → q is false only for (T, F); true for (T,T), (F,T), (F,F).

Practice Problems

Difficulty 2/10

Write the truth table for p ∨ q.

Difficulty 4/10

Which formula is logically equivalent to p → q?

p ∧ ¬q¬p ∨ q¬p ∧ qq → p

Difficulty 5/10

A pump should run only when the tank is NOT full AND (the manual switch is on OR the auto-timer fires). Write the control condition as a Boolean expression and name the gates involved.

Difficulty 5/10

A guard clause rejects input unless 'age ≥ 18 AND has_license'. Using De Morgan's law, rewrite the rejection condition ¬(A ∧ B).

Common Mistakes

Common Mistake

Believing p → q is false whenever p is false.

The material conditional is TRUE whenever the antecedent p is false, regardless of q ('vacuously true'). Only T→F is false.

Common Mistake

Treating → as equivalent to ↔.

p → q only requires q whenever p holds; it says nothing about what happens when p is false. p ↔ q additionally requires q → p.

Quiz

Summary

Propositional logic studies true/false statements (propositions) combined via connectives: ¬, ∧, ∨, →, ↔.
Each connective is a truth function — a compound's truth value depends only on the truth values of its parts.
Truth tables enumerate every input combination to determine a formula's truth value in each case.
De Morgan's laws let you push negation through ∧ and ∨, swapping one for the other.
Propositional logic is the foundation for predicate logic, proof techniques, and digital circuit design.

References

WebsiteWikipedia — Propositional logic
BookEnderton, H. A Mathematical Introduction to Logic, 2nd ed.