4. Propositional Logic

We are finally ready to turn to the proper subject matter of this course, logic. We will see that although propositional logic has limited expressive power, it can be used to carry out useful combinatorial reasoning in a wide range of applications.

4.1. Syntax

We start with a stock of variables $p_0, p_1, p_2, \ldots$ that we take to range over propositions, like “the sky is blue” or “2 + 2 = 5.” We’ll make the interpretation of propositional logic explicit in the next section, but, intuitively, propositions are things that can be either true or false. (More precisely, this is the classical interpretation of propositional logic, which is the one we will focus on in this course.) Each propositional variable is a formula, and we also include symbols $\top$ and $\bot$ for “true” and “false” respectively. We also provide means for building new formulas from old ones. The following is a paradigm instance of an inductive definition.

Definition

The set of propositional formulas is generated inductively as follows:

Each variable $p_i$ is a formula.
$\top$ and $\bot$ are formulas.
If $A$ is a formula, so is $\lnot A$ (“not $A$”).
If $A$ and $B$ are formulas, so are
- $A \land B$ (”$A$ and $B$”),
- $A \lor B$ (”$A$ or $B$”),
- $A \to B$ (”$A$ implies $B$”), and
- $A \liff B$ (”$A$ if and only if $B$”).

We will see later that there is some redundancy here; we could get by with fewer connectives and define the others in terms of those. Conversely, there are other connectives that can be defined in terms of these. But the ones we have included form a complete set of connectives, which is to say, any conceivable connective can be defined in terms of these, in a sense we will clarify later.

The fact that the set is generated inductively means that we can use recursion to define functions on the set of propositional formulas, as follows:

\[\begin{split}\mathit{complexity}(p_i) & = 0 \\ \mathit{complexity}(\top) & = 0 \\ \mathit{complexity}(\bot) & = 0 \\ \mathit{complexity}(\lnot A) & = \mathit{complexity}(A) + 1 \\ \mathit{complexity}(A \land B) & = \mathit{complexity}(A) + \mathit{complexity}(B) + 1 \\ \mathit{complexity}(A \lor B) & = \mathit{complexity}(A) + \mathit{complexity}(B) + 1 \\ \mathit{complexity}(A \to B) & = \mathit{complexity}(A) + \mathit{complexity}(B) + 1 \\ \mathit{complexity}(A \liff B) & = \mathit{complexity}(A) + \mathit{complexity}(B) + 1.\end{split}\]

The function $\mathit{complexity}(A)$ counts the number of connectives. The function $\mathit{depth}(A)$, defined in a similar way, computes the depth of the parse tree.

\[\begin{split}\mathit{depth}(p_i) & = 0 \\ \mathit{depth}(\top) & = 0 \\ \mathit{depth}(\bot) & = 0 \\ \mathit{depth}(\lnot A) & = \mathit{depth}(A) + 1 \\ \mathit{depth}(A \land B) & = \max(\mathit{depth}(A), \mathit{depth}(B)) + 1 \\ \mathit{depth}(A \lor B) & = \max(\mathit{depth}(A), \mathit{depth}(B)) + 1 \\ \mathit{depth}(A \to B) & = \max(\mathit{depth}(A), \mathit{depth}(B)) + 1 \\ \mathit{depth}(A \liff B) & = \max(\mathit{depth}(A), \mathit{depth}(B)) + 1.\end{split}\]

Here’s an example of a proof by induction:

Theorem

For every formula $A$, we have $\mathit{complexity}(A) \le 2^{\mathit{depth}(A)} - 1$.

Proof

In the base case, we have

\[\mathit{complexity}(p_i) = 0 = 2^0 - 1 = 2^{\mathit{depth}(p_i)} - 1,\]

and similarly for $\top$ and $\bot$. In the case for negation, assuming the claim holds of $A$, we have

\[\begin{split}\mathit{complexity}(\lnot A) & = \mathit{complexity}(A) + 1 \\ & \le 2^{\mathit{depth}(A)} - 1 + 1 \\ & \le 2^{\mathit{depth}(A)} + 2^{\mathit{depth}(A)} - 1 \\ & \le 2^{\mathit{depth}(A) + 1} - 1 \\ & = 2^{\mathit{depth}(\lnot A)} - 1.\end{split}\]

