Logic Programming

Logic Programming:

Logic Programming Logic programming Candidates should be familiar with the concept of logic programming for declaring logical relationships.

Scenario 1. Procedural Programming:

Scenario 1. Procedural Programming If teacher1=evil Then Msg box=sack teacher Else Msg box =keep teacher If teacher 2 =evil Then Etc etc Sequence of instructions. Selection If something is like This then do that. etc

Scenario 2. Declarative programming:

Scenario 2. Declarative programming Facts Teacher 1 = evil Teacher 2 = evil Teacher 3 =good Rules Evil teacher = sacked Good teacher = kept Getting something out of this sort of programming. Questions you could then ask: Should teacher 1 be sacked or kept? Should teacher 3 be sacked or kept?

Types of Languages:

Types of Languages Declarative –facts about people, objects and events and how they relate to each other Procedural –how to do things, use declarative knowledge to work things out –perhaps in a sequence COMPUTERS MAY BE PROGRAMMED WITH THESE TWO DIFFERENT KINDS OF KNOWLEDGE

Examples of High Level PROCEDURAL Languages include::

Examples of High Level PROCEDURAL Languages include: PASCAL COBOL FORTRAN PROLOG <<- This one is Declarative! Works in a different way Procedural languages have A sequence of instructions telling The machine what to do. The programmer has to Know exactly what steps Are needed to solve the Problem and what order, for Any given set of data. As an instruction is executed, Variables for the program Are modified using Assignment statements. Prolog =Declarative =Logic Programming Language =rules & facts Not sequence!

What is PRO LOG stand for?:

What is PRO LOG stand for? PRO GRAMMING IN LOG IC

Characteristics of this Logic Programming Language (PROLOG):

Characteristics of this Logic Programming Language (PROLOG) Instead of defining HOW a problem is solved (steps, sequence) the programmer states the facts and rules associated with the problem. What is a FACT/RULE? Something that is always unconditionally TRUE (is a FACT ) Something that is true depending on a given condition –(is a RULE )

More stuff about Logic Programming (PROLOG):

More stuff about Logic Programming (PROLOG) The order in which the rules and facts are stated is NOT important. The order in which the rules and facts are stated IS important in a __________________ language. DECLARATIVE

So how are programs executed?:

So how are programs executed? Executing a prolog program involves: STATING A GOAL to be achieved Allowing Prolog to determine whether the goal can be achieved (with the given facts and rules!)

Important Note::

Important Note: The route, or the steps or the sequence through the program does NOT have to be explicitly stated by the programmer. If one route doesn’t work….go back to the beginning and try another! SO…NO SET ROUTE at start!

How does Prolog do stuff then (without a route?):

How does Prolog do stuff then (without a route?) Prolog will select a possible route through a program and if that fails it will BACKTRACK to that point and try another route. This will continue until Goal is achieved or All routes have been tried (no more routes!)

What is the application of programming in PROLOG?:

What is the application of programming in PROLOG? Expert Systems They (above) embody the facts and rules about a particular field Of knowledge….such as oil prospecting, social security regulations Or medical diagnosis. In this sort of system, facts and rules are Described in the program to form the ‘expert knowledge’ and a user Can then QUERY the program to obtain answers to problems, Given that certain facts or conditions are true.

What is another application of programming in PROLOG?:

What is another application of programming in PROLOG? Processing of Natural Language You could also get a computer to try and understand other Languages like Mandarin or Greek or something. Each of these languages has its own syntax rules which can Be stated in the program to help the computer decide whether A group of words make a sentence and what it means! In other words Trying to get a Computer to understand Ordinary English!)

Another use:

Another use You could have a whole load of rules about a family…and thereby use prolog to determine information about relationships between members of a family. (this could be useful if you had a huge family…500 people geneology etc)

The “knowledge” (facts and rules) that have to be programmed is a representation of the family tree below and rules about relationships.:

The “knowledge” (facts and rules) that have to be programmed is a representation of the family tree below and rules about relationships. Dorothy m. Jack Liz John Bill m. Evelyn What facts can we Establish about this family Tree?

The “knowledge” (facts and rules) that have to be programmed is a representation of the family tree below and rules about relationships.:

The “knowledge” (facts and rules) that have to be programmed is a representation of the family tree below and rules about relationships. Dorothy m. Jack Liz John Bill m. Evelyn What facts can we Establish about this family Tree? Jack, Bill and John are Male The others are female! Dorothy is parent of Evelyn Jack is parent of Evelyn Evelyn is parent of John Bill is parent of John etc

The “knowledge” (facts and rules) that have to be programmed is a representation of the family tree below and rules about relationships.:

The “knowledge” (facts and rules) that have to be programmed is a representation of the family tree below and rules about relationships. Dorothy m. Jack Liz John Bill m. Evelyn What Rules can we Establish? Facts Male(jack). Male(john). Etc Female(grace). Female(evelyn). Etc Parent(dorothy, jack). Parent(jack, evelyn). Parent (evelyn, john). Spot the mistake (the fact that is not a fact!)

The “knowledge” (facts and rules) that have to be programmed is a representation of the family tree below and rules about relationships.:

The “knowledge” (facts and rules) that have to be programmed is a representation of the family tree below and rules about relationships. Dorothy m. Jack Liz John Bill m. Evelyn What Rules can we Establish? How do we know if someone Is someone’s mother? Or if M is the mother Of X?

The “knowledge” (facts and rules) that have to be programmed is a representation of the family tree below and rules about relationships.:

The “knowledge” (facts and rules) that have to be programmed is a representation of the family tree below and rules about relationships. Dorothy m. Jack Liz John Bill m. Evelyn What Rules can we Establish? M is the mother of X if M is a parent of X and M is a Female! Mother (M,X) :- Parent (M,X), Female (M).

The “knowledge” (facts and rules) that have to be programmed is a representation of the family tree below and rules about relationships.:

The “knowledge” (facts and rules) that have to be programmed is a representation of the family tree below and rules about relationships. Dorothy m. Jack Liz John Bill m. Evelyn What Rules can we Establish for Grandparent? Mother (M,X) :- Parent (M,X), Female (M).

The “knowledge” (facts and rules) that have to be programmed is a representation of the family tree below and rules about relationships.:

The “knowledge” (facts and rules) that have to be programmed is a representation of the family tree below and rules about relationships. Dorothy m. Jack Liz John Bill m. Evelyn What Rules can we Establish for Grandparent? G is the Grandparent of X if G is parent of Y and Y is parent of X Grandparent (G,X) Parent (G,P) Parent (P,X)

The “knowledge” (facts and rules) that have to be programmed is a representation of the family tree below and rules about relationships.:

The “knowledge” (facts and rules) that have to be programmed is a representation of the family tree below and rules about relationships. What Rules can we establish For Brother? Dorothy m. Jack Liz John Bill m. Evelyn

The “knowledge” (facts and rules) that have to be programmed is a representation of the family tree below and rules about relationships.:

The “knowledge” (facts and rules) that have to be programmed is a representation of the family tree below and rules about relationships. Dorothy m. Jack Liz John Bill m. Evelyn What Rules can we establish For Brother? X is a brother of Y if P is a parent of X P is a parent of Y and X is a male and X is not his own brother Brother (x, y):- Parent (z,y) Male(x), Not(x=y).

Now that rules and facts are set up.:

Now that rules and facts are set up. Queries can now be made to find out relationships..

A user may want to know..:

A user may want to know.. Does Liz have a brother Is Liz single? Is Liz mentally unstable? Is Liz a Grandparent?

Does Liz have a brother?:

Does Liz have a brother? The query is typed in at the ? prompt. ?-brother (x,liz). The answer is X= John Dorothy m. Jack Liz John Bill m. Evelyn

Who is the mother of Evelyn?:

Who is the mother of Evelyn? The query is typed in at the ? prompt. ?-mother (x,evelyn). The answer is X= Dorothy Dorothy m. Jack Liz John Bill m. Evelyn

Who is the father of john?:

Who is the father of john? The query is typed in at the ? prompt. ………………………… The answer is Dorothy m. Jack Liz John Bill m. Evelyn ?-father(who, John) Who=Bill

Who is the brother of John?:

Who is the brother of John? The query is typed in at the ? prompt. …………………………… The answer is Dorothy m. Jack Liz John Bill m. Evelyn ?-brother(who, John). No Cos John has no brother!

So how do you visualise Prolog?:

So how do you visualise Prolog? It doesn’t consist of INSTRUCTIONS per se….but of a collection of facts and rules . It can be thought of as a database….here some data items are stored directly as facts and other data items can be deduced by applying rules. These items are acted upon by the PROLOG INTERPRETER in response to goals that you give it

What is a fact?:

What is a fact? Something that is true. Something that is conditionally true Something that is unconditionally true There is a God There is no God There maybe a God

What is the definition of a FACT in Prolog?:

What is the definition of a FACT in Prolog? A fact consists of A PREDICATE and ZERO, ONE or MORE arguments.

Fact consists of a predicate, and 0,1 or more arguments.:

Fact consists of a predicate, and 0,1 or more arguments. Eg. Carnivore(lion). Isa (table, furniture) Animal(reptile, large, crocodile) ? Predicate names must be atoms…but arguments can consist of a variety Of data types. PROLOG recognises data types without you having to Declare them at the top of the program. The most common data types are: Integers: only digits Reals: digits and a decimal point Atoms: start with a LOWERCASE letter. Contain numbers, letters and underscore Strings: any characters enclosed in single quotes Variables: start with an UPPERCASE letter

Would the names Jack, Dorothy etc…start with UPPER CASE Or LOWER CASE in Prolog?:

Would the names Jack, Dorothy etc…start with UPPER CASE Or LOWER CASE in Prolog? Variables =Uppercase Atoms –lower case

Slide 35:

Facts Male(jack). Male(john). Etc Female(grace). Female(evelyn). Etc Parent(dorothy, jack). Parent(jack, evelyn). Parent (evelyn, john). Each line (clause) ends With a full stop. Names like jack and dorothy etc are written with Lower case letters….because they are atoms not variables.

Predicates such as “CARNIVORE”:

Predicates such as “CARNIVORE” Are programmer defined predicates Prolog also has built in predicates such as NOT (to reverse anything given as its argument) and LISTING (to write out the whole of the current database)

Things in Prolog and what they mean:

Things in Prolog and what they mean :- IF , logical AND ; logical OR =tests whether two things are identically the same - anonymous variable

Entering items in a Prolog Database:

Entering items in a Prolog Database

What is Backtracking?:

What is Backtracking? Is the basis of the so called “logic programming languages” such as icon, planner and prolog. More here - http://en.wikipedia.org/wiki/Backtracking

What is instantiation?:

What is instantiation? Creating an instance of a class That instance will have all the properties of the original class Aristotle argued that

BNF – Backus Naur form:

BNF – Backus Naur form