Week 1: Exercises

1. Dancing Pairs

(Clocksin, Clause and Effect, worksheet 1)

Consider this Prolog program:

male(honza).
male(karel).

female(eliska).
female(katka).

dance(P, Q) :- male(P), female(Q).

What answers will these queries produce, and in what order?

1. dance(karel, X).

2. dance(jakub, radka).

3. dance(katka, X).

4. dance(X, eliska).

5. dance(X, X).

6. dance(honza, eliska).

7. dance(X, jana).

8. dance(X, Y).

2. Drinking Pairs

(Clocksin, worksheet 2)

Consider this Prolog program:

drinks(tomas, whiskey).
drinks(sonya, beer).
drinks(lucie, wine).
drinks(radek, beer).
drinks(jarda, beer).

pair(P, Q, D) :- drinks(P, D), drinks(Q, D).

What answers will these queries produce, and in what order?

1. pair(P, tomas, whiskey).

2. pair(sonya, jarda, beer).

3. pair(tomas, sonya, beer).

4. pair(radek, radek, beer).

5. pair(X, Y, beer).

6. pair(X, Y, Z).

3. Directed Graph

(Clocksin, worksheet 4)

Consider an acyclic directed graph defined as follows:

edge(g, h).
edge(g, d).
edge(e, d).
edge(h, f).
edge(e, f).
edge(a, e).
edge(a, b).
edge(b, f).
edge(b, c).
edge(f, c).

1. Write a predicate path(V, W) that is true if there is some path from V to W in the directed graph.

2. Given your predicate, what answers will each of these queries produce?

   • path(f, f).

   • path(a, c).

   • path(g, e).

   • path(g, X).

   • path(X, h).

   • path(X, X).

   • path(X, Y).

4. Genealogy

Suppose that we define a family tree using predicates male, female and parent:

male(jan). male(karel). male(vaclav).

female(anna). female(eliska).

parent(vaclav, anna). parent(vaclav, karel).
parent(karel, jan). parent(karel, eliska).
...

Write Prolog predicates expressing the following relationships:

1. mother, grandparent

2. sibling, brother

   Two people are siblings if they have at least one parent in common.

3. full_sibling

   Full siblings share both parents.

4. first_cousin, second_cousin

   First cousins have parents who are siblings. Second cousins have parents who are first cousins.

5. cousin

   Two people are cousins if they are N^th cousins for any N ≥ 1.

5. Map of Europe

Consider a map that shows 7 countries: the Czech Republic, Slovakia, Germany, Poland, Austria, Hungary, and Ukraine. Is it possible to color this map with 3 colors so that no bordering countries have the same color? Write a Prolog program that can answer this question.

6. Occupations and Instruments

(Levesque, Thinking as Computation, 5.5)

Write a Prolog program that can solve the following puzzle.

Katka, Maria and Roman have distinct occupations and play distinct musical instrments. Their occupations are doctor, lawyer, and teacher, and the instruments they play are piano, flute, and violin. Also:

1. Maria lives next to the doctor.

2. The lawyer plays the piano.

3. Maria is not the teacher.

4. Katka is a patient of the violinist.

Who plays the flute?

7. At a Restaurant

(Levesque, ex. 5.4)

Write a Prolog program that can solve the following puzzle.

Jana, Markéta, Pavel and Václav were seated at a restaurant in Prague. The men sat across the table from each other, as did the women. Each of them ordered a different food along with a different beverage. Also:

1. Markéta sat beside the person who ordered fried cheese.

2. The chicken came with wine.

3. The person with pasta sat across from the person with beer.

4. Václav never drinks coffee.

5. Jana only drinks water.

6. Pavel does not like fried cheese.

Who ordered the pancakes?