Logic Programming and Matching in Prolog

logic programming n.w
1 / 46
Embed
Share

Explore the concepts of logic programming, matching, and unification in Prolog through examples and explanations. Learn about the search strategy used by Prolog and the precise definitions of matching criteria. Discover how terms are matched based on equality and variable instantiation in Prolog.

  • Logic Programming
  • Matching
  • Prolog
  • Unification
  • Search Strategy
rayaanacharya
roy_432 Follow

Uploaded on | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

Download Presentation

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript

  1. Logic Programming Dr. Metwally Rashad 8/10/2018

  2. Knowledge Base 4 woman(mia). woman(jody). woman(yolanda). loves(vincent, mia). loves(marsellus, mia). loves(pumpkin, honey_bunny). loves(honey_bunny, pumpkin). ?- loves(marsellus,X), woman(X). X=mia yes ?- 1/44

  3. Matching and Proof Search Today s lecture has two main goals: 1. To discuss the idea of matching (unification) in Prolog, and to explain how Prolog matching differs from standard matching. -Along the way, we ll introduce =, the built-in Prolog predicate for matching. 2. To explain the search strategy Prolog uses when it tries to prove something. 2/44

  4. Matching (Unification) Recall previous example, where we said that Prolog matches woman(X) with woman(mia) The variable X match with the atom mia. 3/44

  5. Matching (Unification) Matching Definition - Two terms match, if they are equal (same term) or - if they contain variables that can be instantiated in such a way that the resulting terms are equal. Ex. mia and mia match/unify 42 and 42 match woman(mia) and woman(mia) match mia and X match woman(Z) and woman(mia) match vincent and mia do not match woman(mia) and woman(jody) do not match 4/44

  6. Precise Definition 1. If T1 and T2 are constants, then T1 and T2 match if they are the same atom, or the same number. 2. If T1 is a variable and T2 is any type of terms, then T1 and T2 match, and T1 is instantiated to T2. (and vice versa) 3. If T1 and T2 are complex terms then they match if: a) They have the same functor and arity, and b) all their corresponding arguments match, and c) the variable instantiations are compatible. 5/44

  7. Prolog matching ?- mia = mia. or =(mia, mia). yes ?- 6/44

  8. Prolog matching ?- mia = mia. yes ?- mia = vincent. no ?- 7/44

  9. Prolog matching ?- mia = mia. yes ?- mia = vincent. no ?- mia = X. X=mia yes ?- 8/44

  10. Prolog matching ?- mia = mia. yes ?- mia = vincent. no ?- mia = X. X=mia yes ?- 2=2 yes ?- 9/44

  11. Prolog matching ?- mia = mia. yes ?- mia = vincent. no ?- mia = X. X=mia yes ?- 2=2 yes ?- 2 =2 no 10/44

  12. Prolog matching ?- mia = mia. yes ?- X=Y. X=Y yes ?- On the other hand, you may get the following output: ?- mia = vincent. no ?- mia = X. X=mia yes X = _5071 Y = _5071 ?- 2=2 yes Here, both arguments are variables. Prolog is doing here is to create a new variable (namely _5071 ) and saying that, from now on, both X and Y share the value of this variable. ?- 2 =2 no 11/44

  13. How will Prolog respond? ?- X=mia, X=vincent. 12/44

  14. How will Prolog respond? ?- X=mia, X=vincent. no ?- Why? after working through the first goal, Prolog has instantiated X with mia, so that it cannot match it with vincent anymore. Hence the second goal fails. 13/44

  15. Example with complex terms ?- k(s(g),Y) = k(X,t(k)). 14/44

  16. Example with complex terms ?- k(s(g),Y) = k(X,t(k)). X=s(g) Y=t(k) yes ?- 15/44

  17. Example with complex terms ?- k(s(g),Y) = k(X,t(k)). X=s(g) Y=t(k) yes ?- k(s(g),t(k)) = k(X,t(Y)). 16/44

  18. Example with complex terms ?- k(s(g),Y) = k(X,t(k)). X=s(g) Y=t(k) yes ?- k(s(g),t(k)) = k(X,t(Y)). X=s(g) Y=k yes ?- 17/44

  19. Occurs Check In A standard matching algorithm - Carries out an occurs check. - If it is asked to match a variable with another term it checks whether the variable occurs in the term. In Prolog - It does not make an occurs check 18/44

  20. Occurs Check Prolog does not use a standard matching algorithm when it performs matching/unification. Consider the following query: ?- father(X) = X. - Do you think these terms match or not? A standard matching algorithm would say: No, they don t. Do you see why? Pick any term and instantiate X to the term you picked. EX. If you instantiate X to father(father(butch)), the left hand side becomes father(father(father(butch))), and the right hand side becomes father(father(butch)). 19/44

  21. Occurs Check - Infinite terms In old Prolog (Not enough memory to complete query!) ?- father(X) = X. X=father(father(father(father(father(father(father(father(father(father(father (father(father(father(father(father(father(father(father(father (father(father (father(father(father(father(father(father(father(father(father(father(father(father(father (father(father(father(father(father(father(father(father(father(father(father(father(father ( .. In New Prolog (SWI) ?- father(X) = X. X=father(father(father( ))) yes ?- 20/44

  22. Programming with matching vertical( line(point(X,Y), point(X,Z))). horizontal( line(point(X,Y), point(Z,Y))). ?- vertical(line(point(1,1),point(1,3))). yes ?- 21/44

  23. Programming with matching vertical( line(point(X,Y), point(X,Z))). horizontal( line(point(X,Y), point(Z,Y))). ?- vertical(line(point(1,1),point(1,3))). yes ?- vertical(line(point(1,1),point(3,2))). no ?- 22/44

  24. Programming with matching vertical( line(point(X,Y), point(X,Z))). horizontal( line(point(X,Y), point(Z,Y))). ?- horizontal(line(point(1,1),point(1,Y))). Y = 1; no ?- 23/44

  25. Programming with matching vertical( line(point(X,Y), point(X,Z))). horizontal( line(point(X,Y), point(Z,Y))). ?- horizontal(line(point(2,3),Point)). Point = point(Z,3); or Point = point(_554,3); no ?- 24/44

  26. Proof Search Now that we know about matching, we are in a position to learn how Prolog searches a knowledge base to see if a query is satisfied. In other words: we are ready to learn about Proof Search 25/44

  27. Example f(a). f(b). g(a). g(b). h(b). k(X):- f(X), g(X), h(X). ?- k(Y). 26/44

  28. Example: Search Tree f(a). f(b). g(a). g(b). h(b). k(X):- f(X), g(X), h(X). ?- k(Y). ?- k(Y). 27/44

  29. Example: Search Tree f(a). f(b). g(a). g(b). h(b). k(X):- f(X), g(X), h(X). ?- k(Y). Y=X ?- f(X), g(X), h(X). ?- k(Y). 28/44

  30. Example: Search Tree f(a). f(b). g(a). g(b). h(b). k(X):- f(X), g(X), h(X). ?- k(Y). Y=X ?- f(X), g(X), h(X). X=a ?- g(a), h(a). ?- k(Y). 29/44

  31. Example: Search Tree f(a). f(b). g(a). g(b). h(b). k(X):- f(X), g(X), h(X). ?- k(Y). Y=X ?- f(X), g(X), h(X). X=a ?- g(a), h(a). ?- k(Y). ?- h(a). Fail Fail 30/44

  32. Example: Search Tree f(a). f(b). g(a). g(b). h(b). k(X):- f(X), g(X), h(X). ?- k(Y). Y=X ?- f(X), g(X), h(X). X=a X=b ?- g(a), h(a). ?- g(b), h(b). ?- k(Y). ?- h(a). Fail Fail 31/44

  33. Example: Search Tree f(a). f(b). g(a). g(b). h(b). k(X):- f(X), g(X), h(X). ?- k(Y). Y=X ?- f(X), g(X), h(X). X=a X=b ?- g(a), h(a). ?- g(b), h(b). ?- k(Y). ?- h(a). ?- h(b). Fail Fail 32/44

  34. Example: Search Tree f(a). f(b). g(a). g(b). h(b). k(X):- f(X), g(X), h(X). ?- k(Y). Y=X ?- f(X), g(X), h(X). X=a X=b ?- g(a), h(a). ?- g(b), h(b). ?- k(Y). Y=b ?- h(a). ?- h(b). Fail Fail True 33/44

  35. Example: Search Tree f(a). f(b). g(a). g(b). h(b). k(X):- f(X), g(X), h(X). ?- k(Y). Y=X ?- f(X), g(X), h(X). X=a X=b ?- g(a), h(a). ?- g(b), h(b). ?- k(Y). Y=b; no ?- ?- h(a). ?- h(b). Fail Fail True 34/44

  36. Another example loves(vincent,mia). loves(marsellus,mia). jealous(A,B):- loves(A,C), loves(B,C). ?- jealous(X,Y). 35/44

  37. Another example ?- jealous(X,Y). loves(vincent,mia). loves(marsellus,mia). jealous(A,B):- loves(A,C), loves(B,C). ?- jealous(X,Y). 36/44

  38. Another example ?- jealous(X,Y). loves(vincent,mia). loves(marsellus,mia). jealous(A,B):- loves(A,C), loves(B,C). X=A Y=B ?- loves(A,C), loves(B,C). ?- jealous(X,Y). 37/44

  39. Another example ?- jealous(X,Y). loves(vincent,mia). loves(marsellus,mia). jealous(A,B):- loves(A,C), loves(B,C). X=A Y=B ?- loves(A,C), loves(B,C). A=vincent C=mia ?- jealous(X,Y). ?- loves(B,mia). 38/44

  40. Another example ?- jealous(X,Y). loves(vincent,mia). loves(marsellus,mia). jealous(A,B):- loves(A,C), loves(B,C). X=A Y=B ?- loves(A,C), loves(B,C). A=vincent C=mia ?- jealous(X,Y). X=vincent Y=vincent ?- loves(B,mia). True B=vincent 39/44

  41. Another example ?- jealous(X,Y). loves(vincent,mia). loves(marsellus,mia). jealous(A,B):- loves(A,C), loves(B,C). X=A Y=B ?- loves(A,C), loves(B,C). A=vincent C=mia ?- jealous(X,Y). X=vincent Y=vincent; X=vincent Y=marsellus ?- loves(B,mia). True True B=vincent B=marsellus 40/44

  42. Another example ?- jealous(X,Y). loves(vincent,mia). loves(marsellus,mia). jealous(A,B):- loves(A,C), loves(B,C). X=A Y=B ?- loves(A,C), loves(B,C). A=marsellus C=mia A=vincent C=mia ?- jealous(X,Y). X=vincent Y=vincent; X=vincent Y=marsellus; ?- loves(B,mia). ?- loves(B,mia). True True B=marsellus B=vincent 41/44

  43. Another example ?- jealous(X,Y). loves(vincent,mia). loves(marsellus,mia). jealous(A,B):- loves(A,C), loves(B,C). X=A Y=B ?- loves(A,C), loves(B,C). A=marsellus C=mia A=vincent C=mia . X=vincent Y=marsellus; X=marsellus Y=vincent ?- loves(B,mia). ?- loves(B,mia). True True True B=vincent B=marsellus B=vincent 42/44

  44. Another example ?- jealous(X,Y). loves(vincent,mia). loves(marsellus,mia). jealous(A,B):- loves(A,C), loves(B,C). X=A Y=B ?- loves(A,C), loves(B,C). A=marsellus C=mia A=vincent C=mia . X=marsellus Y=vincent; X=marsellus Y=marsellus ?- loves(B,mia). ?- loves(B,mia). True True True True B=marsellus B=vincent B=vincent B=marsellus 43/44

  45. Another example ?- jealous(X,Y). loves(vincent,mia). loves(marsellus,mia). jealous(A,B):- loves(A,C), loves(B,C). X=A Y=B ?- loves(A,C), loves(B,C). A=marsellus C=mia A=vincent C=mia . X=marsellus Y=vincent; X=marsellus Y=marsellus; no ?- loves(B,mia). ?- loves(B,mia). True True B=marsellus True True B=vincent B=vincent B=marsellus 44/44

  46. 1/20

Related


Coverage Semantics for Dependent Pattern Matching

Coverage Semantics for Dependent Pattern Matching

ivory
Logic Programming and AI Principles

Logic Programming and AI Principles

autumn
Introduction to Prolog Programming: Facts, Rules, and Queries

Introduction to Prolog Programming: Facts, Rules, and Queries

phan_yan
Inference in Prolog with Himalayan Club Example

Inference in Prolog with Himalayan Club Example

lyla_16
Enhancing Matching Gift Strategies for Nonprofits

Enhancing Matching Gift Strategies for Nonprofits

loyd_ora
Graph Pattern Matching Challenges and Solutions

Graph Pattern Matching Challenges and Solutions

mmenk
Matching Keys in Database Systems

Matching Keys in Database Systems

keagen
Stable Matching Problem and Gale-Shapley Algorithm Overview

Stable Matching Problem and Gale-Shapley Algorithm Overview

dem_k
Prolog Mini-Exercises: Solving Logic Problems

Prolog Mini-Exercises: Solving Logic Problems

cat_b
Declarative Programming and Regular Expressions

Declarative Programming and Regular Expressions

anes444
Stable Matching and Orderly Markets in Various Allocation Systems

Stable Matching and Orderly Markets in Various Allocation Systems

cmcke
Califa Simulations and Experimental Observations in Nuclear Physics Research

Califa Simulations and Experimental Observations in Nuclear Physics Research

lars_30
Overview of Prolog Programming Paradigm

Overview of Prolog Programming Paradigm

alysan
Prolog: A Declarative Approach through the Years

Prolog: A Declarative Approach through the Years

sha_kre
Pattern Matching: Overview and Applications in Technology

Pattern Matching: Overview and Applications in Technology

ari_van
Prolog Queries in Discrete Mathematics

Prolog Queries in Discrete Mathematics

bgend
Conditional Expressions and Pattern Matching

Conditional Expressions and Pattern Matching

diontae
Ultimatch: Matching Counterfactuals in Your Way

Ultimatch: Matching Counterfactuals in Your Way

doslu
Introduction to Prolog: Declarative Programming for AI Systems

Introduction to Prolog: Declarative Programming for AI Systems

fabi_3
A First Look at Prolog: Chapter Nineteen Modern Programming Languages

A First Look at Prolog: Chapter Nineteen Modern Programming Languages

mysliwiec_t
Fast Exact Matching Algorithms for Large DNA and Protein Sequences

Fast Exact Matching Algorithms for Large DNA and Protein Sequences

valenasa
Maximizing Happiness Through Ice-Cream Matching Problem

Maximizing Happiness Through Ice-Cream Matching Problem

balderson_d

More Related Content