Software Paradigms (Lesson 6) Logic Programming Table of Contents 1 Introduction 2 2 Facts 3 3 Predicates

1. Introduction

2. Facts

Examples:

• 
  Alex is a nice guy.
  
• 
  25 > 36
  
• 
  25 + 41 = 66
  
• 
  .Smith is a student and he got “2” for examination on Software Paradigms
  

3. Predicates (Structured Terms)

1. General Structures

Examples:

• 
  Alex is a nice guy. = = niceGuy (Alex)
  

• 
  25 > 36. = = greater Than (25,36)
  

• 
  25 + 41 = 66. = = plus (25,41,66)
  

• 
  .Smith is a student and he got “2” for examination on Software Paradigms
  

2. Predicates (Syntax)

Each argument of a predicate is a so-called term, for example, it can be another predicate (structured term). The number of arguments of a structured term is called its arity.

Examples:

greaterThan(9, 6) exam(a, b, h(c,d)) plus(2, 3, 5)

An important point to mention is that a structure is simply a mechanism for combining terms together, thus forming more complex ones but without performing any implicit evaluation. So for instance, in the last example above, the integers 2, 3, and 5 are combined with the functor plus. An equally valid combination, albeit a slightly misleading one, could be plus(2, 3, 7).

If evaluated,

• 
  plus(2,3,5) is True
  
• 
  plus(2,3,7) is False
  

3. Simple Terms

4. Atoms

• 
  A letter, which can possibly be followed by other letters (either case), digits, and the underscore character.
  

a greaterThan two_B_or_not_2_b

• 
  A string of special characters such as: + - * / \ = ^ < > : . ~ @ # $ &
  

• 
  A string of any characters enclosed within single quotes.
  

'ABC' '1234' 'a<>b'

In the third case above, if what appears between the single quotes is a valid atom as specified by one of the first two cases, then the quotes are optional. Thus, 'abc' and abc represent the same atom.

5. Numbers

0 -16 33 +100

Real numbers can be written in standard or scientific notation, as illustrated in the following:

0.5 -3.1416 6.23e+23 11.0e-3 -2.6e-2

A decimal point must appear in all real numbers and there must be at least one digit on either side of it. Several points with respect to the representation of numbers are implementation dependent. A brief list of some of these points follows. The actual range of numbers (real and integer) that can be represented.

6. Variables

Examples:

StudentName may be ‘Johns’, ‘Mayer’ , ‘Ivanov’, etc.

ExaminationMark may be 1, 2, 3, 4 and 5

GoodGuy may be True and False

Set of all possible values which may have a particular variable is called a variable scope or a variable range.

Please note the following (!)

A predicate (structured term) having all arguments as constants is called a fact. A particular Fact can be either true or false.

Example:

• 
  greaterThan (25,36) is False
  
• 
  plus (25,41,66) is True
  

Because we know formal rules to validate the facts and can communicate these rules to computers, i.e. an algorithm can be defined. Such terms are called computational terms.

• 
  niceGuy(Alex) is True
  

• 
  exam(‘Smith’,’Software Paradigms’) is False
  

Because we know that from our own experience which cannot be formalized as an algorithm. We can simply put such knowledge into a computer’s memory by listing all facts which are valid. For example, we can list all guys who considered to be nice or list all students who pass an examination on software paradigms. Such facts are called basic facts or database facts. Formally speaking, a logic programming paradigm heavily rely on a database of persistent data objects which list all basic facts which are valid. If a particular basic fact cannot be found in such database, it is considered to be false.

A predicate (structured term) having at least one variable argument is called a logical function or simply predicate. All variables used for definition of such predicate are called free variables. A particular logical function maps each combination of free variable values onto True/False boolean value. In other words, predicate can be true or false depending on a particular combination of free variable values.

Example:

• 
  greaterThan (25,X) is a function of variable “X” F(X)
  

• 
  plus (X,Y,66) is True
  

• 
  niceGuy(X) is True
  

