16 Oct 2011

School

Department

Course

Professor

For unlimited access to Class Notes, a Class+ subscription is required.

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.

∀x•f(x) = g(x, a),∀x•P(x)⇒Q(f(x)) |=

ND ∃x• ¬P(f(x)) ∨Q(g(f(x), x))

(ais a constant)

Soln:

1∀x•f(x) = g(x, a) premise

2∀x•P(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,4−9,10 −11

13 ∃x• ¬P(f(x)) ∨Q(g(f(x), x)) ∃I 12

1

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.

(a) State your theory.

(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. ∀a•horiz row(a)∨vert row(a)⇔wins(a)

C. ∀a•(∃r•0≤r < J ∧(∀c•0≤c < J ⇒(loc(r, c) = a)) ⇔horiz row(a)

D. ∀a•(∃c•0≤c < J ∧(∀r•0≤r < J ⇒(loc(r, c) = a)) ⇔vert row(a)