This

**preview**shows half of the first page. to view the full**3 pages of the document.**CS 245 Winter 2009

Assignment 2

Due: Thu 29 Jan 2009 10am in the CS245 Drop Boxes

30 marks

SOLUTION SET

There may be multiple correct answers to some of these questions.

1. (25 marks) For each of the following problems, determine whether the argument is valid or

invalid. If it is valid, prove its validity using the indicated proof method (natural deduction

or semantic tableaux). If it is invalid, provide a counterexample and demonstrate that the

argument is invalid.

(a) Natural Deduction: Â¬(câˆ¨d), a â‡’bâˆ¨c, b â‡’d|=

ND Â¬a

This argument is valid.

1Â¬(câˆ¨d) premise

2aâ‡’bâˆ¨cpremise

3bâ‡’dpremise

ï£®

ï£¯

ï£¯

ï£¯

ï£¯

ï£¯

ï£¯

ï£¯

ï£¯

ï£¯

ï£¯

ï£¯

ï£¯

ï£¯

ï£¯

ï£°

4aassumption

5bâˆ¨câ‡’E 2,4

ï£®

ï£¯

ï£¯

ï£°

6bassumption

7dâ‡’E 3,6

8câˆ¨dâˆ¨I 7

9false Â¬E 1,8

ï£®

ï£°

10 cassumption

11 câˆ¨dâˆ¨I 10

12 false Â¬E 1,11

13 false cases 5,6âˆ’9,10 âˆ’12

14 Â¬aRAA 4 âˆ’13

1

###### You're Reading a Preview

Unlock to view full version