人工智能謂詞演算

人工智能謂詞演算第1頁，課件共32頁，創(chuàng)作于2023年2月第一節(jié)一階謂詞邏輯命題：凡可確定真假的陳述句稱為命題可以取值“真”（T）或“假”（F）在一定的條件下，只能取其中一個值例：（1）北京是中國的首都√（2）3+2>10

×（3）1+11=100（根據(jù)制數(shù)）（4）禁止吸煙（祈使句）（5）本命題是假的（悖論）2第2頁，課件共32頁，創(chuàng)作于2023年2月謂詞：是用來刻畫個體詞的性質或個體詞之間的關系的詞（帶參量的命題叫謂詞）n元謂詞，P（x1,x2,x3,…,xn）P是謂詞符號，代表一個確定的特征（一個參量）或關系（多個參量）x1,x2,x3,…,xn稱為參量或項（個體常元或個體變元）論述域（個體域）：個體變元的取值范圍例：北京是一個城市——CITY（北京）x是人——HUMAN（x）A是B的兄弟——兄弟（A，B）x大于y——G（x，y）不帶個體變元的謂詞公式叫命題，命題是謂詞公式的特例3第3頁，課件共32頁，創(chuàng)作于2023年2月邏輯連接詞：研究單個謂詞是不夠的，還必須研究多個謂詞之間的關系，這需要引入邏輯連接詞?：否定詞

?A讀為“非A”，當A為真時，?A為假，當A為假時，?A為真∧：合取詞A∧B讀為“A并且B”，當且僅當A和B都為真時，A∧B為真，否則A∧B為假∨：析取詞A∨B讀為“A或者B”，當且僅當A和B都為假時，A∨B為假，否則A∨B為真4第4頁，課件共32頁，創(chuàng)作于2023年2月→：蘊涵詞A→B讀為“若A則B”，當且僅當A為真，且B為假時，A→B為假，否則A→B為真在A→B中，A稱為前件，B稱為后件：等值詞AB讀為“A等值于B”，當且僅當A和B同為真或同為假時，AB為真，否則AB為假5第5頁，課件共32頁，創(chuàng)作于2023年2月量詞：有些陳述句包含表示數(shù)量的詞，如“所有”、“任一”、“存在”、“至少有一個”等，為了表示這樣的陳述句，需引入新的符號，稱為量詞全稱量詞（

x）表示“對于所有的x…”例：凡是人都有名字——（

x）（M（x）→N（x））（

x）A（x）

A（a1）∧A（a2）∧…∧A（an），若論域為有限集合，且a1、a2、…

、an是論域中的所有個體存在量詞（

x）表示“對于某個x…”例：存在不是偶數(shù)的整數(shù)——（

x）（G（x）∧?E（x））（

x）A（x）

A（a1）∨A（a2）∨…∨A（an）例：見P56例1—36第6頁，課件共32頁，創(chuàng)作于2023年2月項：（P64定義1）（1）個體常元和個體變元都是項（2）f(t1,t2,…,tn)是項，f是n元函數(shù)，t1,t2,…,tn是項（3）只有有限次使用（1）、（2）得到的符號串才是項原子公式：（P64定義2）設P為n元謂詞符號，t1,t2,…,tn是項，則P（t1,t2,…,tn）稱為原子謂詞公式，簡稱原子公式7第7頁，課件共32頁，創(chuàng)作于2023年2月謂詞公式：（P56定義3）（1）原子公式是謂詞公式（2）若A、B是謂詞公式，則A∧B、A∨B、?A、A→B、AB、

xA、

xA也是謂詞公式（3）只有有限次應用（1）、（2）生成的公式才是謂詞公式謂詞公式又稱為謂詞邏輯中的合式公式，記為Wff(well-formedformula)幾個概念：轄域（P57）：緊接于量詞之后被量詞作用的（說明的）謂詞公式稱為該量詞的轄域指導變元、約束變元和自由變元（P57）改名規(guī)則（P57），保證一個變元或者是約束變元，或者是自由變元例：

x（H（x）→G（x,y））∧

xA（x）∧B（x）8第8頁，課件共32頁，創(chuàng)作于2023年2月合取范式：（P58定義4）A為合取范式，B1∧B2∧…∧Bn,其中Bi形如L1∨

L2∨…∨Lm,Lj為原子公式或其否定例：（P（x）∨

Q（y））∧（?

P（x）∨

Q（y）∨

R（x，y））∧…任一謂詞公式均可化為與之等價的合取范式，但一般不唯一析取范式：（P66定義5）A為析取范式，B1∨B2∨…∨Bn,其中Bi形如L1∧

L2∧…∧Lm,Lj為原子公式或其否定例：（P（x）∧

Q（y））∨（?

P（x）∧

Q（y）∧

