Prolog Demo Lecture Recording Below

Logic programming is a programming methodology very different from imperative programming (i.e. Procedural/Structured) as it is based on formal mathematical logic and set theory. Prolog programs are expressed using symbolic logic and the logical inferencing process (Inference Engine) performs the execution. In other words, we define a relation by stating the n-tuples of objects that satisfy the relation and add them to the Knowledge Base.

You will note right away that the syntax and semantics of logic programs bear little resemblance to imperative programs as logic programs are declared rather than sequenced (no Algorithm). Facts and rules are input or defined for the program and queries are posed to database stated in relational calculus. Put another way, we specify desired results and leave the detailed procedures for producing results to the inferencing engine.

There are many evolving and emerging uses for logic programming and these include: Expert Systems, Artificial Intelligence, Natural Language Processing, Education and Tutoring Systems, RDBMS

Predicate Calculus

Predicate calculus is the basis of formal logic and symbolic logic programming. As a result the programming environment has 3 basic requirements: 1) the ability to express propositions, 2) the ability to express relationships between propositions, and 3) the ability to describe how new propositions may be inferred.

Syntax

The classification of Prolog data objects can be recognized by their syntactic form so no type declarations needed for Prolog to recognize type of object.

Variables begin with upper case letter and may be constructed from strings of letters, digits and underscore character.

atoms start with lower case letters and may be constructed from strings of letters, digits and underscore character. Note we can enclose strings of characters in single quotes if we desire an atom which begins with a capital letter – e.g. ‘Pi’ is an atom and not a variable

Numbers – Integer and real numbers are supported and the range of integers is limited to the range supported by particular architecture

Comment % to end of line – or paragraph text crossing enclosed in /* */

End Clauses with a period (.)

Semantics, Programming & Knowledge Base Creation

Logic Programming is done by defining Objects and Relations and again, they are not sequenced so order is irrelevant. We define a relation, by stating the n-tuples of objects that satisfy the relation and add them to the Knowledge Base.

Relations such as parent, offspring and mother may be illustrated with graphs where nodes correspond to objects (e.g. arguments of relations) and the arcs between notes correspond to binary relations. Unary relations are indicated in diagrams by marking corresponding objects with name of relation. Defined relations are represented by dashed arcs and if relations shown by solid arcs hold then relations shown by dashed arc holds.

An axiom is a fact (axiom is a self evident truth) and facts like parent(tom, liz) are always true (unconditionally true).

We may change the order of the two requirements and the logical meaning remains the same

Prolog program consists of clauses, each clause terminates with a full stop (i.e. a period)

Arguments of relations may be atoms (concrete objects) or Variables (general objects)

Rules facilitate program extension/inference and specify things that are true by their own definition (i.e. a tautology) or may be true if some condition is satisfied. Rules consist of two parts:

condition (right hand side of rule) that forms the body of the clause and is also known as the antecedent

conclusion ( left-hand side of rule) that forms the head of the clause and is also known as the consequent

If the body or antecedent evaluates to true (i.e. the variables can be instantiated to satisfy the body clauses), then the logical consequent or head evaluates to true and the variables are are permanently instantiated or Unified in the head.

Code Convention: we write the head of the clause on a separate line followed by each goal of the body on a separately indented line

Running Prolog (Windows)

SWI Prolog download is here: http://www.swi.psy.uva.nl/projects/SWI-Prolog/download.html.

Start menu => SWI Prolog

Note prompt of ?- /* Indicates Prolog system is awaiting information as Prolog is interactive system awaiting facts, rules, queries */

Note availability of help(Topic) and apropos(Topic) (e.g. ?-apropos(consult).)

?- pwd. % gives present working directory

?- chdir(‘a:’). /* My directory – chdir(‘c:/HVCC Courses/CISS 100/prolog/intro’). Note only forward slashes regardless of OS */

?- consult(‘01person.pl’). /*consults (e.g. loads and compiles) 01person.pl from present working directory – note no space between functor and arguments (also called parameters and terminated with a period – also note consult is available in the graphical menu on Windows systems*/

?- assert(parent(tom,bob)). /* adds single clause to database that indicates tom isa parent of bob – also see assert or assertz by using ?- apropos(assert) */

. % the period ends a clause and stops the stream of solutions

, % the comma is conjunction -> AND

; % the semi-colon gives us more responses and is used for disjunction -> OR

Ctrl-C will break present execution

trace % turns on trace mechanism – notrace turns it off

