Report Final

USING PROLOG AS A KNOWLEDGE – BASED SYSTEM A PROJECT REPORT FOR CSE 563 KNOWLEDGE REPRESENTATION Vaibhav Bhembre (vaibhavb) Ashish Dhal (ashishdh) Abhay Kashyap (abhaylok) November 17, 2009

1 GENERAL DESCRIPTION This project is adapted from Russell and Norvig’s AI texts [1,2]. This project presents the development and formalization of a knowledge base, based on a preliminary statement. Additional details are added to the base, in order to successfully answer the questions given. The knowledge base is processed and queried using Prolog. Prolog is a declarative logic programming language. Prolog works by attempting to find a resolution refutation of a set of data, and produces results based on the outcome. [3] The knowledge base is loaded in the form of a set of assertions, which are queried sequentially by Prolog. Each query of the statements logically follows the previous one, and on successfully satisfying all the necessary conditions, Prolog returns a ‘yes’ or ‘no’ answer. [3] This project begins with a single problem statement, to which additional bits of information are added to successfully answer the queries supplied. The following sentence S is used, to which more information is added as described in the following sections:

Yesterday, John went to the Tops Maple Road supermarket and bought five pounds of potatoes and a pound and a half of ground beef.

2 DOMAIN AND KNOWLEDGE BASE 2.1 SYNTAX AND SEMANTICS OF ATOMIC SYMBOLS

•

john : The person ‘John’

•

mary : The person ‘Mary’

•

potatoes : The product ‘potatoes’

•

topsM: The Tops Maple Road Supermarket

•

beef: The product ‘Ground Beef’

•

meat: The product category ‘meat’

•

livesAlone(X): X lives alone

•

hasToShopAlone(X): X has to shop alone

•

isa(X, Y): X is Y

•

shop(W, X, Y, Z): W shops for X at Y during Z

•

unitWeight(X, Y): X weighs Y pounds

•

pounds(X, Y, Z): X has Y pounds of Z

•

number(X, Y, Z): X has Y amount of Z

•

largerorequal(X, Y): X is larger of equal to Y

•

hasatleast(X, Y, Z): X has atleast Y amounts of Z

•

typeOf(X, Y): X is a type of Y

•

bought(X, Y): X has bought Y

•

buys(X, Y): X buys Y

•

isAtStore(X, Y, Z): X is at Y store on Z day

•

isAtStall(X, Y, Z): X is at Y stall on Z day

•

sees(X,Y): X sees Y

•

originates(X, Y): X originates from Y

•

made(X, Y): X is made in Y

•

can(X, Y): X can be Y

•

after(X, Y): X comes after Y

•

has(X, Y, Z): X has Y on Z

•

whatWill(W, X, Y, Z): W will do Z on X on Y day

•

hasBranch(X, Y): X has a branch called Y

•

available(X, Y): X is available at Y

•

sells(X, Y): X sells Y

•

pays(W, X, Y, Z): W pays X to Y on Z

•

brings(W, X, Y, Z): W brings X to Y on Z

•

spentMoney(X, Y, Z): X spends money on Y at Z type of place

•

moneyLeft(W, X, Y, Z): W has X left at Y after Z time

•

edible(A): A is edible

2.2 ENGLISH DESCRIPTION OF THE KNOWLEDGE BASE

% John shopped for potatoes at tops maple road supermarket. shop(john,potatoes,topsM,yesterday).

% John shopped for beef at tops maple road supermarket. shop(john,beef,topsM,yesterday).

% John lives alone livesAlone(john).

% Anyone who lives alone has to shop alone hasToShopAlone(X):-livesAlone(X).

% If anyone has to shop alone and if they shop then they are adults. isa(X,adult):-shop(X,_,_,_),hasToShopAlone(X).

% If Someone is not an adult then he is a child. isa(X,child):- !,\+ isa(X,adult).

% If someone is an adult he cannot be a child. isa(X,child):- isa(X,adult), !, fail.

% Potatoes have a unit weight of 0.5 pounds unitWeight(potatoes,0.5).

% If John shopped for potatoes, he bought 5 pounds of potatoes. pounds(john,5,potatoes):-shop(john,potatoes,topsM,yesterday).

% The number of potatoes that john has is obtained by the no. of pounds/unit % weight. number(john,X,potatoes):-unitWeight(potatoes,Y),pounds(john,Z,potatoes),X is Z/Y.

% If N>=M then N is larger or equal to M. largerorequal(N,M):-N>=M.

