7.1 Propositional Logic

The formal syntax for propositional logic is quite straightforward. Fix a vocabulary— a nonempty set Φ of primitive propositions, which I typically label by letters such as p and q (perhaps with a prime or subscript). These primitive propositions can be thought of as representing statements such as "it is brillig" or "this thing is mimsy." Intuitively, these statements describe the basic facts of the situation. More complicated formulas are formed by closing off under conjunction and negation, so that if φ and ψ are formulas, then so are φ and φ ∧ ψ (read "not φ" and "φ and ψ," respectively). Thus, if p stands for "it is brillig" and q stands for "this thing is mimsy," then p says "it is not brillig" while p ∧ q says "it is brillig and this thing is mimsy." The set ^Prop (Φ) of formulas consists of all the formulas that can be formed in this way.

There are some other standard connectives that can easily be defined in terms of conjunction and negation:

φ ∨ ψ (read "φ or ψ") is an abbreviation for ( φ ∧ ψ);
φ ⇒ ψ (read (read "φ implies ψ" or "if φ then ψ") is an abbreviation for φ ∨ ψ;
Φ ⇔ ψ (read "φ if and only if ψ") is an abbreviation for (Φ ⇒ ψ) ∧ (ψ ⇒ Φ);
true is an abbreviation for p ∨ p (where p is a fixed primitive proposition in Φ);
false is an abbreviation for true.

If p and q stand for "it is brillig" and "this thing is mimsy," as before, and r stands "this thing is a borogrove," then the informal English argument at the beginning of the chapter can be readily expressed in propositional logic. "Borogroves are mimsy whenever it is brillig" can be restated as "if it is brillig then [if this thing is a borogrove, then it is mimsy]." (Check that these two English statements really are saying the same thing!) Thus, this becomes p ⇒ (r ⇒ q). "It is now brillig and this thing is a borogrove" becomes p ∧ r. It seems reasonable to conclude q: "this thing is mimsy." Can this conclusion be justified?

So far, I have defined a formal language, along with an intended reading of formulas in the language. The intended reading is supposed to correspond to intuitions that we have regarding words like "and," "or," and "not." These intuitions are captured by providing a semantics for the formulas in the language, that is, a method for deciding whether a given formula is true or false.

The key component of the semantics for propositional logic is a truth assignment v, a function that maps the primitive propositions in Φ to a truth value, that is, an element of the set {true, false}. The form of the truth assignment guarantees that each primitive proposition has exactly one truth value. It is either true or false; it cannot be both true and false, or neither true nor false. This commitment, which leads to classical or two-valued logic, has been subject to criticism; some alternative approaches are mentioned in the notes to this chapter.

A truth assignment determines which primitive propositions are true and which are false. There are standard rules for then determining whether an arbitrary formula φ is true under truth assignment v, or satisfied by truth assignment v, written v ⊨ φ. Formally, the ⊨ relation is defined by induction on the structure of φ. That is, it is first defined for the simplest formulas, namely, the primitive propositions, and then extended to more complicated formulas of the form φ or φ ∧ ψ under the assumption that the truth under v of each constituent has already been determined. For a primitive proposition p,

Thus, a primitive proposition is true under truth assignment v if and only if v assigns it truth value true.

Intuitively, φ is true if and only if φ is false. This intuition is captured as follows:

It is also easy to formalize the intuition that φ ∧ ψ is true if and only if both φ and ψ are true:

What about the other connectives that were defined in terms of ∧ and ? It seems reasonable to expect that φ ∨ ψ is true if and only if one of φ or ψ is true. It is not immediately obvious that defining φ ∨ ψ as an abbreviation for ( φ ∧ ψ) enforces this intuition. As the following lemma shows, it does. The other definitions have the appropriate meaning as well.

Lemma 7.1.1

For every truth assignment v,

v ⊨ φ ∨ ψ iff v ⊨ φ or v ⊨ ψ;
if v ⊨ φ ⇒ ψ, then if v ⊨ φ then v ⊨ ψ;
v ⊨ φ ⇔ ψ iff either v ⊨ φ and v ⊨ ψ or v ⊨ φ and v ⊨ ψ;
v ⊨ true;
v ⊭ false.

Proof I prove part (a), leaving the remaining parts as an exercise for the reader (Exercise 7.1). Suppose that v ⊨ φ ∨ ψ. This is the case iff v ⊨ ( φ ∧ ψ). This, in turn, is the case iff v ⊭ φ ∧ ψ. The definition of ⊨ guarantees that v does not satisfy a conjunction iff it does not satisfy one of the conjuncts: that is, iff v ⊭ φ or v ⊭ ψ. But this last situation holds iff v ⊨ φ or v ⊨ ψ. This completes the proof of part (a).

Lemma 7.1.1 says, among other things, that the formula true is always true and false is always false. This is certainly the intent! Similarly, it says that φ ⇔ ψ is true exactly if φ and ψ have the same truth value: either they must both be true, or they must both be false. It also says that if φ ⇒ ψ is true, then if φ is true, then ψ is true. Put another way, it says that the truth of φ implies the truth of ψ. Again, this seems consistent with the interpretation of implication. However, notice that viewing φ ⇒ ψ as an abbreviation for φ ∨ ψ guarantees that φ ⇒ ψ will automatically be true if φ is false. This may seem counterintuitive. There has been a great deal of discussion regarding the reasonableness of this definition of ⇒; alternative logics have been proposed that attempt to retain the intuition that φ ⇒ ψ is true if the truth of φ implies the truth of ψ without automatically making φ ⇒ ψ true if φ is false. I use the standard definition in this book because it has proved so useful; references for alternative approaches are provided in the notes to this chapter. One important thing to remember (perhaps the most important thing, as far as the proofs in this book are concerned) is that when trying to show that v ⊨ φ ⇒ ψ, it suffices to assume that v ⊨ φ, and then try to show that v ⊨ ψ under this assumption; for if v ⊨ φ, then v ⊨ φ ⇒ ψ is vacuously true.

A formula such as true is true under every truth assignment. A formula that is true under every truth assignment is said to be a tautology, or to be valid. Other valid formulas include (p ∧ q) ⇔ (q ∧ p), and p ⇔ p. The first one says that the truth value of a conjunction is independent of the order in which the conjuncts are taken; the second says that two negations cancel each other out. A formula that is true under some truth assignment is said to be satisfiable. It is easy to see that φ is valid if and only if φ is not satisfiable (Exercise 7.2).

To make precise the sense in which the argument about mimsy borogroves at the beginning of the chapter is legitimate, I need one more definition. A set Σ of formulas entails a formula φ if every truth assignment that makes all the formulas in Σ true also makes φ true. Note that a formula φ is valid iff ⊘ (the empty set of formulas) entails φ. The argument at the beginning of the chapter is legitimate precisely because {p ⇒(r ⇒q), p ∧ r} entails q (Exercise 7.3).