During the course of computation, variables are substituted for/matched with other objects and the variable becomes instantiated. If this is done in a rule, if the antecedent variables can be instantiated, the goal/consequent can be satisfied and the instantiation is Unified (made permanent).

Now please read the following for a use-case introduction to Prolog noting the necessary files are located below should you wish to consult and run them rather than input them line by line: http://homepages.abdn.ac.uk/f.guerin/pages/teaching/CS1015/abdn.only/bratko.pdf

Consult files for the chapter above and the Prolog Reference Manuals for your pleasure reading – :). Note you will have to remove the .txt extension from the files below (I needed .txt files to render them in a browser) leaving just the .pl prolog extension which is what SWI-Prolog expects.

Prolog Manuals

Prolog files for demo below:

[listyofiles folder=”wp-content/uploads/prolog-intro” options=”table,filesize,icon,new_window”]

Advanced Prolog & Theory

As previously introduced, Prolog is based on formal logic and mathematics (predicate calculus) and with this basis, the fundamental axioms of numbers and set theory assumed to be true. Theorems are additional propositions which may be inferred from initial set.

Closed World Assumption – Prolog is based on a closed world assumption where Prolog only reports truths which may be proved using its database. In other words, Prolog has no knowledge beyond what is contained in its database and this may be misleading. As an example, if there is insufficient information Prolog will report “False”.

Theorem Proving – 2 Approaches

Forward Chaining – this is bottom up resolution where the system begins with facts/rules and attempts to find a sequence of matching propositions that lead to goal. This works well when the number of possible answers is large as backward chaining introduced below would require a large number of matches to get thae answer.

Backward Chaining – this is top down resolution where the system begins with a goal and attempts to find set of matching propositions that lead to set of facts in database. This is Prolog’s mechanism and works well when there is reasonably small set of candidate answers.

Propositions are logical statements that may or may not be true and they consist of objects and relationships of objects to each other. These propositions are checked (through inference) to determine validity. Propositions may contain:

Facts – are defined to be true

Queries – a query is a theorem and consists of a sequence of one or more goals (i.e. goal may have subgoals) and its truth is determined through matching and inference engine. To prove a goal is true, the inference engine must find a chain of inference rules and facts (axioms & tautologies) in the database to establish the validity of the goal. The steps that Prolog follows is known as the Proof Sequence.

Let’s present this in another way: Prolog tries to satisfy all goals/subgoals by proving they are true. A goal is true (satisfiable) if it logically follows from facts and rules of program. If the query contains variables, prolog finds instantiations of particular objects to achieve goals. If conclusion proved, instantiated variables are shown whereas if the conclusion can not be proved, prolog returns false.

Matching is the process of proving goals/subgoals through proposition matching (e.g. checking facts and instantiating variables). Proving a subgoal/goal is called satisfying the subgoal/goal.

Procedure is a set of clauses about logically related relations.

Proof Sequence is determined in inverse order (backward chaining) starting with the goal.

Variables assumed to be universally quantified (read as ‘FOR ALL’ ?) or existentially quantified ( read as ‘THERE EXISTS’ ?) if the variable appears only in body. Example:

hasachild(X) :- parent(X, Y) %may be read in two ways

1. For all X and Y, If X is a parent of Y then X has a child (you may think of this as beginning with the body/antecedent)

2. For all X, X has a child if there exists a Y such that (st.) X is a parent of Y (you may think of this as beginning with the goal/consequent)

Recursion – Recursive programming is fundamental to Prolog programming and is required to solve complex tasks.

Under Construction… this is my scratch paper 🙂

Logic Programming (PROLOG) Advantages

Prolog’s ability to work out its own procedural details considered an important advantage as procedural programming requires programmers to specify the solution algorithm. This encourages programmers to consider the declarative meaning of programs independently of procedural meaning.

A variable is a symbol that may represent different objects at different times. This is much closer to variable in mathematical formalism as it is not associated with memory cell in contrast to imperative/procedural programming languages

ATOMIC PROPOSITION

Simplest proposition consisting of compound terms

COMPOUND TERM

One element of mathematical relation

Written in form that has appearance of mathematical function notation

Mathematical function is mapping

Represented as either

an expression

a table

a list of tuples

Composed of two parts

FUNCTOR function symbol that names the relation

ordered list of parameters

referred to as tuples

COMPOUND PPROPOSITION

2 or more atomic propositions

Connected by logical connectors for operators

