1、n什么是人工智能？n從表現形式的角度機器智能，能夠在各類環境中，自主地或交互地執行各種擬人任務（Anthropomorphic Anthropomorphic taskstasks）的機器。n從學科發展的角度人工智能，是計算機科學中涉及研究、設計和應用智能機器的一個分支，其近期主要目標是用機器來模仿和執行人腦的某些智能功能，并開發相關理論和技術。n從實用主義的角度智能計算，研究智能信息處理技術，以使機器具有與人類智能相類似的行為，如：判斷、推理、證明、識別、感知、理解、通信、設計、思考、規劃、學習和問題求解等思維活動 知識表示方法知識表示方法n狀態空間法狀態空間法n問題歸約法問題歸約法n謂詞邏

2、輯法謂詞邏輯法. .n語義網絡語義網絡n另外還有框架表示以及劇本表示另外還有框架表示以及劇本表示, ,過程表示過程表示, ,這這里不在一一詳述里不在一一詳述. .n在表示和求解比較復雜的問題時在表示和求解比較復雜的問題時, ,采用單一的表采用單一的表示方法是不夠的示方法是不夠的, ,往往采用多種方法的混合表示往往采用多種方法的混合表示. .目前這仍是人工智能專家感興趣的研究方向目前這仍是人工智能專家感興趣的研究方向. .T0,1nq q ,.q Q 初始棋局初始棋局目標棋局目標棋局初始狀態初始狀態目標狀態目標狀態W 猴子的水平位置；猴子的水平位置；x 當猴子在箱子頂上時取當猴子在箱子頂上時取1

3、；否則取；否則取0；Y 箱子的水平位置；箱子的水平位置；z 當猴子摘到香蕉時取當猴子摘到香蕉時取1；否則取；否則取0。n要把問題的一切狀態都表示出來，要定義一組算符。要把問題的一切狀態都表示出來，要定義一組算符。n問題的求解過程是一個不斷把算符作用于狀態的過程。問題的求解過程是一個不斷把算符作用于狀態的過程。解解就是從初始狀態到目標狀態所采用算符的序列。使就是從初始狀態到目標狀態所采用算符的序列。使用算符最少的解稱為用算符最少的解稱為最優解最優解。n對任一個狀態，可使用的算符可能不止一個。對任一個狀態，可使用的算符可能不止一個。 已知問題的描述，通過一系列變換把此問題變為一個已知問題的描述，通

4、過一系列變換把此問題變為一個子問題集合；這些子問題的解可以直接得到，從而解子問題集合；這些子問題的解可以直接得到，從而解決了初始問題。決了初始問題。n問題歸約法的組成部分問題歸約法的組成部分（1 1）一個初始問題描述；）一個初始問題描述；（2 2）一套把問題變換為子問題的操作符；）一套把問題變換為子問題的操作符；（3 3）一套本原問題描述。）一套本原問題描述。( (本原問題本原問題: :不能再分解或不能再分解或變換且直接可解的子問題變換且直接可解的子問題) )n問題歸約的本質問題歸約的本質 從目標（要解決的問題）出發逆向推理，建立從目標（要解決的問題）出發逆向推理，建立子問題以及子問題的子問題

5、，直到最后把初始問題子問題以及子問題的子問題，直到最后把初始問題歸約為一個本原問題集合。歸約為一個本原問題集合。問題歸約示例問題歸約示例梵塔難題梵塔難題(a) 初始狀態初始狀態(b) 目標狀態目標狀態n復雜問題的簡化復雜問題的簡化n分解分解把一個復雜問題分解為若干個把一個復雜問題分解為若干個較為簡單的子問題，形成較為簡單的子問題，形成“與與”樹。樹。n等價變換等價變換利用同構或同態的等價變換，利用同構或同態的等價變換，把原問題變換為若干個較為容把原問題變換為若干個較為容易求解的新問題，形成易求解的新問題，形成“或或”樹。樹。n終葉節點是可解節點終葉節點是可解節點(對應于本原問題對應于本原問題)

6、。n如果某個非終葉節點含有或后繼節點，那么只要如果某個非終葉節點含有或后繼節點，那么只要當其后繼節點至少有一個是可解的時，此非終葉當其后繼節點至少有一個是可解的時，此非終葉節點才是可解的。節點才是可解的。n如果某個非終葉節點含有與后繼節點，那么只有如果某個非終葉節點含有與后繼節點，那么只有當其后繼節點全部為可解時，此非終葉節點才是當其后繼節點全部為可解時，此非終葉節點才是可解的。可解的。n沒有后裔的非終葉節點為不可解節點。沒有后裔的非終葉節點為不可解節點。 n如果某個非終葉節點含有或后繼節點，那么只有如果某個非終葉節點含有或后繼節點，那么只有當其全部后裔為不可解時，此非終葉節點才是不當其全部后

