# Lecture 6. Propositional logic

## 6.0 Overview and motivation

In Lecture 4 and Lecture 5 we studied **Boolean algebra**: an algebraic structure with operations $\wedge$, $\vee$, and complement on the two-element set $\{0,1\}$, together with a body of laws (commutativity, distributivity, De Morgan, and the rest). We manipulated expressions the way we manipulate ordinary algebra — by rewriting, factoring, and simplifying.

**Propositional logic** is the *same* machinery seen from a different angle — the angle of *meaning and truth* rather than algebraic manipulation. Instead of bits and gates we now speak of **propositions** (declarative sentences), the **connectives** that glue them together, and the central question: *when is a compound sentence true?* The two subjects are, quite literally, two dialects of one theory. Where Lecture 4 wrote $1$ we now write $T$; where it wrote $x \cdot y = y \cdot x$ we now write $p \wedge q \equiv q \wedge p$. This is not a loose analogy — it is an isomorphism, and §6.9 makes it precise.

Why build a *formal* language for something as ordinary as "and", "or", and "if"? Three reasons, each a theme of the whole course:

- **Precision.** Natural language is ambiguous ("or" can be inclusive or exclusive; "if" is often mistaken for "if and only if"). A formal language forces every sentence to have exactly one structure and exactly one truth value per interpretation.
- **Mechanization.** Once meaning is reduced to a finite table lookup, a *machine* can check whether an argument is valid, whether a circuit meets its specification, or whether a configuration of constraints can be satisfied. This is the birthplace of automated reasoning, SAT solvers, and hardware/software verification.
- **Foundation for proof.** Every proof you will write in Lecture 7 and beyond — direct proof, contraposition, contradiction, cases — is a disciplined way of establishing exactly the *semantic* relationships defined here. You cannot say what a proof *proves* until you can say what its statements *mean*.

We treat propositional logic as a **formal system** in three layers, and this lecture is organized around them:

- **Syntax** (§6.5) — what counts as a legal formula: well-formed formulas, connectives, parenthesization, precedence, parse trees. Pure grammar, no truth involved.
- **Semantics** (§6.6) — how a formula acquires a truth value once we fix the truth values of its atoms: interpretations, the recursive definition of truth, truth tables.
- **Meta-theory** (§6.7–§6.11) — classifying formulas (tautology, contradiction, contingency), testing satisfiability (SAT), deciding when two formulas mean the same thing ($\equiv$), reducing formulas to normal forms (CNF, DNF), and deciding when a sentence *follows from* others ($\models$).

> **Remark (where we stop).** This lecture is about *truth*, decided ultimately by inspecting a truth table. How to **derive** consequences by *rules of inference* (modus ponens, natural deduction) and how to organize those rules into **proof techniques** belongs to Lecture 7. The distinction — semantics ($\models$) versus proof theory ($\vdash$) — is fundamental and is drawn explicitly in §6.12. Keep it in mind throughout: here, nothing is ever "derived"; everything is *computed* or *checked*.

---

## 6.1 Statements and propositions

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

The two possible values form the tiny **truth-value set** $\{\text{True}, \text{False}\}$, written $\{T, F\}$ or $\{1, 0\}$. Whether we currently *know* which value a sentence has is irrelevant; what matters is that it *has* exactly one. "There are infinitely many twin primes" is a perfectly good proposition even though, at the time of writing, no one knows whether it is true.

Consider the sentences a logic course traditionally opens with:

- *"The Dnipro flows into the Black Sea."* — a statement; it happens to be **true**.
- *"The Dnipro flows into the Sea of Azov."* — a statement; it happens to be **false**.
- *"What's the date today?"* — **not** a statement. It is a question; it cannot be assigned $T$ or $F$.

Sentences that are *not* propositions include:

- **questions** — *"What time is it?"*;
- **commands / imperatives** — *"Close the door."*;
- **exclamations** — *"How cold it is!"*;
- **paradoxical self-referential sentences** — *"This sentence is false."* If it were true it would be false, and if false, true; it can be assigned neither value consistently, so it lies outside the realm of propositions altogether. (This is the **Liar paradox**, and the care needed to exclude such sentences is one reason a formal syntax matters.)

**Definition (open sentence).** A sentence containing a free variable whose truth value depends on the value substituted for that variable is an **open sentence** (a **propositional function** or **predicate**).

A subtler case than the ones above is *"$X$ is divisible by 5."* This has no fixed truth value on its own: it depends on $X$. It becomes a genuine proposition only after $X$ is given a concrete value — for $X = 15$ it is true, for $X = 8$ it is false. Propositional logic treats only *closed* sentences with definite truth values; open sentences, together with the quantifiers "for all" ($\forall$) and "there exists" ($\exists$) needed to close them, are the subject of **predicate (first-order) logic**, which the course takes up later.

> **Example 6.1 (classification).** Classify each sentence.
> (a) *"$7$ is a prime number."*
> (b) *"Please pass the salt."*
> (c) *"$n^2 \ge 0$ for the integer $n$."*
> (d) *"Is it raining?"*
> (e) *"$x + 3 = 10$."*
>
> **Solution.** (a) proposition, **true**. (b) **not** a proposition (imperative). (c) proposition, **true** — the variable $n$ is bound by the phrase "for the integer $n$", which quantifies it, so the sentence as a whole makes a definite (true) claim. (d) **not** a proposition (question). (e) **open sentence** — true when $x=7$, false otherwise; a proposition only once $x$ is fixed.

> **Common pitfall.** Do not confuse *"we don't know its truth value"* with *"it has no truth value."* The Goldbach conjecture is a proposition (exactly one of true/false), even though its status is open. By contrast *"$x+3=10$"* genuinely has no truth value until $x$ is supplied — it is a different kind of object, an open sentence.

---

## 6.2 Atomic and compound propositions

**Definition (atom).** An **atom** (**atomic proposition**) is a simple declarative sentence that contains no logical connective and cannot be decomposed into smaller propositions — "a simple narrative sentence." Atoms are the indivisible building blocks of the language. We denote them by **propositional variables**: $p, q, r, s, \dots$ (or $P, Q, R, \dots$).

**Definition (compound proposition).** A **compound** (or **molecular**) **proposition** is one built from atoms using **logical connectives**.

The defining feature of the language is captured by one principle:

**Principle of truth-functionality.** The truth value of a compound proposition is determined **completely** by the truth values of its atoms together with the meanings of its connectives — and by *nothing else*.

Truth-functionality is a genuine restriction, and it is what makes the whole theory computable. It says the connective "and" contributes only a rule for combining truth values; it is blind to *what* the atoms say, whether they are related in meaning, whether one causes the other, or whether they are even about the same topic. The compound *"$2+2=4$ and Kyiv is a city"* is true for exactly the same reason as *"grass is green and snow is white"*: both conjuncts are true. English connectives sometimes smuggle in extra meaning (temporal order in "she opened the door and left"); propositional logic deliberately discards all of that.

> **Example 6.2.** *"Peter was late"* is an atom, say $P$. *"Peter was late and Peter was speeding"* is compound: $P \wedge Q$, where $Q$ is the atom *"Peter was speeding."* The whole sentence carries no truth value of its own beyond what $P$, $Q$, and $\wedge$ supply.

---

## 6.3 Logical connectives

Propositional logic uses five standard connectives. **Negation** is **unary** (applies to one formula); the other four are **binary** (combine two).

| Connective | Symbol | Reads as | Natural-language cues |
|---|---|---|---|
| **Negation** | $\neg p$ | "not $p$" | *not; it is not the case that; fails to* |
| **Conjunction** | $p \wedge q$ | "$p$ and $q$" | *and; but; both … and; yet; although* |
| **Disjunction** | $p \vee q$ | "$p$ or $q$" | *or; either … or* (inclusive) |
| **Implication** | $p \to q$ | "if $p$ then $q$" | *if …, then …; only if; implies; is sufficient for* |
| **Biconditional** | $p \leftrightarrow q$ | "$p$ if and only if $q$" | *iff; exactly when; is necessary and sufficient for* |

Each connective is *defined* by how it computes a truth value; those definitions are the rows of the base truth table in §6.6. Four points of natural-language nuance deserve emphasis now.

**(1) "But" is $\wedge$.** Logically, *"it is raining but the sun is shining"* is just the conjunction $p \wedge q$. English uses "but" to signal contrast or surprise; truth-functionally there is no such thing, and $p \wedge q$ is true precisely when both parts are.

**(2) Disjunction is inclusive.** $p \vee q$ is true when *at least one* of $p, q$ holds, **including when both hold**. English "or" is sometimes **exclusive** ("soup or salad, not both"); that meaning is a *different* connective, **exclusive-or** $p \oplus q$, expressible as

$$
p \oplus q \;\equiv\; (p \vee q) \wedge \neg(p \wedge q) \;\equiv\; (p \wedge \neg q) \vee (\neg p \wedge q).
$$

When a menu says "soup or salad" it means $\oplus$; when a scholarship says "open to students who study mathematics or computer science" it means $\vee$ (a double major still qualifies). Which one is intended is a matter of translation, not of logic.

**(3) Implication is truth-functional and needs no causal link.** $p \to q$ is **false in exactly one case**: antecedent $p$ true and consequent $q$ false. In every other case it is true. In particular, when the antecedent $p$ is false, $p \to q$ is **vacuously true**, regardless of $q$ — *"if the moon is made of cheese, then $2+2=5$"* is a *true* implication. Here $p$ is the **antecedent** (hypothesis) and $q$ the **consequent** (conclusion). Implication captures the pattern "$q$ is guaranteed whenever $p$", not "$p$ causes $q$".

**(4) The four English faces of $p \to q$.** All of the following translate to $p \to q$:
*"if $p$, then $q$"*; *"$p$ only if $q$"*; *"$p$ is sufficient for $q$"*; *"$q$ is necessary for $p$"*; *"$q$ whenever $p$"*; *"$q$ follows from $p$."* The two easy-to-miss ones are "only if" and "necessary": "$p$ only if $q$" does **not** say $q \to p$ — it says that $p$ can hold *only* in circumstances where $q$ also holds, i.e. $p \to q$.

