CS245 Study Guide - Propositional Calculus, Khoein, Free Variables And Bound Variables
Document Summary
In this module, we will extend our previous system of natural deduction for propositional logic, to be able to deal with predicate logic. The main things we have to deal with are equality, and the two quanti ers (existential and universal). All of the rules from propositional logic carry over to predicate logic, and there are six new rules (introduction and elimination for each of the new features). We will also introduce one derived rule not in the textbook, for convenience. The rule for introducing equality is fairly simple: it simply says that any term t is equal to itself, and that no premises are needed to conclude this. The elimination rule for equality is more interesting; it describes how substitution may be used in formulas. If t1 and t2 are free for z in , then we may substitute the term t2 for t1 in . But our de nition of substitution substitutes a term for a variable.
