Solution for Assignment 3

Due Monday, March. 21, midnight in the CS47225 assignment bin.

 

  1. (5 marks) Exercise 7.2

 

To save space, we’ll show the list of models as a table rather than a collection of diagrams. There are eight possible combinations of pits in the three squares, and four possibilities for the wumpus location (including nowhere). We can see that KB |= α2 because every line where KB is true also has α2 true. Similarly for α3.

 

 

 

 

 

 

  1. (5 marks) Exercise 7.9

The knowledge base includes the following sentences according to the story:

Mythical ⇒ Immortal

￢Mythical ⇒ ￢Immortal ∧ Mammal

Immortal ∨ Mammal ⇒ Horned

Horned ⇒ Magical

 

 

From the first two sentences, we see 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.

 

 

  1. (3 marks) Exercise 8.2

 

The knowledge base does not entail ∀x P(x). To show this, we must give a model where P(a) and P(b) but ∀x P(x) is false. Consider any model with three domain elements, where a and b refer to the first two elements and the relation referred to by P holds only for those two elements.

 

  1. (3 marks) Exercise 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.

 

  1. Exercise 8.6

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. (1 mark) Some students took French in spring 2001.

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

b. (1 mark) Every student who takes French passes it.

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

c. (1 mark)  Only one student took Greek in spring 2001.

∃x Student(x)∧Takes(x,G, Spring2001)∧∀y y _= x⇒￢Takes(y,G, Spring2001).

d. (1 mark)  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. (1 mark)  Every person who buys a policy is smart.

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

f. (1 mark)  No person buys an expensive policy.

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

g. (1 mark)  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. (1 mark)  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. (2 marks) 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. (2 marks) 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. (2 marks)  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))