Related to $p\to q$ are three formulas built from the same atoms; distinguishing them is a constant source of error:

- **converse:** $q \to p$;
- **inverse:** $\neg p \to \neg q$;
- **contrapositive:** $\neg q \to \neg p$.

> **Common pitfall (affirming/denying traps).** A conditional is **not** equivalent to its converse or its inverse. *"If it rains, the ground is wet"* ($p\to q$) does **not** entail *"if the ground is wet, it rained"* (converse — the sprinkler could be on) nor *"if it does not rain, the ground is not wet"* (inverse). It **is** equivalent to its contrapositive *"if the ground is not wet, it did not rain"* — a fact we prove in §6.9 and use constantly in Lecture 7.

> **Remark (other connectives).** Two further binary connectives matter in computer science: **NAND** $p \mathbin{\uparrow} q \equiv \neg(p\wedge q)$ and **NOR** $p \mathbin{\downarrow} q \equiv \neg(p \vee q)$. §6.10 shows *every* connective can be expressed with $\{\neg,\wedge,\vee\}$; remarkably, NAND alone (or NOR alone) also suffices, which is why entire chips are built from one gate type.

---

## 6.4 Formalization: from natural language to formulas

**Formalization** (**translation**, **symbolization**) is the act of replacing atoms by variables and connective-words by symbols. It is the first practical skill of the subject and the bridge between messy language and computable logic.

![Formalizing an English sentence into the propositional formula r → w](img/l06_formalize.png)

The method:

1. Identify the **atomic** propositions and assign each a variable. Choose atoms to be *positive* where possible (let $p$ = "the door is open", not "the door is closed"), so that negations show up explicitly.
2. Locate the **connective words** ("and", "or", "if…then", "not", "unless", "only if", …).
3. Determine the **grouping** (scope) — this is the step that requires judgment — and insert parentheses accordingly.

> **Example 6.3 (the "Peter" sentence).** *"Because Peter was late, he was speeding, and therefore he is not a good driver."*
> Atoms: $P$ = "Peter was late", $Q$ = "Peter was speeding", $S$ = "Peter is a good driver".
> The sentence asserts: *if* (Peter's being late led to $Q$) *then* not $S$. Formalized:
>

$$
(P \to Q) \to \neg S.
$$

Translation is not mechanical: cue words guide it, but scope and grouping require reading the sentence's intent. The placement of "not" is especially treacherous.

> **Example 6.4 (scope of negation).**
> *"Not both $p$ and $q$"* $\;=\; \neg(p \wedge q)$ — at least one fails.
> *"Both not $p$ and not $q$"* $\;=\; \neg p \wedge \neg q$ — both fail.
> These are genuinely different formulas: the first is true when $p=T, q=F$, the second is not. (By De Morgan, $\neg(p\wedge q) \equiv \neg p \vee \neg q$, so the first equals "$\neg p$ **or** $\neg q$" — note the *or*.)

> **Example 6.5 ("unless").** *"You will pass unless you cheat."* Read "$A$ unless $B$" as "$A$ if not $B$", i.e. $\neg B \to A$, equivalently $B \vee A$. With $A$ = "you pass", $B$ = "you cheat":
>

$$
\neg B \to A \quad\equiv\quad B \vee A.
$$

> **Example 6.6 ("neither…nor" and "only if").**
> *"Neither $p$ nor $q$"* $= \neg p \wedge \neg q \;\equiv\; \neg(p \vee q)$.
> *"$p$ only if $q$"* $= p \to q$ (not $q \to p$!).
> *"$p$ if $q$"* $= q \to p$.
> *"$p$ if and only if $q$"* $= p \leftrightarrow q$.

> **Example 6.7 (a compound argument to formula).** *"If the program compiles and the tests pass, then we deploy; we did not deploy; the tests passed. So the program did not compile."* Atoms $c$ = "compiles", $t$ = "tests pass", $d$ = "we deploy". Premises: $(c \wedge t)\to d,\; \neg d,\; t$. Conclusion: $\neg c$. (We check whether this argument is valid in §6.11.)

> **Common pitfall (the "and"/"or" reversal after "not").** Everyday speech says "you can't have cake and ice cream" to mean you can have *at most one* — logically $\neg(c \wedge i)$, which is $\neg c \vee \neg i$. The English keeps "and", but the correct paraphrase uses "or". Always translate the *meaning*, then let De Morgan reconcile it with the words.

---

## 6.5 Syntax: well-formed formulas

Syntax is grammar with truth deliberately set aside. Before we can ask what a formula *means*, we must fix exactly which strings of symbols *are* formulas. This matters for the same reason a compiler has a grammar: only well-formed input can be assigned a meaning, and the meaning must be *unambiguous*.

**Definition (well-formed formula).** The **well-formed formulas (WFFs)** of propositional logic over a set of propositional variables are defined by **recursion**:

1. **(base)** Every propositional variable $p, q, r, \dots$ is a WFF (an atom).
2. **(negation)** If $\varphi$ is a WFF, then $(\neg\varphi)$ is a WFF.
3. **(binary)** If $\varphi$ and $\psi$ are WFFs, then $(\varphi \wedge \psi)$, $(\varphi \vee \psi)$, $(\varphi \to \psi)$, and $(\varphi \leftrightarrow \psi)$ are WFFs.
4. **(closure)** Nothing else is a WFF.

Clause 4 is essential: it says the WFFs are the *smallest* set closed under 1–3. This is what licenses the two most important tools of the subject — proof by **structural induction** and definition by **structural recursion**.

Thus $((p \to q) \wedge (\neg r))$ is well-formed, while $p\,q\to$, $\;\wedge p$, and $(p \to \to q)$ are not.

> **Remark (fully parenthesized vs. readable).** The definition above puts parentheses around *every* application, which makes the theory clean but the formulas ugly. In practice we drop the outermost parentheses and the parentheses around negation, and we use **precedence** and **associativity** conventions to reinsert the rest.

**Precedence and associativity.** From *tightest* binding (evaluated first) to *loosest*:

$$
\neg \;>\; \wedge \;>\; \vee \;>\; \to \;>\; \leftrightarrow
$$

Binary connectives associate to the **right**, so $p \to q \to r$ abbreviates $p \to (q \to r)$. Under these rules,

$$
\neg p \vee q \to r \quad\text{abbreviates}\quad (((\neg p) \vee q) \to r).
$$

> **Common pitfall (association of $\to$).** Right-association is a *convention for abbreviation*, not a logical law: $(p \to q) \to r$ and $p \to (q \to r)$ are **not** equivalent. Their truth tables differ:
>
> | $p$ | $q$ | $r$ | $(p\to q)\to r$ | $p\to(q\to r)$ |
> |:--:|:--:|:--:|:--:|:--:|
> | F | F | F | F | T |
> | F | F | T | T | T |
> | F | T | F | F | T |
> | F | T | T | T | T |
> | T | F | F | T | T |
> | T | F | T | T | T |
> | T | T | F | F | F |
> | T | T | T | T | T |
>
> The columns disagree in rows 1 and 3. When in doubt, **write the parentheses**.

### Parse trees and the main connective

Every WFF corresponds to a unique **parse tree** (**syntax tree**): leaves are atoms, internal nodes are connectives, and each connective's children are the trees of its immediate subformulas. The connective at the **root** — the one applied *last* — is the **main connective**. Identifying the main connective is *the* key step in reading and evaluating a formula, because it tells you the outermost structure.

![Parse tree of (p ∧ q) → ¬r, with the main connective at the root](img/l06_parse_tree.png)

> **Example 6.8.** The parse tree of $((p \to q) \wedge (\neg r))$:
>
> ```
>            ∧            ← main connective
>          /   \
>         →     ¬
>        / \     \
>       p   q     r
> ```
>
> The main connective is $\wedge$; its left subtree is $p \to q$ and its right subtree is $\neg r$. Contrast:
>
> - In $(P \to Q) \to \neg S$ the main connective is the **second** $\to$ (left subtree $P\to Q$, right subtree $\neg S$).
> - In $\neg(p \wedge q)$ the main connective is $\neg$, applied to the whole conjunction.
> - In $\neg p \wedge q$ the main connective is $\wedge$ (because $\neg$ binds tighter): left subtree $\neg p$, right subtree $q$.

### Unique readability

The convenience of precedence rules rests on a theorem that is easy to take for granted and surprisingly delicate to prove: a well-formed formula can be parsed in **exactly one** way. Without this, "the main connective" and "the truth table" would not even be well defined.

**Theorem 6.1 (Unique Readability).** *Every WFF is of **exactly one** of the following forms, and in each case its parts are **uniquely** determined:*
- *an atom $p$; or*
- *$(\neg\varphi)$ for a unique WFF $\varphi$; or*
- *$(\varphi \circ \psi)$ for a unique binary connective $\circ \in \{\wedge,\vee,\to,\leftrightarrow\}$ and unique WFFs $\varphi, \psi$.*

*Proof.* For a string $\sigma$ over our alphabet, let $w(\sigma)$ be the number of "$($" minus the number of "$)$" occurring in $\sigma$. We first establish two lemmas.

**Lemma A.** *Every WFF $\varphi$ satisfies $w(\varphi) = 0$.* We argue by structural induction on $\varphi$. If $\varphi$ is an atom it contains no parentheses, so $w(\varphi) = 0$. If $\varphi = (\neg\alpha)$ then $w(\varphi) = 1 + w(\alpha) + (-1) = w(\alpha) = 0$ by the induction hypothesis. If $\varphi = (\alpha \circ \beta)$ then $w(\varphi) = 1 + w(\alpha) + w(\beta) - 1 = 0 + 0 = 0$. This proves Lemma A.

**Lemma B.** *Every **proper, nonempty prefix** $\pi$ of a WFF $\varphi$ satisfies $w(\pi) > 0$.* (A prefix is proper if it is not all of $\varphi$.) Again by structural induction on $\varphi$.
- *Base.* An atom has length $1$, hence no proper nonempty prefix; the claim holds vacuously.
- *Negation, $\varphi = (\neg\alpha)$.* A proper nonempty prefix $\pi$ is one of: "$($" (then $w=1>0$); "$(\neg$" (then $w=1>0$); "$(\neg\pi'$" where $\pi'$ is a nonempty prefix of $\alpha$. If $\pi'$ is a *proper* prefix of $\alpha$, then $w(\pi) = 1 + w(\pi') > 1 > 0$ by the induction hypothesis; if $\pi' = \alpha$ (the whole thing), then $w(\pi) = 1 + w(\alpha) = 1 + 0 = 1 > 0$ by Lemma A.
- *Binary, $\varphi = (\alpha \circ \beta)$.* Enumerate the proper nonempty prefixes: "$($" ($w=1$); "$(\pi'$" with $\pi'$ a proper nonempty prefix of $\alpha$ ($w = 1 + w(\pi') > 1$); "$(\alpha$" ($w = 1+0 = 1$); "$(\alpha\circ$" ($w = 1$); "$(\alpha\circ\pi''$" with $\pi''$ a proper nonempty prefix of $\beta$ ($w = 1 + w(\pi'') > 1$); "$(\alpha\circ\beta$" ($w = 1$). Every case gives $w > 0$.

