邏輯式程序設(shè)計(jì)語言

1、第六章 邏輯式程序設(shè)計(jì)語言,邏輯式語言基本形式：用一種符號(hào)邏輯作為程序設(shè)計(jì)語言來進(jìn)行程序設(shè)計(jì)，通常稱為邏輯程序設(shè)計(jì)語言，或聲明性語言,第六章 邏輯式程序設(shè)計(jì)語言,程序要對(duì)數(shù)據(jù)結(jié)構(gòu)實(shí)施某個(gè)算法過程,算法實(shí)現(xiàn)計(jì)算邏輯 算法 = 邏輯 + 控制邏輯程序設(shè)計(jì)的基本觀點(diǎn)是程序描述的是數(shù)據(jù)對(duì)象之間的關(guān)系。關(guān)系也是聯(lián)系對(duì)象和對(duì)象、對(duì)象和屬性的聯(lián)系就是我們所說的事實(shí)。事實(shí)之間的關(guān)系以規(guī)則表述，根據(jù)規(guī)則找出合乎邏輯的

2、事實(shí)就是推理邏輯程序設(shè)計(jì)范型是陳述事實(shí)、制定規(guī)則，程序設(shè)計(jì)就是構(gòu)造證明。程序的執(zhí)行就在推理,6.1謂詞演算,謂詞演算是符號(hào)化事實(shí)的形式邏輯系統(tǒng)，它也是邏輯程序設(shè)計(jì)語言的模型表示命題表示命題之間的關(guān)系描述如何根據(jù)假設(shè)為真的命題推斷出新命題 謂詞演算諸元素 用形式方法研究論域上的對(duì)象需要一種語言，它能表達(dá)該域?qū)ο缶哂惺裁葱再|(zhì)(properti

3、es)， 以及對(duì)象間有些什么關(guān)系(relations) 描述以公式(Formulas)表達(dá)。謂詞公式中各元素按一定邏輯規(guī)則變換，即謂詞演算(predicate calculus),(1)公式 由一組約定的符號(hào)組成的序列，它包括常量、變量、邏輯連接、命題函數(shù)、謂詞、量詞(2)常量 指明論域上的對(duì)象(3)變量 可束定到特定域上某個(gè)范圍的對(duì)象上(4)函數(shù) 表征對(duì)象具有的映射關(guān)系(5)謂詞 表征對(duì)象某種性質(zhì)的符號(hào)(6)量

4、詞 量詞限定的變量名作用域是整個(gè)公式(7) 邏輯操作 and， or， not， →(蘊(yùn)含) (全等)當(dāng)謂詞應(yīng)用到的變?cè)浅Ａ炕蛞驯皇ǖ淖兞可蠒r(shí)，就叫做句子(sentence)或命題(proposition),謂詞變?cè)膫€(gè)數(shù)稱作目(arity)，有單目、N目謂詞之稱 N-目謂詞的例子。 謂詞 目 含義 od

5、d(X) 1 X是奇數(shù) father(F，S) 2 F是S的父親 divide(N，D，Q，R) 4 N除D得商Q和余數(shù)R 謂詞例化 結(jié)果值

6、 odd(2) False divide (23， 7， 3，2) Ture father (changshan， changping) True divide (23， 7， 3， N) N未例化， 不知真假,謂詞的

7、量化量化謂詞 結(jié)果值 ?Xodd(X) False ?Xodd(X) True ?X(X=2*Y+1→odd (X)) True ?X?Ydivide (X，3，Y，0) Tr

8、ue， 如X =3，Y=1?X?Ydivide (X，3，Y，0) False?X?Ydivide(X，3，Y，0) False， 但很難證明,證明一個(gè)全稱謂詞是比較難的，因?yàn)樽羁煽康淖C明方法是枚舉例證。 于是采取反證的方法，全稱量化的謂詞取反量化謂詞 取反?Xodd(X)

9、 ?Xnot odd(X) [1]?Xodd(X) ?Xnot odd(X) [2]?X(X=2*Y+1→odd(X)) ?Xnot(X+2*Y+1→odd(X)) [3]

