Harvey Mudd College
Computer Science 60
Assignment 9, Due Thursday, March 30, by midnight

Prolog

Problem 1: Circuit design and Karnaugh maps

This half of the assignment is pencil-and-paper, rather than a programming problem. It provides an example of a circuit-design application in which Karnaugh maps can be used.

In order to make it easy to print out these problems, they are included on a separate webpage:

Problem 1 (Karnaugh Maps and circuits)

You should submit your solutions to Problem 1 under the door of Olin 1245 (formerly 245) by 6:00 pm on Saturday evening, April 1 (that is, given the built-in extension).

Problem 2: Food Knowledge Base for Local Restaurants

This problem entails coding queries into predicate logic using Prolog. Your file should be a program which will load and run in Prolog named restaurants.pl.

In prolog the names of constants and predicates are in lower-case. Variables are alphabetic strings beginning with an uppercase letter (or the underscore). The following predicates about local restaurants have been pre-coded in Prolog. Your program should access this code by including the following line in your restaurants.pl source:

:- ensure_loaded('/cs/cs60/as/a9/foodkb.pl').

The problems

Code the following queries in Prolog. You will likely find it helpful to define auxiliary predicates to assist you.

Important: Name the final query (the one that returns the answers to each question in a list) ans1, ans2, ..., ans12. If you don't do this, the testing program will not give you credit for your solutions. See the example that appears after these queries for the expected format -- the predicates ans1, ans2, etc. are a good place to use setof, so that the whole set is returned.

1. Which restaurants are in claremont?
2. Which restaurants have italian cuisine?
3. Which restaurants serve bouillabaisse?
4. In what restaurants can you get served rice in claremont?
5. In what restaurants can you get served a vegetarian dish in montclair?
6. Which restaurants serve both vegetarian and meat dishes?
7. Which cities have both a chinese restaurant and a mexican restaurant?
8. Which restaurants in claremont or upland serve meat dishes?
9. Which restaurants in san_bernardino_county serve vegetarian dishes?
10. Which restaurants in claremont don't serve snapper?
11. Which cities have more than one restaurant of some sort of cuisine?
12. Which cities have more than one restaurant serving noodles?

Each answer should be encoded as a predicate, ans1, ans2, ..., which gives the whole set of entities as a list. The following is an example of how this would be done for the first query:

/* 1. Which restaurants are in claremont? */

/* inClaremont(Restaurant) is true iff Restaurant is in claremont */

inClaremont(R) :- restaurant(R, _, claremont).


/* ans1(Set) gives the set of restaurants in claremont */

ans1(Set) :- setof(R, inClaremont(R), Set).

Prolog Tips

• To start prolog, just type prolog at the unix prompt.
  
  
• To quit prolog, type halt. at the prolog prompt. The period is important!
  
  
• To load a file into prolog, there are three possibilities:
  • Type ['filename.pl']. at the prolog prompt.
    
  • Type consult('filename.pl'). at the prolog prompt.
    
  • Type reconsult('filename.pl'). at the prolog prompt. (After the first time.)
    
  
  
  
• Simple equality testing in prolog uses ==
  
  
• Testing for nonequality in prolog uses \==
  
  
• "NOT" of some predicate p(...) is expressed as \+p(...).
  
  
• Comments can be added to a file with /* ... */
  
  

Testing your code

ans1(S).
ans2(S).
...

Reading

Predicate Logic and prolog is covered in Chapter 10 of the text.

Submission

Hand in your Karnaugh Maps under the door of Olin 1245 (by 6:00 pm Sat., April 1). Submit the prolog file restaurants.pl in the usual way, i.e., by running

% cs60submit restaurants.pl

You will be asked to input the assignment number (9).

Restaurants Knowledge Base

The following is a summary of the restaurants knowledge base:

There are four predicates that hold all of the information in the database:

