Exam Questions
2006

ID


Question 1 [5 marks]

Given the sets $ A=\{\alpha, \beta,\gamma\}$ and $ B=\{\triangle, \nabla\}$ , list all the functions mapping $ A$ to $ B$ and all the functions mapping $ B$ to $ A$ .


Answer

Functions from $ A$ to $ B$ :       Functions from $ B$ to $ A$ :
  $ \alpha$ $ \beta$ $ \gamma$
$ f_1$ $ \triangle$ $ \triangle$ $ \triangle$
$ f_2$ $ \triangle$ $ \triangle$ $ \nabla$
$ f_3$ $ \triangle$ $ \nabla$ $ \triangle$
$ f_4$ $ \triangle$ $ \nabla$ $ \nabla$
$ f_5$ $ \nabla$ $ \triangle$ $ \triangle$
$ f_6$ $ \nabla$ $ \triangle$ $ \nabla$
$ f_7$ $ \nabla$ $ \nabla$ $ \triangle$
$ f_8$ $ \nabla$ $ \nabla$ $ \nabla$
     
  $ \triangle$ $ \nabla$
$ g_1$ $ \alpha$ $ \alpha$
$ g_2$ $ \alpha$ $ \beta$
$ g_3$ $ \alpha$ $ \gamma$
$ g_4$ $ \beta$ $ \alpha$
$ g_5$ $ \beta$ $ \beta$
$ g_6$ $ \beta$ $ \gamma$
$ g_7$ $ \gamma$ $ \alpha$
$ g_8$ $ \gamma$ $ \beta$
$ g_9$ $ \gamma$ $ \gamma$


Question 2 [6 marks]

In Propositional Logic, $ \lnot$ (not) and $ \land$ (and) are sufficient to express all other operators. The operator $ XOR$ is defined by the following truth table:

p q p XOR q
T T F
T F T
F T T
F F F



Expess $ p \,XOR\, q$ using only $ \lnot$ and $ \land$ .


Answer

$ p \,XOR\, q$ means p OR q but NOT p AND q, which translates in $ \lnot(\lnot p \land \lnot q) \land \lnot(p \land q)$


Question 3 [10 marks]

Using resolution, show that the following sentence is valid.

$ \lnot((p \land \lnot q) \lor \lnot(\lnot r \to \lnot q)) \to r \lor \lnot p$

HINT. Negate, put into clausal form, and derive the empty clause.


Answer

Given $ \lnot((p \land \lnot q) \lor \lnot(\lnot r \to \lnot q)) \to r \lor \lnot p$ , it's negation is:
Negation:

$ \lnot(\lnot((p \land \lnot q) \lor \lnot(\lnot r \to \lnot q)) \to r \lor \lnot p)$
Clausal form:

  $ \lnot(\lnot((p \land \lnot q) \lor \lnot(\lnot r \to \lnot q)) \to r \lor \lnot p)$
I $ \lnot (\lnot \lnot((p \land \lnot q) \lor \lnot(\lnot \lnot r \lor \lnot q)) \lor (r \lor \lnot p))$
N $ \lnot(((p \land \lnot q) \lor \lnot (r \lor \lnot q))\lor(r \lor \lnot p))$
  $ \lnot((p \land \lnot q)\lor\lnot(r \lor \lnot q))\land\lnot (r \lor \lnot p)$
  $ \lnot(p \land \lnot q) \land (r \lor \lnot q) \land (\lnot r \land p)$
D  
O $ \{\lnot p, q\}$
  $ \{r, \lnot q\}$
  $ \{\lnot r\}$
  $ \{p\}$

Resolution:

1. $ \{\lnot p, q\}$ P
2. $ \{r, \lnot q\}$ P
3. $ \{\lnot r\}$ P
4. $ \{p\}$ P
5. $ \{\lnot q\}$ 2,3
6. $ \{q\}$ 1,4
7. $ \{\}$ 5,6


Question 4 [6 marks]

An equivalence relation is a binary relation that is reflexive, symmetric and transitive. Express that the binary relation $ r$ is an equivalence relation in relational logic (use quantifiers).


