Math 470 Spring ’05

HW #3 Solutions

Section 1.5

3. Suppose that A is tableau refutable, then there is a contradictory tableau T with root TA. If A is satisfiable. there is a valuation V such that V(A) = T. If V agrees with the root entry of T, so by Lemma 5.2, there is a path P on T such that V agrees with every entry on P. But every path P on T is contradictory, so no V can agree with every entry on P. Therefore A is unsatisfiable.

4. Suppose that A is unsatisfiable and let T be the CST with root TA. If T is not contradictory, it has a noncontradictory path P. Define a truth assignment an is Lemma 5.4 and let V be the unique valuation extending it. Then V agrees with all enties on P, including the root TA. But then V(A) would = T, contradicting the unsatisfiability of A.

Section 1.6

1. We will imitate the proof of Theorem 4.8. Note that Theorem 4.11 does not hold for CSTs with premises, i.e. they may be infinite. We show that they are nonetheless finished.

As in Theorem 4.8, consider any entry E occurring at some level of the CST T and lying on a noncontradictory path P. There are finitely many occurring at or above level n of the CST. So there is an m0 such that for every m >m0, Tm through level n is the same as T. If E is not reduced by mo, it will become the lexicographically least unreduced entry within a finite number of steps and will then become reduced.

2. This proof is similar to the proof of Lemma 5.2, with the added condition that V makes every element of S true. The base case of the induction, as in Lemma 5.2, is obvious because V is assumed to agree with the root. The induction step proceeds as in 5.2, except that Pn+1 may also contain TA for some A in S. But V(A) is assumed to be true.

Then let P be the union of the Pn.

3. If T is a finished tableau from S, every noncontradictory path P contains TA for every A in S. Define V as in Lemma 5.4. Define V and proceed as in Lemma 5.4. V agrees with all entries on P and thus V makes all elements in S true.

6. Let S = {A1, …An)

(a) => (b) . Assume (a). Then every V that makes all of S true also makes A true.

Let V be any valuation. If V (A1^ …An) = T, V(A) = T for all A in S. By (a), V(A) = T. This makes V( (A1^…^An) -> A) = T. If V(A1^…An) = F, the implication is also T. So it is true under every valuation.

(b) => (a). Assume that ( (A1^…^An) -> A) is valid and let V be any valuation making all of S true. Then V(A1^…^An) = T, so V(A) = T. Therefore A is a consequence of S.

(a) ó (c) and (b) ó (d) by Theorems 6.6 and 6.8. Since we have just shown that (a) ó (b), all four are equivalent.

12. Note that this wouldn’t be true if S is infinite. For example, if S is the set of all propositional letters, a CST from S will be infinite unless it is contradictory.

But now suppose that S is finite = {A1, …, An}. A CST from S is like a CST except that at stage m, we add TAm at the end of every noncontradictory path. This happens at most n times.

After all the TAm have been added, proceed as in the proof of Theorem 4.11.

Prove the soundness of the axiomatic system presented in Section 7.

Let T be provable in the system and let A1, …, An be a proof of T.

We prove soundness by induction on n.

Base case: n = 1. A1 must be an instance of one of the axioms listed in 7.1. So we must show that each of these is valid.

(i) A1 = (a -> (b -> a))

Let V be any valuation. If V(a) = F, then V((a -> (b -> a)) = T. If V(a) = T, then V(b-> a) = T, so again V(a -> (b -> a)) = T.

So every valuation makes A1 true, i.e., A1 is valid.

(ii) A1 = ((a -> (b-> g)) -> ((a->b) -> (a -> g)))

Let V be any valuation. If V(a) = F, then V(a ->g) = T. This makes V(((a->b) -> (a -> g))) = T and finally V(A1) = T.

If V(a) = T and V(b) = F, the V(a -> b) = F. This again makes V(((a->b) -> (a -> g))) = T and finally V(A1) = T.

If V(a) = V(b) = T and V(g) = F, then V((b-> g) = F. This makes V((a -> (b-> g))) = F and finally V(A1) = T.

If V(a) = V(b) = V(g) = T, then V(((a->b) -> (a -> g))) = T and finally V(A1) = T.

So every valuation makes A1 true, i.e., A1 is valid.

(iii) A1 = (not b -> not a) -> ((not b -> a) -> b)

Let V be any valuation. If V(b) = T, then V(((not b -> a) -> b)) = T and finally V(A1) = T.

If V(b) = F and V(a) = T, then V(not b -> not a) = F , so V(A1) = F.

If V(b) = V(a) = T, then V(((not b -> a) -> b)) = T and finally V(A1) = T.

So every valuation makes A1 true, i.e., A1 is valid.

Induction Step: Assume Ai is valid for all I < n.

Either a) An is an axiom or b) it follows by modus ponens from Ai and Aj = (Ai -> An) i, j < n.

Case a) proceeds exactly as in the base case.

For case b). Let V be any valuation. By the induction assumption, Ai and valid so V(Ai) = V(Aj) = T. Since Aj = (Ai -> An), V(An) must also = T. Thus An is valid.