10、 ?Xnot(X=2*Y+1)or odd (X)) [4] ?X((X=2*Y+1)and not add(X)) [5]?X?Y divide (X，3，Y，0) ?X?Y not divide (X，3，Y，0) [6]?X?Y divide (X，3，Y，0) ?X?Y not div

11、ide (X，3，Y，0) [7]?X?Y divide (X，3，Y，0) ?X?Y not divide (X，3，Y，0) [8],謂詞演算的等價(jià)變換,[1]以∧，∨， ?消除→、符號(hào)[2]化為前束范式,消除最外的?符號(hào),否定符號(hào)內(nèi)移?(?XP(X)┠ ?X(? p(X))[3]用斯柯林變換消去存在量詞 ?X(a ( X) ∧ b(X) ∨?Y c (X，Y)) ┠ ?X(a (X) ∧ b(X) ∨

12、c (X， g(X)))[4] 消除前束范式的全稱量詞 ┠ a(X) ∧ b(X) ∨ c (X，g(X)),一般謂詞公式變換為子句的實(shí)例?！摹?hào)為“可推出”,[5]用分配率P∨(Q∧R)=(P∨Q)∧(P∨R)化成合取范式 ┠ (a(X)∨c(X，g(X)))∧(b(X)∨c(X，g(X))) 經(jīng)過以上變換,任何一復(fù)合公式均可成為如下形式: F = C1∧C2 ∧…Cn 且其中Ci稱為子句

13、若以';'代'∨'則有: Ci = L1 ∨L2 ∨…Lv = L1;L2;…;Lv 因此，任一公式均可化為'∨'連接的子句的集合,6.2 自動(dòng)定理證明,證明系統(tǒng) 事實(shí)即證明系統(tǒng)中的公理(axioms) 證明系統(tǒng)(proof system)是應(yīng)用公理演繹出定理

14、 (theorems)的合法演繹規(guī)則的集合 演繹也叫歸約(deduction)，是對(duì)證明系統(tǒng)中合法 推理規(guī)則的一次應(yīng)用 演繹從公理導(dǎo)出結(jié)論(conclusion)， 中間可利用以 這些規(guī)則演繹出的定理證明(proof)是個(gè)語句序列， 以每個(gè)語句得到證明而結(jié)束， 即每個(gè)句子要么演繹成公理， 要么演繹成前此導(dǎo)出的定理,一個(gè)證明若有N個(gè)語句(命題)則稱N步

15、證明反駁(refutation)是一個(gè)語句的反向證明。 它證明 一個(gè)語句是矛盾的， 即不合乎給定的公理一個(gè)語句若能從公理出發(fā)推演出來， 則稱合法語句， 任何合法語句也叫做定理(theorem)從某一公理集合導(dǎo)出的所有定理集合稱為理論(theory),模型 從公理集合中導(dǎo)出定理集稱之為理論，有了理論我們要解釋它的語義必須借助某個(gè)模型(model)。因?yàn)樾问较到y(tǒng)只是符號(hào)抽象，借助

16、模型我們可為每個(gè)常量、函數(shù)、謂詞符號(hào)找到真理性的解釋。即定義每個(gè)論域，并表明域上成員和常量公理之間的關(guān)系。 公理的謂詞符號(hào)必須派定為域中對(duì)象的性質(zhì)， 函數(shù)派定為對(duì)域中對(duì)象的操作。 公理集合一般情況下只是定義的部分(偏)函數(shù)和謂詞， 是問題域的一個(gè)側(cè)面。 所以能滿足該理論的模型往往不止一個(gè)。,例 一個(gè)最簡單的理論 公理集: ?Xin

17、terval(X)→not interval (X+1) (a1)?Xnot interval (X+1)→interval(X) (a2)2=1+1 (a3) 從間隔數(shù)公理可導(dǎo)出定理:

18、 ?Xinterval (X)→interval (X+2) (t1)?Xinterval (X+2) → interval(X) (t2),謂詞interval(間隔數(shù))在整數(shù)域上有兩個(gè)子域odd、even都能夠滿足間隔數(shù)理論不能證明interval(3)，也不能證明not interval(3)為真命題。這就是Hi

