Description
Question 1: Constraint Satisfaction
Consider the problem of placing two knights and two queens on a 4×4 chess board such that no two pieces attack each
other. Suppose that rows 1 and 2 must each contain a knight, and rows 3 and 4 must each contain a queen, as follows:
a) Formulate this problem as a CSP with binary constraints. List the variables, their domains, and the
constraints. Draw the constraint graph.
b) Run AC-3 on this problem, then apply backtracking search to find a solution if possible.
c) Starting from the original problem (i.e., without running AC-3), run backtracking search with one-step
forward checking.
Question 2: Search and Game Playing
You are playing rock-paper-scissors with your friend, but with a twist. The game now consists of three rounds, and
each round, players may not play something that they have played before. So, if you play rock the first round, you
cannot play it again in rounds two and three. The winner of the game is the player who wins the most rounds.
a) Draw the AND-OR tree associated with this game.
b) In the first round, you play paper and your friend plays rock, giving you the first win. Can you guarantee a
win of the game overall? Explain by extracting a contingency plan from the AND-OR tree above. Check your
answer by reformulating the AND-OR tree into a game tree where you apply the Minimax algorithm.
Question 3: Propositional Logic
a) How many models are there for each of the following statements in propositional logic?
i) (𝐴 ∧ 𝐵) ∨ 𝐶
ii) 𝐴 ∧ (𝐴 ⇒ 𝐵) ∧ ¬𝐵
iii) ¬(𝐴 ∧ 𝐵 ∧ 𝐶 ∧ 𝐷 ∧ 𝐸) ∨ (𝐵 ∧ 𝐶)
b) State whether each of the following is valid, unsatisfiable, or satisfiable. Support your answers with a truth
table or a proof using rules of logical inference.
i) ((𝐴 ⇒ 𝐵) ∧ (𝐴 ∨ 𝐶)) ⇒ (𝐵 ∨ 𝐶)
ii) ((𝐴 ∨ 𝐵) ⇒ 𝐶) ⇒ (𝐴 ⇒ 𝐶) ∧ (𝐵 ⇒ 𝐶)
Question 4: First Order Logic
This question is not for marks, and will not be marked. It is here to help you prepare for the midterm.
(Adapted from Russell & Norvig, 8.10)
Consider a vocabulary with the following symbols:
Occupation(p, o): Predicate. Person p has occupation o
Customer(p1, p2): Predicate. Person p1 is a customer of person p2.
Boss(p1, p2): Predicate. Person p1 is a boss of person p2.
Doctor, Surgeon, Lawyer, Actor: Constants denoting occupations.
Emily, Joe: Constants denoting people.
a) Use these symbols to write the following assertions in FOL:
i) Emily is either a surgeon or a lawyer.
ii) Joe is an actor, but he also holds another job.
iii) All surgeons are doctors.
iv) Joe does not have a lawyer.
v) Emily has a boss who is a lawyer
vi) There exists a lawyer all of whose customers are doctors.
vii) Every surgeon has a lawyer.
b) Give a model of the above FOL such that clauses i) – vii) above are satisfied.
