人工智能與專家系統(tǒng)第2章知識表示方法課件

1、人工智能與專家系統(tǒng)第2章 知識表示方法2.1 一階謂詞邏輯表示方法2.2 產(chǎn)生式表示方法 知識表示是對知識的一種描述，或者說是一組約定，是一種計(jì)算機(jī)可以接受的用于描述知識的數(shù)據(jù)結(jié)構(gòu)。 知識外部表示模式：是與軟件開發(fā)與運(yùn)行的軟件工具與平臺無關(guān)的知識表示的形式化描述。 知識內(nèi)部表示模式：是與開發(fā)軟件工具與平臺有關(guān)的知識表示的存儲結(jié)構(gòu)。2.1 一階謂詞邏輯表示方法2.1.1 一階謂詞邏輯2.1.2 一階謂詞邏輯表示方法2.1.1 一階謂詞邏輯1 命題 命題是具有真假意義的語句。命題代表人們進(jìn)行思維時(shí)的一種判斷，或者是肯定，或者是否定。它取的真值為真或假，記為T或F。謂詞 在謂詞邏輯中，命題是用謂詞來

2、表示的。 謂詞:謂詞可分為謂詞名與個體兩部分，個體表示某個獨(dú)立存在的事物或者某個抽象謂詞的概念，謂詞名用于刻畫個體的性質(zhì)、狀態(tài)或個體間的關(guān)系。 一階謂詞的一般形式為： P（x1, x2, , xn）其中，P是謂詞名，x1, x2 , xn 是個體。 個體變元的取值范圍稱為個體域。 在謂詞P（x1, x2, , xn）中，若xi都是個體常量，變元或函數(shù)，i=1,2,n，則稱它為一階謂詞，若某個xi本身又是一個一階謂詞，則稱P為二階謂詞。 一階謂詞中的個體可以是常量，也可以是變元，還可以是一個函數(shù)。個體常量，個體變元、函數(shù)統(tǒng)稱為“項(xiàng)”。如：Teacher(father(Wang) father(W

3、ang)是一個函數(shù)，它是謂詞Teacher的個體。 Less(x,5) 代表x5謂詞與函數(shù)的區(qū)別：謂詞的真值是真或假而函數(shù)是一個個體到另一個個體的映射，無真值。 規(guī)定：謂詞名或謂詞名的第一個字符用大寫字符表示，項(xiàng)中的常量（或常量的第一個字符）用大寫字符表示，項(xiàng)中的變元和函數(shù)名（或函數(shù)名的第一個字符）以及函數(shù)的變元都用小寫字符表示。謂詞公式 （1）連詞 非連詞 或連詞：用連接兩個命題稱為析取。 與連詞：用連接兩個命題稱為合取。 蘊(yùn)合連詞：它表示 “如果P，則Q”，其中P稱為前件，Q稱為后件。 （2）量詞 全稱量詞（ x）：表示對個體域 X 中的所有（或任一個）個體 x 。 存在量詞（ x ）：表

4、示在個體域X中存在個體 x 。 例：若謂詞P(x )表示x是正數(shù)，F(xiàn)(x,y)表示x與y是朋友，則：( x)P(x )表示個體域X中的所有個體x 都是正數(shù)。( x )( y)F(x ,y)表示對于個體域X中的任何個體x ，在個體域Y中都存在個體y，x 與y是朋友。( x )( y)F(x ,y)表示在個體域X中存在個體x ，他與個體域Y中的任何個體y都是朋友。( x )( y)F(x ,y)表示在個體域X中存在個體x 和在個體域Y中存在個體y， x 與y是朋友。 （3）謂詞公式 由下述規(guī)則得到的謂詞公式稱為合式公式： 單個謂詞和單個謂詞的否定稱為原子謂詞公式，原子謂詞公式是合式公式。 若A是合

5、式公式，則A也是合式公式。 若A、B都是合式公式，則AB、AB、AB也都是合式公式。 若A是合式公式， x 是任一個體變元，則 ( x )A和( x )A也都是合式公式。 在合式公式中，連詞的優(yōu)先級別依序?yàn)椋?，4 謂詞公式的解釋 在命題邏輯中，對命題公式中各個命題的一次真值指派稱為命題公式的一個解釋。一個謂詞公式的解釋可能有很多個。對于每一個解釋，謂詞公式都可求出一個真值（T或F）。例2.1 設(shè)變元x和y的個體域是D=1，2，謂詞P（ x ，y）表示x 大于等于y，給出公式A=( x)( y)P(x ,y)在D上的解釋，指出每一種解釋下公式A的真值。 解：設(shè)對謂詞P（ x , y）在個體域D

