Why bother with logic?

Every argument you have ever lost was really about logic. Someone said “if it rains, the match is off; it’s raining — so pack up” and it was airtight. You couldn’t wriggle out. Another time someone said “you didn’t text back, so clearly you hate me” and something felt off — but you couldn’t put your finger on what. This chapter is about putting your finger on it.

Logic is the toolkit for telling the airtight from the leaky. We’ll start so simple it feels like cheating, and build until you can take any tangled claim apart with your hands.

One thing before we begin, because it’s the real reason this feels different from school maths: there is almost no arithmetic here. Nothing to calculate. The whole skill is reading and writing precise statements — a different muscle from the one you used for sums, and the one that makes the rest of your degree click into place. So if it feels strange at first, that’s not you being slow. It’s a new muscle. We’ll warm it up gently.

What counts as a statement?

Before we can reason about statements, we have to agree on which sentences we’re even allowed to reason about. Logic is picky here, on purpose.

A proposition is a sentence that is definitely true or definitely false — one or the other, never both, never neither.

Where the word comes from: proposition is Latin for “something put forward” (pro = forward, ponere = to place). You’re putting a claim on the table for the world to judge true or false.

The quick test: could you bet money on it and settle the bet?

• “The Moon is made of cheese.” — false, but still a proposition. You can settle it.
• “4 is a prime number.” — false, a proposition.
• “It is raining in Bangalore right now.” — a proposition (true or false depending on the sky, but settleable).

And the sentences that don’t make the cut — nothing’s wrong with them, they’re just not bettable:

• “What time is it?” — a question. You can’t call it true or false.
• “Shut the door!” — a command. Same problem.
• “$x + 1 = 2$” — can’t settle it until someone tells you what $x$ is.

Writing whole sentences every time gets tiring, so we give propositions short names — single letters, usually $p$, $q$, $r$ (just say the letter out loud: “p”, “q”). From here on, $p$ might stand for “It is raining” and $q$ for “The home team wins.” The letter is just a nickname for a sentence that’s either true or false.

The four glue-words

One proposition on its own is a bit dull. The fun starts when you glue small ones together into bigger ones. There’s only a handful of glue-words, and you already know them from ordinary speech — we’re just going to make them exact. Meet the first four.

NOT — flipping a statement on its head

Symbol: $\neg$. Say it: “not”. Put it in front of a proposition and it flips the truth: true becomes false, false becomes true. If $p$ is “it is raining”, then $\neg p$ is “it is not raining.” That’s the whole story — toggle it and watch:

AND — the strict bouncer

Symbol: $\wedge$. Say it: “and”. $p \wedge q$ is true only when both $p$ and $q$ are true. Think of a bouncer who checks two things at the door — ID and dress code. Fail either one and you’re not getting in. (You’ve used this without knowing: a search for samosa AND recipe only returns pages that have both words.)

OR — the generous one

Symbol: $\vee$. Say it: “or”. $p \vee q$ is true when at least one side is true — and that quietly includes the case where both are true. This trips people up, because everyday “or” often means one or the other, not both (“tea or coffee?”). Logic’s plain “or” is the generous kind: both is fine too.

A memory hook from the names: conjunction means “joined together” — AND fuses two things into one strict demand. Disjunction means “pulled apart” — OR offers you separate options.

EXCLUSIVE OR — pick exactly one

Symbol: $\oplus$. Say it: “ex-or”, or “exclusive or”. $p \oplus q$ is true when exactly one side is true — one or the other, but not both. This is the everyday “tea or coffee?”: choose one, you can’t have both.

So keep the pair straight: $\vee$ is “at least one” (both allowed), $\oplus$ is “exactly one” (both forbidden). Same English word “or”, two different machines.

Implication — the one worth slowing down for

Now the glue-word that trips up almost everyone the first time. Take it slowly; once it clicks, it stays clicked.

Symbol: $\rightarrow$. Say it: “implies”, or just read $p \rightarrow q$ as “if $p$, then $q$.” The first part, $p$, is the hypothesis (the “if”). The second, $q$, is the conclusion (the “then”).

Here’s the trick that makes it make sense. Think of $p \rightarrow q$ (say it: p implies q, or if p then q) as a promise:

If you score 100%, then I’ll buy you pizza.

When have I broken my promise? There’s only one way: you scored 100% and I gave you no pizza. That’s the single case that makes me a liar.

Now the cases that feel wrong but aren’t. You did badly and I bought you pizza anyway? I’m generous, not a liar — promise unbroken. You did badly and I bought nothing? I only promised pizza if you got 100% — you didn’t, so I’m off the hook. The promise only breaks on the one case where the if happened but the then didn’t.

So $p \rightarrow q$ is false in exactly one situation — $p$ true, $q$ false — and true everywhere else. Toggle it and find that single false row for yourself:

That “true when the if never happens” idea has a name: vacuously true. “If pigs fly, I’m the Queen of England” is a true statement — pigs don’t fly, so I can never be caught out. Empty promise, technically kept.

One last thing, because the exam loves it: English has a dozen ways to say the very same $p \rightarrow q$. The plain ones — “if $p$, then $q$”, “$p$ implies $q$”, “$q$ if $p$”. And two sneaky ones worth memorising, because they sound backwards but aren’t:

• “$p$ only if $q$” means $p \rightarrow q$. (Not $q \rightarrow p$!)
• “$q$ is necessary for $p$” also means $p \rightarrow q$.

Read those twice. When they show up in a question, slow down and map them back to the arrow.

Three cousins of a promise

Take $p \rightarrow q$ and shuffle the two pieces around. You get three close relatives — and people mix them up constantly, including in exams. They each have a name that tells you what was done.

• Converse — $q \rightarrow p$. Say it: “converse” (Latin, “turned around”). You swapped the two sides.
• Inverse — $\neg p \rightarrow \neg q$. Say it: “inverse”. You negated both sides.
• Contrapositive — $\neg q \rightarrow \neg p$. Say it: “contra-positive”. You swapped and negated.

Now the part that’s genuinely useful — and this is checked maths, not my opinion (a machine confirmed every word of it):

• A statement and its contrapositive are always the same. “If it’s raining, the ground is wet” means exactly “if the ground isn’t wet, it isn’t raining.” Same promise, said backwards. (You’ll use this constantly when proving things: if a statement is awkward to prove head-on, prove its contrapositive instead — it’s the same fact.)
• A statement and its converse are not the same. “If it’s raining, the ground is wet” does not mean “if the ground is wet, it’s raining” — somebody could’ve spilled a bucket.
• The converse and the inverse happen to be the same as each other.

When the promise goes both ways

Sometimes a promise runs in both directions at once. That’s the biconditional.

Symbol: $\leftrightarrow$. Say it: “if and only if” — so often that we shorten it in writing to “iff” (say it: “iff”, and yes, that second “f” is deliberate — it’s short for “if and only if”). $p \leftrightarrow q$ is true when $p$ and $q$ have the same truth value: both true, or both false.

It’s really two implications bolted together. Saying “$p$ if and only if $q$” is exactly saying “$p$ if $q$” (that’s $q \rightarrow p$) and “$p$ only if $q$” (that’s $p \rightarrow q$) at the same time. A machine confirms the two are identical: $p \leftrightarrow q$ is the same statement as $(p \rightarrow q) \wedge (q \rightarrow p)$.

Everyday version: “You pass if and only if you score at least 40.” Score 40+, you pass; pass, and you must have scored 40+. The door swings both ways.

And a satisfying loose end tied off: remember exclusive-or, $\oplus$, true when the two sides differ? It’s the exact opposite of the biconditional. $p \oplus q$ is true in precisely the rows where $p \leftrightarrow q$ is false. $\leftrightarrow$ says “they match”; $\oplus$ says “they differ.” Two sides of one coin.

