Truth Functions

 

A truth function is a function whose arguments can take only the values true or false and whose values are either true or false. So any wff defines a truth function. For example, the function g defined by

g(P, Q) = P Ù Q

is a truth function. Is the converse true? In other words, is every truth function a wff? The answer is yes. To see why this is true, we'll present a technique to construct a wff for any truth function. For example, suppose we define the truth function f  by saying that f(P, Q) is true exactly when P and Q have opposite truth values. Is there a wff  that has the same truth table as f? We'll introduce the technique with this example. Table 5.3 is the truth table for f. We'll explain the statements on the right side of this table.

 

Table 5.3

P

Q

f(P, Q)

 

 

Create

Create

0

0

1

1

0

1

0

1

0

1

1

0

 

We've written the two wffs  and on the second and third lines of the table because the values of f are true on these lines. Each wff is a conjunction of argument letters or their negations according to their values on the same line, according to the following two rules:

If P is true, then put P in the conjunction.

If P is false, then put Ø P in the conjunction.

Let's see why we want to follow these rules. Notice that the truth table for  (Table 5.3) has exactly one true value and it occurs on the third line. Similarly, the truth table for  has exactly one true value and it occurs on the second line of the table.

Table 5.4

P

Q

f(P, Q)

0

0

1

1

0

1

0

1

0

1

1

0

0

0

1

0

0

1

0

0

 

Thus each of the tables for  and  has exactly one true value per column, and these true values occur on the same lines as the true values for f. Since there is one conjunctive wff for each occurrence of true in the table for f, it follows that the table for f can be obtained by taking the disjunction of the tables for and . Thus we obtain the following equivalence:

.

Let's do another example to get the idea. Then we will discuss the special forms that we obtain by using this technique.

EXAMPLE. Let f  be the truth function defined as follows:

f(P,Q,R) = true if and only if either P = Q = false or Q = R = true.

Then f  is true in exactly the following four cases:

f(0, 0, 1),

f(0, 0, 0),

f(1, 1, 1),

f(0, 1, 1).

So we can construct a wff equivalent to f  by taking the disjunction of the four wffs that correspond to these four cases. The disjunction follows:

.

The method we have described can be generalized to construct an equivalent wff for any truth function having at least one true value. If a truth function doesn't have any true values, then it is a contradiction and is equivalent to false. So every truth function is equivalent to some propositional wff. We'll state this as the following theorem:

 Every truth function is equivalent to a propositional wff.                                       

Now we're going to discuss some useful forms for propositional wffs. But first we need a little terminology. A literal is a propositional letter or its negation. For example, P, Q, Ø P, and Ø Q are literals.