84
Formal Logic
19. Suppose a Prolog database exists that gives information about the ingredients in the menu items of a restaurant. Predicates of dry, liquid, perishable, and ingredientof are included.
a. Write a query to find all the dry ingredients of other ingredients.
b. Write a query to find all perishable ingredients that contain liquid subingredients.
c. Formulate a recursive rule to define foundin.
20. Suppose a Prolog database exists that gives information about flights for AA (Always Airborne) airline.
Predicates of city and flight are included. Here flight(X, Y ) means that AA has a direct (nonstop) flight
from city X to city Y.
a. Write a query to find all cities you can get to on a direct flight from Indianapolis.
b. Write a query to find all cities that have direct flights to San Francisco.
c. Formulate a recursive rule to define route where route(X, Y ) means that you can get from city X to city
Y using AA but it might not be a direct flight.
Exercises 21–22 refer to a “Toy Prolog interpreter” that can be found online at http://www.csse.monash.edu.
au/~lloyd/tildeLogic/Prolog.toy. The syntax used in this section matches that of this online version except that
in the online version each statement and query must end with a period. Here is a shortened version of Example
39 as entered into the code window, followed by the response to the query:
eat(bear, fish).
eat(fish, littlefish).
eat(littlefish, algae).
eat(raccoon, fish).
eat(bear, raccoon).
eat(bear, fox).
animal(bear).
animal(fish).
animal(littlefish).
animal(raccoon).
animal(fox).
prey(X) <= eat(Y, X) and animal(X).
?prey(X).
--- running --prey(fish) yes
prey(littlefish) yes
prey(fish) yes
prey(raccoon) yes
prey(fox) yes
In addition, you can look at and run the online sample program to be sure you understand the syntax rules.
21. Using the online Toy Prolog program, enter the Prolog database of Exercise 13. Run the queries from
Exercises 13 and 14 and compare the results with your previous answers.
22. Using the online Toy Prolog program, create a database for Exercise 20. Run the queries from Exercise
20. Also run a query using the route predicate.
S e c t I o n 1 . 6 pRoof of CoRReCtneSS
As our society becomes ever more dependent on computers, it is more and
more important that the programs computers run are reliable and error-free.
Program verification attempts to ensure that a computer program is correct.
Formal Logic
19. Suppose a Prolog database exists that gives information about the ingredients in the menu items of a restaurant. Predicates of dry, liquid, perishable, and ingredientof are included.
a. Write a query to find all the dry ingredients of other ingredients.
b. Write a query to find all perishable ingredients that contain liquid subingredients.
c. Formulate a recursive rule to define foundin.
20. Suppose a Prolog database exists that gives information about flights for AA (Always Airborne) airline.
Predicates of city and flight are included. Here flight(X, Y ) means that AA has a direct (nonstop) flight
from city X to city Y.
a. Write a query to find all cities you can get to on a direct flight from Indianapolis.
b. Write a query to find all cities that have direct flights to San Francisco.
c. Formulate a recursive rule to define route where route(X, Y ) means that you can get from city X to city
Y using AA but it might not be a direct flight.
Exercises 21–22 refer to a “Toy Prolog interpreter” that can be found online at http://www.csse.monash.edu.
au/~lloyd/tildeLogic/Prolog.toy. The syntax used in this section matches that of this online version except that
in the online version each statement and query must end with a period. Here is a shortened version of Example
39 as entered into the code window, followed by the response to the query:
eat(bear, fish).
eat(fish, littlefish).
eat(littlefish, algae).
eat(raccoon, fish).
eat(bear, raccoon).
eat(bear, fox).
animal(bear).
animal(fish).
animal(littlefish).
animal(raccoon).
animal(fox).
prey(X) <= eat(Y, X) and animal(X).
?prey(X).
--- running --prey(fish) yes
prey(littlefish) yes
prey(fish) yes
prey(raccoon) yes
prey(fox) yes
In addition, you can look at and run the online sample program to be sure you understand the syntax rules.
21. Using the online Toy Prolog program, enter the Prolog database of Exercise 13. Run the queries from
Exercises 13 and 14 and compare the results with your previous answers.
22. Using the online Toy Prolog program, create a database for Exercise 20. Run the queries from Exercise
20. Also run a query using the route predicate.
S e c t I o n 1 . 6 pRoof of CoRReCtneSS
As our society becomes ever more dependent on computers, it is more and
more important that the programs computers run are reliable and error-free.
Program verification attempts to ensure that a computer program is correct.