Building a truth table — the bread-and-butter exam skill

Here’s the move the exam asks for over and over: take a tangled compound statement and lay its whole behaviour out, row by row, until there’s nowhere left for it to hide. That layout is a truth table.

The idea: list every possible true/false combination of the variables, then work out the whole statement for each one. With $n$ variables you get $2^n$ rows — 2 variables make $4$ rows, 3 variables make $8$. (Why doubling? Each new variable can be true or false, so it doubles the number of cases.)

The method that never fails: make a column for each variable, then build up columns for the small pieces from the inside out — innermost brackets first — until the last column is the whole statement.

Now the exam’s single most-repeated truth table. They have asked for this exact one, $(p \vee \neg q) \rightarrow q$, again and again. Fill it in yourself — pick the truth value for each row, and it’ll tell you the moment you’re right:

Walk the first row with me so the rhythm is clear. Take $p$ false, $q$ false. Inside the bracket: $\neg q$ is true (since $q$ is false), so $p \vee \neg q$ is “false or true” = true. Now the whole thing is “true $\rightarrow$ false” — the if happened, the then didn’t — so the promise breaks: false. Then do the same for the other three rows. Inside the brackets first, arrow last.

Three kinds of statement

Once you can build a truth table, you can sort any statement into one of three boxes just by glancing at its final column.

Tautology — always true

The final column is all true. The statement holds no matter what. Say it: “taw-TOL-uh-jee”.

Where the word comes from: Greek tauto (“the same”) + logos (“saying”) — literally “saying the same thing twice.” A tautology tells you nothing new; it’s just always-true by its own shape.

Classic example: $p \vee \neg p$ — “it is raining or it is not raining.” One of those is always so. You cannot lose this bet.

Contradiction — always false

The final column is all false. The statement can never be true. Say it: “contradiction” (Latin, “to speak against” — the statement argues against itself).

Classic example: $p \wedge \neg p$ — “it is raining and it is not raining.” Impossible, every time.

Contingency — it depends

The final column is a mix of true and false. Its truth depends on the inputs. Say it: “con-TIN-jen-see”.

Where the word comes from: Latin contingere, “to touch upon, to depend on” — it’s contingent on the circumstances.

Most statements are contingencies — including the exam favourite you just built, $(p \vee \neg q) \rightarrow q$. Sometimes true, sometimes false.

One last idea to carry into the next chapter, because it’s a quiet powerhouse: two statements are logically the same (we’ll call them equivalent) when they have identical final columns. That’s precisely how we knew, earlier, that a statement equals its contrapositive — their columns match line for line. Next chapter turns this one observation into a whole toolkit.

One housekeeping rule: order of operations

Just like arithmetic has BODMAS to settle “what do I do first?”, logic has its own pecking order for when brackets don’t spell it out. Tightest-binding first:

$\neg$  >  $\wedge$  >  $\vee$  >  $\oplus$  >  $\rightarrow$  >  $\leftrightarrow$

So $\neg p \wedge q$ means $(\neg p) \wedge q$ — the “not” grabs only the $p$, not the whole thing. And $p \vee q \rightarrow r$ means $(p \vee q) \rightarrow r$, because the arrow is looser than the “or”.

Honest advice, worth more than the rule itself: when in doubt, add brackets. No examiner ever docked a mark for brackets that made your meaning clear, and they’ll save you from silly slips under time pressure. Clarity is free — spend it.

Make it yours

You started this chapter able to feel when an argument was leaky. Now you can point at exactly where. That’s the whole job of this first piece of logic — and every proof you write for the rest of the degree leans on it.

Going further: how computers actually think

Everything in this chapter is the seed of how a computer actually thinks. Those glue-words — NOT, AND, OR — aren’t just notation; they are real physical gates etched by the million into every chip in your phone and laptop. A truth table is, quite literally, a circuit’s blueprint: feed in true/false as voltage high/low, and the gates compute the final column for you.

You’ll meet all of this again with the hardware in front of you in Logic Design (CSD202A), and the quiet idea from the last section — two statements with the same truth table are interchangeable — grows up into Boolean algebra, the tool engineers use to shrink a clumsy circuit into a lean one. The puzzle you just learned to play by hand is the foundation of the machine you’re learning to build.

And this is your path in particular: as a Mathematics & Computing student you’ll push these same ideas much further — into the algebra of logic and, later, into how reasoning itself gets made rigorous. Today’s pizza promise is the first brick.

Same idea, in different clothes

Two people describe the same rule. One says “you can’t have it cheap and fast.” The other says “it’ll be expensive or slow.” Different words, same meaning — and you knew that instantly, without thinking.

That instinct is the whole of this chapter, made exact. Two statements can look completely different on the page yet be the same logical machine — true in exactly the same situations. Spotting when two things are secretly the same, and proving it, is one of the most useful moves in all of maths. It’s how you simplify a monster expression into a tidy one, and it’s worth a fat chunk of marks on every paper.

By the end you’ll be able to take a tangled statement and, line by line, reshape it into a clean one — the way you’d simplify $\tfrac{6}{8}$ to $\tfrac{3}{4}$, except for logic.

What “equivalent” actually means

Remember the last idea from Chapter 1: two statements are logically equivalent when they have identical final columns in their truth tables — they agree in every single case. That’s the whole definition. Nothing more mysterious than “they always match.”

We write it with a three-bar equals sign: $p \equiv q$. Say it: “p is equivalent to q” (or “p is logically equivalent to q”).

Where the word comes from: equivalent is Latin equi (equal) + valent (worth) — “of equal worth.” Two equivalent statements carry exactly the same truth, so either one will do.

Let’s see it with your hands. Here are two statements that look different: $\neg(p \wedge q)$ and $\neg p \vee \neg q$. Toggle the inputs on each — watch the two outputs move in perfect lockstep, every time:

Same output in all four cases. So $\neg(p \wedge q) \equiv \neg p \vee \neg q$. They are the same statement, just dressed differently — and you just met your first famous law (more on it in a moment).

Two ways to prove two things are equivalent

There are exactly two routes, and you need to know when you’re allowed to use each.

Route 1 — the truth table. Build the full table for both, and check the final columns match. It always works and it’s impossible to get logically wrong. The catch: with many variables it’s a slog ($2^n$ rows), and — crucially —

Route 2 — the laws of logic. Start from one side and, one tidy step at a time, reshape it into the other using a toolbox of known equivalences (the “laws”). Slicker, faster, and it shows you genuinely understand the structure rather than just grinding rows.

De Morgan’s laws — the star of the toolbox

You already met these two by toggling the tables above. They’re named after Augustus De Morgan, a 19th-century mathematician, and they tell you how a “not” spreads across an “and” or an “or”:

$\neg(p \wedge q) \equiv \neg p \vee \neg q$    and    $\neg(p \vee q) \equiv \neg p \wedge \neg q$

In plain words: push the “not” inside, and flip the connective. “And” becomes “or”, “or” becomes “and.”

It matches how you already talk. “It is not (cheap and fast)” is just another way of saying “it’s (not cheap) or (not fast)” — if it failed the combo, it failed on at least one of them. Say a “not” out loud over a bracket and you can feel the and/or flip.

The toolbox: laws you’re allowed to use

Here is your full set of moves. You don’t memorise these by staring — you learn them by using them, which is what the next section is for. Keep this nearby as a reference. (Every law here that doesn’t mention the constants T “always true” or F “always false” has been machine-checked; the few that do are the base facts everything else is built on.)

The single most useful one for exams is the very last: $p \rightarrow q \equiv \neg p \vee q$. Almost every “prove using laws” question starts by using it to get rid of the arrow, because arrows are awkward to push around and “or” is easy. See an arrow? Your first instinct is to kill it with this law.

The main event: proving with laws