Answer

Reflexivity: $ \forall x. r(x, x)$
Symmetry: $ \forall x \forall y. (r(x, y) \to r(y, x))$
Transitivity: $ \forall x \forall y \forall z. r(x, y) \land r(y, z) \to r(x, z))$


Question 5 [6 marks]

Assume the universe of discourse is real numbers and we are using infix notation for the $ +$ and the $ =$ . For each of the following sentences, state whether it is true or false.

  1. $ \forall x. \forall y. \exists z. (x + y =z)$
  2. $ \forall x. \exists z. \forall y. (x + y =z)$
  3. $ \forall x. \forall z. \exists y. (x + y =z)$


Answer


  1. TRUE: this is the definition of sum-for all $ x$ and $ y$ combinations, there is a number $ z$ that's equal to the sum of $ x$ and $ y$ .
  2. FALSE: this is saying that for all values of $ x$ , there is some value $ z$ such that for any number $ y$ , $ x + y = z$ .
  3. TRUE: this says that for all $ x$ and all $ z$ , there is some $ y$ .


Question 6 [6 marks]

Give a most general unifier (if one exists) for the following statements:
$ p(f(x,a), f(f(b,a)))$    and $ p(z, f(z))$


Answer

$ \{z \leftarrow f(b,a), x \leftarrow b\}$


Question 7 [7 marks]

Assume that the binary relation $ r(x,y)$ has the properties of irreflexivity (i.e., not reflexive) and transitivity. Using resolution, show that $ r$ is asymmetric (i.e., if $ r(x,y)$ then not $ r(y, x)$ ).


Answer