% If John has some number of potatoes and if it is larger or equal to some % number then he has atleast that many number of potatoes.

hasatleast(john,Y,potatoes):- number(john,X,potatoes),largerorequal(X,Y).

% Beef is a type of meat. typeOf(beef,meat).

% Chicken is a type of meat. typeOf(chicken,meat).

% If someone shopped for something somewhere sometime, then they bought % that thing. bought(X,Y):-shop(X,Y,_,_).

% If John bought something and if that thing is meat then John bought meat buys(X,Y):-bought(X,Z), typeOf(Z,Y).

% Mary was buying potatoes at tops at the same time as john. shop(mary,potatoes,topsM,T):-shop(john,potatoes,topsM,T).

% Peter buys beef at tops yesterday. shop(peter,beef,topsM,yesterday).

% If someone buys something at some store at sometime then that person is at % that store at that time. isAtStore(X,Y,Z):-shop(X,_,Y,Z).

% If someone buys something at some stall at sometime then that person is at % that stall at that time.

isAtStall(X,Y,Z):-shop(X,Y,_,Z).

% If someone is at some stall at some store, and if someone else is also at the % same stall and same store, then that person sees the other person sees(X,V):-isAtStore(X,Y,Z),isAtStall(X,U,Z),isAtStore(V,Y,Z),isAtStall(V,U,Z).

% Or else they will not see each other. sees(X,V):-!, \+isAtStore(X,Y,Z);\+isAtStall(X,U,Z);\+isAtStore(V,Y,Z);\ +isAtStall(V,U,Z), fail.

% If X sees Y then Y also sees X. sees(Y,X):-sees(X,Y).

% Potatoes are type of vegetables. typeOf (potatoes,vegetable).

% Shoes are type of footwears. typeOf(shoes,footwear).

% If something is a vegetable then it originates from nature. originates(X,nature):-typeOf(X,vegetable).

% If something is a footwear then it does not originate in nature. originates(X,nature):-typeOf(X,footwear), !, fail.

% If something is of form something which orginates from man, then it is made % in the supermarket. made(X,supermarket):- !,\+originates(X,nature).

% Potatoes are type of vegetables % Beef is a type of meat. % If something is a Vegetable or meat, it can be eaten. can(X,eaten):-typeOf(X,vegetable);typeOf(X,meat).

% Precedence of days after(yesterday,daybeforeyesterday). after(today, daybeforeyesterday). after(tomorrow, daybeforeyesterday). after(today,yesterday). after(tomorrow,yesterday). after(tomorrow,today).

% Someone has something at sometime if he has shopped for it. has(X,Y,T):-shop(X,Y,_,T).

% Someone eats something at sometime if someone has something at that time % and if that thing can be eaten. whatWill(X,Y,T,eatThem):- has(X,Y,K), can(Y,eaten),after(T,K).

% Deodorant is a type of skin care product. typeOf(deodorant, skincare).

% Soap is a type of skin care product. typeOf(soap,skincare).

% Tops Maple road Supermarket is a type of Supermarket. typeOf(topsM,supermarket).

% Tops has a branch called Tops Maple road supermarket hasbranch(tops,topsM).

% Skin care products, vegetables, meat are available in supermarkets. available(skincare,supermarket). available(meat,supermarket). available(vegetable,supermarket).

% Something sells something if it has a branch which is a supermarket which % has those class of products sells(X,Y):hasbranch(X,U),typeOf(U,supermarket),typeOf(Y,Z),available(Z,supermarket); hasbranch(X,U),typeOf(U,supermarket),available(Y,supermarket);

% If anyone shops at someplace for anything at some times then they pay % money for that thing at that time at that place. pay(X,money,Y,T):-shop(X,_,Y,T).

% If someone has to pay money at sometime at a store which is of some type % then they must bring that money to that place at that time. bring(X,money,Y,T):-pay(X,money,K,T),typeOf(K,Y).

% If anyone shops at someplace for anything at some times then they pay % money for that thing at that time at that place. % If someone who pays money at sometime at someplace of some type then

% then he spent money that time in that type of place. spentMoney(X,Z,T) :-pay(X,money,Y,T),typeOf(Y,Z).

% Define after and before yesterday after(after,yesterday). after(yesterday,before).

% If someone spend money at someplace at some time then he had less money % after that time at the same place. moneyLeft(W,less,Y,T):- spentMoney(W,Y,U),after(T,U).