19、lbert討論過的可判定(decidability)問題。1936年Church和Turing證實(shí)謂詞演算可判定性問題是沒有解的一旦我們斷言interval(3)或interval(2)是真命題,我們立刻可通過演繹證明按這個(gè)理論寫出的每一個(gè)謂詞為真。這就是Godel和Herbrand1930年證實(shí)的謂詞演算具備的完整性(completeness),證明技術(shù)

20、 從謂詞演算具有完整性， 理論上可證明按公理集合建立的任何理論。關(guān)鍵是效率。 如果我們從公理出發(fā)做出每一個(gè)步驟， 在新的步驟上仍然要查找每一個(gè)公理，找出可能的推理。如此下去就形成一個(gè)龐大的樹行公理集， 每層的結(jié)點(diǎn)表示一個(gè)公理的語句， 其深度和寬度隨問題和最初給出的公理而定， 一層一步驟， N層的樹就是N步推理。 對(duì)于自動(dòng)定理證明程序， 只有窮舉每條可能的證明步驟才能說它是完全的。 窮舉完所有路徑馬上遇到

21、組合爆炸問題，無論是深度優(yōu)先還是廣度優(yōu)先，百步演繹可能的路徑數(shù)都是天文數(shù)字。,歸結(jié)定理證明 J.A.Robinson1965年提出的歸結(jié)法(resolution) ，是命題演算中對(duì)合適公式的一種證明方法。 為了證明合適公式F為真， 歸結(jié)法證明?F恒假來代替F永真。 把兩子句合一(unification)并消去一對(duì)正逆命題，故歸結(jié)也譯作消解。 歸結(jié)證明的過程并稱之歸結(jié)演繹， 其步驟如下:,[1]

22、把前題中所有命題換成子句形式。[2]取結(jié)論的反,并轉(zhuǎn)換成子句形式,加入[1]中的子句集.[3]在子句集中選擇含有互逆命題的命題歸結(jié)。用合一算法得出新子句(歸結(jié)式)，再加入到子句集。[4]重復(fù)[3]，若歸結(jié)式為空則表示此次證明的邏輯結(jié)論是矛盾，原待證結(jié)論若不取反則恒真。命題得證。 否則繼續(xù)重復(fù)[3]。,例：歸結(jié)證明 若有前題 待證命題 取反得新子句 p1 Q∨?P

23、 ?P∨?U p5 P p2 R∨?Q p6 U p3 S∨?R p4 ?U∨?S 取待證命題的反， 得P∧U， 它是∧連接的兩個(gè)子句P、U，把它們加到前題子句集， 為p5，p6。,歸

24、結(jié)演繹如下圖: Q∨?P P p1-p5歸結(jié) Q R∨?Q 再與p2歸結(jié) S∨?R R 再與p3歸結(jié) S ?U∨?S

25、 再與p4歸結(jié) U ?U 再與p6歸結(jié) 矛盾,,,,,,,,,,,,由本例可以看出兩個(gè)問題：第一，歸結(jié)法是由合一算法實(shí)現(xiàn)的。所謂合一是找出型式匹配的兩子句， 將它們合一為歸結(jié)式， 相當(dāng)于代數(shù)中的化簡。第二，如果得不出矛盾，那么歸結(jié)法要無休止地做

26、下去，中間歸結(jié)式出得越多， 匹配查找次數(shù)越多， 每一步都做長時(shí)間計(jì)算。 Solution：利用切斷(cut)操作， 并利用對(duì)子句形式進(jìn)一步限制的超級(jí)歸結(jié)法(Hyperresolution)。,Horn子句實(shí)現(xiàn)超歸結(jié) Horn子句是至多只有一個(gè)非負(fù)謂詞符號(hào)的子句 Horn子句形式示例如下: ?P∨?Q∨S∨?R∨?T 其中只有一個(gè)非負(fù)謂詞S,可作以下演算： 先將S移向右方