This proves Lemma B.

**Consequence.** No proper nonempty prefix of a WFF is itself a WFF, since a WFF has $w = 0$ (Lemma A) but such a prefix has $w > 0$ (Lemma B).

Now the theorem. The first symbol of a WFF determines its form: a WFF beginning with a propositional letter is that atom (atoms have length $1$ and no other clause produces a string starting with a letter); a WFF beginning with "$($" followed by "$\neg$" is a negation; a WFF beginning with "$($" followed by anything else is a binary formula. So the three forms are mutually exclusive. For uniqueness within the binary case, suppose $(\alpha \circ \beta) = (\alpha' \circ' \beta')$ as strings. Deleting the leading "$($" gives $\alpha\circ\beta) = \alpha'\circ'\beta')$. The substrings $\alpha$ and $\alpha'$ both begin at the first position, so one is a prefix of the other; if they had different lengths, the shorter would be a proper nonempty prefix of the longer WFF — impossible by the Consequence. Hence $\alpha = \alpha'$, so the connective symbols align, giving $\circ = \circ'$, and therefore $\beta = \beta'$. The negation case is immediate (the inner formula is the unique substring between "$(\neg$" and the matching final "$)$"). ∎

> **Remark.** Theorem 6.1 is the propositional analogue of a *parser* proving its grammar is unambiguous. The proof technique — a numeric invariant ($w$) plus structural induction — is exactly how one reasons about balanced brackets in compilers and about balanced-parenthesis languages in formal language theory. It is why the abbreviation conventions (dropping parentheses, using precedence) are safe: each abbreviation names one and only one fully parenthesized WFF.

---

## 6.6 Semantics: interpretations and truth tables

Syntax says which strings are formulas; **semantics** says what they *mean*. Meaning here is entirely a matter of truth values.

**Definition (interpretation).** An **interpretation** (**truth valuation**, **assignment**) is a function

$$
v : \{\text{propositional variables}\} \to \{T, F\}
$$

assigning a truth value to every atom.

Because the connectives are truth-functional, an interpretation of the atoms *forces* the truth value of every formula built from them. The next theorem makes "forces" precise and rigorous — it is the semantic counterpart of Unique Readability.

**Theorem 6.2 (the valuation extends uniquely).** *For every interpretation $v$ of the atoms there is a **unique** function $\bar v$ from all WFFs to $\{T,F\}$ satisfying:*
1. *$\bar v(p) = v(p)$ for every atom $p$;*
2. *$\bar v((\neg\varphi)) = T$ if $\bar v(\varphi) = F$, and $F$ otherwise;*
3. *$\bar v((\varphi \wedge \psi)) = T$ iff $\bar v(\varphi) = T$ and $\bar v(\psi) = T$;*
4. *$\bar v((\varphi \vee \psi)) = T$ iff $\bar v(\varphi) = T$ or $\bar v(\psi) = T$;*
5. *$\bar v((\varphi \to \psi)) = F$ iff $\bar v(\varphi) = T$ and $\bar v(\psi) = F$, and $T$ otherwise;*
6. *$\bar v((\varphi \leftrightarrow \psi)) = T$ iff $\bar v(\varphi) = \bar v(\psi)$.*

*Proof.* **Existence.** Define $\bar v(\varphi)$ by structural recursion on $\varphi$, using clauses 1–6. By Theorem 6.1 every WFF matches *exactly one* of the forms atom / negation / binary, so exactly one clause applies at each step and the recursion is well defined; its value is computed from the strictly smaller immediate subformulas, so the recursion terminates. The resulting $\bar v$ satisfies 1–6 by construction.

**Uniqueness.** Suppose $f$ and $g$ both satisfy 1–6. We show $f(\varphi) = g(\varphi)$ for all WFFs $\varphi$ by structural induction. If $\varphi$ is an atom, $f(\varphi) = v(\varphi) = g(\varphi)$ by clause 1. If $\varphi = (\neg\alpha)$, then by the induction hypothesis $f(\alpha) = g(\alpha)$, and clause 2 computes $f(\varphi)$ and $g(\varphi)$ from that common value, so they agree. The binary cases are identical, using the induction hypothesis on both immediate subformulas $\alpha,\beta$ and the relevant clause 3–6. Hence $f = g$. ∎

We henceforth write $v$ for both the assignment and its extension $\bar v$, and introduce the satisfaction symbol.

**Definition (satisfaction, model).** For an interpretation $v$ and formula $\varphi$, write

$$
v \models \varphi \quad\text{to mean}\quad \bar v(\varphi) = T,
$$

read "*$v$ satisfies $\varphi$*" or "*$v$ is a **model** of $\varphi$*." We write $v \not\models \varphi$ when $\bar v(\varphi) = F$.

A formula with $n$ distinct atoms has exactly $2^n$ interpretations (each atom independently $T$ or $F$) — these are precisely the rows of its **truth table**.

**The base connective table.** Theorem 6.2's clauses, tabulated with atoms $A, B$:

| $A$ | $B$ | $\neg A$ | $A \wedge B$ | $A \vee B$ | $A \to B$ | $A \leftrightarrow B$ |
|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
| F | F | T | F | F | T | T |
| F | T | T | F | T | T | F |
| T | F | F | F | T | F | F |
| T | T | F | T | T | T | T |

Read the rows as definitions: conjunction is true only when both conjuncts are true; disjunction is false only when both disjuncts are false; implication is false only in the row $A=T, B=F$; the biconditional is true exactly when $A$ and $B$ agree.

> **Remark (row ordering).** We list rows with $F$ before $T$, reading each row as a binary number with $F=0, T=1$ counting upward ($00, 01, 10, 11$). Any fixed order works; consistency is what matters, and we keep this one throughout the lecture.

**Building a truth table.** To evaluate a compound formula, introduce one column per **subformula**, ordered by the parse tree (atoms first, main connective last). Each column is computed from earlier columns via the base table.

> **Example 6.9.** Truth table for $(p \to q) \wedge \neg q$ (main connective $\wedge$):
>
> | $p$ | $q$ | $p \to q$ | $\neg q$ | $(p \to q) \wedge \neg q$ |
> |:---:|:---:|:---:|:---:|:---:|
> | F | F | T | T | **T** |
> | F | T | T | F | **F** |
> | T | F | F | T | **F** |
> | T | T | T | F | **F** |
>
> The bold final column is the value of the whole formula under each of the $2^2 = 4$ interpretations. It is true only when $p = q = F$.

> **Example 6.10 (three atoms, eight rows).** Truth table for $(p \wedge q) \vee \neg r$:
>
> | $p$ | $q$ | $r$ | $p \wedge q$ | $\neg r$ | $(p\wedge q)\vee\neg r$ |
> |:--:|:--:|:--:|:--:|:--:|:--:|
> | F | F | F | F | T | T |
> | F | F | T | F | F | F |
> | F | T | F | F | T | T |
> | F | T | T | F | F | F |
> | T | F | F | F | T | T |
> | T | F | T | F | F | F |
> | T | T | F | T | T | T |
> | T | T | T | T | F | T |
>
> False exactly when $r=T$ and not both $p,q$ hold.

---

## 6.7 Classifying formulas: tautology, contradiction, contingency

Looking only at the **final column** of a formula's truth table, every formula falls into exactly one of three classes.

**Definitions.**
- A **tautology** is a formula true under **every** interpretation (final column all $T$). Also called **logically valid**; we write $\models \varphi$. Example: $p \vee \neg p$ (*law of excluded middle*).
- A **contradiction** is a formula false under **every** interpretation (final column all $F$). Example: $p \wedge \neg p$.
- A **contingency** is a formula true under some interpretations and false under others. Example: $p \to q$.

![The three classes — tautology, contradiction, contingency — by their truth-table columns](img/l06_classify.png)

These classes partition the set of all formulas: every formula is exactly one of the three. They are linked by negation.

**Theorem 6.3 (tautology–contradiction duality).** *A formula $\varphi$ is a tautology if and only if $\neg\varphi$ is a contradiction; and $\varphi$ is a contradiction if and only if $\neg\varphi$ is a tautology.*

*Proof.* By clause 2 of Theorem 6.2, for every interpretation $v$ we have $\bar v(\neg\varphi) = T$ iff $\bar v(\varphi) = F$. Now: $\varphi$ is a tautology $\iff$ $\bar v(\varphi) = T$ for all $v$ $\iff$ $\bar v(\neg\varphi) = F$ for all $v$ $\iff$ $\neg\varphi$ is a contradiction. The second statement follows by applying the first to $\neg\varphi$ and using double negation ($\neg\neg\varphi \equiv \varphi$, Theorem 6.7). ∎

