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).

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.

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.

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$:

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$.

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.

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).

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.

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:

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

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):

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.

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.

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.

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”.

Remark (which is which). Mnemonic: CNF = Conjunction on the outside; DNF = Disjunction 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}$$