R（x，y））∨…任一謂詞公式均可化為與之等價的析取范式，但一般不唯一9第9頁，課件共32頁，創(chuàng)作于2023年2月謂詞公式的永真（有效）、永假（不可滿足）、可滿足：（P58定義6、7）與個體域有關謂詞公式之間的關系常用邏輯等價式P59表3.1注意與的區(qū)別，是等價符號，說明兩個謂詞公式之間的等價性，是邏輯連接詞，是謂詞公式的組成部分

常用邏輯蘊涵式P60表3.2注意與的區(qū)別，是推導符號，說明由左邊的謂詞公式可以推導出右邊的謂詞公式，是邏輯連接詞，是謂詞公式的組成部分

10第10頁，課件共32頁，創(chuàng)作于2023年2月自然演繹推理：（1）將自然語言命題轉化為謂詞公式（2）利用上面的邏輯等價式和邏輯蘊涵式，可以進行推理，得出一些隱含在謂詞公式中的結論例：P61例4-6自然演繹推理實施困難，推理規(guī)則太多、應用規(guī)則需要很強的模式識別能力、中間結論呈指數(shù)增長引入新的推理技術——歸結演繹推理技術歸結——消解（Resolution），由Robinson于1965年提出，大大推動了自動定理證明的發(fā)展11第11頁，課件共32頁，創(chuàng)作于2023年2月練習：1、設已知以下事實：

A B A→C B∧C→D D→Q

求證：Q為真。12第12頁，課件共32頁，創(chuàng)作于2023年2月

證明： 因為

A，A→CC B，CB∧C B∧C，B∧C→DD D，D→QQ

所以 Q為真13第13頁，課件共32頁，創(chuàng)作于2023年2月2、設已知如下事實： （1）凡是容易的課程小王都喜歡。 （2）C班的課程都是容易的。 （3）ds是C班的一門課程。

求證：小王喜歡ds這門課程。14第14頁，課件共32頁，創(chuàng)作于2023年2月

證明： 事實

x（EASY（x）→LIKE（Wang，x））

x（C（x）→EASY（x））

C（ds）

LIKE（Wang，ds） 因為

x（C（x）→EASY（x）） 所以 C（ds）→EASY（ds） 所以 C（ds），C（ds）→EASY（ds）

EASY（ds） 因為

x（EASY（x）→LIKE（Wang，x）） 所以 EASY（ds）→LIKE（Wang，ds） 所以 EASY（ds），EASY（ds）→LIKE（Wang，ds）

LIKE（Wang，ds）15第15頁，課件共32頁，創(chuàng)作于2023年2月第二節(jié)歸結演繹推理建立子句集文字、子句、空子句（P62定義1）建立謂詞公式G的子句集合（P62定義2）例：P62例3.7例：P63例2有關消去存在量詞子句集中各子句的關系是合取∧

經(jīng)過變換后的子句集S，與謂詞公式G并不等價子句集的不可滿足（P64定義3）G不可滿足當且僅當S不可滿足（P64定理1），即G永假是S永假的充分必要條件16第16頁，課件共32頁，創(chuàng)作于2023年2月練習：

P931、（1）{p(x,y),Q(u,v)}（2）{?p(x,y)∨Q(x,y)}（3）{P(x,f(x))∨?Q(x,f(x))∨R(x,f(x))}（4）{?P(x,z)∨Q(x,y)∨R(x,y)}（5）{P(a,b,z,f(z),v,g(z,v)), Q(a,b,f(t),s,g(t,s))∨?R(a,t,g(t,s))}17第17頁，課件共32頁，創(chuàng)作于2023年2月命題邏輯中的歸結原理在定理證明系統(tǒng)中，已知一公式集F1，F(xiàn)2，…，F(xiàn)n，要證明W（定理）是否成立，即要證明W是公式集的邏輯結果，有兩種方法：1、證明F1∧

F2∧…∧Fn→W為永真式（見上一節(jié)）2、（反證法）證明F1∧

F2∧…∧Fn∧

?

W永假，即要證明對應子句集永假（不可滿足）幾個概念：（P64定義4、5）互補文字、歸結式（消解式）、親本子句、消解基例：例3.9歸結式是其親本子句的邏輯結果P64定理2單向推導關系18第18頁，課件共32頁，創(chuàng)作于2023年2月歸結原理：C1∧C2

（C1-{L1}）∨（C2-{L2}）互補文字進行歸結得空子句（L∧?

L=?），另L∧?

