chapter  9
7 Pages

Truth-Tables as a Decision Procedure

WithG. E. Hughes, D. G. Londey

For every class of objects we may formulate questions of the form: ‘Is so-and-so a member of the class?’ And there is a clear sense in which any given object either is or is not a member of a particular class. I am either a member of the class of people over 6 feet tall or I am not; Queenie the elephant either is or is not a triangle; 2071 either is or is not a prime number; ‘There are animals on Mars’ is either a true statement or not; and so on. But, although there is, in this sense, always an answer to the question, we do not always know how to find this answer. What we need is a recipe for deciding whether or not an object, x, is a member of a class, K. We have already described such a recipe for the class of well-formed formulae of PC. The Rules of Formation provide us with a procedure for deciding of any arbitrarily chosen object whether it is a wff of PC. Such a recipe or procedure is called a decision procedure for the class. Such a procedure must be effective - that is, it must be precisely statable, reliable and completable in a finite time. (It must be the sort of procedure which could be carried out by a suitably constructed machine.)