記：人工智能和先進人工智能寫在一起了,懶得分開寫
目錄
第一章
第二章 知識表示方法
知識表示
知識表示方法
狀態空間法
問題歸約法
謂詞邏輯法(重點 但是不單獨考察)
語意網路法
第三章：搜索技術
基于狀態空間法的搜索技術
基于問題歸約的搜索技術
第四章：邏輯推理技術
消解原理
消解歸結
反演求解
第五章：不確定性推理
C-F模型
模糊推理
基礎概念：
準備做題：
第六章：計算智能
進化計算
第七章：群智能演算法
第一章
先說總體框架：人工智能
先給幾個概念
Artificial Intelligence (AI)：人工智能就是用人工的方法在機器（計算機）上實作的智能，或稱機器智能、計算機智能，
知識：人們通過體驗、學習或聯想而知曉的對客觀世界規律性的認識，包括事實、條件、程序、規則、關系和規律等，
智能：一種應用知識對一定環境或問題進行處理的能力或者進行抽象思考的能力，
人工智能的三大學派：
符號主義：立足于邏輯運算和符號操作,適合于模擬人的邏輯思維程序,解決需要邏輯推理的復雜問題
連接主義：通過過神經元之間的并行協作實作資訊處理,處理程序具有并行性,動態性,全域性
行為主義：采用行為模擬方法，也認為功能、結構和智能行為是不可分的，不同行為表現出不同功能和不同控制結構，
第二章 知識表示方法
了解知識表示,并熟悉幾種知識表示的常用方法
知識表示
相關概念(了解即可)
- 一般來說，我們把有關資訊關聯在一起所形成的資訊結構稱為知識，
- 知識表示就是對知識的一種描述，一種計算機可以接受的用于描述知識的資料結構，
- 知識的要素：指構成知識的必需元素，一般而言，人工智能系統的知識包含事實、規則、控制和元知識，
知識表示方法
狀態空間法
基本要素：基于解答空間的問題表示和求解方法就是狀態空間法
- 狀態（State）：為描述某類不同事物間的差別而 入的一組最少變數 q0 q1，…，qn的有序集合
給定每個分量的一組值就得到一個具體的狀態，例如Qk =[q０k, , q1k ,…,qnk ] 表示一個具體的狀態 - 算符（operator）：把問題從一種狀態變換為另一種狀態的手段
算符可為走步、程序、規則、數學算子、運算子號 或邏輯符號等， - 狀態空間方法（Method on State Space)
使用狀態空間法解題：1.給出狀態描述，特別是初始狀態，目標狀態，2.給定運算子集合，以及運算子的作業，3.通過使用不同運算子使得從初始狀態轉移到目標狀態
狀態空間例題：猴子摘香蕉，傳教士過河
（注：不打算作為重點去看）
問題歸約法
實質：將原始問題分解一些子問題，通過求解這些子問題可以最終求解原始問題，將得到的子問題不斷分解直至得到平凡的本原問題，通過平凡的本原問題的解逆推最終得到原始問題的解，
組成部分
- 一個初始問題描述；
- 一套把問題變換為子問題的運算子；
- 一套本原問題描述，
問題歸約的例題：梵塔難題，不定積分的求解、
（注：不打算作為重點去看）
謂詞邏輯法(重點 但是不單獨考察)
基礎概念
- 邏輯主要研究推理程序，而推理程序必須依靠命題來表達，
命題是陳述客觀外界發生事情的陳述句， 命題是或為真或為假的陳述句，學會如何判斷一個句子是否為命題 - 命題抽象：取值為0或1的p等符號，
若p取值1，則表示p為真命題；
若p取值0，則表示p為假命題 - 復雜命題：由連結詞和命題連接而成的更加復雜命題
復合命題的真偽完全由構成它的簡單命題的真偽所決定，
命題連接詞(五種) 概念性問題，記住即可，沒必要浪費時間
- 否定 ?P
- 合取 p∧q
- 析取 p∨q
“相容或”：可以同時發生 ：可表示為p∨q
“相異或”：不可以同時發生，當且選擇其一 ： 可表示為 (p∧ ?q) ∨ (?p∧q) - 蘊含 p → q 如果p, 則q
- 等價 p?q “p當且 僅當q
命題符號化(第一步 建議多加練習，)直接一步到位，直接看謂詞邏輯符號化
照例先給出一些概念：
謂詞邏輯法采用謂詞合式公式和一階謂詞演算把要解決的問題變為一個有待證明的問題,然后采用消解原理和消解反演來證明一個新陳述句是從已知的正確陳述句匯出的,從而證明新陳述句也是正確的.(注：看不懂沒關系，有些概念在后邊才會給出證明 )
謂詞：用于刻畫個體的性質、狀態和個體之間關系的語言成分，
舉例：張三是研究生，李四是研究生
在這個問題中，研究生就是張三和李四共同的屬性，使用符號P(x)表示 x是研究生，則上述句子的符號化為 P(張三) ∨ P(李四)
謂詞邏輯的語法元素表示如下
- 個體符號或常量:A、B、張三、李四等等，通常是物件的名稱，
- 變數符號：習慣上用小寫字母表示，如x、y、z等，
- 函式符號：習慣上用小寫英文字母或小寫英文字母串表 示，如plus、f、g，
- 謂詞符號：習慣上用大寫英文字母或（首字母）大寫英文字母串表示，
- 連接詞：否定 合取 析取 蘊含
- (說明：暫時不知道函式符號 和 謂詞符號之間 怎樣區分)
- 量詞
全稱量詞：若一個原子公式 P(x)，對于所有可能變數x都具有T 值,則用(?x)P(x)表示
舉例：所有學生都穿彩色制服 (?x)[Student(x)=>Uniform (x, Color)]
存在量詞：若一個原子公式P(x), 至少有一個變元x可使 P(x) 為T值, 則用(?x)P(x)表示
舉例：1號房間內有個物體 (?x)INROOM(x,r1)
謂詞邏輯法表示句子：
- 煉訓比他父親有名，
- 高揚是計算機系的學生，但他不喜歡編程，
- 人人愛勞動，
第一步：定義如下謂詞：
Famous(x,y):x比y有名， Computer(x): x是計算機系的學生 Like(x,y): x喜歡y Love(x,y): x愛y Man(x): x
第二步：用謂詞公式表示
- Famous(煉訓，煉訓的父親)
- Computer(高楊) ∧ ~like(高楊，編程)
- (?x)[Man(x)=>Love(x, labour)]
合式公式：由原子謂詞公式經過有限次的連接運算和量詞拼接起來的公式
定義類似于初等函式 定義：由 基本初等函式經過有限次四則運算得到的函式
注： 合式公式的性質并不需要全部記，需要記得公式會在后邊給出
注意點：
- 量詞否定
~ (?x)P(x)等價于(?x)[~P(x)] ~(?x)P(x)等價于(?x)[~P(x)] - 量詞分配
(?x)[P(x)∧Q(x)]等價于(?x)P(x)∧(?x)Q(x) - 量詞轄域
量詞的轄域是鄰接量詞之后的最小子公式， 故除非轄域是個原子公式，否則應在該子公式的兩端有括號
注：找轄域的方法：1.看有無括號 2.緊跟的原子公式
舉例：(?x)P(x)→Q(x) ?x的轄域是P(x)
(?x ) [P(x, y)→Q(x，y)] ∨ P(y, z) ?x的轄域是P(x，y)→Q(x，y)
利用謂詞公式進行知識表示的步驟如下： (概念 配合例題進行理解)
- 定義謂詞及個體,確定其含義
- 根據要表達的事物或概念,為每個謂詞中的變元賦值;
- 根據表達的知識的含義,用適當的連接符號將各個謂詞連接起來,形成謂詞公式
例題：（在練習中去體驗每一步應該做什么）
- 如果張三比李四大，那么李四比張三小
定義如下謂詞：Old(x,y) x比y大 Young(x,y) x比y小
用謂詞公式表示：Old(張三，李四)=>Young(李四, 張三) - 若一個人是老實人，他就不會說謊
Honest(x) x是老實的 Man(x）x是人 Lie(x) x撒謊
Honest(Man(x)) => ~Lie(x) - 并不是所有的學生選修了歷史和生物
Student(x) x是學生 learn(x,y) x選修了y
~(?x)[Student(x) => ( learn(x,歷史) ∨learn(x,生物)） - 所有選修人工智能課程的學生都喜歡玩游戲，
Student(x) x是學生 learn(x,y) x選修了y Like(x,y) x喜歡y
(?x)[Student(x) ∧ learn(x，AI） => Like（x,games） - 歷史考試中有學生不及格，
Fail(x,y) x沒有通過y Student(x) x是學生
(?x) Student(x) ∧ Fail(x，歷史考試) - 星期六，所有的學生或者去了舞會，或者去作業， 但是沒有兩者都去的，
Student(x) x是學生 Party(x) x參加舞會 Work(x) x參加作業
(?x) Student(x) => ((Party(x) ∧ ~Work(x)) ∨ ((~Party(x) ∧ Work(x)))
置換：在該運算式中用置換項置換變數.
{ti/xi} 用 t1(常量、 變數、函式) 去置換運算式中的 xi(變數)
舉例：運算式：P[x,f(y),B] 置換：s2={A/y} 結果：P[x,f(y),B]s2=P[x,f(A),B]
s1={z/x,w/y} 結果：P[x,f(y),B]s1 = P[z,f(w),B]
合一：尋找項對變數的置換，以使兩運算式一致，(物件：兩個運算式 操作：做同一個置換 結果：若置換結果相同，則這個置換叫做一個合一)
舉例：運算式1{P[x,f(y),B]， 置換：s={A/x,B/y} 結果：P[A,f(B),B] 則這個置換叫做這兩個運算式的一個合一
運算式2P[x,f(B),B]} P[A,f(B),B]
最一般合一：通過置換最少的變數以使運算式一致
語意網路法
語意網路是知識的一種結構化圖解表示，它由節點和弧線組成，
節點用于表示物體、概念和情況等，節點之間的
弧線用于表示節點間的關系，
在注意一點：語意網路從本質上說只能表示兩元關系，題目中的多元關系需要拆分成兩元關系
直接看題(不用管那么多)
要表達北京大學(BEIJING University,簡稱BU) 和清華大學(TSINGHUA University,簡稱TU)兩校籃球隊在北大進行的一場比賽的比分是85比89，
框架
框架是一種結構化表示法，通常采用語意網路中的節點-槽-值表示結構，(框架跟語意網路并沒有本質區分)
框架表示：
<框架名>
<槽名1>:<槽值1>
.............
<槽名n>:<槽值n>
劇本：框架的一種特殊形式，
第三章：搜索技術
主要內容：
基于狀態空間法的搜索技術
- 圖搜索策略
- 盲目搜索
- 啟發式搜索
基于問題歸約的搜索技術
- 與或樹搜索
- 機器博弈
基于狀態空間法的搜索技術
圖搜索策略
- OPEN表(記錄還沒有擴展的點 用于存放剛生成的節點)
- CLOSED表(記錄已經擴展的點 用于存放已經擴展或將要擴展的節點)
- 每個表示狀態的節點結構中必須有指向父節點 的指標
這是一個通用的搜索程序,后面討論的狀態空間各種搜索策略都是其特例.各種搜索策略的主要區別就是對OPEN表中節點排序準則不同
盲目搜索 ： (主要看一下等代價，前兩個或多或少都接觸過)
- 寬度優先搜搜
- 廣度優先搜索
- 等代價搜索
代價樹的廣度優先搜索 ：OPEN表中的節點在任一時刻都是按其代價從小到大排序的，代價小的節點排在前面，代價大 的節點排在后面 (對擴展節點的子節點和剩余節點進行排序)
如果問題有解，代價樹的廣度優先搜索一定可以求得解，并且求出的是最優解，
代價樹的深度優先搜索： OPEN表中將其子節點按代價從小到大的順序放到 OPEN表中的前端 (對擴展節點的子節點進行排序，剩余節點排在末尾)
補充題： 列出圖中樹的節點訪問序列以滿足下面的兩個搜索策略 ,并寫出其搜索程序中的 open 和closed表（在所有情況中都選擇最左分枝優先訪問 , 設節點12為目標節點）：
（ 1）深度優先搜索； （ 2）寬度優先搜索，
解答：
深度優先訪問序列：1,2,5,6,10,11,3,7,12,13,4,8,9
深度優先open表和closed表存盤內容
| open表 | closed表 |
| 1 | |
| 2,3,4 | 1 |
| 5,6,3,4 | 1,2 |
| 6,3,4 | 1,2,5 |
| 10,11,3,4 | 1,2,,5,6 |
| 11,3,4 | 1,2,5,6,10 |
| 3,4 | 1,2,5,6,10,11 |
| 7,4 | 1,2,5,6,10,11,3 |
| 12,13,4 | 1,2,5,6,10,11,3,7 |
| 13,4 | 1,2,5,6,10,11,3,7,12 |
closed表中找到目標節點12，搜索結束
寬度優先訪問序列：1,2,3,4,5,6,7,8,9,10,11,12
寬度優先open表和closed表存盤內容
| open表 | closed表 |
| 1 | |
| 2,3,4 | 1 |
| 3,4,5,6 | 1,2 |
| 4,5,6,7 | 1,2,3 |
| 5,6,7,8,9 | 1,2,3,4 |
| 6,7,8,9 | 1,2,3,4,5 |
| 7,8,9,10,11 | 1,2,3,4,5,6 |
| 8,9,10,11,12,13 | 1,2,3,4,5,6,7 |
| 10,11,12,13 | 1,2,3,4,5,6,7,8,9 |
| 12,13 | 1,2,3,4,5,6,7,8,9,10,11 |
| 13 | 1,2,3,4,5,6,7,8,9,10,11,12 |
closed表中找到目標節點12，搜索結束
補充題：根據右邊的交通圖， 分別利用代價樹的廣度優先搜索和代價樹的深度優先搜索求出從 A點出發到達 E點的路徑，
代價樹的廣度優先搜索 的表格 第一次經過下標為1，第二次經過下標為2
| open表 | open表中的代價 | closed表 | closed表中的代價 |
| A | |||
| C1,B1 | 3,4 | A | |
| B1,D1 | 4,5 | A,C1, | 0,3, |
| D1,E1,D2 | 5,6,8 | A,C1,B1 | 0,3,4 |
| E1,D2,E2,B2 | 6,8,8,9 | A,C1,B1,D1 | 0,3,4,5 |
| A,C1,B1,D1,E1 | 0,3,4,5,6 |
所以 ： 路徑為 A→B1→E1
代價樹的深度優先搜索 第一次經過下標為1，第二次經過下標為2
所以 ： 路徑為 A→C1→D1→E1
啟發式搜索
特點：重排OPEN表,選擇最有希望的節點加以擴展
種類：有序搜索,A*演算法
定義估價函式：估算節點 希望程度的量度
有序搜索：選擇OPEN表上具有最小f值的節點作為下一個要擴展的節點
A*演算法
估價函式：f(n)=g(n)+h(n) (好家伙，真的看不懂想說啥，還是看題吧)
做題中 需要明確g(n)和h(n)的如何計算，選擇其和最小的進行擴展
對于如圖所示的八數碼問題，給出滿足A *演算法的啟發函式，并給出相應的搜索圖，（說白了 A*演算法只能出八數碼問題，出其他題可能會炸）
解答：
啟發函式的選取如下：g(n)表示節點n在搜索樹中的深度，h(n)=ω(n)表示節點n中不在目標狀態中相應位置的數碼個數，
f(n)= ω(n)+g(n),可以得到如圖所示搜索程序，
基于問題歸約的搜索技術
與或樹搜索
設有如圖所示的與/或樹，其中t1,t2,t3,t4均為終葉節點,A和B是不可解的端節點， 用與/或樹的寬度優先搜索法對該圖進行搜索，
| open表 | closed表 |
| 1 | |
| 2,3 | 1 |
| 3,4,t1 | 1,2 |
| 4,t1,5,B | 1,2,3 |
| t1,5,B,A,t2 | 1,2,3,4 |
| 5,B | 1,2,3,4 |
| B,t3,t4 | 1,2,3,4,5 |
設有如圖所示的與/或樹，其中t1,t2,t3,t4均為終葉節點,A和B是 不可解的端節點，
采用與/或樹的深度優先搜索法對該圖進行搜索，（規定深度界限為4）
| open表 | closed表 |
| 1 | |
| 2,3 | 1 |
| 4,t1,3 | 1,2 |
| A,t2,t1,3 | 1,2,4 |
| 3 | 1,2,4 |
| 5,B | 1,2,4,3 |
| t3,t4,8 | 1,2,4,3,5 |
機器博弈:方法：Max-Min搜索、α-β剪枝
博弈的問題表示：博弈樹表示
- 一種特殊的與或樹
- 節點：博弈的格局（即棋局），相當于狀態空間中的狀態， 反映了博弈的資訊， 并且與節點、或隔層交替出現，
解釋一下：我方行棋時，每一步之間是任選的，在邏輯上是或運算，對方行棋時，我方需要應付對方的每一步，在邏輯上是與運算
基本思想：
- 目的是為博弈的雙方中的一方尋找一個最優行動方案； 要尋找這個最優方案，就要通過計算當前所有可能的方案來進行比較
解釋一下：在當前狀態下，為了尋找最優的下一步方案，我們計算出來所有的行動方案(不知一步)，通過某種演算法進行比較 - 方案的比較是根據問題的特征來定義一個估價函式，用來估算當前博弈樹端節點的得分；
- 當計算出端節點的估值后，再推算出父節點的得分（即計算倒推值）
- 對或節點，選其子節點中一個最大得分作為父節點的得分
- 對與節點，選其子節點中一個最小得分作為父節點的得分
- 如果一個行動方案能獲得較大的倒推值，則它就是當前最好 的行動方案，
Max-Min搜索
步驟：
- Step1：以 c(o) 為根，生成 k-步博弈樹；
- Step2：評估博弈樹葉節點對應的博弈狀態(棋局)；
為特定的博弈問題定義一個估價函式est(c)，用以評估k-步博弈樹葉節點對應的棋局c
est(c)的值越大，意味著棋局c對Max越有利， - Step3：進行極大極小運算 (Max-Min 運算)；
由葉節點向根節點方向回溯評估，在Max處取最大評估值(或運算)，在Min 處取最小評估值(與運算)，
確保我方必定能贏，在Max處取最大評估值(或運算)，我方最優勢
確保敵方必定能輸，在Min 處取最小評估值(與運算)，敵方最劣勢 - Step4：等待 Min 行棋，產生新的 c(o)，回傳 step1.
舉例：(大抵只能出這個題了)
一字棋： 設有 3*3 棋格，Max 與 Min 輪流行棋，黑先白 后，先將 3 顆棋子連成一線的一方獲勝，
解：定義估價函式：est(c) (怎么說呢，這規則就挺難寫的)
對于非終局的博弈狀態c，估價函式為： est(c)=(所有空格都放上黑色棋子之后,3顆黑色棋子連成的直線總數)－ (所有空格都放上白色棋子之后,3顆白色棋子連成的直線總數)
若 c 是 Max 的勝局，則： est(c) = +∞
若 c 是 Min 的勝局，則： est(c) = –∞
用叉號表示MAX，用圓圈代表MIN，
3*3棋局有些旗子位置是等價的，不用出重復列出來了
這里有一個倒退值之間的計算，與節點的并列的子節點往上倒推取最小值，或節點的并列的子節點往上倒推取最大值，
α-β剪枝：基本思想，邊生成博弈樹邊計算評估各節點的倒推值，并且根據評估出的倒推值范圍，及時停止擴展那些已無必要再擴展的子節點
α-β剪枝演算法的剪枝規則
- 對于一個 與節點來說，它取當前子節點中的最小倒推值作為它倒推值的上界，稱此為β值；(β<= 最小值 )
- 對于一個 或節點來說，它取當前子節點中的最大倒推值作為它倒 推值的下界，稱此為α值.（α >= 最大值）
作業：設有如下圖所示的博弈樹，其中最下面的數字是假設的估值，該博弈樹做如下作業：
- 計算各節點的倒推值
- 利用α-β剪枝技術剪去不必要的分枝，
第四章：邏輯推理技術
消解原理
基本概念：
- 文字：一個原子公式和原子公式的否定都叫做文字 P(x)， ?P(x,f(x))，
- 子句：由文字的析取組成的公式 P(x)∨Q(x) .... ?P(x,f(x))∨Q(x,g(x))
- 子句集：由子句構成的集合， {P(x)∨Q(x) , ~P(x，f(x)∨Q(x,g(x)) }
- 合取范式：C1 ∧C2 ∧C3… ∧Cn 由合取連接形成的公式
- 消解
子句集的求取，分為九步：
- 消去蘊涵符號 只應用∨和～符號，以～A∨B替換A→B
- 減少否定符號的轄域，每個否定符號～最多只用到一個謂詞符號上，并反復應用狄·摩根定律
以～A∨～B代替～(A∧B）
以～A∧～B代替～(A∨B)
以(?x){～A}代替～(?x)A
以(?x){～A}代替～(?x)A
以A代替～(～A) - 對變數標準化 兩個變數的轄域不重復，若重復，就換變數
- 消去存在量詞 分兩種情況
如果要消去的存在量詞在某些全稱量詞的轄域內，用Skolem函式替換(?y)[(?x)P(x,y) 所存在的x可能依賴于y值 所以令 x = g(y) (?y)P(g(y),y)
消去的存在量詞不在任何一個全稱量詞的轄域內 用常量替換 -
化為前束形
-
把母式化為合取式， 謂詞公式和(或)謂詞的否定的析取的有限集組成的合取
常用公式 A∨{B∧C} 化為 {A∨B}∧{A∨C} A∨{B∨C} 化為 {A∨B∨C} -
消去全稱量詞
-
消去連詞符號 ∧
-
更換變數名稱
舉例： (?x) (?y) {P(x,y) ∨ [Q(x,y) → R(x,y)]}
第一步：消蘊含 (?x) (?y) {P(x,y) ∨ [ ~ Q(x,y) ∨ R(x,y)] }
第二步：減少否定的轄域 (?x) (?y) {P(x,y) ∨ [ ~ Q(x,y) ∨ R(x,y)] }
第三步：變數標準化 (?x) (?y) {P(x,y) ∨ [ ~ Q(x,y) ∨ R(x,y)] }
第四步：消去存在量詞 全稱量詞x 的轄域 (?y) {P(x,y) ∨ [ ~ Q(x,y) ∨ R(x,y)] } 存在量詞y的轄域 {P(x,y) ∨ [ ~ Q(x,y) ∨ R(x,y)] }
所以采用 Skolem函式 令 y = g(x) (?x) {P(x,g(x)) ∨ [ ~ Q(x,g(x)) ∨ R(x,g(x))] }
第五步 ：化為前束形 (?x) {P(x,g(x)) ∨ [ ~ Q(x,g(x)) ∨ R(x,g(x))] }
第六步 ：母式華為合取范式 {P(x,g(x)) ∨ ~ Q(x,g(x)) ∨ R(x,g(x)）}
第七步：消去全稱量詞 {P(x,g(x)) ∨ ~ Q(x,g(x)) ∨ R(x,g(x)）}
第八部 ：消去合取符號 {P(x,g(x)) ∨ ~ Q(x,g(x)) ∨ R(x,g(x)）}
第九步：更換變數名稱 {P(x,g(x)) ∨ ~ Q(x,g(x)) ∨ R(x,g(x)）}
注：說一下子句集化簡要求(掌味訓本的化簡要求即可)，練習題的謂詞公式給的比較復雜，可以作為檢驗內容，實際問題中不會那么多符號的，
消解歸結
(證明題)：設F1、 … 、Fn、G為公式，G為F1、 … 、Fn的邏輯推論，當且僅當公式（（F1∧…∧Fn）→G）①是有效的.(如何 F 那么G ，通過合式公式性質A→B 等價于～A∨B
可以得到)，~(F1∧…∧Fn ) ∨ G ②，然后取否定 (F1∧…∧Fn ) ∧ ~G ③ 證明③式矛盾(不成立)，來說明 ②式成立，繼而①式成立
消解的定義：令L1,L2為兩任意原子公式： L1和L2具有相同的謂詞符號，但一般具有不同的變數，已知兩個子句 L1 ∨ α和～ L2 ∨ β，如果L1和L2具有最一般合 一σ,那么通過消解可以從兩個父輩子句推匯出一個新子句（α∨β）σ ， 這個新子句叫做消解式，
(注：消解步驟 1.找相同的謂詞公式 存在公式及其否定 2.找兩者之間的最一般合 一σ 3.剩余部分之間做析取，然后做置換σ 必須會）
重言式：公式及公式的否定兩者取析取
舉例 1.：(要求 ：熟悉消解反演證明的步驟)
前提：(P →Q) ∧~Q 結論： ~P
證明步驟：一 .對前提(條件) 和 結論的否定 化成子句集形式
( ~P ∨ Q）∧ ~Q ，然后 { ~P ∨ Q， ~Q } 在加上結論的否定 得到 { ~P ∨ Q， ~Q，P} 不妨設定編號為 1,2,3
二 使用消解原則進行歸結
1,2歸結得到 ~P 命名為4 3,4歸結得到 NIL 所以原命題成立
舉例2：練習題
已知：F：(?x)[(?y) ( A(x,y) ∧ B(y)) → (?y) ( C(y) ∧ D(x,y))]
G: ~(?x) C(x) → (?x)(?y) (A(x,y) → ~ B(y))
求證：G是F的邏輯結論，
解：首先：將 F 和 ~G 化后子句集形式 (注：我覺得按照G的形式 先化簡，后帶入~ 能簡單點)
F：(?x)[(?y) ( A(x,y) ∧ B(y)) → (?y) ( C(y) ∧ D(x,y))]
(?x)[ ~ [(?y) ( A(x,y) ∧ B(y))] ∨ (?y) ( C(y) ∧ D(x,y))]
(?x)[ (?y) ( ~ A(x,y) ∨ ~B(y)) ∨ (?y) ( C(y) ∧ D(x,y))]
(?x)[ (?y) ( ~ A(x,y) ∨ ~B(y)) ∨ (?w) ( C(w) ∧ D(x,w))]
全稱量詞 x 的轄域 [ (?y) ( ~ A(x,y) ∨ ~B(y)) ∨ (?w) ( C(w) ∧ D(x,w))] 全稱量詞 y:( ~ A(x,y) ∨ ~B(y)) 存在量詞w：( C(w) ∧ D(x,w))
令 w = f(x) (?x)[ (?y) ( ~ A(x,y) ∨ ~B(y)) ∨ ( C(f(x)) ∧ D(x,f(x)))]
(?x) (?y)[ ( ~ A(x,y) ∨ ~B(y)) ∨ ( C(f(x)) ∧ D(x,f(x)))]
( ~ A(x,y) ∨ ~B(y) ∨ C(f(x)) ) ∧ ( ~ A(x,y) ∨ ~B(y) ∧ D(x,f(x)))
{ ~ A(x,y) ∨ ~B(y) ∨ C(f(x)), ~ A(x,y) ∨ ~B(y) ∧ D(x,f(x))} 給定編號：1,2
G:~(?x) C(x) → (?x)(?y) (A(x,y) → ~ B(y))
~[ ~(?x) C(x) ] ∨ (?x)(?y) (A(x,y) → ~ B(y)) 在來一次 ~[ ~(?x) C(x) ] ∨ { ~ (?x)(?y) (A(x,y) ∨ ~ B(y) }
(?x) C(x) ∨ { (?x)(?y)~ (A(x,y) ∨ ~ B(y) }
(?u) C(u) ∨ { (?x)(?y)~ (A(x,y) ∨ ~ B(y) }
令 u= z , x = a , y = b C(a) ∨ { ~ (A(a,b) ∨ ~ B(b) }
C(a) ∨ ~ (A(a,b) ∨ ~ B(b)
所以 ~G: ~ [C(a) ∨ ~ (A(a,b) ∨ ~ B(b) ] = ~C(a) ∧ (A(a,b) ∧ B(b)
~G:{ ~C(a) , A(a,b) , B(b) } 給定編號：3,4,5
然后 使用消解原則進行歸結 (注：歸結順序可以不一樣，)
~B(b) ∨ C(f(x)） 14歸結 a/x b/y 得到 6
~B(b) 3,6歸結 a/f(x) 得到 7
NIL 5,7歸結 得到8
所以G是F的邏輯結論
舉例3：(注：實際問題求解）
某公司招聘作業人員，A、B、C三人應試，經面試 后公司表示如下想法：
（1）三人中至少錄取一人，（2）如果錄取A而不錄取B，則一定錄取C， （3）如果錄取B，則一定錄取C，
求證：公司一定錄取C，
解：首先 向所給出的條件和知識用謂詞公式表示
定義:P(x) 表示 公司錄取 x
(1) P(A)∨ P(B) ∨P(C) （2） [ P(A)∧ ~P(B) ] → P(C) （3） P(B) → P(C) 結論：P(C)
將謂詞公式表示成子句集形式，并給出編號 (注：可以不用分開寫，寫出謂詞公式后面緊跟寫出子句集)
{P(A)∨ P(B) ∨P(C)} 1 { ~ P(A) ∨P(B) ∨ P(C)} 2 { ~P(B) ∨ P(C) } 3 {~P(C)} 4
歸結，得出結論
P(B) ∨ P(C) 1,2歸結 得到 5
P(C) 3,5歸結 得到 6
NIL 4,6歸結 得到 7
所以：公司一定錄取C
反演求解
(求解題)：程序
- 用謂詞公式表示知識(條件)，并化成子句集
- 目標公式和目標公示的否定做析取，構成重言式
- 使用消解原理進行歸結，最后得到問題的解
關鍵想法是把問題化為一個包含某個存在量詞的目標公式，使得此存在量詞量化變數表示對該問題的一個解答，
解釋：將所要回答的問題，化成 (?x) P(x) 的形式
舉例1 ：如果無論約翰(John)到哪里去，菲多(Fido) 也就去那里，那么如果約翰在學校里，菲多在哪里呢?”
1.定義謂詞 At(x,y) x在y處
(?x) [ At(John,x) → At(Fido,x) ] 化成子句集 ~ At(John,x) ∨ At(Fido,x) 編號1
At(John,School ) 編號2
2.目標公示 菲多在哪里呢？ 理解：存在一個地方z，菲多在z處 (或者可以換一種理解 菲多同一時間下只能在一個地方，不能在多個地方)
需要你去體會存在量詞，(這種題只能是存在量詞)
(?x) At(Fido,x)
重言式： ~At(Fido,x) ∨ At(Fido,x) 編號3
3.進行歸結
~ At(John,x) ∨ At(Fido,x) 1,3歸結 得到4
At(Fido,School） 2,4歸結 得到5
所以：菲多在學校
(注：這題不難，就是給出一個反演求解的一個大致模型，好好體會一下求解的程序)
(注：反演求解考題難度不高)
舉例2：(?x)(?y)(?z) [ Father(z,x) ∧ Brother(x,y) → Father(z,y)]
Father(Jim,John) Brother(John,Bob)
問：誰是Bob的父親？ (?u) Father(u,Bob), u=?
解：重言式，歸結
規則演繹系統:(這塊規則過于繁瑣，練習題那個難度就挺大的 不打算看了)
基于規則的演繹推理是一種直接的推理方法，把有關問題的知識和資訊劃分為規則和事實兩種型別，
規則由包含蘊含形式的運算式表示，
事實由無蘊含形式的運算式表示，并畫出相應的與或圖，然 后通過規則進行演繹推理，(注：這與或圖定義就離譜 )
規則演繹系統的表示 if → then if ：前項 then：后項
分類：規則正向演繹推理、規則逆向演繹系統和規則雙向演繹系統，
產生式系統：(這純概念我都不知道看啥)
第五章：不確定性推理
C-F模型
(注：老師說了今天不考，考的話也很簡單)
(注：C-F模型 就是一個基礎公式，不斷在上邊疊加)
基礎公式：IF E THEN H (CF(H,E))
E為前提條件(證據) : CF(E) 證據的可信度
H為結論 ： CF(H)= CF(H,E) ×max［0，CF(E)］ 一般都是求解 CF(H)
CF(H, E)為確定性因子，簡稱可信度，取值[-1 1]表示E對H的支持度
變化1：若組合證據是多個單一證據構成時，
- 組合證據是多個單一證據的合取 ，即 E=E1 AND E2 AND…AND En 則 CF(E)=min{CF(E1), CF(E2)… CF(En)}
- 組合證據是多個單一證據的析取，即： E=E1 OR E2 OR…OR En 則 CF(E)=max{CF(E1), CF(E2)… CF(En)}
變化2：加閾值 λ
- 公式為 IF E THEN H (CF(H,E)，λ)
- 表示含義 ： 只有當 CF(E) 大于等于 λ 這條知識才被采用
變化3 ：加權的證據
- 公式 IF E1(ω1) AND E2(ω2) AND…AND En(ωn) THEN H (CF(H,E)) ωi(i=1,2,…,n)是加權因子
- 此時 CF(E) = w1 * CF(E1) + w2 * CF(E2)+....+wn * CF(En)
(注：題目中 這些變換更多情況是組合形式出現)
舉例1：例設有如下知識：(應用了變換2和變換3，解題步驟也很固定 計算需要計算器把)
R1: IF E1(0.6) AND E2(0.4) THEN E6(0.8,0.75)
R2: IF E3(0.5) AND E4(0.3) AND E5(0.2) THEN E7(0.7,0.6)
R3: IF E6(0.7) AND E7(0.3) THEN H(0.75,0.6)
已知：CF(E1)=0.9, CF(E2)=0.8, CF(E3)=0.7, CF(E4)=0.6, CF(E5)=0.5
求：CF(H)=?
.解：由R1得到：CF(E1(0.6) AND E2(0.4))=0.86>λ1=0.75 ∴R1可被應用，
由R2得到： CF(E3(0.5) AND E4(0.3) AND E5(0.2))＝0.63>λ2 =0.6 ∴R2可被應用，
由R1得到：CF(E6)=0.69 由R2得到：CF(E7)=0.44
由R3得到： CF(E6(0.7) AND E7(0.3))=0.615>λ3 =0.6 ∴R3可被應用 ,得到： CF(H)=0.46
即最終得到的結論H可信度為0.46
模糊推理
(重點：今年要考)
基礎概念：
模糊集合：論域U中的模糊集F用一個在區間[0,1]的取值的隸屬函式 μF來表示，即：μF：U→[0,1]
μF稱為F的隸屬函式，μF(u)稱為u對A的隸屬度， (u是論域U中的元素)
模糊集的表示方法：
(記這一個夠用了) 解釋公式：“/”不是表示相除，它只是一個記號，其分母是論域中的元素，分子是該元素對模糊子集F的隸屬度
特例：μF (ui )/ui 表示ui對模糊集F的隸屬度，當某 個隸屬度為0時，可以略去不寫
舉例：論域U= {1,2,3,4}
A=1/u1 +0.7/u2 + 0/u3 +0.5/u4 和 B=1/u1 +0.7/u2 +0.5/u4 表示相同的模糊集，
模糊集合上的運算
- A∪B 并：所有的 u ∈U 被逐點定義為取大運算: μ A∪B = μA (u) ∨ μB (u) ∨:符號取極大值運算
- A∩B 交：所有的 u ∈U 被逐點定義為取小運算: μ A∩B = μA (u) ∧ μB (u) ∧：符號取極小值運算
- 補：知道有這個東西就夠了 所有的 u ∈U 被逐點定義：取負值 + 1 運算
- 有界和運算：(在模糊關系合成的Rm用到，但是模糊關系合成一般用Ra)
有界和算子 ⊕ A ⊕ B : min{1, μA (u) + μB (u)}
有界積算子 ⊙ A ⊙ B: max{0,μA (u) + μB (u)-1}
模糊關系： (說明一下 ： U × V 是笛卡爾乘積)
(注：說理解吧 模糊關系：1.兩個論域之間先做笛卡爾乘積 U × V，得到一個新論域，2.論域中的元素 按照某種運算得到其隸屬度 ， 這個新的隸屬度就是模糊關系）
模糊集的笛卡爾乘積
(注：1.模糊集的笛卡爾乘積 感覺像是一種比較簡單的模糊關系合成演算法，從結果上說 給出了論域 U × V的隸屬度集合
補：模糊集的笛卡爾乘積 就是模糊關系構造中的 Mamdani方法 ，但是這方法用不到
2. 為稍后 模糊關系的合成做準備）
模糊關系的合成 (大題的最后一步)
設R1與R2分別是U×V 及 V×W上的兩個模糊 關系，則R1與R2的合成是指從U到W的一個模糊關系，記為：R1 °R2
(注: 按照矩陣乘法規則 對應元素之間做 交 運算，得到的中間結果 做 并 運算得到最終結果）
準備做題：
簡單模糊推理
模糊關系合成
(注：一般考題計算步驟 通過Rm構造模糊關系，然后再于證據合成)
(注：別問問啥只記最簡單的)
舉例：
(注：模糊推理我打算寫到這里就結束了 如果你覺得不過癮的話，我可以再給你推薦
模糊匹配問題 描述一下：知識 IF x is A THEN y is B 現在有證據 x is A'，x is A'',x is A''' 請問應該采用哪條證據進行模糊關系合成
沖突消解問題 描述一下 ：知識1 IF x is A' THEN y is B' 知識2 IF x is A'' THEN y is B'' 知識3 IF x is A''' THEN y is B''' 現有證據 x is A 請問哪條知識先被應用)
(注：說明一下 第六章以后 ，沒有好好聽過課 而且重點不明確 不好整理 我覺得可以不用接著看了 沒啥底氣)
第六章：計算智能
基本概念：
- 計算智能就是受自然界（生物界）規律的啟迪， 根據其原理，模仿設計求解問題的演算法，
- 目前這方面的內容很多，如：神經網路、進化計算、人工生命、群集智能技術、人工免疫系統技術等領域
進化計算
- 進化計算是一類模擬生物進化程序與機制求解問題的自組織、自適應技術，
- Darwin進化論最重要的是適者生存原理， Mendel遺傳學說最重要的是基因遺傳原理
- 依照達爾文的自然選擇和孟德爾的遺傳變異 理論，生物的進化是通過繁殖、變異、競爭、 選擇來實作的，進化演算法就是建立在上述生物模型基礎上的一種隨機搜索技術
- 進化演算法的分類：遺傳演算法、進化規劃和進化策略，
- 進化演算法的兩大特點：種群搜索策略和種群中個體之間的資訊交換
遺傳演算法 (這~~~~~~看不懂呀)
一般的遺傳演算法由四個部分組成 : 編碼機制、適應度函式、控制引數、遺傳算子
進化策略（~~~~~）
進化規劃 (~~~~) （你敢出 我敢不會）
第七章：群智能演算法
基本概念
- 人們把群居昆蟲的集體行為稱作“群智能”，即低智能的主體通過合作表現出高智能行為的特性，
- 群智能演算法是一種基于生物群體行為規律的計算技術，
- 典型演算法： 粒子群優化演算法（鳥群捕食） 蟻群演算法（螞蟻覓食）
炸了 這后邊都是什么鬼玩意 放棄了 到此為止
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/243834.html
標籤：其他
上一篇：計算機網路試題