【正文】 A為起點(diǎn)的和終點(diǎn)的總數(shù)據(jù)庫(kù)都滿足終止條件 . ? 這種圖搜索控制策略將在第三章討論 . 推銷(xiāo)員旅行問(wèn)題 ? 例 推銷(xiāo)員旅行問(wèn)題（旅行商問(wèn)題） ? 一個(gè)推銷(xiāo)員計(jì)劃出訪推銷(xiāo)產(chǎn)品。要求尋找最短路線。選擇一個(gè)狀態(tài)表示，表示出所求得的狀態(tài)空間的節(jié)點(diǎn)及弧線，標(biāo)出適當(dāng)?shù)拇鷥r(jià)，并指明圖中從起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最佳路徑。 ? 該方法也就是從 目標(biāo) (要解決的問(wèn)題 )出發(fā)逆向推理，建立子問(wèn)題以及子問(wèn)題的子問(wèn)題，直至最后把初始問(wèn)題歸約為一個(gè)平凡的本原問(wèn)題集合 。 問(wèn)題歸約法的組成部分 ? （ 1）一個(gè)初始問(wèn)題描述； ? （ 2）一套把問(wèn)題變換為子問(wèn)題的操作符； ? （ 3）一套本原問(wèn)題描述。 在每個(gè)圓盤(pán)的中心有個(gè)孔 ， 所以圓盤(pán)可以堆疊在柱子上 。 ? 要求把所有圓盤(pán)都移到柱子 3上 ， 每次只許移動(dòng)一個(gè) ， 而且只能先搬動(dòng)柱子頂部的圓盤(pán) ， 還不許把尺寸較大的圓盤(pán)堆放在尺寸較小的圓盤(pán)上 。 梵塔難題 (a) 初始狀態(tài) (b) 目標(biāo)狀態(tài) 分析 ? 原始問(wèn)題歸約（簡(jiǎn)化）為三個(gè)子問(wèn)題 移動(dòng) A， B盤(pán)至柱子 2的雙圓盤(pán)難題 移動(dòng)圓盤(pán) C至柱子 3的單圓盤(pán)問(wèn)題 移動(dòng) A， B盤(pán)至柱子 3的雙圓盤(pán)難題 分析 ? 可以用狀態(tài)空間表示的三元組合 (S、 F、 G)來(lái)規(guī)定與描述問(wèn)題；對(duì)于梵塔問(wèn)題，子問(wèn)題［（ 111） →(122) ］，［ (122)→(322) ］以及［ (322)→(333) ］規(guī)定了最后解答路徑將要通過(guò)的腳踏石狀態(tài) (122)和 (322)。 與或圖表示 例如，設(shè)想問(wèn)題 A需要由求解問(wèn)題 B、 C和 D來(lái)決定，那么可以用一個(gè)與圖來(lái)表示 (左圖 ) 同樣，一個(gè)問(wèn)題 A或者由求解問(wèn)題 B、或者由求解問(wèn)題 C來(lái)決定，則可以用一個(gè)或圖來(lái)表示 (右圖 ) 與或圖表示 與或圖的一些術(shù)語(yǔ) ? 如果某條弧線從節(jié)點(diǎn) a指向節(jié)點(diǎn) b，那么節(jié)點(diǎn) a叫做節(jié)點(diǎn)b的 父輩節(jié)點(diǎn) ；節(jié)點(diǎn) b叫做節(jié)點(diǎn) a的后繼節(jié)點(diǎn)或后裔； ? 或節(jié)點(diǎn) ，只要解決某個(gè)問(wèn)題就可解決其父輩問(wèn)題的節(jié)點(diǎn)集合； ? 與節(jié)點(diǎn) ，只有解決所有子問(wèn)題，才能解決其父輩問(wèn)題的節(jié)點(diǎn)集合； ? 弧線，是父輩節(jié)點(diǎn)指向子節(jié)點(diǎn)的圓弧連線； ? 終葉節(jié)點(diǎn) ，是對(duì)應(yīng)于原問(wèn)題的本原節(jié)點(diǎn) . 舉例 58 與或圖構(gòu)成規(guī)則 (1) 與或圖中的每個(gè)節(jié)點(diǎn)代表一個(gè)要解決的單一問(wèn)題或問(wèn)題集合。 (2) 對(duì)應(yīng)于本原問(wèn)題的節(jié)點(diǎn)，叫做終葉節(jié)點(diǎn)，它沒(méi)有后裔。 (4) 一般對(duì)于代表兩個(gè)或兩個(gè)以上子問(wèn)題集合的每個(gè)節(jié)點(diǎn)，有向弧線從此節(jié)點(diǎn)指向此子問(wèn)題集合中的各個(gè)節(jié)點(diǎn)。 (5) 在特殊情況下，當(dāng)只有一個(gè)算符可應(yīng)用于問(wèn)題 A，而且這個(gè)算符產(chǎn)生具有一個(gè)以上子問(wèn)題的某個(gè)集合時(shí)，由上述規(guī)則 3和規(guī)則 4所產(chǎn)生的圖可以得到簡(jiǎn)化。 59 作業(yè) ? P54 25 ? 試用 四元 數(shù)列結(jié)構(gòu)表示 四圓盤(pán)梵塔問(wèn)題 ，并畫(huà)出求解該問(wèn)題的與或圖。 ? ?? 在命題邏輯中， “命題 ”被看作最小單位。 命題邏輯 ? 什么是命題？ ? ?? 命題是陳述客觀外界發(fā)生事情的陳述句。 ? 特征： ? ?? 陳述句 ? ?? 真假必居其一 , 且只居其一 . 命題邏輯 ? 例 1 下列句子是命題嗎？ ? ?? 8小于 10. ? ?? 8大于 10. ? ?? 任一個(gè) 5的偶數(shù)可表示成兩個(gè)素?cái)?shù)的和 . ? 答：是 命題邏輯 ? 例 2 下列句子是命題嗎？ ? ?? 8大于 10嗎 ? ? ?? 請(qǐng)勿吸煙 . ? ?? X大于 Y. ? ?? 我正在撒謊 . ? —— 悖論 ? 答：不是 命題邏輯 ? 命題的抽象 ? ?? 以 p、 q、 r等表示命題。 ? 則命題就抽象為： 取值為 0或 1的 p等符號(hào) 。 那么 ? ?? 由聯(lián)結(jié)詞和命題連接而成的更加復(fù)雜命題稱(chēng)為復(fù)合命題；相對(duì)地，不能分解為更簡(jiǎn)單命題的命題稱(chēng)為簡(jiǎn)單命題。 ? 注：簡(jiǎn)單命題和復(fù)合命題的劃分是相對(duì)的。p， “172。p”為真當(dāng)且僅當(dāng) p為假。p. 命題邏輯 ? 合取聯(lián)結(jié)詞 ? ?? 定義 2 設(shè) p、 q為兩個(gè)命題，復(fù)合命題 “p而且 q”稱(chēng)為 p、 q的合取式，記為 p∧ q， “∧ ”稱(chēng)作合取聯(lián)結(jié)詞。 p ∨ q為真當(dāng)且僅當(dāng) p與 q中至少有一個(gè)為真 . ? 例 3的 (3)“期中考試 , 張三和李四中有人考 90分 .”可記為 p ∨ q, 其中 p代表 “張三考 90分 ”,q代表 “李四考 90分 ”。 ? ?? 前者稱(chēng)為 “相容或 ”，后者稱(chēng)為 “相異或 ”。 ? ?? 注意 ：不能見(jiàn)了或就表示為 p∨ q。 “p → q” 假當(dāng)且僅當(dāng) p真而 q假 . ? p→q 這樣的真值規(guī)定有其合理性，也有人為因素。此外，自然語(yǔ)言中對(duì)“如果...，則 ...” 這樣的語(yǔ)句，當(dāng)前提為假時(shí)，結(jié)論不管真假，整個(gè) 語(yǔ)句的真假無(wú)法判斷。此外，自然語(yǔ)言中對(duì)“如果...，則 ...” 這樣的語(yǔ)句， 當(dāng)前提為假時(shí)，結(jié)論不管真假，整個(gè) 語(yǔ)句的真假無(wú)法判斷 。 ? p?q 真當(dāng)且僅當(dāng) p、 q同時(shí)為真或同時(shí)為假 . 命題邏輯 ? 注意 ? ?? 上述五個(gè)聯(lián)結(jié)詞來(lái)源于日常使用的相應(yīng)詞匯 ,但并不完全一致，在使用時(shí)要注意： ? ?? 以上聯(lián)結(jié)詞組成的復(fù)合命題的真假值一定要根據(jù)它們的定義去理解 , 而不能據(jù)日常語(yǔ)言的含義去理解。 ? ?? 有些詞也可表示為這五個(gè)聯(lián)結(jié)詞，如 “但是 ”也可表示為 “∧ ”。q)，其中 : ? p代表 “鐵和氧化合 ”， ? q代表 “鐵和氮化合 ”。P)∧ q)→r ，其中 : ? p代表 “我很累 ”, ? q代表 “我下班早 ”, ? r代表 “我去商店看看 ” 命題邏輯 （ 3）李四是計(jì)算機(jī)系的學(xué)生 , 他住在 312室或 313室 . ? p∧ ((q∨ r)∧ (172。 r)) ∨ ((172。 命題公式：由如下規(guī)則生成的公式稱(chēng)為命題公式： 1. 單個(gè)原子公式是命題公式。 3. 所有命題公式都是有限次應(yīng)用 2得到的符號(hào)串。用 I表示。 永真公式與永假公式：如果公式在它所有的解釋 I下，其值都為 T，則稱(chēng)公式 G為恒真的；如果其值都為 F，則稱(chēng)公式 G為恒假的（不可滿足的）。 ?， ?， ?， ? * 聯(lián)結(jié)詞相同時(shí)，從左至右運(yùn)算。如果將這些真值和它們的解釋列成表，就是 G的真值表。常用的等價(jià)公式有： 1. (P ? Q)= (P ? Q) ? (Q ? P) 2.(P ? Q)=(172。(172。 例如 要證明公式 P ? Q=~Q ? ~P [證 ] P ? Q =~ P ? Q =~ P ?~ (~ Q ) =~(~Q) ?~P =~Q ?~P 命題邏輯 永真蘊(yùn)涵式 若命題公式 G ? H是恒真的 ，稱(chēng)其為永真蘊(yùn)涵式。 永真蘊(yùn)涵式 常用的永真蘊(yùn)涵式： 1. P ? P ? Q [證 ] P ? P ? Q = ~P ? (P ?Q) = ~P ? P ?Q = T ? Q = T 2. P ? Q ? P [證 ] P ? Q ? P =~(P ? Q) ? P = ~P ? ~Q ?P =T ?~Q= T 3. P ? (P ? Q) ? Q 4.( P ? Q) ? ~Q ? ~P 5. ~P ?(P ? Q) ? Q 6.(P ? Q) ?(Q ? R) ? (P ? R) 7.( P ? Q) ?( (Q ? R) ?( P ? R)) 8.((P ? Q) ?( R ? S)) ? (P ? R ? Q ? S) 9.(( P ? Q) ?( Q ? R)) ?( P ? R) 在命題邏輯中有一個(gè)三段論法： P:“ 所有的人都會(huì)犯錯(cuò)誤” Q:“ 張三是人” R:“ 張三會(huì)犯錯(cuò)誤” R應(yīng)該是 P和 Q的邏輯結(jié)論。 為準(zhǔn)確表達(dá)此類(lèi)公式，必須引進(jìn)謂詞和量詞的概念 。如：解釋 : I=P/T,Q/T,R/F 則公式為假值 F. 就是說(shuō)解釋 I 弄假了此公式。 “ 是質(zhì)數(shù)”、“生于”、“ … =... ?...” 都是謂詞。因此引入一個(gè)符號(hào)表示 “是研究生 ”，再引入一個(gè)方法表示個(gè)體的名稱(chēng)，這樣就能把 “某某是研究生 ”這個(gè) 命題的本質(zhì)屬性 刻畫(huà)出來(lái)。 其中 Graduate是謂詞名，張三和李四都是個(gè)體， “Graduate”刻畫(huà)了 “張三 ” 和 “李四 ” 是研究生這一特征。 對(duì)于 “x大于 y”這種兩個(gè)個(gè)體之間關(guān)系的命題 ， 可表達(dá)為 B（ x， y） ， 這里 B表示 “… 大于 … ”謂詞 。 語(yǔ)法與語(yǔ)義 謂詞邏輯的基本符號(hào)：謂 詞符號(hào)、變量符號(hào)、常量符號(hào)、函數(shù)符號(hào)、括號(hào)和逗號(hào) 。 變量符號(hào)：不明確指定是哪一個(gè)實(shí)體。 函數(shù)符號(hào) ：規(guī)定論域內(nèi)相應(yīng)的一個(gè)函數(shù)。 語(yǔ)法與語(yǔ)義 ? 常量符號(hào)是最簡(jiǎn)單的項(xiàng)，用來(lái)表示論域內(nèi)的物體或?qū)嶓w。 ? 句子 “所有的機(jī)器人都是灰色的 ”可表示為 ( ) [ RO B O T ( ) CO L O R( , G RA Y ) ]x x x??我們注意到：這里的 x是被量化的變量 若某個(gè)變量是經(jīng)過(guò)量化的，就把這個(gè)變量叫做約束變量 ，否則叫做 自由變量 。 ? 例：我喜愛(ài)音樂(lè)和繪畫(huà)。析取項(xiàng)是析取式的每個(gè)組成部分 . ? 例：李力打籃球或踢足球 . PLAYS(LILI， BASKETBALL)∨ PLAYS(LILI,FOOTBALL) ? 蘊(yùn)涵（ Implication—用連詞 ?表示 “如果 —那么 ”的 語(yǔ)句 . ? 例：如果劉華跑得最快，那么他取得冠軍 RUNS(LIUHUA FASTEST) ?(LIUHUA，CHAMPION) ? 例如， “如果該書(shū)是何平的，那么它是藍(lán)色的 ” ? OWN（ HEPING， BOOK1)? COLOR（ BOOK1，BLUE） ? 非（ Not) — 用符號(hào) ～ 表示否定的公式（有時(shí)也用 ┑ 表示） ? 例：機(jī)器人不在 例：機(jī)器人不在 2號(hào)房間內(nèi)。 ? 析?。何鋈№?xiàng)至少一個(gè)為真，析取為真。 ? 非：原式真值相反。 ? 例：所有學(xué)生都穿彩色制服 (?x)[Student(X)? Uniform (x, Color)] ? 所有的機(jī)器人都是灰色的 (?x)[Robot(X) ? COLOR(x, GRAY)] 量詞 ? 存在量詞（ Existential Quantifiers ) ? 若一個(gè)原子公式 P(x), 至少有一個(gè)變?cè)?X可使 P(X)為 T值 , 則用 (?x)P(x)表示。 ? 例： (?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) 量詞的轄域 ? 定義：在量詞 ?x， ?x轄域內(nèi)變?cè)?x的一切出現(xiàn)叫約束出現(xiàn)，稱(chēng)這樣的 x為 約束變?cè)? ? 例： 指出下列謂詞公式中的自由變?cè)图s束變?cè)?，并指明量詞的轄域 ? (? x )[P(x) ? R(x)]→( ? x ) P(x) ? Q(x) ? 解：表達(dá)式中的 ? x[P(x)?R(x)]中 x的轄域是 P(x) ? R(x),其中的 x是約束出現(xiàn) ? (? x ) P(x)中 x的轄域是 P(x),其中的 x是約束出現(xiàn) ? Q(x)中的 x是自由變?cè)? 量詞的轄域 ? 例：指出下列謂詞公式中的自由變?cè)图s束變?cè)?, 并指明量詞的轄域。 ? 注：在一個(gè)公式中，一個(gè)變?cè)瓤梢约s束出現(xiàn)，又可以自由出現(xiàn)。 注意事項(xiàng) ? (1) 分析命題中表示 性質(zhì) 和 關(guān)系 的謂詞，分別符號(hào)化為一元和 n（ n ? 2）元謂詞。 ? (3) 在不同的個(gè)體域中，命題符號(hào)化的形式可能不一樣。 ? (4)多個(gè)量詞同時(shí)出現(xiàn)時(shí)，不能隨意顛倒它們的順序，顛倒后會(huì)改變?cè)}的含義。通常把 P（ x1,x2,…,x n）叫做謂詞演算的原子公式 ? 分子謂詞公式 ? 用連詞把原子謂詞公式組成復(fù)合謂詞公式，并把它叫做分子謂詞公式 合 式 公式 （ WFF ,wellformed formulas ） ? 合式公式的遞歸定義 ? 合式公式的性質(zhì) ? 合式公式的真值 等價(jià)（ Equivalence) 合式公式的遞歸定義 1. 原子謂詞公式是合式公式 2. 若 A為合式公式，則 ～ A也是一個(gè)合式公式。 4. 若 A是合適公式， x為 A中的自由變?cè)?，則（ ?x）A和（ ?x） A都是合式公式。 ? 為此，化簡(jiǎn)合式公式到某些約定的標(biāo)準(zhǔn)形式是很有意義的， 合式公式的性質(zhì)則為化簡(jiǎn)工作提供了依據(jù)。 ?