1. What a proposition is
A proposition is a sentence that makes a claim — one that's either true or false, with nothing in between. "Paris is in France" is a proposition. "What time is it?" is not — questions don't have truth values. Neither does "Close the door" — commands don't either. The word linguists use for sentences-that-make-claims is declarative, which is why some textbooks define a proposition as a declarative sentence with a truth value.
The two possible verdicts are just T (true) and F (false). In more formal writing you'll also see the symbols $\top$ for true and $\bot$ for false — same idea, fancier notation. We'll mostly stick with T and F here.
Three things qualify a sentence as a proposition: it makes a claim, the claim is unambiguous enough to evaluate, and exactly one of "true" or "false" applies to it. Questions, commands, and sentences with unfilled blanks don't qualify.
A declarative sentence that is either true or false — but never both, and never neither. The two truth values are written T and F (or, formally, $\top$ and $\bot$).
Yes / no examples
- $2 + 2 = 4$ (true)
- $7$ is prime (true)
- $\pi$ is rational (false)
- It is raining in Paris right now (true or false — still a proposition)
- "Is it raining?" — a question
- "Please close the door." — a command
- $x + 1 = 2$ — depends on $x$ (an open sentence)
- "This statement is false." — a paradox; no consistent value
Atomic vs. compound
An atomic proposition is one we treat as indivisible — typically written as a capital letter $P, Q, R, \ldots$ — and whose internal grammar we ignore. A compound proposition is built from atomics by gluing them with logical connectives. If $P$ stands for "it is raining" and $Q$ for "it is windy," then $P \wedge \neg Q$ is the compound proposition "it is raining and it is not windy."
Not because the sentence is short, but because propositional logic chooses not to look inside. "Every prime greater than 2 is odd" is a single atom in propositional logic — the inner quantification only becomes visible when you move up to predicate logic.
2. The five connectives
Each connective is fully specified by what it does to truth values — nothing else. We'll spell each out below.
Flips the truth value. True becomes false, false becomes true.
True only when both $P$ and $Q$ are true.
True when at least one of $P, Q$ is true. Inclusive — both is allowed.
False only when $P$ is true and $Q$ is false. True everywhere else, including when $P$ is false.
True exactly when $P$ and $Q$ have the same truth value.
For implication, the antecedent (the "if" part) is $P$ and the consequent (the "then" part) is $Q$. Order matters: $P \to Q$ and $Q \to P$ are very different statements — more on this below.
Precedence
When parentheses are missing, the convention is that $\neg$ binds tightest, then $\wedge$, then $\vee$, then $\to$, then $\leftrightarrow$. So $P \wedge Q \to \neg R$ parses as $(P \wedge Q) \to (\neg R)$. When in doubt, parenthesise — the cost is one extra symbol; the cost of being wrong is the entire argument.
3. Truth tables
A truth table is a row-by-row enumeration of every possible truth assignment to a formula's atoms, with the resulting truth value computed at each row. A formula with $n$ distinct atoms has $2^n$ rows — one for each way the atoms could combine.
Here are the five connectives in one consolidated table. Each output column is the connective's complete definition.
| $P$ | $Q$ | $\neg P$ | $P \wedge Q$ | $P \vee Q$ | $P \to Q$ | $P \leftrightarrow 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 |
Read it column by column. AND is the strictest — it asks for both. OR is the most permissive — it asks for at least one. The biconditional is the "match" detector — same value, true; different, false. And implication is the one that takes some getting used to.
For any compound formula, walk the columns: list the atoms, then add a column for each subformula (innermost first), and finally a column for the whole expression. Every question you can ask about the formula — is it always true? is it equivalent to that other one? — comes down to comparing those final columns.
A worked truth table
Evaluate $P \to (Q \vee \neg P)$ at every assignment. The auxiliary columns make the computation mechanical:
| $P$ | $Q$ | $\neg P$ | $Q \vee \neg P$ | $P \to (Q \vee \neg P)$ |
|---|---|---|---|---|
| T | T | F | T | T |
| T | F | F | F | F |
| F | T | T | T | T |
| F | F | T | T | T |
Final column: T, F, T, T. The formula is true in three rows and false in one — neither always true nor always false. We'll classify that kind of formula in section 5.
4. Implication and vacuous truth
The implication row that surprises people is the one with a false antecedent. Look at the truth table again: $P \to Q$ is true whenever $P$ is false, regardless of $Q$. The bottom two rows of the implication column are both T.
An implication fails in exactly one situation — when the antecedent is true and the consequent is false. Every other situation, it succeeds by default.
The conventional name for this default success is vacuous truth. The implication "If pigs fly, then $1 = 0$" is true — not because anyone has worked out the consequences of flying pigs, but because pigs don't fly, so the conditional has no case to fail in. Likewise "If $5 < 3$, then $7 = 8$" is true: the antecedent is false, so the whole conditional is vacuously true.
Because of theorems like "for every integer $n$, if $n$ is a prime greater than $2$, then $n$ is odd." We want this to be true at every $n$, including $n = 4$ and $n = 6$ where the antecedent fails. The vacuous-truth convention makes it so. The alternative — declaring conditionals "undefined" or "false" when the antecedent fails — would force us to guard every universal statement with extra clauses, cluttering all of mathematics for no gain.
The four related forms
Given any implication $P \to Q$, three close cousins always come up:
| Name | Form | Equivalent to the original? |
|---|---|---|
| Converse | $Q \to P$ | No |
| Inverse | $\neg P \to \neg Q$ | No (but equivalent to the converse) |
| Contrapositive | $\neg Q \to \neg P$ | Yes |
The contrapositive is the one you can swap in freely. The converse and inverse aren't equivalent to the original — confusing them is a famous mistake, dealt with in section 8.
One concrete example: take "if it is raining, the ground is wet." Its contrapositive — "if the ground is not wet, it is not raining" — is also true, and means the same thing. Its converse — "if the ground is wet, it is raining" — is false in general; the ground could be wet because of a sprinkler. The fact that converse and original are different is precisely what lets the contrapositive carry real information.
5. Tautology, contradiction, contingency
A propositional formula's truth table sorts it into exactly one of three classes:
- $P \vee \neg P$ (law of excluded middle)
- $P \to P$ (identity)
- $(P \wedge Q) \to P$ (simplification)
- $P \wedge \neg P$
- $(P \to Q) \wedge P \wedge \neg Q$
- $\neg(P \vee \neg P)$
Everything else is a contingency — sometimes true, sometimes false, depending on the assignment. Most formulas you'll meet in practice are contingencies. $P \to Q$ is the canonical example: true in three rows, false in one. The two extremes — formulas whose truth doesn't depend on their inputs at all — are the interesting structural objects, because they're the laws of logic itself.
Every tautology is a fact about the connectives alone, independent of what the atoms refer to. When mathematicians write a "logical law" they're usually pointing at a tautology — e.g. modus ponens written as the tautology $[(P \to Q) \wedge P] \to Q$.
6. Logical equivalence
Two formulas $\varphi$ and $\psi$ are logically equivalent — written $\varphi \equiv \psi$ — when their truth tables match row for row. Equivalently: $\varphi \leftrightarrow \psi$ is a tautology. Equivalent formulas can be swapped for each other anywhere without changing the meaning.
A small set of equivalences gets used over and over, and is worth memorising. They are the algebra of propositional logic.
| Name | Equivalence |
|---|---|
| Double negation | $\neg\neg P \equiv P$ |
| De Morgan (AND) | $\neg(P \wedge Q) \equiv \neg P \vee \neg Q$ |
| De Morgan (OR) | $\neg(P \vee Q) \equiv \neg P \wedge \neg Q$ |
| Material conditional | $P \to Q \equiv \neg P \vee Q$ |
| Contrapositive | $P \to Q \equiv \neg Q \to \neg P$ |
| Negation of conditional | $\neg(P \to Q) \equiv P \wedge \neg Q$ |
| Biconditional expansion | $P \leftrightarrow Q \equiv (P \to Q) \wedge (Q \to P)$ |
| Distributivity (both ways) | $P \wedge (Q \vee R) \equiv (P \wedge Q) \vee (P \wedge R)$ |
| Absorption | $P \vee (P \wedge Q) \equiv P$ |
De Morgan's laws deserve a second look: they tell you how negation distributes over a conjunction or disjunction. The connective flips. To deny "rain and wind" is to assert "no rain, or no wind." To deny "rain or wind" is to assert "no rain, and no wind." Try a row of the truth table if it feels suspicious — at $P = T, Q = F$, $\neg(P \wedge Q) = \neg F = T$, and $\neg P \vee \neg Q = F \vee T = T$. They agree.
The material conditional rewrite is the secret behind why vacuous truth works: $P \to Q$ is $\neg P \vee Q$. Either the antecedent fails (left disjunct), or the consequent holds (right disjunct) — and that's it. The four rows of the implication table are nothing but $\vee$ applied to $\neg P$ and $Q$.
Why equivalences earn their keep
Once you know the list, simplification becomes algebra. To negate "if $P$ then $Q$," for example, you don't need to think — you just compute:
$$ \neg(P \to Q) \;\equiv\; \neg(\neg P \vee Q) \;\equiv\; \neg\neg P \wedge \neg Q \;\equiv\; P \wedge \neg Q. $$The negation of "if $P$ then $Q$" is "$P$ and not $Q$" — exactly the single row where the implication fails.
7. Normal forms (CNF and DNF)
Every propositional formula, no matter how tangled, is equivalent to a formula in one of two highly structured "normal" shapes. They're useful because algorithms — including the SAT solvers that drive modern verification — prefer a fixed shape over the wild variety of arbitrary formulas.
| Form | Shape | Example |
|---|---|---|
| Disjunctive normal form (DNF) | OR of ANDs of literals | $(P \wedge Q) \vee (\neg P \wedge R)$ |
| Conjunctive normal form (CNF) | AND of ORs of literals | $(P \vee \neg Q) \wedge (\neg P \vee R)$ |
A literal here means an atomic proposition or its negation — $P$ or $\neg P$, but not $P \wedge Q$. The DNF of a formula corresponds row-by-row to the true rows of its truth table; CNF corresponds to the false rows. Both forms can be built mechanically from the table.
CNF is the input language for SAT solvers — the algorithms that decide whether a propositional formula can be made true and that underpin a lot of modern hardware and software verification. DNF makes it especially easy to read off "what would have to be true for this formula to hold." Either way, knowing that a normal form always exists is the deeper point: every propositional formula has a canonical written shape.