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. And if you are not a student and they wave you through anyway? Generous. Still not a lie. The sign only ever promised something 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 we will need. A proposition is a sentence that is definitely true or definitely false. “7 is prime” is one. “x² ≥ 0” is not — until somebody says what x is, there is nothing to judge. Pin x down and it becomes one: “if x is a real number, then x² ≥ 0”.
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. Leave one out and the proof is void. That skipped row is exactly where a counterexample hides.
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 |
Memorize every column. But only one of them regularly starts arguments, and that is the → column.
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. Write the definition that way 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.”
Now the two bottom rows, where p is 0. Both come out true, whatever q does. That is the part people argue with, so let’s argue with it.
Say you tell your roommate:
“If it snows in July, I’ll buy lunch for everyone.”
July comes. No snow. You buy nobody lunch. Did you lie? Decide before you read on.
Most people say yes, or at least “kind of”. It feels like you got away with something.
You did not lie. You promised one thing about one situation: snow in July. To catch you breaking it, somebody has to point at a July snowfall and an empty lunch table. July had no snow. The situation that could have caught you never happened, so the promise was never broken — and an unbroken promise is a true one.
Logicians call this vacuous truth. True because it was never tested.
That rule is doing real work, not dodging. Take “for every integer n, if n > 100 then n > 5”. We need that statement to be true, and that includes when n = 3. It only covers n = 3 if a false left side gives a true conditional. Break the bottom two rows and most of mathematics goes with them.
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” means: write it using simpler connectives. Two standard answers, both fair game:
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 each one matches 1, 0, 0, 1 exactly.
For proofs, use the first. It tells you a biconditional is two jobs, not one, and each direction has a name 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.
The same machinery sits behind the word equivalent. Saying P ≡ Q is saying P ↔ Q is a tautology. So a truth-table proof of an equivalence ends by pointing at a column of all 1s. We are not showing the two sides usually agree. We are showing the biconditional between them can never fail.
A contradiction is the mirror image, and it is what a proof by contradiction hunts 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.”
Add the four-row table underneath. It costs thirty seconds and removes all doubt about what you meant. If the question says “state when it is considered true”, the table is the answer, so 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.