Well-Formed Formulas and Semantics

 

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.