27、 ┠ S∨?P∨?Q∨?R∨?T 按德·摩根定律 ┠ S∨? (P∧Q∧R∧T) '∨?'即’→’， 則 ┠ S →(P ∧ Q ∧ R ∧ T) 此條件Horn子句的意義是 if S then (P∧Q∧R∧T) 。 若S為空， 則為無條件Horn子句， 是一個(gè)斷言(事實(shí)),6.3 邏輯程序

28、的風(fēng)格,第一個(gè)特點(diǎn)是它不描述計(jì)算過程而是描述證明過程第二個(gè)特點(diǎn)是描述性第三個(gè)特點(diǎn)是大量用表和遞歸實(shí)現(xiàn)重復(fù)操作sort（old_list,new_list） ┠ permute(old_list,new_list) ∧ sorted(new_list) sorted(list) ∧ ?j 使得 1≤ j < n, list(j) ≤ list(j+1)*permute是一個(gè)謂詞，如果第二個(gè)參數(shù)組是第一個(gè)參數(shù)組的一個(gè)

29、排列，就返回真,Prolog語言,Prolog是一種基于一階謂詞的邏輯式語言Prolog是基于Horn子句的，使用歸結(jié)推理，具有很強(qiáng)的邏輯描述能力和推理能力Prolog語言特點(diǎn)：一階邏輯的語言形式是形式化地嚴(yán)格定義的一階邏輯的語法簡易易懂邏輯公式不需要重復(fù)表達(dá)，與不同應(yīng)用無關(guān)事實(shí)、假設(shè)、推理、查詢、視圖和完整性規(guī)約條件都能以基于一階邏輯的prolog語言表達(dá)邏輯語言Prolog可作為定義和比較其它知識(shí)表示模型的共同模型,例

30、 求平均成績的邏輯程序，打開一分?jǐn)?shù)文件scores， 讀入分?jǐn)?shù)求和并用的數(shù)N除之得平均成績 average :- see(scores)， getinput (Sum，N)， seen (scores)， Av is Sum /N， print ('Average

31、= '， Av) getinput (Sum，N) :- ratom (X)， not (eof)， getinput (Sum1，N1)， Sum is Sum1 + X，

32、 N is N1＋1. getinput (0，0) :- eof.,6.4 典型邏輯程序設(shè)計(jì)語言Prolog,Prolog要環(huán)境支持 ，即管理事實(shí)和規(guī)則的數(shù)據(jù)庫 Prolog的基本成分是對(duì)象(常量、變量、結(jié)構(gòu)、表)、謂詞、運(yùn)算符、函數(shù)、規(guī)則從純語法意義上Prolog的項(xiàng)什么都可以表示: ::=|||()|

33、 ||,從語義角度， 以下語法描述提供了處理時(shí)的語義概念: → → ( | | ) → → : - → → ， → /*形如p或q(T， …，)的字面量*/,與Prolog交互,？- （在每輪交互開始時(shí)系統(tǒng)都會(huì)給出“提示符號(hào)”）表示希望得到一個(gè)查詢？- consult（links）.Consult結(jié)構(gòu)讀入包含事實(shí)和規(guī)則的文

34、件，并將這些內(nèi)容添加到當(dāng)前規(guī)則數(shù)據(jù)庫末尾。？- link（algol60，L），link（L，M）.L = cplM = bcpl表示：是否存在L和M，使link（algol60，L）and link（L，M）？輸入“；”并回車，Prolog將用另一個(gè)解作為響應(yīng)，或者用“no”說明已經(jīng)無法在找到解。規(guī)則的表示規(guī)則就是horn子句 :- 1, 2, ……, k.:- 左邊的項(xiàng)稱為頭部，在:- 右邊的那些項(xiàng)稱為條件。事實(shí)

35、是規(guī)則的特殊形式，只有頭部而沒有條件。Path(L, L).Path(L, M) :- link(L, X), path(X, M).其中變量X，出現(xiàn)在條件里面，而不在頭部，表示某個(gè)滿足條件的對(duì)象,與Prolog交互,合一 ？- f（X, b） = f（a，Y）.X = aY = b得到項(xiàng)T的實(shí)例方法：用一些項(xiàng)去替換T中的一個(gè)或幾個(gè)變量。同一個(gè)變量的所有出現(xiàn)必須用同一個(gè)項(xiàng)去替換。f（a，b）是f（X，b）的實(shí)例

36、，同理f（a，b）是f（a，Y）的實(shí)例。共同的實(shí)例是f（a，b）。g（a，b）不是g（X，X）的實(shí)例合一是在規(guī)則應(yīng)用時(shí)隱含發(fā)生的。算術(shù)：“=”運(yùn)算符表示合一？- X = 2+3 X = 2+3中綴運(yùn)算符“is”對(duì)表達(dá)式求值：？- X is 2+3 X = 5,Prolog程序結(jié)構(gòu) Prolog程序由子句組成， 子句模型是Horn子句。(1) 事實(shí)與規(guī)則

37、 Prolog程序先定義公理集例：Prolog的規(guī)則和事實(shí) 條件子句(規(guī)則) pretty (X):-artwork(X) pretty (X):-color(X，red)，flower(X). watchout (X):-sharp(X

38、，_). 無條件子句(事實(shí)) color (rose，red). sharp (rose，stem). sharp (holly，leaf). flower(rose).

39、 flower(violet) artwork (painting (Monet， haystack_at_Giverny)).,(2)查詢

40、 Prolog中查詢(query)是要求Prolog證明定理。 因?yàn)樘岢龅膯栴}就是證明過程的目標(biāo),所以查詢也叫目標(biāo)(goal)。例: Prolog的查詢 ?- pretty (rose). yes