> **Example 6.11 (verify a tautology).** Show $\models (p \to q) \leftrightarrow (\neg q \to \neg p)$ (a conditional is equivalent to its contrapositive).
>
> | $p$ | $q$ | $p\to q$ | $\neg q\to\neg p$ | $(p\to q)\leftrightarrow(\neg q\to\neg p)$ |
> |:--:|:--:|:--:|:--:|:--:|
> | F | F | T | T | **T** |
> | F | T | T | T | **T** |
> | T | F | F | F | **T** |
> | T | T | T | T | **T** |
>
> The final column is all $T$, so the formula is a **tautology**. (The two inner columns are equal — foreshadowing $p\to q \equiv \neg q\to\neg p$ in §6.9.)

---

## 6.8 Satisfiability and the SAT problem

**Definition (satisfiability).** A formula is **satisfiable** if **at least one** interpretation makes it true — i.e. its final column contains at least one $T$. A formula with no satisfying interpretation is **unsatisfiable**.

![A satisfying assignment (p=T, q=F, r=T) makes every clause true](img/l06_sat.png)

Thus **unsatisfiable = contradiction**, while tautologies and contingencies are satisfiable. The following little theorem ties satisfiability to the classification of §6.7 and to validity, and is the theoretical basis of *refutation*-style reasoning.

**Theorem 6.4 (satisfiability/validity duality).** *A formula $\varphi$ is a tautology if and only if $\neg\varphi$ is unsatisfiable.*

*Proof.* $\varphi$ is a tautology $\iff$ $\bar v(\varphi)=T$ for all $v$ $\iff$ no $v$ has $\bar v(\varphi)=F$ $\iff$ no $v$ has $\bar v(\neg\varphi)=T$ $\iff$ $\neg\varphi$ is unsatisfiable. ∎

**Definition (joint satisfiability).** A *set* of formulas $\{\varphi_1, \dots, \varphi_n\}$ is **jointly (simultaneously) satisfiable** if some single interpretation makes *all* of them true at once — equivalently, if the conjunction $\varphi_1 \wedge \dots \wedge \varphi_n$ is satisfiable.

> **Example 6.12.** Is $(p \vee q) \wedge (\neg p \vee \neg q)$ a tautology, contradiction, or contingency, and is it satisfiable?
>
> | $p$ | $q$ | $p\vee q$ | $\neg p\vee\neg q$ | whole |
> |:--:|:--:|:--:|:--:|:--:|
> | F | F | F | T | **F** |
> | F | T | T | T | **T** |
> | T | F | T | T | **T** |
> | T | T | T | F | **F** |
>
> Mixed final column $\Rightarrow$ **contingency**, hence **satisfiable** (e.g. by $p=F, q=T$). It is true exactly when exactly one of $p, q$ holds — it is the exclusive-or $p \oplus q$.

### The SAT problem

**The Boolean satisfiability problem (SAT)** is the decision problem: *given a propositional formula, is it satisfiable?* A truth table always answers it — build the table, scan for a $T$ — but the table has $2^n$ rows for $n$ atoms, so the naive method becomes hopeless well before $n = 100$ (already $2^{100} \approx 10^{30}$ rows).

SAT is a landmark of theoretical computer science:

- **Cook–Levin Theorem (1971).** SAT was the **first problem proved NP-complete** (Stephen Cook; Leonid Levin independently). Informally, NP-complete problems are the *hardest* problems whose candidate solutions can be *checked* quickly; SAT is a "universal" such problem, in that *every* problem in NP reduces to it. Whether SAT admits a worst-case polynomial-time algorithm is the famous open **P vs. NP** question. No efficient worst-case algorithm is known, and most researchers conjecture none exists.
- **In practice, SAT is astonishingly tractable.** Modern **SAT solvers** based on the **DPLL** procedure (Davis–Putnam–Logemann–Loveland) and its modern extension **CDCL** (conflict-driven clause learning) routinely settle formulas with *millions* of variables. They exploit structure — unit propagation, learning from conflicts, clever branching — rather than enumerating all $2^n$ rows.

**Why CS cares.** SAT (and its close cousins) is the engine behind:

- **Hardware verification / equivalence checking:** to prove two circuits compute the same function, assert they *differ* on some input and let a SAT solver try to satisfy that assertion; unsatisfiable means the circuits are equivalent (this is exactly Theorem 6.4 at industrial scale — recall Lectures 4–5, where circuits *are* Boolean formulas).
- **Model checking** of hardware and software (does this system ever reach a bad state?).
- **Planning, scheduling, and configuration** (encode constraints as clauses; a model is a valid plan/schedule).
- **Program analysis and symbolic execution** (path conditions are formulas; feasibility is satisfiability).

> **Remark (validity is co-SAT).** By Theorem 6.4, testing whether $\varphi$ is a *tautology* is the same as testing whether $\neg\varphi$ is *unsatisfiable*. So tautology-checking (a *validity* question) and SAT (a *satisfiability* question) are two sides of one coin, and a single SAT solver handles both.

---

## 6.9 Logical equivalence

**Definition (logical equivalence).** Two formulas $\varphi$ and $\psi$ are **logically equivalent**, written $\varphi \equiv \psi$, if they have the **same truth value under every interpretation** — identical final columns in the truth table.

Note the level distinction, which trips up many beginners:

> **Common pitfall ($\equiv$ vs. $\leftrightarrow$).** The symbol $\leftrightarrow$ is a **connective**: $\varphi \leftrightarrow \psi$ is *itself a formula*, which may be true under some interpretations and false under others. The symbol $\equiv$ is a **meta-level assertion** *about* two formulas — a statement in our mathematical English, not a symbol inside the logic. The next theorem is the precise bridge between them.

**Theorem 6.5 (equivalence via the biconditional).** *$\varphi \equiv \psi$ if and only if $\varphi \leftrightarrow \psi$ is a tautology. Moreover, $\equiv$ is an **equivalence relation** on formulas: it is reflexive, symmetric, and transitive.*

*Proof.* By clause 6 of Theorem 6.2, for each interpretation $v$, $\bar v(\varphi \leftrightarrow \psi) = T$ iff $\bar v(\varphi) = \bar v(\psi)$. Therefore $\varphi \leftrightarrow \psi$ is a tautology iff $\bar v(\varphi) = \bar v(\psi)$ for *every* $v$, which is exactly the definition of $\varphi \equiv \psi$.

For the equivalence-relation claim, work directly from the definition. *Reflexive:* $\bar v(\varphi) = \bar v(\varphi)$ for all $v$, so $\varphi \equiv \varphi$. *Symmetric:* if $\bar v(\varphi) = \bar v(\psi)$ for all $v$, then $\bar v(\psi) = \bar v(\varphi)$ for all $v$, so $\psi \equiv \varphi$. *Transitive:* if $\bar v(\varphi) = \bar v(\psi)$ and $\bar v(\psi) = \bar v(\chi)$ for all $v$, then $\bar v(\varphi) = \bar v(\chi)$ for all $v$, so $\varphi \equiv \chi$. ∎

The next theorem is what lets us *reason algebraically* — replacing a subformula by an equivalent one anywhere inside a larger formula, exactly as we substitute equals in ordinary algebra.

**Theorem 6.6 (substitution / replacement).** *Let $\chi$ be a formula containing $\varphi$ as a subformula, and let $\chi'$ be the result of replacing that occurrence of $\varphi$ by $\psi$. If $\varphi \equiv \psi$, then $\chi \equiv \chi'$.*

*Proof.* Fix any interpretation $v$; since $\varphi\equiv\psi$ we have $\bar v(\varphi) = \bar v(\psi)$. We show $\bar v(\chi) = \bar v(\chi')$ by structural induction on $\chi$, where $\chi'$ is $\chi$ with the marked occurrence of $\varphi$ replaced by $\psi$.

- If the marked occurrence *is* all of $\chi$, then $\chi = \varphi$ and $\chi' = \psi$, and $\bar v(\chi) = \bar v(\varphi) = \bar v(\psi) = \bar v(\chi')$.
- Otherwise the occurrence lies strictly inside $\chi$, so $\chi$ is not an atom. If $\chi = \neg\alpha$, the occurrence is inside $\alpha$; by the induction hypothesis $\bar v(\alpha) = \bar v(\alpha')$, and clause 2 gives $\bar v(\chi) = \bar v(\chi')$. If $\chi = \alpha \circ \beta$ for a binary $\circ$, the occurrence lies in $\alpha$ or in $\beta$; the induction hypothesis gives $\bar v(\alpha) = \bar v(\alpha')$ and $\bar v(\beta) = \bar v(\beta')$ (the untouched side is unchanged), and the clause for $\circ$ then gives $\bar v(\chi) = \bar v(\chi')$.

Since $v$ was arbitrary, $\chi \equiv \chi'$. ∎

### The equivalence laws

The following laws are the working toolkit. Each is a claim that two formulas are equivalent, and each is verifiable by a truth table (and provable from the others by algebra via Theorem 6.6).

| Law | Form |
|---|---|
| Double negation | $\neg\neg p \equiv p$ |
| Idempotence | $p \wedge p \equiv p$, $\quad p \vee p \equiv p$ |
| Commutativity | $p \wedge q \equiv q \wedge p$, $\quad p \vee q \equiv q \vee p$ |
| Associativity | $(p \wedge q) \wedge r \equiv p \wedge (q \wedge r)$, $\quad (p \vee q) \vee r \equiv p \vee (q \vee r)$ |
| Distributivity | $p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)$, $\quad p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)$ |
| De Morgan | $\neg(p \wedge q) \equiv \neg p \vee \neg q$, $\quad \neg(p \vee q) \equiv \neg p \wedge \neg q$ |
| Identity | $p \wedge T \equiv p$, $\quad p \vee F \equiv p$ |
| Domination | $p \vee T \equiv T$, $\quad p \wedge F \equiv F$ |
| Complement | $p \vee \neg p \equiv T$, $\quad p \wedge \neg p \equiv F$ |
| Absorption | $p \vee (p \wedge q) \equiv p$, $\quad p \wedge (p \vee q) \equiv p$ |
| Implication | $p \to q \equiv \neg p \vee q$ |
| Contrapositive | $p \to q \equiv \neg q \to \neg p$ |
| Biconditional | $p \leftrightarrow q \equiv (p \to q) \wedge (q \to p) \equiv (p \wedge q) \vee (\neg p \wedge \neg q)$ |

