First-Order Logic Examples

(1)

Home Page

Title Page

Contents

JJ II

J I

Page1of100

Go Back

Full Screen

CS206 ^{Lecture 08}

Logic Progamming

G. Sivakumar

Computer Science Department IIT Bombay

siva@iitb.ac.in

http://www.cse.iitb.ac.in/∼siva Thu, Jan 16, 2003

Plan for Lecture 8

First-Order Logic Examples

(2)

Home Page

Title Page

Contents

JJ II

J I

Page2of100

Go Back

Predicate Logic Semantics

Formal Treatment later in the course. First we will do the following.

• Informal Treatment

Translating from English to Logic Constructing models for Formulae

• Two Applications of Logic

Logic Programming (2-3 lectures) Equational Reasoning (2-3 lectures)

(3)

Home Page

Title Page

Contents

JJ II

J I

Page3of100

Go Back

From English to Logic

Consider the following statements.

• Every student has a faculty advisor.

• Every Indian Grandmaster has beaten some European Grandmaster.

• There exist innitely many Pythagorean triples.

• No two students got the same marks.

We have to choose

• Suitable domains (numbers, people, strings, ...)

• Suitable functions and predicates

• Use correct connectives

• Use correct quantiers

(4)

Home Page

Title Page

Contents

JJ II

J I

Page4of100

Go Back

Possible Solutions

• Every student has a faculty advisor.

∀x∃y(student(x)∧ f aculty(y) ∧ advisor(x, y))

• Every Indian Grandmaster has beaten some European Grandmaster.

∀x∃y(gm(x) ∧ gm(y) ∧ indian(x)...)

• There exist innitely many Pythagorean triples.

∀n∃i∃j∃k(i > n∧ i² = j² + k²)

• No two students got the same marks.

(5)

Home Page

Title Page

Contents

JJ II

J I

Page5of100

Go Back

From Logic Formula to Meaning

Consider the following formulae.

• ∀x∃y(P(x) → Q(x, y))

• (∀x∃yP(x, y)) → (∀y∃xP(x, y))

Can we make them mean true (or false) by choosing suitable Interpreta- tions?

Let us try domain of natural numbers.

(6)

Home Page

Title Page

Contents

JJ II

J I

Page6of100

Go Back

Possible Interpretations

∀x∃y(P(x) → Q(y)) can mean

• true

Domain of x, y is Natural Numbers P(x) means x is even

Q(x, y) means y > x and y is odd

• false

Domain of x, y is Natural Numbers P(x) means x is prime

Q(x, y) means y divides x and 2 ≤ y ≤ (x − 1)

(7)

Home Page

Title Page

Contents

JJ II

J I

Page7of100

Go Back

Logic Programming Paradigm

Consider a simple function like addition (plus) Functional View

Binary function Two inputs and one output.

Example:

plus(2,3) > 5, plus(1,4) > 5

Directionality is associated.

Given the two inputs, a program can compute the output.

(8)

Home Page

Title Page

Contents

JJ II

J I

Page8of100

Go Back

From Functions to Relations

Suppose we treat plus as a relation taking 3 arguments.

That is, we say

plus(2,3,5) is true because 2 + 3 = 5.

plus(2,3,4) is false because 2 + 3 6= 4.

and so on . . . .

A Logic Program for plus is one that somehow expresses for any three arguments X, Y, Z the truth value of plus(X,Y,Z).

Can be done using two clauses (facts and rules) as we will see later.

(9)

Home Page

Title Page

Contents

JJ II

J I

Page9of100

Go Back

Querying a Logic Program

Now we can ask the Logic program interpreter queries like:

?- plus(2,3,6).

?- plus(1,4,3).

?- plus(1,1,2).

and it will correctly answer yes or no.

Such queries which have no variables are called ground goals.

They do not seem to achieve much as it can only verify answers.

(10)

Home Page

Title Page

Contents

JJ II

J I

Page10of100

Go Back

Queries with Variables

Queries can also be of the form:

?- plus(2,3,X).

?- plus(2,4,Y).

where uppercase letters denote variables.

Now the interpreter will answer X = 5

for rst query and Y = 6

for second query.

This seems to be doing some computing. (Variables in queries are existentially quantied and we are solving for suitable values.)

But nothing new from imperative or functional programming yet.

(11)

Home Page

Title Page

Contents

JJ II

J I

Page11of100

Go Back

No Directionality!

But, what about goals like

?- plus(X,2,6).

?- plus(2,Y,7).

or even

?- plus(X,Y,5).

The interpreter will generate: X = 4 for rst query, and Y = 5 for second query, and many answers for the third query including

<X = 1, Y = 4>,

<X = 2, Y = 3>, ...

Question: What about a goal like plus(X,Y,Z)?

(12)

Home Page

Title Page

Contents

JJ II

J I

Page12of100

Go Back

History of Logic Programming

About 25 years old.

In 1970s in Marseilles, France the rst Prolog Interpreter was developed.

Robert Kowalski's famous slogan Algorithm = Logic + Control

For a subset of First-order Logic (Horn clauses) which was powerful enough to express most relations, the control to solve goals could be automated and implemented eciently!

(13)

Home Page

Title Page

Contents

JJ II

J I

Page13of100

Go Back

Successful Applications of Prolog

