Logic

Two people disagree about whether a conclusion really follows from what was said, and nothing in the words themselves settles it.

That is the problem this subject solves. Not whether a claim is true, which is usually a question for chemistry or history or the accounts, but whether accepting some claims commits you to another one. The answer turns out to depend on the shape of the argument and on nothing else, and shapes can be written down, listed and checked. Everything in the fourteen lessons that follow is machinery for doing that check, and this lesson fixes what the check is meant to test.

What an argument is

An argument here is not a quarrel. It is a set of statements, the premises, offered in support of one further statement, the conclusion. A calm paragraph in a contract and a shouted claim can have the same argument in them.

A statement is a sentence that is true or false. "The Thames flows through London" is one. "Close the door", "what time is it" and "if only I had known" are not, because they make no claim that could be right or wrong. That is a real restriction, worth stating up front: the machinery only judges arguments whose parts are true or false.

English marks the parts with signposts. "Therefore", "so", "hence" and "it follows that" introduce conclusions; "because", "since" and "given that" introduce premises. The order on the page means nothing, so "Socrates is mortal, since all men are mortal and he is a man" is the same argument written backwards.

Two things that look like arguments are not. An explanation takes an agreed fact and says why it happened: "the bridge collapsed because the bearings seized" is not trying to convince anyone the bridge collapsed. And a confident chain of assertions with no support relation is a description. The test is whether one statement is being offered as a reason for another.

Validity is an impossibility claim

Here is the central definition, and everything else in the subject depends on getting it exactly right.

An argument is valid if and only if there is no possible situation in which all its premises are true and its conclusion is false.

Read what that does and does not say. It does not say the premises are true. It does not say the conclusion is true. It says the combination "premises all true, conclusion false" cannot happen, which is a claim about what is possible, not about what is the case. Validity is the guarantee that truth is transmitted: feed true premises into a valid argument and a true conclusion must come out. Feed false ones in and the guarantee is silent.

So testing validity means trying to imagine the bad combination. Take: "All whales are fish. All fish are mammals. Therefore all whales are mammals." Both premises are false and the conclusion is true, but that is not the question. The question is whether any situation could make both premises true while leaving the conclusion false, and none could: if every whale is among the fish and every fish is among the mammals, every whale is among the mammals. The argument is valid.

Now take: "If the company committed fraud, the quarterly figures would be unusually smooth. The figures are unusually smooth. Therefore the company committed fraud." Both premises might well be true, and so might the conclusion. But the bad combination is easy to picture: a genuinely stable business with a small product range produces smooth figures with no fraud anywhere. Premises true, conclusion false. The argument is invalid, and it stays invalid even in the cases where the company did commit fraud.

The four combinations

Since validity and truth are independent, it pays to see how they combine. Of the four pairings of premise truth with conclusion truth, three are open to a valid argument and one is not. True premises with a true conclusion is the ordinary good case. False premises with a false conclusion is fine too, since such an argument fails on its facts rather than its logic. False premises with a true conclusion is the whales case above. The single forbidden pairing is true premises with a false conclusion, and it is forbidden by the definition itself, which is what makes validity worth having.

Invalid arguments can show all four, including true premises with a true conclusion, which is the trap. "Paris is the capital of France, therefore water is a compound of hydrogen and oxygen" has a true premise and a true conclusion and no connection whatever between them. Checking that the premises and the conclusion are all true tells you nothing about whether the argument works.

Example. Build an argument that is valid, has at least one false premise, and has a true conclusion.

Start from a form known to transmit truth, then feed it a falsehood that happens to land somewhere true. "All metals conduct electricity. Graphite is a metal. Therefore graphite conducts electricity." The second premise is false, since graphite is a form of carbon, a non-metal. The conclusion is true, since graphite conducts well enough to be used for the brushes in electric motors. And the argument is valid: if everything metallic conducted and graphite were metallic, graphite would conduct. Validity was never a claim about the premises.

Now you. Build an argument that is invalid, has two true premises, and has a true conclusion.

Soundness

Validity is a low bar on its own, because it never asks whether the premises are true. The property that actually matters in argument is soundness: an argument is sound when it is valid and all its premises are in fact true. A sound argument has a true conclusion, guaranteed, and that is exactly what a proof is.

The division of labour is the point. Logic owns validity completely and can settle it by inspection of form. Nothing in logic can settle whether "all metals conduct electricity" is true; that is measurement. So an argument is attacked in one of two quite different ways, and confusing them wastes everybody's time. Either you deny a premise, which is a dispute about the world, or you deny that the conclusion follows, which is a dispute about form. "Your figures are wrong" and "your figures do not show that" are different objections and need different evidence.

This subject is entirely about the second kind, which is a narrow speciality: most bad arguments in the wild fail on their premises rather than their form. The last lesson comes back to that honestly.

Form is what does the work

Look again at the whales argument. Nothing about whales, fish or mammals was used. Replace those three words with any others and the guarantee survives:

All $A$ are $B$. All $B$ are $C$. Therefore all $A$ are $C$.

Validity is a property of this form, and every argument with this shape, on any subject, in any language, is valid. That is the discovery the subject is built on, and it was Aristotle's, in the Prior Analytics of around 350 BCE. His decisive move was the one just made: writing letters where the terms go, so that an argument can be studied without knowing what it is about.

Contrast the invalid argument. Its form is: if $P$ then $Q$; $Q$; therefore $P$. Every argument of that shape is invalid, including the ones with true conclusions, because the shape carries the fault. This is why logic can be taught at all: there are not infinitely many arguments to memorise, only a stock of forms and a method for the forms nobody has catalogued.

Refutation by parallel form

The most useful practical consequence: if validity depends only on form, then two arguments with the same form stand or fall together. So to show that an argument is invalid, exhibit another argument of the same form whose premises are plainly true and whose conclusion is plainly false. That parallel argument cannot be valid, so neither can the original, and the person you are arguing with does not have to grant anything about the original subject matter.

Suppose someone argues: "Every economy that raised interest rates in 2022 saw inflation fall by 2024. Inflation in Japan fell by 2024. So Japan raised interest rates in 2022." Rather than argue about Japanese monetary policy, hand back the parallel: "Everyone with flu has a temperature. This patient has a temperature. So this patient has flu." The premise is true and the conclusion does not follow, since a hundred other things raise a temperature. Same form, obviously broken, argument over. The method has one requirement: the parallel must genuinely share the form rather than merely feel similar, and if the original says "some" where the parallel says "all", the refutation fails and will be seen to fail.

Example. Refute by parallel form: "If a country has a large trade deficit, its currency will weaken. The pound weakened. So the United Kingdom has a large trade deficit."

The form is: if $P$ then $Q$; $Q$; therefore $P$. Substitute something where the second step is transparently bad. "If it snowed last night, the roof is wet. The roof is wet. So it snowed last night." The roof is wet because it rained, or because someone hosed it down. True premises, false conclusion, same shape, so the original is invalid. Notice that the United Kingdom does in fact run a large trade deficit. The conclusion is true and still does not follow, which is exactly the distinction this lesson is drilling.

Now you. Refute by parallel form: "No one who trains properly gets injured. Ferrer was injured. So Ferrer did not train properly."

Forms worth knowing by name

Four propositional forms account for most everyday reasoning, and they come in two valid pairs and two invalid impostors that differ from them by one word.

Modus ponens is: if $P$ then $Q$; $P$; therefore $Q$. Valid, and the workhorse of every calculation and every application of a rule. Modus tollens is: if $P$ then $Q$; not $Q$; therefore not $P$. Valid, and the engine of testing: a hypothesis predicts something, the something fails to appear, the hypothesis goes.

The impostors change one word each. Affirming the consequent is: if $P$ then $Q$; $Q$; therefore $P$. Invalid, and the most common fault in reasoning about evidence, being the fraud argument, the flu argument and the trade deficit argument all at once. Denying the antecedent is: if $P$ then $Q$; not $P$; therefore not $Q$. Also invalid. "If you inherit the gene you will get the disease. She did not inherit it. So she will not get it." Other causes remain.

Two more, both valid. Disjunctive syllogism: $P$ or $Q$; not $P$; therefore $Q$. And hypothetical syllogism: if $P$ then $Q$; if $Q$ then $R$; therefore if $P$ then $R$, which is how long chains of reasoning are stitched together.

Example. Name the form and say whether it is valid: "If the alloy contains nickel, the sample is magnetic. The sample is not magnetic. Therefore the alloy contains no nickel."

The second premise denies the consequent, so this is modus tollens, and it is valid. Any situation making both premises true has a non-magnetic sample, and a nickel-bearing alloy would have been magnetic, so there is no nickel. Whether it is sound is a separate question, and here the first premise is doubtful, since austenitic stainless steels contain about 8 per cent nickel and are essentially non-magnetic. The argument is valid and unsound, and only the second half of that verdict is metallurgy.

Now you. Name the form and say whether it is valid: "If the server were down, the dashboard would be blank. The server is not down. Therefore the dashboard is not blank."

Where the guarantee stops

Everything so far has demanded an absolute guarantee, and most real reasoning cannot supply one. "The last four hundred swans I saw were white, so the next one will be white" has premises that make the conclusion likely without forcing it, which is why Australia was a surprise. Such arguments are inductive, and they are judged on a different scale, strength rather than validity, one that belongs to probability and statistics rather than to logic. Deductive validity buys certainty and pays for it by never telling you anything the premises did not already contain.

Two edge cases fall out of the definition and are worth meeting now rather than in the middle of a proof. If the premises contradict each other, no situation makes them all true, so the forbidden combination cannot arise and the argument is valid whatever the conclusion says. And if the conclusion cannot be false, the same holds for any premises at all. Both feel wrong and both follow from the definition, which is a sign that it is doing work rather than restating intuition.

The tools of this lesson are already useful, and they do not scale. Nothing here says what to do with an argument whose form nobody has named, and the parallel-form method needs a fresh flash of invention every time. To go further, forms must be written in a language precise enough to compute with, which means fixing a small set of connectives whose meaning never varies. That is the next lesson.

The previous lesson found that validity depends on form, and then had to describe forms in English, which is the language whose vagueness caused the problem in the first place.

"He will resign or the board will force him out, and the shares will fall" has two readings, and they are not equivalent: one says a disjunction and a fall both hold, the other says either he resigns or the board acts and the shares fall together. Ordinary punctuation does not separate them. Before any form can be tested mechanically, the forms have to be written in a notation where that ambiguity cannot arise. This lesson builds that notation for the part of logic that treats whole statements as unanalysed blocks, and fixes the symbols used for the rest of the subject.

Atoms

Start by deciding what will not be analysed. A simple statement, or atom, is one containing no other statement as a part: "the shares fell", "Titan has a nitrogen atmosphere", "the alloy contains nickel". Each is written as a capital letter, and which letter is a free choice, though a mnemonic one saves work later: $S$ for the shares, $N$ for the nickel.