exam(StudentName,VO) is False if StudentName = “Alex”, VO = “Software Paradigm” and (“Alex”,”Software Paradigms” can be found among persistent database objects “exam”),

4. Logical Operations and Composite Predicates

   1. Logical Operations

Example:

greaterThan(25,36) is True and plus(55,11,66) is True

niceGuy(‘Alex’) | exam(‘Alex’,’Software Paradigms’) is True if one of the facts: niceGuy(‘Alex’) or exam(‘Alex’,’Software Paradigms’) can be found in the database.

The operator precedence for the '&' and '|', operators follow the standard precedence rules, i.e. '&' binds stronger than '|'. Thus,

F1 & F2 | F3 == ( F1 & F2 ) | F3

Explicit use of parenthesis, as in predicate above, is required to override this default precedence. Thus if the intention is for the '|' operator to bind stronger in the above expression, it has to be written as

F1 & (F2 | F3)

Example

• 
  niceGuy(‘Alex’) & niceGuy(‘Tom’) | exam(‘Tom’, ‘Software Paradigm’,1)
  

• 
  niceGuy(‘Alex’) & (niceGuy(‘Tom’) | exam(‘Tom’, ‘Software Paradigm’,1))
  

2. Quantifiers

• 
  the existential quantifier, denoted by the symbol '', and
  
• 
  the universal quantifier, denoted by the symbol ''
  

Quantification is applied to a formula and is written preceding it. For example,

x (greaterThan(Y,X) & greaterThan(12,Y))

would be read as "there exists an X such that X is less than Y and Y is less than 12". The formula to which the quantification is applied is called the scope of quantification. Occurrences of quantified variables in the scope of quantification are said to be bound (existentially or universally). The scope is normally obvious from the written expressions, but if ambiguities might otherwise arise, we will use parenthesis to delimit scope.

Informally, the formula “X ( )" asserts that there exists at least one value of X (from among its range of values) such that is true. This assertion is false only when no value of X can be found to satisfy . On the other hand, if the assertion is true, there may be more than one such value of X, but we don't care which (!). In other words, the truth of an existentially quantified expression is not a function of the quantified variable(s).

As an example, consider the unquantified expression

greaterThan(Y,X) & greaterThan(12,Y)

and suppose X ranges over {4,15} and Y over {7,14}. The truth table for the expression is:

X (greaterThan(Y,X) & greaterThan(12,Y))

Since we don't care which value of X makes the expression true as long as there is at least one, its truth depends only on the unbound variable Y:

Y	X (greaterThan(Y,X) & greaterThan(12,Y))
7	True
14	False

The truth of a quantified expression does depend, of course, on the range of permitted values of the quantified variables.

Let's turn now to the universal quantifier. Informally, the formula "X ( > )" asserts that for every value of X(from among its range of values) is true. Like the existential quantifier, the truth of an existentially quantified expression is not a function of the quantified variable(s).

Consider, for example, the unquantified expression

greaterThan(Y,X) | greaterThan(12,Y)

and suppose X ranges over {4,15} and Y over {7,14}.

The truth table for the expression is:

X	Y	greaterThan(Y,X) | greaterThan(12,Y)
4	7	True
15	7	True
4	14	True
15	14	False

Now consider the same expression but with X universally quantified:

X (greaterThan(Y,X) & greaterThan(12,Y))

In a sense, like the existentially quantified variable, we don't care what the values of X are, as long as every one of them makes the expression true for any given Y. Thus its truth table is:

:

Y	X (greaterThan(Y,X) | greaterThan(12,Y))
7	True
14	False

Note that the different types of quantifiers can be mixed. But note also that their order is significant, i.e. x y ( ) is not the same as y x ( ).

Suppose, for example, a predicate is_a_mother(M,Ch) defines a set of database facts “ M is the mother of Ch”.

Ch M (is_a_mother(M,Ch))

asserts that everyone has a mother. Whereas,

M Ch (is_a_mother(M,Ch))

asserts that there is a single individual (M) who is the mother of everyone!

3. Well-Formed Formulae

1. F(X1, ... Xn) is a WFF where X1, X2, .. are called free variables

