Chapter 1: Propositional Logic

"Contrariwise, if it was so, it might be; and if it were so, it would be; but as it isn't, it ain't. That's logic." — Lewis Carroll, Through the Looking-Glass

Overview

Open any program you have ever written and you will find logic holding it together. Every if, every while, every && and || and !, every guard clause that decides whether to charge a credit card or grant access to a file — each one is a small machine for deciding true or false. When a program has a bug, very often the bug is not in the arithmetic or the data structures. It is in the logic: a condition that says or when it should say and, a negation that pushes the wrong way, an edge case that slips through because two conditions overlap in a way the author never drew out on paper.

Propositional logic is the mathematics of exactly those decisions. It is the oldest and simplest branch of formal logic, and it is also the most immediately useful one for a programmer, because the correspondence with code is almost perfect: a logical proposition is a Boolean expression, a logical connective is a Boolean operator, and a truth table is nothing more than the exhaustive test suite for a Boolean function — every possible input, paired with its output. Master this chapter and you gain two concrete powers. First, you can take a tangled if condition and prove it equivalent to a simpler one, the way you would refactor a tangled function. Second, you can read and write the precise statements that the rest of this book — and the rest of mathematics — is built from. Every theorem we prove in the proof chapters ahead is, at its core, a claim in logic.

This is also where the book's first recurring theme appears: discrete math is the language of computer science. Logic is not a topic you study and set aside. It is the grammar in which conditions, circuits, type rules, database queries, and proofs are all written. We start here because everything else assumes it.

In this chapter, you will learn to:

• Decide whether an English sentence is a proposition, and translate it into symbols.
• Combine propositions with the six connectives and predict the result.
• Build a truth table for any compound proposition, by hand and in code.
• Recognize tautologies (always true), contradictions (always false), and the equivalences that let you rewrite one expression as another.
• Apply De Morgan's laws and the other laws of logic to simplify a real if condition.
• State the satisfiability problem and understand why it sits at the boundary between the easy and the hard — a boundary we will not cross properly until the very end of the book.

Learning Paths