Here is a problem in the exact shape your papers ask, over and over:

Using the laws of logic, prove that $p \rightarrow (q \vee r)$ is equivalent to $(p \wedge \neg q) \rightarrow r$.

Watch how it goes — then you’ll do it yourself, with the support dialled down step by step. The plan is the thing to notice: kill the arrow, tidy up, rebuild the arrow on the other side.

Every line below is a single law applied to the line above it, and every one has been machine-checked — you are standing on solid ground the whole way down. Choose your level: see it fully worked, fill the gaps, work from just the plan, or take the blank page.

That little box $\blacksquare$ at the end (say it: “QED”, or just “done”) is how mathematicians say proof finished. Get in the habit of ending with it — it tells the examiner you know you’ve arrived.

The phrases that earn the marks

A proof isn’t just the symbols — it’s the little sentences naming each move, written down the right-hand side. Those justifications are where half the marks live. Here are the exact phrases to reach for; tap any to copy it:

Notice every line in the worked proof had a phrase like these beside it. That’s the habit: one move, one named reason. Never write a line a marker can’t justify.

Your turn — no scaffolding this time

Here’s a genuinely useful identity to prove: the negation of an implication. What does it mean for “if $p$ then $q$” to be false? Prove that $\neg(p \rightarrow q) \equiv p \wedge \neg q$.

(Think back to Chapter 1’s pizza promise — the promise breaks in exactly one case: the “if” happened and the “then” didn’t. This proof is just that sentence, in symbols.)

Start on the blank page if you’re feeling bold; drop down a level whenever you want a hand. The hint that unlocks it is the same as always: an arrow appears, so kill it first.

Going further: logic doing real work

These laws aren’t a classroom game. The same “reshape one statement into an equivalent, simpler one” move runs underneath things you use daily.

Search engines. When you type samosa AND (recipe OR tutorial) into a search box, the engine uses the distributive law to rewrite and optimise your query before it ever hits the index — literally these laws, at scale.

Checking that rules don’t contradict. Engineers writing the rules for a system (“the alarm is on if a door is open and the system is armed…”) need to check the whole set of rules can all be true at once — that they’re not secretly a contradiction. That’s an equivalence-and-satisfiability check, built from exactly this chapter.

And the big one for you: rewriting a logical expression into the smallest equivalent form is circuit minimisation — fewer logic gates, a cheaper, faster chip. You’ll do this with real hardware in Logic Design (CSD202A), and the algebra of it is your gateway into Boolean algebra. The tidy-up trick you just learned is, quite literally, how chips get designed.

Make it yours

You can now do the thing the exam asks most often in this unit: take an equivalence, start from one side, and walk it to the other with named, legal moves. The whole craft is two habits — kill the arrow first, and never write a line you can’t justify.

Next up: we leave statements that are simply true-or-false and learn to talk about “for all” and “there exists” — the language that lets logic describe real mathematics. That’s Chapter 3, Predicate Logic.

Why true-or-false runs out

Here’s an argument that has convinced people for 2,400 years:

All men are mortal. Socrates is a man. So Socrates is mortal.

You can feel it’s airtight. But here’s the awkward thing: everything you learned in the last two chapters is useless on it. To propositional logic, those three sentences are just three separate letters — $p$, $q$, $r$ — with no visible connection. It can’t see that the “men” in the first line and the “man” in the second are the same idea. It’s reading the sentences from the outside, like sealed boxes, and the link is inside the boxes.

This chapter hands you a can opener. We’re going to crack sentences open and talk about the things inside them — objects, and what’s true of those objects — and about the words all and some, which are doing the real work above. This is the logic that can finally say things like “every even number bigger than 2 is the sum of two primes” or “there is no largest prime” — the logic that mathematics is actually written in. It’s also, fair warning, the hardest-working chapter in this unit and the one the exam leans on most. So let’s build it carefully.

Statements with a hole in them

Take the sentence “$x > 0$.” Is it true or false? You can’t say — it depends what $x$ is. It’s a proposition with a hole in it. Fill the hole and it snaps into a real true-or-false statement: plug in $5$ and it’s true; plug in $-2$ and it’s false.

We write that hole-having sentence as $P(x)$ — say it: “P of x” — and call it a predicate.

Where the word comes from: predicate is Latin for “to declare something about a subject.” In “the sky is blue,” the predicate is the part that makes a claim about the subject. $P(x)$ is exactly that: the claim, waiting for a subject to be dropped in.

So if $P(x)$ means “$x > 0$,” then $P(5)$ is true, $P(-2)$ is false, and $P(x)$ on its own — hole unfilled — is neither. The hole can take more than one slot, too: $S(x, y)$ might mean “$x$ is a sibling of $y$,” a claim with two holes.

One more piece of furniture. The bag of values you’re allowed to drop into the hole is called the domain (sometimes the universe, written $U$). Same predicate, different domain, different story — “$x > 0$” behaves very differently if the domain is “all integers” versus “the positive numbers.” Always know your domain; half the confusion in this chapter comes from losing track of it.

Two new words: for-all and there-exists

Filling the hole one value at a time is slow. The power of this chapter is two words that fill it for a whole domain at once.

“For every $x$, $P(x)$.” Written $\forall x\, P(x)$. Say it: “for-all x, P of x.” The symbol $\forall$ is just a capital A turned upside down — A for All. It claims $P$ is true for every value in the domain, no exceptions.

“For at least one $x$, $P(x)$.” Written $\exists x\, P(x)$. Say it: “there-exists x, P of x.” The symbol $\exists$ is a backwards E — E for Exists. It claims $P$ is true for some value — one is enough.

Where the word comes from: a quantifier tells you the quantity — how many of the domain make $P$ true. $\forall$ says “all of them”; $\exists$ says “at least one.” These are the only two you need.

You’ve actually met these before in disguise. If the domain is small — say just $\{1, 2, 3\}$ — then:

$\forall x\, P(x)$  is just  $P(1) \wedge P(2) \wedge P(3)$   —  a giant AND
$\exists x\, P(x)$  is just  $P(1) \vee P(2) \vee P(3)$   —  a giant OR

That’s the whole intuition. For-all is AND stretched over the whole domain; there-exists is OR stretched over the whole domain. Everything you learned about $\wedge$ and $\vee$ in Chapter 2 is about to come back, scaled up. (Keep this in your pocket — it’s the secret to the rest of the chapter.)

A useful way to picture checking them, when the domain is finite, is a loop:

• To test $\forall x\, P(x)$: walk through every value. The moment you hit one where $P$ is false, stop — the whole thing is false. Get to the end with no failures and it’s true. (One counterexample kills a for-all.)
• To test $\exists x\, P(x)$: walk through values looking for a hit. The moment one makes $P$ true, stop — the whole thing is true. Reach the end with no hit and it’s false. (One witness makes a there-exists.)

And because the domain is doing half the work, the same statement can flip truth value when you change it. “$\forall x\,(x > 0)$” is false over all the integers (there’s $-3$), but true over just the positive integers. Same symbols, different universe, opposite answer.

One housekeeping rule (worth a mark): a quantifier grabs as little as it can. $\forall x\, P(x) \vee Q(x)$ means $\big(\forall x\, P(x)\big) \vee Q(x)$ — the $\forall$ only owns the $P(x)$ next to it. If you mean it to cover the whole “$P(x) \vee Q(x)$,” you must write the brackets: $\forall x\,\big(P(x) \vee Q(x)\big)$. Missing brackets here is a classic silent mistake.

Saying it in symbols — where the marks live

Now the single most-tested skill in this chapter: taking an English sentence and writing it in logic, and back again. It’s on paper after paper, usually for a fat block of marks. And almost all of it comes down to two templates and not mixing them up.

Take “Every student in this class has taken Java.” Let $S(x)$ mean “$x$ is a student in this class” and $J(x)$ mean “$x$ has taken Java,” with the domain being all people. The right translation is:

$\forall x\,\big(S(x) \rightarrow J(x)\big)$  —  for-all teams up with the arrow.

Why the arrow? Because $\forall$ sweeps over everybody in the world — shopkeepers, cats, your grandmother. You can’t claim they all took Java. The arrow is a filter: “if you’re a student in this class, then you took Java.” For everyone who isn’t a student, the “if” never fires, so — remember the pizza promise from Chapter 1 — the implication is true for free, and they don’t spoil the claim.

The tempting wrong answer is $\forall x\,\big(S(x) \wedge J(x)\big)$. Read it out loud: “everyone in the world is a student in this class and took Java.” That says your grandmother is in the class. Nonsense.

Now the other template. “Some student in this class has taken Java” is:

$\exists x\,\big(S(x) \wedge J(x)\big)$  —  there-exists teams up with the and.

Here you just need one witness who is both a student in this class and a Java-taker. The “and” pins down that single person. The tempting wrong answer $\exists x\,\big(S(x) \rightarrow J(x)\big)$ is almost always true for a stupid reason: pick any non-student — a teapot — and “if teapot is a student, then…” is vacuously true, so the whole $\exists$ is satisfied by the teapot. It tells you nothing.

So the entire game is this one line, worth committing to memory:

$\forall$ goes with $\rightarrow$.    $\exists$ goes with $\wedge$.
(“all…arrow,” “some…and”)

Mix them up — an $\exists$ with an arrow, or a $\forall$ with an and — and you’ve written something that’s either absurd or trivially true. Markers see this constantly. Get the pairing right and the marks are yours.

Saying the opposite — De Morgan, upgraded

How do you negate a quantified statement? This is its own exam question, and it has a beautifully simple rule. Suppose someone claims “every student passed,” i.e. $\forall x\, P(x)$. To call them a liar, what do you have to show? Not that everyone failed — just one student who didn’t. So:

$\neg\,\forall x\, P(x) \;\equiv\; \exists x\, \neg P(x)$

“Not everyone passed” means “someone didn’t.” And the mirror image: to deny “some student cheated” ($\exists x\, P(x)$) you must vouch that every single one didn’t:

$\neg\,\exists x\, P(x) \;\equiv\; \forall x\, \neg P(x)$

The rule in four words: flip the quantifier, push the “not” inside. $\forall$ becomes $\exists$, $\exists$ becomes $\forall$, and the negation slides past it onto the predicate. These are called the De Morgan laws for quantifiers — and they’re not even really new. Remember from the last section: $\forall$ is a giant AND and $\exists$ is a giant OR. So this is exactly Chapter 2’s De Morgan — “not (this AND that) = (not this) OR (not that)” — just stretched over a whole domain. Same move you already know.

There’s one more negation worth burning in, because it’s shown up as its own exam question (“show that these two are logically equivalent”): negating an all-arrow statement.

Quantifiers inside quantifiers — and why order is everything

Real statements often need two quantifiers at once. “Everybody loves somebody” has an everybody and a somebody. We nest them: one quantifier sits inside the scope of the other, read left to right.

And here is the single most important warning in this chapter: the order of the two quantifiers can completely change the meaning. Watch these two, with $L(x, y)$ meaning “$x$ loves $y$”:

• $\forall x\,\exists y\, L(x, y)$ — “everybody loves somebody.” Each person gets to pick their own someone. (Warm, plausible.)
• $\exists y\,\forall x\, L(x, y)$ — “there is one special someone whom everybody loves.” A single person, adored by all. (Much stronger, much rarer.)

Same four symbols, swapped order, wildly different claims. The second one is a far bigger ask — it demands one fixed $y$ that works for all the $x$’s at once, while the first lets the $y$ change from person to person.

Don’t take my word for it — poke it. Below is a tiny three-person world (a rock-paper-scissors loop: each beats exactly one other). Build the two statements yourself, swap the order, and watch the verdict flip:

You’ll find “everyone beats someone” ($\forall x\,\exists y$) is true — each player has a victim — but “someone is beaten by everyone” ($\exists y\,\forall x$) is false, because in a loop nobody loses to all the others. Order changed the answer.

There is one safe direction, and it’s worth knowing: if the strong one holds, the weak one follows. “There’s someone everyone loves” does force “everyone loves someone” (that one universally-loved person is the someone each picks). In symbols, $\exists y\,\forall x\, L(x,y) \rightarrow \forall x\,\exists y\, L(x,y)$ is always true. But the arrow only runs that one way — never assume the reverse.

When the same quantifier is repeated, though, order is harmless: $\forall x\,\forall y \equiv \forall y\,\forall x$ and $\exists x\,\exists y \equiv \exists y\,\exists x$. (Two ANDs in a row, or two ORs in a row — you can swap them freely, just like in Chapter 2.) It’s only the mixed $\forall\exists$ pair where order bites.

Your turn

Here’s a set in the exact style of the “choose the obvious predicates and express in logic” question that keeps appearing. Try each on paper first, then reveal. The whole challenge is picking the right template and getting the order right.

Going further: making the order-trap provable, and where it bites in real maths

How do we know $\forall x\,\exists y$ and $\exists y\,\forall x$ differ? We can turn the question into a Chapter-1 truth table and settle it cold. Take the smallest interesting world — just two objects, 1 and 2 — and a two-hole predicate $P(x,y)$. Over a finite world, remember, a $\forall$ is an AND and a $\exists$ is an OR, so each nested statement becomes an ordinary propositional formula in the four facts $P(1,1), P(1,2), P(2,1), P(2,2)$ (call them $p, q, r, s$):

$\forall x\,\exists y\, P(x,y)$  becomes  $(p \vee q) \wedge (r \vee s)$
$\exists y\,\forall x\, P(x,y)$  becomes  $(p \wedge r) \vee (q \wedge s)$

Now just compare their truth tables — the same trick from Chapter 2:

They disagree — for instance at $p = \text{T}, q = \text{F}, r = \text{F}, s = \text{T}$ the first is true and the second is false. That single differing row is a complete, airtight proof that the two orders are not equivalent. (That assignment is exactly the rock-paper-scissors situation: each $x$ has a $y$, but no single $y$ serves every $x$.) This is the kind of thing the checker behind this book does automatically for every claim — no hand-waving, just rows.

Where this will bite you for real: in Real Analysis, the definition of a limit is a nest of three quantifiers. “$f(x)$ tends to $L$” is written, roughly, $\forall \varepsilon\,\exists \delta\,\forall x\,(\dots)$ — say it: “for-all epsilon, there-exists delta…” The entire meaning hangs on that order: $\delta$ is allowed to depend on $\varepsilon$ (chosen after it), but must work for every $x$. Swap two of those quantifiers and you’ve defined something else entirely — and that exact mix-up is the most common stumble in first-year analysis. The care you’re practising now is the care that course will demand. You’re ahead of it.

A bonus pair of laws (these show up in the harder exercises). A $\forall$ may be split across an AND, and a $\exists$ across an OR — but not the other way round:

• $\forall x\,(P(x) \wedge Q(x)) \equiv \forall x\, P(x) \wedge \forall x\, Q(x)$  — fine. (If all are both, then all are $P$ and all are $Q$.)
• $\exists x\,(P(x) \vee Q(x)) \equiv \exists x\, P(x) \vee \exists x\, Q(x)$  — fine.
• $\forall x\,(P(x) \vee Q(x)) \;\not\equiv\; \forall x\, P(x) \vee \forall x\, Q(x)$  — trap. “Every animal is a cat or a dog” is not “every animal is a cat, or every animal is a dog.”
• $\exists x\,(P(x) \wedge Q(x)) \;\not\equiv\; \exists x\, P(x) \wedge \exists x\, Q(x)$  — trap. “Some animal is both striped and a horse” is far stronger than “some animal is striped, and some animal is a horse.”