L=F（假），故空子句即永假子句關于消解前后子句集的可滿足性——P65推論（證明略）故：要證明一子句集永假，可以通過對子句集應用消解原理得到空子句來證明運用歸結原理證明定理的例子：P65例11、12*歸結過程可以用一棵歸結演繹樹表示19第19頁，課件共32頁，創(chuàng)作于2023年2月替換與合一為了對謂詞邏輯的子句集運用消解原理，即在子句集合中尋找含互補文字的子句對，必須對子句進行替換合一操作替換：P66定義6{t1/x1，t2/x2，…，tn/xn}對表達式的替換過程P66定義7表達式——項、原子公式、文字、子句兩個替換的乘積P66-67定義8一部分仍是θ的替換對，只是θ的項被λ作了替換；另一部分是λ中與θ不同的那些變量對例：例3.13替換的乘積滿足結合律20第20頁，課件共32頁，創(chuàng)作于2023年2月合一：P67定義9θ是S的一個合一其中S是一個原子謂詞公式集，θ是一個替換滿足F1θ=F2θ=…=Fnθ一個公式集的合一一般不唯一最一般的合一：P67定義10σ是S的一個合一對于S的任何一個合一θ，存在替換λ，使θ=σ?λ稱σ為S的最一般（最普通、最簡單）合一MGU例：例3.14MGU的替換限制最少，所產(chǎn)生的例更一般化，這有利于歸結過程的靈活使用一個公式集的最一般合一也可不唯一，如{P（x），P（y）}，{y/x}、{x/y}都是它的最一般合一21第21頁，課件共32頁，創(chuàng)作于2023年2月差異集：P67定義11針對具有相同謂詞名的原子公式集例：例3.15合一算法：求非空有限具有相同謂詞名的原子公式集的最一般合一P67-68合一算法是解決兩個表達式匹配的問題，兩個表達式都可以含有變量，通過算法求得MGU并進行替換后就可以得到匹配的例例：例16、17合一定理：P68-69定理3可合一公式集一定存在最一般合一，用上述合一算法求得22第22頁，課件共32頁，創(chuàng)作于2023年2月謂詞邏輯中的歸結原理歸結過程：若S中的兩子句間有相同互補文字的謂詞，但它們的項不同，則必須找出對應的不一致項進行變量替換合一操作，使它們的對應項一致求歸結式看能否導出空子句幾個概念：（P69定義12）謂詞邏輯中的二元歸結式（二元消解式）、親本子句、消解文字例：例18、19子句用文字的集合表示，各文字之間的關系是析取∨首先對子句內部的可合一文字進行合一23第23頁，課件共32頁，創(chuàng)作于2023年2月因子、單因子（P69定義13）例：例14子句的歸結（消解）式（P69定義14）定理：謂詞邏輯中的消解式是它的親本子句的邏輯結果謂詞邏輯中的歸結原理：C1∧C2

（C1σ-{L1σ}）∪（

C2σ-{L2σ}）關于消解前后子句集的可滿足性——P70（同命題邏輯）故：要證明F1∧

F2∧…∧Fn→W為永真式，可證明F1∧

F2∧…∧Fn∧

?

W永假，這又可以通過對對應子句集應用消解原理得到空子句來證明（同命題邏輯）24第24頁，課件共32頁，創(chuàng)作于2023年2月例：例15、16定理：歸結原理的完備性（P71）練習：

P933、（1）-（5）25第25頁，課件共32頁，創(chuàng)作于2023年2月第三節(jié)歸結原理的應用例3.23：P71例3.24：P72練習：

P945、6、26第26頁，課件共32頁，創(chuàng)作于2023年2月歸結策略計算機實現(xiàn)歸結原理的一般算法：

1.將子句集S置入CLAUSES表；

2.若空子句NIL在CLAUSES中，則歸結成功，結束。

3.若CLAUSES中存在可歸結子句對，則歸結之，并將歸結式放入CLAUSES中；

4.歸結失敗，退出。歸結策略的完備性策略：刪除策略、支持集策略、線性歸結策略、輸入歸結策略、單元歸結策略、祖先過濾形策略。27第27頁，課件共32頁，創(chuàng)作于2023年2月歸結舉例Sam、Clyde和Oscar是大象。關于它們，我們知道以下事實：1）Sam是粉紅色的；2）Clyde是灰色的且喜歡Oscar；3）Oscar是粉紅色或者是灰色（但不是兩種顏色）且喜歡Sam。用歸結法證明一個灰色大象喜歡一個粉紅色大象。即證明：xy[Gray(x)∧Pink(y)∧Likes(x,y)]?

∧∨謂詞： Gray(x),Pink(x),Like（x,y）事實： 1）Pinky(Sam) 2）Gray(Clyde)∧Like(Clyde,Oscar) 3）(Gray(Oscar)∨Pink(Oscar))∧Likes(Oscar,Sam)28第28頁，課件共32頁，創(chuàng)作于2023年2月子句集：1）Pink(Sam) 2）Gray(Clyde) 3）Like(Clyde,Oscar) 4）Gray(Oscar)∨Pink(Oscar) 5）Likes(Oscar,Sam) 6）

?

Gray(x)∨?

Pink(y)∨

?

Likes(x,y)歸結： 7）?

Gray(Oscar)∨

?

Pink(Sam) 5，6得 8）?

Gray(Clyde)∨

?

Pink(Oscar) 3，6得 9）Pink(Oscar)∨?

Pink(Sam) 4，7得

10）?

Pink(Oscar)