CS447 Lecture 7: L17.pdf
Document Summary
Let"s look at one of the examples from last time again. We construct a truth table as follows: p : ( a b) c. Note that we use certain patterns to see whether a clause determines p in the truth table. For c, we check adjacent rows in the truth table. For b, we check pairs of rows separated by one row; and for a we check one from the top half and one from the bottom half. We"ve seen the brute-force way to gure out when a clause determines a predicate. It wouldn"t scale, since truth tables grow exponentially. There are also symbolic ways of guring out when a clause determines a predicate; here"s one way that the textbook presents. For predicate p and clause c: let pc=true represent p with c replaced by true, and pc=false represent p with c replaced by false. Assume that c occurs exactly once in p, hence 0 times in pc=true and pc=false.