7、裔為不可解時，此非終葉節點才是不可解的。可解的。 n如果某個非終葉節點含有與后繼節點，那么只要如果某個非終葉節點含有與后繼節點，那么只要當其后裔至少有一個為不可解時，此非終葉節點當其后裔至少有一個為不可解時，此非終葉節點才是不可解的。才是不可解的。n由可解節點所構成，并且由這些可解節點可推出初由可解節點所構成，并且由這些可解節點可推出初始節點為可解節點的子樹稱為解樹。始節點為可解節點的子樹稱為解樹。n解樹中一定包含初始節點，它對應于原始問題解樹中一定包含初始節點，它對應于原始問題。 命題邏輯命題邏輯 一個命題是一個或真或假不能兩者都是的斷一個命題是一個或真或假不能兩者都是的斷言。斷言是指一陳述

8、語句。簡單地說，命題是指言。斷言是指一陳述語句。簡單地說，命題是指一句有真假意義的陳述句。命題為真，記為一句有真假意義的陳述句。命題為真，記為 T 。 命題為假，記為命題為假，記為 F。 一個命題一個命題P如果是真值未指定任意命題，稱如果是真值未指定任意命題，稱P為命題變元。為命題變元。命題變元用命題變元用 P, Q, R表示；如果表示；如果P是一個真值已經指定的命題，稱為命題常元。命是一個真值已經指定的命題，稱為命題常元。命題常元只有題常元只有 T 和和 F。 復合命題復合命題：單個命題通過聯結詞聯結構成的新：單個命題通過聯結詞聯結構成的新命題。命題。常用的常用的5種聯結詞：種聯結詞：復合命

9、題與原命題的真值關系復合命題與原命題的真值關系P Q P P Q P Q PQ PQF F T F F T TT F F T F F FF T T T F T FT T F T T T T否定否定 合取合取 析取析取 蘊涵蘊涵 等值等值 命題公式及其解釋命題公式及其解釋原子公式原子公式：單個命題變元、單個命題常元稱為原子：單個命題變元、單個命題常元稱為原子公式。公式。命題公式命題公式：由如下規則生成的公式稱為命題公式：由如下規則生成的公式稱為命題公式：1. 單個原子公式是命題公式。單個原子公式是命題公式。2. 若若A ,B是命題公式，則是命題公式，則A , AB , AB , A B , A

10、B是公式。是公式。3. 所有命題公式都是有限次應用所有命題公式都是有限次應用1、2得到的符號串。得到的符號串。例如：公式例如：公式G= (A B) C 的一個解釋是：的一個解釋是：I1(G) = A/T, B/F, C/T 在解釋在解釋I1(G)下下G為真。為真。永真公式與永假公式永真公式與永假公式：如果公式在它所有的解釋：如果公式在它所有的解釋I下，其值都為下，其值都為T，則稱公式，則稱公式G為恒真的；如果其值為恒真的；如果其值都為都為F，則稱公式，則稱公式G為恒假的（不可滿足的）。為恒假的（不可滿足的）。命題公式的命題公式的解釋解釋：給命題公式中的每一個命題變元：給命題公式中的每一個命題變

11、元指定一個真假值，這一組真假值，就是命題公式的指定一個真假值，這一組真假值，就是命題公式的一個解釋。用一個解釋。用I表示。表示。注意：注意：關于五個聯結詞的約定關于五個聯結詞的約定：* 結合力的強弱順序：結合力的強弱順序： ， ， ， ， * 聯結詞相同時，從左至右運算。聯結詞相同時，從左至右運算。解釋的個數解釋的個數：如果一個公式如果一個公式G中有中有n個不同的原子公式（或簡個不同的原子公式（或簡稱原子），則稱原子），則G有有2n個不同的解釋，于是個不同的解釋，于是G在在2n個解個解釋下有釋下有2n個真值。如果將這些真值和它們的解釋列成個真值。如果將這些真值和它們的解釋列成表，就是表，就是G

12、的真值表。的真值表。等價命題公式等價命題公式 如果兩個命題公式所含原子公式相同，且在任一解釋如果兩個命題公式所含原子公式相同，且在任一解釋下，兩個命題公式的值相同，則稱這兩個命題公式為等價下，兩個命題公式的值相同，則稱這兩個命題公式為等價命題公式或等價公式。常用的等價公式有：命題公式或等價公式。常用的等價公式有：1. (P Q)= (P Q) (Q P)P Q P Q Q P (P Q) (Q P) P QT T T T T TT F F T F FF T T F F FF F T T T T2.(P Q)=(P Q)3. (P)= P4.交換律：P Q=Q P P Q=Q P5.結合律：P

