A product manager writes in a ticket: "Show the discount banner if the user is a member or has spent over $100, but not if they’re logged out." You translate that into code. A week later a bug report arrives: logged-out members are seeing the banner. Was the ticket ambiguous, or was the code wrong?

English is a wonderful language for poetry and a terrible one for specifications. "Or" sometimes means "one or the other or both" and sometimes "one or the other but not both". "But" means "and" with an attitude. "Unless" means something different to almost everyone who reads it. Logic is the discipline of removing that ambiguity: it gives each connecting word one precise meaning, and then gives rules for combining and rewriting statements without changing what they say.

Think of a statement as a wire that carries either true or false. Connectives are little machines that take one or two wires in and produce one wire out. "Not" flips its wire. "And" outputs true only if both inputs are true. "Or" outputs true if at least one input is true. Because each wire has only two possible values, you can describe any machine completely by listing what it does for every combination of inputs. That list is a truth table, and it is the whole definition: no further interpretation is needed or allowed.

The symbols \(\wedge\) (and) and \(\vee\) (or) are easy to mix up. A mnemonic: \(\wedge\) looks like the "A" in *A*nd with the crossbar missing; \(\vee\) comes from the Latin vel, "or".

Here are the definitions, all in one table. Each row is one possible combination of truth values for \(p\) and \(q\); with two inputs there are \(2^2 = 4\) rows.

Try it: The conditional’s truth table.

Three of these columns match everyday intuition. Two need comment.

Or is inclusive. \(p \vee q\) is true when both are true. If you mean "one or the other but not both", that is a different connective, exclusive or, written \(p \oplus q\) (and p != q or p ^ q in most languages). Mathematics, logic and programming languages all default to the inclusive reading.

The conditional is the subject of the next section; its last two rows surprise almost everyone.

Let us settle the banner ticket. Let \(m\) = "user is a member", \(s\) = "user spent over $100", \(\ell\) = "user is logged in". The most reasonable reading is Try it: Build the banner truth table.

With three atomic propositions there are \(2^3 = 8\) rows. The systematic way to list them is to count down in binary: the first column alternates in blocks of four, the second in blocks of two, the third every row. Then compute intermediate columns left to right, exactly as you would evaluate a sub-expression before the expression that uses it.

Rows 2 and 4 are the bug report: a member who is logged out. The specification says F. The most likely culprit is code written as is_member or big_spender and logged_in, which Python parses as \(m \vee (s \wedge \ell)\) because and binds more tightly than or. In rows 2 and 4 that gives \(T \vee (\ldots) = T\): the banner appears. A truth table makes this kind of disagreement impossible to miss.

Try it: Truth table, step by step.

The procedure is an algorithm, so here it is as code. itertools.product([True, False], repeat=n) generates the \(2^n\) rows in exactly the order described in step 2.

Truth tables are exhaustive, which is both their virtue and their limit: \(n\) variables need \(2^n\) rows. Ten variables means 1,024 rows; forty means about a trillion. That exponential wall is exactly why the algebraic laws later in this chapter, and the SAT solvers mentioned at the end, matter.

Everyday: rules with several conditions. A shop offers "free delivery if you are a member, or if the order is at least $40 and not oversized". With \(m\), \(f\) (at least $40) and \(o\) (oversized), that is \(m \vee (f \wedge \neg o)\). The brackets matter: \((m \vee f) \wedge \neg o\) is a different policy that charges members for oversized parcels. Writing the formula is how you settle the argument at the checkout.

Medicine: "at least two of three". The qSOFA bedside screen for sepsis flags a patient when at least two of these hold: breathing rate at least 22 per minute (\(r\)), altered mental state (\(a\)), systolic blood pressure at most 100 mmHg (\(b\)). As a formula: \((r \wedge a) \vee (r \wedge b) \vee (a \wedge b)\), the majority function. Its truth table is T in exactly 4 of the 8 rows (TTT, TTF, TFT, FTT), and the same function is the carry-out bit of a full adder.