A compound statement is built from simpler ones with a connective: "the shares fell and the bond yields rose" contains two statements. Propositional logic studies exactly the structure that compounding creates, and it deliberately sees nothing inside an atom. "Socrates is a man" is a single letter to it, with no visible parts, which is the limitation that eventually forces the eighth lesson.

Choosing the atoms is the first real decision in any translation. Take them too coarse and structure the argument depends on disappears; take them too fine and you invent structure the English does not have. The rule of thumb: an atom should contain no word from the connective list below.

The five connectives

Five symbols do all the work, and each has a fixed meaning that never varies with context.

Negation, $\neg P$, is read "not $P$", and it is true exactly when $P$ is false. English hides negation in many places: "it is not the case that", the prefix in "unhappy", the verb in "she denied it", and the quiet negation in "she failed to arrive".

Conjunction, $P\wedge Q$, is "$P$ and $Q$", true when both parts are true. It is not only carried by "and". "But", "however", "although", "yet", "while" and a plain semicolon are all conjunctions as far as truth is concerned. "She is qualified but inexperienced" is true in exactly the circumstances that "she is qualified and she is inexperienced" is true. The contrast that "but" conveys is real and it makes no difference to truth, so the notation drops it. That is the first of several deliberate losses.

Disjunction, $P\vee Q$, is "$P$ or $Q$", and it is inclusive: true when either part is true and also when both are. English sometimes means the exclusive version, "one or the other but not both", as in "the set menu comes with soup or salad". Logic fixes the inclusive reading as the meaning of $\vee$ and writes the exclusive one explicitly as $(P\vee Q)\wedge \neg (P\wedge Q)$ when it is wanted. Latin had two separate words, vel for the inclusive and aut for the exclusive, and the symbol $\vee$ is the first letter of vel.

The conditional, $P\to Q$, is "if $P$ then $Q$". $P$ is the antecedent and $Q$ the consequent. Its truth conditions are strange enough to deserve their own lesson, which is the fourth.

The biconditional, $P\leftrightarrow Q$, is "$P$ if and only if $Q$", true when the two sides have the same truth value. It is the standard form of a definition and of a mathematical criterion: a number is even if and only if it is divisible by two.

Truth-functionality, and what will not fit

Behind all five sits one restriction that decides what this language can and cannot say. A connective is truth-functional when the truth value of the compound depends on nothing but the truth values of its parts. Give me the value of $P$ and the value of $Q$ and I can compute $P\wedge Q$ without knowing what either says.

Plenty of English connectives fail this. "She resigned because the audit failed" cannot be evaluated from the two truth values alone: both parts can be true with the causal claim false, if she resigned for unrelated reasons. Causation is not a truth function, and neither is "before", since "he left before she arrived" and "she arrived before he left" can differ in truth while their parts do not change. Nor is "it is likely that", "the manager believes that", "it is obligatory that" or "it would have been the case that". Each has a whole branch of logic devoted to it, and none is here.

This exclusion is what makes the machinery of the next three lessons possible. Truth-functional connectives can be tabulated exhaustively, and tabulation is the whole method. The price is that any argument turning on causation, time, belief or obligation has that content flattened out of it in translation, and a valid formal argument may correspond to a bad English one for exactly that reason. Keeping track of what was thrown away is part of using the tool honestly.

Scope, brackets and the main connective

The ambiguity that opened this lesson is a question of scope: which connective governs which parts. Brackets settle it. $(P\vee Q)\wedge R$ says the disjunction and $R$ both hold; $P\vee (Q\wedge R)$ says either $P$ holds or the conjunction does. Those are different claims, and later lessons will show a case where one is true and the other false.

Every well-formed formula has one main connective, the one applied last when the formula was built and the one applied first when it is taken apart. Finding it is the first move in any analysis, and the procedure is mechanical: strip any outermost bracket pair, then the connective not enclosed in any remaining brackets is the main one. In $\neg (P\wedge Q)$ the main connective is the negation, so the formula denies a conjunction. In $\neg P\wedge Q$ it is the conjunction, so the formula asserts one thing and denies another. Those two are not equivalent, and mixing them up is the commonest translation error there is.

To reduce bracket clutter there is a precedence order: $\neg$ binds most tightly, then $\wedge$, then $\vee$, then $\to$, and $\leftrightarrow$ binds least. So $\neg P\wedge Q\to R$ means $((\neg P)\wedge Q)\to R$. Precedence is a convenience and never a defence: when a formula is hard to read, put the brackets in.

Example. Find the main connective of $\neg (P\to Q)\vee (R\wedge \neg S)$, and say what kind of statement it is.

There is no outermost bracket pair enclosing the whole formula, so scan for a connective outside all brackets. The first $\neg$ applies to $(P\to Q)$ only, and $\wedge$ and $\neg S$ sit inside the second bracket pair. The $\vee$ is the only connective outside every bracket, so it is the main connective and the formula is a disjunction. Its left disjunct denies a conditional and its right asserts a conjunction.

Now you. Find the main connective of $(P\vee Q)\to \neg (R\leftrightarrow S)$.

Translating

Translation is where care is repaid, and a few English constructions cause nearly all the trouble.

"Only if" is not "if". "You may vote only if you are registered" does not say registration gets you a vote; it says a vote requires registration. So "$P$ only if $Q$" is $P\to Q$, with the part after "only if" as the consequent, exactly opposite to the placement in "$P$ if $Q$", which is $Q\to P$. Combining the two gives the reason "if and only if" is a biconditional.

"Unless" means "if not". "The flight leaves unless the fog thickens" is $\neg F\to L$, and since that is equivalent to $L\vee F$, translating "unless" as $\vee$ is also correct. Readers argue about whether "unless" is exclusive; treat it as inclusive unless the sentence says otherwise, and note the choice.

"Neither $P$ nor $Q$" is $\neg P\wedge \neg Q$, both denied. "Not both $P$ and $Q$" is $\neg (P\wedge Q)$, which is weaker: it permits either one alone. The difference between those two formulas is a law with a name, and it arrives in the fifth lesson.

"Provided that", "given that" and "assuming that" all introduce an antecedent, so they behave like "if". A sufficient condition is an antecedent and a necessary condition is a consequent, which the fourth lesson makes precise.

Example. Translate: "The contract is valid unless it was signed under duress, but it is void if either party lacked capacity."

Atoms: $V$ for the contract being valid, $D$ for it being signed under duress, $C$ for either party lacking capacity. Take the clauses in turn. "Valid unless $D$" is "if not $D$ then valid", so $\neg D\to V$. "But" is a conjunction. "It is void if $C$" puts the antecedent second, so it is $C\to \neg V$, using $\neg V$ for void, since void and valid are contradictories here. The whole translation is

Note what the translation had to decide: that "void" is the negation of "valid" rather than a third state, and that "either party lacked capacity" is one atom rather than a disjunction over two parties. Both choices are defensible and both are choices, which is why translation is judgement rather than calculation.

Now you. Translate: "The alarm sounds only if the door is open or the glass is broken, and it does not sound now."

Two more habits worth forming

Negations of compounds repay slowing down. "It is not true that the fee is refundable and the deadline is fixed" is $\neg (R\wedge F)$, not $\neg R\wedge \neg F$. The English is denying a package, and denying a package leaves both individual claims open.

Scope over "and" inside a negation catches almost everyone, and so does the English habit of dropping repeated subjects. "The valve is neither open nor stuck" expands to two atoms with two negations, and "the valve is not open or stuck" is genuinely ambiguous in English between $\neg (O\vee S)$ and $\neg O\vee S$. When the source is ambiguous, the honest thing is to translate both and note that the argument may depend on which was meant.

Example. Translate "not both of the tanks are full" and "neither tank is full", and say how they differ.

With $A$ and $B$ for the two tanks being full, the first is $\neg (A\wedge B)$ and the second is $\neg A\wedge \neg B$. They differ in the case where exactly one tank is full: the first sentence is then true and the second false. So the second implies the first and not the other way round, which is the general relation between denying a conjunction and conjoining two denials.

Now you. Translate "the report is neither timely nor accurate" and "the report is not both timely and accurate", and give a situation that separates them.

What the language now has, and what it lacks

There is now a syntax: atoms, five connectives, brackets, a precedence order, and a translation practice with its known traps. Every formula built by those rules is well formed, and every well-formed formula has exactly one main connective and one unambiguous reading.

What is missing is any way to evaluate one. Nothing so far says whether $(A\to (D\vee G))\wedge \neg A$ can be true, or whether one formula follows from another. The connectives were chosen to be truth-functional precisely so that this can be answered by computation rather than by intuition, and the computation is a table with $2^n$ rows for $n$ atoms. That is the next lesson, and it makes validity decidable for everything this language can say.

The previous lesson built a language for writing forms down and gave no way at all to evaluate one.

That gap closes here, and it closes completely. Because every connective was chosen to be truth-functional, a formula's value depends on nothing but the values of its atoms, and there are only finitely many ways to assign those. Listing them all is the whole method. Validity, consistency and equivalence all become questions about a finished table, answerable by looking, and for a while that feels like the end of the subject rather than the third lesson of it.

A row is a possible situation

A valuation assigns true or false to every atom in a formula. With one atom there are two valuations, with two there are four, and in general $n$ atoms give $2^n$, since each atom doubles the count. A truth table is the list of all of them with the formula's value worked out in each.

The link to the first lesson is direct. Validity was defined as the impossibility of true premises with a false conclusion, "impossible" meaning across all possible situations. In propositional logic a possible situation is exactly a valuation, because the only thing a formula can see is which atoms are true. So the vague quantifier over situations becomes a finite list of rows, and a definition that looked philosophical becomes an inspection.

That is a real narrowing, worth saying out loud. A row where $P$ is "the alloy contains nickel" and $Q$ is "the alloy contains no nickel" is counted as possible, because the notation cannot see that they conflict. Propositional logic only knows about situations in the sense of assignments to letters, and any impossibility living inside the atoms is invisible to it.

The five tables

The connectives are defined by these tables and by nothing else. All the rest of the subject is consequences of them.

Four of the five columns match ordinary English closely enough to need no defence. Negation flips. A conjunction needs both. A disjunction needs at least one, and its bottom row is the only false one. A biconditional is true when the two sides agree, which is the top and bottom rows.

The conditional column is the odd one. It is false in exactly one row, the one where the antecedent is true and the consequent false, and it counts as true in both rows where the antecedent is false. That means "if the moon is made of cheese then Paris is in Spain" comes out true. There are reasons for this, and they take a lesson, which is the fourth. For now, take the column as given and notice its shape: a conditional is a promise that is broken only by a true antecedent with a false consequent.

Building a table

A compound formula is evaluated by working outward from the atoms, one column per subformula, ending with the main connective. The discipline is to give each column its own space rather than trying to do it in one's head.

Take $(P\wedge \neg Q)\wedge (\neg P\vee Q)$. Four rows, since there are two atoms.

The final column is false in every row. Notice how it happened: the left conjunct picks out exactly the row where $P$ is true and $Q$ false, and the right conjunct is false in exactly that row, so nothing survives. That is worth seeing rather than just recording, because it is the reason the formula is a contradiction rather than a fact about it.