The pattern echoes the order rule: $\forall$ is happy with AND, $\exists$ is happy with OR; cross them and you get nonsense.

Make it yours

You’ve gone from logic that can only see whole sealed sentences to logic that opens them up — objects, predicates, and the two quantifiers that range over a domain. Three things from this chapter earn marks on nearly every paper, so hold them tight:

• Translation: $\forall$ goes with $\rightarrow$, $\exists$ goes with $\wedge$. All-arrow, some-and.
• Negation: flip the quantifier, push the “not” inside. The opposite of “all do” is “at least one doesn’t.”
• Order: $\forall x\,\exists y$ and $\exists y\,\forall x$ are different; the $\exists\forall$ one is stronger and implies the other, never the reverse.

Next, we put quantifiers to work. Chapter 1 and 2 gave us statements; this chapter gave us statements about everything and something. Now we learn to argue — to chain statements into a watertight case the way the Socrates argument does, and to know a valid step from a sneaky one. That’s Chapter 4, Rules of Inference.

Arguments you can’t wriggle out of

Back in Chapter 1 we met two arguments. One was airtight: “if it rains, the match is off; it’s raining — so pack up.” The other was leaky: “you didn’t text back, so clearly you hate me.” We could feel the difference. This chapter is where you stop feeling it and start proving it — where you can hand someone an argument and say, with a straight face, you cannot escape this conclusion.

An argument is just a list of statements. The ones you’re given to stand on are the premises; the one you’re trying to force is the conclusion. Here’s one you’ve lived:

If you have a current password, you can log onto the network.
You have a current password.
∴ You can log onto the network.

That last line uses a new symbol, $\therefore$ — three dots in a little triangle. Say it: “therefore.” It’s the mathematician’s “so…”, and it always sits in front of the conclusion. The premises go above a line, the conclusion below it — like a sum you’re adding up.

Where the words come from: premise is Latin for “sent before” — the things you put down before the conclusion. Valid is Latin validus, “strong.” A valid argument is a strong one: grab the premises and the conclusion comes with them, no matter what.

Here is the one definition the whole chapter rests on:

An argument is valid when, if all its premises are true, the conclusion is forced to be true as well.

Read it carefully, because it’s sneakier than it looks — and the next section is about the one part of it everyone misreads.

“Valid” is about the shape, not the facts

Here’s the trap. Validity has nothing to do with whether the premises are actually true. It’s about the shape of the argument — whether the conclusion is glued to the premises. Look:

If pigs can fly, then I am the Queen.
Pigs can fly.
∴ I am the Queen.

Silly premises — both false. But the argument is valid. If those daft things were true, the conclusion really would follow. The shape is airtight; the inputs are just garbage. (“Garbage in, garbage out” is a statement about validity: a valid machine fed false premises will happily hand you a false conclusion.)

So an argument can be valid with false premises. And — the other half of the trap — an argument can be invalid even when everything in it happens to be true:

So how do we check the shape? We already have a tool from Chapters 1 and 2. Line up all the premises with “and”, point an arrow at the conclusion, and ask the old question: is it a tautology?

The argument with premises $p_1, p_2, \dots, p_n$ and conclusion $q$ is valid exactly when   $(p_1 \wedge p_2 \wedge \dots \wedge p_n) \rightarrow q$  is a tautology.

That’s the whole idea, and it makes sense word for word: “a tautology” means “true in every row,” so there is no row where the premises are all true and the conclusion is false — which is exactly “you can’t escape it.” Take the password argument: $p$ for “you have a current password,” $q$ for “you can log on.” The shape is $(p \wedge (p \rightarrow q)) \rightarrow q$. Toggle it — the final column is all true:

All true, every row. The argument is valid — provably, not just by feel.

So we’re done? Build a truth table and check? In principle, yes. In practice, the exam arguments have four or five letters, and that’s $2^5 = 32$ rows, then $2^6 = 64$… the same slog you met in Chapter 2. So we do the same thing we did there: instead of grinding rows, we build a toolbox of trusted moves and chain them. That toolbox is the rest of this chapter.

The toolbox: rules of inference

A rule of inference is a tiny argument so obviously valid that we just trust it and reuse it — a Lego brick of reasoning. You met the most famous one already, in the password example. It has a grand name:

Modus ponens — the workhorse

Say it: “MOH-duss POH-nenss.” It’s Latin for “the method that affirms” — you affirm the if-part, and the then-part drops out. In plain English: if you know ‘if p then q’, and you know p is true, then you may write down q.

From  $p \rightarrow q$  and  $p$,  conclude  $q$.    Tautology: $(p \wedge (p \rightarrow q)) \rightarrow q$.

That’s the move you just watched come out all-true in the table above. It’s the engine; most proofs are just modus ponens over and over. Every other rule in the toolbox is the same kind of thing — a trusted little shape — and every one of them has been machine-checked to be a tautology, so when you reach for one you are standing on solid ground. Here is the full set:

Don’t memorise this by staring — you’ll learn it the way you learned the laws of logic, by using it. But notice the four you’ll lean on hardest, because they say something you already believe:

• Modus tollens (“the method that denies”): the promise didn’t pay out, so the trigger never happened. If snow means I study, and I didn’t study, then it didn’t snow. It’s the contrapositive from Chapter 1, wearing a uniform.
• Hypothetical syllogism (say it: SIL-uh-jiz-um, Greek for “reasoning together”): chaining arrows. Snow → study, study → an A, therefore snow → an A. Dominoes.
• Disjunctive syllogism: one of two doors, and one is shut. Maths or literature; not maths; therefore literature.
• Simplification and addition are the small change of proofs. Simplification: “p and q, so in particular p” — pick one off a pair. Addition: “p, so p or anything” — an “or” is easy to make true, so you’re allowed to weaken a fact into an “or” whenever it helps. (That last one feels like cheating the first time. It isn’t — watch for it later.)

The two traps that look like rules

Some arguments wear the costume of a valid rule but are quietly broken. They’re called fallacies (say it: FAL-uh-seez, Latin fallacia, “a deception”). Two of them trip up almost everyone, and the exam likes to slip one in — a question that asks “is this argument valid?” where the honest answer is “no.” Both are just the converse and inverse errors from Chapter 1, grown up.

Trap 1 — affirming the conclusion. You have $p \rightarrow q$, and you spot that $q$ is true, so you announce $p$. Wrong way down the arrow.

If people have the flu, they cough.
Alison is coughing.
∴ Alison has the flu.  (Not valid!)

Plenty of things cause a cough. Having the flu is enough to make you cough, but it isn’t the only way — so the cough doesn’t prove the flu. The machine agrees: $((p \rightarrow q) \wedge q) \rightarrow p$ is not a tautology (it fails in the row where Alison coughs without the flu), and that failure is checked in this chapter’s claims.

Trap 2 — denying the hypothesis. You have $p \rightarrow q$, you see $p$ is false, so you announce $\neg q$. Same wrong direction.

If it is raining, the sky is cloudy.
It is not raining.
∴ The sky is not cloudy.  (Not valid!)

Skies can be cloudy with no rain at all. Again the machine confirms $((p \rightarrow q) \wedge \neg p) \rightarrow \neg q$ is not a tautology.

The clean way to keep these straight: the two valid arrow-rules go forwards (modus ponens: have $p$, get $q$) or backwards with a ‘not’ (modus tollens: have $\neg q$, get $\neg p$). Anything else — affirming $q$ to get $p$, or denying $p$ to get $\neg q$ — is a trap.

The main event: building a proof, line by line

