CS245 Lecture Notes - Lecture 2: Binary Tree, Structural Induction, Logical Possibility

• School: University of Waterloo
• Department: Computer Science
• Course: CS245
• Professor: Lila Kari

Document Summary

Sketch of solutions (1) translation of the argument from english into propositional logic: p 1: t b m, p 2: t, p 3: m h, p 4: h, c: b. T b m h b m t b m m h h p 1 p 2 p 3 p 4 5 b. K e s k e k s s e p 1 p 2 p 3 e. Prove by contradiction that the argument is sound (valid). Indeed, assume that the argument is not sound (valid). Then there exists a value assignment v such that v(p1) = 1, v(p2) = 1, v(p3) = 1, v(p4) = 1, but v(concl. ) From v(p3) = 1 we deduce that v(l) = 0. = 0 we deduce that v( c) = 1 and v(a o) = 0, which implies v(c) = 0. As v(l) = v(c) = 0 and using the fact that v(p2) = 1, we deduce that v(o) = 1.