Three kinds of formula

The final column of a table can come out three ways, and the three names are used constantly.

A tautology is true in every row. $P\vee \neg P$ is one, and so is $(P\to Q)\vee (Q\to P)$, which surprises people: whichever way the values fall, at least one of the two conditionals has a false antecedent or a true consequent, so at least one is true. A tautology says nothing about the world, since no situation can falsify it, and that emptiness is exactly why it is safe to assert anywhere.

A contradiction is false in every row, like the formula just tabulated, or the plain $P\wedge \neg P$.

A contingency is true in some rows and false in others, which is what almost every useful statement is. "It is raining" tells you something precisely because it rules out situations.

A formula is satisfiable when at least one row makes it true, so tautologies and contingencies are satisfiable and contradictions are not. A set of formulas is consistent when some single row makes them all true at once. Consistency is not the same as everything being individually satisfiable: $P$, $P\to Q$ and $\neg Q$ are each satisfiable on their own and no row makes all three true together.

Example. Classify $P\to (Q\to P)$.

Two atoms, four rows. When $P$ is true, the inner conditional $Q\to P$ has a true consequent, so it is true, and the whole conditional has a true consequent and is true. When $P$ is false, the whole conditional has a false antecedent, so it is true by the third and fourth rows of the conditional table. Every row comes out true, so it is a tautology. It is worth pausing on how little it says: a true statement is implied by anything at all.

Now you. Classify $(P\vee Q)\wedge (\neg P\wedge \neg Q)$.

The test for validity

Here is the payoff. To test an argument, tabulate every premise and the conclusion over the same rows, then look for a row where every premise is true and the conclusion is false. If there is one, the argument is invalid and that row is a counterexample, a fully specified situation you can describe out loud. If there is no such row, the argument is valid, with no cleverness required.

Take: "If the reactor is scrammed, the pumps run. Either the pumps are not running or the valve is open. The valve is not open. So the reactor is not scrammed." With $S$, $P$ and $V$ the argument is $S\to P$, $\neg P\vee V$, $\neg V$, therefore $\neg S$. Three atoms, so eight rows.

Scan the three premise columns for a row of all Ts. Only the last row qualifies, and its conclusion column is T. No row has true premises with a false conclusion, so the argument is valid. Note how thin the result is: seven of the eight rows were thrown out by the premises, and the verdict rests on one surviving row.

Example. Test: $P\to (Q\vee R)$, $\neg Q$, therefore $R$.

Look for a row making both premises true and $R$ false. Try $R$ false and $Q$ false, which satisfies the second premise. Then $Q\vee R$ is false, so the first premise demands that $P$ be false, and $P$ false makes it true. So the row $P$ false, $Q$ false, $R$ false has both premises true and the conclusion false. The argument is invalid, and the counterexample is concrete: nothing is on, the conditional holds vacuously, and $R$ never had to be true.

Now you. Test: $(P\wedge Q)\to R$, $\neg R$, $P$, therefore $\neg Q$.

Entailment, and a symbol for it

When no valuation makes a set of formulas $\Gamma$ true while making $\phi$ false, $\Gamma$ entails $\phi$, written

and read "$\Gamma$ entails $\phi$", or "$\phi$ is a semantic consequence of $\Gamma$". Validity of an argument is exactly entailment of its conclusion by its premises. With nothing on the left, $\models \phi$ says $\phi$ is a tautology.

The symbol matters because a second one arrives in the sixth lesson: $⊢$, for what can be derived by a fixed set of rules. One is about tables, the other about proofs, and the fact that they coincide is the deepest result in propositional logic rather than an obvious identity.

Two facts fall straight out of the definition and settle the puzzles from the first lesson. An inconsistent set entails everything, since it makes no row true and so has no row with true premises at all. And a tautology is entailed by anything, since no row makes it false.

The short cut

Eight rows are tedious and sixteen are worse, so in practice the table is almost never drawn in full. Instead, assume the argument is invalid and try to build the offending row directly. Set the conclusion false, then work through the premises forcing values as far as they will go. If you reach a contradiction on every branch, no such row exists and the argument is valid. If you complete a row without contradiction, that row is a counterexample.

That is what the last two exercises did, and the saving grows fast: the second exercise settled a three-atom argument in two lines instead of eight rows, and the same reasoning handles ten atoms without ever mentioning 1024.

The method needs care in one place. When a premise leaves a genuine choice, both branches must be tried before declaring validity. A disjunction with neither side forced is the usual case: $P\vee Q$ with nothing else known splits into $P$ true and $P$ false with $Q$ true, and abandoning one branch is how a counterexample gets missed.

Example. Test $P\vee Q$, $P\to R$, $Q\to R$, therefore $R$, by the short cut.

Set $R$ false. The second premise then forces $P$ false and the third forces $Q$ false, since a true antecedent with a false consequent would break them. But the first premise needs one of $P$ and $Q$ to be true, and both have just been forced false. Every branch closes, so no counterexample row exists and the argument is valid. Eight rows never had to be written, and the reasoning shows which premises did the work.

Now you. Test $P\to Q$, $R\to S$, $P\vee R$, therefore $Q\wedge S$.

What the table costs

The table method is complete, mechanical and guaranteed to terminate, which puts propositional logic in a rare position: its validity problem is decidable, and a procedure exists that answers every instance in finite time.

The trouble is the finite time. Rows double with each atom, so 10 atoms give 1024 rows, 20 give 1,048,576, and 30 give 1,073,741,824. At a million rows a second that last one takes about 18 minutes, and 60 atoms, still a small argument by the standards of a real legal document or circuit, would take roughly 36 years at a billion rows a second. Doubling defeats hardware improvements: buying a machine ten times faster buys about three more atoms.

There is a second complaint, and it is the one that shapes the rest of the subject. A completed table certifies that no counterexample exists without showing why the conclusion follows. It gives no argument you could present to somebody, no insight into which premise did the work, and no way to reuse a step in the next problem. It is a verdict rather than a proof.

The response to both complaints is the same: reason with the formulas instead of enumerating their rows. That needs rules for transforming formulas while preserving truth, which is the fifth lesson, and rules for deriving conclusions line by line, which is the sixth. Before either, one column of the table above still needs explaining, and the next lesson is about that column alone.

One column of the previous lesson's table was handed over without justification, and it is the column almost every argument in the world runs through.

The conditional is the connective of rules, laws, predictions, promises, contracts and proofs. It is also the only one whose truth table offends people on first sight, because it counts "if the moon is made of cheese then Paris is in Spain" as true. This lesson shows that the table is forced rather than chosen, sets out honestly what it fails to capture, and then works through the practical consequences: necessary and sufficient conditions, converse and contrapositive, and the two fallacies that account for most bad reasoning about evidence.

The row nobody disputes and the two that follow

Start from what is not controversial. "If you pass the exam, you get the certificate" is broken by exactly one situation: you passed and got nothing. Passing and receiving is the promise kept. So $P\to Q$ must be false when $P$ is true and $Q$ false, and true when both are true. Those two rows are fixed by the meaning of "if" in any reading.

The dispute is over the two rows where $P$ is false. You did not pass. Was the promise kept or broken? The natural answer is that it was neither, that the question does not arise. But the language of the second lesson has no third value, and every connective in it is a function from the values of the parts to a value for the whole. Something must go in those rows.

There are only four ways to fill two rows, so enumerate them and see which survives. Filling both with false gives a connective true only when $P$ and $Q$ are both true, which is $P\wedge Q$: asserting "if you pass you get the certificate" would then assert that you passed. Filling the false-true row with false and the false-false row with true gives the biconditional, so "if" would mean "if and only if", making "if it rains the match is cancelled" claim that nothing else could cancel it. Filling the false-true row with true and the false-false row with false gives a connective whose value is just $Q$, so the antecedent would be idle and "if $P$ then $Q$" would say no more than $Q$.

Each of the three is plainly wrong. The remaining option, true in both rows where the antecedent is false, is the material conditional, and it is the only truth-functional candidate left standing. A conditional with a false antecedent is called vacuously true, and the name is a fair description: nothing has been claimed, so nothing has been broken.

What the material conditional gets wrong

Being the only candidate does not make it a good model of English "if", and pretending otherwise is how logic gets a reputation for sophistry. Three consequences are genuinely uncomfortable, and all three are tautologies you can verify in four rows.

First, $\neg P\to (P\to Q)$: a false statement implies anything. Second, $Q\to (P\to Q)$: a true statement is implied by anything. Third, $(P\to Q)\vee (Q\to P)$: for any two statements whatever, one implies the other. Take "the reactor is scrammed" and "the price of tin is rising", and one of the two conditionals joining them is true, which no English speaker would accept.

The reason is that the material conditional records only a pattern of truth values, and English "if" claims a connection. Counterfactuals show the gap most sharply. "If this bridge had been built in steel, it would have survived" and "if this bridge had been built in steel, it would have collapsed anyway" have the same false antecedent, so both are vacuously true as material conditionals, while engineers can disagree about which is right for good reasons. Whole logics exist for that, and the honest position is that $\to$ is a deliberately crude tool: it is exactly right for the conditionals of mathematics and formal rules, and approximate for conditionals about causes, times and possibilities.

Necessary and sufficient

The vocabulary that goes with the conditional is worth getting exactly right, because it is used constantly in law, engineering and mathematics and confused just as often.

$P$ is a sufficient condition for $Q$ when $P\to Q$: having $P$ is enough for $Q$. $Q$ is a necessary condition for $P$ in the same situation: without $Q$ you cannot have $P$. A single conditional therefore states both facts at once, and which word you reach for depends only on which end you look from.

Being a square is sufficient for being a rectangle, and being a rectangle is necessary for being a square. Passing the medical is necessary for a pilot's licence and nowhere near sufficient. When a condition is both necessary and sufficient, the biconditional holds, and that is what a definition asserts: an integer is even if and only if it is divisible by two, which is two conditionals in one symbol.

Example. "A valid contract requires consideration." Which is consideration, necessary or sufficient, and what conditional does the sentence assert?

"Requires" marks a necessary condition, so with $V$ for validity and $C$ for consideration the sentence is $V\to C$: if the contract is valid, consideration was present. Equivalently, no consideration means no valid contract. It plainly does not say $C\to V$, since a contract can have consideration and fail for a dozen other reasons, and a lawyer who read it that way would be badly wrong.

Now you. "Only members may use the pool." Express it as a conditional, and say which condition is which.

Converse, contrapositive and inverse

Three formulas can be built from $P\to Q$ by swapping and negating, and exactly one of them is equivalent to it.

The converse is $Q\to P$, which is a different claim. The inverse is $\neg P\to \neg Q$, also different, and in fact the converse of the converse. The contrapositive is $\neg Q\to \neg P$, and it is equivalent to the original: check the four rows and the two columns match everywhere. The converse and the inverse are equivalent to each other and to neither of the other two.