Articial Intelligence: Rule-based Systems:

• Expert System Shells

• British Nationality Act (used by UK immigration) Natural-Language Processing

Compilers: Prototyping and testing of compiler tools Databases: Deductive Data-bases (HornLog)

Japanese Fifth Generation Project.

(14)

Home Page

Title Page

Contents

JJ II

J I

Page14of100

Go Back

Drawbacks of Prolog

• Speed

• Programming in the Large (Modules)

• Type systems and Type Checking

• Debugging Tools

• Need for Extra-Logical Features More on these later in the course.

(15)

Home Page

Title Page

Contents

JJ II

J I

Page15of100

Go Back

Prolog Programming Model

The model for prolog programming is the following:

Program

+--V---+|

| Prolog |

Query -->| Interpreter |--> Answers +---+

The Program is a set of logic formulae (axioms or denitions).

The Query is a theorem to prove (with existentially quantied variables).

The Interpreter is a proof procedure that is sound and complete.

(16)

Home Page

Title Page

Contents

JJ II

J I

Page16of100

Go Back

A Simple Prolog Program

Consider the following domain:

• States of India

• Capital cities of each state

• Rivers of India

• States each river ows through

• Languages spoken in each state

• Chief minister of each state

(17)

Home Page

Title Page

Contents

JJ II

J I

Page17of100

Go Back

Representing simple information (Facts)

In Prolog we can write Facts (unit clauses) as follows.

Suppose we wish to say that Jayalalitha is the chief minister of Tamil- nadu.

We choose a predicate, say cm_of(X,Y) which means that X is the chief minister of Y and write

cm_of(tn,jaya) Similarly:

cm_of(kerala,karunakaran) cm_of(bengal,basu)

cm_of(bihar,laloo)

(18)

Home Page

Title Page

Contents

JJ II

J I

Page18of100

Go Back

Example (Cont'd)

Note that each fact that we have introduced has a meaning true. And we write down only true facts.

Similarly we can introduce other predicates and build up our facts as below.

spoken_in(tn,tamil) flows_thru(tn,kaveri) spoken_in(maha,marati) flows(bihar,ganga)

.... ....

capital_of(tn,madras) capital_of(ap,hyderabad) ....

(19)

Home Page

Title Page

Contents

JJ II

J I

Page19of100

Go Back

What can we do with only Facts?

Assume many such facts are already added to our Prolog Program.

We can now ask the interpreter queries like- cm_of(bihar,siva)

Answer --> no.

flows_through(X,ganga) Answer --> yes,

X = bihar ; X = up ; X = bengal

(20)

Home Page

Title Page

Contents

JJ II

J I

Page20of100

Go Back

Rules

Seems trivial so far. Queries can be answered by just looking up facts.

What about asking questions like:

• what languages are spoken in the states through which Ganga runs?

• what are the capital cities of the states through which Kaveri ows?

From the given facts these can be answered provided Prolog is given the correct Rules to make these inferences.

(21)

Home Page

Title Page

Contents

JJ II

J I

Page21of100

Go Back

How to write Rules in Prolog

A rule in Prolog consists of two parts:

• A head (a unit clause)

• The body (unit clauses separated by , and ended with .) connected by :-.

For example:

spoken_near(River, Lang) :-

flows_through(River, State), spoken_in(State, Lang).

Note that River, Lang and State are variables here and not specic names.

One way to read this rule in English is as follows:

(22)

Home Page

Title Page

Contents

JJ II

J I

Page22of100

Go Back

Answering Queries using Rules

Consider the query:

spoken_near(ganga,Lang)

There is no fact that can answer this directly.

We check for a rule with spoken_near as the head.

There is one. It requires us to solve the subgoals:

flows_through(State,ganga), spoken_in(State,Lang).

(23)

Home Page

Title Page

Contents

JJ II

J I

Page23of100

Go Back

Solving Subgoals

We try the rst subgoal.

flows_through(State,ganga) Answer --> State = bihar;

State = bengal;

...

For each answer we try the second subgoal:

spoken_in(bihar, Lang)

Answer--> Lang = hindi;

spoken_in(bengal, Lang)...

Answer--> Lang = bengali;

...

(24)

Home Page

Title Page

Contents

JJ II

J I

Page24of100

Go Back

Exercises

• What are the capitals of the states through which a river runs?

• What is the capital city of the state of some chief minister?

• What languages are spoken in the state of some chief minister?

Also, what will happen if the two clauses in the body are interchanged?

spoken_near(River, Lang) :- spoken_in(State, Lang),

flows_through(River, State).

First-Order Logic Examples

CS206 Lecture 08

Logic Progamming

Plan for Lecture 8

First-Order Logic Examples

Predicate Logic Semantics

From English to Logic

Possible Solutions

From Logic Formula to Meaning

Possible Interpretations

Logic Programming Paradigm

From Functions to Relations

Querying a Logic Program

Queries with Variables

No Directionality!

History of Logic Programming

Successful Applications of Prolog

Drawbacks of Prolog

Prolog Programming Model

A Simple Prolog Program

Representing simple information (Facts)

Example (Cont'd)

What can we do with only Facts?

Rules

How to write Rules in Prolog

Answering Queries using Rules

Solving Subgoals

Exercises

CS206 ^{Lecture 08}