Top-down proof with SLD resolution [611538]

Articial Intelligence Homework, Spring 2017
May 29, 2017
Author: Malea Cristina-Ecaterina
Professor: Costin B adic a
Title: Top-down proof with SLD resolution
Groupe: CR. 2.2 A
Web: Articial Intelligence
1

Contents
1 Problem Statement 3
1.1 Title . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 NumberProblem 4
3 Algorithm 4
4 Functions 6
4.1 reading FUNCTION . . . . . . . . . . . . . . . . . . . . . . . . . 6
4.2 tree FUNCTION . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
4.3 display FUNCTION . . . . . . . . . . . . . . . . . . . . . . . . . 7
5 Application design 8
5.1 Modules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
5.1.1 Input Data . . . . . . . . . . . . . . . . . . . . . . . . . . 8
5.1.2 Output Data . . . . . . . . . . . . . . . . . . . . . . . . . 8
6 Conclusions 8
6.1 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2

Abstract
The top-down proof procedure can be understood in terms of answer
clauses.An alternative proof method is to search backward or top-down
from a query to determine if it is a logical consequence of the given denite
clauses. This procedure is called propositional denite clause resolution
or SLD resolution, where SL stands for Selecting an atom using a Linear
strategy, and D stands for Denite clauses. It is an instance of the more
general resolution method.
1 Problem Statement
1.1 Title
Top-down proof with SLD resolution.
1.2 Introduction
SLD resolution is the primary and the most important rule that used in logic
programming.In my opinion, in logic program, there are four principal compo-
nents, they are probabilistic facts, rules, background information, and query .The
top-down and bottom-up terms refer to the way building a demonstration.In the
top-down demonstration starts from the query until the knowledge base clauses
are reached,which are known to be true.The project is focused on the devel-
opment of skills forgood programming of euristic algorithms, covering coding,
design, documentation and presentation of result .
Fig.1. Diagram of the blocks-world problem.
3

2 NumberProblem
For each letter in my name I searched for the ASCII equivalent:
1.M 77
2.a 97
3.l 108
4.e 101
5.a 97
6.C 67
7.r 114
8.i 105
9.s 115
10.t 116
11.i 105
12.n 110
13.a 97
14.TotalSum 1309
15.TheRestOfTheDivisionAt 4 1
16.NumberOfProblem Rest + 1 = 2
3 Algorithm
Top-down denite clause proof procedure is a procedure thet solving a query.The
project consist in creating an application that follows the denition of a deriva-
tion.In this procedure, G is the set of atoms in the body of the answer clause.
The procedure is non-deterministic in that a point exists in the algorithm where
it has to choose a denite clause to resolve against.If there are choices that result
in G being the empty set, it returns yes; otherwise it fails.
NonDeterministic procedure DCDeductionTD(KB,Querry)
1.INPUTS
2. KB a set of denite clauses
3. Query a set of atoms to prove
4.OUTPUT
5. yes if KBj= Query and the procedure fails otherwise
6.LOCAL
7. G is a set of atoms
8.G Query
9.repeat
10. select an atom a in G
11. choose denite clause " a B" in KB with a as head
4

12. replace a with B in G
13.until G=fg
14.return yes
Fig.2. A search graph for a top-down derivation.
5

4 Functions
4.1 reading FUNCTION
reading(Node *p, int arr[max 3])
1.v[0] 0
2.while (!feof(le))
3. c fgetc(le)
4.if(((c48)and (c57)) or ((c97) and (c122)))then
5. d[strlen (d)] c
6. d[strlen (d)] NULL
7.else
8. if(strlen(d)!=0) then
9. if((d[0]97) and (d[0]122))then
10. v[++v[0]]=d[0]
11. if((d[0]48) and (d[0]57))then
12. v[++v[0]]=atoi(d)
13. fori 0, n, 1 execute
14. d[i] NULL
15.p v+1
16.n n*p
17.p p+1
18.fori 0, n, 1 execute
19. base[i]:a *p
20. p p+1
21. forj 0,base[i].k, 1 execute
22. base[i]:arr[j][0] *p
23. p p+1
24. form 1,base[i].k, 1 execute
25. p p+1
4.2 tree FUNCTION
display(Node *p, Node *q)
1.if(p! NULL) then
2.fori; swi 0, (i<n) and (swi==0), 1 execute
3. if(arr[1]==base[i].a) then
4. sw 1
5. id 1
6.if(swi!=0) then
7. if(base[id].k >0) then
8. fori 0, base[id].k, 1 execute
9. forj 1,arr[0], 1 execute
10. rr[j+ 1] rr[j]
11. rr[0] arr[0]
6