Finally, assuming the claim holds of $A$ and $B$, we have

\[\begin{split}\mathit{complexity}(A \land B) & = \mathit{complexity}(A) + \mathit{complexity}(B) + 1 \\ & \le 2^{\mathit{depth}(A)} - 1 + 2^{\mathit{depth}(B)} - 1 + 1 \\ & \le 2 \cdot 2^{\max(\mathit{depth}(A), \mathit{depth}(B))} - 1 \\ & = 2^{\max(\mathit{depth}(A), \mathit{depth}(B)) + 1} - 1 \\ & = 2^{\mathit{depth}(A \land B)} - 1,\end{split}\]

and similarly for the other binary connectives.

In our metatheory, we will use variables $p, q, r, \ldots$ to range over propositional variables, and $A, B, C, \ldots$ to range over propositional formulas. The formulas $p_i$, $\top$, and $\bot$ are called atomic formulas. If $A$ is a formula, $B$ is a subformula of $A$ if $B$ occurs somewhere in $A$. We can make this precise by defining the set of subformulas of any formula $A$ inductively as follows:

\[\begin{split}\mathit{subformulas}(A) & = \{ A \} \quad \text{if $A$ is atomic} \\ \mathit{subformulas}(\lnot A) & = \{ \lnot A \} \cup \mathit{subformulas}(A) \\ \mathit{subformulas}(A \star B) & = \{ A \star B \} \cup \mathit{subformulas}(A) \cup \mathit{subformulas}(B)\end{split}\]

In the last clause, the star is supposed to represent any binary connective.

If $A$ and $B$ are formulas and $p$ is a propositional variable, the notation $A[B/p]$ denotes the result of substituting $B$ for $p$ in $A$. Beware: the notation for this varies widely; $A[p \mapsto B]$ is also becoming common in computer science. The meaning is once again given by a recursive definition:

\[\begin{split}p_i[B/p] & = \begin{cases} B & \text{if $p$ is $p_i$} \\ p_i & \text{otherwise} \end{cases} \\ (\lnot C) [B/p] & = \lnot (C[B /p]) \\ (C \star D) [B / p] & = C[B / p] \star D[B / p]\end{split}\]

4.2. Semantics

Consider the formula $p \land (\lnot q \lor r)$. Is it true? Well, that depends on the propositions $p$, $q$, and $r$. More precisely, it depends on whether they are true — and, in fact, that is all it depends on. In other words, once we specify which of $p$, $q$, and $r$ are true and which are false, the truth value of $p \land (\lnot q \lor r)$ is completely determined.

To make this last claim precise, we will use the set $\{ \top, \bot \}$ to represent the truth values true and false. It doesn’t really matter what sorts of mathematical objects those are, as long as they are distinct. You can take them to be the corresponding propositional formulas, or you can take $\top$ to be the number 1 and $\bot$ to be the number 0. A truth assignment is a function from propositional variables to the set $\{ \top, \bot \}$, that is, a function which assigns a value of true or false to each propositional variable. Any truth assignment $v$ extends to a function $\bar v$ that assigns a value of $\top$ or $\bot$ to any propositional formula. It is defined recursively as follows:

\[\begin{split}\bar v (p_i) & = v(p_i) \\ \bar v (\top) & = \top \\ \bar v (\bot) & = \bot \\ \bar v (\lnot A) & = \begin{cases} \top & \text{if $\bar v(A) = \bot$} \\ \bot & \text{otherwise} \end{cases} \\ \bar v (A \land B) & = \begin{cases} \top & \text{if $\bar v(A) = \top$ and $\bar v(B) = \top$} \\ \bot & \text{otherwise} \end{cases} \\ \bar v (A \lor B) & = \begin{cases} \top & \text{if $\bar v(A) = \top$ or $\bar v(B) = \top$} \\ \bot & \text{otherwise} \end{cases} \\ \bar v (A \to B) & = \begin{cases} \top & \text{if $\bar v(A) = \bot$ or $\bar v(B) = \top$} \\ \bot & \text{otherwise} \end{cases} \\ \bar v (A \liff B) & = \begin{cases} \top & \text{if $\bar v(A) = \bar v(B)$} \\ \bot & \text{otherwise.} \end{cases}\end{split}\]