Engineering: interlocks. An industrial press may cycle only if the guard is closed (\(g\)) and both of the operator’s hands are on the two buttons (\(\ell\), \(r\)): \(g \wedge \ell \wedge r\). Two-hand controls exist so that no hand can be under the ram; the safety argument is literally a truth table with one T row out of eight.

Computing. Search boxes that accept jaguar AND (engine OR gearbox) NOT cat are evaluating a propositional formula per document; firewall and feature-flag rules are the same thing.

A parent says: "If you finish your homework, you can play video games." The child does not finish the homework and plays anyway. Did the parent lie? Most people say: no, the parent made no promise about what happens if the homework is unfinished.

Now look at the truth table for \(p \to q\) again. When \(p\) is false, \(p \to q\) is true, whatever \(q\) is. "False implies anything." This feels like a cheat when you first meet it. Why is it the right definition?

Read \(p \to q\) as a promise or a contract: "whenever \(p\) holds, I guarantee \(q\)". The only way to break such a promise is for \(p\) to happen and \(q\) not to: row T, F. In every other row the promise has not been broken, and in two-valued logic "not false" means true.

A better test case than homework is a rule that has to hold for many cases at once. Take "for every whole number \(n\), if \(n\) is divisible by 4 then \(n\) is even". Everyone agrees this is true. Now check it at \(n = 3\): "if 3 is divisible by 4 then 3 is even" has a false hypothesis and a false conclusion. At \(n = 6\): "if 6 is divisible by 4 then 6 is even" has a false hypothesis and a true conclusion. If either of these instances counted as false, then the general rule, which is the conjunction of all its instances, would be false. So for universal rules to work the way everyone wants, the conditional with a false hypothesis must be true. Logic is designed so that general statements behave; the truth table follows.

"Only if" deserves a second look because it trips everyone. "You can vote only if you are 18 or over" means voting \(\to\) 18-or-over: being 18 is necessary. It does not say every 18-year-old can vote (they might not be registered).

Comparing columns shows that \(p \to q\) has exactly the same truth table as \(\neg p \vee q\):

"If it is raining, I take an umbrella" says the same as "either it is not raining, or I take an umbrella". This is how you implement implication in a language that has no implication operator, and it is the form that algebraic simplification works with.

From one conditional \(p \to q\) you can form three relatives by swapping and/or negating the parts.

The pattern in the example is universal: a conditional is always equivalent to its contrapositive, and the converse is always equivalent to the inverse (the inverse is the contrapositive of the converse). But a conditional is not equivalent to its converse. Check the contrapositive with a truth table:

The third and last columns agree in every row. The contrapositive is not a curiosity: it is a whole proof technique in Chapter 22, used whenever "not \(q\)" is easier to work with than \(p\).

A picture makes the asymmetry obvious. Treat \(p\) and \(q\) as properties and draw the set of things having each. "Every square is a rectangle" means the square region sits entirely inside the rectangle region. The converse would need the reverse containment, and the non-square rectangle on the right shows it fails.

A comment says: "If the cache is warm, the request returns in under 10 ms." Let \(w\) = "cache is warm", \(f\) = "request is fast". Then:

If you observe a slow request, the contrapositive lets you conclude the cache was cold, assuming the comment is true. If you observe a fast request, you can conclude nothing about the cache.

Everyday: reading offers and rules. "If you spend over $50, delivery is free" is broken only by a customer who spends $60 and is charged for delivery. The shop that also gives free delivery on a $30 order has not broken it (false hypothesis). "Only if" clauses are the ones people misread: "the warranty is valid only if the device has not been opened" means valid \(\to\) not opened. Not opening it is necessary, but not sufficient: a two-year-old device may be out of warranty anyway.

Medicine: a test and its converse. "If you have the disease, the test is positive" (a test with high sensitivity) is the statement labs measure. The patient wants the converse, "if the test is positive, I have the disease", and that can be badly false when the disease is rare. Quantifying how false is a job for Bayes' theorem in Chapter 29; recognising that it is a different statement is a job for this section.

Engineering: fault-finding with the contrapositive. "If the fuse is intact and the switch is closed, the lamp lights": \((f \wedge s) \to L\). The lamp is dark, so by modus tollens \(\neg(f \wedge s)\), which by De Morgan (next section) is \(\neg f \vee \neg s\): the fuse has blown or the switch is open. Check the switch first; it is cheaper.

