;;;	CS141 Midterm
;;;	Some of these answers are not unique.  This is just one of the
;;;   	many possible solutions that will give you 100/100.


1. (10) Evaluate the following expressions:

(a) (let ((x (+ 2 3)))
	(cond((> x 7) "interesting")
		((and (= x 6) nil) "Amazing!")
		(t (or "Disappointing!" nil))))

answer:	DISAPPOINTING!

(b) (rest (first (rest `(a (b c) d))))

answer:	(c)

(c) (not (> 7 (first (cons 2 (cons 8 nil)))))

answer:	nil






2. (10) Consider the following Lisp function:

answer:	(defun anon (s)
	   (cond ((null s) nil)
		 ((atom s) (list s))
		 (t (append (anon (first s))
		 (anon (rest s))))))

(a) What is the value of (anon (list nil))?

answer:	nil

(b) What is the value of (anon `(a (a (a (b)))))?

answer:	(a a a b)





3. Write a recursive Lisp function that takes two lists of numbers of
the same length and computes the sum of the products of the ith elements
(e.g., (sumproducts `(2 3) `(4 5)) => 2 x 4 + 3 x 5 = 23)

answer:	(defun sumproducts (x y) 
	  (cond ((null x) 0)
	    ((null y) 0)
              (t (+ (*(first x) (first y)) (sumproducts (rest x) (rest y))))))




4. Label the following formulas as either satisfiable (but not valid),
valid, or not satisfiable, given the specified set of interpretations. 

(a) (and (not (or (not a) b)) (and (not b) (not a)))
	given all possible interpretation (assignments to {a, b})

answer:	not satisfiable

(b) (or (and (not a) b) (and a (not b)))
	given the interpretations {((a false) (b true)),((a true) (b (false))}

answer:	valid






5. (10) Given the following axioms and the rules of inference, modus
ponens and conjunction, prove b or state that it is not a theorem.

answer:
	1. 	e				AXIOM
	2. 	d				AXIOM
	3. 	t				AXIOM
	4. 	e -> s				AXIOM
	5. 	(i ^ t ^ h) -> w		AXIOM
	6. 	(i ^ d ^ s) -> a		AXIOM
	7. 	s -> i				AXIOM
	8. 	(a ^ d) -> b			AXIOM

	9. 	s				mp 1,4
	10.	i				mp 7,9
	11.	i ^ d ^ s			conj 2,9,10
	12.	a				mp 6,11
	13.	a ^ d				conj 2,12
	14.	b				mp  8, 13    QED







6. Represent the following in first-order predicate logic. Use the predicates mushroom(x), 
purple(x) and poisonous(x).
(a) There are no purple mushrooms.

answer:	forall x, mushroom(x) -> ~purple(x)

(b) There is only one poisonous mushroom and it is purple.

answer:	forall x, exists y,
	mushroom(x) ^ mushroom(y) ^ poisonous(y) ^  ~(equal x y)
				->  ~poisonous(x) ^ purple(y)







7. For each of the following pairs of literals, determine if they
unify. If so, give the most general substitution; if not, give a brief
explanation. x, y and z are variable symbols, a and b are constants, f
is a function symbol, and P is a predicate.

(a) 	P(x,x) 		P(z,a)

answer:	Unifies, x -> z,	x -> a

(b) 	P(a,f(y))	P(x,x)

answer: not unify because cannot unify constants a

(c) 	P(f(y),y,x)	P(z,f(a),f(b))

answer: unifies, f(y) -> z,	y -> f(a), 	x -> f(b)







8. Determine which blind-search method, depth-first, breadth-first, iterative-deepening, is the most appropriate for the following search spaces.

(a) A very large tree-structured search space in which there exists a goal node near the starting node and the next function is very expensive to compute.

answer:	breadth-first

(b) An infinite tree-structured search space.

answer:	iterative deepening 

(c) A finite but large and arbitrarily-structured search space in which checking that a node has been previously visited is cheap.

answer:	depth-first






9. Consider the following grid-structured search space shown in Fig. 1
in which the goal is marked G, the starting node is marked S, and
obstacles are marked X. The nodes returned by the next function when
at a location H are marked N in Fig.2.


	Recall that on each iteration, best-first search applies the
goal predicate to the first element of the list of nodes unless that
list is empty. In sorting nodes that have the same heuristic value,
assume that ties are broken on the basis of when nodes are added to
the list of nodes to explore next (earliest first) and among the next
nodes of a particular node ties are broken on the basis of the
ordering shown in Fig. 3 (smallest ranking first). Also assume that
previously visited nodes are never added to the list of nodes to
explore next.

	Determine the sequence of locations to which the goal
predicate is applied using best-first search in which the heuristic
function at a node n is the absolute value of 
	(- (COORD-x c) (COORD-x g))) 
where c is the coordinate associated with n and g is the
coordinate associated with the goal. For example, in Fig. 1, the
x-coordinate of the node marked E is 1.
	Write the sequence that the nodes are visited in the grid below:

answer:

		*  * 10 11  G
		*  *  9  X  *
		*  *  7  5  X
		*  S  1  2  3
		*  *  8  6  4

where * = nodes not visited.







10. Consider the following axioms in the situation calculus.

	1. holds(0,f)
	2. forall s, holds(s,f) -> holds(result(s,a),g)
	3. forall s, (holds(s,g)^holds(s,f)) -> holds(result(s,b),h)

a) Determine s such that holds(s,g).

answer:	s=result(0, a)

b) Using conjunction, modus ponens and universal instantiation, prove 
	holds(result(result(0,a),b),h), adding frame axioms as needed.

answer:	4.  holds(0,f) -> holds(result(0,a) , g)		UI 2
	5.  holds(result(0,a),g)                            	MP 1,4
	6.  forall s, holds(s,f) -> holds(results(s,a), f)   frame axiom added
	7.  holds(0, f) -> holds (results (0,a),f)     		UI 6
	8.  holds (result(0,a),f) 				MP 1,7
	9.  holds(result(0,a),g)^ holds (result(0,a),f) 	CONJ 5,6
	10. (holds(result(0,a),g)^holds(result(0,a),f))
		-> holds(result(result(0,a),b),h)    		UI 3
	11. holds(result(result(0,a),b),h)	 		MP 9,10
	12. QED