3 DEMONSTRATION RUNS timberlake {~} > sicstus SICStus 4.0.5 (x86_64-linux-glibc2.3): Thu Feb 12 09:48:30 CET 2009 Licensed to SP4cse.buffalo.edu | ?- consult(user). % consulting user... |% 1) Is John an adult??

% John lives alone livesAlone(john).

% Anyone who lives alone has to shop alone hasToShopAlone(X):-livesAlone(X).

% If anyone has to shop alone and if they shop then they are adults. isa(X,adult):-shop(X,_,_,_),hasToShopAlone(X).

% If Someone is not an adult then he is a child. isa(X,child):- !,\+ isa(X,adult).

% If someone is an adult he cannot be a child. isa(X,child):- isa(X,adult), !, fail.

/* Question --------------------------------------------* Is John a child or an adult? [Adult] * John lives alone. * Anyone who lives alone shop alone. * So John shops alone. * John shops at tops for potatoes and beef. * If someone has to shop alone and shops then its an adult. * Hence John is an adult. ~~~~~~~~~~~~~~~~~~ | ?- isa(john,X). X = adult ? yes | ?- isa(john,child). no ~~~~~~~~~~~~~~~~~~ */

% 2) Does John now have at least two potatoes?

% Potatoes have a unit weight of 0.5 pounds unitWeight(potatoes,0.5).

% If John shopped for potatoes, he bought 5 pounds of potatoes. pounds(john,5,potatoes):-shop(john,potatoes,topsM,yesterday).

% The number of potatoes that john has is obtained by the no. of pounds/unit % weight. number(john,X,potatoes):-unitWeight(potatoes,Y),pounds(john,Z,potatoes),X is Z/Y.

% If N>=M then N is larger or equal to M. largerorequal(N,M):-N>=M.

% If John has some number of potatoes and if it is larger or equal to some % number then he has atleast that many number of potatoes. hasatleast(john,Y,potatoes):- number(john,X,potatoes),largerorequal(X,Y).

/* Question --------------------------------------------* If John shops for potatoes at tops yesterday then he bought 5 pounds of potatoes. * The unit weight of potatoes is 0.5. * If each potato weight 0.5 lbs and if john has 5lbs then john has 10 potatoes. * If John has some number of potatoes and if it is larger or equal to some

number then he has atleast that many number of potatoes. * Hence John has atleast 2 potatoes. ~~~~~~~~~~~~~~~~~~~~~~~~~~ | ?- hasatleast(john,2,potatoes). yes | ?- hasatleast(john,5,potatoes). yes | ?- hasatleast(john,100,potatoes). no ~~~~~~~~~~~~~~~~~~~~~~~~~~~ */

% 3) Did John buy any meat?

% Beef is a type of meat. typeOf(beef,meat).

% Chicken is a type of meat. typeOf(chicken,meat).

% If someone shopped for something somewhere sometime, then they bought % that thing. bought(X,Y):-shop(X,Y,_,_).

% If John bought something and if that thing is meat then John bought meat buys(X,Y):-bought(X,Z), typeOf(Z,Y).

/* Question --------------------------------------------Did John buy any meat? [yes] * John shopped for beef at tops yesterday * If someone shopped for something someday then they bought that thing * So John bought beef. * Beef is a type of meat. * If someone bought something and if that thing is of type X then that * person bought X. * John bought beef which is of type meat. * Hence, John bought meat ~~~~~~~~~~~~~~~~~~~~~~~~~ | ?- buys(john,meat). yes | ?- buys(john,vegetable). yes | ?- buys(john,X). X = vegetable ? n X = meat ? yes ~~~~~~~~~~~~~~~~~~~~~~~~~ */

% 4)If Mary was buying potatoes at the same time as John, did he see her?

% Mary was buying potatoes at tops at the same time as john.

shop(mary,potatoes,topsM,T):-shop(john,potatoes,topsM,T).

% Peter buys beef at tops yesterday. shop(peter,beef,topsM,yesterday).

% If someone buys something at some store at sometime then that person is at % that store at that time. isAtStore(X,Y,Z):-shop(X,_,Y,Z).

% If someone buys something at some stall at sometime then that person is at % that stall at that time. isAtStall(X,Y,Z):-shop(X,Y,_,Z).

% If someone is at some stall at some store, and if someone else is also at the % same stall and same store, then that person sees the other person sees(X,V):-isAtStore(X,Y,Z),isAtStall(X,U,Z),isAtStore(V,Y,Z),isAtStall(V,U,Z).