41、 ?- pretty (Y). Y=painting (Monet，haystack_at_Giverny). Y=rose. no ?-prett

42、y(W)， sharp(W，Z) W=rose Z=stem no,例: 最大公約數(shù)的歐基里得算法 最大公約數(shù)歐基里得算法可用三條規(guī)則描述: gcd (A，0，A). gcd (A，B，D):-(A>B)，(B>0)，R is A mod B，

43、 gcd(B，R，D). gcd (A，B，D):-(A<B)， gcd (B，A，D).,封閉世界內(nèi)的假設(shè) 如果有某個(gè)子目標(biāo)查遍數(shù)據(jù)庫也找不到能滿足的事實(shí)， 該子目標(biāo)失敗， 但不等于整個(gè)目標(biāo)的失敗。 即使是整個(gè)目標(biāo)最后失敗， 也不等于這個(gè)目標(biāo)追求的命題是否定的， 因?yàn)橄抻跀?shù)據(jù)庫存放的規(guī)則和事實(shí)有限， 它是“封閉

44、世界假說”之下的失敗。,函數(shù)和計(jì)算(1) 函子完成邏輯設(shè)計(jì)中的計(jì)算 函子以結(jié)構(gòu)形式出現(xiàn)， 如: 中綴表示 前綴表示 X+Y*Z +(X，*(Y，Z)) A-B/C -(A，/(B，C)) 故它不是謂詞

45、，僅僅是一特殊的結(jié)構(gòu)： (， …， )函數(shù)求值的的結(jié)果一般通過謂詞is(，)束定到變?cè)蟝cd (A，B，D);-(A>B)，(B>0)，R is A mod B，gcd(B，R，D).把函數(shù)改寫為約束，很容易寫出prolog程序,例 求斐波那契數(shù)的Prolog程序 斐波那契函數(shù)以下述公式生成以下數(shù)列: 1， 1， 2， 3， 5

46、， 8， 13， 21， … Fib(0) = 1 Fib(1) = 1 Fib(n) = Fib(n-1) + Fib(n-2)第一、二式是事實(shí)也是公理，把結(jié)果值作為變?cè)諏憽?第三式說明，若n為斐波那契數(shù)，n-1和n-2的斐波那契必須成立，且這兩個(gè)數(shù)之和是

47、n的斐波那契數(shù)， n>1， 于是有Prolog程序 Fib (0，1). Fib (1，1). Fib (n，f):-Fib(m，g)，F(xiàn)ib(k，h)，m is n-1，k is m-1，