12. forh 1,base[id].arr[i][0], 1 execute
13. forj rr[0],1,-1 execute
14. rr[j+ 1] [j]
15. rr[0] rr[0]+1
16. forh 1,base[id].arr[i][0], 1 execute
17. rr[h] base[id].arr[i][h]
18. p!leg[i] new Node
19. p!leg[i]!r[0] new Node
20. forl 1,rr[0], 1 execute
21. p!leg[i]!r[l] rr[l]
22. reading( p!leg[i], rr)
23. p!leg[base[id]:k] NULL
24. else
25. if(base[id]:k 0) then
26. if(p!arr[0] >0) then
27. forj 1,arr[0], 1 execute
28. arr[j] r[j+1]
29. arr[0] arr[0]-1
30. p!leg[0] new Node
31. p!leg[0]!arr[0] r[0]
32. forl 1, arr[0], 1 execute
33. p!leg[0]!arr[l] arr[l]
34. p!leg[1] NULL
35. reading( p!leg[0],r)
36. else
37. p!leg[0] NULL
38. else
39. p!leg[0] NULL
4.3 display FUNCTION
display(Node *p, Node *q)
1.if(p! NULL) then
2.if(p!arr[0] 0) then
3. printf("0 ")
4.fori 1,p!arr[0], 1 execute
5. printf("c", p!arr[i])
6. printf("b")
7.if(q! NULL) then
8. printf("(")
9. forj 1,q!arr[0], 1 execute
10. printf("b")
11. q p
12. else
13. q p
7

14. fori p!leg[i]! NULL, 1 execute
15. display( p!leg[i], q)
5 Application design
5.1 Modules
As a programming language, I chose C++ because is fast and ecient, can create
compiled programs like Windows executables, make the most of the resources of
a computer, but not in the sense of overworking it, but in the sense of exploiting
its technical capabilities for which it was designed.My project is organized in 3
functions C++ with a variable number of variables.The 3 functions have been
described above.
5.1.1 Input Data
I provide for this applications one le tests that show us the dierence between
how fast the algorithms nd solution for the rsts test and how hard the al-
gorithm nd the path for complex example.Which every test le the execution
time and the number of possible states become very large.
5.1.2 Output Data
The exit of the program is represented by an on-screen display of all the action
made to reach the goal state that are presented very clear.
6 Conclusions
In conclusion, this project was a real challenge for me.It combined both the
knowledge of Articial Intelligence and C ++ programming(graphs, lists, search
methods end so on).As complexity, it was an average-hard project and I did my
best to understand certain things about Articial Intelligence.
8

6.1 References
References
[1] Thomas H. Cormen and Charles E. Leiserson and Ronald L. Rivest and
Cliord Stein, Introduction to Algorithms . MIT Press, 3rd Edition, 2009.
[2] Stuart Russell and Peter Norvig, Articial Intelligence: A Modern Approach .
Prentice Hall, 3rd Edition, 2010
[3] The University of British Columbia site, http://wiki.ubc.ca/Course:
CPSC522/Problog , accessed in May 2017.
[4] Articial Inteligence site, http://artint.info/html/ArtInt_110.html ,
accessed in May 2017.
[5] LATEXproject site, http://latex-project.org/ , accessed in May 2017.
9