% Or else they will not see each other. sees(X,V):-!, \+isAtStore(X,Y,Z);\+isAtStall(X,U,Z);\+isAtStore(V,Y,Z);\ +isAtStall(V,U,Z), fail.

% If X sees Y then Y also sees X. sees(Y,X):-sees(X,Y).

/* Question --------------------------------------------If Mary was buying potatoes at the same time as John, did he see her? [yes] * John shopped for potatoes at tops yesterday.

* Hence Mary also shopped for potatoes yesterday. * If someone buys something at some stall at sometime then that person is at that stall at that time. * Hence John and Mary and Peter are at Tops store yesterday. * If someone buys something at some stall at sometime then that person is at that stall at that time. * Hence John and Mary are at the potato stall yesterday and John and Peter are at the beef stall yesterday. * If someone is at some stall at some store, and if someone else is also at the same stall and same store, then that person sees the other person. * If X sees Y then Y also sees X. * Hence Mary and John see each other and Peter and John see each other. sees(mary,john) sees(john,mary) sees(peter,john) sees(john,peter) * If they are not at the same store at the same stall at the same time then they don’t see each other. * Hence, Mary and Peter don’t see each other sees(mary,peter) sees(peter,mary) ~~~~~~~~~~~~~~~~~~~~~ | ?- sees(mary,john). yes | ?- sees(john,mary). yes | ?- sees(john,peter). yes | ?- sees(mary,peter). no

~~~~~~~~~~~~~~~~~~~~~ */

% 5)Are the potatoes made in the supermarket?

% Potatoes are type of vegetables. typeOf (potatoes,vegetable).

% Shoes are type of footwears. typeOf(shoes,footwear).

% If something is a vegetable then it originates from nature. originates(X,nature):-typeOf(X,vegetable).

% If something is a footwear then it does not originate in nature. originates(X,nature):-typeOf(X,footwear), !, fail.

% If something is of form something which orginates from man, then it is made % in the supermarket. made(X,supermarket):- !,\+originates(X,nature).

/* Question --------------------------------------------Are the potatoes made in the supermarket? [No] * Potatoes are vegetables. * If something is a vegetable then it originates in nature.

* Hence potatoes originate in nature. * Shoes are footwear. * If something is footwear then it cannot originate in nature. * If something is made in nature then it cannot be made in the supermarket. * Hence potatoes cannot be made by the supermarket. made(potatoes,supermarket) * Shoes can be made by the supermarket made(shoes,supermarket) ~~~~~~~~~~~~~~~~~~~~~~~~~~ | ?- made(potatoes,supermarket). no | ?- made(shoes,supermarket). yes ~~~~~~~~~~~~~~~~~~~~~~~~~~ */

% 6) What is John going to do with the potatoes?

% Potatoes are type of vegetables % Beef is a type of meat. % If something is a Vegetable or meat, it can be eaten. can(X,eaten):-typeOf(X,vegetable);typeOf(X,meat).

% Precedence of days after(yesterday,daybeforeyesterday). after(today, daybeforeyesterday). after(tomorrow, daybeforeyesterday).

after(today,yesterday). after(tomorrow,yesterday). after(tomorrow,today).

% Someone has something at sometime if he has shopped for it. has(X,Y,T):-shop(X,Y,_,T).

% Someone eats something at sometime if someone has something at that time % and if that thing can be eaten. whatWill(X,Y,T,eatThem):- has(X,Y,K), can(Y,eaten),after(T,K).

/* Question --------------------------------------------What is John going to do with the potatoes? [Eat them] * Potatoes are type of vegetables. * Beef is a type of meat. * If something is a Vegetable or meat, it can be eaten. * Hence potatoes and Beef can be eaten. * Someone has something at sometime if he has shopped for it. * Hence John has potatoes and beef. * Someone eats something at sometime if someone has something at that time and if that thing can be eaten. * Today and Tomorrow comes after yesterday. * Hence John eats beef or potatoes at anytime after yesterday ie today or tomorrow. **** Since the time unit is in days, it become vague to ask if John ate the **** potatoes or Beef yesterday, because the time could be before he bought it

**** or after he bought it. Here it is assumed that John goes shopping late night ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ | ?- whatWill(john,potatoes,today,X). X = eatThem ? yes | ?- whatWill(john,potatoes,tomorrow,X). X = eatThem ? yes | ?- whatWill(john,potatoes,yesterday,eatThem). no ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ */

% 7) Does Tops sell deodorant?

% Deodorant is a type of skin care product. typeOf(deodorant, skincare).