It is common to write $[\![A]\!]_v$ instead of $\bar v(A)$. Double-square brackets like these are often used to denote a semantic value that is assigned to a syntactic object. Think of $[\![A]\!]_v$ as giving the meaning of $A$ with respect to the interpretation given by $v$. In this case, variables are interpreted as standing for truth values and the meaning of the formula is the resulting truth value, but in the chapters to come we will come across other semantic interpretations of this sort.

The following definitions are now fundamental to logic. Make sure you are clear on the terminology and know how to use it. If you can use these terms correctly, you can pass as a logician. If you get the terminology wrong, you’ll be frowned upon.

If $[\![A]\!]_v = \top$, we say that $A$ is satisfied by $v$, or that $v$ is a satisfying assignment for $A$. We also sometimes write $\models_v A$.
A formula $A$ is satisfiable if there is some truth assignment that satisfies it. A formula $A$ is unsatisfiable if it is not satisfiable.
A formula $A$ is valid, or a tautology, if it is satisfied by every truth assignment. In other words, $A$ is valid if $[\![A]\!]_v = \top$ for every truth assignment $v$.
If $\Gamma$ is a set of propositional formulas, we say that $\Gamma$ is satisfied by $v$ if every formula in $\Gamma$ is satisfied by $v$. In other words, $\Gamma$ is satisfied by $v$ if $[\![A]\!]_v = \top$ for every $A$ in $\Gamma$.
A set of formulas $\Gamma$ is satisfiable if it is satisfied by some truth assignment $v$. Otherwise, it is unsatisfiable.
If $\Gamma$ is a set of propositional formulas and $A$ is a propositional formula, we say $\Gamma$ entails $A$ if every truth assignment that satisfies $\Gamma$ also satisfies $A$. Roughly speaking, this says that whenever the formulas in $\Gamma$ are true, then $A$ is also true. In this case, $A$ is also said to be a logical consequence of $\Gamma$.
Two formulas $A$ and $B$ are logically equivalent if each one entails the other, that is, we have $\{A\} \models B$ and $\{ B \} \models A$. When that happens, we write $A \equiv B$.

There is a lot to digest here, but it is important that you become comfortable with these definitions. The mathematical analysis of truth and logical consequence is one of the crowning achievements of modern logic, and this basic framework for reasoning about expressions and their meaning has been applied to countless other settings in logic and computer science.

You should also get used to using semantic notions in proofs. For example:

Theorem

A propositional formula $A$ is valid if and only if $\lnot A$ is unsatisfiable.

Proof

$A$ is valid if and only if $[\![A]\!]_v = \top$ for every truth assignment $v$. By the definition of $[\![\lnot A]\!]_v$, this happens if and only if $[\![\lnot A]\!]_v = \bot$ for every $v$, which is the same as saying that $\lnot A$ is unsatisfiable.

4.3. Calculating with propositions

Remember that Leibniz imagined that one day we would be able to calculate with propositions. What he had noticed is that propositions, like numbers, obey algebraic laws. Here are some of them:

$A \lor \lnot A \equiv \top$
$A \land \lnot A \equiv \bot$
$\lnot \lnot A \equiv A$
$A \lor A \equiv A$
$A \land A \equiv A$
$A \lor \bot \equiv A$
$A \land \bot \equiv \bot$
$A \lor \top \equiv \top$
$A \land \top \equiv A$
$A \lor B \equiv B \lor A$
$A \land B \equiv B \land A$
$(A \lor B) \lor C \equiv A \lor (B \lor C)$
$(A \land B) \land C \equiv A \land (B \land C)$
$\lnot(A \land B) \equiv \lnot A \lor \lnot B$
$\lnot(A \lor B) \equiv \lnot A \land \lnot B$
$A \land (B \lor C) \equiv (A \land B) \lor (A \land C)$
$A \lor (B \land C) \equiv (A \lor B) \land (A \lor C)$
$A \land (A \lor B) \equiv A$
$A \lor (A \land B) \equiv A$.