The equivalence of a conditional with its contrapositive is a working tool rather than a curiosity. "If the sample contains chloride, the silver nitrate test goes cloudy" and "if the test stays clear, there is no chloride" are the same statement, and the second is often the easier one to use, since it is the one a negative test licenses. A whole proof technique is built on this and arrives in the thirteenth lesson.

The converse error is so common it has a name in every field. "All fraudulent accounts look smooth" does not give "all smooth accounts are fraudulent". "Every case of the disease shows this marker" does not give "everyone with the marker has the disease", and the gap between those two is the entire subject of diagnostic testing.

The two fallacies, seen in the table

The first lesson named affirming the consequent and denying the antecedent as invalid. The table now shows exactly why, and shows that they are the same mistake twice.

Affirming the consequent argues $P\to Q$, $Q$, therefore $P$. Look for a row with both premises true and the conclusion false: $P$ false and $Q$ true does it, since a false antecedent makes the conditional vacuously true and the second premise is satisfied. One row is all it takes.

Denying the antecedent argues $P\to Q$, $\neg P$, therefore $\neg Q$. The same row refutes it: $P$ false, $Q$ true makes both premises true and the conclusion false. The two fallacies are refuted by one valuation, which is a hint that they are the same error, namely reading $\to$ as $\leftrightarrow$. Both would be valid if the conditional really were a biconditional, and people commit them because ordinary conversation often does mean a biconditional. "If you tidy your room you can have ice cream" is normally understood to promise no ice cream otherwise, which is precisely the reading logic refuses.

Example. A test for a condition is positive in every case of the condition. A patient tests positive. What follows?

With $C$ for having the condition and $T$ for a positive test, the premise is $C\to T$ and the fact is $T$. That is affirming the consequent, and nothing follows about $C$. What would follow from a negative test is $\neg C$, by modus tollens, which is why a highly sensitive test is used to rule a condition out rather than in. Numbers make the point sharper: if the condition affects 1 in 1000 people and the test has a 5 per cent false positive rate, then among 100,000 people about 100 have the condition and test positive, while about 4995 of the rest test positive anyway, so a positive result is wrong roughly 98 times in 100.

Now you. "If the shipment cleared customs, the tracking page shows a customs event. The tracking page shows no customs event." What follows, and by which form?

Why this is hard for people

There is direct evidence about how badly untrained reasoners handle the conditional, and it is one of the most replicated results in psychology.

Peter Wason's selection task, from 1966, lays four cards on a table showing D, K, 3 and 7. Each card has a letter on one side and a number on the other. The rule is: if a card has a D on one side, it has a 3 on the other. Which cards must be turned over to find out whether the rule is broken?

The correct answer is D and 7. The rule is $D\to 3$, and only one combination breaks it, a D with a non-3 on the back. Turning D can reveal exactly that. Turning 7 can too, since a D behind the 7 is a D without a 3. Turning 3 is useless, because whatever is behind it, no rule is broken: the rule never said only D cards carry 3s, and thinking otherwise is affirming the consequent. Turning K is useless, because the rule says nothing about non-D cards.

Fewer than one in ten participants get this right. Most turn D alone, or D and 3, choosing the card that could confirm the rule rather than the card that could break it. The interesting part is what fixes it: Griggs and Cox in 1982 posed the same task as a bar checking that anyone drinking beer is over 18, with cards reading "beer", "cola", "22" and "16". About three quarters of participants then chose correctly, which is "beer" and "16", the exact same logical form. The structure was never the problem; the abstraction was.

Example. In the drinking version, why is the "22" card the one that matches the useless "3" card?

The rule is: drinking beer implies over 18. The "22" card is a person over 18, so it satisfies the consequent, and whatever they are drinking the rule stands, since over-18s may drink anything. Turning it can produce no violation, which is exactly the position of the "3" card. Checking it is affirming the consequent dressed as diligence.

Now you. The rule is "if a package is marked fragile, it must be shipped by air". Four packages are on the bench: one marked fragile, one not marked, one already loaded on a plane, one already loaded on a truck. Which two must be checked?

Where this leaves the language

The conditional is now fully understood as a truth function, with its uses and its known distortions. The same four rows license modus ponens and modus tollens, refute their two impostors, and turn "necessary", "sufficient" and "only" into placements of an arrow.

The next question is what else the tables license. A conditional and its contrapositive have identical columns, which means either can replace the other anywhere without changing any truth value, and that is a far more powerful observation than it looks. If formulas with identical columns are interchangeable, logic can be done by substitution and calculation rather than by row-counting, and long formulas can be pushed into standard shapes. That is the next lesson.

A conditional and its contrapositive came out with identical truth table columns in the previous lesson, and that observation is worth far more than the fact itself.

If two formulas are true in exactly the same rows, then no argument, no matter how long, can tell them apart, and either may be swapped for the other anywhere it appears. That licenses doing logic the way algebra is done: by rewriting, in steps, each step justified by a law. This lesson sets out the laws, shows how any formula can be pushed into one of two standard shapes, and finishes with the surprising fact that one connective is enough to express everything the language can say.

Equivalence, and why substitution is safe

Two formulas are logically equivalent, written $\phi \equiv \psi$, when they have the same truth value under every valuation. Equivalently, $\phi \leftrightarrow \psi$ is a tautology, since a biconditional is true exactly when its sides agree. The two definitions are the same statement read from the table and from the formula.

Equivalence licenses substitution: replacing any subformula by an equivalent one leaves the value of the whole unchanged, in every row. This follows from truth-functionality and nothing else. A connective sees only the truth values of its parts, so if a part is swapped for something with the same value in every row, no connective above it can notice. Whole chains of rewriting are therefore safe, which is the property that makes calculation possible.

Note carefully what equivalence is not. It is not sameness of meaning: $2+2=4$ and Fermat's last theorem are both tautologies of arithmetic and nobody would call them the same claim. Within propositional logic, where the only thing visible is a column of Ts and Fs, equivalence is as fine a distinction as the machinery can draw, and the loss is the same one the second lesson noted when "but" became $\wedge$.

The laws

Ten laws do nearly all the work. Each can be checked in four or eight rows, and doing that once for each is the best hour available in this subject.

Two of these deserve a second look. De Morgan is the law behind the second lesson's warning about "neither" and "not both": denying a conjunction gives a disjunction of denials, not a conjunction of them. It generalises the informal rule for negating English, that a negation pushed inward flips "and" to "or" and back.

Distribution is the one where the analogy with school algebra fails. In arithmetic, multiplication distributes over addition and addition does not distribute over multiplication. In logic both directions hold, so $P\vee (Q\wedge R)\equiv (P\vee Q)\wedge (P\vee R)$ as well. That symmetry is what makes it possible to convert freely between the two normal forms below.

Two more equivalences follow from the laws and are used constantly: $\neg (P\to Q)\equiv P\wedge \neg Q$, which says a conditional is denied by asserting its antecedent and denying its consequent, and $P\to (Q\to R)\equiv (P\wedge Q)\to R$, called exportation, which is how a rule with two conditions gets split or joined.

Pushing negations inward

The first thing to do with any formula is tidy it, and there is a standard destination for the tidying. A formula is in negation normal form when negations apply to atoms and to nothing else, so no $\neg$ sits in front of a bracket.

Getting there is a fixed procedure with no choices in it. Replace every $\leftrightarrow$ using the biconditional law, then every $\to$ using the implication law, then push each remaining negation inward with De Morgan, cancelling double negations as they appear. The procedure always terminates, because each De Morgan step moves a negation strictly closer to an atom and there are only finitely many places left to go.

Example. Simplify $\neg (P\wedge (Q\vee \neg R))$ until no negation applies to anything but an atom.

De Morgan on the outer negation gives $\neg P\vee \neg (Q\vee \neg R)$. De Morgan again on the second disjunct gives $\neg P\vee (\neg Q\wedge \neg \neg R)$, and double negation finishes it as

Three steps, each one law, and the result is in negation normal form.

Now you. Bring $\neg (P\to (Q\wedge R))$ to negation normal form.

Two standard shapes

Rewriting is more useful when it has a destination. Two shapes are standard.

A formula is in disjunctive normal form, or DNF, when it is a disjunction of conjunctions of literals, a literal being an atom or its negation. $(P\wedge \neg Q)\vee (Q\wedge R)\vee \neg P$ is in DNF. It is in conjunctive normal form, or CNF, when it is a conjunction of disjunctions of literals, and each of those disjunctions is called a clause.

The two shapes answer different questions at a glance. A DNF is satisfiable exactly when one of its conjunctions is free of an atom together with that atom's negation, so satisfiability is read off by inspection. A CNF is a tautology exactly when every clause contains some atom alongside its negation, so being a tautology is read off by inspection. Neither shape makes both questions easy, which is a hint about how hard the underlying problems are.

Reading a normal form off the table

Every formula has both forms, and no ingenuity is needed to find them, because the truth table hands them over directly.

For DNF, take each row where the formula is true and write the conjunction of literals describing that row, with an atom that is true appearing plain and one that is false appearing negated. Each such conjunction is true in its own row and false in every other, so their disjunction is true in exactly the rows the formula is. For CNF, work from the false rows instead, writing for each one the clause that rules it out by negating every literal of the row. Each clause is false only in its own row, so the conjunction is false in exactly the rows the formula is.

A formula true in no row has an empty DNF, and one true in every row has an empty CNF, which is the sensible boundary case rather than a defect.

Example. Put $(P\to Q)\wedge (Q\to R)$ into disjunctive normal form.

Its table has eight rows and the formula is true in four of them: all three atoms false; $P$ and $Q$ false with $R$ true; $P$ false with $Q$ and $R$ true; and all three true. Writing each row as a conjunction gives

which is correct and clumsy. The first two rows agree except on $R$, and $R$ is true in one and false in the other, so together they say $\neg P\wedge \neg Q$ whatever $R$ does. The last two agree except on $P$, so together they say $Q\wedge R$. The formula reduces to

and that pairing-off of rows that differ in one atom is exactly the simplification that circuit designers do with Karnaugh maps.

Now you. Put $P\leftrightarrow Q$ into disjunctive normal form.

One connective is enough

A set of connectives is functionally complete when every truth function can be written using only those. Since every formula has a DNF, and a DNF uses only $\neg$, $\wedge$ and $\vee$, that set is complete: the two-line argument is the whole proof, and it also covers every truth function of any number of arguments, because the DNF construction never cared how many atoms there were.

The set shrinks. De Morgan turns $P\vee Q$ into $\neg (\neg P\wedge \neg Q)$, so $\vee$ can go and $\{\neg ,\wedge \}$ is complete. The implication law turns $\neg P\vee Q$ into $P\to Q$, so $\{\neg ,\to \}$ is complete too.

It shrinks to one. Write $P\uparrow Q$ for "not both", the connective now called NAND. Then $\neg P$ is $P\uparrow P$, and $P\wedge Q$ is $(P\uparrow Q)\uparrow (P\uparrow Q)$, and with negation and conjunction available everything else follows. Henry Sheffer published this in 1913, and Charles Sanders Peirce had found it in 1880 in work that stayed unpublished until 1933. Its dual, NOR, works the same way, and of the sixteen binary truth functions those two are the only ones that are complete on their own. Emil Post settled the general question in 1921, classifying exactly which sets are complete.