Computing. An assert or a function’s documented precondition is a conditional: "if the input is sorted, the result is the index of the target". Calling it on unsorted input does not make the function wrong; it makes the contract vacuous, and the result meaningless.

Here is a real-world conditional from a code review:

What does it actually say? Under what conditions is the user allowed? And can it be written so that a tired reviewer at 6 p.m. can check it? We need a way to transform logical expressions while guaranteeing the meaning does not change.

Two expressions are equivalent if no situation can tell them apart: in every row of the truth table they give the same answer. Just as algebra has laws such as \(a(b + c) = ab + ac\) that let you rewrite expressions, logic has laws that let you rewrite propositions. Each law can be verified once, by truth table, and then used forever without checking again.

Notice the pattern: every law comes in a pair, obtained by swapping \(\wedge\) with \(\vee\) and \(\mathbf{T}\) with \(\mathbf{F}\). This is the duality principle. Also notice that unlike ordinary algebra, both distributive laws hold: "and" distributes over "or" (like multiplication over addition), and "or" also distributes over "and" (which has no arithmetic counterpart: \(a + bc \neq (a + b)(a + c)\) in general).

To push a "not" inside a bracket, negate each piece and flip the connective. "It is not the case that the server is both up and healthy" means "the server is down or it is unhealthy". "It is not the case that it’s raining or snowing" means "it is not raining and it is not snowing".

Why must the connective flip? "Not both" fails only when both hold, so it is true as soon as one of them fails: that is an "or" of failures. "Neither" requires every option to fail: that is an "and" of failures. You saw the truth tables in the first exercise set; the Venn diagram in Section 21.5 gives the same picture for sets.

Let \(a\) = user.is_admin, \(o\) = user.is_owner, \(\ell\) = doc.locked. The code raises when Try it: Push the negation inward.

Push the negation inward one step at a time:

In words: deny if the user is not an admin, and either is not the owner or the document is locked. The code can be rewritten

Even better is to name the positive condition, since the original’s inner expression was the allow rule all along:

Which is better is a judgment call; the point is that you can now move between the forms with certainty.

Simplify \((p \wedge q) \vee (p \wedge \neg q)\). Try it: Check the absorption example.

Sanity check in words: "\(p\) and \(q\), or \(p\) and not \(q\)" is true exactly when \(p\) is true, whatever \(q\) does. The variable \(q\) was irrelevant, and the code if (p and q) or (p and not q) is a smell.

You have three ways to decide whether two expressions are equivalent.

Try it: De Morgan, row by row; Contrapositive versus conditional; Converse is not equivalent; Distributive law, three variables.

Rule of thumb: use the laws to find a simpler form, then use a truth table or equivalent to confirm it. When refactoring a production conditional, write the confirmation as a unit test.

Everyday: rules phrased in the negative. A cinema says "no entry unless you are over 15 or with an adult". Entry is allowed when \(a \vee w\); by De Morgan you are refused exactly when \(\neg a \wedge \neg w\), under 15 and alone. Spreadsheets obey the same law: =NOT(OR(B2>100, C2="late")) and =AND(B2⇐100, C2<>"late") filter the same rows, and the second is easier for a colleague to read.

Engineering: fewer gates. Each gate costs chip area, power and a few picoseconds of delay. The absorption example above turned \((p \wedge q) \vee (p \wedge \neg q)\) (two ANDs, a NOT and an OR, four gates) into \(p\) (no gates: a wire). Circuit synthesis tools apply exactly these laws, millions of times, to every chip design.

Computing. Database query optimisers rewrite WHERE NOT (status = 'done' OR archived) into status <> 'done' AND NOT archived so that each part can use an index; compilers push negations inward the same way. The Watch out box above is the bug you get when a human does the rewrite by hand and forgets to flip the or.

"\(x > 3\)" is not a proposition, because its truth depends on \(x\). Yet mathematics and code are full of statements like "every element of the list is positive", "some user has no password", "for every input there is a matching output". Propositional logic, with its fixed T/F atoms, cannot express any of these. We need statements with variables in them, and a way to say "all" and "some".

