Truth and Logical Truth 103How can the truth value for the formula be determined? Since this discussion is formal
logic, one must first define what it means for 0 to be T or F. Of course, this definition, to
be useful, must match most people's intuitions.
To start, one must know what p, q, and r stand for. At first sight, one might expect to
be told what sentences they stand for, such asp = "Mr. Holmes never made a mistake."q = "The professor is not a criminal."
r = "Mrs. Hudson suspected the thief from the start."
For ordinary applications, that is exactly where one begins, but for the study of proposi-
tional logic, this is an unnecessary detail. In propositional logic, it matters not at all what
sentences the proposition letters represent, only what the truth values of the sentences are.
(This will become apparent as you see how truth values are assigned to complex formulas).
Remember, F is shorthand for FALSE and T for TRUE. So, the starting point in proposi-
tional logic is an assignment of truth values to the proposition letters. For example, p may
be assigned the value T, and q and r may be assigned the value F.
Definition 1. Let P be the set of proposition letters. An interpretation is an assignmentI of a truth value (T or F) to every proposition letter in P. For r E P, the assignment of a
truth value to r is denoted I (r).
Example 1. Let P be the set of proposition letters, and let p, q, and r E P and X = P -
{p, q, r}. Let I be the following assignment of truth values to elements of P: I(p) = F,
I(q) = F, l(r) = T, and I(x) = F for every x e X. Then, I is an interpretation.
An interpretation must assign a truth value to every proposition letter. (This is a tech-
nicality, just as it appears to be. Requiring this now simplifies the discussion a bit later.)
Once the interpretation I of the proposition letters is fixed, the interpretations of all
other formulas can be computed by induction on formulas. We illustrate this here with
an expression tree. The process is different from the way that arithmetic expressions are
evaluated, because a value is found in a simple, bottom-up fashion.
Example 2. Determine whether the formula
0 = (-p V q) --* (r --+ p)
is T or F for an interpretation I where I(p) = T and I(q) = 1(r) = F. (Remember: All
other proposition letters have value F.)
Solution. Mark the leaves of the expression tree of 0 with the truth values as shown in
Figure 2.9.
((-p) v q) -- (r -- p)((-'p) v q) (r - p)(-P) qFrF pTp TFigure 2.9 Expression tree.