This is not a curiosity. It is why NAND gates are the cheapest way to build hardware: one gate type, repeated, can compute any Boolean function, and integrated circuits are built out of exactly that repetition. It is also why flash memory is called NAND flash, after the gate arrangement of its cells.

Example. Express $P\vee Q$ using only $\uparrow$.

By De Morgan, $P\vee Q\equiv \neg (\neg P\wedge \neg Q)$, and "not both" is what $\uparrow$ already means, so $\neg (\neg P\wedge \neg Q)$ is $\neg P\uparrow \neg Q$. Substituting the NAND form of each negation gives

Three gates, and a check on the row where both are false confirms it: each inner NAND gives true, and true NAND true is false, which is what $P\vee Q$ should be.

Now you. How many of the sixteen binary truth functions are functionally complete on their own?

Where calculation runs out

Normal forms are the input to real machinery. Satisfiability of a CNF formula, the SAT problem, was the first problem shown NP-complete, by Stephen Cook in 1971 and independently by Leonid Levin, so every problem in NP can be encoded as a CNF and solved by a SAT solver. Modern solvers handle industrial instances with millions of clauses, and they are used to verify processor designs and to plan schedules, all of it downstream of the conversion in this lesson.

The honest limit is that conversion itself can explode. Distributing to turn a DNF into a CNF can square the number of clauses at each step, and formulas exist whose smallest CNF is exponentially larger than the original. The standard fix, Tseytin's transformation of 1970, introduces a new atom for each subformula and produces a CNF of linear size that is satisfiable exactly when the original is, which is enough for a solver even though it is not equivalent to the original.

And the deeper limit is unchanged from the previous lesson. Everything here still rests on columns of a table, whether or not the table is written out. Nothing yet lets you argue from premises to a conclusion in steps that a reader could follow and check. That is what the next lesson builds, and the equivalences here become the justification for its rules.

A truth table certifies that no counterexample exists and gives no account of why the conclusion follows, which is the difference between a verdict and a proof.

There is a second reason to want something better, and it is arithmetic: the previous lessons' method doubles in size with every atom, so an argument with thirty atoms is a billion rows. This lesson replaces enumeration with derivation. A derivation is a numbered list of formulas, each one either a premise or the result of applying a stated rule to earlier lines, ending at the conclusion. Nobody has to trust the writer, because every line names what it came from, and checking a derivation is mechanical even when finding it was not.

The system built here is natural deduction, designed by Gerhard Gentzen in 1934 with the explicit aim of matching how mathematicians actually argue. Its organising idea is that each connective gets exactly two rules: one to introduce it and one to eliminate it.

The shape of a derivation

A derivation is written in three columns: the line number, the formula, and the justification, which names the earlier lines used and the rule applied. Premises are justified by the word "premise" and by nothing else.

Here is the smallest interesting one, the chain from the first lesson. From $P\to Q$, $Q\to R$ and $P$, derive $R$.

Two things are worth noticing before any rule is stated. Each new line is a formula that must be true whenever the lines it cites are true, which is the only property a rule needs. And the derivation is checkable line by line without ever considering the argument as a whole, which is exactly what a table cannot offer.

When the premises $\Gamma$ yield $\phi$ by such a derivation, write $\Gamma ⊢\phi$, read "$\Gamma$ proves $\phi$". Keep it firmly apart from $\Gamma \models \phi$ from the third lesson, which was about rows of a table. One is a claim about what can be written down with these rules, the other about what is true in every valuation, and the relation between them is the subject of the end of the next lesson.

Rules for conjunction

Conjunction is the easiest connective and shows the pattern.

Conjunction introduction ($\wedge$I): from $\phi$ and $\psi$ on any two earlier lines, write $\phi \wedge \psi$. Conjunction elimination ($\wedge$E): from $\phi \wedge \psi$, write either $\phi$ or $\psi$.

Both are justified by the table. The introduction rule is sound because the only row where a conjunction is false is one where a conjunct is false, so if both conjuncts are true on their lines, the conjunction cannot be false. The elimination rule is sound because a true conjunction has both parts true.

That justification is the pattern for every rule below, and it is why the system is not a set of conventions. A rule is admitted only if it can never take you from true lines to a false one, and the truth tables are the court of appeal.

Rules for the conditional

Conditional elimination ($\to$E) is modus ponens: from $\phi \to \psi$ and $\phi$, write $\psi$. It is sound because the only row where a conditional is true with its antecedent true has the consequent true as well, which is a restatement of the single false row of the conditional table.

There is no introduction rule here yet. To write a conditional you must be able to suppose its antecedent, and supposing needs machinery that the next lesson supplies. Until then the system can take conditionals apart and cannot build them, which is a real gap and worth feeling rather than patching.

Three further rules about conditionals are derived: each can be reconstructed from the basic ones, and each is used often enough to be worth naming. Modus tollens (MT): from $\phi \to \psi$ and $\neg \psi$, write $\neg \phi$. Hypothetical syllogism (HS): from $\phi \to \psi$ and $\psi \to \chi$, write $\phi \to \chi$. Disjunctive syllogism (DS): from $\phi \vee \psi$ and $\neg \phi$, write $\psi$.

Calling them derived matters for a reason that will return in the next lesson. A small set of basic rules is easier to prove things about, and a large set is easier to work with, so systems keep the basic set minimal and then license the convenient ones once. Nothing is lost either way.

Example. Derive $R$ from the premises $(P\wedge Q)\to R$, $P$, $S\to Q$ and $S$.

The conclusion is the consequent of the first premise, so the target is its antecedent, $P\wedge Q$. $P$ is already given, and $Q$ is one step from the last two premises.

The strategy generalises: look at what the conclusion is a part of, and work backwards to what would deliver it. Derivations are found from both ends and written forwards.

Now you. Derive $D$ from $A\to B$, $B\to C$, $\neg C$ and $A\vee D$.

Rules for disjunction

Disjunction introduction ($\vee$I): from $\phi$, write $\phi \vee \psi$ for any $\psi$ at all. This looks like cheating. From "the sample is copper" it licenses "the sample is copper or the moon is hollow", which no sensible person would say.

It is nevertheless sound, and the table shows why immediately: a disjunction is true whenever either side is true, so a true line cannot yield a false disjunction. What offends is not the truth of the conclusion but its uselessness, and logic guarantees only truth preservation. The rule earns its place because a disjunction is the input to disjunctive syllogism and to argument by cases, so manufacturing one deliberately is often the step that makes a proof go through.

Elimination for disjunction is the hard one, because knowing $\phi \vee \psi$ tells you almost nothing on its own. The honest rule is argument by cases: show that the conclusion follows from $\phi$ and also from $\psi$. That needs suppositions again, so like conditional introduction it waits for the next lesson. Disjunctive syllogism is the poor relation available in the meantime, and it works only when one disjunct can be ruled out.

Rules for negation and the biconditional

Double negation elimination ($\neg \neg$E): from $\neg \neg \phi$, write $\phi$. Its converse, introducing a double negation, is equally sound, and both follow from the one-line table for $\neg \neg P$.

Introducing a negation properly means proving that an assumption leads to disaster, which again waits for the next lesson. So negation, like the conditional and the disjunction, currently has an elimination rule and no introduction rule, and the pattern of what is missing is now unmistakable.

The biconditional is handled by trading it for two conditionals. Biconditional elimination ($\leftrightarrow$E): from $\phi \leftrightarrow \psi$, write $\phi \to \psi$, or write $\psi \to \phi$. Biconditional introduction ($\leftrightarrow$I): from $\phi \to \psi$ and $\psi \to \phi$, write $\phi \leftrightarrow \psi$. This one is available now because it does not need a supposition, only two conditionals already in hand, though in practice those conditionals will have come from the next lesson's machinery.

Example. Derive $\neg B$ from $(A\wedge B)\to C$, $A$ and $\neg C$.

Modus tollens on the first and third premises gives the negation of the antecedent, and the rest is reading what that negation says.

Lines 5 and 6 use equivalences from the previous lesson as rewriting steps, which is legitimate because equivalent formulas are interchangeable everywhere. Many textbooks list those equivalences among the rules for exactly this reason, and the derivation is shorter for it.

Now you. Derive $Q\wedge S$ from $P\to Q$, $R\to S$ and $P\wedge R$.

Finding a derivation

The rules say what may be written; they do not say what to write, and that is a genuine difficulty rather than a lack of practice. Three habits cover most cases.

Work backwards from the conclusion. If it is a conjunction, plan to get both halves and use $\wedge$I. If it is an atom sitting as the consequent of a premise, plan to get that premise's antecedent. If it appears as a disjunct, plan to eliminate the other disjunct.

Take every premise apart as far as it goes. Conjunctions should be split immediately, biconditionals turned into their two conditionals, and double negations removed, because a formula buried inside a compound cannot be used.

Watch for a negation among the premises. It is almost always there to fire modus tollens or disjunctive syllogism, and spotting which premise it is aimed at usually unlocks the problem.

Example. Derive $S$ from $P\leftrightarrow Q$, $P\vee R$, $\neg R$ and $Q\to S$.

$S$ is the consequent of the fourth premise, so the target is $Q$. $Q$ is the right-hand side of the biconditional, so it will come from $P$, and $P$ comes from the second and third premises.

Disjunctive syllogism at line 5 works with the negated disjunct on the right, which is fine: the rule cares that one disjunct is denied, not which.

Now you. Derive $C$ from $A\vee B$, $\neg A$, $B\leftrightarrow D$ and $D\to C$.

What the system cannot yet do

Count the gaps. Conjunction has both rules. The biconditional has both. The conditional, the disjunction and the negation each have an elimination rule and no way to be introduced, apart from the disjunction's near-useless one.

The consequence is severe. This system cannot derive $P\to P$, the most obvious tautology there is, because with no premises there is nothing to eliminate and no way to build an arrow. It cannot prove any tautology at all from no premises. It cannot use a disjunction except by killing one side. Whatever else it is, it is not complete.

Every one of those gaps has the same cause. Building a conditional requires reasoning under a supposition you do not believe; building a negation requires assuming something in order to wreck it; using a disjunction requires taking each case in turn as a temporary assumption. Suppositions are the missing machinery, and they need a bookkeeping discipline, since a formula proved under an assumption must not escape and be used as though it had been proved outright. That discipline, and the two most important proof techniques in mathematics that come out of it, are the next lesson.

The previous lesson ended with a system that could take conditionals, disjunctions and negations apart and had no way to build any of them, so it could not even derive $P\to P$.

Everything missing has one cause. To prove a conditional you must reason from its antecedent without believing it. To prove a negation you must assume the thing you are denying and watch it fail. To use a disjunction you must take each case in turn. All three are suppositions, and a supposition is dangerous: whatever is proved under it is proved only under it, and letting such a line escape would let anything be proved from nothing. The bookkeeping that keeps suppositions in their place is what this lesson adds, and with it the system becomes complete.

