1. Facts
The simplest kinds of statement called a fact. Facts are a means of starting that a relation holds between objects. An example is father(abraham,isaac). It means that abraham is father of isaac. Names of a individually are called atoms. A finite set of facts constitues a program. A set of facts is also description of a situation.
2. Queries
Queries are a means of retrieving information from a logic program. A query asks whether a certain relation holds between objects. For example,the query father(abraham,isaac)? asks whether the father relationship holds between abraham and isaac. The facts is in program 1 and the answer is yes.
3. Logical Variable,Substitutions, and Instances
logical variable stands for an unspecified individual and is used accordingly. variables are means of summarizing many queries. A query containing a variable asks whether there is a value for the variable that makes the query a logical consequence of the program.Variable in logic programs behave differently from variables in conventional programming languages. They stand for an unspecified but single entity rather than for a store location in memory.
Having introduced variables,we can define a term, the single data structure in logic programs. Constants and variable are terms. Also compound terms, or structures are terms.
Queries,goals, and more generally terms where variables do not occur are called ground. Where variables do occur,they are called nonground.
Definition
A substituion is a finite set(possibly empty) of pairs of the form Xi = ti,where Xi is a variable and ti is a term, and and Xi ≠ Xj for every i ≠ j, and Xi does not occur in tj,for any i and j.
Definition
A is an instance of B if there is a substitution θ such that A =Bθ
4. Existential Queries
Variables in queries are existentially quantified which means,intuively, that the query father(abraham,X)?reads “Does there exist an X such that abraham is the father of X?The next deduction rule is generalization. The fact father(abraham,issaac) implies that there exist an X such taht father (abraham,X) is true,namely,X=isaac.
5. Universal facts
VAriables in facts are implicitly universally quantifiesd,which means,intuively, that the fact likes(X,pomegranates) states that for all X, X like pomegranates.In general, a factp(T1,T2,…,Tn) readas that for all X1,…,Xk,where Xi are variables occuring in the fact,p(T1,…,Tn) is true. Logically,from a universally quantified fact one can deduce any instance of it. For example, from likes(X,pomegrantes),deduce likes (abraham,pomegranates). This is the third deduction rule,called instantiation. From a universally quantified statements P,deduce an instance
of it,P0,for any substitution 0.
Definition
C is common instance of A and B if it an instance of A and an instance of B,in other words,if there are substitutions θ1 and θ2 such that C=Aθ1 is syntatically identical to Bθ2
6. Conjunctive Queries and Shared Variables
Conjunctive queries are a conjunction of goals passed as a query . for example a query father(haran,X),male(X)?. The solutions to the query father(haran,X)? Are restricted to the children that are male. A conjunctive query is a logical consequence of a program P if all the goals in the conjunction are consequences of P,where shared variables are instantiated to the same values in different goals.A sufficient condition is is that there be a ground instance of the query that is consequence of P. This instance then deduces the conjuncts in the query via generalizations.
7. Rules
Rules are the statements of the form : A <– B1,B2,…,Bn
Where n ≥ 0. The goal A is the head of the rule. A rule expressing the son relationship is
son(X,Y) <- father(Y,X),male(X).
Rules can be viewed in two ways :
- Procedural reading
They are a means of expressing new or complex queries in terms of simple queries. A query son(X,haran)? To the program that contains the preceding rule of a son is translated to the query father(haran,X),male(X)? According to the rule, and solved as before.A new query about the son relationship has been built from simple queries involving father and male relationship.
- Logical axiom
The backward arrow is used to denote logical implication. The son rule reads:”X is son of Y if Y is the father of X and X is male”. In this view, rules are a means of defining new or a complex relationship using other,simpler relationship.
Definition
The law of universal modus ponens says that from the rule
R=(A<-B1,B2,…,Bn)
And the facts
B1.
B2
.
.
Bn
A’ can be deduced if
A’ <- B’1, B’2,…, B’n is an instance of R.
Definition
A logic programs is a finite set of rules
Definition
An existentially quallified goal G is logical consequence of a program P if there is a clause in P with a ground instance is a clause in P with a ground instance A <- B1,B2,…,Bn,n≥0 such that B1,…, Bn are logical consequences of P, and A is an instance of G.
8. A simple abstract listener
The abstract interpreter performs yes/no computations. It takes as input a program and a goal, and answer yes if the goal is a logical consequence of the program and no otherwise. The current,usually conjunctive,goal at any stage of the computation is called resolvent. A trace of the interpreter is the sequence of resolvents produced during the computation. Each iteration of the while loop of the abstract interpreter corresponds to a single application of modus ponens. This called reduction.
Input : A ground goal G and a program P
Output : yes if G is a logical consequence of P
No otherwise
Algorithm :
Initialize the resolvent to G
While the resolvent is not empty do
Choose a goal A from the resolvent
Choose a ground instance of a clause A’<-B1...Bn from P
Such that A and A’ are identical
If no such goal and clause exist,exit the while loop
Replace A by A’<-B1...Bn in the resolvent
If the resolvent is empty,then output yes,else no
Definition
A reduction of a goal G by a program P is the replacement of G by the body of an instance of a clause in P,whose head is identical to the choosen goal.
9. The Meaning of a Logic Program
Definition
The meaning of a logic program P,M(P) is thee set of ground goals deducible from P.
Reference :
Sterling,Leon ,Shapiro, Ehud. The art of prolog.1999.Massachussets Of Technology.
Recent Comments