邏輯程式設計

邏輯程式設計

邏輯程式設計將邏輯直接作為程式設計語言並將計算作為受控推理的一種程式設計技術。

介紹

邏輯編程 的要點是將正規的邏輯風格帶入電腦程式設計之中。數學家和哲學家發現邏輯是有效的理論分析工具。很多問題可以自然地表示成一個理論。說需要解答一個問題,通常與解答一個新的假設是否跟現在的理論無衝突等價。邏輯提供了一個證明問題是真還是假的方法。創建證明的方法是人所皆知的,故邏輯是解答問題的可靠方法。邏輯編程系統則自動化了這個程式。人工智慧在邏輯編程的發展中發揮了重要的影響。

猴子和香蕉問題是邏輯編程社區的著名問題。電腦須自行找出令猴子接觸香蕉的可行方法,取代程式設計師指定猴子接觸香蕉的路徑和方法。

邏輯編程創建了描述一個問題里的世界的邏輯模型。邏輯編程的目標是對它的模型創建新的陳述。世界上知識不斷澎漲。傳統來說,我們會將一個問題陳述成單一的假設。邏輯編程的程式通過證明這個假設在模型里是否為真來解決問題。

一些經常用到邏輯編程工具的範疇:

•專家系統,程式從一個巨大的模型中產生一個建議或答案。

•自動化證明定理,程式產生一些新定理來擴充現有的理論。

最常用的邏輯程式語言是Prolog,另外有較適用於大型方案的Mercury。詳盡的清單可見於Category:邏輯程式語言。

沿革

1972年法國科莫勞埃小組實現了第一個邏輯程式設計語言PROLOG。1974年以後R.科瓦爾斯基進一步闡明了PROLOG的理論基礎,並系統地發展了邏輯程式設計的思想。對於傳統的程式設計來說,算法的邏輯意義往往被程式複雜的控制成分所掩蓋,使程式的正確性難以得到證明。而且通常的高級程式設計語言屬於過程性語言,需要在程式執行前詳細規定運行步驟。科瓦爾斯基對傳統的算法或對用通常高級語言編寫的程式提出了一個著名的分析公式,即算法=邏輯+控制。其基本思想是要從根本上改變程式設計的方法:用戶只需要編寫程式的邏輯部分(邏輯程式設計之名由此而來),而系統中的解釋程式則實施控制部分的職能。

優點

這種將邏輯與控制分開的方法具有下列的優點:①可以在控制部分設計之前不斷改進邏輯程式。②可以改進控制部分而無需變動邏輯程式本身。③可以從程式說明中生成邏輯程式,加以驗證和變換,而無需考慮其控制部分。④只需在邏輯程式中規定目標和實現這些目標的現有條件,也就是只需告訴系統做什麼(What to do),至於如何執行也就是說怎樣做 (How to do),則由系統的控制部分,即解釋程式處理解決。

歷史

早在二十世紀七十年代,羅伯特·科瓦爾斯基等人提出了邏輯可以作為程式設計語言的基本思想,把邏輯和程式這兩個截然不同的概念協調統一為一個概念,於是誕生了邏輯程式設計。這也是早期自動定理證明和人工智慧發展的自然結果。隨後,邏輯程式設計得到了迅速發展,特別是基於一階謂詞的邏輯程式設計語言,將邏輯推理對應於計算,具有豐富的表達能力、非確定性等特點,在定理機器證明、關係資料庫系統、程式驗證、模組化程式設計和非單調推理等都有了廣泛的套用。

現狀

現行邏輯程式的基本語句屬於一階謂詞演算的一個子集,HORN子句集。HORN子句的一般形式為: A1,…, Am← B1, B2,…, Bn,其中 Ai(1≤ i≤ m)、 Bj(1≤ j≤ n)都是原子公式,分別代表結論和前提的形式。前提部分是各原子的合取式,構成子句體,結論部分最多只有一個原子,稱為子句頭。由此可將HORN子句分成兩個基本類型:①有頭HORN子句(用來代表一條規則),例如,grandfather( x,z)←father( x,y),father ( y,z)代表: x是 y的父親且 y是z的父親,則 x是z的祖父。有頭無體的HORN子句是一斷言(用來代表一個事實)。例如,father( A,B)代表: A是 B的父親,father( B,C)代表: B是 C的父親。②無頭HORN子句,稱為目標語句(用來代表結論的否定式),例如,←grandfather( A,C)代表: A不是 C的祖父。邏輯學家A.霍恩對這類子句性質作了詳盡的研究,HORN子句即因此得名。

從問題歸約的角度看,可將HORN子句解釋為一過程,它將問題(目標) A歸約為若干子問題(子目標),每一子問題 Bi(1≤ i≤ n)又可解釋為對其他過程(HORN子句)的調用。有頭無尾的HORN子句則代表一個已知其解的基元問題。過程調用實際上是使構成子句體的一個原子(子目標)與某一子句頭匹配,這就是運用歸結原理中的合一的過程。因此邏輯程式的執行過程也就可以看成是定理證明過程,其中解釋程式起定理證明器或問題求解器的作用。

發展

HORN子句的過程調用( B1, B2,…, Bn)可按任意次序進行,適合於平行處理。HORN子句可作過程性的解釋也可作陳述性的解釋,運用比較方便。因此,以HORN子句為基礎的邏輯程式設計語言PROLOG受到人們的重視(見PROLOG語言)。日本的第五代計算機系統的計畫也推動了邏輯程式設計的研究。也有人認為,不同類型的問題需要不同風格的程式設計方法,在下一代的知識信息處理系統中除邏輯程式設計之外,還必須重視面向對象的程式設計、面向存取的程式設計、規則型程式設計,此外,建立與知識信息處理相適應的程式設計環境也是重要的課題。

相關詞條

相關搜尋

熱門詞條

聯絡我們