Appearance
8.2 — Logic
"If it rains, the match is cancelled. The match was cancelled. Therefore it rained."
That argument is invalid, and most people accept it without hesitation. The match might have been cancelled for a dozen other reasons. Logic is the discipline of separating arguments that are genuinely valid from arguments that merely feel convincing, and it does so by ignoring the content entirely and looking only at the shape.
Aristotle started it around 350 BCE. George Boole made it algebra in 1847. Claude Shannon noticed in 1937 that Boole's algebra describes electrical switching circuits, and every computer since has been built on that observation — Volume I, 1.1 tells that story.
1. Propositions and connectives
A proposition is a statement that is definitely true or definitely false. "Delhi is in India" is a proposition. "What time is it?" is not, and neither is "this sentence is false", which is a different problem entirely.
Five connectives build compound propositions.
| Symbol | Name | Read as | True when |
|---|---|---|---|
| \neg P | negation | not P | P is false |
| P\land Q | conjunction | P and Q | both true |
| P\lor Q | disjunction | P or Q | at least one true |
| P\to Q | implication | if P then Q | see below |
| P\leftrightarrow Q | equivalence | P if and only if Q | both same |
Note that "or" is inclusive. P\lor Q is true when both are true. Everyday English often means exclusive or ("tea or coffee"), and mathematics does not — when the exclusive version is meant it is written \oplus and is Chapter 8.1's symmetric difference.
2. Implication, which is where the trouble is
\begin{array}{cc|c} P & Q & P\to Q\\\hline T&T&T\\ T&F&F\\ F&T&\textbf{T}\\ F&F&\textbf{T} \end{array}
An implication is false only when the premise is true and the conclusion is false. When the premise is false, the implication is true regardless of the conclusion.
That last part is where everyone objects. "If the moon is made of cheese, then 2+2=5" is a true statement in logic.
Here is why it must be. Take the promise: "if you pass the exam, I will buy you a bike." When have you broken that promise? Only if the student passed and got no bike. If they failed, you have not broken it whether you bought the bike or not — the promise said nothing about that case.
So a false premise cannot make the implication false, and since every proposition must be true or false, it is true. This is called being vacuously true, and Chapter 8.1 used it to say the empty set is a subset of everything.
The three variants, and only one of them is equivalent to the original:
- Converse Q\to P. Not equivalent. This is the rain-and-match error from the opening.
- Inverse \neg P\to\neg Q. Not equivalent. "If it did not rain, the match was not cancelled" — also wrong.
- Contrapositive \neg Q\to\neg P. Equivalent, always. "If the match was not cancelled, it did not rain." True whenever the original is.
The contrapositive is a genuinely useful tool, because it lets you prove a statement by proving something logically identical that may be easier to attack. Chapter 8.3 uses it.
Confusing a statement with its converse is the most common reasoning error there is. "All successful founders dropped out" does not mean dropping out makes you successful. "Every fraudster used encryption" does not mean encryption users are fraudsters. Once you have the word "converse" you notice the error everywhere.
3. Truth tables, tautologies and equivalences
A tautology is true under every assignment: P\lor\neg P. A contradiction is false under every assignment: P\land\neg P. A contingency is sometimes true.
Equivalences worth knowing:
\neg(P\land Q) \equiv \neg P\lor\neg Q
\neg(P\lor Q)\equiv\neg P\land\neg Q
De Morgan again — the same law as Chapter 8.1's set version, because sets and logic are the same algebra with different symbols. Union is or, intersection is and, complement is not.
P\to Q \equiv \neg P\lor Q
This one is worth internalising, because it converts every implication into a form built from the simpler connectives, and it makes the truth table of Section 2 obvious: the implication is true unless P is true and Q is false.
\neg(P\to Q)\equiv P\land\neg Q
To disprove "if P then Q", you need a case with P true and Q false. That case is a counterexample, and it is the only thing that refutes a universal claim.
4. Quantifiers
Propositional logic cannot express "every prime greater than 2 is odd", because that is a statement about infinitely many things. Predicate logic adds two symbols.
\forall x\, P(x) \quad\text{— for all } x, P(x) \text{ holds}
\exists x\, P(x) \quad\text{— there exists an } x \text{ with } P(x)
Negating a quantifier flips it and pushes the negation inward:
\neg\forall x\,P(x) \equiv \exists x\,\neg P(x)
\neg\exists x\,P(x)\equiv\forall x\,\neg P(x)
In plain words: "not everything is P" means "something is not P", and "nothing is P" means "everything is not P".
This is the formal justification for proof by counterexample, and it is a habit worth having in ordinary argument: the opposite of "all swans are white" is not "no swans are white" but "there is at least one non-white swan".
Order of quantifiers changes the meaning completely
\forall x\,\exists y\;(y \gt x) \quad\text{— for every number there is a larger one. TRUE.}
\exists y\,\forall x\;(y \gt x) \quad\text{— there is one number larger than every number. FALSE.}
The symbols are the same and the order is reversed. In the first, y may depend on x. In the second, one y must work for all x at once.
This is the difference between "everyone has a mother" and "there is someone who is everyone's mother", and getting it wrong in a specification produces requirements that are trivially satisfiable or impossible. It is also the exact distinction in the epsilon-delta definition of Chapter 5.1, and in the definition of uniform continuity, where swapping two quantifiers gives a genuinely different and stronger property.
5. Rules of inference
Valid argument forms, each of which can be checked with a truth table.
Modus ponens. From P\to Q and P, conclude Q. If it rains the ground gets wet; it is raining; therefore the ground is wet.
Modus tollens. From P\to Q and \neg Q, conclude \neg P. The ground is dry, so it did not rain. This is the contrapositive in action, and it is the logic behind every falsification test in science: the theory predicted an effect, the effect was absent, so the theory is wrong.
Hypothetical syllogism. From P\to Q and Q\to R, conclude P\to R. Chains of reasoning.
Disjunctive syllogism. From P\lor Q and \neg P, conclude Q. Elimination.
Two fallacies with names, both of which look like the valid rules and are not:
Affirming the consequent. From P\to Q and Q, concluding P. The opening example.
Denying the antecedent. From P\to Q and \neg P, concluding \neg Q. "If you study, you pass. You did not study, so you failed." Perhaps you passed anyway.
An argument being invalid does not make its conclusion false. It means the conclusion does not follow from those premises. Valid form and true conclusion are independent, and keeping them separate is most of what clear thinking consists of.
6. Boolean algebra and circuits
Rewrite true as 1 and false as 0, and as multiplication and or as addition (with 1+1=1), and logic becomes an algebra you can compute with. That is Boole's contribution, and Shannon's 1937 master's thesis showed that a switching circuit implements it directly: switches in series are and, switches in parallel are or.
Every digital circuit is a Boolean expression made of transistors, and Volume I, 1.1 and 1.2 build up from gates to a working processor.
Simplification saves real hardware. The expression
(A\land B)\lor(A\land\neg B)
is just A, because B either holds or does not. Two gates removed. At the scale of a processor with billions of gates, systematic simplification — Karnaugh maps, and the algorithms that replaced them — is worth enormous amounts of power and silicon.
And it is why if statements can be rewritten. if (!(a && b)) is if (!a || !b), and knowing De Morgan's law makes that rewrite automatic rather than a puzzle. Short-circuit evaluation in programming languages — where a && b does not evaluate b if a is false — is the same law being exploited for speed, and it is why you can safely write if (obj && obj.value).
7. The limits of logic
Two results are worth knowing about, and Chapter 11.5 tells their stories properly.
Propositional logic is decidable. A truth table settles any formula. But a formula with n variables needs 2^n rows, so deciding satisfiability is exponential in the worst case. The satisfiability problem, SAT, was the first problem proved NP-complete (Volume I, 1.7), and it sits at the centre of the P versus NP question.
That said, modern SAT solvers handle problems with millions of variables in practice, and they are used for hardware verification, scheduling, and proving software correct. The worst case is bad; the typical case is often fine.
Predicate logic is not decidable. Church and Turing proved in 1936 that no algorithm can determine whether an arbitrary statement of predicate logic is provable. This is the Entscheidungsproblem, and settling it is what led Turing to invent the Turing machine — the model of computation that founded computer science. Volume I, 1.7 covers the halting problem, which is the same result in different clothing.
Gödel's incompleteness theorems, from 1931, go further: any consistent formal system powerful enough to describe arithmetic contains true statements it cannot prove. Hilbert's programme to place all of mathematics on a complete and provably consistent foundation was shown to be impossible, five years after it was launched.
Every formula above, built from scratch
None of the results in this chapter are worth memorising, because each one can be rebuilt in under a minute from something simpler. What follows is that rebuilding, one result at a time, so the formula and the reason for it sit on the same page as the explanation that needed them.
Logic
| p | q | p\land q | p\lor q | p\to q | p\leftrightarrow q |
|---|---|---|---|---|---|
| T | T | T | T | T | T |
| T | F | F | T | F | F |
| F | T | F | T | T | F |
| F | F | F | F | T | T |
The row that troubles everyone: p\to q is true when p is false. "If it rains, I take an umbrella" is not broken by a dry day — on a dry day the promise says nothing at all, so it has not been violated. An implication is only false when the promise is made and then broken: p true, q false. Defining it any other way would make "all prime numbers greater than 100 that are even are also purple" false, when it should be trivially true for lack of any counterexample.
The equivalences that do real work.
p\to q \;\equiv\; \lnot p\lor q
p\to q \;\equiv\; \lnot q\to\lnot p \qquad\text{(the contrapositive)}
\lnot(p\to q)\;\equiv\; p\land\lnot q
The contrapositive is the useful one. "If it is a square, it is a rectangle" is exactly the same statement as "if it is not a rectangle, it is not a square". Swapping and negating preserves truth. Swapping alone does not: the converse q\to p is a different claim entirely, and confusing a statement with its converse is the engine of most bad reasoning — including the medical-test error of 7.P, where P(+|D) was mistaken for P(D|+).
Quantifiers, and how to negate them.
\lnot\forall x\,P(x) \;\equiv\; \exists x\,\lnot P(x), \qquad \lnot\exists x\,P(x)\;\equiv\;\forall x\,\lnot P(x)
To disprove "every swan is white" you need one black swan. To disprove "some swan is green" you must check them all. This asymmetry is why a single counterexample destroys a universal claim and why proving an existence claim needs only one example.
8. Where this shows up in your life
Every conditional in every program you have ever written, and every bug caused by getting a negation wrong.
Every database query's WHERE clause. Boolean algebra, optimised by an engine that applies exactly these equivalences.
Every digital circuit in every device. Shannon's insight, at scale.
Every legal or contractual clause. "If and only if", "unless", "provided that" — and the ambiguity of natural language is precisely why contracts are so verbose.
Every argument you evaluate. Affirming the consequent is the most common fallacy in public discourse, and having a name for it makes it visible.
Every formal verification of safety-critical software — aircraft, medical devices, rail signalling — which is a SAT or theorem-proving problem.
Logic tells you what follows from what. To establish a mathematical statement you need to actually construct such a chain, and there are a handful of standard shapes those chains take.