Logic Programming and AI Principles
2018
LOGIC PROGRAMMING
By
Dr. Metwally Rashad
C
o
u
r
s
e
S
p
e
c
i
f
i
c
a
t
i
o
n
a
n
d
A
i
m
1/29
Course Data
- Course Code
: CSW352
- Specialization:
Computer Science
- No. of Instructional Units:
Lecture 3 hrs/week
Practical 2 hrs/week
5 hrs/week
Course Aim
- The course is intended to give the student an understanding of the principles of logic
programming and how these are applied to standard problems in AI.
S
c
h
e
d
u
l
e
2/29
Assessment 1 Week 4
Midterm exam Week 7 or 8
Assessment 2 Week 11
Oral exam
Week 14
Practical exam
Week 15
Final exam Week 16
W
e
i
g
h
t
i
n
g
o
f
A
s
s
e
s
s
m
e
n
t
:
3/29
Mid-Term Examination 10 %
Final-term Examination
65 %
Oral Examination
10 %
Practical exam
15 %
---------------------------------------------------------------------
Total
100 %
5 3-Quiz
10 P. Exam
C
o
u
r
s
e
M
a
t
e
r
i
a
l
s
4/29
Ivan Bratko,
Prolog Programming for Artificial Intelligence
, (4ED),
Pearson Education Limited, 2012, ISBN 978-0-231-41746-6.
Ulf Nilsson and Jan Ma luszynski,
Logic, Programming and Prolog
(2ED).
Patrick Blackburn, Johan Bos, Kristina Striegnitz,
Learn Prolog Now
!.
C
o
n
t
e
n
t
s
5/29
Introduction and Logic Foundations of Prolog
Prolog Variables, Bound and free Variables and Matching
Syntax and Meaning of Prolog Program
Backtracking and Recursive Rule Definition
Built-in Predicates and Arithmetic Expressions
Lists Manipulation I
Lists Manipulation II
Operators
Controlling Backtracking I
Controlling Backtracking II
Data Structures in Prolog
Advanced Techniques
L
o
g
i
c
p
r
o
g
r
a
m
m
i
n
g
6/29
Programming languages are of two kinds:
- Procedural
(BASIC, ForTran, Pascal ,C++, Java).
- Declarative
(LISP, Prolog, ML).
In
procedural programming
, we tell the computer
how
to solve a problem.
In
declarative programming
, we tell the computer
what
problem we want solved.
(you do not write out what the computer should do line by line)
The general idea behind declarative languages is that you describe a situation.
- Based on this code, the interpreter or compiler will tell you a solution.
H
i
s
t
o
r
y
o
f
L
o
g
i
c
P
r
o
g
r
a
m
m
i
n
g
(
L
P
)
7/29
Formulated in 1974 by a professor at Univ. of Edinburgh.
First system implemented in 1995 by a research group in France.
First compiler built in 1997 by a PhD student also in Edinburgh.
Japan’s fifth generation computer project announced in 1980.
Efficiency improved in recent years.
Interfaces with other languages such as C/Java.
W
h
y
P
r
o
l
o
g
i
s
n
o
t
a
s
p
o
p
u
l
a
r
a
s
C
/
J
a
v
a
?
8/29
Mistaken at first as some universal computer language.
Not yet as efficient as C.
Support to Prolog takes effort, resources; companies are not willing
to pay for it.
Its value not recognized by industry.
W
h
a
t
i
s
a
l
o
g
i
c
?
9/29
A logic is a language:
it has syntax and semantics. More than a language, it has
inference rules.
Syntax:
the rules about how to form formulas; this is usually the easy part of
a logic.
Semantics:
about the meaning carried by the formulas, mainly in terms of
logical consequences.
Inference rules:
describe correct ways to derive conclusions.
P
r
o
l
o
g
10/29
“
Pro
gramming with
Log
ic“
Very different from other (procedural) programming languages.
Good for knowledge-rich tasks.
Prolog is a computer programming language that is used for solving
problems that involve
objects
and the
relationships
between objects.
In Prolog, the word "
object
"
does not refer to a data structure that can
inherit variables and methods from a class
,
but it refers to things that
we can represent using
terms.
A Prolog program consists of
clauses
. Each clause terminates with a full stop.
H
i
s
t
o
r
y
o
f
P
r
o
l
o
g
11/29
H
i
s
t
o
r
y
o
f
P
r
o
l
o
g
12/29
H
i
s
t
o
r
y
o
f
P
r
o
l
o
g
13/29
H
i
s
t
o
r
y
o
f
P
r
o
l
o
g
14/29
H
i
s
t
o
r
y
o
f
P
r
o
l
o
g
15/29
B
a
s
i
c
i
d
e
a
o
f
P
r
o
l
o
g
16/29
Describe the situation of interest.
Ask a question.
Prolog logically deduces new facts about the situation we
described.
Prolog gives us its deductions back as answers .
L
o
g
i
c
F
o
r
m
u
l
a
s
17/29
When describing some states in the real world, we often use declarative
sentences like:
- Every mother loves her children
- Mary is a mother and
- Tom is Mary's child
By applying some general rules of reasoning such descriptions can be used to
draw new conclusions
.
- Mary loves Tom
L
o
g
i
c
F
o
r
m
u
l
a
s
18/29
Declarative statement contains
:
-
Persons (individual)
•
"
Mary, Tom
".
- Relation between individuals like:
•
"
.
. . is a mother
"
•
"
. . . is a child of . . .
"
•
"
. . . loves . . .
"
- Relation may not hold between individuals like:
•
"
…being a mother
"
- Relations with more than two objects like:
•
"
. . . is the sum of . . . and . . .
"
C
o
n
c
e
p
t
o
f
L
o
g
i
c
F
o
r
m
u
l
a
s
19/29
Constant
:
- Symbols for denoting individuals
•
Tom
tom
Predicate (functor)
:
- Symbols for denoting relations
•
(loves , mother, child of )
Arity
:
- Number of arguments of the predicate.
•
loves
2-ary
- nullary
0-ary, unary
1-ary, binary
2-ary and ternary
3-ary.
F
o
r
m
a
l
i
z
a
t
i
o
n
20/29
The formal language should provide sentences refers to all elements of the
described “world".
- e.g.
“
for all individuals X and Y, if X is a mother and Y is a child of X then X loves Y
".
The language of logic introduces:
-
“
”
symbol of universal quantifier
•
To be read “
for every
“ or “
for all
“
-
Variable
is a symbol that refers to an unspecified individual,
•
like X and Y
F
o
r
m
a
l
i
z
a
t
i
o
n
21/29
Previous example can be formalized
“
" reads “
and
"
“
,
" is called implication and corresponds to the “
if-then
“
(….) are used to disambiguate the language.
⇒
F
o
r
m
a
l
i
z
a
t
i
o
n
22/29
“
”
denoted by
negation
(with reading “not")
“
Tom does not loves Mary"
loves(tom, mary)
“
” denoted by existential quantifier and reads “
there exists
".
- The existential quantifier makes it possible to express the fact .
- There exists at least one individual which is in a certain relation with some other
individuals.
- “Mary has a child"
X child of (X, mary).
“
”
OR
“
”
“if and only if”
Compound term
family(bill, mary, child (tom, child (alice, none)))
E
x
a
m
p
l
e
s
23/29
1. All cats are mammals
2. All of Bill’s kids are also Hillary’s kids
3. Somebody likes brain
4. Nobody likes brain
-
∀
X(cat(X)
⇒
mammal(X))
-
∀
X(father(bill, X)
⇒
mother(hillary, X))
-
∃
X(likes(X, brain))
- ¬
∃
X[likes(X, brain)] or
∀
X[¬ X(like(X, brain))
which is mean everybody doesn't likes brain
T
r
y
w
i
t
h
y
o
u
r
s
e
l
f
24/29
1. marcus was a man
2. All pompeians were romans
3. caesar was a ruler.
4. All romans were either loyal to caesar or hated him.
5. Everyone is loyal to someone.
6. marcus tried to assassinate caesar
1/20
This course focuses on logic programming principles applied to AI problems. Topics include Prolog programming, backtracking, recursive rule definition, built-in predicates, lists manipulation, and advanced techniques. Declarative languages like Prolog differ from procedural languages by describing problems to solve instead of specifying how to solve them. The history of Logic Programming dates back to 1974, with its formulation at the University of Edinburgh.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
LOGIC PROGRAMMING By Dr. Metwally Rashad 2018
Course Specification and Aim Course Data - Course Code: CSW352 - Specialization: Computer Science - No. of Instructional Units: Lecture 3 hrs/week Practical 2 hrs/week 5 hrs/week Course Aim - The course is intended to give the student an understanding of the principles of logic programming and how these are applied to standard problems in AI. 1/29
Schedule Assessment 1 Week 4 Midterm exam Week 7 or 8 Assessment 2 Week 11 Oral exam Practical exam Final exam Week 16 Week 14 Week 15 2/29
Weighting of Assessment: Mid-Term Examination 10 % Final-term Examination Oral Examination Practical exam --------------------------------------------------------------------- Total 65 % 10 % 15 % 5 3-Quiz 10 P. Exam 100 % 3/29
Course Materials Ivan Bratko, Prolog Programming forArtificial Intelligence, (4ED), Pearson Education Limited, 2012, ISBN 978-0-231-41746-6. Ulf Nilsson and Jan Ma luszynski, Logic, Programming and Prolog (2ED). Patrick Blackburn, Johan Bos, Kristina Striegnitz, Learn Prolog Now!. 4/29
Contents Introduction and Logic Foundations of Prolog Prolog Variables, Bound and free Variables and Matching Syntax and Meaning of Prolog Program Backtracking and Recursive Rule Definition Built-in Predicates and Arithmetic Expressions Lists Manipulation I Lists Manipulation II Operators Controlling Backtracking I Controlling Backtracking II Data Structures in Prolog Advanced Techniques 5/29
Logic programming Programming languages are of two kinds: - Procedural (BASIC, ForTran, Pascal ,C++, Java). - Declarative (LISP, Prolog, ML). In procedural programming, we tell the computer how to solve a problem. In declarative programming, we tell the computer what problem we want solved. (you do not write out what the computer should do line by line) The general idea behind declarative languages is that you describe a situation. - Based on this code, the interpreter or compiler will tell you a solution. 6/29
History of Logic Programming (LP) Formulated in 1974 by a professor at Univ. of Edinburgh. First system implemented in 1995 by a research group in France. First compiler built in 1997 by a PhD student also in Edinburgh. Japan s fifth generation computer project announced in 1980. Efficiency improved in recent years. Interfaces with other languages such as C/Java. 7/29
Why Prolog is not as popular as C/Java? Mistaken at first as some universal computer language. Not yet as efficient as C. Support to Prolog takes effort, resources; companies are not willing to pay for it. Its value not recognized by industry. 8/29
What is a logic? A logic is a language: it has syntax and semantics. More than a language, it has inference rules. Syntax: the rules about how to form formulas; this is usually the easy part of a logic. Semantics: about the meaning carried by the formulas, mainly in terms of logical consequences. Inference rules: describe correct ways to derive conclusions. 9/29
Prolog Programming with Logic Very different from other (procedural) programming languages. Good for knowledge-rich tasks. Prolog is a computer programming language that is used for solving problems that involve objects and the relationships between objects. In Prolog, the word "object" does not refer to a data structure that can inherit variables and methods from a class, but it refers to things that we can represent using terms. A Prolog program consists of clauses. Each clause terminates with a full stop. 10/29
History of Prolog first Prolog interpreter by Colmerauer and Roussel 1972 1980s/1990s 1977 1980 2005 11/29
History of Prolog implementation of DEC10 compiler by Warren 1972 1980s/1990s 1977 1980 2005 12/29
History of Prolog Definite Clause Grammars implementation by Pereira and Warren 1972 1980s/1990s 1977 1980 2005 13/29
History of Prolog Prolog grows in popularity especially in Europe and Japan 1972 1980s/1990s 1977 1980 2005 14/29
History of Prolog Prolog used to program natural language interface in international space station by NASA 1972 1980s/1990s 1977 1980 2005 15/29
Basic idea of Prolog Describe the situation of interest. Ask a question. Prolog logically deduces new facts about the situation we described. Prolog gives us its deductions back as answers . 16/29
Logic Formulas When describing some states in the real world, we often use declarative sentences like: - Every mother loves her children - Mary is a mother and - Tom is Mary's child By applying some general rules of reasoning such descriptions can be used to draw new conclusions. - Mary loves Tom 17/29
Logic Formulas Declarative statement contains: -Persons (individual) "Mary, Tom". - Relation between individuals like: ". . . is a mother " ". . . is a child of . . . " ". . . loves . . . " - Relation may not hold between individuals like: " being a mother" - Relations with more than two objects like: ". . . is the sum of . . . and . . . " 18/29
Concept of Logic Formulas Constant: - Symbols for denoting individuals Tom tom Predicate (functor) : - Symbols for denoting relations (loves , mother, child of ) Arity: - Number of arguments of the predicate. loves 2-ary - nullary 0-ary, unary 1-ary, binary 2-ary and ternary 3-ary. 19/29
Formalization The formal language should provide sentences refers to all elements of the described world". - e.g. for all individuals X and Y, if X is a mother and Y is a child of X then X loves Y". The language of logic introduces: - symbol of universal quantifier To be read for every or for all - Variable is a symbol that refers to an unspecified individual, like X and Y 20/29
Formalization Previous example can be formalized " reads and" , " is called implication and corresponds to the if-then ( .) are used to disambiguate the language. 21/29
Formalization denoted by negation (with reading not") Tom does not loves Mary" loves(tom, mary) denoted by existential quantifier and reads there exists". - The existential quantifier makes it possible to express the fact . - There exists at least one individual which is in a certain relation with some other individuals. - Mary has a child" X child of (X, mary). OR if and only if Compound term family(bill, mary, child (tom, child (alice, none))) 22/29
Examples 1. All cats are mammals - X(cat(X) mammal(X)) 2. All of Bill s kids are also Hillary s kids - X(father(bill, X) mother(hillary, X)) 3. Somebody likes brain - X(likes(X, brain)) 4. Nobody likes brain - X[likes(X, brain)] or X[ X(like(X, brain)) which is mean everybody doesn't likes brain 23/29
Try with your self 1. marcus was a man 2. All pompeians were romans 3. caesar was a ruler. 4. All romans were either loyal to caesar or hated him. 5. Everyone is loyal to someone. 6. marcus tried to assassinate caesar 24/29