🏃 Fast Track: If Boolean algebra is already second nature, skim 1.1–1.3 to lock in our notation, then concentrate on 1.4 (equivalences and De Morgan's laws) and 1.5 (simplifying conditions), which is where the everyday payoff lives. Read 1.6 for the preview of SAT — it pays off in Chapter 37. Do the ⭐⭐ and ⭐⭐⭐ exercises.

📖 Standard Path: Read in order. Build every truth table yourself before checking ours, and work each 🔄 Check Your Understanding from memory before reading on. The skill being trained is not "knowing the connectives" but fluently translating between English, symbols, code, and truth tables — and that comes only from doing it.

🔬 Deep Dive: After the chapter, prove that the single connective NAND is functionally complete (every truth table can be built from NAND alone), and connect it to why a chip can be manufactured from one kind of gate. The exercise set, Part D, walks you there.

1.1 Why logic? Bugs, conditions, and circuits

Here is a bug. A streaming service wants to grant access to a video if the user is a subscriber, or if the video is free and the user is over thirteen. A developer writes:

if is_subscriber or is_free and age > 13:
    play(video)

It looks right. It reads, in English, almost exactly like the requirement. And it is wrong — not always, but on exactly the inputs that matter. To see why, you need to know that and binds tighter than or, so Python reads the condition as is_subscriber or (is_free and age > 13). That happens to be what we wanted this time. But suppose the requirement had instead been "(subscriber or free) and over thirteen" — an age gate that applies to everyone. Then the same-looking code is_subscriber or is_free and age > 13 is a serious bug: a twelve-year-old subscriber sails right through, because is_subscriber alone makes the whole expression true regardless of age.

The fix is a single pair of parentheses. But knowing where the parentheses go, and being able to prove that your condition means what you intend, requires a precise theory of how and, or, and not combine. Guessing is how a twelve-year-old ends up watching an R-rated film, or how a "deactivated and unpaid" account check accidentally locks out paying customers. Conditions are where requirements meet reality, and they are unforgiving.

The same structures appear one level down, in hardware. A physical AND gate outputs a high voltage exactly when both of its inputs are high; an OR gate, when at least one is. Your processor is, at bottom, millions of these gates wired together, and the rules for combining them are identical to the rules for combining conditions in code. This is not an analogy — it is the same algebra, applied to electrons instead of Booleans. We will see the hardware connection again in Chapter 13, when Boolean algebra gets its own treatment and we go from logic to logic gates.

🔗 Connection. The "language of CS" theme is not a slogan. The same six operators you are about to learn govern: branching in code, gates in silicon, the set operations of Part II, predicates in database WHERE clauses, and the conditions a theorem prover checks. Learn them once, use them everywhere.

💡 Intuition: Think of a compound condition as a little circuit. Inputs (the variables) flow in; the connectives are gates that combine them; one truth value comes out. Logic is the discipline of predicting that output for every possible input at once, instead of testing one input and hoping.

So our plan is to build the theory from the ground up: what counts as a basic true-or-false statement, how to combine such statements, how to compute the result for every input, and finally how to use all of that to simplify real conditions and to ask a question — is there any input that makes this true? — that turns out to be one of the most important questions in all of computer science.

1.2 Propositions and connectives

Logic begins with the smallest unit that can be true or false.

Definition (proposition). A proposition is a declarative statement that is either true or false, but not both.

The "declarative" matters, and so does "either true or false." Consider some examples and non-examples.

• "$7$ is a prime number." — a proposition (it happens to be true).
• "$2 + 2 = 5$." — a proposition (false, but definitely one or the other).
• "Toronto is the capital of Canada." — a proposition (false; the capital is Ottawa).
• "What time is it?" — not a proposition; a question has no truth value.
• "Close the door." — not a proposition; a command is not true or false.
• "$x > 3$." — not a proposition on its own, because its truth depends on $x$. (Statements with variables are the subject of Chapter 2, where they become predicates.)
• "This sentence is false." — not a proposition; if it were true it would be false and vice versa, so it has no consistent truth value. (This is the famous liar paradox, and excluding such self-referential sentences is exactly why the definition says "either true or false, but not both.")

We give propositions short names — propositional variables — usually lowercase letters $p, q, r, s$. So we might let $p$ stand for "it is raining" and $q$ for "the ground is wet." Each variable holds one of two truth values: true ($T$) or false ($F$). In code these are the Booleans True and False; in hardware, high and low voltage; in mathematics, often $1$ and $0$. They are all the same two-element world.

⚠️ Common Pitfall: "This statement is true for me" is not how truth values work in logic. A proposition's truth value is fixed (within one interpretation); logic does not deal in opinions, degrees of belief, or "it depends." Sentences whose truth varies with a free variable, like "$x > 3$," are handled by predicate logic (Chapter 2), not here.

A single proposition is not very interesting. The power comes from building compound propositions out of simpler ones using connectives (also called logical operators).

Definition (connective). A connective is an operator that combines one or more propositions into a new proposition whose truth value is determined entirely by the truth values of its parts.

That last clause — "determined entirely by the truth values of its parts" — is the heart of propositional logic. It means each connective is fully described by what it does to truth values, ignoring all meaning. We never need to know what $p$ says, only whether it is true. This is the same abstraction a compiler makes: if (a && b) cares only about the Booleans a and b, not what they represent. The reward of this abstraction is the third theme of the book — abstraction is the master tool — and it shows up on page one.

Here are the six connectives we use throughout the book. The first is unary (one input); the rest are binary (two inputs).

A few of these need care, because everyday English is sloppier than logic.

Disjunction is inclusive. In logic, $p \lor q$ is true when $p$ is true, when $q$ is true, or when both are true. Everyday "or" is sometimes exclusive ("soup or salad" usually means not both), but the default in mathematics and in or/|| in code is inclusive. When you mean "exactly one," you want exclusive or, $p \oplus q$, which is true precisely when the two differ.

Implication is the slippery one. The statement $p \rightarrow q$ ("if $p$ then $q$") is the connective programmers most often mis-read, so we slow down. Call $p$ the hypothesis (or antecedent) and $q$ the conclusion (or consequent). The rule is:

$p \rightarrow q$ is false in exactly one case: when $p$ is true but $q$ is false. In all three other cases it is true.

The case that surprises people is the two rows where $p$ is false: there, $p \rightarrow q$ is true no matter what $q$ is. We call this vacuously true. The intuition is a promise: "If you ship the order, then I will pay." You break that promise only if the order ships and you don't pay ($p$ true, $q$ false). If the order never ships ($p$ false), you haven't broken anything — the promise simply never came due, so we count it as kept (true). This convention is not arbitrary; it is the only choice that makes the rules of inference in Chapter 3 work, and it is exactly how assert statements and preconditions behave: a precondition that is never triggered is never violated.

💡 Intuition: Read $p \rightarrow q$ as a guarantee that fires only when $p$ holds. "If it's a weekday, the office is open." On the weekend ($p$ false) the statement makes no claim, so it can't be wrong. The only way to catch the guarantee lying is to find a weekday with the office closed.

The biconditional is equality of truth values. $p \leftrightarrow q$ is true exactly when $p$ and $q$ have the same truth value (both true or both false). That is why it corresponds to p == q on Booleans, and why its negation is exactly $\oplus$: "differ" is the opposite of "agree."

Worked example: translating English

Translate "You can run the deploy if you are an admin and either the tests pass or you used the --force flag."

Let $a$ = "you are an admin," $t$ = "the tests pass," $f$ = "you used --force," and $d$ = "you can run the deploy." The sentence says $d$ holds when $a$ holds and ($t$ or $f$). The phrase "X if Y" means $Y \rightarrow X$ (the condition Y is the hypothesis). So:

$$\big(a \land (t \lor f)\big) \rightarrow d.$$

Note the parentheses around $t \lor f$: without them, the precedence rules below would group it wrong, just like the streaming bug in 1.1.

Operator precedence

When parentheses are missing, connectives bind in this order, from tightest to loosest:

$$\neg \;\succ\; \land \;\succ\; \lor \;\succ\; \rightarrow \;\succ\; \leftrightarrow.$$

So $\neg p \lor q \land r$ means $(\neg p) \lor (q \land r)$, and $p \rightarrow q \land r$ means $p \rightarrow (q \land r)$. This mirrors arithmetic, where $\neg$ acts like a unary minus, $\land$ like multiplication, and $\lor$ like addition.

⚠️ Common Pitfall: Relying on precedence to save typing is how the 1.1 bug was born. In proofs we lean on precedence for brevity; in code you should almost always add the parentheses, because the reader of your if statement is human and tired. Clarity beats cleverness.

🔄 Check Your Understanding 1. Which of these are propositions? (a) "$13$ is even." (b) "Please log in." (c) "$n^2 \ge 0$ for the integer $n = -4$." (d) "Is this code thread-safe?" 2. For what truth values of $p$ and $q$ is $p \rightarrow q$ false? 3. Translate into symbols: "The build fails if and only if a test fails or the linter errors." (Use $b$ for build fails, $t$ for a test fails, $\ell$ for the linter errors.)

Answers

1. (a) is a proposition (false). (b) is a command — not a proposition. (c) is a proposition (true; with the specific value $n=-4$ there is no free variable). (d) is a question — not a proposition.
2. Only when $p$ is true and $q$ is false. 3. $b \leftrightarrow (t \lor \ell)$.

1.3 Truth tables

We have described each connective in words. To compute with them — and to prove things — we need a systematic way to list the output for every possible input. That is a truth table.

Definition (truth table). A truth table for a compound proposition lists, in its rows, every possible assignment of truth values to the propositional variables, and gives the resulting truth value of the proposition in each case.

If a proposition has $n$ variables, each variable can be $T$ or $F$ independently, so there are $2^n$ rows. One variable: $2$ rows. Two variables: $4$ rows. Three: $8$. The row count doubles with each new variable — a fact that looks innocent now and comes back to haunt us in 1.6. We will list rows in a fixed convention: count down in binary with $T$ before $F$ in the leftmost column, so the pattern is easy to reproduce.

Here are the truth tables for the six connectives. Commit the shapes to memory; everything else is built from them.

Negation (1 variable, $2$ rows):

The five binary connectives (2 variables, $4$ rows):

Read each column as a definition. Conjunction is true only in the top row (both true). Disjunction is false only in the bottom row (both false). Exclusive or is true exactly where $p$ and $q$ differ. Implication is false only in the second row (true hypothesis, false conclusion) — there is the one case that surprises everyone. The biconditional is true exactly where $p$ and $q$ agree (rows 1 and 4), the complement of $\oplus$.

Building a truth table for a compound proposition

For anything more complicated, you build up column by column, computing sub-expressions before the whole. The method is mechanical, which is exactly why a computer can do it too.

Worked example. Build the truth table for $(p \land q) \rightarrow r$.

Three variables means $2^3 = 8$ rows. We add helper columns for the sub-expression $p \land q$, then combine it with $r$ using the implication rule (false only when the left side is true and $r$ is false).

Notice the result is false in only one row — the second, where $p$ and $q$ are both true but $r$ is false. That makes sense: $(p \land q) \rightarrow r$ is the claim "whenever $p$ and $q$ both hold, $r$ holds," and the only way to break that claim is to find $p$ and $q$ true while $r$ is false.

💡 Intuition: A truth table is the exhaustive test suite for a Boolean function. Where a unit test checks one input, a truth table checks them all — and "all" is finite here, because each variable has only two values. This is the rare, happy case in computing where exhaustive testing is actually possible. Hold onto that feeling; by 1.6 we'll see how quickly it slips away.

Truth tables in code

We can have Python build a truth table for us. The key trick is to enumerate all $2^n$ assignments, which is precisely counting in binary from $0$ to $2^n - 1$. Python's itertools.product gives us exactly those bit patterns.

from itertools import product

def truth_table(fn, names):
    """Print the truth table of a Boolean function fn(*args).
    `names` are the variable names, in the order fn expects them."""
    header = names + [fn.__name__]
    print("  ".join(header))
    for row in product([True, False], repeat=len(names)):
        out = fn(*row)
        cells = ["T" if v else "F" for v in (*row, out)]
        print("  ".join(cells))

# Example: the implication (p and q) -> r
def impl(p, q, r):
    return (not (p and q)) or r

truth_table(impl, ["p", "q", "r"])
# Expected output:
# p  q  r  impl
# T  T  T  T
# T  T  F  F
# T  F  T  T
# T  F  F  T
# F  T  T  T
# F  T  F  T
# F  F  T  T
# F  F  F  T

Two things are worth pausing on. First, we wrote implication as (not (p and q)) or r — there is no -> operator in Python, so we used the equivalence $x \rightarrow y \equiv \neg x \lor y$, which we will prove in the next section. Second, product([True, False], repeat=3) yields the eight triples in exactly our table's order (all-True first, all-False last), which is why the hand table and the code agree row for row. This truth_table function is the very first piece of the Discrete Math Toolkit you will build across this book — we formalize it in the Project Checkpoint at the end of the chapter.

🔄 Check Your Understanding 1. How many rows does the truth table of a proposition with five variables have? 2. In the table for $(p \land q) \rightarrow r$, why is the row $p=T, q=F, r=F$ true even though $r$ is false? 3. Without running it, what would the last line of truth_table's output be if we instead passed def conj(p, q): return p and q with names=["p","q"]?

Answers

1. $2^5 = 32$. 2. Because $p \land q$ is false there (since $q$ is false), and an implication with a false hypothesis is vacuously true regardless of $r$. 3. The rows are printed all-True first to all-False last, so the last line is F F F (for $p=F, q=F$, the conjunction is false).

1.4 Logical equivalences and De Morgan's laws

We now reach the idea that turns logic from a lookup table into an algebra — and the one that lets you refactor a condition with confidence.

Notice something about two of the expressions we have already met. The truth table column for $p \rightarrow q$ reads $T, F, T, T$ down its four rows. Now build the column for $\neg p \lor q$:

The column for $\neg p \lor q$ is also $T, F, T, T$. The two expressions are different strings of symbols, but they produce the identical output on every single input. For the purposes of truth — and therefore for the purposes of code — they are interchangeable.

Definition (logical equivalence). Two compound propositions are logically equivalent, written $A \equiv B$, if they have the same truth value for every assignment of truth values to their variables — that is, if their truth-table output columns are identical.

So we may write $p \rightarrow q \equiv \neg p \lor q$. This single equivalence is why we could implement implication in Python as (not p) or q. Logical equivalence is the formal version of "these two conditions mean the same thing," and proving one is exactly how you justify rewriting a condition in a code review.

Before the catalog of equivalences, two special kinds of proposition deserve names, because the whole theory of equivalence is anchored on them.

Definition (tautology). A tautology is a compound proposition that is true for every assignment of truth values to its variables (its output column is all $T$).

Definition (contradiction). A contradiction is a compound proposition that is false for every assignment (its output column is all $F$). A proposition that is neither — true for some assignments and false for others — is called a contingency.

The cleanest example of each: $p \lor \neg p$ ("$p$ or not $p$") is a tautology — whatever $p$ is, one of $p$, $\neg p$ is true. This is the law of the excluded middle. Its mirror image $p \land \neg p$ ("$p$ and not $p$") is a contradiction — it asks $p$ to be both true and false at once, which never happens. We will meet $p \land \neg p$ again in the proof techniques later in Part I, because proof by contradiction works by deriving exactly such an impossibility.

🔗 Connection. Equivalence and tautology are two views of the same coin: $A \equiv B$ holds if and only if the biconditional $A \leftrightarrow B$ is a tautology. To check an equivalence, you can build one combined truth table and confirm the $\leftrightarrow$ column is all $T$. We use this repeatedly, and Chapter 3 builds the whole theory of valid arguments on top of "this implication is a tautology."

The laws of logic

Just as numbers obey commutative, associative, and distributive laws, so do propositions — and the laws have the same names. Here is the working catalog. Each can be verified by a truth table (you will prove several in the exercises), and together they let you transform expressions without ever drawing a table, the way you simplify algebra by rule.

Most of these match your intuition for and/or. Two deserve special attention.

De Morgan's laws are the most-used equivalences in all of programming, so they get their own spotlight. In words: the negation of an "and" is the "or" of the negations, and the negation of an "or" is the "and" of the negations. Negation flips the connective as it moves inward.

Definition (De Morgan's laws). For any propositions $p$ and $q$, $$\neg(p \land q) \equiv \neg p \lor \neg q \qquad\text{and}\qquad \neg(p \lor q) \equiv \neg p \land \neg q.$$

These are named for the 19th-century logician Augustus De Morgan, who stated them in their modern symbolic form. You use them every time you push a not through a condition. "It is not the case that the user is logged in and verified" becomes "the user is not logged in or not verified" — the connective flips from and to or as the negation distributes.

Strategy first, then the proof. Let's prove the first De Morgan law. We have two ways: (a) the semantic way — build a truth table and check the two columns match; or (b) the syntactic way — manipulate symbols by other known laws. The truth table is the most certain method for a beginner and needs no prior laws, so we use it; it is also how the Toolkit's equivalent function will check equivalences in the Project Checkpoint. The strategy is simply: tabulate both sides over all four rows and confirm the output columns are identical.

Proof that $\neg(p \land q) \equiv \neg p \lor \neg q$. We build a single truth table holding both sides and compare their columns.

The column for $\neg(p \land q)$ is $F, T, T, T$. The column for $\neg p \lor \neg q$ is $F, T, T, T$. They agree in every row, so by the definition of logical equivalence, $\neg(p \land q) \equiv \neg p \lor \neg q$. $\blacksquare$

The second De Morgan law is proved the same way (it is an exercise), or derived from the first by substituting $\neg p$ for $p$ and $\neg q$ for $q$ and applying double negation.

The contrapositive equivalence, $p \rightarrow q \equiv \neg q \rightarrow \neg p$, is the engine of an entire proof technique you will meet later in Part I (proof by contraposition). It says "if $p$ then $q$" is interchangeable with "if not $q$ then not $p$." For example, "if it's raining then the ground is wet" says exactly the same thing as "if the ground is not wet then it is not raining." We will verify it in a worked example below, because it is so easy to confuse with the (invalid!) converse $q \rightarrow p$.

⚠️ Common Pitfall: converse vs. contrapositive. The contrapositive of $p \rightarrow q$ is $\neg q \rightarrow \neg p$, and it is equivalent to the original. The converse is $q \rightarrow p$, and it is generally not equivalent. "If it's raining, the ground is wet" does not let you conclude "if the ground is wet, it's raining" (someone may have run a sprinkler). Swapping hypothesis and conclusion is a real and common reasoning bug — Chapter 3 names it "affirming the consequent."

Proving an equivalence by the algebra of logic

The truth-table method always works, but it costs $2^n$ rows. With many variables, it is faster to manipulate symbols using the laws — the way you simplify $2(x+3) - 6$ to $2x$ without plugging in numbers. Each step cites a law, and because every law is an equivalence, the start and end are equivalent.

Worked example. Show that $\neg(p \rightarrow q) \equiv p \land \neg q$ using the laws.

Strategy first. We have no direct law for negating an implication, so the move is: first rewrite the implication using the Implication law to turn $\rightarrow$ into $\lor$ and $\neg$, then push the outer negation inward with De Morgan, then clean up with double negation. "Rewrite arrows into and/or/not, then apply De Morgan" is the standard recipe for any negation problem.

Proof. $$ \begin{aligned} \neg(p \rightarrow q) &\equiv \neg(\neg p \lor q) && \text{(Implication law)}\\ &\equiv \neg(\neg p) \land \neg q && \text{(De Morgan's law)}\\ &\equiv p \land \neg q && \text{(Double negation)}. \end{aligned} $$ Each line is an equivalence by the cited law, so the first and last are equivalent: $\neg(p \rightarrow q) \equiv p \land \neg q$. $\blacksquare$

This result is worth remembering on its own: the only way an implication fails is hypothesis-true, conclusion-false — which is exactly $p \land \neg q$. We read that off the truth table in 1.3; now we have derived it algebraically. Two methods, one answer — that is theme four, computation and proof are complementary, in miniature: the truth table computes the fact on all four rows; the algebra proves it by rule.

🔄 Check Your Understanding 1. Use De Morgan's laws to rewrite, with the negation pushed all the way in: $\neg(a \lor (b \land c))$. 2. Is $p \rightarrow q$ equivalent to its converse $q \rightarrow p$? Give a one-row reason. 3. Classify each as tautology, contradiction, or contingency: (a) $p \lor \neg p$, (b) $(p \land q) \land \neg p$, (c) $p \rightarrow q$.

Answers

1. $\neg(a \lor (b \land c)) \equiv \neg a \land \neg(b \land c) \equiv \neg a \land (\neg b \lor \neg c)$. 2. No. Take $p=F, q=T$: then $p \rightarrow q$ is $T$ but $q \rightarrow p$ is $F$, so they differ. 3. (a) tautology; (b) contradiction (it requires $p$ and $\neg p$ both); (c) contingency (true in three rows, false in one).

1.5 Simplifying conditions: the programmer's payoff

Now we cash in. The laws of logic are refactoring rules for Boolean expressions — and unlike a hopeful refactor, each one is a proven equivalence, so applying it cannot change behavior. This is the second theme of the book made concrete: proofs guarantee correctness. "I simplified the condition and the tests still pass" tells you the new code is right on the cases you tested; an equivalence proof tells you it is right on every case.

Example: untangling a guard

A code reviewer finds this guard:

if not (user.is_active and user.has_paid):
    deny_access()

A teammate proposes rewriting it as if not user.is_active or not user.has_paid:. Is that safe? Let $a$ = user.is_active, $h$ = user.has_paid. The original condition is $\neg(a \land h)$; the proposal is $\neg a \lor \neg h$. By De Morgan's first law, $\neg(a \land h) \equiv \neg a \lor \neg h$ — they are logically equivalent, so the rewrite is provably safe. Either form is fine; pick the one that reads more clearly to your team. (Often the De Morgan'd version reads better: "deny access if the user is not active, or has not paid.")

Example: a condition that collapses

Consider this real-looking mess, perhaps assembled by successive edits:

if (user.is_admin) or (user.is_admin and user.mfa_enabled):
    grant_root()

Let $a$ = is_admin, $m$ = mfa_enabled. The condition is $a \lor (a \land m)$. By the absorption law, $a \lor (a \land m) \equiv a$. The entire mfa_enabled check is dead code — the condition is just if user.is_admin:. That might be a harmless redundancy, or it might be a security bug: if the intent was to require MFA for admins, the code does not do that, and absorption is what exposes the gap. Simplification is not only about tidiness; reducing a condition to its essence reveals what it actually tests.

🔗 Connection — short-circuit evaluation. Real languages evaluate and/or left to right and stop early. In Python, a and b never evaluates b if a is false (the answer is already settled, by the domination law $F \land x \equiv F$); a or b skips b if a is true (by $T \lor x \equiv T$). This is not just an optimization — it changes behavior, and you exploit it constantly: if user is not None and user.is_admin: is safe precisely because the left side guards the right from a crash. The order of operands matters in code in a way it does not in pure logic, where $\land$ is commutative. That gap between the mathematics and the machine is worth respecting.

⚠️ Common Pitfall: Logical equivalence ignores side effects and evaluation order; running code does not. $p \land q \equiv q \land p$ as propositions, but swapping the operands of and in code can change whether the program crashes (if q has a side effect or can throw). When you refactor a condition, preserve the guarding order even though the logic says you may swap. Equivalence is about truth values, not about execution.

A worked simplification

Simplify the condition $(p \land q) \lor (p \land \neg q)$ and say in English what it tests.

Strategy first. Both terms share the factor $p$. Pull it out with the distributive law (used in reverse — "factoring"), and the leftover is a tautology that vanishes by the negation and identity laws. "Factor the common term, then collapse the $q \lor \neg q$" is the standard move.

$$ \begin{aligned} (p \land q) \lor (p \land \neg q) &\equiv p \land (q \lor \neg q) && \text{(Distributive, factoring out } p\text{)}\\ &\equiv p \land T && \text{(Negation law: } q \lor \neg q \equiv T\text{)}\\ &\equiv p && \text{(Identity law)}. \end{aligned} $$

So the whole condition is just $p$: the $q$ was irrelevant all along. In code, a guard like (is_paid and is_eu) or (is_paid and not is_eu) is simply is_paid — the region check does nothing, which is either a simplification win or a bug you just found. This is the payoff in one line: simplification turns "what does this condition do?" from a guess into a derivation.

🔄 Check Your Understanding 1. Use a law to simplify if user.is_banned or (user.is_banned and over_quota):. Which law, and to what? 2. Rewrite not (a or b or c) with all negations pushed in. 3. Why might p and q and q and p behave differently in a program even though $p \land q \equiv q \land p$?

Answers

1. Absorption: $b \lor (b \land q) \equiv b$, so the condition is just if user.is_banned:. 2. By De Morgan (applied twice), $\neg(a \lor b \lor c) \equiv \neg a \land \neg b \land \neg c$. 3. Short-circuit evaluation: if evaluating one operand has a side effect or can raise an error, the order in which they are tested changes the program's behavior, even though their truth values are the same.

1.6 Satisfiability: the first hard problem (a preview)

We end with a question that looks modest and turns out to be one of the deepest in computer science.

Throughout this chapter, given a proposition, we asked "what is its truth value on each input?" Now turn the question around. Given a compound proposition, we ask: is there any assignment of truth values to the variables that makes the whole thing true?

Definition (satisfiability). A compound proposition is satisfiable if there exists at least one assignment of truth values to its variables that makes it true. An assignment that does so is a satisfying assignment. A proposition with no satisfying assignment is unsatisfiable — equivalently, a contradiction.

This is not an idle question. An enormous range of practical problems are really satisfiability questions in disguise:

• Configuration and dependencies. "Can I install these packages so that every dependency is met and no two conflicting versions are both selected?" Package managers literally encode this as a satisfiability problem and hand it to a SAT solver.
• Hardware and software verification. "Is there any input that drives this circuit into a forbidden state?" If the proposition "reaches a bad state" is unsatisfiable, the design is proven safe — a proof over all inputs at once.
• Scheduling and constraints. "Can these exams be assigned to time slots with no student double-booked?" Encode each constraint as a clause; a satisfying assignment is a valid schedule.

Here is the unsettling part. We can answer satisfiability by brute force: build the truth table and look for a single $T$ in the output column. With $n$ variables that is $2^n$ rows. For $n = 20$ that's about a million rows — instant. For $n = 60$ it is about $10^{18}$ rows — more than a modern computer can check before the sun burns out. The doubling we shrugged at in 1.3 ("each variable doubles the rows") is, viewed from here, an exponential wall. And nobody on Earth currently knows a method that is guaranteed to be dramatically faster than brute force on every input.

🚪 Threshold Concept — easy to check, maybe hard to find. Notice the asymmetry. If someone hands you a satisfying assignment, you can verify it in moments: plug it in, evaluate, done — a truth-table evaluation of a single row. But finding one, with no hint, may require searching an exponential space. "Easy to verify, seemingly hard to solve" is the exact signature of the most important open problem in computer science, P vs. NP, and SAT is its emblem. The Cook–Levin theorem (Chapter 37) shows SAT is NP-complete: it is, in a precise sense, as hard as every problem whose solutions are easy to check. The little question "is this if condition ever true?" is a doorway to the boundary of what computers can do efficiently. Once you see that boundary, you cannot unsee it.

We are not going to solve P vs. NP here — nobody has, and there is a million-dollar prize waiting if you do. The point of meeting SAT now is perspective: the same truth tables that make a two-variable condition trivial become an exponential monster at sixty variables, and that tension between small and easy and large and intractable runs through the entire book. We pick the thread back up with full machinery in Chapter 37; for now, simply notice that you have already met the world's most famous hard problem, and it is built from nothing but the $\neg$, $\land$, and $\lor$ you learned in 1.2.

🔗 Connection. SAT also closes a loop with this chapter: a proposition is a tautology exactly when its negation is unsatisfiable. So "is this a tautology?" and "is this satisfiable?" are two faces of the same coin — checking validity (Chapter 3) reduces to checking satisfiability, which is why SAT solvers double as automated theorem provers.

🔄 Check Your Understanding 1. Is $p \land \neg p$ satisfiable? Is $p \lor \neg p$? Justify each in one sentence. 2. Roughly how many truth-table rows would you check to test satisfiability of a proposition with $30$ variables? Is that feasible? 3. Explain the link: "$A$ is a tautology" is equivalent to "____ is unsatisfiable."

Answers

1. $p \land \neg p$ is unsatisfiable (it is a contradiction — false in both rows). $p \lor \neg p$ is **satisfiable** (in fact a tautology — true in every row, so certainly some row). 2. $2^{30} \approx 1.07 \times 10^9$, about a billion rows — feasible for a fast computer (seconds to minutes), though it is already where naive brute force starts to strain; $2^{60}$ would not be. 3. "$\neg A$ is unsatisfiable" — if $A$ is always true, then $\neg A$ is always false, i.e. has no satisfying assignment.

Project Checkpoint: starting logic.py in the Toolkit

Across this book you will build one Python package, dmtoolkit, one piece per chapter. By the capstone it will be a small but genuine discrete-mathematics library. We begin where the book begins: with logic. The module logic.py (grown across Chapters 1–3) starts with three functions, and we can implement all three now, because each is just a disciplined walk over a truth table.

The core idea — and the reason logic is so amenable to code — is that a compound proposition is just a Python function returning a bool, and "every assignment of truth values" is exactly itertools.product([True, False], repeat=n). With that, a tautology is a function whose output is True on all assignments, and an equivalence is two functions that agree on all assignments.

Create dmtoolkit/logic.py and add:

from itertools import product

def truth_table(fn, names):
    """Return the truth table of fn as a list of (assignment_tuple, output) rows."""
    rows = []
    for assignment in product([True, False], repeat=len(names)):
        rows.append((assignment, fn(*assignment)))
    return rows

def is_tautology(fn, n):
    """True iff the n-ary Boolean function fn is true on every assignment."""
    return all(fn(*a) for a in product([True, False], repeat=n))

def equivalent(f, g, n):
    """True iff n-ary Boolean functions f and g agree on every assignment."""
    return all(f(*a) == g(*a) for a in product([True, False], repeat=n))

# Confirm De Morgan's first law (proved in 1.4) on all 4 assignments:
lhs = lambda p, q: not (p and q)
rhs = lambda p, q: (not p) or (not q)
print(equivalent(lhs, rhs, 2))
# Expected output:
# True

The printed True is the computational twin of our truth-table proof in 1.4: where the proof checked all four rows by hand and reasoned that they must match, equivalent checks the same four rows mechanically. Neither replaces the other — equivalent cannot tell you why the law holds, and a proof cannot run on a million examples in a second — but together they are how a working mathematician-programmer gains confidence: test broadly with code, then prove to be sure. That is theme four of the book, now executable.

How this builds toward the capstone: is_tautology is the seed of a tautology checker, and "is the negation unsatisfiable?" (from 1.6) connects it to SAT; in Chapter 2 we extend logic.py to predicates over finite domains, and in Chapter 3 to checking the validity of arguments — at which point your logic.py can verify a chain of reasoning, not just a single formula. The whole package inventory lives in Appendix I.

Summary

Propositional logic is the algebra of statements that are true or false. Reference recap:

Core objects

The six connectives (binary ones false/true as marked):

Precedence (tightest first): $\neg \succ \land \succ \lor \succ \rightarrow \succ \leftrightarrow$.

Most-used equivalences

• De Morgan: $\neg(p \land q) \equiv \neg p \lor \neg q$; $\neg(p \lor q) \equiv \neg p \land \neg q$.
• Implication: $p \rightarrow q \equiv \neg p \lor q$. Negated implication: $\neg(p \rightarrow q) \equiv p \land \neg q$.
• Contrapositive: $p \rightarrow q \equiv \neg q \rightarrow \neg p$ (the converse $q \rightarrow p$ is not equivalent).
• Distributive (factoring): $p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$ and dual.
• Absorption: $p \lor (p \land q) \equiv p$; $p \land (p \lor q) \equiv p$.
• Negation/Identity: $q \lor \neg q \equiv T$; $p \land T \equiv p$.

Key facts

• $A \equiv B$ iff $A \leftrightarrow B$ is a tautology.
• $A$ is a tautology iff $\neg A$ is unsatisfiable; $A$ is a contradiction iff it is unsatisfiable.
• A truth table has $2^n$ rows; this doubling is feasible for small $n$ but becomes the exponential wall behind SAT and P vs. NP.

Toolkit added (logic.py): truth_table(fn, names), is_tautology(fn, n), equivalent(f, g, n).

Spaced Review

Retrieval keeps knowledge available. This is Chapter 1, so these questions revisit this chapter's ideas — answer from memory before checking, and expect them to resurface (alongside Chapter 2) in Chapter 3's review.

1. State both De Morgan's laws from memory, in symbols.
2. In which single row is $p \rightarrow q$ false? Why does that make $\neg(p \rightarrow q) \equiv p \land \neg q$?
3. What is the difference between the converse and the contrapositive of $p \rightarrow q$, and which one is logically equivalent to it?
4. A proposition has $4$ variables. How many truth-table rows? How many would a $40$-variable proposition have, and what does that illustrate about SAT?
5. Give the law that justifies simplifying $a \lor (a \land b)$, and state the result.

Answers

1. $\neg(p \land q) \equiv \neg p \lor \neg q$ and $\neg(p \lor q) \equiv \neg p \land \neg q$.
2. False only when $p$ is true and $q$ is false; that single failing row is precisely the assignment making $p \land \neg q$ true, so the negation of the implication equals $p \land \neg q$. 3. The converse is $q \rightarrow p$ (swap), the contrapositive is $\neg q \rightarrow \neg p$ (swap and negate both); the contrapositive is equivalent to the original, the converse is not. 4. $2^4 = 16$ rows; a $40$-variable proposition has $2^{40} \approx 1.1 \times 10^{12}$ rows — over a trillion, illustrating that brute-forcing satisfiability is exponential and quickly infeasible. 5. The absorption law, $a \lor (a \land b) \equiv a$.

What's Next

Propositional logic can say "it is raining" and "the ground is wet," but it cannot say "every even number greater than two is a sum of two primes," or "there exists a key that decrypts this message." The moment a statement quantifies over a collection — for all, there exists — we need more expressive machinery. Chapter 2 introduces predicate logic and quantifiers, which add variables and the symbols $\forall$ ("for all") and $\exists$ ("there exists") to everything you just learned. You will see that quantifiers are the mathematics behind for loops and all()/any(), that negating them is governed by a quantified version of De Morgan's laws, and that they are how we write the preconditions and postconditions a correct program must satisfy. The logic you built here becomes the inner layer of a far more powerful language.