Now the move the exam asks for over and over. You’re handed a few premises and a conclusion, and you have to get there — one trusted rule at a time, naming each move as you go. It’s exactly like the “prove using laws” proofs from Chapter 2, except the moves are now rules of inference and each new line is a fresh fact, not a re-dress of the last one.

Here is the single most reliable version of this question. Some shape of it has turned up on the logic paper again and again — worth knowing cold:

Show that the premises “If you send me an email, then I’ll finish the program,” “If you don’t send me an email, then I’ll go to sleep early,” and “If I go to sleep early, then I’ll wake up refreshed” lead to the conclusion “If I don’t finish the program, then I’ll wake up refreshed.”

The first job is always the same: name the propositions, then translate.

• $p$: you send me an email
• $q$: I’ll finish the program
• $r$: I’ll go to sleep early
• $s$: I’ll wake up refreshed

So the premises are $p \rightarrow q$,  $\neg p \rightarrow r$,  $r \rightarrow s$, and the target is $\neg q \rightarrow s$. Now we walk it down. Notice the plan: the conclusion starts with $\neg q$, so begin by getting a $\neg q$ on the left of something — and the contrapositive of premise 1 does exactly that. After that it’s dominoes (hypothetical syllogism), twice.

Every derived line below has been machine-checked: the line really does follow from the lines it cites. Choose your level — see it fully worked, fill in the reasons, work from just the plan, or take the blank page.

That’s the whole craft: a column of statements down the left, a named reason for each one down the right, and a $\blacksquare$ when you land. A line without a reason beside it earns nothing — the reasons are where the marks live.

The phrases that earn the marks

Same as in Chapter 2: the little sentences naming each move are half the answer. Here are the exact ones for inference proofs — tap any to copy it:

Notice the habit: one new line, one named rule, and the line numbers it came from. Write the line numbers — “hypothetical syllogism, lines 4 and 2” — and a marker can follow you instantly.

Your turn — the one with the surprise ending

Now you drive. This one is a real paper question, and it’s a beauty because it uses almost the whole toolbox — and it ends with that “feels like cheating” move from earlier.

Show that the premises “If it is Saturday, we play soccer or basketball,” “If the field is occupied, we do not play soccer,” and “It is Saturday and the field is occupied” lead to the conclusion “We play basketball or volleyball.”

Translate first. Let $p$: it’s Saturday, $q$: the field is occupied, $r$: we play soccer, $s$: we play basketball, $t$: we play volleyball. So the premises are $p \rightarrow (r \vee s)$,  $q \rightarrow \neg r$,  $p \wedge q$, and the target is $s \vee t$.

Before you start, look at that target. Volleyball ($t$) is never mentioned in any premise. Where on earth will it come from? Hold that thought — it’s the whole trick, and it’s the addition rule waiting to pounce. Start on the blank page if you’re bold; drop a level whenever you want a hand. The opening move is to crack open that “and” premise with simplification.

There it is. Volleyball shows up at the very end, out of nowhere — and it’s completely legal, because once you know basketball is on, “basketball or volleyball” is automatically true. That’s addition: a fact can always be weakened into an “or”. If a conclusion has a letter the premises never mention, addition at the end is almost always how it gets there.

Stepping up: inference with “for all” and “there exists”

Everything so far has been about whole statements being true or false. But Chapter 3 gave you $\forall$ and $\exists$ — statements about every $x$ or some $x$. To reason with those, you need four more rules, and they all do one simple job: take the quantifier off, do ordinary inference, put a quantifier back on.

• Universal instantiation (take the “for all” off): if $\forall x\, P(x)$ is true, then $P(c)$ is true for any particular $c$ you name. “All dogs are cuddly; Fido is a dog; so Fido is cuddly.”
• Universal generalisation (put a “for all” on): if you proved $P(c)$ for a totally arbitrary $c$ — one you assumed nothing special about — then $\forall x\, P(x)$.
• Existential instantiation (take the “there exists” off): if $\exists x\, P(x)$, then you may name one and call it $c$ — “someone got an A; call her $c$.”
• Existential generalisation (put a “there exists” on): if $P(c)$ holds for a specific $c$, then $\exists x\, P(x)$ — “Michelle got an A, so someone did.”

The famous one ties it all together. It is the oldest argument in logic, and it is just universal instantiation followed by modus ponens:

And here is the version that keeps appearing on the logic paper — the same machinery, one notch harder, worth a full chunk of marks:

An honest note. The propositional proofs above (the email and the soccer ones) are checked line by line by the book’s verifier — every step is a proven tautology. The quantifier steps here (EI, UI, EG) can’t be checked the same brute-force way, for the same reason Chapter 3 flagged: “for all” ranges over a whole domain. So treat the shape of these proofs as the thing to learn; the propositional engine inside them — modus ponens, simplification — is rock-solid.

What the exam actually asks

Three shapes cover almost everything you’ll be set in this unit. They’re really the same task in three coats:

• “Show that the premises … lead to the conclusion …” — build the derivation.
• “Is this argument valid?” — build the derivation if you can; if you smell a fallacy, find the row where the premises are all true but the conclusion is false, and say so.
• “Construct a valid argument showing …” — same as the first, usually with quantifiers.

And one recipe handles all three:

1. Name the propositions ($p, q, r, \dots$) — write the key out.
2. Translate every premise and the conclusion into symbols.
3. Plan from the target. What does the conclusion start with? Get that piece on the page first. (A $\neg q$ target → reach for a contrapositive; an unmentioned letter in the target → addition at the end.)
4. Derive one line at a time, each with a named rule and the line numbers it came from. End with $\blacksquare$.

The real skill being tested isn’t doing a step — each step is easy. It’s recognising which step fires next. That recognition is what the toolbox table and all that “which rule is this?” practice were quietly building.

Going further: machines that prove things

Rules of inference aren’t a classroom ritual — they’re the instruction set for automated reasoning. The quiet star of the toolbox, resolution, is the one a computer actually runs. Resolution is a single rule powerful enough that, applied over and over, it can prove any valid conclusion in propositional logic. Turn everything into “or”s, then resolve away opposite letters until you reach a contradiction — that’s the heart of a SAT solver, the workhorse behind chip verification, software bug-finding, and scheduling.

It’s also how the language Prolog works: you give it facts and rules, ask a question, and it searches for a proof using inference like this. And it’s the seed of a deep idea you’ll meet later — that a proof can itself be an object a machine builds and checks. When you write your derivations with named reasons and line numbers, you are doing by hand exactly what an automated prover does at a million lines a second.

Make it yours

You can now do the thing this unit asks most: take a pile of premises and walk them to a conclusion, one trusted rule at a time, with a reason beside every line. The whole craft is four habits — name and translate first, plan from the target, one line one named rule, and never go the wrong way down an arrow. A proof, in the end, is nothing but a valid argument written out in full — which is exactly what Chapter 5 is about.

Next up: we put these rules to work. Direct proof, proof by contraposition, proof by contradiction, proof by cases — the named strategies for proving real mathematical statements. Every one of them is just a clever arrangement of the inference rules you now own. That’s Chapter 5, Proof Techniques.

Writing for a reader who wants you to be wrong

In Chapter 4 you learned to take a pile of premises and walk them to a conclusion, one trusted rule at a time. A proof is that same craft, pointed at a real mathematical claim — “every odd number squared is odd,” “$\sqrt{2}$ is not a fraction” — and written so tightly that you could hand it to the most hostile reader in the world, someone who wants you to be wrong, and they still couldn’t find a single crack to slip through.

That image is the whole chapter. Every technique here is just a different way of leaving the hostile reader nowhere to stand. And the thing the exam actually rewards isn’t cleverness — it’s leaving a clean, named trail they can follow: here is what I assumed, here is the move I made, here is why it’s legal. A correct idea with no reasons written down earns almost nothing. So we’ll spend as much time on the words as on the maths.

