# Assignment #4 + Solution Winter 2009

82 views5 pages
16 Oct 2011
School
Course
Professor

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 document

This preview shows pages 1-2 of the document.
Unlock all 5 pages and 3 million more documents.

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)
Unlock document

This preview shows pages 1-2 of the document.
Unlock all 5 pages and 3 million more documents.

# Get access

\$10 USD/m
Billed \$120 USD annually
Homework Help
Class Notes
Textbook Notes