% Soap is a type of skin care product. typeOf(soap,skincare).

% Tops Maple road Supermarket is a type of Supermarket. typeOf(topsM,supermarket).

% Tops has a branch called Tops Maple road supermarket hasbranch(tops,topsM).

% Skin care products, vegetables, meat are available in supermarkets. available(skincare,supermarket). available(meat,supermarket). available(vegetable,supermarket).

% Something sells something if it has a branch which is a supermarket which % has those class of products sells(X,Y):hasbranch(X,U),typeOf(U,supermarket),typeOf(Y,Z),available(Z,supermarket); hasbranch(X,U),typeOf(U,supermarket),available(Y,supermarket);

/* Question --------------------------------------------Does Tops sell deodorant? [Yes] * Tops has a branch called Tops Maple road supermarket. * Tops Maple road Supermarket is a type of Supermarket. * Hence tops is also a type of supermarket. * Skin care products, vegetables, meat are available in supermarkets. * Deodorant is a type of skin care product. * Something sells something if it has a branch which is a supermarket which has those class of products * Hence tops sells deodorant because tops is a supermarket and supermarkets have skin care products and deodorant is a skin care product ~~~~~~~~~~~~~~~~~~~~~~~~ | ?- sells(tops,deodorant). yes

| ?- sells(tops,potatoes). yes | ?- sells(tops,meat). yes | ?- sells(tops,chicken). yes | ?- sells(tops,pork). no | ?- sells(tops,soap). yes | ?- sells(tops,apples). no | ?- sells(tops,vegetable). yes ~~~~~~~~~~~~~~~~~~~~~~~~~ */

% 8) Did John bring any money to the supermarket?

% If anyone shops at someplace for anything at some times then they pay % money for that thing at that time at that place. pay(X,money,Y,T):-shop(X,_,Y,T).

% If someone has to pay money at sometime at a store which is of some type % then they must bring that money to that place at that time. bring(X,money,Y,T):-pay(X,money,K,T),typeOf(K,Y).

/* Question --------------------------------------------Did John bring any money to the supermarket? [Yes] * If anyone shops at someplace for anything at some times then they pay money for that thing at that time at that place. * John shops at tops for potatoes and beef yesterday * Hence John pays money for potatoes and beef yesterday. * If someone has to pay money at sometime at a store which is of some type then they must bring that money to that place at that time. * Tops maple road is a supermarket. * Hence Johns brings money to the supermarket yesterday ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ | ?- bring(john,money,supermarket,yesterday). yes ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ */

% 9) Does John have less money after going to the supermarket?

% If anyone shops at someplace for anything at some times then they pay % money for that thing at that time at that place. % If someone who pays money at sometime at someplace of some type then % then he spent money that time in that type of place spentMoney(X,Z,T) :-pay(X,money,Y,T),typeOf(Y,Z).

% Define after and before yesterday

after(after,yesterday). after(yesterday,before).

% If someone spend money at someplace at some time then he had less money % after that time at the same place. moneyLeft(W,less,Y,T):- spentMoney(W,Y,U),after(T,U).

/* Question --------------------------------------------Does John have less money after going to the supermarket? [Yes] * If anyone shops at someplace for anything at some times then they pay money for that thing at that time at that place. * John shops at tops for potatoes and beef yesterday * Hence John pays money for potatoes and beef yesterday. * If someone who pays money at sometime at someplace of some type then then he spent money that time in that type of place. * Tops maple road is a supermarket. * Hence Johns spent money in a supermarket. * If someone spend money at someplace at some time then he had less money after that time at the same place. * After going to supermarket is after yesterday. * John spent money in that supermarket yesterday. * Hence John had less money after going to the supermarket. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ | ?- moneyLeft(john,X,supermarket,after). X = less ?

yes ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ */ %----------------------------------------------------------------------------------------------------------------------------

4 REFERENCES [1] Stuart Russell & Peter Norvig, Artificial Intelligence: A Modern Approach, Prentice Hall, Upper Saddle River, NJ, 1995, pp 263–264.

[2] Stuart Russell & Peter Norvig, Artificial Intelligence: A Modern Approach, Second Edition, Prentice Hall, Upper Saddle River, NJ, 2003, pp 372–373.

[3] Wikipedia.org. http://en.wikipedia.org/wiki/Prolog [4] Stuart C.Shapiro, “Project statement for ‘Using Prolog as a Knowledge-Based System’” http://www.cse.buffalo.edu/~shapiro/Courses/CSE563/2009/Projects/proj2.pdf