Like any
programming language or any natural language, whenever we deal with symbols, at
least two questions always arise. The first deals with syntax:
Is an expression
grammatically (or syntactically) correct? The second deals with semantics: What
is the meaning of an expression? Let's look at the first question first.
A grammatically
correct expression is called a well-formed
formula, or wff for short, which can be
pronounced "woof." To decide whether an expression is a wff, we need to precisely define the syntax (or grammar)
rules for the formation of wffs in our language. So
let's do it.
As with any
language, we must agree on a set of symbols to use as the alphabet. For our
discussion we will use the following sets of symbols:
Truth symbols:
true, false (0, 1)
Connectives: Ø, ®, Ú, Ù
Propositional
variables: Capital letters like P, Q,
and R
Punctuation
symbols: ( , ).
Next we need to
define those expressions (strings) that form the wffs
of our language. We do this by giving the following informal inductive
definition for the set of propositional wffs:
A wff is either a truth
symbol, or a propositional letter, or the negation of a wff,
or the conjunction of two wffs, or the disjunction of
two wffs, or the implication of one wff from another, or a wff
surrounded by parentheses.
For example, the
following expressions are wffs:
0,
1, P, Ø Q, P Ù Q, P
® Q, (P
Ú Q) Ù R, P Ù Q ® R.
If push comes to
shove and we must justify that some expression is a wff,
then we can apply the inductive definition. Let's look at an example.
EXAMPLE
1. We'll show that the expression P
Ù Q Ú R is a wff. First, we know that P, Q,
and R are wffs
because they are propositional letters. Therefore Q Ú R is a wff
because it's a disjunction of two wffs. It follows
that P Ù Q Ú R is a wff
because it's a conjunction of two wffs. We could have
arrived at the same conclusion by saying that P Ù Q is a wff and
then stating that P Ù Q Ú R is a wff, since it is the disjunction
of two wffs.
Can we associate a
truth table with each wff? Yes we can, once we agree
on a hierarchy of precedence among the connectives. For example, P Ù Q Ú R is a perfectly good wff. But to find a truth table, we need to agree on which
connective to evaluate first. We will define the following hierarchy of
evaluation for the connectives of the propositional calculus:
Ø (highest, do first)
Ù
Ú
® (lowest, do last).
We also agree that
the operations Ù, Ú, and ® are left associative. In
other words, if the same operation occurs two or more times in succession,
without parentheses, then evaluate the operations from left to right. Be sure
you can tell the reason for each of the following lines, where each line
contains a wff together with a parenthesized wff with the same meaning:
P Ú Q Ù R means P Ú (Q Ù R)
P ® Q ® R means (P
® Q) ® R
Ø P Ú Q means (Ø P) Ú Q
Ø P ® P Ù Q Ú R means (Ø P) ® ((P Ù Q) Ú R)
Ø Ø P means Ø (Ø P).
Any wff has a natural syntax tree that clearly displays the
hierarchy of the connectives. For example, the syntax tree for the wff P
Ù (Q Ú Ø R) is given by the diagram
in Figure 5.1.
Figure
5.1
Now we can say that
any wff has a unique truth table. For example, suppose
we want to find the truth table for the wff
Ø P ® Q Ù
R.
From the hierarchy
of evaluation we know that this wff has the following
parenthesized form:
(Ø P) ® (Q Ù R).
So we can construct
the truth table as follows: Begin by writing down all possible truth values for
the three letters P, Q, and R. This gives
us a table with eight lines. Next, compute a column of values for Ø P . Then compute a column of
values for Q Ù R. Finally, use these two columns to compute the column of values
for Ø P ® Q Ù R. Table 5.1 gives the result.
Although we've
talked some about meaning, we haven't specifically defined the meaning, or
semantics, of a wff. Let's do it now.
Table 5.1
|
P |
Q |
R |
Ø P |
Q Ù R |
Ø P ® Q Ù R |
|
0 |
0 |
0 |
1 |
0 |
0 |
|
0 |
0 |
1 |
1 |
0 |
0 |
|
0 |
1 |
0 |
1 |
0 |
0 |
|
0 |
1 |
1 |
1 |
1 |
1 |
|
1 |
0 |
0 |
0 |
0 |
1 |
|
1 |
0 |
1 |
0 |
0 |
1 |
|
1 |
1 |
0 |
0 |
0 |
1 |
|
1 |
1 |
1 |
0 |
1 |
1 |
We know that any wff has a unique truth table. So we'll associate each wff with its truth table:
The meanings of the
truth symbols true and false are true and false, respectively. Otherwise, the
meaning of a wff is its truth table.