Suppositions and discharge

A subproof begins with an assumption, made freely and with no justification, and runs until it is closed. Lines inside it are written shifted to the right, and here they carry a bar. When the subproof is closed, the assumption is discharged: it is no longer in force, and the conclusion drawn from it survives only in a form that mentions it explicitly.

The scope rule is absolute. Once a subproof is closed, none of its lines may be cited again, and only the conclusion the closing rule produces remains available. A line proved under an assumption depends on that assumption, and dragging it out into the main proof would be exactly the error of treating a supposition as a fact.

Everything else stays as before. Lines are numbered, each carries its justification, and a checker verifies the derivation without needing to know how it was found.

Conditional proof

Conditional introduction ($\to$I): assume $\phi$, derive $\psi$, close the subproof, and write $\phi \to \psi$, citing the range of lines.

That is what a mathematician means by "suppose $x$ is even" at the start of a proof, and it is why the technique is called conditional proof. Its soundness is the conditional's table read from the other side: the conditional can only fail when the antecedent is true and the consequent false, and the subproof shows that if the antecedent holds the consequent follows, so that row is unreachable.

From $P\to Q$ and $Q\to R$, derive $P\to R$, which is hypothetical syllogism proved rather than assumed.

Line 6 is the first line in the whole subject that depends on no assumption beyond the premises, having been built out of lines that did. Note also that $P$, $Q$ and $R$ never had to be true: the derivation shows what would follow if $P$ were.

Subproofs nest, which is how a conditional with a conditional inside it gets proved. From no premises at all, derive $P\to (Q\to (P\wedge Q))$.

Line 3 cites line 1, which is legitimate because the outer subproof is still open there. The reverse never is: after line 5 nothing may cite lines 1 to 4.

Example. Derive $P\to P$ from no premises.

Two lines, and the subproof does no work at all: assume $P$, and $P$ is immediately available, so the conditional follows. The tautology that defeated the previous lesson's system falls out the moment assumptions are allowed.

Now you. Derive $P\to (Q\to R)$ from the single premise $(P\wedge Q)\to R$.

Reductio ad absurdum

Negation introduction ($\neg$I): assume $\phi$, derive a contradiction, close the subproof, and write $\neg \phi$. A contradiction here means any formula together with its negation, or the symbol $\perp$ used to mark that they have both appeared.

The reasoning is that a set of true statements cannot contain a contradiction, so if adding $\phi$ produced one, $\phi$ was not true. This is reductio ad absurdum, in use since Euclid, and the twelfth lesson of Mathematical Foundations used it to show that no fraction squares to 2.

From $P\to Q$ and $P\to \neg Q$, derive $\neg P$.

The mirror-image rule is the one that makes the system classical. Indirect proof, or negation elimination: assume $\neg \phi$, derive a contradiction, and conclude $\phi$. Strictly this is $\neg$I followed by double negation elimination, and it is worth naming separately because it is the standard way to prove something positive that resists a direct attack.

One further rule follows from contradiction and is worth stating because it startles people: from $\perp$, anything at all may be inferred. This is ex falso quodlibet, and it is the derivation-level version of the third lesson's result that an inconsistent set entails everything. The system is not being reckless; it is recording that once your premises contradict each other, they have stopped constraining anything.

Example. Derive $\neg Q$ from $\neg (P\wedge Q)$ and $P$.

The shape is worth memorising, since it is how nearly every negative conclusion is reached: assume the positive version, build the thing that was denied, and collect the contradiction.

Now you. Derive $\neg P$ from $P\to (Q\wedge \neg Q)$.

Argument by cases

Disjunction elimination ($\vee$E): given $\phi \vee \psi$, if a subproof assuming $\phi$ reaches $\chi$ and another assuming $\psi$ also reaches $\chi$, then $\chi$ follows.

This is the rule the previous lesson could not state, and it is the one that makes a disjunction useful rather than merely true. Its soundness is direct: any row making the disjunction true makes at least one disjunct true, and either way $\chi$ comes out true.

From $P\vee Q$, $P\to R$ and $Q\to R$, derive $R$.

Everyday reasoning uses this constantly without naming it. A doctor who says the pain is either a strain or a stress fracture, and that either way the treatment is rest, has argued by cases, and the conclusion holds without ever settling which case is real.

Proving what looks unprovable

With assumptions available, tautologies can be derived from no premises whatever, and the case worth working through is the law of excluded middle, $P\vee \neg P$, since there is nothing to start from and no obvious first move.

The despised disjunction introduction of the previous lesson does the work twice, at lines 3 and 6, which is what it is for. And line 9 is where the system commits itself: intuitionistic logic, developed by Brouwer and formalised by Heyting around 1930, keeps every other rule here and rejects double negation elimination, with the result that $P\vee \neg P$ is not provable in it. That is not a fringe position, since it corresponds to demanding a construction rather than a mere absence of contradiction, and it is the logic underlying proof assistants. Classical logic, used throughout this course, accepts line 9.

Example. Derive $(P\vee Q)\wedge (P\vee R)$ from $P\vee (Q\wedge R)$.

Argue by cases on the premise. If $P$, then $P\vee Q$ and $P\vee R$ both follow by disjunction introduction, so the conjunction follows. If $Q\wedge R$, then $Q$ gives $P\vee Q$ and $R$ gives $P\vee R$, so the conjunction follows again. Both cases reach the same formula, so disjunction elimination delivers it. That is the distribution law of the fifth lesson, proved rather than tabulated, and the proof works for reasons a reader can follow, which the table never gave.

Now you. Show, in outline, how to derive $\neg P\vee \neg Q$ from $\neg (P\wedge Q)$.

Soundness and completeness

There are now two relations between premises and conclusion. $\Gamma \models \phi$ says no valuation makes the premises true and the conclusion false. $\Gamma ⊢\phi$ says a derivation exists. One is about tables, the other about writing lines on a page, and there is no reason in advance for them to agree.

They agree exactly, and the two halves have names.

Soundness: if $\Gamma ⊢\phi$ then $\Gamma \models \phi$. Every derivable conclusion is genuinely entailed. The proof is an induction on the length of the derivation, and the work is the check already done for each rule as it was introduced: no rule takes you from true lines to a false one, so nothing false can be reached. Soundness is what makes a derivation worth anything, since without it the rules could prove nonsense.

Completeness: if $\Gamma \models \phi$ then $\Gamma ⊢\phi$. Every valid argument has a derivation. This one is not obvious at all, since it says that a fixed handful of rules suffices for every valid argument in the language, including ones nobody has thought of. Emil Post established it for propositional logic in 1921, and Gödel proved the far harder version for predicate logic in 1929, which the eleventh lesson returns to.

Together they say $⊢$ and $\models$ pick out the same pairs, so the semantic notion of validity and the syntactic notion of provability coincide. That licenses the practical habit of using whichever is easier: a countermodel to show invalidity, a derivation to show validity, and no worry that the two methods might disagree.

Propositional logic is therefore finished, and its limits are exact: sound, complete, and decidable by a table that is exponentially large. What it cannot do is see inside an atom. "All men are mortal, Socrates is a man, so Socrates is mortal" is three unrelated letters to it, and the most famous valid argument in the subject comes out invalid. Fixing that means breaking sentences open, and it is the next lesson.

The most famous valid argument in the subject comes out invalid in the system built so far, and that is not a small defect.

"All men are mortal. Socrates is a man. Therefore Socrates is mortal." Propositional logic sees three sentences with no connective in any of them, so it assigns three unrelated letters and finds a valuation making the first two true and the third false. The verdict is invalid, and it is wrong. The failure is not in the rules of the previous lessons but in the language: the form that makes the argument work lies inside the sentences, where atoms have no parts to look at. This lesson opens them up, and the price is a much richer notation that will take the next four lessons to pay off.

Inside an atomic sentence

Split a simple sentence into what it is about and what it says. "Socrates is a man" mentions one individual and applies one property. Write individuals with lower-case letters near the start of the alphabet, called names or constants: $s$ for Socrates, $a$ for the alloy. Write properties with capital letters, called predicates: $M$ for being a man, $F$ for being mortal.

An atomic formula is a predicate followed by the right number of names, so "Socrates is a man" is $Ms$ and "Socrates is mortal" is $Fs$. The number a predicate takes is fixed, and the choice of letter is arbitrary, though a mnemonic saves effort later.

Predicates of more than one place are what make the notation powerful, and they arrive in the next lesson: $Lab$ for "$a$ loves $b$", $Gab$ for "$a$ is greater than $b$". For now everything is one-place, which is enough for the syllogism and for most of the traps.

Note what has already changed. Propositional logic could see that "Socrates is a man" and "Plato is a man" were different sentences and nothing else; the notation now shows they share a predicate, and that shared structure is what an argument about all men can grab hold of.

Variables and the domain

To say something about every individual rather than a named one, a placeholder is needed. Variables are lower-case letters from the end of the alphabet, $x$, $y$, $z$, and $Fx$ on its own is not a statement: it has no truth value until something fills $x$.

Filling it is what the quantifiers do. The universal quantifier $\forall x$ says the formula after it holds for every individual, and the existential quantifier $\exists x$ says it holds for at least one. So $\forall xFx$ says everything is mortal and $\exists xFx$ says something is.

Every quantified statement is implicitly about some collection, the domain of discourse, and the same formula changes truth value as the domain changes. $\forall xFx$ is false if the domain is all things and true if the domain is all people. Fixing the domain is part of stating the problem, and forgetting to fix it is a standard source of fake disagreements. When the domain is everything, restrictions must be written into the formula itself, which is what the next section is about.

"At least one" is the exact reading of $\exists$. It does not mean exactly one, and it does not suggest that not all. $\exists xFx$ is true when everything is $F$, in the same way that $P\vee Q$ is true when both hold, and for the same reason: logic takes the weaker reading and makes you write the stronger one out.

The two translations

Nearly everything in this lesson rests on two patterns, and getting them the wrong way round is the single most common error in the subject.

All $F$ are $G$ is $\forall x(Fx\to Gx)$: take anything at all, and if it is $F$ then it is $G$. Some $F$ are $G$ is $\exists x(Fx\wedge Gx)$: there is something that is both.

The connectives cannot be swapped, and it pays to see exactly what goes wrong. Writing $\forall x(Fx\wedge Gx)$ for "all ravens are black" claims that everything in the domain is a raven and black, which makes a claim about ravens into a claim about the universe. Writing $\exists x(Fx\to Gx)$ for "some ravens are black" is worse in a subtler way: a conditional is true whenever its antecedent is false, so if the domain contains a single non-raven the formula is true, whatever colour ravens are. Neither error changes the sentence slightly; both destroy it.

The reason for the asymmetry is that $\forall$ needs to let irrelevant things through, and the conditional does that by being vacuously true of them, while $\exists$ needs to pin down one thing that satisfies both conditions, and only a conjunction does that.

Example. Translate, with the domain being everything: "Every alloy containing nickel is magnetic" and "some alloys containing nickel are not magnetic".