2. F1 & F2 and F1 | F2 are WFFs if F1 and F2 are WFFs

3. (F) is a WFF if F is a WFF

4. x (F(X)) and x (F(X)) are WFFs if F(X) is a WFF with a free occurrence of the variable X. In this case, X is called a bound variable in the scope of F(x).

5. Rules of Inference

   1. Head and Body

Note, these two component (body and head) may be also called conclusion and premise respectively.

:-

where

body is a WFF (logical expression)

head is a predicate

If we do not use variables, both components (i.e. head and body) are facts. The rule is interpreted as follows:

“If a body is valid (true) then head is also valid (true) by definition”

Examples:

humanBeing(‘Alex’):-goodGuy(‘Alex’)

if Alex is a good guy, then he is a human being.

Suppose, fact enrollVO(‘Alex’, ‘Programming’) is true if a student “Alex” is enrolled for the course “Programming”.

Suppose also, the fact locVO(‘Programming’, ‘Thursady, ‘Room 22’) is true if the classes on Programming take place in room 22 on Thursday. We can define the following rule of inference

mustGo(‘Alex’, ‘Thursday’,’Room 22’) :-

enrollVO(‘Alex’, ‘Programming’) & locVO(‘Programming’, ‘Thursday’, ‘Room 22’)

meaning that the fact mustGo(‘Alex’, ‘Thursday’, ‘Room 22’) is true if both facts

enrollVO(‘Alex’, ‘Programming’) and locVO(‘Programming’, ‘Thursday’, ‘Room 22’)

are true.

Actually, all the examples above are not very illustrative because rules of inference are almost never defined without variables.

If we use variables, both components (i.e. head and body) are predicates. The rule is interpreted as follows:

“If a body is valid (true) for a particular combination of values of free variables then the head is also valid (true) for the same combination of values of free variables”

Examples:

humanBeing(X):-goodGuy(X)

any (!) good guy is a human being.

Suppose, predicate enrollVO(Student, Subject) is true if a student is enrolled for a course on this particular subject.

Suppose also, the predicate locVO(Subject, Day, Room) is true if classes on this particular subject takes place in this room and on this day.

We can define the following rule of inference

mustGo(Student, Room, Day, Subject) :-

enrollVO(Student, Subject) & locVO(Subject, Day, Room)

meaning that a particular student should be in a particular room on a stipulated day, if he/she enrolled for a classes and this classes take place in this room on that day.

Predicates enrollVO and locVO definitely operates on database facts, i.e. system should search an internal database to find whether, for example, the fact enrollVO(‘Alex’, ‘Programming’) is true or false.

Suppose, the database looks as follows:

locVO	Subject	Day	Room
	Hypermedia	Monday	Room 22
	Databases	Tuesday	Room 23
	Programming	Thursday	Room 22

The table above, just told us that, for example, the fact locVO (Databases,Tuesday,Room 23) is true, at the same time the fact locVO (Databases,Monday,Room 23) is false, etc.

In analogy, basic facts enrollVO may be seen as the following table.

enrollVO	Student	Subject
	Palina	Hypermedia
	Palina	Programming
	Alex	Programming
	Alex	Databases

Result of application the following rule of inference

mustGo(Student, Room, Day, Subject) :-

enrollVO(Student, Subject) & locVO(Subject, Day, Room)

to the above mentioned basic facts is a number of inferred facts !

All inferred facts are true by definition and can be seen as the following table:

mustGo	Student	Room	Day	Subject
	Palina	Room 22	Monday	Hypermedia
	Palina	Room 22	Thursday	Programming
	Alex	Room 22	Thursday	Programming
	Alex	Room 23	Tuesday	Databases

In other words, the system automatically infer such facts as

mustGo(Palina,Room 22, Monday, Hypermedia) is true:

“Palina should go to Room 22 on Monday to participate in classes on Hypermedia”

mustGo(‘Alex’,’Room 22’, ‘Monday’, ‘Hypermedia’) is false:

“Alex has nothing to do in Room 22 on Monday”

The last example suggest that perhaps we should simplify the rule by removing the Subject variable from the head:

mustGo(Student, Room, Day) :-

enrollVO(Student, Subject) & locVO(Subject, Day, Room)

and inferring the following facts:

mustGo	Student	Room	Day
	Palina	Room 22	Monday
	Palina	Room 22	Thursday
	Alex	Room 22	Thursday
	Alex	Room 23	Tuesday

Actually, this rule is erroneous because free variables in the head of the rule are not identical to the variables in the body.

Thus, in order to verify a fact mustGo(‘Alex’,’Room 22’, ‘Thursday’), the system should evaluate the following expression:

enrollVO(‘Alex’, Subject) & locVO(Subject, ‘Room 22’, ‘Thursday’)

Obviously the expression is not a fact and depends on a particular Subject. For example, it is true, if subject is programming and false for any other value.

enrollVO(‘Alex’, ‘Programming’) & locVO(‘Programming’, ‘Room 22’, ‘Thursday’) – true

enrollVO(‘Alex’, ‘Databases’) & locVO(‘Databases’, ‘Room 22’, ‘Thursday’) – false

Following to the formal definition of a rule of inference:

“If a body is valid (true) for a particular combination of values of free variables then the head is also valid (true) for the same combination of values of free variables”

the system simply cannot make conclusion on whether the expression

mustGo(‘Alex’,’Room 22’, ‘Thursday’) is true or false.

There is of course an obvious solution for the problem: existential quantifier.

Thus, we can define the rule as the following:

mustGo(Student, Room, Day) :-

Subject (enrollVO(Student, Subject) & locVO(Subject, Day, Room))

The above predicate (body) is true if there exists at least one subject such that the condition

enrollVO(Student, Subject) & locVO(Subject, Day, Room) is true.

In other words, the fact mustGo(‘Alex’,’Room 22’, ‘Thursday’) is definitely true since there exists a subject, for example, “Programming” such that

enrollVO(‘Alex’, ‘Programming’) & locVO(‘Programming’, ‘Room 22’, ‘Thursday’) is true.

2. Recursion

Recursive definition of rules of inference is a very powerful and commonly used method of logic programming.

Suppose, we have a predicate

parent(G,D)

the predicate identifies whether a person D is a child of person G.

We can easily define a new predicate descendent(G,D) that identifies whether a person D is a descendent of person G as

descendent(G,D):-parent(G,D) | X (parent(G,X) & descendent(X,D))

Note that rules like this one, can be defined more clearly using a number of rules of inference with one and the same head.

descendent(G,D):-parent(G,D)

descendent(G,D):- X (parent(G,X) & descendent(X,D))

• 
  first rule for finding direct descendent just copy all facts “parent” as facts “descendent”
  
• 
  the second rule uses the same head predicate (i.e., recursion) to find indirect descendent.
  

Here, if the inferred fact is true in accordance with one of the rules, it is considered to be true generally.

Consider the following genealogy tree,

It may be described as the following facts:

parent	G	D
	Nick	Pauline
	Pauline	Alex
	Pauline	Paul
	Alex	Tom

Application of the rule:

descendent(G,D):-parent(G,D)

results in the following inferred facts

descendent	G	D
	Nick	Pauline
	Pauline	Alex
	Pauline	Paul
	Alex	Tom

Application of the rule:

descendent(G,D):- X (parent(G,X) & descendent(X,D))

results in the following inferred facts

descendent	G	D	X	parent(G,X) & descendent(X,D))
	Nick	Alex	Pauline	parent(‘Nick’,’Pauline’) & descendent(‘Pauline’,’Alex’)
	Nick	Paul	Pauline	parent(‘Nick’,’Pauline’) & descendent(‘Pauline’,’Paul’)
	Pauline	Tom	Alex	parent(‘Pauline’,’Alex’) & descendent(‘Alex’,’Tom’)
	Nick	Tom	Pauline	parent(‘Nick’,’Pauline’) & descendent(‘Pauline’,’Tom’)

