1、人工智能原理及應(yīng)用人工智能原理及應(yīng)用第第3章章 確定性推理方法確定性推理方法3.1 推理的基本概念推理的基本概念 已知事實(shí)已知事實(shí)（證據(jù)）（證據(jù)）已有知識(shí)已有知識(shí)新的事實(shí)新的事實(shí)（結(jié)論）（結(jié)論）3.1 推理的基本概念推理的基本概念由一般到個(gè)別由一般到個(gè)別l 大前提: BCl 小前提: ABl 三段論: AC3.1 推理的基本概念推理的基本概念由一般到個(gè)別由一般到個(gè)別l 大前提: 計(jì)算機(jī)學(xué)院的學(xué)生都會(huì)編程序l 小前提: 李強(qiáng)是一名計(jì)算機(jī)學(xué)院的學(xué)生l 結(jié)論: 李強(qiáng)會(huì)編程序3.1 推理的基本概念推理的基本概念由個(gè)別到一般由個(gè)別到一般l A的所有實(shí)例具有X屬性 (完全歸納)l 結(jié)論: A具有X屬性3.

2、1 推理的基本概念推理的基本概念由個(gè)別到一般由個(gè)別到一般l 檢查某廠的所有產(chǎn)品均合格 (完全歸納)l 結(jié)論: 該廠的產(chǎn)品合格3.1 推理的基本概念推理的基本概念由個(gè)別到一般由個(gè)別到一般l A的部分實(shí)例具有X屬性 (部分歸納)l 結(jié)論: A具有X屬性3.1 推理的基本概念推理的基本概念由個(gè)別到一般由個(gè)別到一般l 抽查某廠的一部分產(chǎn)品合格 (部分歸納)l 結(jié)論: 該廠的產(chǎn)品合格3.1 推理的基本概念推理的基本概念由個(gè)別到一般由個(gè)別到一般l A具有X屬性l B與A類似 (類比歸納)l 結(jié)論: B具有X屬性3.1 推理的基本概念推理的基本概念由個(gè)別到一般由個(gè)別到一般l 軟件工程專業(yè)的學(xué)生都會(huì)編程序l

3、計(jì)算機(jī)科學(xué)與技術(shù)與軟件工程專業(yè)方向類似 (類比歸納)l 結(jié)論: 計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的學(xué)生都會(huì)編程序3.1 推理的基本概念推理的基本概念知識(shí)不完全的情況下的推理知識(shí)不完全的情況下的推理l ABl 沒有證據(jù)證明Al 結(jié)論: B3.1 推理的基本概念推理的基本概念知識(shí)不完全的情況下的推理知識(shí)不完全的情況下的推理l 未滿18歲不能進(jìn)入營業(yè)性網(wǎng)吧l 不知道學(xué)生李強(qiáng)的真實(shí)年齡l 李強(qiáng)不能進(jìn)入營業(yè)性網(wǎng)吧3.1 推理的基本概念推理的基本概念已知事實(shí)已知事實(shí)（證據(jù)）（證據(jù)）已有知識(shí)已有知識(shí)新的事實(shí)新的事實(shí)（結(jié)論）（結(jié)論）3.1 推理的基本概念推理的基本概念已知事實(shí)已知事實(shí)（證據(jù)）（證據(jù)）已有知識(shí)已有知識(shí)新的事

