Suppose our task is
to classify a wff W
as a tautology, a contradiction, or a contingency. If W contains n letters,
then there are 2n
different assignments of truth values to the letters of W. Building a truth
table with 2n rows can be
tedious when n is moderately large.
Is there another way? Yes. We can use equivalences to solve the problem. If A is a letter and W is a wff, we let
W(A/true)
denote the wff obtained from W
by replacing all occurrences of A by
true. Similarly, we define W(A/false) to be
the wff obtained from W by replacing all occurrences of A by false. Now we come to the key observation:
W is a tautology if and only if W(A/true) and W(A/false) are
tautologies.
The idea is to
simplify W(A/true) and W(A/false) by using the basic properties.
After simplification we do the same thing to the resulting wffs.
It's time for an example to see what we're talking about.
EXAMPLE
(Quine's Method). Suppose we want to check the
meaning of the following wff W:
.
First we compute
the two wffs W(A/true) and W(A/false) and
simplify them:
![]()
![]()
Therefore W(A/false) is a tautology. Now we need to
check the simplification of W(A/true). Call it
X. We continue the process by
constructing the two wffs X(B/true) and Х(B/false):
![]()
So X(B/true) is a tautology, Now let's look at X(B/false).
![]()
So X(B/false) is also a tautology. Thus X is a tautology, and it follows
that W is a tautology.
Quine's method can also be
described graphically with a binary tree. Let W be the root. If N is
any node, pick one of its variables, say V,
and let the two children of N be N(V/true) and N(V/false). Each node
should be simplified as much as possible. Then W is a tautology if all leaves are true, a contradiction if all
leaves are false, and a contingency otherwise. Let's illustrate the idea with
the wff
. The binary tree in Figure 5.2 shows that the wff
is a contingency
because Quine's method gives one false leaf and two
true leaves.

Figure 5.2