Posted By

bjornredemption on 07/08/11

Statistics

Viewed 1084 times
Favorited by 0 user(s)

AI Forward Chaining implementation for propositional logic horn form knowledge bases

/ Published in: Java  Artificial intelligence basics : This is a forward chaining implementation which works with horn form knowledge bases. Had some trouble finding any simple and easy to understand examples online - so here's my version!!!
http://en.wikipedia.org/wiki/Forward_chaining

Copy this code and paste it in your HTML
1. import java.util.*;
2. import java.io.*;
3.
4. // to run simply do a: new FC(ask,tell) and then fc.execute()
5. // ask is a propositional symbol
6. // and tell is a knowledge base
8. // tell : p=>q;q=>r;p;q;
9.
10. class FC{
11. // create variables
12. public static String tell;
14. public static ArrayList<String> agenda;
15.
16. public static ArrayList<String> facts;
17. public static ArrayList<String> clauses;
18. public static ArrayList<Integer> count;
19. public static ArrayList<String> entailed;
20.
21.
22. public FC(String a, String t){
23. // initialize variables
24. agenda = new ArrayList<String>();
25. clauses = new ArrayList<String>();
26. entailed = new ArrayList<String>();
27. facts = new ArrayList<String>();
28. count = new ArrayList<Integer>();
29. tell = t;
31. init(tell);
32. }
33.
34. // method which calls the main fcentails() method and returns output back to iengine
35. public String execute(){
36. String output = "";
37. if (fcentails()){
38. // the method returned true so it entails
39. output = "YES: ";
40. // for each entailed symbol
41. for (int i=0;i<entailed.size();i++){
42. output += entailed.get(i)+", ";
43. }
45. }
46. else{
47. output = "NO";
48. }
49. return output;
50. }
51.
52. // FC algorithm
53. public boolean fcentails(){
54. // loop through while there are unprocessed facts
55. while(!agenda.isEmpty()){
56. // take the first item and process it
57. String p = agenda.remove(0);
60. // for each of the clauses....
61. for (int i=0;i<clauses.size();i++){
62. // .... that contain p in its premise
63. if (premiseContains(clauses.get(i),p)){
64. Integer j = count.get(i);
65. // reduce count : unknown elements in each premise
66. count.set(i,--j);
67. // all the elements in the premise are now known
68. if (count.get(i)==0){
69. // the conclusion has been proven so put into agenda
71. // have we just proven the 'ask'?
73. return true;
75. }
76. }
77. }
78. }
79. // if we arrive here then ask cannot be entailed
80. return false;
81. }
82.
83.
84.
85.
86. // method which sets up initial values for forward chaining
87. // takes in string representing KB and seperates symbols and clauses, calculates count etc..
88. public static void init(String tell){
89. String[] sentences = tell.split(";");
90. for (int i=0;i<sentences.length;i++){
91.
92. if (!sentences[i].contains("=>"))
93. // add facts to be processed
95. else{
99. }
100. }
101. }
102.
103.
104. // method which checks if p appears in the premise of a given clause
105. // input : clause, p
106. // output : true if p is in the premise of clause
107. public static boolean premiseContains(String clause, String p){
108. String premise = clause.split("=>");
109. String[] conjuncts = premise.split("&");
110. // check if p is in the premise
111. if (conjuncts.length==1)
112. return premise.equals(p);
113. else
114. return Arrays.asList(conjuncts).contains(p);
115. }
116. } Subscribe to comments