Question 1 [5 marks]
Given the sets and , list all the functions mapping to and all the functions mapping to .
|Functions from to :||Functions from to :|
Question 2 [6 marks]
In Propositional Logic, (not) and (and) are sufficient to express all other operators. The operator is defined by the following truth table:
|p||q||p XOR q|
Expess using only and .
Question 3 [10 marks]
Using resolution, show that the following sentence is valid.
HINT. Negate, put into clausal form, and derive the empty clause.
Question 4 [6 marks]
An equivalence relation is a binary relation that is reflexive, symmetric and transitive. Express that the binary relation is an equivalence relation in relational logic (use quantifiers).
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.
Question 6 [6 marks]
Give a most general unifier (if one exists) for the following statements:
Question 7 [7 marks]
Assume that the binary relation has the properties of irreflexivity (i.e., not reflexive) and transitivity. Using resolution, show that is asymmetric (i.e., if then not ).
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.
Question 9 [10 marks]
Prove that if an heuristic is consistent, it must be admissible.
The proof is by induction on the number of nodes on the shortest path to any goal from . Let be the true cost of getting from to the goal. We will work backwards from the goal to show that for every node . For , let be the goal node and one step prior, then . For the inductive case, assume is on the path steps from the goal and that is admissible (by inductive hypothesis), then where is the true cost of getting from to the goal. Since , at steps from the goal is admissible.
Question 10 [10 marks]
Consider a state space where the start state is number , and the successor function for state returns two states labeled and . 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 using your heuristic.
Hint. Draw the portion of the state space for states 1 through 15.
We can represent a path of length by a binary string with a for the initial state followed by a 0 for every left branch and a for every right branch (just the binary representation of the node number). Let our heuristic 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 otherwise. This results in a search path of , as we would hope.
Question 11 [5 marks]
Prove the following assertion
is valid if and only if
A valid sentence is one that is true in all models. The sentence True is also valid in all models. So if is valid then (because both True and hold in every model), and if the entailment holds then 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.
Question 13 [4 marks]
Decide and explain why the following is (not) a valid sentence:
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 and we wish to move it to square in the smallest number of moves. Without constructing a solution, explain how to decide whether the required number of moves is even or odd.