With $Ax$ for being an alloy containing nickel and $Mx$ for being magnetic, the first is $\forall x(Ax\to Mx)$ and the second is $\exists x(Ax\wedge \neg Mx)$. Note that the second is the exact denial of the first: it says there is a counterexample, which is precisely what refuting a universal claim requires, and austenitic stainless steels are that counterexample in the real world.

Now you. Translate "no reptile is warm-blooded" and "some reptiles are venomous".

The four categorical forms

Aristotle worked with four sentence forms, and they are still the best drill for translation. They are labelled with vowels from the Latin affirmo and nego.

A and O are exact denials of each other, and so are E and I. That is the whole content of the traditional square of opposition, minus the parts that depend on the assumption discussed below. Recognising which of the four an English sentence is saying is most of the work of translating it, and the misleading English is worth watching: "all that glitters is not gold" is an E claim in intent and an A claim with a negation in form, and only context resolves it.

Now the syllogism. "All men are mortal. Socrates is a man. So Socrates is mortal" becomes $\forall x(Mx\to Fx)$, $Ms$, therefore $Fs$, and the validity is visible: the universal premise applies to Socrates in particular, giving $Ms\to Fs$, and modus ponens finishes it. The eleventh lesson makes that instantiation an official rule.

Existential import, and a count

Aristotle's system assumes that the terms in a syllogism are not empty: talk of ravens presupposes that ravens exist. Modern logic drops that assumption, so $\forall x(Fx\to Gx)$ comes out true when nothing is $F$ at all. "Every unicorn in this room is on fire" is true, vacuously, in a room with no unicorns.

This is not a quibble, and the difference can be counted. A categorical syllogism has three terms and two premises, each premise and the conclusion being one of the four forms, arranged in one of four figures, which gives $4\times 4\times 4\times 4=256$ possible forms. Under modern semantics, exactly 15 are valid. Under Aristotle's assumption that every term is non-empty, 24 are, the extra 9 being exactly those that draw a "some" conclusion from two universal premises.

The most useful of the nine is easy to see: from "all $F$ are $G$" and "all $G$ are $H$" it concludes "some $F$ is $H$". If there are no $F$s, both premises hold vacuously and the conclusion is false, so the inference needs the extra assumption. Modern logic makes you state it, writing $\exists xFx$ as an extra premise when the argument depends on it, which is the honest arrangement: the assumption is often true and it should be visible.

Example. Is "all trespassers will be prosecuted, and nobody has trespassed, therefore somebody will be prosecuted" valid?

No. The first premise is $\forall x(Tx\to Px)$ and the second is $\neg \exists xTx$. In a domain where nothing is a trespasser, the first premise is vacuously true, the second is true, and $\exists xPx$ can be false. The premises are consistent and the conclusion fails, which is exactly the situation Aristotle's assumption rules out by fiat and modern logic allows.

Now you. Under modern semantics, is "all $F$ are $G$, all $G$ are $H$, therefore some $F$ is $H$" valid, and what single premise would make it so?

Scope, free and bound

A quantifier governs a stretch of formula, its scope, marked by brackets exactly as in propositional logic. In $\forall x(Fx\to Gx)$ the scope is the whole conditional. In $\forall xFx\to Gx$ it is $Fx$ alone, and the $x$ in $Gx$ is left dangling.

An occurrence of a variable inside the scope of a quantifier using that variable is bound; one that is not is free. A formula with a free variable is not a statement and has no truth value, the way $x>3$ has none until $x$ is fixed. A formula with no free variables is a sentence, and only sentences are true or false. Checking that a translation has no free variables is the fastest error check there is, and it catches the misplaced bracket above immediately.

Placing the negation is the other half of scope. $\neg \forall xFx$ says not everything is $F$; $\forall x\neg Fx$ says everything fails to be $F$. The first is far weaker, and mixing them up turns "not all snakes are venomous" into "no snake is venomous". The rule that relates them is the subject of the next lesson.

Example. Translate "not every alloy containing nickel is magnetic" and say how it relates to the earlier translation.

It is $\neg \forall x(Ax\to Mx)$, the denial of the earlier A form. It is equivalent to $\exists x(Ax\wedge \neg Mx)$, the O form, which is the useful shape because it says what to go and look for: one alloy, containing nickel, not magnetic.

Now you. Which of $\neg \exists x(Rx\wedge Vx)$ and $\exists x(Rx\wedge \neg Vx)$ says "no reptile is venomous"?

What this buys and what it costs

The language now has names, predicates, variables, two quantifiers and the whole propositional apparatus on top. The syllogism is valid in it, the four categorical forms are expressible, and the empty-term assumption that Aristotle left implicit is now something you write down or leave out deliberately.

The cost arrives with the next lesson. As soon as predicates take two places, a formula can carry two quantifiers, and their order changes what is said: everyone loving someone is a different claim from someone being loved by everyone. English handles that ambiguity badly, mathematics depends on it completely, and the notation is about to make it exact.

Everything quantified so far has had one place, so a formula could say what all things are like and never how any two of them stand to each other.

Relations fix that, and they bring the first genuinely hard thing in the subject with them. Once two quantifiers can appear in one formula, their order matters, and the difference between one order and the other is the difference between a triviality and a claim nobody can prove. English marks this distinction badly, which is why "everyone loves someone" is ambiguous in a way that $\forall x\exists yLxy$ is not. This lesson makes the order precise, gives the rules for pushing a negation through a string of quantifiers, and ends with the place where the distinction earns its living, the definition of a limit.

Relations

A two-place predicate takes two names: $Lab$ for "$a$ loves $b$", $Gab$ for "$a$ is greater than $b$", $Rab$ for "$a$ read $b$". Order inside the predicate is fixed by convention and never symmetric by default, so $Lab$ and $Lba$ are different formulas and must be, since love famously runs one way as often as two.

Three-place predicates are equally legal, $Bxyz$ for "$x$ is between $y$ and $z$", and everything below works the same way for them. Most of the useful cases have two places.

With relations available, properties of relations become formulas rather than English descriptions, and this is where the notation starts to pay. A relation $R$ is reflexive when $\forall xRxx$, symmetric when $\forall x\forall y(Rxy\to Ryx)$, and transitive when $\forall x\forall y\forall z((Rxy\wedge Ryz)\to Rxz)$. "Is the same age as" satisfies all three; "is taller than" is transitive and neither reflexive nor symmetric; "is a sibling of" is symmetric and, on the usual reading, not transitive, since a person is not their own sibling and the relation chains oddly through half-siblings.

Order matters

Take the domain to be the positive integers and $Gxy$ to mean $x>y$. Then

says that for every integer there is a larger one, which is true. Swap the quantifiers:

says that some single integer is larger than every integer, which is false, and not slightly false. The formulas differ only in the order of two symbols, and the reason for the difference is that in the first the choice of $y$ may depend on $x$, while in the second $y$ is fixed before $x$ is considered and must work for all of them.

That is the whole rule and it is worth stating plainly: an inner quantifier may depend on an outer one, never the reverse. $\exists y\forall x$ is a stronger claim than $\forall x\exists y$, and it entails it, while the converse fails.

Quantifiers of the same kind do commute. $\forall x\forall y$ and $\forall y\forall x$ say the same thing, and so do $\exists x\exists y$ and $\exists y\exists x$. Only mixed pairs are order-sensitive, and only those need care.

Example. With a domain of three people, $a$, $b$ and $c$, suppose $a$ loves $b$, $b$ loves $c$, and $c$ loves $a$, and nobody loves anyone else. Evaluate $\forall x\exists yLxy$ and $\exists y\forall xLxy$.

The first says everybody loves somebody. Check each person: $a$ loves $b$, $b$ loves $c$, $c$ loves $a$, so it is true. The second says somebody is loved by everybody, which requires a single person loved by all three. $b$ is loved only by $a$, $c$ only by $b$, $a$ only by $c$, so it is false. One small domain separates the two formulas, and building such a domain is the whole method of the next lesson.

Now you. In the same situation, evaluate $\exists x\forall yLxy$ and say what it claims.

Pushing a negation through

Two laws relate the quantifiers, and they are De Morgan's laws again in a new setting.

In words: denying that everything is $F$ is asserting that something is not $F$, and denying that anything is $F$ is asserting that everything is not $F$. The connection to De Morgan is exact. Over a finite domain of three objects, $\forall xFx$ is $Fa\wedge Fb\wedge Fc$ and $\exists xFx$ is $Fa\vee Fb\vee Fc$, so the quantifier laws are the propositional ones with the conjunction and disjunction stretched to any length, including an infinite one.

Applied repeatedly, they push a negation all the way inside: each quantifier it passes flips, and the negation lands on the matrix at the end. So

using the fifth lesson's rule for negating a conditional at the last step. This is the standard first move in any proof by contradiction involving quantifiers, and doing it mechanically rather than by intuition is what stops "not every" from turning into "none".

Example. Negate "every student read some book on the list", and say what a refutation must produce.

Write it as $\forall x(Sx\to \exists y(By\wedge Rxy))$. Pushing the negation in: $\exists x\neg (Sx\to \exists y(By\wedge Rxy))$, then $\exists x(Sx\wedge \neg \exists y(By\wedge Rxy))$, then

So a refutation must produce one student such that every book on the list went unread by that student. Not a student who missed one book: a student who read none of them. The mechanical negation says exactly what evidence would settle the question, which is usually the reason for doing it.

Now you. Negate $\exists x\forall y(Fy\to Gxy)$ and read the result in words.

Translating with restrictions

Most English quantification is restricted to a kind of thing, and the eighth lesson's two patterns still do the work: a universal takes a conditional, an existential takes a conjunction. With relations, those patterns nest.

"Every student read a book" is $\forall x(Sx\to \exists y(By\wedge Rxy))$: the outer universal takes a conditional, the inner existential a conjunction. "Some student read every book" is $\exists x(Sx\wedge \forall y(By\to Rxy))$, with the same two patterns in the other order. Writing them side by side is the best drill available, since each mistake produces a formula that says something clearly wrong rather than something merely odd.

English is genuinely ambiguous here and the notation is not, which cuts both ways. "Every student read a book" most naturally means each read some book or other, but it can mean there is one particular book they all read, and only the formula distinguishes them. When translating a real document, translating both readings and asking which was meant is often the most useful thing a logician does.

The definition of a limit

The most consequential quantifier order in mathematics is in the definition of continuity, and it is worth seeing because it shows the difference doing real work rather than making a point about love or integers.

A function $f$ is continuous on a set when

and uniformly continuous when the $\exists \delta$ moves in front of the $\forall x$:

Everything else is identical. In the first, $\delta$ may depend on where you are; in the second, one $\delta$ must work everywhere at once. By the rule above, uniform continuity implies continuity and not conversely.

