Is It a Tautology, a Contradiction, or a Contingency?

 

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