48、 f is g+h， n>1. 當(dāng)有查詢 ?-Fib(5，f)時(shí)， f返回8,(2) 邏輯程序的算法表達(dá) 算法怎樣用公理表達(dá)呢？拿一個(gè)最典型的Quicksort分類程序討論。 quicksort(未分類表，分類完的表):- (從未分類表拿出第一元素,以它為基準(zhǔn),分成兩個(gè)表), [1] quicksort(小表，分類完小

49、表)， [2] quicksort(大表，分類完大表)， [3] append (分類完小表， 基準(zhǔn)元素和分類完大表，分類完總表) [4]這樣把快速分類的總目標(biāo)變成了四個(gè)子目標(biāo),例 快速分類的Prolog代碼 r1

50、 split(_，[ ]，[ ]，[ ] ). r2 split (Pivot，[Head | Tail]，[Head | Sm]，Lg):- Head < Pivot，split (Pivot，Tail，Sm，Lg). r3 split (Pivot，[Head | Tail]，Sm [Head | Lg]):- Pivot &l

51、t; Head，split (Pivot，Tail，Sm，Lg). r4 quicksort ([ ]，[ ]). r5 quicksort ([Head [ ] ]，Head). r6 quicksort ([Pivot | Unsorted] AllSorted):- split (Pivot，Unsorted，Small，Large), quic

52、ksort (Small，SmSorted)， quicksort (Large，Lgsorted), append (SmSorted，[Pivot | LgSorted]，AllSorted).,(3)邏輯和控制分離 Prolog無通常意義的控制結(jié)構(gòu)，也就是該程序動(dòng)作次序（顯然也有）和計(jì)算的子句邏輯沒有必然的關(guān)系。例如:把上例中r4,r5,r6寫在r1,r2,r3前面并不影

53、響本程序的執(zhí)行結(jié)果。,cut和not謂詞 因?yàn)镻rolog的歸結(jié)模型只能完整地證明正命題， 是否有解無法判定 如果明知再作沒有意義，可人為截?cái)郼ut(1) 安全cut 非形式解釋cut， 它如同一籬笆， 由程序員任意置放在規(guī)則

54、之中， 以停止無意義的回溯。,例 安全cut示例：求1到N的整數(shù)之和 r1 sum_to(N，1):-N=1，！. r2 sum_to (N，R):-N1 is N-1，sum_to(N1，R1)，

55、 R is R1 + N.當(dāng)有查詢: ?-sum_to(1，X) //匹配r1 X=1; //打‘;’號(hào)由于有！不致無限 查找第2個(gè)

56、 no ?-sum_to(6，X) //匹配r1失敗， 匹配r2連續(xù)r2 X=21; //直至成功， 打';'號(hào)也不再找 no r1 可用sum_to(1,1).事實(shí)代,(2) cut 實(shí)現(xiàn)n

57、ot操作 r1 not(X):-X，！，fail. r2 not(_).其推理過程是: ·若X為假，匹配r1，在未達(dá)到！時(shí)已失敗，則匹配規(guī)則r2，由于r2什么變?cè)伎梢郧铱倿槌晒?，所以?not(X)是成功的。 · 若X為真，匹配r1后，X為真，控制通過！傳到fail,則r

58、1失敗。 于是回溯到！過不去，只好失敗。由于用了!就地失敗，它不再匹配r2， 故not(X)為失敗。 正是由于這個(gè)原因， 謂詞p和not(not (p))求值結(jié)果不能保證一樣， 有時(shí)not(p)和not(not (p))求值結(jié)果倒是一樣的， 以下是not謂詞出毛病的例子:,例 不可靠的not謂詞 假定一規(guī)則test有以下定義: test (S，T):-S=T. 運(yùn)行以下查詢時(shí)有:

59、 ?-test(3，5). no ?-test(5，5) yes ?-not( test(5，5) )

60、 no ?-test(X，3)，R is X+2. X=3 R=5 ?- not (not test (X，3))， R is X+2. ！ error in arithmetic exp

