本書采用一種創(chuàng)新的模型論進(jìn)行邏輯編程,從數(shù)據(jù)集的基本概念(即閉原子集)開始。沿著這一基本概念,我們引入視圖(即虛擬關(guān)系);我們將經(jīng)典邏輯程序定義為視圖定義集,使用傳統(tǒng)的類似于Prolog的表示法編寫,但語義是根據(jù)數(shù)據(jù)集而不是根據(jù)實現(xiàn)方式給出。然后介紹了一些閉原子操作,如添加和刪除。
本書是關(guān)于邏輯編程的入門教科書,它主要適用于本科生,但也適合中學(xué)生和低年級研究生閱讀。
本書假設(shè)學(xué)生已經(jīng)理解集合和集合運算,比如并集、交集等。本書還假設(shè)學(xué)生熟悉符號運算,掌握高中代數(shù)或有更高水平。
如果讀者有運用計算思維的經(jīng)驗,會對閱讀本書有幫助,但這并不是閱讀本書的條件。另外,編程經(jīng)驗也不是必需的。實際上,我們已經(jīng)觀察到,一些具有編程背景的學(xué)生剛開始閱讀這本書的時候比沒有編程經(jīng)驗的學(xué)生要困難得多。為了欣賞邏輯編程的力量和美感,他們似乎需要忘掉一些以前學(xué)過的知識。
本書采用的邏輯編程方法來自30多年來我們在學(xué)術(shù)和商業(yè)環(huán)境中的研究、應(yīng)用和教學(xué)。這些經(jīng)歷很寶貴,使得本書在以下兩個方面不同于其他書籍。
,本書采用模型理論的方法來闡述語義,而不用傳統(tǒng)的證據(jù)理論方法。從數(shù)據(jù)集的基本概念(即基本原子集)開始,我們引入了視圖定義的經(jīng)典邏輯程序,這種程序使用傳統(tǒng)的Prolog表示法編寫,但根據(jù)數(shù)據(jù)集而不是實現(xiàn)給出語義。我們也會在稍后的演示中討論實現(xiàn)。
第二,我們同時關(guān)注數(shù)據(jù)集的改變與邏輯代理的狀態(tài)。在討論了數(shù)據(jù)集之后,我們引入了更新的基本概念,即添加和刪除基本原子。根據(jù)這個基本概念,我們引入動態(tài)邏輯程序作為動作定義集,其中動作被概念化為同步更新集。這個擴(kuò)展允許我們討論邏輯代理以及靜態(tài)邏輯程序。(邏輯代理實際上是一個狀態(tài)機(jī),其中每個狀態(tài)被建模為數(shù)據(jù)集,每條弧被建模為一組更新。)
本書有印刷版和在線版,還通過教學(xué)網(wǎng)站提供能自動評分的在線練習(xí)、編程作業(yè)、邏輯編程工具和各種示例程序。該網(wǎng)站免費開放,網(wǎng)址為http://logicprogramming.stanford.edu。
后,我們要感謝對本書的編寫工作產(chǎn)生深遠(yuǎn)影響的兩個人:Jeff Ullman 和 Bob Kowalski。Jeff Ullman是我們在斯坦福大學(xué)的同事,他編寫的廣受歡迎的教材啟發(fā)了我們,并幫助我們認(rèn)識到邏輯編程和數(shù)據(jù)庫之間的深層關(guān)系。Bob Kowalski是邏輯編程的共同發(fā)明者,他傾聽了我們的想法,為我們的工作提供幫助,甚至就本書的某些章節(jié)與我們進(jìn)行了合作。
我們還想感謝Abhijeet Mohapatra。他是動態(tài)邏輯編程的共同發(fā)明者,也是本書中許多邏輯編程工具的共同創(chuàng)造者。他是這門課程的助教,為本書內(nèi)容的呈現(xiàn)和組織提供了寶貴的建議。
后,我們要感謝那些不得不忍受本書早期版本的學(xué)生們,在許多情況下,他們通過經(jīng)歷并不總是成功的實驗來幫助我們找到正確的方法。盡管犯了很多錯誤,他們似乎還是學(xué)會了書中的內(nèi)容,他們很聰明。他們的耐心和建設(shè)性的意見對于幫助我們理解哪些東西是可取的尤為寶貴。
Michael Genesereth和Vinay K. Chaudhri
2019年12月
譯者序
前言
部分 邏輯編程的介紹
第1章 概述3
1.1 邏輯編程3
1.2 邏輯程序作為可運行規(guī)范3
1.3 邏輯編程的優(yōu)點4
1.4 邏輯編程的應(yīng)用5
1.5 基本邏輯編程6
1.6 歷史筆記7
第2章 數(shù)據(jù)集9
2.1 引言9
2.2 概念化9
2.3 數(shù)據(jù)集的定義10
2.4 示例女生聯(lián)誼會12
2.5 示例親屬關(guān)系13
2.6 示例積木世界14
2.7 示例食物世界16
2.8 重組16
2.9 習(xí)題18
第二部分 查詢的更新
第3章 查詢23
3.1 引言23
3.2 查詢語法24
3.3 查詢語義25
3.4 安全性26
3.5 預(yù)定義概念27
3.6 示例親屬關(guān)系28
3.7 示例地圖著色29
3.8 習(xí)題30
第4章 更新33
4.1 引言33
4.2 更新語法33
4.3 更新語義34
4.4 同步更新35
4.5 示例親屬關(guān)系36
4.6 示例顏色37
4.7 習(xí)題40
第5章 查詢評估43
5.1 引言43
5.2 評估真值查詢43
5.3 匹配44
5.4 用變量評估查詢47
5.5 計算分析48
5.6 習(xí)題49
第6章 視圖優(yōu)化51
6.1 引言51
6.2 子目標(biāo)排序51
6.3 子目標(biāo)移除53
6.4 規(guī)則移除55
6.5 示例密碼算術(shù)55
6.6 習(xí)題57
第三部分 視圖的定義
第7章 視圖定義61
7.1 引言61
7.2 語法62
7.3 語義63
7.4 半正程序66
7.5 分層程序68
7.6 習(xí)題71
第8章 視圖評估73
8.1 引言73
8.2 基礎(chǔ)目標(biāo)和規(guī)則的自頂向下處理74
8.3 合一75
8.4 非基礎(chǔ)查詢和規(guī)則的自頂向下處理79
8.5 習(xí)題81
第9章 示例83
9.1 引言83
9.2 示例親屬關(guān)系83
9.3 示例積木世界84
9.4 示例模運算86
9.5 示例有向圖87
9.6 習(xí)題88
第10章 列表、集合、樹91
10.1 引言91
10.2 示例皮亞諾公理91
10.3 列表93
10.4 示例排序列表94
10.5 示例集合95
10.6 示例樹96
10.7 習(xí)題96
第11章 動態(tài)系統(tǒng)99
11.1 引言99
11.2 表示100
11.3 仿真101
11.4 計劃103
11.5 習(xí)題104
第12章 元知識105
12.1 引言105
12.2 自然語言處理105
12.3 布爾邏輯107
12.4 習(xí)題108
第四部分 操作的定義
第13章 操作113
13.1 引言113
13.2 語法113
13.3 語義115
13.4 習(xí)題118
第14章 動態(tài)邏輯程序121
14.1 引言121
14.2 響應(yīng)式系統(tǒng)121
14.3 封閉系統(tǒng)122
14.4 混合主動124
14.5 同時動作124
14.6 習(xí)題126
第15章 數(shù)據(jù)庫管理127
15.1 引言127
15.2 約束更新127
15.3 物化視圖維護(hù)128
15.4 通過視圖更新129
15.5 習(xí)題130
第16章 交互式工作表131
16.1 交互式工作表簡介131
16.2 示例132
16.3 網(wǎng)頁數(shù)據(jù)133
16.4 手勢134
16.5 操作定義135
16.6 視圖定義136
16.7 語義建模137
第五部分 結(jié)論
第17章 其他類型的邏輯程序設(shè)計143
17.1 引言143
17.2 邏輯生產(chǎn)系統(tǒng)143
17.3 約束邏輯編程144
17.4 析取邏輯編程145
17.5 存在邏輯編程146
17.6 回答集編程147
17.7 歸納邏輯編程149
附錄A EpilogJS中的預(yù)定義概念151
附錄B Sierra161
參考文獻(xiàn)182