13、(Q R)=(P Q) R P (Q R)=(P Q) R6.分配律：P (Q R)=(P Q) (P R) P (Q R)=(P Q) (P R)7.泛界律：P F=P , P T=P P F=F ,P T=T 8.互余律：P P=T,P P=F9.德 摩根定律：(P Q)=P Q (P Q)=P Q證明兩個公式等價，可用真值表，也可用基本公式。證明兩個公式等價，可用真值表，也可用基本公式。例如例如 要證明公式要證明公式 P Q=Q P證 P Q = P Q = P ( Q )=(Q) P=Q P若要證明公式P P Q=P證 P P Q = P ( P Q) = P (Q Q) ( P Q)

14、= (P Q) (P Q) ( P Q)=( P Q) ( P Q) = P (Q Q)=P永真蘊涵式永真蘊涵式 若命題公式若命題公式G H是恒真的，稱其為永真蘊涵式。是恒真的，稱其為永真蘊涵式。記為記為GH，讀做，讀做“G蘊涵蘊涵H”，也稱，也稱“G是是H的邏輯結的邏輯結果果”。常用的永真蘊涵式：1. P P Q 證P P Q = P (P Q) = P P Q = T Q = T2. P Q P證P Q P =(P Q) P= P Q P=T Q= T3. P (P Q) Q4.( P Q) Q P5. P (P Q) Q6.(P Q) (Q R) (P R)7.( P Q) ( (Q R

15、) ( P R)8.(P Q) ( R S) (P R Q S)9.( P Q) ( Q R) ( P R)謂詞與量詞謂詞與量詞在命題邏輯中有一個三段論法：在命題邏輯中有一個三段論法：P:“所有的人都會犯錯誤所有的人都會犯錯誤”Q:“張三是人張三是人”R:“張三會犯錯誤張三會犯錯誤” R應該是應該是P和和Q的邏輯結論。但在命題邏輯中無法準確的邏輯結論。但在命題邏輯中無法準確表達這三個命題的邏輯關系。表達這三個命題的邏輯關系。因為因為( P Q ) R 不是恒真的。如：不是恒真的。如：解解釋釋: I=P/T,Q/T,R/F 則公式為假值則公式為假值F. 就是說解釋就是說解釋I 弄假了此公式。弄假

16、了此公式。為準確表達此類公式，必須引進謂詞和量詞的概念。為準確表達此類公式，必須引進謂詞和量詞的概念。謂詞謂詞先看幾個命題：先看幾個命題：1. 3是質數是質數2. 王二生于武漢市王二生于武漢市3. 7=2 3 x是質數是質數x生于武漢市生于武漢市x=y zF(x)G(x,y)H(x,y,z)稱稱“3”、“王二王二”、“武漢市武漢市”、“7”、“2”、“3”為個為個體體;代表個體的變元稱為個體變元；代表個體的變元稱為個體變元；刻畫個體性質或個體之間關系的詞叫刻畫個體性質或個體之間關系的詞叫謂詞謂詞。“是質數是質數”、“生于生于”、“=. .”都是謂詞。都是謂詞。量詞量詞量詞分為全稱量詞和存在量詞

17、。量詞分為全稱量詞和存在量詞。符號符號“ ”表示全稱量詞。符號表示全稱量詞。符號“ ”表示存在量詞。表示存在量詞。 x讀作讀作“對一切對一切x”,或或“對每一對每一x”，或，或“對任對任一一x”。x是是 所作用的個體變元。所作用的個體變元。 x讀作讀作“存在一個存在一個x”,或或“對某些對某些x”，或，或“至少有一至少有一x”。x是是 所作用的個體變元。所作用的個體變元。再看前面的三段論法：再看前面的三段論法：P:“所有的人都會犯錯誤所有的人都會犯錯誤”Q:“張三是人張三是人”R:“張三會犯錯誤張三會犯錯誤” x(M(x) R(x)M(“張三張三”)R(“張三張三”)在謂詞前加上在謂詞前加上

18、x,叫做變元被全稱量化；叫做變元被全稱量化；在謂詞前加上在謂詞前加上 x,叫做變元被存在量化。叫做變元被存在量化。量化的目的是約束變元。量化的目的是約束變元。n謂詞演算謂詞演算項項謂詞符號常量符號 函數符號 謂詞公式謂詞公式 ( x)(I(x) (P(x)N(x)BA例例2 用謂詞邏輯描述右圖中的房子的概念。用謂詞邏輯描述右圖中的房子的概念。 個體個體 ：A , B 謂詞謂詞 ：SUPPORT( x,y ) 表示表示 x 被被 y支撐著支撐著 WEDRE ( x ) 表示表示 x 是楔形塊是楔形塊 BRICK( y ) 表示表示 y 是長方塊是長方塊 2022-4-19置換與合一置換與合一張寧張寧學生學生Is-a手手人體人體A-part-of 張寧張寧英語英語18160havehavecan學校學校公園公園風景美麗風景美麗Similar to fetch書書桌子桌子Loca