> **Remark (this is Lecture 4 again).** These are *exactly* the Boolean-algebra laws of Lecture 4, with $T/F$ in place of $1/0$, $\wedge/\vee$ in place of $\cdot/+$, and $\equiv$ in place of $=$. The map $T\mapsto 1, F\mapsto 0$ carrying $(\{T,F\},\wedge,\vee,\neg)$ to the two-element Boolean algebra $(\{0,1\},\cdot,+,{}')$ is an **isomorphism**: propositional logic *is* the two-element Boolean algebra, read semantically. Everything you proved algebraically there holds here, and vice versa.

Now we discharge the task of actually *proving* the load-bearing laws. Truth tables are the direct method; each is a finite check of "same final columns."

**Theorem 6.7 (double negation).** $\neg\neg p \equiv p$.

*Proof.*

| $p$ | $\neg p$ | $\neg\neg p$ |
|:--:|:--:|:--:|
| F | T | F |
| T | F | T |

The columns $p$ and $\neg\neg p$ are identical. ∎

**Theorem 6.8 (De Morgan's laws).** $\neg(p \wedge q) \equiv \neg p \vee \neg q$ and $\neg(p \vee q) \equiv \neg p \wedge \neg q$.

*Proof.* First law:

| $p$ | $q$ | $p\wedge q$ | $\neg(p\wedge q)$ | $\neg p$ | $\neg q$ | $\neg p\vee\neg q$ |
|:--:|:--:|:--:|:--:|:--:|:--:|:--:|
| F | F | F | T | T | T | T |
| F | T | F | T | T | F | T |
| T | F | F | T | F | T | T |
| T | T | T | F | F | F | F |

Columns $\neg(p\wedge q)$ and $\neg p\vee\neg q$ agree $(T,T,T,F)$. Second law:

| $p$ | $q$ | $p\vee q$ | $\neg(p\vee q)$ | $\neg p$ | $\neg q$ | $\neg p\wedge\neg q$ |
|:--:|:--:|:--:|:--:|:--:|:--:|:--:|
| F | F | F | T | T | T | T |
| F | T | T | F | T | F | F |
| T | F | T | F | F | T | F |
| T | T | T | F | F | F | F |

Columns $\neg(p\vee q)$ and $\neg p\wedge\neg q$ agree $(T,F,F,F)$. ∎

**Theorem 6.9 (distributivity).** $p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)$ and $p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)$.

*Proof.* First law (the second is dual; its table is checked the same way):

| $p$ | $q$ | $r$ | $q\vee r$ | $p\wedge(q\vee r)$ | $p\wedge q$ | $p\wedge r$ | $(p\wedge q)\vee(p\wedge r)$ |
|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|
| F | F | F | F | F | F | F | F |
| F | F | T | T | F | F | F | F |
| F | T | F | T | F | F | F | F |
| F | T | T | T | F | F | F | F |
| T | F | F | F | F | F | F | F |
| T | F | T | T | T | F | T | T |
| T | T | F | T | T | T | F | T |
| T | T | T | T | T | T | T | T |

The two boldfaced-in-comparison columns are both $(F,F,F,F,F,T,T,T)$. ∎

**Theorem 6.10 (implication as disjunction).** $p \to q \equiv \neg p \vee q$.

*Proof.*

| $p$ | $q$ | $p\to q$ | $\neg p$ | $\neg p\vee q$ |
|:--:|:--:|:--:|:--:|:--:|
| F | F | T | T | T |
| F | T | T | T | T |
| T | F | F | F | F |
| T | T | T | F | T |

Columns $p\to q$ and $\neg p\vee q$ agree $(T,T,F,T)$. ∎

This law is the most useful of all: it lets us **eliminate $\to$ entirely** and rewrite any formula using only $\neg, \wedge, \vee$ — the first step of the normal-form algorithm in §6.10.

**Theorem 6.11 (contrapositive).** $p \to q \equiv \neg q \to \neg p$.

*Proof.*

| $p$ | $q$ | $p\to q$ | $\neg q$ | $\neg p$ | $\neg q\to\neg p$ |
|:--:|:--:|:--:|:--:|:--:|:--:|
| F | F | T | T | T | T |
| F | T | T | F | T | T |
| T | F | F | T | F | F |
| T | T | T | F | F | T |

Columns $p\to q$ and $\neg q\to\neg p$ agree $(T,T,F,T)$. ∎

**Theorem 6.12 (biconditional).** $p \leftrightarrow q \equiv (p \to q) \wedge (q \to p) \equiv (p \wedge q) \vee (\neg p \wedge \neg q)$.

*Proof.*

| $p$ | $q$ | $p\leftrightarrow q$ | $p\to q$ | $q\to p$ | $(p\to q)\wedge(q\to p)$ | $p\wedge q$ | $\neg p\wedge\neg q$ | $(p\wedge q)\vee(\neg p\wedge\neg q)$ |
|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|
| F | F | T | T | T | T | F | T | T |
| F | T | F | T | F | F | F | F | F |
| T | F | F | F | T | F | F | F | F |
| T | T | T | T | T | T | T | F | T |

The columns $p\leftrightarrow q$, $(p\to q)\wedge(q\to p)$, and $(p\wedge q)\vee(\neg p\wedge\neg q)$ are all $(T,F,F,T)$. ∎

### Reasoning algebraically

By Theorem 6.6 we may chain equivalences, substituting inside larger formulas, without ever drawing a truth table. This is often far faster.

> **Example 6.13 (simplify $\neg(p \to q)$).**
>

$$
\neg(p \to q) \;\equiv\; \neg(\neg p \vee q) \;\text{(impl., Thm 6.10)}\; \equiv\; \neg\neg p \wedge \neg q \;\text{(De Morgan)}\; \equiv\; p \wedge \neg q \;\text{(double neg.).}
$$

> So "*not ($p$ implies $q$)*" means exactly "*$p$ holds but $q$ fails*" — matching the single $F$-row ($p=T,q=F$) of the implication table.

> **Example 6.14 (simplify $\neg(p \leftrightarrow q)$).** Using Theorem 6.12 then De Morgan and distribution,
>

$$
\neg(p\leftrightarrow q) \equiv \neg\big((p\wedge q)\vee(\neg p\wedge\neg q)\big) \equiv \neg(p\wedge q)\wedge\neg(\neg p\wedge\neg q) \equiv (\neg p\vee\neg q)\wedge(p\vee q).
$$

> That last formula is the exclusive-or of Example 6.12 — so $\neg(p\leftrightarrow q) \equiv p \oplus q$, confirming that "*not equivalent*" means "*exactly one holds*".

> **Example 6.15 (a chain to $T$).** Show $(p \wedge q) \to p$ is a tautology by algebra.
>

$$
(p\wedge q)\to p \equiv \neg(p\wedge q)\vee p \equiv (\neg p\vee\neg q)\vee p \equiv (\neg p \vee p)\vee\neg q \equiv T \vee \neg q \equiv T.
$$

> (Steps: implication; De Morgan; commutativity/associativity; complement; domination.) A formula provably equal to $T$ is a tautology.

---

## 6.10 Normal forms: CNF and DNF

Normal forms are standardized shapes into which *every* formula can be rewritten. They matter because algorithms (SAT solvers, circuit synthesizers, Lecture 4–5 minimization) expect their input in a fixed shape.

**Definitions.**
- A **literal** is an atom or the negation of an atom: $p$ or $\neg p$.
- A **clause** is a disjunction of literals, e.g. $(\neg p \vee q \vee \neg r)$.
- A **term** (**implicant**) is a conjunction of literals, e.g. $(p \wedge \neg q \wedge r)$.
- A formula is in **conjunctive normal form (CNF)** if it is a conjunction of clauses: $\bigwedge_i \big(\bigvee_j \ell_{ij}\big)$ — an "AND of ORs".
- A formula is in **disjunctive normal form (DNF)** if it is a disjunction of terms: $\bigvee_i \big(\bigwedge_j \ell_{ij}\big)$ — an "OR of ANDs".

![CNF as an AND of ORs versus DNF as an OR of ANDs](img/l06_cnf_dnf.png)

> **Remark (which is which).** Mnemonic: **C**NF = **C**onjunction on the outside; **D**NF = **D**isjunction on the outside. CNF is the input format demanded by SAT solvers. DNF makes satisfiability trivial to read off (a DNF is satisfiable iff some term contains no complementary pair $p, \neg p$) but can be exponentially large.

**Theorem 6.13 (existence of normal forms).** *Every propositional formula $\varphi$ is logically equivalent to a formula in DNF and to a formula in CNF.*

*Proof.* We give a constructive proof from the truth table of $\varphi$; let its atoms be $p_1, \dots, p_n$.

**DNF.** If $\varphi$ is a contradiction, then $\varphi \equiv p_1 \wedge \neg p_1$, which is (a degenerate) DNF. Otherwise, for each interpretation $v$ with $v \models \varphi$ (each *true* row), form the **minterm**

$$
m_v \;=\; \ell_1 \wedge \ell_2 \wedge \dots \wedge \ell_n, \qquad \ell_i = \begin{cases} p_i & \text{if } v(p_i)=T,\\ \neg p_i & \text{if } v(p_i)=F. \end{cases}
$$

By construction $m_v$ is true under $v$ and false under every *other* interpretation (any other interpretation disagrees with $v$ on some $p_i$, making that literal $\ell_i$ false, hence the whole conjunction false). Let $D = \bigvee_{v \models \varphi} m_v$. For any interpretation $u$: if $u \models \varphi$ then the disjunct $m_u$ is true, so $D$ is true; if $u \not\models \varphi$ then *every* disjunct $m_v$ (with $v \neq u$, $v\models\varphi$) is false at $u$, so $D$ is false. Hence $D$ has the same truth value as $\varphi$ everywhere: $\varphi \equiv D$, and $D$ is in DNF.