4、實(shí)新的事實(shí)（結(jié)論）（結(jié)論）3.1 推理的基本概念推理的基本概念已知事實(shí)已知事實(shí)（證據(jù)）（證據(jù)）已有知識(shí)已有知識(shí)新的事實(shí)新的事實(shí)（結(jié)論）（結(jié)論）3.1 推理的基本概念推理的基本概念Y3.1 推理的基本概念推理的基本概念3.1 推理的基本概念推理的基本概念事實(shí)事實(shí): AB知識(shí)知識(shí): ACD BEF目標(biāo)目標(biāo): CFA?BABABCDEFCF目標(biāo)匹配匹配F規(guī)則已知事實(shí)r1r2 3.1 推理的基本概念推理的基本概念事實(shí)事實(shí): P(x,y)(Q(x)R(v,y)知識(shí)知識(shí): P(u,v)(S(u)N(v)目標(biāo)目標(biāo): S(x)N(y)Q(x)推理示例推理示例知識(shí)庫知識(shí)庫事實(shí)事實(shí)目標(biāo)結(jié)論目標(biāo)結(jié)論推理示例推理示例

5、g(x)4.5g(x)4.5 g(x)4.5A(x)g(x)4E(x)A(x) E(x) E(x) A(x)推理示例推理示例如何對事實(shí)進(jìn)行如何對事實(shí)進(jìn)行合理的歸納？合理的歸納？如何選擇事實(shí)的如何選擇事實(shí)的推理順序？推理順序？3.1 推理的基本概念推理的基本概念推理示例推理示例知識(shí)庫知識(shí)庫事實(shí)事實(shí)問題：請問誰是小偷？問題：請問誰是小偷？推理示例推理示例如何選擇假設(shè)的如何選擇假設(shè)的驗(yàn)證順序？驗(yàn)證順序？3.1 推理的基本概念推理的基本概念3.1 推理的基本概念推理的基本概念3.2 自然演繹推理自然演繹推理（1）雙重否定律：）雙重否定律： （2）交換律：）交換律： （3）結(jié)合律：）結(jié)合律： （4）分配

6、律：）分配律： （5）摩根定律：）摩根定律： PP )()(),()(PQQPPQQP)()(RQPRQP)()(RQPRQP)()()(RPQPRQP)()()(RPQPRQP(PQ)PQ(PQ)PQ3.2 自然演繹推理自然演繹推理（6）吸收律：）吸收律： （7）補(bǔ)余律）補(bǔ)余律: （8）連詞化歸律）連詞化歸律: （9）量詞轉(zhuǎn)換律）量詞轉(zhuǎn)換律: （10）量詞分配律）量詞分配律: PQPP)(PQPP)(FPPTPP,QPQP)()(PQQPQP)(PPxx ）（)()(PxPxQxPxQPx)()()(QxPxQPx)()()(PQ)(PQ) (QP)3.2 自然演繹推理自然演繹推理（1）化簡

7、式：）化簡式： （2）附加式：）附加式： （3）析取三段論：）析取三段論： （4）假言推理：）假言推理： （5）拒取式：）拒取式： QQPPQP,QPQQPP,QQPP,QQPP,PQPQ,3.2 自然演繹推理自然演繹推理（6）假言三段論：）假言三段論： （7）二難推理：）二難推理： （8）全稱固化：）全稱固化： 其中，其中，y是個(gè)體域中的任一是個(gè)體域中的任一個(gè)體，依此可消去謂詞公式中的全稱量詞。個(gè)體，依此可消去謂詞公式中的全稱量詞。（9）存在固化：）存在固化： 其中，其中，y是個(gè)體域中某一個(gè)是個(gè)體域中某一個(gè)可以使可以使 P(y)為真的個(gè)體，依此可消去謂詞公式中的存在量詞。為真的個(gè)體，依此可消

8、去謂詞公式中的存在量詞。RPRQQP,RRQRPQP,),()()(yPxPx,)()()(yPxPx3.3 謂詞公式轉(zhuǎn)換為子句集謂詞公式轉(zhuǎn)換為子句集3.3 謂詞公式轉(zhuǎn)換為子句集謂詞公式轉(zhuǎn)換為子句集1)消去連接詞消去連接詞“”和和“”2)把否定符號把否定符號“”移到每個(gè)謂詞符號的前面移到每個(gè)謂詞符號的前面3)變量標(biāo)準(zhǔn)化（使不同量詞約束的變量有不同的名字）變量標(biāo)準(zhǔn)化（使不同量詞約束的變量有不同的名字）4)引入引入Skolem函數(shù)消去存在量詞函數(shù)消去存在量詞5)化為前束形（使所有全稱量詞在公式最前面）化為前束形（使所有全稱量詞在公式最前面）6)化為化為Skolem標(biāo)準(zhǔn)形（子句的合取式）標(biāo)準(zhǔn)形（子句