The gap is real and numbers show it. Take $f(x)=x^2$ on the whole real line with $\epsilon =1$. Near $x=1$ a step of $\delta =0.001$ is ample: ${1.001}^2-1^2=0.002001$, comfortably under 1. Near $x=1000$ the same step fails, since ${1000.001}^2-{1000}^2=2.000001$, which is over 1. To keep the output change under 1 near $x=1000$ the step must be under about $1/2000$, and as $x$ grows the required $\delta$ shrinks without limit. So no single $\delta$ serves every $x$: the function is continuous everywhere and not uniformly continuous. Squaring is a familiar operation, and the difference between two orderings of two quantifiers is what separates two of its properties.

Example. State, with quantifiers, what it takes for $f$ to fail to be uniformly continuous.

Negate the definition and push the negation in. $\forall \epsilon$ becomes $\exists \epsilon$, $\exists \delta$ becomes $\forall \delta$, the two $\forall$s become $\exists$s, and the conditional becomes a conjunction:

For $f(x)=x^2$ this is what the numbers above exhibit: with $\epsilon =1$, whatever $\delta$ is offered, a pair of points that close together can be found far enough out to move the output by at least 1.

Now you. "Every lock in the building has a key that opens it" and "there is a key that opens every lock in the building". Write both, and say which entails the other.

What is still missing

The language is now expressive enough for the working mathematics of the rest of this course and for most careful English. What has not been said is what any of it means precisely. "True in the domain of positive integers" was used freely above, and "false" was justified by pointing at three people and a loving relation, which is persuasive rather than exact.

The gap matters because the truth table method has quietly died. A formula with quantifiers has no finite list of valuations to run through: the domain may be infinite, and there are infinitely many domains. So the third lesson's decision procedure is gone and something must replace it, both for saying what truth in a structure is and for the practical business of refuting an invalid argument. That is the next lesson.

Quantified formulas have been called true and false for two lessons without anything saying what those words mean once a domain is involved.

For propositional logic the answer was a row of a table, and there were finitely many rows. Here there is no such list: a domain may hold any number of things, including infinitely many, and there are infinitely many domains to consider. So the truth table method is gone, and with it the guarantee that any question can be settled by grinding. What replaces it is the notion of a model, which makes truth precise, and the practice of building countermodels, which is how invalidity gets shown in practice.

What an interpretation supplies

An interpretation, also called a structure or a model, has three parts.

A domain: a non-empty set of objects the quantifiers range over. Non-empty is a stipulation rather than a discovery, made so that $\forall xFx\to \exists xFx$ comes out valid, and it is worth knowing it is a convention that could have gone the other way.

An object for each name: the constant $s$ picks out one member of the domain. Two names may pick out the same object, and an object may have no name at all.

An extension for each predicate: for a one-place predicate, the set of domain members it is true of; for a two-place one, the set of ordered pairs. The extension is all there is to a predicate. $F$ does not mean "is a fish" in an interpretation; it just is a set, and calling it fishhood is a comment for the reader.

That is deliberately spare, and the spareness is the point. Logic is checking whether the conclusion follows under every way of filling those slots, so it must not care what the slots are filled with.

Truth in a model

With an interpretation fixed, every sentence gets a truth value by a recursion that runs through its structure.

An atomic sentence $Fa$ is true when the object named by $a$ is in the extension of $F$, and $Rab$ is true when the pair of objects named sits in the extension of $R$. The connectives behave exactly as in the truth tables of the third lesson, so $\phi \wedge \psi$ is true when both parts are, and so on for the rest.

The quantifiers are the new part. $\forall x\phi$ is true when $\phi$ holds of every member of the domain, and $\exists x\phi$ is true when it holds of at least one, where "holds of an object" means the object is temporarily treated as the value of $x$. Over a finite domain this is a finite check, and over an infinite one it is a definition rather than a procedure: it says what truth is without saying how to establish it.

Take a domain of three people, $\{1,2,3\}$, with $Lxy$ for "$x$ likes $y$" whose extension is the pairs $(1,2)$, $(2,3)$ and $(3,1)$, and $Hx$ true of 1 and 2 only. Then $\exists x\neg Hx$ is true, witnessed by 3. $\forall x\exists yLxy$ is true, since each person likes one other. $\exists y\forall xLxy$ is false, since being liked by everyone would need three incoming arrows and each person has exactly one. Nothing here required inspiration; each answer was read off the extensions.

Countermodels

The eighth lesson's definition of validity carries over word for word, with interpretations in place of rows: an argument is valid when no interpretation makes every premise true and the conclusion false. So to show an argument invalid, produce one such interpretation. It is called a countermodel, and it settles the question permanently, the way a single counterexample destroys a universal claim.

This is the workhorse skill of predicate logic, and it has a method rather than requiring inspiration.

Start with the smallest domain that could work, usually one or two objects. Write down what the conclusion being false requires. Write down what each premise being true requires. Fill in the extensions to satisfy all of it, adding objects only when forced. Then check every premise and the conclusion against the finished interpretation, because a countermodel that does not actually work is worse than none.

Example. Show that $\forall x(Fx\to Gx)$ and $\exists xGx$ do not entail $\exists xFx$.

The conclusion is false when nothing is $F$, so try an empty extension for $F$. The first premise is then vacuously true, since no object has to pass the test. The second premise needs something in $G$. So take the domain $\{1\}$, the extension of $F$ empty, the extension of $G$ containing 1.

Check: $\forall x(Fx\to Gx)$ holds because $F1$ is false, making the conditional true. $\exists xGx$ holds because $G1$ is true. $\exists xFx$ fails because $F$ is empty. One object settles it. Reading it in English: every fish is a mammal is true when there are no fish, something is a mammal is true, and nothing is a fish.

Now you. Show that $\forall x(Fx\to Gx)$ and $\forall x(Hx\to Gx)$ do not entail $\forall x(Fx\to Hx)$.

Countermodels with relations

Relations need slightly larger domains, and the quantifier order of the previous lesson is where they are needed most.

Example. Show that $\forall x\exists yRxy$ does not entail $\exists y\forall xRxy$.

The premise needs every object to relate to something; the conclusion must fail, so no single object may be related to by everything. Two objects suffice. Take the domain $\{1,2\}$ with $R$ holding of the pairs $(1,2)$ and $(2,1)$ and no others.

Check the premise: 1 relates to 2 and 2 relates to 1, so every object relates to something. Check the conclusion: for it to hold, some object must be related to by both. Object 1 qualifies only if $R11$ and $R21$ both hold, and $R11$ is absent; object 2 qualifies only if $R12$ and $R22$ hold, and $R22$ is absent. So the conclusion is false and the argument is refuted. In English, everyone has a friend does not give that someone is everyone's friend.

Now you. Show that a transitive relation need not be reflexive, by giving a model of $\forall x\forall y\forall z((Rxy\wedge Ryz)\to Rxz)$ in which $\forall xRxx$ fails.

How big must a countermodel be

Small, usually. Many invalid arguments are refuted by one object, most of the rest by two or three, and a good rule is to try each size in turn rather than starting with something elaborate.

The number of interpretations to check at each size is finite and grows fast: with a domain of $n$ objects, a one-place predicate has $2^n$ possible extensions and a two-place one has $2^{n^2}$, so a two-object domain with one binary relation already offers 16 choices and a three-object domain offers 512. That is why the guided method beats enumeration.

There is an honest limit. Not every satisfiable formula has a finite model. Take the conjunction of three sentences: $\forall x\neg Rxx$, saying nothing relates to itself; $\forall x\forall y\forall z((Rxy\wedge Ryz)\to Rxz)$, transitivity; and $\forall x\exists yRxy$, saying everything relates to something. The positive integers with $Rxy$ as $x<y$ satisfy all three. No finite domain can: brute force over all relations on domains of one, two, three and four objects finds zero models, and the reason generalises, since starting anywhere and following the relation gives an endless chain of distinct objects, distinct because a repeat would make something related to itself by transitivity.

So searching for countermodels is not a decision procedure. It is a method that usually works quickly and can fail to terminate, and the theory says that this cannot be repaired.

What cannot be done

Propositional logic was decidable: the table always finished. First-order logic is not. Alonzo Church and Alan Turing showed independently in 1936 that no algorithm decides whether an arbitrary first-order formula is valid, which settled Hilbert's Entscheidungsproblem in the negative and, in Turing's case, produced the machine model of computation on the way to the answer.

What survives is weaker and still useful. Validity is semi-decidable: the derivations can be enumerated mechanically, so a search that tries all of them will find a proof if one exists. If the formula is valid you eventually get a proof; if it is not, the search may run for ever, and no signal tells you which situation you are in. That asymmetry is exactly what makes automated theorem provers behave the way they do.

There is one important special case. Monadic first-order logic, with only one-place predicates and no relations, is decidable, and the categorical syllogisms of the eighth lesson live inside it, which is why the count of valid forms could be computed by exhausting a finite list of possibilities. Adding a single two-place predicate loses the property.

Example. Why is producing a countermodel a complete method for showing invalidity but not for showing validity?

Because invalidity is an existential claim and validity is a universal one. One interpretation with true premises and a false conclusion establishes invalidity outright, and no amount of failing to find one establishes validity, since the interpretations are unbounded in size and number. Establishing validity therefore needs a proof about all interpretations at once, which is what a derivation supplies.

Now you. An argument survives your search through every domain of one, two and three objects. What have you established?

Where this leaves things

Truth in a model is now defined, invalidity has a practical test, and the limits of that test are known: countermodels are usually small, sometimes impossible, and searching for one never certifies validity.

That last gap is what the next lesson fills. Derivation was the answer for propositional logic when tables became unwieldy, and it is the answer here for a stronger reason, since the semantic method has stopped being a procedure at all. Four rules for the quantifiers turn out to be enough, and two of them need restrictions that look fussy until you see what happens without them.

Searching for a countermodel can establish that an argument fails and can never establish that it succeeds, so predicate logic needs derivations even more than propositional logic did.

The previous lesson closed with the reason: the semantic method is no longer a procedure, since domains are unbounded and no algorithm decides validity. Derivation still works. The system of the sixth and seventh lessons carries over unchanged, and four rules are added, one to introduce and one to eliminate each quantifier. Two of the four are as simple as anything in the subject. The other two carry restrictions, and this lesson spends most of its length on those restrictions, because without them the system proves that everything is everything.

Universal elimination

Universal elimination ($\forall$E): from $\forall x\phi$, write $\phi$ with any name substituted for $x$ throughout.

If everything is mortal then Socrates is, and so is the alloy, and so is anything else you can name. The rule is sound because the premise says the formula holds of every object in the domain, and a name picks out one of them. There is no restriction: the name may be new or already in use, and it may be one that occurs in the premises, since instantiating a universal claim to something you already know about is exactly what the claim licenses.

Existential introduction

Existential introduction ($\exists$I): from a formula containing a name, write the existential formula got by replacing that name with a variable and binding it.

If Socrates is mortal then something is. Soundness is immediate: the named object is a witness. Note that the rule may replace some or all occurrences of the name, so from $Laa$, "$a$ loves $a$", you may infer $\exists xLxx$, that someone loves themselves, or $\exists xLxa$, that someone loves $a$, and the two are different claims.

Those two rules alone settle the argument that broke propositional logic.