**CNF.** Dually, if $\varphi$ is a tautology then $\varphi \equiv p_1 \vee \neg p_1$ (a degenerate CNF). Otherwise, for each interpretation $v$ with $v \not\models \varphi$ (each *false* row), form the **maxterm**

$$
M_v \;=\; \ell_1 \vee \ell_2 \vee \dots \vee \ell_n, \qquad \ell_i = \begin{cases} \neg p_i & \text{if } v(p_i)=T,\\ p_i & \text{if } v(p_i)=F, \end{cases}
$$

i.e. the *negation* of the pattern of $v$. Then $M_v$ is false under $v$ and true under every other interpretation. Let $C = \bigwedge_{v \not\models \varphi} M_v$. A symmetric argument shows $\varphi \equiv C$, and $C$ is in CNF. (Alternatively: apply the DNF construction to $\neg\varphi$, then negate and push negations in with De Morgan — De Morgan turns the DNF of $\neg\varphi$ into a CNF of $\varphi$.) ∎

**Corollary 6.14 (functional completeness).** *The set of connectives $\{\neg, \wedge, \vee\}$ is **functionally complete**: every truth function of $n$ variables is computed by some formula using only $\neg, \wedge, \vee$.*

*Proof.* A truth function *is* a final column, i.e. the truth table of some formula; Theorem 6.13 produces an equivalent DNF (or CNF), which uses only $\neg, \wedge, \vee$. ∎

> **Remark.** Because $p\wedge q \equiv \neg(\neg p\vee\neg q)$ and $p\vee q\equiv\neg(\neg p\wedge\neg q)$ (De Morgan), even $\{\neg,\wedge\}$ and $\{\neg,\vee\}$ are complete; and a further reduction shows **NAND alone** and **NOR alone** are each complete (the Sheffer stroke, proved complete in print by Sheffer in 1913 and anticipated by Peirce around 1880). This is exactly why digital hardware (Lectures 4–5) can be built entirely from NAND gates.

### Obtaining normal forms by rewriting

The truth-table method of Theorem 6.13 is canonical but produces large formulas. In practice one rewrites, in three stages:

1. **Eliminate $\leftrightarrow$ and $\to$** using $p\leftrightarrow q\equiv(p\to q)\wedge(q\to p)$ and $p\to q\equiv\neg p\vee q$.
2. **Push negations inward** to the atoms using De Morgan and double negation, reaching **negation normal form (NNF)** — where $\neg$ appears only directly on atoms.
3. **Distribute:** for CNF, distribute $\vee$ over $\wedge$; for DNF, distribute $\wedge$ over $\vee$.

> **Example 6.16 (to CNF by rewriting).** Convert $p \to (q \wedge r)$.
>

$$
p\to(q\wedge r) \equiv \neg p\vee(q\wedge r) \;\text{(impl.)}\; \equiv (\neg p\vee q)\wedge(\neg p\vee r)\;\text{(distribute $\vee$ over $\wedge$).}
$$

> The result $(\neg p\vee q)\wedge(\neg p\vee r)$ is in CNF. Meanwhile $\neg p\vee(q\wedge r)$ is already in **DNF** (a disjunction of the one-literal term $\neg p$ and the term $q\wedge r$).

> **Example 6.17 (to DNF by rewriting).** Convert $(p\vee q)\wedge(r\vee s)$.
> Distributing $\wedge$ over $\vee$:
>

$$
(p\vee q)\wedge(r\vee s) \equiv (p\wedge r)\vee(p\wedge s)\vee(q\wedge r)\vee(q\wedge s),
$$

> a DNF with four terms. (This one-formula example already shows how distribution can multiply out: two clauses of size 2 became four terms.)

> **Example 6.18 (NNF via De Morgan).**
>

$$
\neg\big(p\wedge(q\vee\neg r)\big) \equiv \neg p\vee\neg(q\vee\neg r) \equiv \neg p\vee(\neg q\wedge\neg\neg r) \equiv \neg p\vee(\neg q\wedge r).
$$

> Negations now sit only on atoms (NNF), and the result $\neg p\vee(\neg q\wedge r)$ is in DNF.

> **Example 6.19 (canonical forms of $p\to q$).** From its truth table ($T,T,F,T$; false only at $p=T,q=F$):
> - **Canonical DNF** (minterms for the three true rows $FF, FT, TT$): $(\neg p\wedge\neg q)\vee(\neg p\wedge q)\vee(p\wedge q)$.
> - **Canonical CNF** (maxterm for the one false row $TF$): $(\neg p\vee q)$.
>
> The CNF collapses to the single clause $\neg p\vee q$ — precisely Theorem 6.10. This illustrates that canonical forms are *correct* but not *minimal*; minimization (Karnaugh maps, Quine–McCluskey) is the Lecture 4–5 topic.

---

## 6.11 Logical consequence and validity of arguments

We can now make precise what it means for a conclusion to *follow from* premises — the central notion of correct reasoning.

**Definition (logical consequence / entailment).** Given premises $\varphi_1, \dots, \varphi_n$ and a conclusion $\psi$, the premises **entail** $\psi$, written

$$
\varphi_1, \dots, \varphi_n \models \psi,
$$

if **every** interpretation that makes *all* the premises true also makes $\psi$ true. Equivalently: there is no interpretation (**no counterexample**) satisfying all premises yet falsifying $\psi$. Read $\models$ as "*semantically entails*" or "*yields*."

**Definition (valid argument).** An **argument** with premises $\varphi_1,\dots,\varphi_n$ and conclusion $\psi$ is **valid** exactly when $\varphi_1,\dots,\varphi_n \models \psi$; otherwise it is **invalid**, and any interpretation making all premises true and the conclusion false is a **counterexample**.

The following theorem reduces every entailment question to a *tautology* (hence, via Theorem 6.4, to a *satisfiability*) question — the reason a single truth-table procedure decides validity.

**Theorem 6.15 (semantic deduction theorem).** *$\varphi_1, \dots, \varphi_n \models \psi$ if and only if the formula $(\varphi_1 \wedge \dots \wedge \varphi_n) \to \psi$ is a tautology.*

*Proof.* Write $\Phi = \varphi_1 \wedge \dots \wedge \varphi_n$. For any interpretation $v$, $\bar v(\Phi) = T$ iff $v$ satisfies all the premises.

($\Rightarrow$) Assume $\varphi_1,\dots,\varphi_n \models \psi$. Take any $v$. If $\bar v(\Phi) = F$, then $\bar v(\Phi \to \psi) = T$ (implication with false antecedent). If $\bar v(\Phi) = T$, then $v$ satisfies all premises, so by entailment $\bar v(\psi) = T$, whence $\bar v(\Phi \to \psi) = T$. Either way $\Phi\to\psi$ is true under $v$; as $v$ was arbitrary, $\Phi \to \psi$ is a tautology.

($\Leftarrow$) Assume $\Phi \to \psi$ is a tautology. Let $v$ satisfy all premises, so $\bar v(\Phi) = T$. Since $\bar v(\Phi \to \psi) = T$ and the antecedent is true, the consequent $\bar v(\psi) = T$. Thus every model of all premises is a model of $\psi$, i.e. $\varphi_1,\dots,\varphi_n\models\psi$. ∎

**Theorem 6.16 (entailment via unsatisfiability — refutation).** *$\varphi_1, \dots, \varphi_n \models \psi$ if and only if $\{\varphi_1, \dots, \varphi_n, \neg\psi\}$ is jointly unsatisfiable.*

*Proof.* $\varphi_1,\dots,\varphi_n\models\psi$ fails iff some $v$ satisfies all $\varphi_i$ but not $\psi$, i.e. satisfies all $\varphi_i$ *and* $\neg\psi$ — i.e. iff $\{\varphi_1,\dots,\varphi_n,\neg\psi\}$ is jointly satisfiable. Negating both sides gives the claim. ∎

> **Remark (why refutation matters).** Theorem 6.16 is how automated reasoners actually test entailment: to check $\Gamma \models \psi$, throw $\neg\psi$ in with the premises and ask a SAT solver whether the result is unsatisfiable. "Unsatisfiable" *is* the proof. This is the semantic seed of the *proof by contradiction* technique you will meet in Lecture 7.

> **Common pitfall (validity ≠ true premises).** Validity is about *form* — the transmission of truth — not about whether the premises are actually true. A valid argument can have false premises and a false conclusion; validity only guarantees that *if* the premises are true, the conclusion *must* be. Conversely, an argument can have a true conclusion yet be invalid (the conclusion just happens to hold, not because the premises force it).

### Worked validity checks

The truth-table test for $\varphi_1,\dots,\varphi_n\models\psi$: build one table; **scan only the rows where all premises are true**; the argument is valid iff the conclusion is true in *every* such row.

![Validity check: in every row where all premises are true, the conclusion is also true](img/l06_validity_tt.png)

> **Example 6.20 (modus ponens — valid).** *"If it rains, the ground is wet. It rains. Therefore the ground is wet."* Let $p$ = "it rains", $q$ = "the ground is wet". Premises $p\to q,\; p$; conclusion $q$.
>
> | $p$ | $q$ | $p\to q$ | $p$ | $q$ |
> |:--:|:--:|:--:|:--:|:--:|
> | F | F | T | F | F |
> | F | T | T | F | T |
> | T | F | F | T | F |
> | T | T | T | **T** | **T** |
>
> Both premises are true only in the last row, where the conclusion $q$ is also true. No counterexample $\Rightarrow$ **valid**. (Reached purely by inspecting truth values; the *name* "modus ponens" and its use as a derivation rule belong to Lecture 7.)

> **Example 6.21 (affirming the consequent — invalid).** *"If it rains, the ground is wet. The ground is wet. Therefore it rains."* Premises $p\to q,\; q$; conclusion $p$. The row $p=F, q=T$ makes both premises true ($p\to q = T$, $q = T$) yet the conclusion $p = F$. That is a counterexample, so $\{p\to q,\ q\} \not\models p$ — **invalid**, despite its surface resemblance to Example 6.20.