6、上的真值指派為：P(1,1)=T， P(1,2)=F， P(2,1)=T， P(2,2)=T這就是公式A在D上的一個解釋。 在此解釋下，因?yàn)閤 =1時(shí)有y=1使P(x ,y)的真值為T， x =2時(shí)也有y=1使P(x ,y)的真值為T，即x 對于D中的所有取值，都存在y=1，使P(x ,y)的真值為T，所以在此解釋下公式A的真值為T。 例2.2 設(shè)個體域D=1,2，給出公式 R=( x )(P(x )Q(f(x ),B)在D上的一個解釋，指出公式R在此解釋下的真值。 解：設(shè)對個體常量B指派D中的一個元素為B=1，對函數(shù)f (x)指派到D的映射為： f (1)=2，f (2)=1 設(shè)對謂詞指派的

7、真值為：P(1)=F，P(2)=T，Q(1,1)=T，Q(2,1)=F 由于已對個體常量B指派B=1，所以Q(1,2)與Q(2,2)不可能出現(xiàn)，故沒有給它們指派真值。 上述指派就是對公式R的一個解釋。在此解釋下，由于當(dāng) x =1時(shí)，有 P(1)=F，Q(f (1),1)=Q(2,1)=F所以P(1)Q(f (1),1)的真值為T。 當(dāng) x =2時(shí)，有 P(2)=T, Q(f (2),1)=Q(1,1)=T所以P(2)Q(f (2),1)的真值也為T。 即對個體域D中的所有 x 都有 P(x )Q(f (x ),B)的真值為T。所以公式R在此解釋下的真值為T。 可見：謂詞公式的真值是針對某一個解

8、釋而言的，它可能在某一個解釋下的真值為T，在另一個解釋下的真值為F。5 謂詞公式的永真性、可滿足性、不可滿足性 定義2.2: 如果謂詞公式P對個體域D上的任何一個解釋都取得真值T，則稱公式P在域D上是永真的。如果P在每個非空個體域上均永真，則稱P是永真的。 可見：為了判定某個公式永真，必須對每個個體域上的每一個解釋逐一判定公式的真值。 定義2.3 : 對于謂詞公式P，如果至少存在一個解釋使得公式P在此解釋下的真值為T，則稱公式P是可滿足的。 定義2.4 :如果謂詞公式P對于個體域D上的任何一個解釋都取得真值F，則稱公式P在域D上是永假的。如果P在每個非空個體域上均永假，則稱P是永假的。 謂詞公

9、式的永假性又稱為不可滿足性。 6 謂詞公式的等價(jià)性 定義2.5: 設(shè)P與Q是兩個謂詞公式，D是它們共同的個體域，若對D上的任何一個解釋，P與Q都有相同的真值，則稱公式P和Q在D上是等價(jià)的。如果D是任意的個體域，則稱P和Q是等價(jià)的。記為P Q。主要的等價(jià)式: （1）交換律 PQ QP PQ QP（2）結(jié)合律 (PQ)R P(QR) (PQ)R P(QR)（3）分配律 P(QR) (PQ)(PR) P(QR) (PQ) (PR)（4）狄摩根律 (PQ) PQ (PQ) PQ（5）雙重否定律 P P（6）吸收律 P(PQ) P P(PQ) P（7）補(bǔ)余律 P P T P P F（8）連詞化歸律 PQ

10、 PQ（9）量詞轉(zhuǎn)換律 （ x）P ( x ) (P) （ x）P ( x ) (P) (10) 量詞分配律 ( x )(PQ) ( x )P( x ) Q ( x )(PQ) ( x )P( x )Q謂詞公式的永真蘊(yùn)含 定義2.6 : 對于謂詞公式P和Q，如果PQ永真，則稱P永真蘊(yùn)含Q，且稱Q為P的邏輯結(jié)論，稱P為Q的前提，記為P Q。 8 推理規(guī)則、定理與證明 推理規(guī)則用來由已知的合式公式推導(dǎo)出新的合式公式。導(dǎo)出的合式公式稱為定理，而所使用的推理規(guī)則的序列則構(gòu)成該定理的一個證明。2.1.2 一階謂詞邏輯表示方法 1 一階謂詞邏輯表示方法 用謂詞公式表示知識時(shí)，應(yīng)按以下步驟進(jìn)行： (1)定義

11、謂詞，給出每個謂詞的確切含義； (2)用連詞把有關(guān)謂詞連接起來表示一個更復(fù)雜的含義； (3)對謂詞公式中的變元，根據(jù)知識表示的需要，把需要約束的變元用相應(yīng)的量詞予以約束。 例2.3 用謂詞公式表示下列知識： 王林是計(jì)算機(jī)系的學(xué)生，但他不喜歡編程序。人人愛勞動。解： （1） 定義謂詞COMPUTER（x） 表示 x 是計(jì)算機(jī)系的學(xué)生LIKE（x ,y） 表示 x 喜歡yLOVE(x ,y) 表示 x 愛yMAN（x） 表示 x 是人（2）謂詞公式知識表示COMPUTER（Wang Lin）LIKE(Wang Lin,Programing)( x)(MAN(x)LOVE( x，Labour) 例2

12、.4 用謂詞公式表示下列知識： 自然數(shù)是大于零的整數(shù)。 所有整數(shù)不是偶數(shù)就是奇數(shù)。 偶數(shù)除以2是整數(shù)。解： （1） 定義謂詞 N(x )表示 x 是自然數(shù) I(x )表示 x 是整數(shù) E(x )表示 x 是偶數(shù) O(x )表示 x 是奇數(shù) GZ(x )表示 x 大于零（2）謂詞公式知識表示 ( x ) (N(x )GZ (x )I (x ) ( x ) (I (x )E (x )O (x ) ( x ) (E (x )I (f (x ) 其中，函數(shù)f (x )= x /2。例2.5 已知F1：王（Wang）先生是小李（Li）的老師。F2：小李與小張（Zhang ）是同班同學(xué)。F3：如果 x與y

13、是同班同學(xué)，則 x 的老師也 是y 的老師。 求：小張的老師是誰？解： （1） 定義謂詞 T(x , y) x是y的老師。 C(x , y) x與y是同班同學(xué)。 （2）謂詞公式知識表示（已知前提及待求解問題）F1：T (Wang , Li)F2：C (Li, Zhang )F3：( x )( y)( z)(C (x , y)T(z, x ) T(z , y)G ： ( x )T(x , Zhang )例2.6 設(shè)A，B，C三人中有人從不說真話，也有人從不說假話，某人向這三人分別提出同一個問題：誰是說謊者？A答：“B和C都是說謊者”；B答：“A和C都是說謊者”；C答：“A和B中至少有一個是說謊者

14、”。求誰是老實(shí)人，誰是說謊者？解：（1） 定義謂詞 T(x ) 表示 x 說真話。 （2）謂詞公式知識表示 如果A說的是真話，則有 T(A) T(B) T(C) 如果A說的是假話，則有 T(A) T(B)T(C) 對B和C說的話作相同的處理，可得： T(B) T(A) T(C) T(B) T(A)T(C) T(C ) T(A) T(B) T(C ) T(A) T(B)一階謂詞邏輯表示方法的優(yōu)點(diǎn) （1）自然性 （2）精確性 （3）嚴(yán)密性 （4）容易實(shí)現(xiàn)一階謂詞邏輯表示方法的局限性 （1）不能表示不確定性的知識 （2）組合爆炸 （3）效率低2.2 產(chǎn)生式表示方法2.2.1 產(chǎn)生式與產(chǎn)生式系統(tǒng)2.2

15、.2 產(chǎn)生式系統(tǒng)的分類及其特點(diǎn)2.2.1 產(chǎn)生式與產(chǎn)生式系統(tǒng)1、產(chǎn)生式的基本形式 產(chǎn)生式基本形式是：PQ 或者 if P then Q 蘊(yùn)含式與產(chǎn)生式的差別： 蘊(yùn)含式只能表示精確知識；產(chǎn)生式可以表示精確知識，也可以表示不精確知識。 蘊(yùn)含式要求匹配是精確的；產(chǎn)生式匹配可以是精確的，也可以是不精確的。2 、產(chǎn)生式系統(tǒng) 產(chǎn)生式系統(tǒng)：把一組產(chǎn)生式放在一起，并讓它們互相配合，協(xié)同作用，一個產(chǎn)生式生成的結(jié)論可以供另一個產(chǎn)生式作為已知事實(shí)使用，以求得問題的解決。（1）規(guī)則庫 用于描述相應(yīng)領(lǐng)域內(nèi)知識的產(chǎn)生式集合稱為規(guī)則庫。建立規(guī)則庫時(shí)應(yīng)該注意以下問題：1）有效地表達(dá)領(lǐng)域知識2）對知識進(jìn)行合理的組織與管理 例2

16、.7 建立一個動物識別系統(tǒng)的規(guī)則庫，用以識別虎、豹、斑馬、長頸鹿、企鵝、鴕鳥、信天翁等7種動物。解： 為了識別這些動物，可以根據(jù)動物識別的特征，建立包含下述規(guī)則的規(guī)則庫：R1：if 動物有毛發(fā) then 動物是哺乳動物R2：if 動物有奶 then 動物是哺乳動物R3：if 動物有羽毛 then 動物是鳥R4：if 動物會飛 and 會生蛋 then 動物是鳥R5：if 動物吃肉 then 動物是食肉動物R6：if 動物有犀利牙齒 and 有爪 and 眼向前方 then 動物是食肉動物R7：if 動物是哺乳動物and有蹄then動物是有蹄類動物R8：if 動物是哺乳動物 and 反芻 the

17、n 動物是有蹄類動物R9：if 動物是哺乳動物 and 是食肉動物 and 有黃褐色 and 有暗斑點(diǎn) then 動物是豹R10：if 動物是哺乳動物 and 是食肉動物 and 有黃褐色 and 有黑色條紋 then 動物是虎R11：if 動物是有蹄類動物 and 有長脖子and 有長腿 and 有暗斑點(diǎn) then 動物是長頸鹿R12：if 動物是有蹄類動物 and 有黑色條紋 then 動物是斑馬R13：if 動物是鳥 and 不會飛 and 有長脖子 and 有長腿 and 有黑白二色 then 動物是鴕鳥R14：if 動物是鳥 and 不會飛 and 會游泳 and 有黑白二色 the

18、n 動物是企鵝R15：if 動物是鳥 and 善飛 then 動物是信天翁（2）綜合數(shù)據(jù)庫 綜合數(shù)據(jù)庫又稱為全局?jǐn)?shù)據(jù)庫，或稱為事實(shí)庫、黑板。用于存放問題求解過程中各種當(dāng)前信息，例如問題的初始事實(shí)、原始證據(jù)、推理中得到的中間結(jié)論以及最終結(jié)論。綜合數(shù)據(jù)庫的內(nèi)容隨著推理的進(jìn)行是在不斷動態(tài)變化的。（3）控制機(jī)構(gòu) 控制機(jī)構(gòu)又稱為推理機(jī)構(gòu)或推理機(jī)，由一組程序組成，實(shí)現(xiàn)對問題的推理求解。推理機(jī)主要功能為：1）按某種策略從規(guī)則庫中選擇規(guī)則與綜合數(shù)據(jù)庫中的已知事實(shí)進(jìn)行匹配。匹配成功的規(guī)則稱為可用規(guī)則，不成功則相應(yīng)的規(guī)則不可用于當(dāng)前的推理。2）若匹配成功的可用規(guī)則有多條，此時(shí)推理機(jī)必須執(zhí)行某種沖突消解策略，從中選

19、擇一條可用規(guī)則來執(zhí)行。3）在執(zhí)行某一條規(guī)則時(shí)，若該規(guī)則的后件是一個或多個結(jié)論，則把這些結(jié)論添加到綜合數(shù)據(jù)庫中；若規(guī)則的后件是一個或多個操作，則依次執(zhí)行這些操作。4）對于不確定知識，在執(zhí)行每一條規(guī)則時(shí)還要按一定的算法來計(jì)算結(jié)論的不確定性。5）隨時(shí)檢查結(jié)束推理機(jī)運(yùn)行的條件，在滿足結(jié)束條件時(shí)停止推理機(jī)的運(yùn)行。2.2.2 產(chǎn)生式系統(tǒng)的分類及其特點(diǎn)1 可交換的產(chǎn)生式系統(tǒng) 如果一個產(chǎn)生式系統(tǒng)對規(guī)則的使用次序是可交換的，無論先使用哪一條規(guī)則都可達(dá)到目的，即規(guī)則的使用次序?qū)栴}的最終求解是無關(guān)緊要的，則稱為可交換的產(chǎn)生式系統(tǒng)。例：設(shè)DB的初始狀態(tài)是A,B,C，并設(shè)RB中有下述規(guī)則：R1：if A, B, C then A, B, C, ABR2： if A, B, C then A, B, C, BCR3:：if A, B, C then A, B, C, AC 推理終止條件是綜合數(shù)據(jù)庫DB中的內(nèi)容變?yōu)椋篈, B, C, AB, BC, AC 三條規(guī)則各被使用一次后就可達(dá)到目的，且與規(guī)則使用的次序無關(guān)。所以由上述RB和DB構(gòu)成的產(chǎn)生式系統(tǒng)是一個可交換的產(chǎn)生式系統(tǒng)。 在可交換產(chǎn)生式系統(tǒng)中，綜合數(shù)據(jù)庫DB中的內(nèi)容是遞增的，即對任意一個規(guī)則執(zhí)