Exercises: Propositional Logic

These exercises build from mechanical warm-ups (translate, tabulate) to full equivalence proofs, code, and modeling. Difficulty: ⭐ foundational, ⭐⭐ intermediate, ⭐⭐⭐ challenging. Worked solutions to the daggered (†) and odd-numbered problems live in the appendix answers-to-selected.md — try each one cold before you peek. Use the same row convention as the chapter ($T$ before $F$ in the leftmost column, counting down in binary), so your tables line up with ours.

Part A — Warm-ups: translate and tabulate (⭐)

1.1 † Decide whether each is a proposition. If it is, give its truth value; if not, say why. (a) "$17$ is prime." (b) "Restart the server." (c) "$n + 1 > n$ for the integer $n = 5$." (d) "Will this query use the index?" (e) "This sentence has five words."

1.2 Translate into symbols, stating your propositional variables. (a) "The deploy succeeds and the alert clears." (b) "Either the cache is warm or the request is slow." (c) "If the token is expired, access is denied." (d) "The account is locked if and only if there were three failed logins."

1.3 † Build the full truth table for $p \oplus q$ (exclusive or) and, in the same table, a column for $\neg(p \leftrightarrow q)$. What do you observe about the two columns, and what equivalence does that suggest?

1.4 Insert the parentheses that operator precedence implies (do not change the meaning, just make the grouping explicit): (a) $\neg p \land q \lor r$, (b) $p \lor q \rightarrow r$, (c) $p \rightarrow q \leftrightarrow r$, (d) $\neg p \rightarrow \neg q \land r$.

1.5 † Build the truth table for $(p \lor q) \land \neg r$. In how many of the eight rows is it true? Describe in one English sentence the condition it expresses.

1.6 Classify each as a tautology, a contradiction, or a contingency by building its truth table: (a) $(p \rightarrow q) \lor (q \rightarrow p)$, (b) $(p \land \neg p) \rightarrow q$, (c) $p \leftrightarrow \neg p$.

Part B — Prove it: equivalences and classifications (⭐⭐)

For each equivalence you may use either method the chapter showed: a truth table (compare the two output columns) or the algebra of logic (cite a law per line). State which you are using.

1.7 † (Scaffolded — fill in the missing steps.) Prove the second De Morgan law, $\neg(p \lor q) \equiv \neg p \land \neg q$, by truth table. Fill the blanks:

Then state the one sentence that finishes the proof (what must be true of the two boxed columns?).

1.8 (Scaffolded — fill in the missing step.) Prove $p \rightarrow q \equiv \neg q \rightarrow \neg p$ (the contrapositive law) using the algebra of logic. Fill the blank line: $$ \begin{aligned} \neg q \rightarrow \neg p &\equiv \neg(\neg q) \lor \neg p && \text{(Implication law)}\\ &\equiv \underline{\hphantom{xxxxxxxx}} && \text{(Double negation)}\\ &\equiv \neg p \lor q && \text{(Commutative law)}\\ &\equiv p \rightarrow q && \text{(Implication law, used in reverse)}. \end{aligned} $$

1.9 † Prove by the algebra of logic that $(p \land q) \rightarrow p$ is a tautology. (Hint: rewrite the implication, then use a De Morgan and a domination/negation law to reach $T$.)

1.10 Prove $p \rightarrow (q \rightarrow p)$ is a tautology, by truth table. In one sentence, say why this matches the slogan "a true conclusion makes an implication true regardless of its hypothesis."

1.11 † Show that $p \leftrightarrow q \equiv (p \land q) \lor (\neg p \land \neg q)$. (This is the "both true or both false" reading of the biconditional. A truth table is cleanest.)

1.12 Prove or disprove: $p \rightarrow (q \land r) \equiv (p \rightarrow q) \land (p \rightarrow r)$. If true, prove it (algebra is shorter than an eight-row table); if false, give the row that breaks it.

Part C — Implement it (⭐⭐)

Write Python for each. Do not run it — hand-trace and include an # Expected output: comment, matching the book's convention (and the chapter's truth_table helper). Keep each under 30 lines.

1.13 † Using the chapter's truth_table(fn, names) (from §1.3), write the function and three lines that print the truth table of $p \oplus q$. Define xor without Python's ^ operator — use the equivalence "$p \oplus q$ is true exactly when $p$ and $q$ differ." Give the expected eight... no — the expected four-row output.