Here’s the toolbox we’re going to build. Don’t worry about the names yet — just notice there are only a handful, and each one is a fixed move you reach for in a fixed situation:

• Direct — walk straight at it: assume the “if,” reach the “then.”
• Contraposition and contradiction — two ways in through the back door, for when the front door is locked.
• Cases and WLOG — for claims that behave differently in different situations.
• Existence, counterexample, and uniqueness — for claims that say something exists, not everything works, or exactly one thing works.

That’s the entire syllabus for this chapter. The real skill being trained — the one the marks hide in — is looking at a claim and knowing which of these to reach for. We’ll build that the only way it can be built: by writing a lot of proofs, at first with the whole thing laid out for you, then with more and more of it handed back to you to do yourself.

First, the words — and three definitions you’ll use forever

A few pieces of furniture, said out loud once so they stop being scary.

A theorem is just an important true statement that has been proved. A lemma (say it: LEM-uh) is a smaller “helping” theorem — a stepping-stone you prove on the way to a bigger one. A corollary (say it: KOR-uh-lair-ee) is a freebie that drops out almost immediately after a theorem. A conjecture (say it: kun-JEK-chur) is a statement someone believes is true but nobody has proved yet. And an axiom is a rule we simply agree to start from, no proof asked.

Where the words come from: lemma is Greek for “something taken” — a thing you take in hand to use. Corollary is Latin for “a little garland,” the small gift handed over with the main one. A theorem is, from the Greek, “a thing to be looked at.” Names that tell you their own job.

Now the part you’ll lean on in nearly every proof in this chapter. Three definitions, written as formulas, because turning a word into a formula is what lets the algebra start:

• An integer $n$ is even when $n = 2k$ for some integer $k$.
• An integer $n$ is odd when $n = 2k + 1$ for some integer $k$.
• A number $r$ is rational when $r = a/b$ for integers $a, b$ with $b \neq 0$.

That’s the move almost every proof opens with: take the word in the hypothesis (“$n$ is odd”) and immediately rewrite it as its formula (“$n = 2k+1$”). Once it’s a formula, you can do algebra to it; once it’s back in the shape of a definition, you can read the word off again.

One last thing to notice. Most theorems hide a silent “for all.” When a book says “if $x > y$ then $x^2 > y^2$,” it really means “for every pair of positive reals $x, y$…” You don’t prove it for one special $x$ — you prove it for a totally arbitrary $x$, one you assumed nothing about, and then it holds for all of them at once. (That trick is exactly the universal generalisation you met in Chapter 4.)

Two free wins, worth knowing by name. A trivial proof: if the “then” part is already true on its own, the whole “if…then” is true and there’s nothing to do. A vacuous proof (say it: VAK-yoo-us, Latin for “empty”): if the “if” part is never true, the promise can never be broken, so it’s true for free — remember the pizza promise from Chapter 1. You’ll meet both again hiding inside induction.

The front door: direct proof

The simplest weapon. Assume the “if” part is true, and march forward, one honest step at a time, until you reach the “then” part. No tricks. Most proofs you’ll ever write are direct.

Here is the gentlest example in the whole subject — learn its shape cold, because every other proof is a variation on it. We’ll prove: if $n$ is odd, then $n^2$ is odd. Watch how it starts by turning the word “odd” into the formula $2k+1$, does a little algebra, and lands back on the shape of an odd number.

This is a proof fader. Choose your level: see it fully worked, fill in the missing reasons, work from just the plan, or take the blank page and write the whole thing yourself. Start at “Show me” for your very first one.

The little black square $\blacksquare$ (or the letters QED) marks the end of a proof. Say it: QED — it’s short for the Latin quod erat demonstrandum, “which was to be shown.” It’s you planting a flag: I said I’d prove this, and there it is.

The phrases that earn the marks

Just like the inference proofs in Chapter 4, half of a proof’s marks live in the little sentences that name each move. Freezing up because you know the maths but not how to word it is the single most common way to lose marks here. So here is a palette of the exact phrases — tap any to copy it:

Notice the habit these build: name what you’re assuming, name every definition you use, and announce the contradiction or the conclusion when you reach it. A marker who can follow your sentences will give you the marks.

When the front door is locked: the two indirect proofs

Sometimes marching straight at the “then” part is painful, because the “then” part is hard to get your hands on. Two classic moves let you sneak in the back instead. Both are called indirect proofs, and the exam loves them — a recent paper asked for both at once.

Back door 1 — proof by contraposition

Say it: contraposition. Instead of proving “if $p$ then $q$,” you prove its contrapositive: “if not $q$, then not $p$.” You met these two back in Chapter 1 and saw they were equivalent — the same statement in different clothes. Here’s the table again, so you can watch the two columns come out identical, every single row:

All true, every row — so $p \rightarrow q$ and $\neg q \rightarrow \neg p$ are genuinely the same claim. That means you are allowed to prove whichever one is easier. And often the flipped one is much easier, because a hard-to-handle conclusion becomes an easy-to-handle assumption.

Take if $n^2$ is odd, then $n$ is odd. Head-on, you’d have to start from “$n^2$ is odd” — awkward, because square roots are messy. But the contrapositive is “if $n$ is even, then $n^2$ is even” — and starting from “$n$ is even” is a dream, because $n = 2k$ drops straight into the algebra. This exact proof was a 3-mark exam question. Fade it down a level at a time:

Back door 2 — proof by contradiction

Say it: contradiction (Latin, “to speak against”). This one has a flavour of judo. To prove a statement, you assume it’s false and show that this assumption forces something impossible — a number that is both odd and even, say, or $0 = 1$. Since the assumption led to nonsense, the assumption was wrong, so the statement must be true.

Before we use it — a quick check of your instinct.

Good. Now the proof — this was a 2-mark exam question, and it’s the perfect first contradiction because the impossibility is so clean:

Why this is legal, in one line. “Prove $q$ by assuming $\neg q$ and reaching an impossibility” works because $(\neg q \rightarrow (r \wedge \neg r)) \rightarrow q$ is a tautology — if denying $q$ forces a flat contradiction, then $q$ had to be true. (The book’s verifier checks that for us.)

Your turn — same statement, which back door?

Contraposition and contradiction feel similar — both start by negating something — and students mix them up constantly. Here’s the clean difference, worth memorising:

• Contraposition: assume not $q$, and aim to reach not $p$. You end on the negated hypothesis. No “contradiction” needed.
• Contradiction: assume $p$ and not $q$, and aim to reach anything impossible at all. You end on an absurdity.

One reliable tell: if the conclusion is hard to start from but its opposite is easy to start from, reach for contraposition. If you can’t see a clean target at all but you can imagine the false version blowing up, reach for contradiction.

When one argument won’t cover everything: cases & WLOG

Some claims behave differently in different situations — positive versus negative, even versus odd. You can’t cover them with a single line of algebra. The fix is proof by cases: split every possibility into a few buckets that between them catch everything, prove the claim inside each bucket, and you’re done.

Why this is legal. If your cases are exhaustive — say “$p$ or $q$ or $r$” covers every possibility — then proving the conclusion in each one really does prove it overall, because $\big[(p \vee q \vee r) \rightarrow c\big]$ is the same as $\big[(p\rightarrow c) \wedge (q\rightarrow c) \wedge (r\rightarrow c)\big]$. The verifier checks that distribution for 2, 3, and 4 cases. The one thing you must never skip: say why your cases are exhaustive.

The classic exam version splits on signs. We’ll prove $|xy| = |x|\,|y|$ for all real $x, y$ — a real term-test question — by the four sign-combinations of $x$ and $y$:

The shortcut: “without loss of generality”

Sometimes two of your cases are identical except for the names. Writing both out is a waste — so you handle one and say the magic phrase: without loss of generality (often written WLOG). Say the whole thing out loud: “without loss of generality.” It means: by symmetry, the case I’m skipping is the same argument with the labels swapped, so handling this one handles both.