> **Example 6.22 (hypothetical syllogism — valid).** $\{p\to q,\; q\to r\} \models p\to r$.
>
> | $p$ | $q$ | $r$ | $p\to q$ | $q\to r$ | $p\to r$ |
> |:--:|:--:|:--:|:--:|:--:|:--:|
> | F | F | F | T | T | T |
> | F | F | T | T | T | T |
> | F | T | F | T | F | T |
> | F | T | T | T | T | T |
> | T | F | F | F | T | F |
> | T | F | T | F | T | T |
> | T | T | F | T | F | F |
> | T | T | T | T | T | T |
>
> Both premises are true in rows 1, 2, 4, 8; in each of those the conclusion $p\to r$ is true. No counterexample $\Rightarrow$ **valid**.

> **Example 6.23 (modus tollens — valid).** $\{p\to q,\; \neg q\} \models \neg p$.
>
> | $p$ | $q$ | $p\to q$ | $\neg q$ | $\neg p$ |
> |:--:|:--:|:--:|:--:|:--:|
> | F | F | T | **T** | **T** |
> | F | T | T | F | T |
> | T | F | F | T | F |
> | T | T | T | F | F |
>
> Both premises true only in row 1, where $\neg p = T$. **Valid**. Contrast *denying the antecedent* $\{p\to q,\ \neg p\}\models\neg q$: rows $p=F$ make both premises true, but at $p=F, q=T$ the conclusion $\neg q=F$ — a counterexample, so that pattern is **invalid**.

> **Example 6.24 (the deploy argument, Example 6.7).** Premises $(c\wedge t)\to d,\; \neg d,\; t$; conclusion $\neg c$. Suppose all premises hold: $\neg d$ gives $d=F$; $t$ gives $t=T$. If $c$ were $T$, then $c\wedge t = T$, and the first premise would force $d=T$, contradicting $d=F$. So $c=F$, i.e. $\neg c=T$. Every model of the premises satisfies the conclusion — **valid**. (This informal case analysis is exactly what a truth table verifies row by row, and what Theorem 6.15 packages as the tautology $\big((c\wedge t)\to d\big)\wedge\neg d\wedge t\to\neg c$.)

The same truth-table method thus does **triple duty** in this lecture: it *classifies* a single formula (§6.7), it *tests equivalence* of two formulas by comparing final columns (§6.9), and it *tests validity* of an argument by scanning for a counterexample row (§6.11).

---

## 6.12 Semantics versus proof theory (a bridge to Lecture 7)

Everything above is **semantic**: truth values, interpretations, truth tables, and the entailment symbol $\models$. We answered "does $\psi$ follow from $\Gamma$?" by *checking all interpretations*.

Lecture 7 takes the complementary, **proof-theoretic** (syntactic) route. It fixes a small stock of **rules of inference** — modus ponens ("from $\varphi$ and $\varphi\to\psi$, infer $\psi$"), modus tollens, disjunctive syllogism, and so on — and defines a **derivation** $\Gamma \vdash \psi$ as a finite chain of formulas, each an axiom, a premise, or the result of applying a rule to earlier lines. Here nothing is "true" or "false"; formulas are *manipulated by rules*, mechanically, like moves in a game.

| | Semantics (this lecture) | Proof theory (Lecture 7) |
|---|---|---|
| Central relation | $\Gamma \models \psi$ (entailment) | $\Gamma \vdash \psi$ (derivability) |
| Basic object | truth value, interpretation | inference rule, derivation |
| Method | truth tables / model search | rule application / proof construction |
| Question answered | *is it true in all models?* | *can it be derived?* |

The two views are connected by two deep meta-theorems, which the course states (and Lecture 7 uses) but which are proved in a dedicated logic course:

- **Soundness:** if $\Gamma \vdash \psi$ then $\Gamma \models \psi$ (the rules never derive a falsehood from truths — proofs are *trustworthy*).
- **Completeness (Gödel, 1929/30, for first-order; the propositional case is Post, 1921):** if $\Gamma \models \psi$ then $\Gamma \vdash \psi$ (every genuine entailment *can* be derived — the rules are *enough*).

Together, for propositional logic, $\vdash$ and $\models$ **coincide**: derivability and entailment are the same relation, approached from two directions. That is why the proof techniques of Lecture 7 are *correct* (soundness) and *sufficient* (completeness) for exactly the semantic facts established here.

---

## Historical note

The algebraic treatment of logic began with **George Boole**, whose *The Mathematical Analysis of Logic* (1847) and *An Investigation of the Laws of Thought* (1854) reduced reasoning to calculation on the symbols $0$ and $1$ — the origin of "Boolean algebra" (Lectures 4–5). **Augustus De Morgan**, Boole's contemporary, gave the duality laws that bear his name. **Gottlob Frege**'s *Begriffsschrift* (1879) introduced a rigorous formal language with a precise notion of well-formed formula, launching modern mathematical logic and the syntax/semantics distinction of §6.5–§6.6. The **truth table** as a systematic device is usually credited to **Ludwig Wittgenstein** (*Tractatus*, 1921) and **Emil Post** (1921) independently, with earlier anticipations by **Charles S. Peirce**; Post also proved the first **functional-completeness** results. **Jan Łukasiewicz** devised parenthesis-free "Polish notation," reminding us that unique readability (Theorem 6.1) can be achieved by grammar alone. In computer science, **Claude Shannon**'s 1937 master's thesis identified propositional logic with switching circuits — the direct ancestor of Lectures 4–5 — and **Stephen Cook** (1971), with **Leonid Levin** independently, proved SAT NP-complete, placing propositional satisfiability at the very center of computational complexity.

---

## Chapter summary

- A **proposition/statement** is a declarative sentence with a definite truth value in $\{T, F\}$. Questions, commands, exclamations, paradoxical sentences, and **open sentences** like "$X$ is divisible by $5$" are not propositions.
- **Atoms** are indivisible simple sentences (propositional variables). **Compound** propositions are built from atoms with $\neg, \wedge, \vee, \to, \leftrightarrow$ and are **truth-functional**: their value depends only on the atoms' values and the connectives.
- Key connective facts: $\vee$ is **inclusive**; $p\to q$ is false **only** when $p=T, q=F$ (vacuously true when $p=F$); $p\to q$ is equivalent to its **contrapositive** but not its converse or inverse.
- **Syntax** defines **well-formed formulas** by recursion; precedence $\neg > \wedge > \vee > \to > \leftrightarrow$ and parentheses fix a unique **parse tree** with a **main connective**. **Unique Readability** (Theorem 6.1) guarantees exactly one parse.
- **Semantics**: an **interpretation** assigns values to atoms and extends *uniquely* to all formulas (Theorem 6.2); $v \models \varphi$ means $\varphi$ is true under $v$. A formula with $n$ atoms has $2^n$ interpretations — the rows of its **truth table**.
- Every formula is a **tautology** (always $T$; $\models\varphi$), a **contradiction** (always $F$), or a **contingency** (mixed). It is **satisfiable** iff some interpretation makes it true. $\varphi$ is a tautology iff $\neg\varphi$ is unsatisfiable (Theorem 6.4).
- **SAT** — deciding satisfiability — is the first **NP-complete** problem (Cook–Levin); truth tables solve it in $2^n$ steps, while real **SAT solvers** (DPLL/CDCL) scale to millions of variables and power verification, planning, and analysis tools.
- **Logical equivalence** $\varphi\equiv\psi$ (equal columns; equivalently $\varphi\leftrightarrow\psi$ a tautology, Theorem 6.5) is an equivalence relation and supports **substitution** (Theorem 6.6). The laws — double negation, De Morgan, distributivity, $p\to q\equiv\neg p\vee q$, contrapositive, biconditional — are proved by truth tables (Theorems 6.7–6.12) and are the **semantic twins of the Boolean-algebra laws** of Lecture 4.
- Every formula has an equivalent **DNF** and **CNF** (Theorem 6.13), obtained canonically from the truth table or by rewriting (eliminate $\to,\leftrightarrow$; push $\neg$ inward to NNF; distribute). Consequently $\{\neg,\wedge,\vee\}$ is **functionally complete** (Corollary 6.14).
- **Entailment** $\Gamma \models \psi$ holds when every model of $\Gamma$ is a model of $\psi$; an **argument is valid** iff there is no counterexample row, iff (premises $\to$ conclusion) is a tautology (Theorem 6.15), iff $\Gamma\cup\{\neg\psi\}$ is unsatisfiable (Theorem 6.16).
- This lecture is about **meaning and truth** ($\models$); deriving consequences with **rules of inference** ($\vdash$) and proof techniques is Lecture 7, tied back by **soundness** and **completeness**.

---

## Exercises

### Warm-up

1. Decide which are propositions; for those that are, give the truth value if known. (a) *"$13$ is prime."* (b) *"Solve the equation $x^2 = 4$."* (c) *"$x^2 = 4$."* (d) *"Every even integer $> 2$ is a sum of two primes."* (e) *"This exercise is hard!"*
2. Write the negation, converse, inverse, and contrapositive of *"If a number is divisible by $6$, then it is divisible by $3$."* Which of the four is guaranteed to have the same truth value as the original?
3. Insert full parentheses according to the precedence rules and identify the main connective: (a) $\neg p \vee q \to r$; (b) $p \wedge \neg q \leftrightarrow r \vee s$; (c) $\neg(p \to q) \wedge r$.
4. Build the truth table of $p \to (q \vee \neg p)$ and classify it (tautology / contradiction / contingency).
5. Translate into symbols with stated atoms: (a) *"I will go running unless it snows."* (b) *"You may enter only if you have a ticket."* (c) *"Neither the printer nor the scanner works."*

### Standard

