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.