We first meet propositional logic, an algebra whose original purpose, dating back to Aristotle, was to model reasoning. In more recent times, this algebra, like many algebras, has proved useful as a design tool. For example, we can see how propositional logic can be used in computer circuit design. A third use of logic is as a data model for programming languages and systems, such as the language Prolog. Many systems for reasoning by computer, including theorem provers, program verifiers, and applications in the field of artificial intelligence, have been implemented in logic-based programming languages. These languages generally use "predicate logic," a more powerful form of logic that extends the capabilities of propositional logic.
Propositional logic is a mathematical model that allows us to reason about the truth or falsehood of logical expressions. For example, we may replace a statement like a < b by a single symbol p, replace a >= b by the expression NOT p, and replace c == d by the symbol q. The symbols p and q are called propositional variables, since they can stand for any "proposition," that is, any statement that can have one of the truth values, true or false.
We now turn our attention to a generalization of propositional logic, called "predicate," or "first-order," logic. Predicates are functions of zero or more variables that return Boolean values. Thus predicates can be true sometimes and false sometimes, depending on the values of their arguments. For example, we shall find in predicate logic atomic operands such as csg(C, S, G). Here, csg is the predicate name, and C, S, and G are arguments. We can think of this expression as a representation in logic of the database relation Course-Student-Grade. It returns the value TRUE whenever the values of C, S, and G are such that student S got grade G in course C, and it returns FALSE otherwise.
Using predicates as atomic operands, instead of propositional variables, gives us a more powerful language than expressions involving only propositions. In fact, predicate logic is expressive enough to form the basis of a number of useful programming languages, such as Prolog (which stands for "Programming in logic") and the language SQL. Predicate logic is also used in reasoning systems or "expert" systems, such as automatic medical diagnosis programs and theorem-proving programs.
Prolog expressions are comprised of the following truth-functional symbols, which have the same interpretation as in the predicate calculus.
English Predicate Calculus PROLOG and ^ , or v ; if --> :- not ~ not
Variables begin with an uppercase letter. Predicate names, function names, and the names for objects must begin with a lowercase letter. Rules for forming names are the same as for the predicate calculus.
mother_of
male
female
greater_than
socrates
A fact is a predicate expression that makes a declarative statement about the problem domain. Whenever a variable occurs in a Prolog expression, it is assumed to be universally quantified. Note that all Prolog sentences must end with a period.
likes(john, susie). /* John likes Susie */ likes(X, susie). /* Everyone likes Susie */ likes(john, Y). /* John likes everybody */ likes(john, Y), likes(Y, john). /* John likes everybody and everybody likes John */ likes(john, susie); likes(john,mary). /* John likes Susie or John likes Mary */ not(likes(john,pizza)). /* John does not like pizza */ likes(john,susie) :- likes(john,mary)./* John likes Susie if John likes Mary.
A rule is a predicate expression that uses logical implication (:-) to describe a relationship among facts. Thus a Prolog rule takes the form
left_hand_side :- right_hand_side .
This sentence is interpreted as: left_hand_side if right_hand_side. The left_hand_side is restricted to a single, positive, literal, which means it must consist of a positive atomic expression. It cannot be negated and it cannot contain logical connectives.
This notation is known as a Horn clause. In Horn clause logic, the left hand side of the clause is the conclusion, and must be a single positive literal. The right hand side contains the premises. The Horn clause calculus is equivalent to the first-order predicate calculus.
Examples of valid rules:
friends(X,Y) :- likes(X,Y),likes(Y,X). /* X and Y are friends if they like each other */ hates(X,Y) :- not(likes(X,Y)). /* X hates Y if X does not like Y. */ enemies(X,Y) :- not(likes(X,Y)),not(likes(Y,X)). /* X and Y are enemies if they don't like each other */
Examples of invalid rules:
left_of(X,Y) :- right_of(Y,X) /* Missing a period */ likes(X,Y),likes(Y,X) :- friends(X,Y). /* LHS is not a single literal */ not(likes(X,Y)) :- hates(X,Y). /* LHS cannot be negated */
The Prolog interpreter responds to queries about the facts and rules represented in its database. The database is assumed to represent what is true about a particular problem domain. In making a query you are asking Prolog whether it can prove that your query is true. If so, it answers "yes" and displays any variable bindings that it made in coming up with the answer. If it fails to prove the query true, it answers "No".
Whenever you run the Prolog interpreter, it will prompt you with ?-. For example, suppose our database consists of the following facts about a fictitious family.
father_of(joe,paul). father_of(joe,mary). mother_of(jane,paul). mother_of(jane,mary). male(paul). male(joe). female(mary). female(jane).
We get the following results when we make queries about this database. (I've added comments, enclosed in /*..*/, to interpret each query.)
Script started on Wed Oct 01 14:29:32 2003 sh-2.05b$ gprolog GNU Prolog 1.2.16 By Daniel Diaz Copyright (C) 1999-2002 Daniel Diaz | ?- ['family.pl']. compiling /home/ram/public_html/cpsc352/prolog/family.pl for byte code... /home/ram/public_html/cpsc352/prolog/family.pl compiled, 9 lines read - 999 bytes written, 94 ms (10 ms) yes | ?- listing. mother_of(jane, paul). mother_of(jane, mary). male(paul). male(joe). female(mary). female(jane). father_of(joe, paul). father_of(joe, mary). (10 ms) yes | ?- father_of(joe,paul). true ? yes | ?- father_of(paul,mary). no | ?- father_of(X,mary). X = joe yes | ?- Prolog interruption (h for help) ? h a abort b break c continue e exit d debug t trace h/? help Prolog interruption (h for help) ? e sh-2.05b$ exit script done on Wed Oct 01 14:30:50 2003
Closed World Assumption. The Prolog interpreter assumes that the database is a closed world -- that is, if it cannot prove something is true, it assumes that it is false. This is also known as negation as failure -- that is, something is false if PROLOG cannot prove it true given the facts and rules in its database. In this case, in may well be (in the real world), that Paul is the father of Mary, but since this cannot be proved given the current family database, Prolog concludes that it is false. So PROLOG assumes that its database contains complete knowledge of the domain it is being asked about.
In responding to queries, the Prolog interpreter uses a backtracking search, similar to the one we study in Chapter 3 of Luger. To see how this works, let's add the following rules to our database:
parent_of(X,Y) :- father_of(X,Y). /* Rule #1 */ parent_of(X,Y) :- mother_of(X,Y). /* Rule #2 */
And let's trace how PROLOG would process the query. Suppose the facts and rules of this database are arranged in the order in which they were input. This trace assumes you know how unification works.
?- parent_of(jane,mary).
parent_of(jane,mary) /* Prolog starts here and searches
for a matching fact or rule. */
parent_of(X,Y) /* Prolog unifies the query with the rule #1
using {jane/X, mary/Y}, giving
parent_of(jane,mary) :- father_of(jane,mary) */
father_of(jane,mary) /* Prolog replaces LHS with RHS and searches. */
/* This fails to match father_of(joe,paul) and
and father_of(joe,mary), so this FAILS. */
/* Prolog BACKTRACKS to the other rule #2 and
unifies with {jane/X, mary/Y}, so it matches
parent_of(jane,mary) :- mother_of(jane,mary) */
mother_of(jane,mary) /* Prolog replaces LHS with RHS and searches. */
YES. /* Prolog finds a match with a literal and so succeeds.
Here's a trace of this query using Prolog's trace predicate:
| ?- trace,parent_of(jane,mary).
{The debugger will first creep -- showing everything (trace)}
1 1 Call: parent_of(jane,mary) ?
2 2 Call: father_of(jane,mary) ?
2 2 Fail: father_of(jane,mary) ?
2 2 Call: mother_of(jane,mary) ?
2 2 Exit: mother_of(jane,mary) ?
1 1 Exit: parent_of(jane,mary) ?
yes
{trace}
| ?-
father_of(joe,paul). father_of(joe,mary). father_of(joe,hope). mother_of(jane,paul). mother_of(jane,mary). mother_of(jane,hope). male(paul). male(joe). male(ralph). male(X) :- father_of(X,Y). female(mary). female(jane). female(hope). son_of(X,Y) :- father_of(Y,X),male(X). son_of(X,Y) :- mother_of(Y,X),male(X). daughter_of(X,Y) :- father_of(Y,X),female(X). daughter_of(X,Y) :- mother_of(Y,X),female(X). sibling_of(X,Y) :- !,father_of(Z,X),father_of(Z,Y),X\=Y. sibling_of(X,Y) :- !,mother_of(Z,X),mother_of(Z,Y),X\=Y.
son_of(X,Y) daughter_of(X,Y) sibling_of(X,Y) brother_of(X,Y) sister_of(X,Y)
Here's a list of commands that will be useful in loading and running PROLOG programs. The best way to use a Prolog environment is to save your database in a regular ASCII text file, named with the suffix pro or pl (but note that Perl files also use the pl suffix). Then you repeatedly load the file into the interpreter and run queries.
A complete listing of the GPROLOG (Gnu Prolog) commands will be provided as a handout.
^D /* Control-D exits Prolog at the query prompt. */
^C /* Control-C interrupts any query and puts Prolog in interrupt mode:
| ?-
Prolog interruption (h for help) ? h
a abort b break
c continue e exit
d debug t trace
h/? help
Prolog interruption (h for help) ? e /* We exit PROLOG */
/* A PROLOG program can dynamically modify its database */
/* Or you can add a predicate from the query prompt. */
asserta(P). /* Adds P to the front of all matching P's */
assertz(P). /* Adds P to the end of all matching P's */
retract(P). /* Removes P from the database: -- e.g., (retract(male(joe)).
/* A PROLOG database can be loaded from a preexisting ascii file: */
consult('filename'). /* PROLOG reads the database into the interpreter reporting any */
/* syntax errors. If you have errors, fix then and consult again. */
/* NOTE. Some versions of PROLOG will create duplicate facts */
/* and rules if you consult() the same file more than once. */
/* Some versions, but not GPROLOG, have a reconsult() predicate */
reconsult('filename'). /* Reconsult the named file. Don't duplicate existing predicates. */
['file1','file2']. /* List notation can be used to load more than one file at once. */
listing. /* This predicate provides a listing of the database. */
listing(P). /* Provides a listing of just the predicate P. */
trace /* Turns on Prolog's trace utility. This dumps everything. */
notrace. /* Turns off the trace utility. */
spy(P). /* This just traces the predicate P */
nospy(P). /* Removes the spy point on P */
Prolog program is simply based on predicate logic known as Horn clause. In prolog, we compose the program using facts and rules and we pose a query on query prompt about the facts and rules we inserted.
Written as : h :- b ( where b is p1, p2, p3, .., pn and ' :- ' operator is read as 'if' )
Read as : h is true if b is true. In other words h is true if all the predicates on right side are true.
Syntax : Start the statement (relationship or Object) with lowercase letters and end with '.' period (full stop) - for all facts, rules and queries.
Examples :
Headless Horn Clauses :
son(john). // Read as : john is son
son(john,mary). // Read as : john is son of mary
Headed Horn Clauses :
boy(john) :- son(john,mary). // Read as : john is a boy if he is son of mary
Examples: logic_programming. // Read as : logic programming
music_student(john). // Read as : john is a music student
likes('John', car(bmw)) // Read as : john likes bmw car
gives(john, chocolate, jane). // Read as : john gives chocolate to jane
Examples: If we want to say that john and jane are friends if john likes jane and jane likes john. Then in prolog this friends rule can be written as,
friends(john,jane) :- likes(john,jane), likes(jane,john).
Examples: Rules with variables.
likes(john, X) :- car(X). // Read as : john likes X if X is a car.
friends(X, Y) :- likes(X, Y), likes(Y, X). // Read as : X and Y are friends if X likes Y and Y likes X. OR Two people are friends if they like each other.
Example : For below Prolog Program, we will ask two queries about the facts we have provided.
Program :
likes(alice,john). // Read as : alice likes john
likes(john,mary). // Read as : john likes mary
Queries : ?- likes(alice,john). // Read as :- Does alice like john?
true.
?- likes(alice,mary). // Read as :- Does alice like mary?
false.
In above example, text in red color is what user types and queries are terminated by the full stop at the end.
So, when we enter ?- likes(alice,john). interpreter will answer yes or true since it can find the match for the given query.
But when we ask ?- likes(alice,mary). then it would say no or false.
More About Facts, Rules, Queries
Examples : Who, What, X, Y, ABC, Abc, A12
_who, _x, _variable, _abc, _Abc, _12
But Prolog also has a facility of using an anonymous variable i.e. only _ (an underscore) to which no values are bound. It is just a don't-care variable. Using this anonymous variable we are just defining it's position. For an instance, when we write this fact in Prolog - likes(john,_). we are declaring that john likes something, but that something is not actually of any use for the rest of the program. Another example: when we write this query in Prolog ?- gives(john, chocolate, _). we are only interested in john giving the chocolate, but who - we indicate that as an anonymous variable. But keep in mind this difference - 'John' is an atom and John is a variable. Anything you write between single quotes, becomes an atom whether the text starts with uppercase, underscore or lowercase. Below is the example of prolog variable representation -
| Prolog Program Fact: gives(john, chocolate, jane). |
Prolog Query & Answer : ?- gives(john, chocolate,Who). Who = jane. |
Prolog Query & Answer : ?- gives(john, chocolate, _). true. |
More About Prolog Programming Basics
% =================================================================
% == ==
% == An Introduction to ARTIFICIAL INTELLIGENCE ==
% == Janet Finlay and Alan Dix ==
% == UCL Press, 1996 ==
% == ==
% =================================================================
% == ==
% == chapter 2, pages 37-38: certainty factors ==
% == ==
% == Prolog example, Alan Dix, August 1996 ==
% == ==
% =================================================================
mb(foggy,'air is moist',0.5).
md(foggy,'air is moist',0.1).
mb(foggy,'poor visibility',0.7).
md(foggy,'poor visibility',0.0).
% The predicate cf(H,E,CF) calculates the certainty factor of
% an hypothesis H given a single evidence E
cf(H,E,CF) :-
mb(H,E,MB),
md(H,E,MD),
CF is MB-MD.
% There are two versions of the predicates.
% The first version of each mb0 and md0 uses the formulae
% to calculate the combined measure of belief/disbelief
% The second version of each mb and md, adds in the extra
% rule which says that each is 0 if the other is 1.
% If we coded this with a single predicate, then
mb0(H,E1,E2,MB) :-
mb(H,E1,MB1),
mb(H,E2,MB2),
MB is MB1 + MB2*(1-MB1).
md0(H,E1,E2,MD) :-
md(H,E1,MD1),
md(H,E2,MD2),
MD is MD1 + MD2*(1-MD1).
mb(H,E1,E2,0) :- md0(H,E1,E2,1).
mb(H,E1,E2,MB) :- not md0(H,E1,E2,1), mb0(H,E1,E2,MB).
md(H,E1,E2,0) :- mb0(H,E1,E2,1).
md(H,E1,E2,MD) :- not mb0(H,E1,E2,1), md0(H,E1,E2,MD).
% Note the trick here, mb/3 are the facts and mb/4 is
% the calculation. We are usingh the same predicate name
% with different numbers of arguments.
% the certainty factor calculations are identical to cf/3
cf(H,E1,E2,CF) :-
mb(H,E1,E2,MB),
md(H,E1,E2,MD),
CF is MB-MD.
% RUNNING THIS CODE
%
% First of all check the certainty factor calculations for
% single evidences:
% cf(foggy,'air is moist',CF).
% cf(foggy,'poor visibility',CF).
% then try to combine evidence:
% cf(foggy,'air is moist','poor visibility',CF).
%
% You can also examine the calculated measures of belief and
% disbelief given the combined evidence:
% mb(foggy,'air is moist','poor visibility',MB).
% md(foggy,'air is moist','poor visibility',MD).
%
% MORE EVIDENCE
%
% We can do the same for a whole list of evidences
% Obviously more types of evidence would need to be included
% In the database for this to be useful!
mb0_list(H,[],0).
mb0_list(H,[E|Rest],MB) :-
mb(H,E,MBe),
mb_list(H,Rest,MBrest),
MB is MBe + MBrest*(1-MBe).
md0_list(H,[],0).
md0_list(H,[E|Rest],MD) :-
md(H,E,MDe),
md_list(H,Rest,MDrest),
MD is MDe + MDrest*(1-MDe).
mb_list(H,Elist,0) :- md0_list(H,Elist,1).
mb_list(H,Elist,MB) :- not md0_list(H,Elist,1), mb0_list(H,Elist,MB).
md_list(H,Elist,0) :- mb0_list(H,Elist,1).
md_list(H,Elist,MD) :- not mb0_list(H,Elist,1), md0_list(H,Elist,MD).
cf_list(H,Elist,CF) :-
mb_list(H,Elist,MB),
md_list(H,Elist,MD),
CF is MB-MD.
%
% check with a few examples that 'cf_list(H,[E1,E2],MB)' gives the same
% answer as 'cf(H,E1,H2,MB)'
%% Constraint-Based Reasoning (a.k.a. Constraint Satisfaction or Constraint Programming) %% %% Below is the set of variables; for example, think of "a" as a variable that has possible values 1, 2, 30. %% (Be careful to keep the notion of "variable" in Prolog and "variable" in constraint-based reasoning distinct.) %% Now impose a set of constraints on all variables and let Prolog find the possible solutions, given the constraints. %% Prolog uses a method called "unification and backtracking" to find all possible solutions. Very powerful stuff. %% Load this program, and copy the set of constraints after the ?- prompt. How many solutions are there? %% The first four clauses unify values to X, Y, Z, N, and S one at a time. The next four clauses are the constraints. nl is newline. %% Once Prolog makes it through all constraints, it has found a solution, and it then backtracks to try further unifications until it has exhausted all possible values that satisfy the constraints. %% Once Prolog finds a solution, enter the operator ";" to get other solutions if they exist. This makes sense because the meaning of ";" is or. %% %% The next line is the set of constraints. Copy and paste this line after the Prolog prompt ?- %% a(X), b(Y), c(Z), d(N,S), X > 1, Y < 20, X < Y, Z = green, S = large, nl. a(1). a(2). a(30). b(10). b(15). b(20). c(red). c(blue). c(green). d(jack, large). d(tom, medium). d(jane, medium). d(harry, small).
In Prolog, a procedure is
either static or
dynamic. A static procedure is one whose facts/rules are predefined at
the start of execution, and do not change during execution. Normally,
the facts/rules will be in a file of Prolog code which will be loaded
during the Prolog session. Sometimes, you might want to add extra
facts (or maybe even extra rules) to the procedure, during execution
of a Prolog query, usingassert/asserta/assertz",
or maybe remove facts/rules using retract/retractall.
To do this, you must declare the procedure to be dynamic.
You can declare a procedure to be dynamic by including in your code
(normally adjacent to the facts/rules for that procedure) a
suitable dynamic directive. Example - suppose
you have a procedure called likes, with arity 2,
and you have a "starter set" of facts/rules in your Prolog program,
but you want to infer extra facts
about likes during execution, and add them to
the data base so that they don't need to be recomputed each time they
are used. [You would normally only do this - add the new facts to the
database - if the extra facts were slow to compute.] You need to
declare likes (with arity 2) to be dynamic. You
do this as follows:
:- dynamic likes/2.
[By the way, notice that this leaves open the possibility that a
different version of likes (with arity 3, say)
might not be dynamic.]