Section 1.5: Problem 10 Solution
Working problems is a crucial part of learning mathematics. No one can learn... merely by poring over the definitions, theorems, and examples that are worked out in the text. One must work part of it out for oneself. To provide that opportunity is the purpose of the exercises.
James R. Munkres
Add the 0-place connectives , to our language. For each wff and sentence symbol , let be the wff obtained from by replacing by . Similarly for . Then let . Prove the following:
(b) If and does not appear in , then .
(c) The formula is satisfiable iff is satisfiable.
Remarks: We can think of as trying to say everything says, but without being able to use the symbol . Parts (a) and (b) state that is the strongest -free consequence of . The formulas and are not tautologically equivalent in general, but they are “equally satisfiable” by part (c). The operation of forming from is (in another context) called resolution on .
We are going to use the following fact (*): for any truth assignment that includes all sentence symbols of , if then , otherwise . Also, we note that (**) for any truth assignment , .
(a) If a truth assignment satisfies then, according to (*), depending on the value of , or is , and, hence, according to (**), .
(b) Exercise 4 of Section 1.2 tells us that iff is a tautology. Now, according to Exercise 8 of Section 1.2, we can substitute or for in this expression (or, since that exercise was proved for the language without and , substitute or for ), and the resulting wff will still be a tautology. Now, note that in the first case we obtain , while in the other case we obtain (we actually need to prove that substituting or is equivalent to substituting or , but we will skip this part). So, both are tautologies (we could use an argument using truth assignments to avoid referring to previous exercises). Now, for any truth assignment such that satisfies , we can consider the truth assignment restricted to all sentence symbols of except for such that still satisfies (see Exercise 6 of Section 1.2 for more details), and we can extend the truth assignment to or by letting and . Then, according to Exercise 6 of Section 1.2, , and according to (**), at least one of or is . Hence, satisfies .
(c) One direction follows from (a). Now, assume that is satisfiable. If is not satisfiable then every wff is tautologically implied by , including . But then, by (b), is tautologically implied by , which is not true as is satisfiable. Therefore, is satisfiable as well.
To conclude this exercise, we illustrate the concept by some examples. First, consider . which is tautologically equivalent to . We can think of it as the best we can say if is known to be true but we cannot express , or, alternatively, without using , is that is true. Similarly, is tautologically equivalent to , as in this case, without mentioning all we can say is that is true, in other words, we can say nothing specific.