CS 470 - Problem Set 4 - Solutions

6.1 There are 18 solutions for coloring Australia with three colors. Start with SA, which can have any of three colors. Then moving clockwise, WA can have either of the other two colors, and everything else is strictly determined; that makes 6 possibilities for the mainland, times 3 for Tasmania yields 18. With four colors, there are 768 solutions (4*3*2*2*2*2*4). With two colors, there are no solutions.

6.5 The exact steps depend on certain choices you are free to make; here are the ones I made:

a. Choose the X3 variable. Its domain is {0, 1}.
b. Choose the value 1 for X3. (We can’t choose 0; it wouldn’t survive
forward checking, because it would force F to be 0, and the leading
digit of the sum must be non-zero.)
c. Choose F, because it has only one remaining value.
d. Choose the value 1 for F.
e. Now X2 and X1 are tied for minimum remaining values at 2; let’s choose X2.
f. Either value survives forward checking, let’s choose 0 for X2.
g. Now X1 has the minimum remaining values.
h. Again, arbitrarily choose 0 for the value of X1.
i. The variable O must be an even number (because it is the sum of T +
T less than 5 (because O + O = R + 10 × 0). That makes it most
constrained.
j. Arbitrarily choose 4 as the value of O.
k. R now has only 1 remaining value.
l. Choose the value 8 for R.
m. T now has only 1 remaining value.
n. Choose the value 7 for T.
o. U must be an even number less than 9; choose U.
p. The only value for U that survives forward checking is 6.
q. The only variable left is W.
r. The only value left for W is 3.
s. This is a solution.

6.9 The most constrained variable makes sense because it chooses a variable that is (all other things being equal) likely to cause a failure, and it is more efficient to fail as early as possible (thereby pruning large parts of the search space). The least constraining value heuristic makes sense because it allows the most chances for future assignments to avoid conflict.

Chapter 7

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

7.2 As human reasoners, we can see from the first two statements, that if it is mythical, then it is immortal; otherwise it is a mammal. So it must be either immortal or a mammal, and thus horned. That means it is also magical. However, we can’t deduce anything about whether it is mythical. To provide a formal answer, we can enumerate the possible worlds (2⁵ = 32 of them with 5 proposition symbols), mark those in which all the assertions are true, and see which conclusions hold in all of those. Or, we can let the machine do the work—in this case, the Lisp code for propositional reasoning:

> (setf kb (make-prop-kb))
#S(PROP-KB SENTENCE (AND))
> (tell kb "Mythical => Immortal")
T
> (tell kb " ̃Mythical =>  ̃Immortal ˆ Mammal")
T
> (tell kb "Immortal | Mammal => Horned")
T
> (tell kb "Horned => Magical")
T
> (ask kb "Mythical")
NIL
> (ask kb " ̃Mythical")
NIL
> (ask kb "Magical")
T
> (ask kb "Horned")
T

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.4 In all cases, the question can be resolved easily by referring to the definition of entailment.

a. False |= True is true because False has no models and hence entails
every sentence AND because True is true in all models and hence is
entailed by every sentence.

b. True |= False is false.

c. (A ∧ B) |= (A ⇔ B) is true because the left-hand side has exactly
one model that is one of the two models of the right-hand side.

d. A ⇔ B |= A ∨ B is false because one of the models of A ⇔ B has both
A and B false, which does not satisfy A ∨ B.

e. A ⇔ B |= ¬A ∨ B is true because the RHS is A ⇒ B, one of the
conjuncts in the definition of A ⇔ B.

f. (A ∧ B) ⇒ C |= (A ⇒ C) ∨ (B ⇒ C) is true because the RHS is false
only when both disjuncts are false, i.e., when A and B are true and C
is false, in which case the LHS is also false. This may seem
counterintuitive, and would not hold if ⇒ is interpreted as “causes.”

g. (C ∨(¬A∧ ¬B)) ≡ ((A ⇒ C)∧(B ⇒ C)) is true; proof by truth table
enumeration, or by application of distributivity (Fig 7.11).

h. (A ∨ B) ∧ (¬C ∨ ¬D ∨ E) |= (A ∨ B) is true; removing a conjunct
only allows more models.

i. (A ∨ B)∧(¬C ∨ ¬D ∨ E) |= (A ∨ B)∧(¬D ∨ E) is false; removing a
disjunct allows fewer models.

j. (A ∨ B) ∧ ¬(A ⇒ B) is satisfiable; model has A and ¬B.

k. (A ⇔ B) ∧ (¬A ∨ B) is satisfiable; RHS is entailed by LHS so models
are those of A ⇔ B.

l. (A ⇔ B) ⇔ C does have the same number of models as (A ⇔ B); half
the models of (A ⇔ B) satisfy (A ⇔ B) ⇔ C, as do half the non-models,
and there are the same numbers of models and non-models.

a. B ∨ C.
b. ¬A ∨ ¬B ∨ ¬C ∨ ¬D.
c. (A ⇒ B) ∧ A ∧ ¬B ∧ C ∧ D.

7.7 These can be computed by counting the rows in a truth table that come out true, but each has some simple property that allows a short-cut:

a. Sentence is false only if B and C are false, which occurs in 4
cases for A and D, leaving 12.

b. Sentence is false only if A, B, C, and D are false, which occurs in
1 case, leaving 15.

c. The last four conjuncts specify a model in which the first conjunct
is false, so 0.

[(Food ⇒ Party) ∨ (Drinks ⇒ Party)] ⇒ [(Food ∧ Drinks) ⇒ Party] .

• a. Determine, using enumeration, whether this sentence is valid, satisfiable (but not valid), or unsatisfiable.
• b. Convert the left-hand and right-hand sides of the main implication into CNF, showing each step, and explain how the results confirm your answer to (a).
• c. Prove your answer to (a) using resolution.

7.18

a. A simple truth table has eight rows, and shows that the sentence is true for all models and hence valid.

b. For the left-hand side we have:

(Food ⇒ Party) ∨ (Drinks ⇒ Party)
(¬Food ∨ Party) ∨ (¬Drinks ∨ Party)
(¬Food ∨ Party ∨ ¬Drinks ∨ Party)
(¬Food ∨ ¬Drinks ∨ Party)

(Food ∧ Drinks) ⇒ Party
¬(Food ∧ Drinks) ∨ Party
(¬Food ∨ ¬Drinks) ∨ Party
(¬Food ∨ ¬Drinks ∨ Party)

c. To prove that a sentence is valid, prove that its negation is unsatisfiable. I.e., negate it, convert to CNF, use resolution to prove a contradiction. We can use the above CNF result for the LHS.

¬[[(Food ⇒ Party) ∨ (Drinks ⇒ Party)] ⇒ [(Food ∧ Drinks) ⇒ Party]]
[(Food ⇒ Party) ∨ (Drinks ⇒ Party)] ∧ ¬[(Food ∧ Drinks) ⇒ Party]
(¬Food ∨ ¬Drinks ∨ Party) ∧ Food ∧ Drinks ∧ ¬Party

Chapter 8

8.3 The sentence ∃ x,y x = y is valid. A sentence is valid if it is true in every model. An existentially quantified sentence is true in a model if it holds under any extended interpretation in which its variables are assigned to domain elements. According to the standard semantics of FOL as given in the chapter, every model contains at least one domain element, hence, for any model, there is an extended interpretation in which x and y are assigned to the first domain element. In such an interpretation, x = y is true.

8.4 ∀ x,y x = y stipulates that there is exactly one object. If there are two objects, then there is an extended interpretation in which x and y are assigned to different objects, so the sentence would be false. Some students may also notice that any unsatisfiable sentence also meets the criterion, since there are no worlds in which the sentence is true.

a. (∃x x=x) ⇒ (∀y ∃z y=z).
b. ∀x P(x) ∨¬P(x).
c. ∀x Smart(x) ∨ (x=x).

8.6 Validity in first-order logic requires truth in all possible models:

a. (∃x x = x) ⇒ (∀ y ∃z y = z).

Valid. The LHS is valid by itself—in standard FOL, every model has at
least one object; hence, the whole sentence is valid iff the RHS is
valid. (Otherwise, we can find a model where the LHS is true and the
RHS is false.) The RHS is valid because for every value of y in any
given model, there is a z—namely, the value of y itself—that is
identical to y.

b. ∀ x P(x) ∨ ¬P(x).

Valid. For any relation denoted by P, every object x is either in the
relation or not in it.

c. ∀ x Smart(x) ∨ (x = x).

Valid. In every model, every object satisfies x = x, so the
disjunction is satisfied regardless of whether x is smart.

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

8.24 In this exercise, it is best not to worry about details of tense and larger concerns with consistent ontologies and so on. The main point is to make sure students understand connectives and quantifiers and the use of predicates, functions, constants, and equality. Let the basic vocabulary be as follows:

Takes(x,c,s): student x takes course c in semester s;
Passes(x,c,s): student x passes course c in semester s;
Score(x,c,s): the score obtained by student x in course c in semester s;
x > y: x is greater than y;

F and G: specific French and Greek courses (one could also interpret
these sentences as referring to any such course, in which case one
could use a predicate Subject(c,f) meaning that the subject of course
c is field f;

Buys(x,y,z): x buys y from z (using a binary predicate with
unspecified seller is OK but less felicitous);

Sells(x,y,z): x sells y to z;
Shaves(x,y): person x shaves person y
Born(x,c): person x is born in country c;
Parent(x,y): x is a parent of y;
Citizen(x,c,r): x is a citizen of country c for reason r;
Resident(x,c): x is a resident of country c;
Fools(x,y,t): person x fools person y at time t;

Student(x), Person(x), Man(x), Barber(x), Expensive(x), Agent(x),
Insured(x), Smart(x), Politician(x): predicates satisfied by members
of the corresponding categories.

a. Some students took French in spring 2001.

∃ x Student(x) ∧ Takes(x,F,Spring2001).

b. Every student who takes French passes it.

∀ x,s Student(x) ∧ Takes(x,F,s) ⇒ Passes(x,F,s).

c. Only one student took Greek in spring 2001.

∃ x Student(x)∧Takes(x,G,Spring2001)∧∀ y y ≠ x ⇒ ¬Takes(y,G,Spring2001).

d. The best score in Greek is always higher than the best score in French.

∀ s ∃ x ∀ y Score(x,G,s) > Score(y,F,s).

e. Every person who buys a policy is smart.

∀ x Person(x) ∧ (∃ y,z Policy(y) ∧ Buys(x,y,z)) ⇒ Smart(x).

f. No person buys an expensive policy.

∀ x,y,z Person(x) ∧ Policy(y) ∧ Expensive(y) ⇒ ¬Buys(x,y,z).

g. There is an agent who sells policies only to people who are not insured.

∃ x Agent(x) ∧ ∀ y,z Policy(y) ∧ Sells(x,y,z) ⇒ (Person(z) ∧ ¬Insured(z)).

h. There is a barber who shaves all men in town who do not shave
themselves.

∃ x Barber(x) ∧ ∀ y Man(y) ∧ ¬Shaves(y,y) ⇒ Shaves(x,y).

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.

∀ x Person(x)∧Born(x,UK)∧(∀ y Parent(y,x) ⇒ ((∃ r Citizen(y,UK,r))∨
Resident(y,UK))) ⇒ Citizen(x,UK,Birth).

j. A person born outside the UK, one of whose parents is a UK citizen
by birth, is a UK citizen by descent.

∀ x Person(x) ∧ ¬Born(x,UK) ∧ (∃ y Parent(y,x) ∧ Citizen(y,UK,Birth))
⇒ Citizen(x,UK,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.

∀ x Politician(x) ⇒
(∃ y ∀ t Person(y) ∧ Fools(x,y,t)) ∧
(∃ t ∀ y Person(y) ⇒ Fools(x,y,t)) ∧
¬(∀ t ∀ y Person(y) ⇒ Fools(x,y,t))

l. All Greeks speak the same language.

∀ x,y,l Person(x) ∧ [∃ r Citizen(x, Greece,r)] ∧ Person(y) ∧ [∃ r
Citizen(y, Greece,r)] ∧ Speaks(x,l) ⇒ Speaks(y,l)

Chapter 9

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.4 This is an easy exercise to check that the student understands unification.

a. {x/A,y/B,z/B} (or some permutation of this).

b. No unifier (x cannot bind to both A and B).

c. {y/John,x/John}.

d. No unifier (because the occurs-check prevents unification of y with
Father(y)).

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.

9.6 We use a very simple ontology to make the examples easier:

a. Horse(x) ⇒ Mammal(x)
Cow(x) ⇒ Mammal(x)
Pig(x) ⇒ Mammal(x).
b. Offspring(x,y) ∧ Horse(y) ⇒ Horse(x).
c. Horse(Bluebeard).
d. Parent(Bluebeard,Charlie).
e. Offspring(x,y) ⇒ Parent(y,x)
Parent(x,y) ⇒ Offspring(y,x).

(Note we couldn’t do Offspring(x,y) ⇔ Parent(y,x) because that is not
in the form expected by Generalized Modus Ponens.)

f. Mammal(x) ⇒ Parent(G(x),x) (here G is a Skolem function).