CS 470 - Problem Set 4

Assigned:Friday February 14
Deadline:Do not submit

Reading

Russell and Norvig, "Artificial Intelligence: A Modern Approach", Third Edition, 2010. Chapters 6-9. pdf

No Deliverable

This assignment is to prepare you for the midterm. We will publish the answers prior to the midterm.

Chapter 6

  • 6.1. How many solutions are there for the map-coloring problem in Figure 6.1? How many solutions if four colors are allowed? Two colors?
  • 6.5 Solve the cryptarithmetic problem in Figure 6.2 by hand (TWO + TWO = FOUR), using the strategy of backtracking with forward checking and the MRV and least-constraining-value heuristics.
  • 6.9 Explain why it is a good heuristic to choose the variable that is most constrained but the value that is least constraining in a CSP search.

    Chapter 7

  • 7.2 (Adapted from Barwise and Etchemendy (1993).) Given the following, can you prove that the unicorn is mythical? How about magical? Horned? If the unicorn is mythical, then it is immortal, but if it is not mythical, then it is a mortal mammal. If the unicorn is either immortal or a mammal, then it is horned. The unicorn is magical if it is horned. (Hint: you may want to use logic.py to solve, although there appears to be a bug in PropKB.)

    Here is the answer: 

    P1. Mythical ⇒ Immortal
P2. ¬Mythical ⇒ ¬Immortal ∧ Mammal
P3. Immortal ∨ Mammal ⇒ Horned
P4. Horned ⇒ Magical

1. ¬Immortal ⇒ ¬Mythical P1 contrapositive
2. ¬Immortal ⇒ ¬Immortal ∧ Mammal 1, P2, hypothetical syllogism
3. Immortal ∨ (¬Immortal ∧ Mammal) 2, implication defn
4. (Immortal ∨ ¬Immortal) ∧ (Immortal ∨ Mammal) 3, distributive
5. Immortal ∨ Mammal 4, tautology, identity
6. Horned 5, P3, modus ponens
7. Magical 6, P4, modus ponens
    So the unicorn is horned and magical. However, there is no way to show the unicorn is mythical.

  • 7.4 Which of the following are correct? 
    a. False |= True.
b. True |= False.
c. (A ∧ B) |=(A ⇔ B).
d. A ⇔ B |= A ∨ B.
e. A ⇔ B |= ¬A ∨ B.
f. (A ∧ B) ⇒ C |=(A ⇒ C) ∨ (B ⇒ C).
g. (C ∨ (¬A ∧ ¬B)) ≡ ((A ⇒ C) ∧ (B ⇒ C)).
h. (A ∨ B) ∧ (¬C ∨ ¬D ∨ E) |=(A ∨ B).
i. (A ∨ B) ∧ (¬C ∨ ¬D ∨ E) |=(A ∨ B) ∧ (¬D ∨ E).
j. (A ∨ B) ∧¬(A ⇒ B) is satisfiable.
k. (A ⇔ B) ∧ (¬A ∨ B) is satisfiable.
l. (A ⇔ B) ⇔ C has the same number of models as (A ⇔ B) for any fixed set of
proposition symbols that includes A, B, C.
  • 7.7 Consider a vocabulary with only four propositions, A, B, C,and D. How many models are there for the following sentences? 
    a. B ∨ C.
b. ¬A ∨ ¬B ∨ ¬C ∨ ¬D.
c. (A ⇒ B) ∧ A ∧ ¬B ∧ C ∧ D.
  • 7.18 Consider the following sentence: 
    [(Food ⇒ Party) ∨ (Drinks ⇒ Party)] ⇒ [(Food ∧ Drinks) ⇒ Party] .

    Chapter 8

  • 8.3 Is the sentence ∃ x, y x=y valid? Explain.
  • 8.4 Write down a logical sentence such that every world in which it is true contains exactly one object.
  • 8.6 Which of the following are valid (necessarily true) sentences? 
    a. (∃x x=x) ⇒ (∀y ∃z y=z).
b. ∀x P(x) ∨¬P(x).
c. ∀x Smart(x) ∨ (x=x).

  • 8.24 Represent the following sentences in first-order logic, using a consistent vocabulary (which you must define): 
    a. Some students took French in spring 2001.
b. Every student who takes French passes it.
c. Only one student took Greek in spring 2001.
d. The best score in Greek is always higher than the best score in French.
e. Every person who buys a policy is smart.
f. No person buys an expensive policy.
g. There is an agent who sells policies only to people who are not insured.
h. There is a barber who shaves all men in town who do not shave themselves.
i. A person born in the UK, each of whose parents is a UK citizen or a
UK resident, is a UK citizen by birth.
j. A person born outside the UK, one of whose parents is a UK citizen
by birth, is a UK citizen by descent.
k. Politicians can fool some of the people all of the time, and they
can fool all of the people some of the time, but they can’t fool all
of the people all of the time.
l. All Greeks speak the same language. (Use Speaks(x, l) to mean that
person x speaks language l.)

    Chapter 9

  • 9.4 For each pair of atomic sentences, give the most general unifier if it exists: 
    a. P(A,B, B), P(x, y, z).
b. Q(y,G(A,B)), Q(G(x, x),y).
c. Older(Father(y),y), Older(Father(x), John).
d. Knows(Father(y),y), Knows(x, x).
  • 9.6 Write down logical representations for the following sentences, suitable for use with Generalized Modus Ponens: 
    a. Horses, cows, and pigs are mammals.
b. An offspring of a horse is a horse.
c. Bluebeard is a horse.
d. Bluebeard is Charlie’s parent.
e. Offspring and parent are inverse relations.
f. Every mammal has a parent.