Proof. By Konig lemma. Because a contradictory path must be finite and infinite tree with finite branch must has a infinite path. It is contradictory In order to prove the finiteness of every CSt, we first give the following definition Definition 7. We define d(a), the degree of a proposition a by induction 1. if a is a propositional letter, then d(a)=0 2. if a is nB, then d(a)=d(B)+ 3. if a is BV?,B∧γ,orB→T, then d(a)=d(B)+d()+1 The degree of a signed proposition. Ta or Fa is the degree of a. If P is a path in a tableau T, then d(p) the degree of P is the sum of the degree of the signed propositions on P that are not reduced Theorem 8. Every CsT is finite Proof. While path extending, an entry could be split into two branches. whatever, the degree of every path decrease for each reduction. So we have d(Pm+1)< d(Pm) where Pm+1 is an extension of p With this Theorem, we do know something wrong if we run into a tableau which can never be finished Exercises 1. Ex 4/ page 36 2. Ex 6/ page 36 3. Ex 9/ page 36 4. Prove the following tautology by tableau proof (a)(q→r)→(-q→→p)→(p→r) (b)(P∧q)→r)+(p→(q→+r) 5. Prove of refute the following proposition. (If negative, find the counterexample) (a)(a→B)→(a→7)→(a→(3→) (b)(a→B)→(6→1)→(a→)Proof. By K¨onig lemma. Because a contradictory path must be finite and infinite tree with finite branch must has a infinite path. It is contradictory. In order to prove the finiteness of every CST, we first give the following definition. Definition 7. We define d(α), the degree of a proposition α by induction. 1. if α is a propositional letter, then d(α) = 0. 2. if α is ¬β, then d(α) = d(β) + 1. 3. if α is β ∨ γ, β ∧ γ, or β → γ, then d(α) = d(β) + d(γ) + 1. The degree of a signed proposition T α or F α is the degree of α. If P is a path in a tableau τ , then d(P) the degree of P is the sum of the degree of the signed propositions on P that are not reduced on P. Theorem 8. Every CST is finite. Proof. While path extending, an entry could be split into two branches. whatever, the degree of every path decrease for each reduction. So we have d(Pm+1) < d(Pm) where Pm+1 is an extension of Pm. With this Theorem, we do know something wrong if we run into a tableau which can never be finished. Exercises 1. Ex 4/ page 36 2. Ex 6/ page 36 3. Ex 9/ page 36 4. Prove the following tautology by tableau proof (a) (q → r) → ((¬q → ¬p) → (p → r)) (b) ((p ∧ q) → r) ↔ (p → (q → r)) 5. Prove of refute the following proposition.(If negative, find the counterexample) (a) ((α → β) → (α → γ)) → (α → (β → γ)) (b) (α → β) → ((β → γ) → (α → γ)) 4