Transcription
Prolog ProgrammingDr. Maung M. HtayDepartment of Information Technology1/18/161
TextProlog Programming for Artificial Intelligenceby Ivan BratkoThird Edition, Addison Wesley2
Referencesu Artificial Intelligence by George F Luger, FourthEdition, Addison-Wesleyu Prolog Help/References http://www.geocities.com/saviranid/u Roman Barták, 1997 page http://ktiml.mff.cuni.cz/ bartak/prolog.old/intro.html3
What is Prolog?u Programming in Logicu Developed in early 1970, by Robert Kowalski, Maarteen vanEmden, and David D.H. Warren at Edinburgh, U.K., AlainColmerauer at Marseillesu u For symbolic, non-numeric computationSuited for solving problems that involve objects andrelations between objects4
Language Designu centered around a small set of basic mechanismsu including pattern matching, tree-based datastructuring and automatic backtracking5
Chapter 1: Introduction to Prologu Defining relations by factsu Defining relations by rulesu Recursive rulesu How Prolog answers questionsu Declarative and procedural meaning of programs6
1.1 Defining relations by factsu The fact that “Tom is a parent of Bob” can bewritten in Prolog as:u parent(tom,bob).u parent is the relationu tom and bob are its arguments7
A Family Tree8
Prolog Program for the previous family 9
Clausesu A clause declares one fact about a relationFor example,u u u parent(tom,bob) is a particular instance of theparent relationan instance is also called a relationshipa relation is defined as the set of all its instances10
Question to PrologFor example,u Is Bob a parent of Pat?In Prolog,u ?- parent(bob,pat).Prolog will answer:u yes11
More questionsA further query can be:u ?- parent(liz,pat).Prolog answers:u no12
More questions continue --Who is Liz’s parent?u ?- parent(X,liz).So the answer is:u X tom13
More questions continue --Who are Bob’s children?u ?- parent(bob,X).The first answer is:u X annThe another answer follows:u X pat14
Broader Questions -Who is a parent of whom?In other words,u Find X and Y such that X is a parent of Y.In Prolog,u ?- parent(X,Y).15
Broader Questions Continue --The answers are output as:u X pamu Y bob;u u u u u X tomY bob;X tomY liz;.16
Composed Query in Prologu Who is a grandparent of Jim?17
Composed Query in Prolog Continue -To find a grandparent, we need two steps:u Who is a parent of jim? Assume that there is some Y.u Who is a parent of Y? Assume that there is some X.In Prolog,u ?- parent(Y, jim), parent(X,Y).18
Composed Query in Prolog Continue -Who are Tom’s grandchildren?u ?- parent(tom,X), parent(X,Y).Do Ann and Pat have a common parent?u ?- parent(X,ann), parent(X,pat).19
Important Pointsu u u u Easy to define a relation, by stating the n-tuplesof objects that satisfy the relation such as parentEasy to query the Prolog system about relationsdefined in the programA Prolog program consists of clauses. Eachclause terminates with a full stopArguments of relations can be concrete objects,or constants (such as tom and ann), or generalobjects such as X and Y20
Important Points Continue --u u u u Concrete objects or constants are called atomsand general objects are called variablesQuestions to the system consist of one or moregoals that are to be satisfied in the program suchas: ?- parent(X,ann), parent(X,pat).Answer can be positive ( if satisfiable) or negative(if unsatisfable)If several answers satisfy the question thenProlog will find as many of them as desired by theuser21
1.2 Defining relations by rulesMore relationsUnary relationsBinary relationsu female(pam).sex(pam,feminine).u male(tom).sex(tom,masculine).u male(bob).sex(bob,masculine).u female(liz).sex(liz,feminine).u .Unary relations are simple yes / no properties of objects.22
More RelationsExampleu to define a relation offspring as the inverse of the parentrelation as a factu offspring(liz, tom) is inverse of parent(tom, liz)It is understood asLiz is an offspring of Tom if Tom is a parent of Liz.In general, we can say thatY is an offspring of X if X is a parent of Y.23
Relations are Defined Elegantlyu to define offspring relation using already definedparent relationFor all X and Y,Y is an offspring of Xif X is a parent of Y.In Prolog,u offspring(Y,X) :- parent(X,Y).24
What is Rules?For all X and Y,if X is a parent of Y thenY is an offspring of XIn Prolog,u offspring(Y,X) :- parent(X,Y).is called a Rule.25
Difference between facts and rulesu A fact like parent(tom,liz) is something always,unconditionally true.u On the other hand, rules specify things that are true ifsome condition is satisfied.26
Rules haveu body, a condition part (the right-hand side of the rule) andu head, a conclusion part (the left-hand side of the rule)The format isoffspring(Y,X) :- y27
More RulesTo define mother relation by ruleFor all X and Y,X is the mother of Y ifX is a parent of Y andX is a female.In Prolog,u mother(X,Y) :- parent(X,Y), female(X).28
More Rules Continue --To define grandparent relation by ruleFor all X and Y,X is a grandparent of Y ifX is a parent of Z andZ is a parent of Y.In Prolog,u grandparent(X,Y) :u parent(X,Z),u parent(Z,Y).29
More Rules Continue --How do we define sister relation?For all X and Y,X is a sister of Y ifboth X and Y have the same parent, andX is a female.In Prolog,u sister(X,Y) :u parent(Z,X),u parent(Z,Y),u female(X).30
Question to prologWho is pat’s sister?In Prolog,u ?- sister(X,pat).The answer to the previous programu X annu X patu We need to modify the program since pat is a sister ofherself31
Some Important Points, So Faru u u u u Prolog program can be added new clausesClauses are of three types: facts, rules, and questionsFacts declare things that are always, unconditionally trueRules declare things that are true depending on a givenconditionQuestions are to be asked by the user32
More Important Pointsu u u u u u Clauses consists of head and bodyBody is a list of goals separated by commasFacts have a head and the empty bodyQuestions only have the bodyRules have the head and the non-empty bodyA variable can be substituted by another object, thatis called, variable is instantiated33
Prolog Programming Dr. Maung M. Htay Department of Information Technology . 2 Text Prolog Programming for Artificial Intelligence by Ivan Bratko Third Edition, Addison Wesley . 3 References ! Artificial Intelligence
