第3章 確定性推理方法

人工智能原理及應用第3章確定性推理方法PrinciplesandApplicationsofArtificialIntelligence知識表示：將知識以某種模式存儲到計算機中。智能：知識能力+思維能力（運用知識求解問題）推理：計算機的邏輯思維第3章確定性推理方法3.1 推理的基本概念

3.2 自然演繹推理

3.3 謂詞公式轉(zhuǎn)換為子句集3.4消解原理

3.5 歸結(jié)反演

3.1推理的基本概念

推理

已知事實（證據(jù)）已有知識新的事實（結(jié)論）3.1推理的基本概念推理方式演繹推理(deductivereasoning)

由一般到個別大前提:BC小前提:AB

三段論:AC3.1推理的基本概念推理方式演繹推理(deductivereasoning)

由一般到個別大前提:計算機學院的學生都會編程序小前提:李強是一名計算機學院的學生結(jié)論:李強會編程序3.1推理的基本概念推理方式演繹推理(deductivereasoning)歸納推理(inductivereasoning)

由個別到一般

A的所有實例具有X屬性(完全歸納)結(jié)論:A具有X屬性3.1推理的基本概念推理方式演繹推理(deductivereasoning)歸納推理(inductivereasoning)

由個別到一般檢查某廠的所有產(chǎn)品均合格(完全歸納)結(jié)論:該廠的產(chǎn)品合格3.1推理的基本概念推理方式演繹推理(deductivereasoning)歸納推理(inductivereasoning)

由個別到一般

A的部分實例具有X屬性(部分歸納)結(jié)論:A具有X屬性3.1推理的基本概念推理方式演繹推理(deductivereasoning)歸納推理(inductivereasoning)

由個別到一般抽查某廠的一部分產(chǎn)品合格(部分歸納)結(jié)論:該廠的產(chǎn)品合格3.1推理的基本概念推理方式演繹推理(deductivereasoning)歸納推理(inductivereasoning)

由個別到一般

A具有X屬性

B與A類似(類比歸納)結(jié)論:B具有X屬性3.1推理的基本概念推理方式演繹推理(deductivereasoning)歸納推理(inductivereasoning)

由個別到一般軟件工程專業(yè)的學生都會編程序計算機科學與技術(shù)與軟件工程專業(yè)方向類似(類比歸納)結(jié)論:計算機科學與技術(shù)專業(yè)的學生都會編程序3.1推理的基本概念推理方式演繹推理(deductivereasoning)歸納推理(inductivereasoning)缺省推理(defaultreasoning)

知識不完全的情況下的推理

AB沒有證據(jù)證明A結(jié)論:B3.1推理的基本概念推理方式演繹推理(deductivereasoning)歸納推理(inductivereasoning)缺省推理(defaultreasoning)

知識不完全的情況下的推理未滿18歲不能進入營業(yè)性網(wǎng)吧不知道學生李強的真實年齡李強不能進入營業(yè)性網(wǎng)吧3.1推理的基本概念推理方式確定性推理:證據(jù)和知識都是確定的——結(jié)論也是確定的不確定性推理:證據(jù)和知識不都是確定——結(jié)論也是不確定的

已知事實（證據(jù)）已有知識新的事實（結(jié)論）3.1推理的基本概念推理方式單調(diào)推理:從證據(jù)不斷接近結(jié)論非單調(diào)推理:可能推翻已有的結(jié)論

已知事實（證據(jù)）已有知識新的事實（結(jié)論）3.1推理的基本概念推理方式啟發(fā)式推理:推理過程中運用了啟發(fā)式知識非啟發(fā)式推理

已知事實（證據(jù)）已有知識新的事實（結(jié)論）3.1推理的基本概念推理的方向正向推理:從已知事實出發(fā)，逐步嘗試推導出結(jié)論，或證明問題無解Y3.1推理的基本概念推理系統(tǒng)的基本要素知識庫數(shù)據(jù)庫推理機3.1推理的基本概念正向推理事實:AB知識:ACD

BEF目標:CF3.1推理的基本概念正向推理事實:P(x,y)(Q(x)R(v,y))知識:P(u,v)(S(u)N(v))目標:S(x)N(y)Q(x)推理示例知識庫平均績點超過4.5分的學生，授予一等獎學金評為優(yōu)秀研究生的學生，平均績點不能少于4分事實10名學生中，3人績點超過4.5，其余績點均低于4目標結(jié)論評為優(yōu)秀研究生的學生都獲得了一等獎學金獲得了一等獎學金的學生都被評為優(yōu)秀研究生推理示例g(x)>4.5g(x)<4g(x)>4.5∨g(x)<4g(x)>4.5A(x)g(x)<4E(x)A(x)E(x)E(x)A(x)推理示例如何對事實進行合理的歸納？如何選擇事實的推理順序？3.1推理的基本概念推理的方向正向推理:從已知事實出發(fā)，逐步嘗試推導出結(jié)論，或證明問題無解逆向推理:從假設(shè)目標出發(fā)，逐步嘗試找出其證據(jù)，或證明問題無解推理示例知識庫4個嫌疑犯中有一個是小偷，且4人中只有一個說假話事實A說“我不是小偷”B說“C是小偷”C說“D是小偷”D說“C說謊”問題：請問誰是小偷？推理示例如何選擇假設(shè)的驗證順序？3.1推理的基本概念推理的方向正向推理:從已知事實出發(fā)，逐步嘗試推導出結(jié)論，或證明問題無解逆向推理:從假設(shè)目標出發(fā)，逐步嘗試找出其證據(jù)，或證明問題無解混合推理3.1推理的基本概念沖突：已知事實可與知識庫中的多條知識匹配沖突消解按針對性排序按事實新鮮性排序按匹配度排序按條件個數(shù)排序3.2自然演繹推理命題公式及其等價式（1）雙重否定律：

