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

UNIVERSITY OF WATERLOO

Computer Science 245, Winter 2016

Applied Logic for Computer Science

ASSIGNMENT 2

Given: Monday, January 18, Due: Tuesday. January 26, 10:00am

Sketch of solutions

(1) Translation of the argument from English into propositional logic:

•P1: T→B∨M

•P2: T

•P3: M→H

•P4: ¬H

•C:B

P2 P1 P3 P4 5

T B M H B∨M T →B∨M M →H¬H P 1∧P2∧P3∧P4 5 →B

0 0 0 0 0 1 1 1 0 1

0 0 0 1 0 1 1 0 0 1

0 0 1 0 1 1 0 1 0 1

0 0 1 1 1 1 1 0 0 1

0 1 0 0 1 1 1 1 0 1

0 1 0 1 1 1 1 0 0 1

0 1 1 0 1 1 0 1 0 1

0 1 1 1 1 1 1 0 0 1

1 0 0 0 0 0 1 1 0 1

1 0 0 1 0 0 1 0 0 1

1 0 1 0 1 1 0 1 0 1

1 0 1 1 1 1 1 0 0 1

1 1 0 0 1 1 1 1 1 1

1 1 0 1 1 1 1 0 0 1

1 1 1 0 1 1 0 1 0 1

1 1 1 1 1 1 1 0 0 1

1

## 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.