1. serves(Kind,Dish) means that any restaurant of type "Kind" serves the dish "Dish" . For example, serves(american,steak). Dishes are what you'd expect: burgers, tandoori, etc. A "Kind" refers to a restaurant's theme: american, japanese, seafood_place, burger_place, etc.
   
   
2. dish(Type,Dish) means that a particular food ("Dish") is of type "Type" . For example, dish(starch, rice). The following food tpyes are supported: vegetarian, meat, seafood, and starch.
   
   
3. restaurant(R, Kind, City) means that "R" is a restaurant of kind "Kind" in city "City" . For example, restaurant(kishi, japanese, claremont). These cities are supported: claremont, laverne, ontario, pomona, upland, and montclair.
   
   
4. county(City, County) means that "City" is a city in the county "County" . For example, county(claremont, los_angeles_county). Only los_angeles_county and san_bernardino_county are supported.
   
   

The following summarizes the entries in the database:

serves predicate:

american restaurants serve 
	salad, steak, sandwiches, burgers, and fried chicken.
burger_place restaurants serve 
	burgers, fries, and salad.
cajun restaurants serve
	rice, beans, gumbo, and sausage.
chinese restaurants serve 
	eggrolls, rice, shrimp, soup, and noodles. 
indian restaurants serve 
	papadam, bagan_bharta, rice, tandoori, and naan.
italian restaurants serve 
	salad, pasta, cioppino, snapper, and bread.
japanese restaurants serve 
	sashimi, rice, tempura, and noodles. 
mediterranean restaurants serve
	gyros, humus, pita, and falafel. 
mexican restaurants serve 
	tacos, beans, rice, enchiladas, and snapper. 
pizza_place restaurants serve 
	pizza, salad, garlic_bread
seafood_place restaurants serve
	salad, shrimp, snapper, bouillabaisse, and clams. 
thai restaurants serve 
	eggrolls, rice, noodles, and pad_thai. 

Note: There are two ways in which you can define a predicate such as serves: One on hand, you can enumerate each relationship:

etc.

A more concise way is to use lists in an auxiliary predicate, in conjunction with the built-in member predicate that enumerates the relationships.

servesAll(american, [salad, steak, sandwiches, burgers, fried_chicken]).

serves(Kind, Dish) :- servesAll(Kind, Dishes), member(Dish, Dishes).

This is the technique used in foodkb.pl.

(end of note)

dish predicate:

vegetarian dishes:
	beans, bagan_bharta, enchiladas, falafel, humus, 
	pizza, salad, soup, tempura, and all starch dishes 
meat dishes:
	burgers, enchiladas, gyros, pad_thai, pizza, steak, sandwiches, 
	fried_chicken, tacos, tandoori
seafood dishes:
	eggrolls, snapper, cioppino, sashimi, shrimp, bouillabaisse, tempura 
starch dishes:
	naan, papadam, bread, rice, noodles, pita, garlic_bread, pasta, fries

cuisine and location predicates:

arrufos is an italian restaurant in claremont.
bamboo_yuan is a chinese restaurant in claremont.
bombay is an indian restaurant in ontario.
chilis is an american restaurant in laverne. 
don_salsa is a mexican restaurant in claremont. 
el_gato is a mexican restaurant in upland. 
full_house is a chinese restaurant in upland. 
islands is a burger place in montclair. 
kishi is a japanese restaurant in upland. 
nirvana is an indian restaurant in montclair. 
nogi is a japanese restaurant in claremont. 
orchid_garden is a thai restaurant in laverne. 
pizza_n_such is a pizza_place restaurant in claremont. 
rosas is an italian restaurant in ontario. 
sacas is a mediterranean restaurant in claremont. 
sanamluang_cafe is a thai restaurant in pomona. 
shrimp_house is a seafood_place restaurant in claremont. 
tutti_mangia is an italian restaurant in claremont. 
warehouse is a pizza_place restaurant in laverne. 
yiannis is a mediterranean restaurant in claremont. 

county predicate:

claremont is in los_angeles_county. 
laverne is in los_angeles_county. 
montclair is in san_bernardino_county. 
ontario is in san_bernardino_county. 
pomona is in los_angeles_county. 
upland is in san_bernardino_county.