9、的合取式）7)略去全稱量詞略去全稱量詞8)斷開合取式得到子句集斷開合取式得到子句集9)變量名標(biāo)準(zhǔn)化變量名標(biāo)準(zhǔn)化3.3 謂詞公式轉(zhuǎn)換為子句集謂詞公式轉(zhuǎn)換為子句集)()()()(),()()()()(xBxPxxQyxSyxQxPx)()()()(),()()()()(xBxPxxQyxSyxQxPx)()()()(),()()()()(xBxPxxQyxSyxQxPx)()()()(),()()()()(wBwPwxQyxSyxQxPx)()()()()(,()()()(wBwPwxQxfxSxQxPx)()()()(,()()()(wBwPxQxfxSxQxPwx)()()()(,()()(w

10、BwPxQxfxSxPwx)()()()(,()(wBwPxQxfxSxP)(,()(xfxSxP)(xQ)()(wBwP)(,()(xfxSxP( )Q y)()(wBwP3.4 消解原理消解原理C1: PQC2: PRC12: QR3.4 消解原理消解原理C1: P(x)Q(x)C2: P(a)R(y)C12: Q(a)R(y)3.5 歸結(jié)反演歸結(jié)反演(1)將已知前提表示為謂詞將已知前提表示為謂詞F(2)將待證明結(jié)果表示為謂詞將待證明結(jié)果表示為謂詞Q(3)將謂詞公式將謂詞公式FQ化為子句集化為子句集S(4)應(yīng)用歸結(jié)原理對應(yīng)用歸結(jié)原理對S中的子句進(jìn)行歸結(jié)，直至出現(xiàn)空子句，則證明中的子句進(jìn)行歸

11、結(jié)，直至出現(xiàn)空子句，則證明Q為真為真推理示例推理示例知識(shí)庫知識(shí)庫事實(shí)事實(shí)問題：請問誰是天使，誰是魔鬼，誰是凡人？問題：請問誰是天使，誰是魔鬼，誰是凡人？3.5 歸結(jié)反演歸結(jié)反演案例研究案例研究: 故障推理故障推理(USB驅(qū)動(dòng)安裝錯(cuò)誤驅(qū)動(dòng)安裝錯(cuò)誤) (USB口損壞口損壞) (USB口無法使用口無法使用) (設(shè)置了靜音設(shè)置了靜音) (音頻設(shè)備錯(cuò)誤音頻設(shè)備錯(cuò)誤) (沒有聲音沒有聲音) (音頻設(shè)備被禁用音頻設(shè)備被禁用) (聲卡驅(qū)動(dòng)安裝錯(cuò)誤聲卡驅(qū)動(dòng)安裝錯(cuò)誤) (病毒程序破壞了音頻服務(wù)病毒程序破壞了音頻服務(wù)) (聲卡硬件損壞聲卡硬件損壞) (揚(yáng)聲器揚(yáng)聲器硬件損壞硬件損壞) (音頻設(shè)備錯(cuò)誤音頻設(shè)備錯(cuò)誤) 人

12、工智能推理領(lǐng)域?qū)W術(shù)刊物人工智能推理領(lǐng)域?qū)W術(shù)刊物lI n t e r n a t i o n a l J o u r n a l o f A p p r o x i m a t e R e a s o n i n g , E l s e v i e r ( IF: 1.729 lJournal of Automated Reasoning, Springer ( IF: 0.567人工智能推理領(lǐng)域?qū)W術(shù)刊物人工智能推理領(lǐng)域?qū)W術(shù)刊物lInternational Joint Conference on Automated Reasoning (IJCAR), / lInternational Conference on Case-Based Reasoning, /lInternational Conference on Principles of Knowledge Representation and Reasoning, 作業(yè)作業(yè)1.一宗盜竊案有的5個(gè)嫌疑犯，他們當(dāng)中只有3個(gè)人說的是真話。