A predicate is a proposition with a hole in it, a function that returns a boolean: is_even(n). Fill the hole with a value and you get a proposition. A quantifier fills the hole differently: instead of naming one value, it makes a claim about all values or about at least one. In code, the universal quantifier is all(…​) and the existential quantifier is any(…​).

Over a finite domain \(\{a_1, \ldots, a_n\}\), quantifiers are just long connectives:

This view explains vacuous truth again: over an empty domain, a "for all" is an empty "and", which is true (the identity for \(\wedge\)), and a "there exists" is an empty "or", which is false (the identity for \(\vee\)). It is the same reason the empty sum is 0 and the empty product is 1.

Lines three and four are negations of each other, which is the next idea.

To deny "every swan is white" you do not need to show that every swan is non-white. You need one black swan. To deny "some student passed" you need to show that every student failed. That is De Morgan’s law again, applied to the long "and" and the long "or":

Take the statement "every request gets a response within 2 seconds of being sent". With \(R\) the set of requests and \(S\) the set of responses:

What does a monitoring alert need to detect, i.e. what is the negation?

In English: "there is some request such that every response either does not answer it or arrives more than 2 seconds later". Equivalently: some request was not answered in time. You can also write the final disjunction as a conditional, \(\text{answers}(s,r) \to t(s) - t(r) > 2\), "any response that answers it is late".

Compare, over the integers, Try it: Now play ∃∀; Play the ∀∃ game.

The first says "for every number there is a bigger one": true (take \(y = x + 1\)). The second says "there is one number bigger than every number": false (it would have to be bigger than itself). The only difference is the order. In the first, \(y\) is chosen after \(x\) and may depend on it; in the second, \(y\) must be chosen first, once, and work for all \(x\).

A game helps. Read \(\forall\) as your opponent’s move and \(\exists\) as yours, in left-to-right order. The statement is true if you have a winning strategy. In \(\forall x\, \exists y\), your opponent names \(x\), then you reply: easy. In \(\exists y\, \forall x\), you must commit first, and your opponent picks \(x = y\) to beat you.

Everyday: one counterexample is enough. A dish is safe for a guest with coeliac disease when every ingredient is gluten-free: \(\forall i\, G(i)\). Its negation is \(\exists i\, \neg G(i)\): one ingredient with gluten (soy sauce is the classic hidden one) makes the whole dish unsafe. Allergen labels, "all passengers must have a passport" and "every room has a smoke alarm" are universal claims that a single inspection can refute.

Science and engineering: universal claims and finite tests. A specification such as "for every load up to 5 kN the beam deflects less than 2 mm" is a \(\forall\) statement over infinitely many loads. Testing at 1, 2, 3, 4 and 5 kN gives five instances, not the universal claim; the claim rests on a calculation (a proof) plus a safety factor. Scientific laws have the same shape, which is why one reproducible counterexample outweighs any number of confirmations.

Computing. A foreign-key constraint, "every order belongs to some customer", is \(\forall o\, \exists c\, \text{owns}(c, o)\). The query that finds violations is its negation, \(\exists o\, \forall c\, \neg\text{owns}(c, o)\): an orphan order, written in SQL as NOT EXISTS.

A marketing team wants "customers who bought in 2025 but not in 2026, excluding anyone who unsubscribed". A security team wants "every IP address that appears in both the firewall log and the threat list". A compiler wants "the variables that are live at the end of this block". Each of these is a question about collections: combining them, intersecting them, removing one from another. The language for collections is set theory, and it turns out to be logic wearing different clothes.

A set is a bag of distinct things where order does not matter and duplicates do not count. The only question you can ask of a set is "is this thing in it?" Everything else, including union, intersection and complement, is defined by how it answers that question. And the answer to "is \(x\) in \(A \cup B\)?" is "is \(x\) in \(A\) or is \(x\) in \(B\)?" So each set operation is a logical connective applied to membership.