The equivalences $\lnot(A \land B) \equiv \lnot A \lor \lnot B$ and $\lnot(A \lor B) \equiv \lnot A \land \lnot B$ are known as De Morgan’s laws. It is not hard to show that all the logical connectives respect equivalence, and hence substituting equivalent formulas for a variable in a formula results in equivalent formulas. This means that, as Leibniz imagined, we can prove that a Boolean formula is valid by calculating to show that it is equivalent to $\top$. Here is an example.

Theorem

For any propositional formulas $A$ and $B$, we have $(A \land \lnot B) \lor B \equiv A \lor B$.

Proof

\[\begin{split}(A \land \lnot B) \lor B & \equiv (A \lor B) \land (\lnot B \lor B) \\ & \equiv (A \lor B) \land \top \\ & \equiv (A \lor B).\end{split}\]

Mathematicians have a trick, called quotienting, for turning an equivalence relation into an equality. If we interpret $A$, $B$, and $C$ as equivalence classes of formulas instead of formulas, the equivalences listed above become identities. The resulting algebraic structure is known as a Boolean algebra, and we can view the preceding proof as establishing an identity that holds in any Boolean algebra. The same trick is used, for example, to interpret an equivalence between numbers modulo 12, like $5 + 9 \equiv 2$ as an identity on the structure $\bZ / 12 \bZ$.

4.4. Complete sets of connectives

You may have noticed that our choice of connectives is redundant. For example, the following equivalences show that we can get by with $\lnot$, $\lor$, and $\bot$ alone:

\[\begin{split}A \land B & \equiv \lnot (\lnot A \lor \lnot B) \\ A \to B & \equiv \lnot A \lor B \\ A \liff B & \equiv (A \to B) \land (B \to A) \\ \top & \equiv \lnot \bot.\end{split}\]

We can even define $\bot$ as $P \land \lnot P$ for any propositional variable $P$, though that has the sometimes annoying consequence that we cannot express the constants $\top$ and $\bot$ without using a propositional variable.

Let $f(x_0, \ldots, x_{n-1})$ be a function that takes $n$ truth values and returns a truth value. A formula $A$ with variables $p_0, \ldots, p_{n-1}$ is said to represent $f$ if for every truth assignment v,

\[\tval{A}_v = f(v(p_0), \ldots, v(p_{n-1})).\]

If you think of $f$ as a truth table, this says that the truth table of $A$ is $f$.

A set of connectives is said to be complete if every function $f$ is represented by some formula $A$ involving those connectives. In class, we’ll discuss how to prove that $\{ \land, \lnot \}$ is a complete set of connectives in that sense.

It is now straightforward to show that a certain set of connectives is complete: just show how to define $\lor$ and $\lnot$ in terms of them. Showing that a set of connectives is not complete typically requires some more ingenuity. One idea, as suggested in Section 2.4, is to look for some invariant property of the formulas that are represented. Here is an example.

Proposition

$\{ \liff \}$ is not a complete set of connectives.

Proof

Show by induction on propositional formulas that any formula involving only $\liff$ and a single variable $p$ and the constant $\top$ is equivalent to either $p$ or $\top$. This implies that the negation function is not representable. (If a formula uses more than one variable, the definition of representability says that truth value can’t change if we replace the extra variables by $\top$.)

The base case is immediate, and assuming the inductive hypothesis for $A$ and $B$, the formula $A \liff B$ is equivalent to $p \liff p$, $p \liff \top$, $\top \liff p$, or $\top \liff \top$. The first and last are equivalent to $\top$, and the middle one is equivalent to $p$.

4.5. Normal forms

For both theoretical reasons and practical reasons, it is often useful to know that formulas can be expressed in particularly simple or convenient forms.

Definition

An atomic formula is a variable or one of the constants $\top$ or $\bot$. A literal is an atomic formula or a negated atomic formula.

Definition

The set of propositional formulas in negation normal form (NNF) is generated inductively as follows:

Each literal is in negation normal form.
If $A$ and $B$ are in negation normal form, then so are $A \land B$ and $A \lor B$.