6. Build the truth table of $(p \leftrightarrow q) \to (p \wedge q)$ and classify it. On which interpretations is it false?
7. Prove by truth table that $p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)$ (the second distributive law).
8. Using equivalence laws only (cite each step, no truth table), simplify: (a) $\neg(p \vee \neg q)$; (b) $\neg(\neg p \wedge q) \vee q$; (c) $(p \to q) \wedge (p \to \neg q)$.
9. Show that $\{p \vee q,\; p \to r,\; q \to r\} \models r$ (constructive-dilemma pattern). Use a truth table or a short case argument, and identify the rows where all premises hold.
10. Determine, with a truth table, whether the argument is valid: *"If the cache is warm, the request is fast. The request is not fast. Therefore the cache is not warm."*
11. Find a DNF and a CNF for $p \oplus q$ (exclusive-or) and for $p \leftrightarrow q$. (You may read them off truth tables.)
12. Convert to CNF by rewriting (show stages): $\;(p \wedge q) \to (r \vee \neg s)$.
13. Is $\{p \to q,\; \neg p \to r,\; \neg q\} \models r$? Justify by finding all models of the premises and checking the conclusion.
14. Show that $p \to (q \to r) \equiv (p \wedge q) \to r$ (the "exportation" law) by any method, and explain why this does **not** contradict the non-equivalence of $(p\to q)\to r$ and $p\to(q\to r)$ from §6.5.

### Challenge

15. **(Unique readability in action.)** Explain why the string $p \wedge q \vee r$ needs the precedence convention to be read, and exhibit the two *different* fully parenthesized WFFs it could abbreviate. Show by truth table that they are not equivalent, so the convention (not mere taste) is doing real work.
16. **(Functional completeness.)** Show that $\{\neg, \to\}$ is functionally complete by expressing $\vee$, $\wedge$, and $F$ using only $\neg$ and $\to$. (Hint: start from $p \vee q \equiv \neg p \to q$.)
17. **(NAND.)** Let $p \uparrow q \equiv \neg(p \wedge q)$. Express $\neg p$, $p \wedge q$, and $p \vee q$ using only $\uparrow$, thereby proving NAND is functionally complete by itself.
18. **(Refutation.)** Use Theorem 6.16 to test $\{p \to q,\; q \to r,\; p\} \models r$: write the set $\{p\to q,\ q\to r,\ p,\ \neg r\}$, argue it is unsatisfiable, and explain how "unsatisfiable" certifies the entailment.
19. **(Compactness of the method, and its cost.)** A formula has $n$ distinct atoms. (a) How many rows does its truth table have? (b) Explain why deciding satisfiability by truth table is impractical for $n = 60$, giving the approximate row count. (c) State in one sentence what a SAT solver does differently.
20. **(Modeling.)** Three suspects $A, B, C$ are questioned. $A$ says "$B$ did it." $B$ says "I didn't do it." $C$ says "I didn't do it." Exactly one suspect is guilty and exactly one statement is true. Introduce atoms for guilt, encode the constraints as a propositional formula, and determine the guilty party.

---

## Selected answers & hints

**1.** (a) proposition, true. (b) not a proposition (imperative). (c) open sentence — a proposition only once $x$ is fixed. (d) proposition (this is Goldbach's conjecture — its truth value is *unknown*, but it *has* one). (e) not a proposition (exclamation, and subjective).

**2.** Original $d\to t$ ("divisible by $6$" $\to$ "divisible by $3$"). Negation: $d \wedge \neg t$. Converse: $t \to d$. Inverse: $\neg d \to \neg t$. Contrapositive: $\neg t \to \neg d$. Only the **contrapositive** is guaranteed equivalent (Theorem 6.11); the original is *true* here, its contrapositive true, but its converse ("divisible by $3$ $\Rightarrow$ divisible by $6$") is false ($9$ is a counterexample).

**3.** (a) $(((\neg p)\vee q)\to r)$, main connective $\to$. (b) $((p\wedge(\neg q))\leftrightarrow(r\vee s))$, main connective $\leftrightarrow$. (c) $((\neg(p\to q))\wedge r)$, main connective $\wedge$.

**4.** $p\to(q\vee\neg p)$: the column is $T,T,F,T$ — a **contingency**, false only at $p=T, q=F$ (there $q\vee\neg p = F\vee F = F$, so $T\to F = F$; when $p=F$ the implication is vacuously true, and when $p=q=T$ the consequent is true).

**5.** (a) $\neg s \to r$, i.e. $s \vee r$, with $r$="I run", $s$="it snows". (b) $e \to t$ ("only if" $\Rightarrow$ antecedent is *enter*), $e$="enter", $t$="have ticket". (c) $\neg p \wedge \neg s \equiv \neg(p\vee s)$.

**6.** False exactly when $p \leftrightarrow q$ is true but $p\wedge q$ is false — i.e. the row $p=F, q=F$ (there $p\leftrightarrow q=T$, $p\wedge q=F$). So it is a **contingency**, false only at $p=q=F$.

**8.** (a) $\neg p \wedge q$ (De Morgan then double negation). (b) $\neg(\neg p\wedge q)\vee q \equiv (p\vee\neg q)\vee q \equiv p\vee(\neg q\vee q)\equiv p\vee T\equiv T$ — a tautology. (c) $(p\to q)\wedge(p\to\neg q)\equiv(\neg p\vee q)\wedge(\neg p\vee\neg q)\equiv \neg p\vee(q\wedge\neg q)\equiv\neg p\vee F\equiv\neg p$.

**9.** Valid. In any row where $p\vee q$ is true, at least one of $p, q$ holds; together with $p\to r$ / $q\to r$ that forces $r$. No row has all three premises true and $r$ false.

**10.** Valid — this is modus tollens ($w\to f,\ \neg f \models \neg w$); cf. Example 6.23.

**11.** $p\oplus q$: DNF $(\neg p\wedge q)\vee(p\wedge\neg q)$; CNF $(p\vee q)\wedge(\neg p\vee\neg q)$. $\;p\leftrightarrow q$: DNF $(p\wedge q)\vee(\neg p\wedge\neg q)$; CNF $(p\vee\neg q)\wedge(\neg p\vee q)$.

**12.** $(p\wedge q)\to(r\vee\neg s)\equiv\neg(p\wedge q)\vee(r\vee\neg s)\equiv(\neg p\vee\neg q)\vee r\vee\neg s\equiv \neg p\vee\neg q\vee r\vee\neg s$ — a single clause, already CNF.

**14.** Both sides equal $\neg p\vee\neg q\vee r$ (rewrite each with the implication law and associate). No contradiction with §6.5: there we compared $(p\to q)\to r$ with $p\to(q\to r)$ — *different* left-hand sides — whereas here the left side is the *conjunction* $p\wedge q$, not the implication $p\to q$.

**15.** It could abbreviate $((p\wedge q)\vee r)$ or $(p\wedge(q\vee r))$. Truth tables differ (e.g. $p=F, q=F, r=T$: the first is $T$, the second is $F$). The convention $\wedge > \vee$ selects the first reading; without it the string would be ambiguous.

**16.** Using only $\{\neg,\to\}$: $\;p\vee q\equiv\neg p\to q\;$ (since $\neg p\to q\equiv\neg\neg p\vee q\equiv p\vee q$); $\;p\wedge q\equiv\neg(p\to\neg q)$; and a contradiction $F\equiv\neg(p\to p)$ (as $p\to p$ is a tautology). Having reconstructed $\neg,\vee,\wedge$, Corollary 6.14 finishes completeness.

**17.** $\neg p\equiv p\uparrow p$; $\;p\wedge q\equiv(p\uparrow q)\uparrow(p\uparrow q)$; $\;p\vee q\equiv(p\uparrow p)\uparrow(q\uparrow q)$. (Verify each by a $2$- or $4$-row table.)

**18.** From $p$ and $p\to q$ we need $q$; from $q$ and $q\to r$ we need $r$; but $\neg r$ demands $r=F$ — no interpretation satisfies all four, so the set is unsatisfiable, which by Theorem 6.16 certifies $\{p\to q, q\to r, p\}\models r$ (this is two chained modus-ponens steps, a.k.a. the transitivity of $\to$).

**19.** (a) $2^n$. (b) $2^{60}\approx 1.15\times 10^{18}$ rows — beyond any feasible enumeration. (c) A SAT solver searches assignments intelligently (unit propagation, conflict-driven clause learning), pruning the space instead of listing all $2^n$ rows.

**20.** Let $g_A, g_B, g_C$ mean "$A$/$B$/$C$ is guilty." Statements: $S_A = g_B$, $\;S_B = \neg g_B$, $\;S_C = \neg g_C$. Constraints: exactly one of $g_A, g_B, g_C$ is true (guilt) and exactly one of $S_A, S_B, S_C$ is true (truth). Now $S_A$ and $S_B$ are negations of each other, so *exactly one of them* is true no matter what; since only one statement in total may be true, $S_C$ must be **false**. Then $S_C = \neg g_C = F$ gives $g_C = T$, so $C$ is guilty, and exactly-one-guilty forces $A, B$ innocent. Check: with $g_C=T, g_A=g_B=F$ we get $S_A=F, S_B=T, S_C=F$ — exactly one true statement ($S_B$). The model is unique. **C did it.**

---

## Further reading

- **K. H. Rosen**, *Discrete Mathematics and Its Applications* — Chapter 1, "The Foundations: Logic and Proofs," especially §1.1 (propositional logic), §1.2 (applications), §1.3 (propositional equivalences). The standard CS-oriented treatment, with many translation and circuit examples.
- **S. S. Epp**, *Discrete Mathematics with Applications* — Chapter 2, "The Logic of Compound Statements" (statements, connectives, truth tables, logical equivalence, conditionals, valid arguments). Especially clear on natural-language translation and the converse/inverse/contrapositive distinctions.
- **H. B. Enderton**, *A Mathematical Introduction to Logic* — Chapter 1, for the rigorous syntax/semantics development (unique readability, the valuation theorem, functional completeness) at the level of §6.5–§6.6 and §6.10.
- **M. Huth & M. Ryan**, *Logic in Computer Science: Modelling and Reasoning about Systems* — for CNF, SAT/DPLL, and the verification applications sketched in §6.8.
- Cross-references within this course: **Lectures 4–5** (Boolean algebra and logic circuits — the same algebra, read algebraically) and **Lecture 7** (rules of inference and proof techniques — the syntactic counterpart, $\vdash$, to this lecture's $\models$).