A sign at the ticket booth#
A sign at a ticket booth says:
“If you are a student, you get in free.”
You walk up. Four things can happen, and only one of them makes the booth a liar.
You are a student and they let you in free — promise kept. You are a student and they charge you — promise broken. You are not a student and they charge you — fine, the sign said nothing about you. You are not a student and they let you in free anyway — generous, a little odd, but still not a lie: the sign only ever made a promise about students.
So the sign is false in exactly one situation out of four. That is not a quirk of ticket booths. It is the definition of the conditional — the “if… then…” connective — and it is question 1 on most first tests.
The symbols, and what to call them#
Six symbols carry all of propositional logic. Each one has a name you are expected to say out loud in an exam answer, so the name is in the table too.
| Symbol | Name | Say it as | True exactly when… |
|---|---|---|---|
| ¬p | negation | “not p” | p is false |
| p ∧ q | conjunction | “p and q” | both are true |
| p ∨ q | disjunction | “p or q” | at least one is true |
| p ⊕ q | exclusive or | “p xor q” | exactly one is true |
| p → q | conditional | “if p then q” | it is not the case that p is true and q is false |
| p ↔ q | biconditional | “p if and only if q” | both have the same value |
Two more words you will need. A proposition is a sentence that is definitely true or definitely false — “7 is prime” is one, “x² ≥ 0” is not, because until somebody says what x is there is nothing to judge. The moment you pin x down — “if x is a real number, then x² ≥ 0” — it becomes a proposition.
In the conditional p → q, the left part p has a name: the antecedent (or hypothesis). The right part q is the consequent (or conclusion). Examiners use those words without warning.
A truth table is a list of every situation#
Here 1 means true and 0 means false. That is the same shorthand your notes use, and it makes long tables far easier to scan.
A truth table has one row for every combination of values the letters could take. Two letters means 2 × 2 = 4 rows. Three letters means 8. Four means 16. In general n letters gives 2n rows, and leaving one out invalidates the whole thing — the row you skipped is exactly where a counterexample would hide.
Here are all four basic connectives at once:
| p | q | ¬p | p ∧ q | p ∨ q | p ⊕ q | p → q | p ↔ q |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 |
Every column in that table is worth memorising, but only one of them regularly surprises people. It is the → column, and it is next.
The conditional, row by row#
Read the → column downwards: 1, 0, 1, 1. Three trues and a single false.
The single false sits in the row where p is 1 and q is 0 — you were a student and they charged you. That gives the cleanest possible definition, and it is the one to write in an exam:
p → q is false in exactly one case: when p is true and q is false. In every other case it is true. Equivalently, p → q ≡ ¬p ∨ q — “either p fails, or q holds.”
The two bottom rows are the ones that feel wrong. When p is false, p → q comes out true no matter what q does. Logicians call this vacuous truth: the promise was never tested, so it was never broken. “If the moon is made of cheese, I am the King of Spain” is a true statement. Nobody is claiming anything about the King of Spain. The moon simply is not made of cheese, so the promise never came due.
This is not a technicality to be tolerated — it is what makes the rest of mathematics work. “For every integer n, if n > 100 then n > 5” had better be true, and the only way it can be true for n = 3 is if a false left side gives a true conditional.
The biconditional: two promises facing each other#
p ↔ q is read “p if and only if q”, often shortened to “p iff q”. Its column is 1, 0, 0, 1: true when the two sides agree, false when they differ. A statement of this shape is sometimes called a characterization, because it says the two conditions pick out exactly the same things.
“Find the formula for p ↔ q” is asking you to write it using simpler connectives. There are two standard answers, and both are worth knowing:
p ↔ q ≡ (p → q) ∧ (q → p)
p ↔ q ≡ (p ∧ q) ∨ (¬p ∧ ¬q)
The first says: the promise runs both ways. The second says: either both are true, or both are false. Build the columns and you will find each one matches 1, 0, 0, 1 exactly.
The first formula is the one that matters for proofs, because it tells you a biconditional is two jobs, not one. Each direction has a name that examiners use:
| Direction | What it is called | What it says |
|---|---|---|
| p → q | the direct part — q is necessary for p | you cannot have p without q |
| q → p | the converse part — q is sufficient for p | q on its own is enough to force p |
Proving only one direction and stopping is the most common way to lose half the marks on an “if and only if” question.
Exclusive or — the one people miss#
Everyday English is sloppy about “or”. “Soup or salad” on a menu means one of them. “Bring a coat or an umbrella” means at least one, both is fine. Logic keeps them apart:
- p ∨ q (inclusive or) is true when at least one holds — including both. This is the default “or” in mathematics.
- p ⊕ q (exclusive or, xor) is true when exactly one holds, and false when both do.
The two columns differ in one row only — the top one, where p and q are both 1. Whenever a question hinges on “but not both”, it is asking for ⊕.
Tautology, contradiction, and everything in between#
Build a truth table for any compound statement and look at its final column. Exactly three things can happen, and each has a name you may be asked to define outright:
| Final column | Name | Meaning |
|---|---|---|
| all 1s | tautology | true under every possible assignment — true by its shape alone |
| all 0s | contradiction | false under every possible assignment |
| a mix | contingency | depends on the values — the ordinary case |
A tautology is a compound proposition that is true for every possible assignment of truth values to its component propositions — that is, its truth-table column is all 1s. p ∨ ¬p is the standard example: whatever p is, one of the two halves holds.
This is also the machinery behind the word equivalent. Saying P ≡ Q is the same as saying P ↔ Q is a tautology. That is why a truth-table proof of an equivalence ends by pointing at a column of all 1s — you are not checking that the two sides usually agree, you are showing the biconditional between them can never fail.
A contradiction is the mirror image, and it is what a proof by contradiction is hunting for: derive a statement whose column is all 0s and the assumption that produced it cannot stand.
Answering “define it, and state when it is true”#
Short definition questions are marked on precision, not length. Three sentences, in this order, will collect the marks:
- Name the inputs. “Let p and q be propositions.”
- Say what the new object is. “The conditional p → q is the proposition read ‘if p, then q’.”
- Give the truth condition exactly. “It is false when p is true and q is false, and true in all three other cases.”
Adding the four-row table underneath costs you thirty seconds and removes any doubt about what you meant. If the question says “state when it is considered true”, the table is the answer — write it.
Where these go wrong#
- Calling p → q false when p is false. It is true — vacuously. This single mistake wrecks more induction proofs than any other, because the base case often relies on it.
- Reading “or” as exclusive. In mathematics ∨ includes both. If a question means “but not both” it will say so, or use ⊕.
- Proving one direction of an “if and only if”. Two directions, two proofs, both written out.
- Skipping rows. Three letters means eight rows. Seven rows is not a proof; it is seven pieces of evidence.
- Saying “tautology” when you mean “true”. A tautology is true by its shape, whatever the letters stand for. “2 + 2 = 4” is true but is not a tautology.
- Mixing up necessary and sufficient. In p → q, q is necessary for p and p is sufficient for q. Read it as “p is enough; q is required”.
A truth table is a list of every situation. → fails in one row only. ↔ is two promises. A tautology is a column of all 1s.
Test yourself in the free Kestrel Exams app
Discrete Math practice is free and works offline — topic-selectable drills on connectives, truth tables, and tautologies.
Drill propositional logic →Frequently asked questions#
Why is p → q true when p is false?
Because a conditional is a promise about what happens when p holds. If p never holds, the promise was never tested, so it was never broken. This is called vacuous truth. It is what lets a statement like “for every n, if n > 100 then n > 5” be true for n = 3.
What is a tautology?
A compound proposition that is true for every possible assignment of truth values to its parts — its truth-table column is all 1s. p ∨ ¬p is the standard example. Saying two statements are equivalent is the same as saying the biconditional between them is a tautology.
What is the formula for p ↔ q?
Two standard forms: (p → q) ∧ (q → p), which says the promise runs both ways, and (p ∧ q) ∨ (¬p ∧ ¬q), which says both are true or both are false. Both have the column 1, 0, 0, 1.
What is the difference between ∨ and ⊕?
∨ (inclusive or) is true when at least one side holds, including both. ⊕ (exclusive or) is true when exactly one side holds and false when both do. They differ in one row only — the row where p and q are both true.
How many rows does a truth table need?
Two to the power of the number of distinct letters: 2 letters give 4 rows, 3 give 8, 4 give 16. A missing row invalidates the argument, because that is exactly where a counterexample could be hiding.
Something here not clear? A topic you wish we covered? Tell us. We read every message, and a request is the fastest way to get a guide written — several of these exist because somebody asked.