The catch — and markers watch for this — you may only say WLOG when the situation really is symmetric. Here’s the staple exam proof where it shines. We’ll prove: if $xy$ is even and $x + y$ is even, then $x$ and $y$ are both even. Because $x$ and $y$ play identical roles in both “$xy$” and “$x+y$,” we can assume one of them is the odd one and get the other case free:

Claims that say “something exists”

Some statements don’t say “for all” — they say “there exists.” There are two ways to prove one. The honest, hands-on way is a constructive proof: just build the thing and show it works. To prove “some even number is a sum of two primes,” you write $10 = 3 + 7$ and you’re done.

The slippery, beautiful way is a nonconstructive proof: prove the thing must exist without ever building it. This sounds like cheating. It isn’t — and it was worth a full 5 marks on a recent test, so it is firmly on your exam, not a curiosity.

The famous example: there exist irrational numbers $x$ and $y$ such that $x^y$ is rational. The trick is to set up two cases and win in both — so you never have to figure out which case is actually true. Try predicting before you reveal it:

Sit with how strange and airtight that is. We have no idea whether $\sqrt{2}^{\sqrt{2}}$ is rational. We never find out. And yet we have completely proved the statement, because whichever way that coin lands, a working pair is sitting right there. The hostile reader can’t object — both their objections are already answered.

The flip side: disproving “for all” with one counterexample

To prove “for all $x$, $P(x)$” you must handle every $x$. But to disprove it, you only need one $x$ where it fails — a counterexample. That asymmetry is just Chapter 3’s rule $\neg\forall x\, P(x) \equiv \exists x\, \neg P(x)$: the opposite of “always” is “at least once not.”

So if someone claims “every positive integer is the sum of three squares,” you don’t argue — you just point at $7$ (you can’t write $7$ as $a^2+b^2+c^2$) and the claim is dead. One counterexample beats any number of confirming examples. When a question says “is it true that…?”, hunting for a small counterexample is often faster than trying to prove it.

The most famous proof in mathematics: $\sqrt{2}$ is irrational

This is the proof every mathematician knows by heart, and it’s the showpiece of proof by contradiction. It also reuses something you proved earlier in this very chapter — watch for it. The claim: $\sqrt{2}$ cannot be written as a fraction.

The plan is pure judo. Assume it can, in lowest terms, and let that “lowest terms” assumption quietly hang itself.

Feel the shape: one quiet assumption (“lowest terms”) sits there harmlessly for five lines, then springs shut at the end. That’s the art of a contradiction proof — set a trap early, walk the reader into it, snap.

Its twin is just as famous — there is no largest prime — and it runs on exactly the same engine.

Not just “at least one” — “exactly one”

Sometimes a claim is stronger than “something exists.” It says there is exactly one such thing. The symbol is $\exists!\,x$ — say it: “there exists a unique $x$.” A uniqueness proof always has two halves:

• Existence: show at least one such thing exists (build it, usually).
• Uniqueness: show there can’t be two — assume you have two things that both work, and prove they must actually be equal.

A tiny example you already know: for real numbers $a, b$ with $a \neq 0$, the equation $ar + b = 0$ has a unique solution $r$. Existence: $r = -b/a$ works, since $a\!\left(-\tfrac{b}{a}\right) + b = -b + b = 0$. Uniqueness: if $r$ and $r'$ both solve it, then $ar + b = ar' + b$, so $ar = ar'$, and because $a \neq 0$ we can divide to get $r = r'$. One value, no rivals. $\blacksquare$

Notice where $a \neq 0$ did its work — it’s what let us divide. Uniqueness proofs almost always lean on one such “you’re allowed to cancel/divide here” fact; finding it is the whole game.

What the exam actually asks

The proof question on this unit’s paper is reliable in shape and slippery in technique. One slot rotates which weapon it wants — it has been a cases proof one year, a nonconstructive existence proof the next, and a contradiction-plus-contraposition pair the year after that. The longer paper carries the “both-even” WLOG proof almost every time. So you don’t get to specialise — you carry the whole toolbox, and you win by recognising which tool fits.

Here is the recipe that handles any of them:

1. Name what you’re assuming and what you’re proving. Write the hypothesis $p$ and conclusion $q$ out plainly.
2. Pick the door. Direct unless the conclusion is hard to start from. If its opposite is easier to start from → contraposition. If you can’t target it but can imagine the false version exploding → contradiction. If it behaves differently in different situations → cases (and WLOG if they’re symmetric). If it says “there exists” → construct one, or use the two-case nonconstructive trick. If it says “for all” and you suspect it’s false → hunt a counterexample.
3. Turn words into formulas ($n$ odd $\to n = 2k+1$), do the algebra, turn the formula back into a word.
4. Name every move, and finish with $\blacksquare$.

Step 2 is the whole exam. The steps themselves are easy — squaring a bracket, pulling out a 2 — but choosing the right door is what separates a clean 5 from a stuck 1. One last drill on exactly that:

Going further: the rules behind the rules

The $\sqrt{2}^{\sqrt{2}}$ proof leans on something you might not have noticed you assumed: that the statement “$\sqrt{2}^{\sqrt{2}}$ is rational” is either true or false, with no third option. That’s the law of excluded middle, and most of mathematics takes it for granted. But a school of mathematicians — the constructivists — reject nonconstructive proofs precisely because they refuse to call a pair of numbers “known to exist” when you can’t actually exhibit it. To them, our slick proof isn’t good enough. (For the record, there are constructive proofs of the same fact — they’re just harder.) You’ll meet this fault-line again if you study logic or the foundations of computer science, where “a proof that something exists” and “an algorithm that finds it” turn out to be deeply linked.

Two more threads worth a glance. First, the 1729 story: there’s a constructive existence proof hiding in a famous anecdote — the mathematician Ramanujan, ill in hospital, was told the number of his friend’s taxicab, 1729, was “rather dull.” He replied instantly that it was the smallest number expressible as a sum of two cubes in two different ways: $1729 = 10^3 + 9^3 = 12^3 + 1^3$. That single line is a complete constructive proof that such a number exists — he built it.

Second, the well-ordering principle — “every non-empty set of positive integers has a smallest element” — is the quiet engine behind “lowest terms” in the $\sqrt{2}$ proof, and it’s the seed of the next chapter: mathematical induction is really well-ordering wearing a different hat.

Where this all goes: the $\sqrt{2}$ proof is the doorway to Real Analysis, where you build the real numbers precisely because the rationals have holes like $\sqrt{2}$ in them. The infinitude of primes opens Number Theory, which you follow all the way to the cryptography in this course’s final unit. The proofs you’re writing by hand now are the literal first sentences of those subjects.

Make it yours

You now own the whole toolbox. A proof, you’ve seen, isn’t a flash of genius — it’s a small set of named moves and the discipline to write the reasons down. Direct when you can go straight at it; contraposition when the opposite is easier to start from; contradiction when the false version blows up; cases (with WLOG for the symmetric ones) when one argument won’t cover everything; existence by building or by the two-case trick; counterexample to kill a “for all”; uniqueness in two halves. The exam isn’t testing whether you can square a bracket — it’s testing whether you can look at a claim and name the right door. Every fader in this chapter was training exactly that.

There’s one proof shape we’ve dodged so far: claims about every positive integer at once — “$1 + 2 + \dots + n = \tfrac{n(n+1)}{2}$ for all $n$,” “$133$ divides this expression for all $n$.” You can’t check infinitely many cases, and a single direct argument rarely reaches them all. The technique built for exactly this — knock over the first domino, show each one topples the next — is powerful enough and common enough on the exam that it earns its own chapter. That’s Chapter 6, Mathematical Induction, and it closes out Term Test 1.