More concisely, the set of formulas in negation normal form is the smallest set of formulas containing the literals and closed under conjunction and disjunction. If we identify $\top$ with $\lnot \bot$ and $\lnot \top$ with $\bot$, we can alternatively characterize the formulas in negation normal form as the smallest set of formulas containing $\top$, $\bot$, variables, and their negations, and closed under conjunction and disjunction.

Proposition

Every propositional formula is equivalent to one in negation normal form.

Proof

First use the identities $A \liff B \equiv (A \limplies B) \land (B \limplies A)$ and $A \limplies B \equiv \lnot A \lor B$ to get rid of $\liff$ and $\limplies$. Then use De Morgan’s laws together with $\lnot \lnot A \equiv A$ to push negations down to the atomic formulas.

More formally, we can prove by induction on propositional formulas $A$ that both $A$ and $\lnot A$ are equivalent to formulas in negation normal form. (You should try to write that proof down carefully.) Putting a formula in negation normal form is reasonably efficient. You should convince yourself that if $A$ is in negation normal form, then putting $\lnot A$ in negation normal form amounts to switching all the following in $A$:

$\top$ with $\bot$
variables $p_i$ with their negations $\lnot p_i$
$\land$ with $\lor$.

We will see that conjunctive normal form (CNF) and disjunctive normal form (DNF) are also important representations of propositional formulas. A formula is in conjunctive normal form if it can be written as conjunction of disjunctions of literals, in other words, if it can be written as a big “and” of “or” expressions:

\[\bigwedge_{i < n} \left( \bigvee_{j < m_i} \ell_j \right)\]

where each $\ell_j$ is a literal. Here is an example:

\[(p \lor \lnot q \lor r) \land (\lnot p \lor s) \land (\lnot r \lor s \lor \lnot t).\]

We can think of $\bot$ as the empty disjunction (because a disjunction is true only when one of the disjuncts is true) and we can think of $\top$ as the empty conjunction (because a conjunction is true when all of its conjuncts are true, which happens trivially when there aren’t any).

Dually, a formula is in disjunctive normal form if it is an “or” and “and” expressions:

\[\bigvee_{i < n} \left( \bigwedge_{j < m_i} \ell_j \right).\]

If you switch $\land$ and $\lor$ in the previous example, you have a formula in disjunctive normal form.

It is pretty clear that if you take the conjunction of two formulas in CNF the result is a CNF formula (modulo associating parentheses), and, similarly, the disjunction of two formulas in DNF is again DNF. The following is less obvious:

Lemma

The disjunction of two CNF formulas is equivalent to a CNF formula, and dually for DNF formulas.

Proof