Two consequences of the definition of subset surprise people. First, \(\varnothing \subseteq A\) for every set \(A\): the condition "every element of \(\varnothing\) is in \(A\)" is vacuously true. Second, \(\in\) and \(\subseteq\) are different relations: \(2 \in \{1, 2\}\) but \(2 \not\subseteq \{1, 2\}\) (2 is not a set of elements of \(\{1,2\}\)); \(\{2\} \subseteq \{1, 2\}\) but \(\{2\} \notin \{1, 2\}\).

A Venn diagram draws the universal set as a rectangle and each set as a region inside it. Shading shows the result of an operation.

Because each operation is a connective in disguise, every law of logic gives a law of sets. Replace \(\vee\) by \(\cup\), \(\wedge\) by \(\cap\), \(\neg\) by complement, \(\mathbf{T}\) by \(U\) and \(\mathbf{F}\) by \(\varnothing\):

A Venn diagram is a good way to discover or check a set identity. To prove one, use the membership argument below, because diagrams with three or more sets get hard to draw correctly and easy to misread.

Prove \(\overline{A \cup B} = \overline{A} \cap \overline{B}\). Try it: De Morgan on a Venn diagram.

The set identity is literally the logic identity, applied to membership.

How many elements are in \(A \cup B\)? Adding \(|A| + |B|\) counts the overlap twice, so subtract it once: Try it: Inclusion–exclusion with counts.

Example: 120 users enabled two-factor authentication, 85 use a passkey, and 40 do both. Then \(|A \cup B| = 120 + 85 - 40 = 165\) users have at least one of the two. This principle of inclusion–exclusion grows to three or more sets in Chapter 24, and becomes the addition rule for probabilities in Chapter 29.

Two constructions build new, bigger sets from old ones.

Everyday: surveys and inclusion–exclusion. Of 30 people at a meeting, 18 drink coffee, 15 drink tea and 7 drink both. Then \(18 + 15 - 7 = 26\) drink at least one, so \(30 - 26 = 4\) want neither: order 4 bottles of water, not 0 and not 30 minus 33. Try it: Coffee, tea, or neither.

Medicine: blood types are subsets. Red cells carry some subset of three antigens, A, B and the Rhesus antigen D. The eight blood types are exactly the \(2^3 = 8\) subsets: O negative is \(\varnothing\), AB positive is \(\{A, B, D\}\). A transfusion of red cells is compatible when the donor’s set is a subset of the recipient’s, because the recipient’s immune system attacks any antigen it lacks. So O negative (\(\varnothing \subseteq\) everything) is the universal donor and AB positive the universal recipient; an A-positive patient (\(\{A, D\}\)) can receive O−, O+, A− or A+, the four subsets of \(\{A, D\}\).

Computing: search and similarity. A search engine stores, for each word, the set of documents containing it (an inverted index). The query cat dog is the intersection of two such sets. Near-duplicate detection compares documents by the Jaccard similarity \(|A \cap B| / |A \cup B|\) of their word sets: "the cat sat on the mat" and "the cat lay on the mat" share 4 of 6 distinct words, a similarity of \(4/6 \approx 0.67\).

"Is less than", "divides", "has the same remainder when divided by 3", "is a prerequisite of", "follows on social media", "is in the same connected component as". Each of these takes two things and answers yes or no. Some behave very differently from others: "same remainder" sorts things into groups, "prerequisite of" puts them in an order, "follows" does neither. To reason about these patterns, and to know which algorithms apply, we need precise names for the properties a relation can have.

A relation is just a set of pairs: the pairs that are related. Draw the elements as dots, and draw an arrow from \(a\) to \(b\) whenever \(a\) is related to \(b\). The properties are then visual: a loop at every dot (reflexive), every arrow paired with a reverse arrow (symmetric), every two-step path having a shortcut (transitive). That dots-and-arrows picture is a directed graph, the subject of Chapter 25.

The canonical example: on the integers, say \(a \sim b\) when \(a\) and \(b\) leave the same remainder on division by 3. Check the three properties: Try it: Same remainder mod 3.

