1002 Lecture Notes - Atomic Sentence
5 Feb 2013
School
Department
Course
Professor
Document Summary
Length figures in the proof that the tree method is decidable. In that proof, attention is drawn to the fact that all the decomposition rules are such that longer sentences are checked off (so not decomposed again) and decomposed into at most 4 shorter sentences. Combined with a proof that the tree for a finite set of sentences cannot have infinitely many branches, this helps to establish that decomposition cannot go on forever. Even if the tree does not close, eventually only sentences of lengths 1 and 2 (literals) will be left, which means the branches must be completed open. Length also figures in the proof that the tree method is complete and the related proof that sl is compact. Hence, no truth value assignment can assign a t to both a and ~a. So there can be no truth value assignment on which all the sentences in 1 are true and p1 is false.
