布林邏輯的推論法 -- 程式實作
程式作品C 語言JavaC＃JavaScript常用函數文字處理遊戲程式衛星定位系統程式資料結構網路程式自然語言人工智慧機率統計資訊安全等待完成訊息相關網站參考文獻最新修改簡體版English |
根據 Horn 的前向推論法與 Robinson 的 Refutation 方法，我們用 Java 寫了一個推理引擎，其程式碼位於 BooleanLogic.java 中，該程式中的 unitResolution() 函數是採用 Robinson 的推論法則，而 hornReasoning() 函數則採用 Horn 的推論法則，兩者的程式碼分別如下。 程式內容import java.util.*; class BooleanLogic { Random random = new Random(); public static void main(String[] args) { String rules = "a<-b,c;b<-d,e;c<-d,f;d;e;f"; hornReasoning(rules.split(";")); unitResolution(rules.split(";")); } public static String neg(String pTerm) { if (pTerm.startsWith("-")) return pTerm.substring(1); else return "-"+pTerm; } public static String rewrite(String rule) { StringBuffer rzRule = new StringBuffer(); String head = head(rule, "<-"); String body = tail(rule, "<-"); rzRule.append(head); if (body.length() > 0) { String[] conds = body.split(","); for (int i=0; i<conds.length; i++) rzRule.append(","+neg(conds[i])); } return rzRule.toString(); } public static void unitResolution(String[] pRules) { Vector rules = new Vector(); for (int ri=0; ri<pRules.length; ri++) rules.add(rewrite(pRules[ri])); for (int ri=0; ri<rules.size(); ri++) { String rule1 = (String) rules.get(ri); if (rule1.indexOf(",")>0) continue; // it's not unit rule. String term = rule1; String negTerm = neg(term); for (int rj=0; rj<rules.size(); rj++) { String rule2 = (String) rules.get(rj); String exp = ","+rule2+","; if (exp.indexOf(","+negTerm+",")>0) { String unifyExp = replace(exp, ","+negTerm+",", ","); String newRule = unifyExp.substring(1, unifyExp.length()-1); rules.add(newRule); System.out.println("unfiy("+rule1+"|"+rule2+")="+newRule); } } } } public static void hornReasoning(String[] rules) { TreeMap trueMap = new TreeMap(); int satisfyRuleCount; do { satisfyRuleCount = 0; for (int ri=0; ri<rules.length; ri++) { if (rules[ri].length() == 0) continue; String head = head(rules[ri], "<-"); String body = tail(rules[ri], "<-"); String[] conds = body.split(","); boolean isSatisfy = true; for (int ci=0; ci<conds.length; ci++) { if (conds[ci].length() == 0) continue; if (trueMap.get(conds[ci]) == null) isSatisfy = false; } if (isSatisfy) { System.out.println(rules[ri]); trueMap.put(head, "1"); rules[ri] = ""; satisfyRuleCount ++; } } } while (satisfyRuleCount > 0); } public static String head(String pStr, String pSpliter) { int spliterPos = pStr.indexOf(pSpliter); if (spliterPos < 0) return pStr; return pStr.substring(0,spliterPos); } public static String tail(String pStr, String pSpliter) { int spliterPos = pStr.indexOf(pSpliter); if (spliterPos < 0) return ""; return pStr.substring(spliterPos+pSpliter.length()); } public static String replace(String pStr, String fromPat, String toPat) { if (fromPat.length()==0) return pStr; if (pStr.indexOf(fromPat)<0) return pStr; StringBuffer rzStr = new StringBuffer(); int strIdx = 0, nextIdx; while ((nextIdx = pStr.indexOf(fromPat, strIdx))>=0) { rzStr.append(pStr.substring(strIdx, nextIdx)); rzStr.append(toPat); strIdx = nextIdx + fromPat.length(); } rzStr.append(pStr.substring(strIdx)); return rzStr.toString(); } } 執行結果
結語布林邏輯雖然是一種簡單的邏輯系統，但其數學基礎非常紮實，是西洋文化的精隨之所在。如果我們能欣賞這種邏輯系統的美麗之處，那麼將能理解西方數學的重要性，進而將其應用到電腦領域，發展出更好的邏輯程式。 |
page revision: 6, last edited: 03 Nov 2010 02:20
Post preview:
Close preview