1. $ \{\lnot \, r(w, w)\}$ Premise
2. $ \{\lnot \, r(x,y), \lnot \,r(y, z), r(x, z)\}$ Premise
3. $ \{r(a, b)\}$ Goal negation
4. $ \{r(b, a\}$ Goal negation
5. $ \{\lnot\, r(b, z), r(a, z)\}$ 2, 3
6. $ \{r(a, a)\}$ 4, 5
7. $ \{\}$ 1, 6

because

binary relation $ r$ is non-reflexive: $ \forall w.(\lnot\, r(w, w))$
binary relation $ r$ is transitive: $ \forall x \forall y \forall z.(r(x, y) \land r(y, z) \to r(x, z))$
if $ r(x,y)$ then not $ r(y, x)$ means $ \forall x. \forall y. (r(x, y) \to \lnot r(y, x))$ , that is

$ \forall x. \forall y. (\lnot \, r(x, y) \lor \lnot r(y, x))$ and then we should negate the goal.


Question 8 [10 marks]

Give the intial state, goal test, successor function, and cost function for the following problem. Choose a formulation that is precise enough to be implemented.

You have to colour a planar map using only three colours, with no two
adjacent regions having the same colour.


Answer


Initial state:
an uncoloured map
Goal test:
each region on the map is shaded in one of (at most ) three colours, and no region shares a colour with its adjacent regions.
Successor function:
for a partially-coloured map, the successor of a partially-coloured map, on which an agent colours a region, is a copy of the map with the new region coloured in.
Cost function:
if the cost of colouring a region is independent of the colour used, all paths to the goal will have the same cost. No solution is preferred over any other, so let the cost of colouring a state be 1.


Question 9 [10 marks]

Prove that if an heuristic is consistent, it must be admissible.


Answer

An heuristic is consistent iff for every node $ n$ and every successor $ n^\prime$ of $ n$ generated by an action $ a$ it is true that $ h(n) \le c(n, a, n^\prime) + h (n^\prime)$

The proof is by induction on the number $ k$ of nodes on the shortest path to any goal from $ n$ . Let $ h^*(n)$ be the true cost of getting from $ n$ to the goal. We will work backwards from the goal to show that $ h(n) \le h^*(n)$ for every node $ n$ . For $ k = 1$ , let $ n^\prime$ be the goal node and $ n$ one step prior, then $ h(n) \le c(n, a, n^\prime) + h (n^\prime)=c(n,a, n^\prime)=h^*(n)$ . For the inductive case, assume $ n^\prime$ is on the path $ k$ steps from the goal and that $ h(n^\prime)$ is admissible (by inductive hypothesis), then $ h(n) \le c(n, a, n^\prime) + h (n^\prime) \le c(n, a, n^\prime) + h^* (n^\prime) =h^*(n)$ where $ h^*(n)$ is the true cost of getting from $ n$ to the goal. Since $ h(n) \le h^*(n)$ , $ h(n)$ at $ k+1$ steps from the goal is admissible.


Question 10 [10 marks]

Consider a state space where the start state is number $ 1$ , and the successor function for state $ n$ returns two states labeled $ 2n$ and $ 2n + 1$ . Can you apply best-first search to this problem? What would be a good heuristic? List the order in which nodes are visited in searching for the goal of $ 11$ using your heuristic.

Hint. Draw the portion of the state space for states 1 through 15.


Answer

The state space is illustrated by a full binary tree of depth 3 with nodes at level $ i$ numbered from $ 2^i$ to $ 2^{i + 1} -1$ .

We can represent a path of length $ d$ by a binary string with a $ 1$ for the initial state followed by a 0 for every left branch and a $ 1$ for every right branch (just the binary representation of the node number). Let our heuristic $ h(n)$ take on a value of 0 if the path to our current state agrees with the beginning of the path to the goal state and $ 1$ otherwise. This results in a search path of $ 1, 2, 5, 11$ , as we would hope.


Question 11 [5 marks]

Prove the following assertion

$ \alpha$ is valid if and only if $ True \models \alpha$


Answer

Remember: $ \alpha \models \beta$ iff in every model in which $ \alpha$ is true, $ \beta$ is also true.

A valid sentence is one that is true in all models. The sentence True is also valid in all models. So if $ \alpha$ is valid then $ True \models \alpha$ (because both True and $ \alpha$ hold in every model), and if the entailment holds then $ \alpha$ must be valid, because it must be true in all models, because it must be true in all models in which True holds.


Question 12 [8 marks]

Decide whether each of the following sentences is valid, unsatisfiable or neither. Verify your decisions using truth tables or the equivalence rules from lecture.

  1. $ smoke \rightarrow smoke$
  2. $ (smoke \rightarrow fire) \rightarrow (\neg smoke \rightarrow \neg fire)$
  3. $ ((smoke \wedge heat)\rightarrow fire) \leftrightarrow ((smoke \rightarrow fire) \vee (heat \rightarrow fire))$
  4. $ (big \wedge dumb) \vee \neg dumb$


Answer


  1. VALID. By truth table: both $ False \rightarrow False$ and $ True \rightarrow True$ are true.
  2. SATISFIABLE. By truth table: it is true when $ smoke$ is true and $ fire$ is true, but false when $ smoke$ is false and $ fire$ is true.
  3. VALID. By equivalences: apply implication elimination, distributivity, and associativity to make each side of the equivalence the same.
  4. SATISFIABLE. By truth table: true when both $ big$ and $ dumb$ are true, but false when $ big$ is false and $ dumb$ is true.


Question 13 [4 marks]

Decide and explain why the following is (not) a valid sentence:

$\displaystyle \forall x \ smart(x) \lor (x = x)$


Answer

Valid. For every $ x$ , $ x=x$ is true, so the disjunction is true.


Question 14 [7 marks]

A knight moves on a chessboard two squares up, down, left, or right, followed by one square in one of the two directions perpendicular to the first part of the move (i.e., the move is L-shaped). Suppose the knight is on an unbound board at square $ (0,0)$ and we wish to move it to square $ (x,y)$ in the smallest number of moves. Without constructing a solution, explain how to decide whether the required number of moves is even or odd.


Answer

Each move changes the colour of the square on which the knight is resting. This parity property is easy to prove. Hence, if the goal square is a different colour from the start square (i.e., $ \vert c-a\vert+\vert d-b\vert$ is odd) then an odd number of moves are required, otherwise an even number of moves are required.