So the integers split into exactly three classes, \(\lbrack 0] = \{\ldots, -3, 0, 3, 6, \ldots\}\), \(\lbrack 1] = \{\ldots, -2, 1, 4, 7, \ldots\}\) and \(\lbrack 2] = \{\ldots, -1, 2, 5, 8, \ldots\}\). This is the "congruence modulo 3" that Chapter 23 builds a whole arithmetic on.

Why does an equivalence relation always partition? Suppose two classes \(\lbrack a]\) and \(\lbrack b]\) share some element \(x\). Then \(x \sim a\) and \(x \sim b\); by symmetry \(a \sim x\), and by transitivity \(a \sim b\). Now any \(y \in [a]\) has \(y \sim a \sim b\), so \(y \in [b]\), and vice versa. So two classes either coincide or are disjoint. Reflexivity ensures every element is in at least one class (its own).

"Divides" on \(\{1, 2, 3, 4, 6, 12\}\) is a partial order: every number divides itself; if \(a \mid b\) and \(b \mid a\) for positive integers then \(a = b\); and divisibility chains. But 4 and 6 are incomparable: neither divides the other. A Hasse diagram draws a poset economically: put larger elements higher, draw a line only for "immediate" relationships, and let reflexivity and transitivity be implied (12 is above 2 via 4 or 6, so no separate 2–12 line is drawn). Try it: Divisors of 12 as a Hasse diagram.

Classify each relation on the given set. Try it: Classify “less than”.

(a) "\(a \le b\)" on the integers. Reflexive (\(a \le a\)). Not symmetric (\(1 \le 2\) but \(2 \not\le 1\)). Antisymmetric (\(a \le b\) and \(b \le a\) force \(a = b\)). Transitive. So: a partial order, in fact a total order.

(b) "\(a < b\)" on the integers. Not reflexive (\(1 \not< 1\)). Antisymmetric (vacuously: \(a < b \wedge b < a\) never happens). Transitive. Neither an equivalence relation nor a partial order; it is a strict order.

(c) "\(x\) and \(y\) are friends" on users. Symmetric, not reflexive by convention, and not transitive (your friend’s friend may be a stranger). Not an equivalence relation, which is why "friend groups" are not well-defined but "connected components" (friends-of-friends-of-…​ chains) are: taking the transitive closure repairs it.

The checks are mechanical enough to code. Note how each property is a quantified statement turned into all():

A function is a relation with one extra rule. A relation \(f \subseteq A \times B\) is a function from \(A\) to \(B\), written \(f : A \to B\), if every \(a \in A\) is related to exactly one \(b \in B\). We then write \(f(a) = b\) instead of \((a, b) \in f\). In quantifier language: \(\forall a \in A\; \exists!\, b \in B\; (a, b) \in f\).

The relation "\(x\) is a square root of \(y\)" on real numbers is not a function from \(y\) to \(x\) (4 has two square roots, \(-1\) has none); the relation \(\{(x, x^2)\}\) is a function. A Python dict is a finite function: each key maps to exactly one value. The full treatment of domain, codomain, range, injective, surjective and inverse functions is in Chapter 11.

Everyday: getting dressed is a partial order. Underwear before trousers, trousers before shoes, socks before shoes; shirt and socks are incomparable, so either order is fine. Any morning routine that respects the order is a topological sort of it, and recipes ("make the sauce while the pasta boils") are the same structure with parallel steps.

Physics: temperature exists because of an equivalence relation. The zeroth law of thermodynamics says that if bodies \(A\) and \(B\) are each in thermal equilibrium with \(C\), they are in equilibrium with each other. Together with symmetry, that is transitivity, so "in thermal equilibrium with" is an equivalence relation. A thermometer works by naming the equivalence classes: a temperature is a label for a class.

Biology and chemistry: classification. "Is a subgroup of" in taxonomy (species, genus, family, …​) is a partial order whose Hasse diagram is a tree. "Has the same molecular formula" is an equivalence relation whose classes group isomers (ethanol and dimethyl ether are both \(\mathrm{C_2H_6O}\)).

Computing. Beyond the sidebar above: version constraints in a package manager compare versions by a total order, while "this commit is an ancestor of that one" in Git is a partial order (two branches' tips are incomparable until merged).