（2）交換律：

（3）結(jié)合律：

（4）分配律：

（5）摩根定律：

~(P∨Q)~P∧~Q~(P∧Q)~P∨~Q3.2自然演繹推理命題公式及其等價式（6）吸收律：

（7）補余律:（8）連詞化歸律:

（9）量詞轉(zhuǎn)換律:

（10）量詞分配律:P<->Q)(P∧Q)∨(~Q∧~P)3.2自然演繹推理永真蘊含式

（1）化簡式：

（2）附加式：

（3）析取三段論：

（4）假言推理：

（5）拒取式：

3.2自然演繹推理永真蘊含式

（6）假言三段論：

（7）二難推理：

（8）全稱固化：

其中，y是個體域中的任一個體，依此可消去謂詞公式中的全稱量詞。（9）存在固化：

其中，y是個體域中某一個可以使

P(y)為真的個體，依此可消去謂詞公式中的存在量詞。3.3謂詞公式轉(zhuǎn)換為子句集文字:原子公式或其否定子句:文字的析取式謂詞:子句的合取式3.3謂詞公式轉(zhuǎn)換為子句集文字:原子公式或其否定子句:文字的析取式謂詞:子句的合取式消去連接詞“→”和“?”把否定符號“～”移到每個謂詞符號的前面變量標準化（使不同量詞約束的變量有不同的名字）引入Skolem函數(shù)消去存在量詞化為前束形（使所有全稱量詞在公式最前面）化為Skolem標準形（子句的合取式）略去全稱量詞斷開合取式得到子句集變量名標準化3.3謂詞公式轉(zhuǎn)換為子句集3.4消解原理消解原理(RobinsonTheorem)命題邏輯中的歸結(jié)原理:如果C1和C2為真，則C12為真推論1:C1,C2S,則S{C1|C12,C2|C12}不可滿足S不可滿足推論2:C1,C2S,則S{C12}不可滿足S不可滿足C1:PQC2:PRC12:QR3.4消解原理消解原理(RobinsonTheorem)謂詞邏輯中的歸結(jié)原理:如果C1和C2為真，則C12為真推論1:C1,C2S,則S{C1|C12,C2|C12}不可滿足S不可滿足推論2:C1,C2S,則S{C12}不可滿足S不可滿足C1:P(x)Q(x)C2:P(a)R(y)C12:Q(a)R(y)3.5歸結(jié)反演歸結(jié)反演(1)將已知前提表示為謂詞F(2)將待證明結(jié)果表示為謂詞Q(3)將謂詞公式FQ化為子句集S(4)應用歸結(jié)原理對S中的子句進行歸結(jié)，直至出現(xiàn)空子句，則證明Q為真推理示例知識庫天使只說真話不說假話魔鬼只說假話不說真話凡人有時候說真話有時候說假話事實A,B,C三人分別是天使、魔鬼和凡人A說“我不是天使”。B說“我不是魔鬼”。C說“我不是凡人”問題：請問誰是天使，誰是魔鬼，誰是凡人？3.5歸結(jié)反演歸結(jié)反演:可能產(chǎn)生大量不必要的歸結(jié)式控制策略刪除無用子句限制子句的歸結(jié)范圍案例研究:故障推理(USB驅(qū)動安裝錯誤)∨(USB口損壞)(USB口無法使用)(設(shè)置了靜音)∨(音頻設(shè)備錯誤)(沒有聲音)(音頻設(shè)備被禁用)∨(聲卡驅(qū)動安裝錯誤)∨(病毒程序破壞了音頻服務)∨(聲卡硬件損壞)∨(揚聲器硬件損壞)(音頻設(shè)備錯誤)人工智能推理領(lǐng)域?qū)W術(shù)刊物重要國際期刊InternationalJournalofApproximateReasoning,Elsevier(/international-journal-of-approximate-reasoning/)IF:1.729JournalofAutomatedReasoning,Springer(/journal/10817)IF:0.567人工智能推理領(lǐng)域?qū)W術(shù)刊物重要國際會議InternationalJointConferenceonAutomatedReasoning(IJCAR),/InternationalConferenceonCase-BasedReasoning,/InternationalConferenceonPrinciplesofKnowledgeRepresentationandReasoning,

作業(yè)用確定性推理技術(shù)求解以下問題一宗盜竊案有的5個嫌疑犯，他們當中只有3個人說的是真話。A說“D是小偷”;B