3. Inferred Calculations

In Logic Programming, calculation are performed by means of computational terms looking as, for example, follows:

• 
  plus(V1,V2,R) the predicate is true if R = V1 + V2;
  
• 
  mult(V1,V2,R) the predicate is true if R = V1 * V2;
  

etc.

Consider, for example, a well-known example of a so-called bill of materials that identify which components and in which amount are needed to assembly a particular product / another component.

It may be described as the following facts: need(P,C,Q)

need	P	C	Q
	D_A	D_B	5
	D_B	D_D	3
	D_B	D_C	8
	D_D	D_E	4

The following rules identify how many direct and indirect components are needed to assembly a particular product / component

need+(P,C,Q):-need(P,C,Q)

need+( P,C,Q):- X Q1 Q2(need(P,X,Q1) & need+(X,C,Q2) & mult(Q1,Q2,Q))

Application of the rule:

need+(P,C,Q):-need(P,C,Q)

results in the following inferred facts

Need+	P	C	Q
	D_A	D_B	5
	D_B	D_D	3
	D_B	D_C	8
	D_D	D_E	4

Application of the rule:

need+( P,C,Q):- X Q1 Q2(need(P,X,Q1) & need+(X,C,Q2) & mult(Q1,Q2,Q))

results in the following inferred facts

need+	P	C	Q	X,Q1,Q2	need(P,X,Q1) & need+(X,C,Q2) & mult(Q1,Q2,Q)
	D_A	D_D	15	D_B, 5, 3	need(D_A,D_B,5) & need+(D_B,D_D,3) & mult(5,3,15)
	D_A	D_C	40	D_B, 5, 8	need(D_A,D_B,5) & need+(D_B,D_C,8) & mult(5,8,40)
	D_B	D_E	12	D_C, 3, 4	need(D_B,D_C,3) & need+(D_C,D_E,4) & mult(3,4,12)
	D_A	D_E	60	D_B, 5, 12	need(D_A,D_B,5) & need+(D_B,D_E,12) & mult(5,12,60)

4. Functions and Variables

Defining calculations as computational predicates involving multiple bound variable as, for example,

need+( P,C,Q):- X Q1 Q2(need(P,X,Q1) & need+(X,C,Q2) & mult(Q1,Q2,Q))

may constitute a serious problem.

Functions provide much more straight and simple way to define calculations. A particular function may be applied to a number of free variables and be reused further as a variable.

For example, the previously defined rule of inference need+ may be defined in much more clear way as:

need+( P,C,(Q1 * Q2)):- X (need(P,X,Q1) & need+(X,C,Q2) )

where notation (Q1 * Q2) is used in a normal mathematical way

Application of this rule results in the same list of inferred facts, but the inference procedure is much simple

need+	P	C	Q1*Q2	X	need(P,X,Q1) & need+(X,C,Q2)
	D_A	D_D	15	D_B	need(D_A,D_B, 5) & need+(D_B,D_D, 3)
	D_A	D_C	40	D_B	need(D_A,D_B, 5) & need+(D_B,D_C, 8)
	D_B	D_E	12	D_C	need(D_B,D_C,3) & need+(D_C,D_E,4)
	D_A	D_E	60	D_B	need(D_A,D_B,5) & need+(D_B,D_E,12)

6. Some Analogies

One might think of predicates and facts in several ways. One natural way (perhaps especially so for non-programmers) to look at rules of inference is to think of them as declarative sentences in natural language. As stated earlier, predicates describe relationships between entities (e.g., grand-parenthood, parenthood, etc.). Some relationships can be stated in one sentence, other relationships require more than one sentence (rule of inference) in order to specify the relationship fully.

Programmers might find similarities between a predicate and a procedure. In that sense, a predicate specifies how to "compute" something (e.g., finding a ascendant to an individual). In this context, rules would correspond to a procedure call and general directives would correspond to calls involving built-in procedures (this last analogy is weaker than the others). To regard predicates and queries in this way is certainly accurate, however, it constitutes a restricted view.