(Same manner as constructing logic expressions in imperative languages)

LOGICAL CONNECTORS LISTED IN ORDER OF PRECEDENCE

Quantifiers ?,?

Negation ¬

Conjunction ?

Disjunction ?

Equivalence ?

Implication ?

Variables appear in propositions only when introduced by quantifiers

2 quantifiers exist in predicate calculus

Scope extends to all attached propositions and may be extended with parentheses

UNIVERSAL (?X.P) meaning for all X, P is true

EXISTENTIAL (?X.P) meaning there exists a value for X to make P true

A period between X and P syntactically separates variable from proposition

EXAMPLES

?X.(woman(X) ? human(X))

States for any value X, if X is a woman, X is human

?X.(mother(mary,X) ? male(X))

states there exists a value X such that Mary is mother of X

and X is male

CLAUSAL FORM

There are many different ways of stating propositions that have same meaning

This could possibly lead to redundancy

Not a problem for logicians but it is a problem for automated/computerized system

Proposition in clausal form as following general syntax

B1 ? B2 ? …. ? Bn ? A1 ? A2 ? …? An

A’s and B’s are terms

If all A’s are true then at least 1 B is true

Note the similarity to prolog semantics

SEMANTICS

Existential quantifiers are not required

Universal quantifiers are implicit in variables in atomic propositions

No operators other than conjunction/disjunction required

(they also need not appear in order above)

all predicate calculus propositions may be algorithmically converted to clausal form

ANTECEDENT

Right hand side of clausal form proposition

CONSEQUENT

Left-hand side of clausal form

Consequence of antecedent

THEOREM PROVING

RESOLUTION

Inference rule that allows deferred propositions to be computed from given propositions

Provides method for automatic theorem proving

Devised/developed to be applied to propositions in clausal form

Allows discovery of new theorems inferred from known axioms and theorems

EXAMPLE and EXPLANATION

P1 ? P2

Q1 ? Q2

States P2 implies P1 and Q2 implies Q1

Suppose Q1 is equivalent to P2

If Q2 is true then Q1 and P2 are true and truth of P1 may be inferred

(now we know basis of axiomatic semantics)

SEMANTICS/MECHANICS

Terms of left sides of two propositions ANDed together to make left side of new proposition

Same thing is done to get right side of new proposition

Terms that appear on both sides of new proposition removed from both sides

UNIFICATION

Process of determining useful values for variables

INSTANTIATION

Temporary assigning of values to variables to allow unification

Often variables instantiated with value that fails

(Fails to complete subsequent required matching)

This requires the variable to be unbound and the procedural mechanism to BACKTRACK

PROLOG AND LOGIC PROGRAMMING

PROLOG is declarative language (logic programming is declarative)

Program consists of declarations

Declarations are statements or propositions in symbolic logic

Adheres to strict Mathematical formalism

Given proposition may be concisely determined from statement itself

Logic programming has no side effects

Prolog is not procedural => describe form of result

imperative semantics requires

examination of local declarations

knowledge of scoping/referencing environment

execution trace to determine values of variables

PROLOG INFERENCING

BACKWARD CHAINING

Begins with goal and attempts to prove sub goals

Sub goal becomes new goal which in turn may be comprised of sub goals

Prolog uses left to right, depth first order of the evaluation to prove sub goals

One must be careful not to cause infinite loop

Programmer must be aware inferencing process

DEPTH-FIRST

Searches complete sequence of propositions

Completes first subgoal before working on others

note this is a recursive definition/description

prolog designers chose depth first because requires fewer computer resources

Prolog fails as a pure logical programming paradigm

Depth first search requires proper ordering of clauses

Definition: BREADTH-FIRST

Works on all sub goals in parallel

Requires substantial memory and computer resources

BACKTRACKING

When system fails to show truth of subgoal

System abandons subgoal it could not prove

Unbinds instantiated variables and backtracks to reconsider previous proven sub goals

Creates new instantiations and new traversal of tree

Time consuming process

PROOF by CONTRADICTION

Theorem ? propositions

negate theorem -> GOAL

prove theorem by finding inconsistency in propositions -> HYPOTHESES

May not be efficient

Resolution is finite process if set of propositions is finite

Time required to find inconsistency in large database may be huge (large # of propositions)

Simplify resolution process using HORN CLAUSES

HORN CLAUSES

Special kind of propositions

2 forms

single atomic proposition on left side

rules

empty left side

facts

left side of clausal form called the head

right side of clausal form called the body