Class Notes (1,100,000)
CA (650,000)
UW (20,000)
CS (1,000)
CS245 (70)
Lecture

# Assignment #2 + Solution Winter 2009

Department
Computer Science
Course Code
CS245
Professor
Nancy Day

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