COMP-424: Artificial intelligence Homework 2

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.

    d) Not for marks: Solve this problem in as many ways as you can! You may want to write code to do this. For example, you could implement backtracking, or try a local search method.
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 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

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.