1.14 Write a function is_contradiction(fn, n) that returns True iff the $n$-ary Boolean function fn is false on every assignment. (Mirror the chapter's is_tautology.) Then show, with one call, that lambda p: p and (not p) is a contradiction. State the expected output.

1.15 † Write classify(fn, n) that returns the string "tautology", "contradiction", or "contingency" for an $n$-ary Boolean function. Reuse is_tautology and your is_contradiction from 1.14. Test it on $p \lor \neg p$ and on $p \rightarrow q$; give the expected output for both.

1.16 Write to_int(assignment) that turns a tuple of Booleans like (True, False, True) into the integer it represents in binary ($101_2 = 5$), with the first element as the most significant bit. Explain in one comment line how this connects "the rows of a truth table" to "counting from $0$ to $2^n - 1$."

Part D — Find the error (⭐⭐)

Each argument below is wrong. State precisely which step fails and why — name the law or definition that is misapplied.

1.17 † Claim: $\neg(p \rightarrow q) \equiv \neg p \rightarrow \neg q$. "Proof": "Negation distributes over the arrow, just like it distributes over $\land$ via De Morgan, so we negate the hypothesis and the conclusion." — Find the flaw, and give the correct value of $\neg(p \rightarrow q)$ (from §1.4). Include the single row of a truth table that disproves the bogus claim.

1.18 Claim: "Since $p \rightarrow q$ is true and $q$ is true, $p$ must be true." "Proof": "Implication means $p$ and $q$ rise and fall together." — Name the reasoning bug (the chapter flags it in §1.4 and says Chapter 3 names it formally), and give an assignment of $p, q$ that refutes the conclusion.

1.19 † Claim: the guard if a or b and c: is equivalent to if (a or b) and c:. "Proof": "and and or read left to right, so we group left to right." — Using the precedence rules of §1.2, explain the error and write what Python actually computes. Give one assignment of $a, b, c$ on which the two groupings disagree.

1.20 Claim: "$a \lor (a \land m) \equiv a \land m$, because the $a$ on the left is absorbed into the and." "Proof": a misremembered absorption law. — State the correct absorption law and the correct simplified form, and give a row where the bogus result differs from the truth.

Part E — Model it (⭐⭐ / ⭐⭐⭐)

Translate each real scenario into propositional-logic objects, then answer the question. Define your variables explicitly — half the work is naming the right propositions.

1.21 † (Access control.) A document is viewable when the user is the owner, or the document is public and the user is logged in. Let $o$ = "is owner," $b$ = "doc is public," $l$ = "logged in," $v$ = "viewable." (a) Write $v$ as a compound proposition of $o, b, l$. (b) A teammate codes if o or b and l:. Is the precedence what the spec wants? (c) Give the truth table for your $v$ (eight rows) and circle the rows where an anonymous user (not owner, not logged in) can view.

1.22 (Feature flag.) A new checkout flow is shown when the flag is on and the user is in the test cohort, unless the user has opted out (opting out always hides it). Model "show new checkout" ($s$) in terms of flag ($f$), in_cohort ($c$), and opted_out ($x$). Then simplify your expression with the laws if possible, and say in English what the simplified condition tests.

1.23 † (Alarm logic.) A server raises a page when CPU is high or memory is high, but not during the maintenance window. Let $u$ = "CPU high," $m$ = "memory high," $w$ = "in maintenance window," $g$ = "page." (a) Write $g$. (b) Use De Morgan and distribution to rewrite $g$ with the negation pushed all the way in. (c) Your on-call lead asks: "during maintenance, can we ever page?" Answer from the formula, not from intuition.

1.24 (Package install.) You may install package $A$ only if its dependency $B$ is installed, and you may not install both $A$ and a conflicting package $C$. Model the legal-configuration condition as a single proposition over $A, B, C$ (each variable = "this package is selected"). This is a tiny instance of the satisfiability framing in §1.6 — which you'll formalize in 1.27.

Part F — Conjecture and test, then prove (⭐⭐⭐)

Here computation and proof work together (theme four): use code to gather evidence, then prove the result settled.

1.25 † (NAND is functionally complete — the Deep Dive.) Define the NAND connective $p \uparrow q \equiv \neg(p \land q)$. (a) In Python, write nand(p, q) and use it — and only it — to build functions my_not(p), my_and(p, q), and my_or(p, q). (Hint: $\neg p \equiv p \uparrow p$; then $\land$ is a NAND followed by a NOT; then use De Morgan for $\lor$.) (b) Using the chapter's equivalent, write the three lines that test each of your three functions against Python's not/and/or on all assignments. What output confirms they match? (c) Prove that $\neg p \equiv p \uparrow p$ by a two-row truth table, and that $p \land q \equiv (p \uparrow q) \uparrow (p \uparrow q)$ by a four-row truth table. Conclude in one sentence why "NAND alone can build every connective" — and connect it to why a chip can be manufactured from a single kind of gate (§1.1).

1.26 (How many connectives are there, really?) A binary connective is determined by its output column — a length-$4$ string of $T$/$F$. (a) Argue there are exactly $2^4 = 16$ distinct binary connectives. (b) Write a Python snippet that, conceptually, enumerates all $16$ output columns (you may represent each as a 4-tuple of Booleans). (c) Two of the sixteen are the constant tautology and the constant contradiction. Identify the four-tuple for each, and explain why neither depends on its inputs.

1.27 † (Satisfiability by code, then reason.) Recall first_satisfying(fn, names) from §1.6. (a) For $\phi = (p \lor q) \land (\neg p \lor r) \land \neg q$, hand-trace the brute-force search in the chapter's row order ($T$ first) and report the first satisfying assignment. (b) Now prove, by the chapter's identity "$A$ is a tautology iff $\neg A$ is unsatisfiable," that $p \rightarrow (p \lor q)$ is a tautology by arguing its negation is unsatisfiable. (c) Roughly how many rows would brute-force satisfiability check for a $50$-variable formula, and why does that make the method hopeless at scale (§1.6)?

Part G — Interleaved & synthesis

Chapter 1 is the foundation, so these problems weave together its own threads — translation, truth tables, equivalence, simplification, and SAT — and point forward to where each is used. (From Chapter 3 on, this section will also mix in techniques from earlier chapters.)

1.28 † (Translation → equivalence → code, end to end.) Take the English requirement "deny the request if the user is not authenticated, or is authenticated but lacks the write scope." (a) Translate to a proposition $d$ over $a$ = "authenticated" and $s$ = "has write scope." (b) Simplify $d$ with the laws; what single, cleaner condition results? (c) Write the one-line equivalent call that would confirm your original and simplified forms agree on all assignments, and state its expected output.

1.29 (Sets up Chapter 3.) The chapter notes that "$A \equiv B$ iff $A \leftrightarrow B$ is a tautology" and that checking validity reduces to checking a tautology. Take the argument "If it compiles, it ships; it compiled; therefore it ships." Write the single implication whose being a tautology would certify this argument valid, using $c$ = "compiles," $h$ = "ships." (You are previewing modus ponens; Chapter 3 develops the whole theory of valid arguments on exactly this idea.)

1.30 † (Sets up Chapter 13, Boolean algebra.) In §1.1 we said the laws of logic are identical to the laws of the AND/OR/NOT gates in hardware. Rewrite the distributive law $p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$ using $1$ for $T$, $0$ for $F$, $\cdot$ for $\land$, and $+$ for $\lor$. Which familiar law of arithmetic does it now resemble, and which law of logic has no arithmetic analogue (hint: try $p \lor (q \land r)$)?

1.31 (Sets up Chapter 37, SAT.) Explain, in a short paragraph, the asymmetry the chapter called a threshold concept: why verifying a given satisfying assignment is easy (say what you would compute) while finding one may be hard. Then state the precise sense in which "is this proposition a tautology?" and "is its negation satisfiable?" are the same question.

1.32 (Deep Dive — minimal connective sets.) Building on 1.25, decide for each of the following whether the set is functionally complete (can build every connective). For each "yes," sketch how to build $\neg$ and one of $\land$/$\lor$; for each "no," give the property all expressions in the set share that some connective lacks. (a) $\{\neg, \land\}$. (b) $\{\land, \lor\}$ (no negation). (c) $\{\rightarrow, F\}$ where $F$ is the constant false. (Hint for (b): what is the output of any $\{\land,\lor\}$-expression when every input is $T$?)

Solutions to † and odd-numbered exercises: see appendices/answers-to-selected.md. Reference code for the "implement it" problems is in code/exercise-solutions.py. For each equivalence proof, the rubric rewards: a correctly built truth table or a per-line citation of laws, the two compared columns named explicitly, and a one-sentence conclusion invoking the definition of logical equivalence.