For the first claim, we use the equivalence $A \lor (B \land C) \equiv (A \lor B) \land (A \lor C)$. By induction on $n$, we have that for every sequence of formulas $B_0, \ldots, B_{n-1}$ we have $A \lor \bigwedge_{i < n} B_i \equiv \bigwedge_{i < n} (A \lor B_i).$ Then by induction on $n'$ we have $\bigwedge_{i' < n'} A_{i'} \lor \bigwedge_{i < n} B_i \equiv \bigwedge_{i' < n'} \bigwedge_{i < n} (A_{i'} \lor B_i).$ Since each $A_{i'}$ and each $B_i$ is a disjunction of literals, this yields the result.

The second claim is proved similarly, switching $\land$ and $\lor$.

Proposition

Every propositional formula is equivalent to one in conjunctive normal form, and also to one in disjunctive normal form.

Proof

Since we already know that every formula is equivalent to one in negation normal form, we can use induction on that set of formulas. The claim is clearly true of $\top$, $\bot$, $p_i$, and $\lnot p_i$. By the previous lemma, whenever it is true of $A$ and $B$, it is also true of $A \land B$ and $A \lor B$.

In contrast to putting formulas in negation normal form, the exercises below show that the smallest CNF or DNF equivalent of a formula $A$ can be exponentially longer than $A$.

We will see that conjunctive normal form is commonly used in automated reasoning. Notice that if a disjunction of literals contains a duplicated literal, deleting the duplicate results in an equivalent formula. We can similarly delete any occurrence of $\bot$. A disjunction of literals is called a clause. Since the order of the disjuncts and repetitions don’t matter, we generally identify clauses with the corresponding set of literals; for example, the clause $p \lor \lnot q \lor r$ is associated with the set $\{ p, \lnot q, r \}$. If a clause contains a pair $p_i$ and $\lnot p_i$, or if it contains $\top$, it is equivalent to $\top$. If $\Gamma$ is a set of clauses, we think of $\Gamma$ as saying that all the clauses in $\Gamma$ are true. With this identification, every formula in conjunctive normal form is equivalent to a set of clauses. An empty clause corresponds to $\bot$, and an empty set of clauses corresponds to $\top$.

The dual notion to a clause is a conjunction like $\lnot p \land q \land \lnot r$. If each variable occurs at most once (either positively or negatively), we can think of this as a partial truth assignment. In this example, any truth assignment that satisfies the formula has to set $p$ false, $q$ true, and $r$ false.

4.6. Exercises

Prove that if $A$ is a subformula of $B$ and $B$ is a subformula of $C$ then $A$ is a subformula of $C$. (Hint: prove by induction on $C$ that for every $B \in \mathit{subformulas}(C)$, every subformula of $B$ is a subformula of $C$.)
Prove that for every $A$, $B$, and $p$, $\mathit{depth}(A[B/p]) \le \mathit{depth}(A) + \mathit{depth}(B)$.
Prove that $A$ and $B$ are logically equivalent if and only if the formula $A \liff B$ is valid.
Using the definition of substitution for propositional formulas in Section 4.1, If $\tau$ is any truth assignment, $p$ is any variable, and $b$ is a truth value, then $\tau[p \mapsto b]$ is the function defined

\[\begin{split}(\tau[p \mapsto b])(q) = \begin{cases} b & \text{if $q$ is $p$} \\ \tau(q) & \text{otherwise} \end{cases}\end{split}\]

In other words, $\tau[p \mapsto b]$ is the (possible) modification of $\tau$ that maps $p$ to $b$ and leaves the rest of the assignment the same.

Prove that for any $A$, $B$, $p$, and $\tau$,

\[\tval{A[B/p]}_\tau = \tval{A}_{\tau[p \mapsto \tval{B}_\tau]}.\]

In other words, we can evaluate $A[B/p]$ at $\tau$ by evaluating $B$ at $\tau$ and then evaluating $A$ with $p$ replaced by that result.
Use algebraic calculations to show that all of the following are tautologies:
- $((A \land \lnot B) \lor B) \liff (A \lor B)$
- $(A \limplies \lnot A) \limplies \lnot A$
- $(A \limplies B) \liff (\lnot B \limplies \lnot A)$
- $A \limplies (B \limplies A \land B)$
The Sheffer stroke $A \mid B$, also known as “nand,” says that $A$ and $B$ are not both true. Show that $\{ \mid \}$ is a complete set of connectives. Do the same for “nor,” that is, the binary connective that holds if neither $A$ nor $B$ is true.
Show that $\{ \land, \lnot \}$ and $\{ \limplies, \bot \}$ are complete sets of connectives.
Show that $\{ \limplies, \lor, \land \}$ is not a complete set of connectives. Conclude that $\{ \limplies, \lor, \land, \liff, \top \}$ is not a complete set of connectives.
Show that $\{ \bot, \liff \}$ is not a complete set of connectives. Conclude that $\{ \bot, \top, \lnot, \liff, \oplus \}$ is not complete. Here $A \oplus B$ is the “exclusive or,” which is to say, $A \oplus B$ is true if one of $A$ or $B$ is true but not both.
Using the property $A \lor (B \land C) \equiv (A \lor B) \land (A \lor C)$ and the dual statement with $\land$ and $\lor$ switched, put $(p_1 \land p_2) \lor (q_1 \land q_2) \lor (r_1 \land r_2)$ in conjunctive normal form.
The boolean function $\fn{parity}(x_0, x_1, \ldots, x_{n-1})$ holds if and only if an odd number of the $x_i$ s are true. It is represented by the formula $p_0 \oplus p_1 \oplus \cdots \oplus p_{n-1}$. Show that any CNF formula representing the parity function has to have at least $2^n$ clauses.