Class Notes (1,100,000)
CA (630,000)
UW (20,000)
CS (1,000)
CS245 (60)
Lecture

# Assignment #4 + Solution Winter 2009

Department
Computer Science
Course Code
CS245
Professor
Nancy Day

This preview shows page 1. to view the full 5 pages of the document. CS 245 Winter 2009
Assignment 4
Due: Thu 5 Mar 2009 10am in the CS245 Drop Boxes
40 marks
SOLUTION SET
There may be multiple correct answers to some of these questions.
1. (8 marks) Determine whether the following argument is valid or invalid. If it is valid, prove its
validity using natural deduction. If it is invalid, provide a counterexample and demonstrate
that the argument is invalid. Do not use any rules from transformational proof.
xf(x) = g(x, a),xP(x)Q(f(x)) |=
ND x• ¬P(f(x)) Q(g(f(x), x))
(ais a constant)
Soln:
1xf(x) = g(x, a) premise
2xP(x)Q(f(x)) premise
3P(f(a)) ∨ ¬P(f(a)) LEM
4P(f(a)) assumption
5P(f(a)) Q(f(f(a))) E 2
6Q(f(f(a))) E 4,5
7f(f(a)) = g(f(a), a)E 1
8Q(g(f(a), a)) = E 6,7
9¬P(f(a)) Q(g(f(a), a)) I 8
10 ¬P(f(a)) assumption
11 ¬P(f(a)) Q(g(f(a), a)) I 10
12 ¬P(f(a)) Q(g(f(a), a)) cases 3,49,10 11
13 x• ¬P(f(x)) Q(g(f(x), x)) I 12
1

Unlock to view full version

Only page 1 are available for preview. Some parts have been intentionally blurred. 2. (24 marks) Construct a theory about a tic-tac-toe-like game on a J ×J grid, where J is a
constant. The grid is marked with X’s by one player and O’s by the other player. Use the
following functions and predicates as well as arithmetic predicates such as :
wins(x) – means the player with mark xwins
horiz row(x) – means the player with mark xhas a horizontal line
vert row(x) – means the player with mark xhas a vertical line
loc(r, c) – returns the mark at row rand column cin the grid
A player wins if they have a horizontal or vertical line of their marks. Your formalization
should ensure that whenever the function loc is used, its arguments are greater than or equal
to 0 and less than J.
(b) Use your theory to prove: if J=2 and the locations (0,0) and (0,1) have the mark X, then
the player with mark Xwins.
(c) Use your theory to prove: if every column has the mark Xin some row then the player
with mark Ocannot have a vertical line.
(a) Theory:
Constants: X,O, J
Functions:
loc(r, c) – returns the mark at row rand column cin the grid
Predicates:
wins(x) – means the player with mark xwins
horiz row(x) – means the player with mark xhas a horizontal line
vert row(x) – means the player with mark xhas a vertical line
Axioms:
A. ¬(X=O)
B. ahoriz row(a)vert row(a)wins(a)
C. a(r0r < J (c0c < J (loc(r, c) = a)) horiz row(a)
D. a(c0c < J (r0r < J (loc(r, c) = a)) vert row(a)