61、ression : not a number,r1 not(X):-X，！，fail.r2 not(_).由于第二次not(外部的)求值時(shí)用到上例規(guī)則r1， 其中X是not(test(X，3))的結(jié)果值，故X+2不是數(shù)加2。這個(gè)問題原因在于子句邏輯的不可判定性,(3)不安全的cut cut使我們處于兩難的境地， 它的高效是以風(fēng)險(xiǎn)為代價(jià)得到

62、的，如同60年代goto技巧對(duì)非結(jié)構(gòu)化程序的影響。只要模型是超級(jí)歸結(jié)， cut的兩面性是不可以解決的。,6.5 Prolog評(píng)價(jià),Prolog提供一種證明風(fēng)格的聲明式程序設(shè)計(jì)， 推理清晰， 概括能力強(qiáng)， 程序和數(shù)據(jù)沒有明顯分離。Prolog程序具有自文檔性由于非過程性，它也成為潛在的并行程序設(shè)計(jì)語言的候選者它的效率仍不及傳統(tǒng)過程語言。由于它的聲明性質(zhì)， 程序員在優(yōu)化算法時(shí)作用有限復(fù)雜的大型系統(tǒng)一開始很難按照證明系統(tǒng)開發(fā)， 程序不

63、大運(yùn)算量驚人 ， 而Prolog本身也只有局部量， 天生來也不是大型軟件開發(fā)的工具。 因此， Prolog只能作為邏輯程序設(shè)計(jì)的獨(dú)枝存在， 解決大型應(yīng)用多范型語言是個(gè)出路,歸結(jié)練習(xí),已知：某些病人喜歡所有的醫(yī)生(A1) 沒有一個(gè)病人喜歡任意一個(gè)騙子(A2)欲證明：任意一個(gè)醫(yī)生都不是騙子(B)證明：事實(shí)表示：令P（x）：x是病人D（x）：x是醫(yī)生Q（x）：x是騙子L（x，y）：x喜歡yA1： ? x(

64、P(x)∧ ? y(D(y)→ L(x,y)))A2：？ B：？,歸結(jié)練習(xí),P（x）：x是病人D（x）：x是醫(yī)生Q（x）：x是騙子L（x，y）：x喜歡yA1： ? x(P(x)∧ ? y(D(y)→ L(x,y)))A2：? x(P(x)→ ? y(Q(y)→ ?L(x,y)))B： ? x(D(x)→?Q(x))要證明B是A1和A2的邏輯結(jié)果，即公式A1 ∧A2 ∧?B是不可滿足的,歸結(jié)練習(xí),A1= ? x(P(

65、x)∧ ? y(?D(y)→ L(x,y)))A2： ? x(P(x)→ ? y(Q(y)→ ?L(x,y)))B： ? x(D(x)→?Q(x))A1= ? x(P(x)∧ ? y(?D(y)→ L(x,y))) = ? x ? y(P(x)∧(?D(y)→ L(x,y)))---→ ? y(P(a)∧(?D(y)→ L(a,y)))A2=?B=A1 ∧A2 ∧?B的子句集是什么S=,歸結(jié)練習(xí),A1= ?

66、x(P(x)∧ ? y(?D(y)∨L(x,y))) = ? x ? y(P(x)∧(?D(y)∨L(x,y))) ---→ ? y(P(a)∧(?D(y)∨L(a,y)))A2= ? ? x(P(x)→ ? y(?Q(y)∨?L(x,y))) = ? x(?P(x)∨ ? y(?Q(y)∨?L(x,y))) = ? x ? y (?P(x)∨?Q(y)∨?L(x,y))?B= ? (? x(D(x)

67、→?Q(x))) = ? x(?(?D(x)∨?Q(x))) ---→(D(b)∧Q(b))S={P(a), ? D(y)→ L(a,y), ?P(x)∨?Q(y)∨?L(x,y), D(b), Q(b)},歸結(jié)練習(xí),S不可滿足的歸結(jié)演繹序列為：(1)P(a),(2) ?D(y)∨L(a,y),(3) ?P(x)∨?Q(y)∨?L(x,y),(4)D(b)(5)Q(b)(6) ?Q(y)∨?