COMP424 Homework 2 Solution

General instructions.
• This is an individual assignment. You can discuss solutions with your classmates, but should only exchange information orally, or else if in writing through the discussion board on myCourses. All other forms of written exchange are prohibited.
• Unless otherwise mentioned, the only sources you should need to answer these questions are your course notes, the textbook, and the links provided. Any other source used should be acknowledged with proper referencing style in your submitted solution.
• For each problem, you can solve manually, or write a program to help you. You can use a programming language of your choice. You can modify code from other sources if you provide adequate citation; this cannot be code from other students in the class.
• Submit a single pdf document containing all your pages of your written solution on your McGill’s myCourses account. You can scan-in hand-written pages. If necessary, learn how to combine many pdf files into one.
• Submit any code developed to answer questions as a separate file to McGill’s myCourses.

Question 1: Constraint Satisfaction
Consider the following problem:

Find a 10-digit number such that the first digit is the number of zeros in the number, the second digit is the number of ones in the number, …, and the tenth digit is the number of nines in the number. The first digit must be non-zero.

a) Formulate this problem as a CSP. List the variables, their domains, and the constraints. Draw the constraint graph.

b) Show the first ten steps of backtracking search on this problem, where you order the variables from the first digit to the last digit, and the values from lowest to highest. Recall that backtracking search uses a depth-first strategy to expand the search tree.

c) Show the first ten steps of backtracking search on this problem with one-step forward checking, where you order the variables from the first digit to the last digit, and the values from lowest to highest.



Question 2: Search and Game Playing

a) Draw the AND-OR tree associated with this game.

b) In the first round, you play rock and your friend plays scissors, 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.

c) 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

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.