【正文】 1 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 人工智能 第 3 章 謂詞邏輯和歸結(jié)原理 邏輯 : 推理的理論和根據(jù) . 邏輯的分類 , 經(jīng)典邏輯和非經(jīng)典邏輯 命題邏輯和謂詞邏輯 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 人工智能 命題邏輯 1。 什么是命題？ 2。 什么是命題連接詞？ 3。 什么命題公式（ Wellformed formula, WFF）？ 4。 什么是命題演算語句解釋？ 5。什么是命題演算語句在某解釋下的真值？ 6。什么是命題演算語句的真值表？ 7。什么是恒真的命題公式 ? 8。如何進(jìn)行命題邏輯的推理 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 人工智能 命題邏輯的推理規(guī)則 符號和語句 定義 : 命題演算符號包括命題符號 : P, Q, R, S,... 真值符號 : true, false 連接詞 : ∧, ∨, ┐, → , ?, 定義 : 命題邏輯公式（ Wellformed formula, WFF） 利用命題演算符號， 真值符號和邏輯連接詞組成 的合法符號串。 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 人工智能 合取項(xiàng) (conjunct) 析取項(xiàng)（ disjunct） 蘊(yùn)涵式（ implication） 前提（ premise） , 前項(xiàng) (antecedent) 結(jié)論（ conclusion） , 后項(xiàng)（ consequent） 命題語句的例 P, Q, R, ┓P, ┓Q, P∧Q, P∧Q→R, ┓P∨┓Q, ┓P∨┓Q ∨R (P∧Q)→R ? ┓P∨┓Q ∨R 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 人工智能 命題語句就是一個符號串， 只有對串中的命題符號指定了真假值之后， 這個語句才具有實(shí)際意義。 命題演算的語義 由單個邏輯運(yùn)算符連接的簡單語句的語義 定義：命題語句的語義 對每一個命題指定其真假值。 按由單個邏輯運(yùn)算符連接的簡單語句的語義遞歸地求出整個語句的真假值。 解釋： 對命題指定其真假值 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 人工智能 同一個命題語句在不同的解釋之下有不同的真值。 如果一個命題語句具有 n 個命題， 則其具有 2n種不同的解釋 真值表： 設(shè) s 使一個命題語句， s 的真值表是對 s 的所有可能解釋的真值。 P Q F F T T F F T T F F T T P∧ Q 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 人工智能 P ┓ P Q ┓ PVQ P→Q (┓ PVQ)? P→Q T T F F T F T F F F T T T F T T T F T T T T T T 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 人工智能 命題邏輯的等價 命題邏輯中常用的等價公式 PP ???)()( PP ?????QPQP ????QPQP ?????? )())(()( RQPRQP ?????)()()( RPQPRQP ??????QPQP ?????? )())(()( RQPRQP ?????)()()( RPQPRQP ??????吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 人工智能 命題邏輯的推理規(guī)則 推理規(guī)則是用一些命題公式 A1, A2,? 推導(dǎo)出另外一些命題公式 B1, B2,? 附加 : A = A∨B 簡化 : A∧B =A 假言推理 : A→B, A = A 拒取式 : A→B, ┐ B = ┐ A 析取三段論 : A∨B, ┐ A =B 假言三段論 : A→B, B→C = A→C 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 人工智能 命題邏輯的推理規(guī)則 例 1證明 {(P?Q)， (P??R)， (S?T), (? S?R), ?T}?Q 1. S?T 前提引入 2. ?T 前提引入 3. ? S 1,2, 拒取規(guī)則 4. ? S?R 前提引入 5. R 3,4 假言推理 6. P? ? R 前提引入 7. ?P 5， 6；拒取規(guī)則 8. P?Q 前提引入 9. Q 7,8, 析取三段論 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 人工智能 命題邏輯的推理規(guī)則 寫出對應(yīng)下面推理的證明 如果今天下雨 . 則要帶傘或雨衣 , 如果走路上班 , 則不帶雨衣 ,今天下雨 ,走路上班 , 所以帶傘 . P:今天下雨 Q:帶傘 R:帶雨衣 S:走路上班 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 人工智能 命題邏輯的推理規(guī)則 {P ? (Q∨R) ， (S??R)， P, S}?Q 1. P ? (Q∨R) 前提引入 2. P 前提引入 3. Q∨R 1,2,假言推理 4. S??R 前提引入 5. S 前提引入 6. ? R 4,5,假言推理 7. Q 3,6, 析取三段論 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 人工智能 命題邏輯歸結(jié)方法 前面給出的命題邏輯的證明過程需要很多思考過程， 人可以用來實(shí)施推理，但卻不適用于計算機(jī)。 本節(jié)我們介紹一中推理方法 —— 歸結(jié)方法，它以機(jī)械的方式實(shí)施推理， 容易使用計算機(jī)實(shí)現(xiàn)，我們先介紹它的簡單情形，即命題邏輯的歸結(jié)， 然后在下一節(jié)介紹謂詞邏輯歸結(jié)。 命題邏輯證明過程之所以復(fù)雜的一個重要原因是命題公式的形式是各種各樣的。 證明系統(tǒng)必須有處理各種各樣命題公式的能力。 為了簡化命題公式的形式， 人們提出了一種簡單而又有足夠表達(dá)能力的形式，這就是子句。 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 人工智能 命題邏輯歸結(jié)方法 為敘述方便， 我們把命題原子稱作正文字， 例如 P, Q, R?., 等等， 把帶有非符號的命題原子叫做負(fù)文字，例如 ?P, ?Q, ?R?., 等等，把正文字和負(fù)文字統(tǒng)稱為文字。 單個文字， 文字的析取構(gòu)成的命題邏輯公式叫做子句。 例如， P, ?Q, ?P ∨Q ∨ ?R都是子句。 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 人工智能 命題邏輯歸結(jié)方法 ? 一個命題邏輯公式可以采用如下方式轉(zhuǎn)換成等價的子句的合取形式 , 即合取范式： ? 1. 利用等價公式 P←→ Q =( P→Q) ∧ (Q←P) 和 P→Q=~P ∨ Q刪去公式中的 ←→ 符號和 → 符號 . ? 2. 利用 De Man 律把所有的否定符號移到每個原子之前 . ? 3. 利用分配律得到子句的合取形式 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 人工智能 命題邏輯歸結(jié)方法 例 把命題邏輯公式 ~ (~(P→Q) ∧ (~ Q∨ R))轉(zhuǎn)換成等價的子句的合取形式 . ~ (~(P→Q) ∧ (~ Q∨ R)) = ~ (~ (~P∨ Q) ∧ (~ Q∨ R)) = (~P∨ Q) ∨ ~ (~ Q∨ R)) = (~P∨ Q) ∨ ( Q∧ ~ R)) = (~P∨ Q) ∧ (~P∨ Q∨ ~ R)) 上式即為子句的合取形式 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 人工智能 命題邏輯歸結(jié)方法 命題歸結(jié)式 設(shè) c1, c2是兩個子句， c1=L1∨ D1, c2=L2∨ D2 , 其中 L1 =~ L2， L1 ， L2也稱作互補(bǔ)文字， D1和 D2 為子句． 則D1∨ D2稱作 c1, c2的歸結(jié)式， 記為 R(c1, c2), c1, c2稱做是歸結(jié)式的親本子句。 ? 例如， 設(shè) c1, c2是兩個子句， c1 = ~P∨ Q, c2 = P∨ R∨ ~ S, 則 ~P和 P為互補(bǔ)文字 , c1, c2的歸結(jié)式是 Q∨ R∨ ~ S. 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 人工智能 命題邏輯歸結(jié)方法 在利用歸結(jié)推導(dǎo)證明某一邏輯結(jié)果時，我們采用如下的歸結(jié)反駁證明方法。設(shè) F ={f1, f2,…, fn} 是命題邏輯公式集合， g 是命題邏輯公式，為了證明從 F能推導(dǎo)出 g， 我們先把邏輯公式 f1, f2,…, fn 轉(zhuǎn)換成子句或子句集，把 g 的否定～ g 也轉(zhuǎn)換成子句或子句集， 然后把這些子句放在一起， 組成一個子句集，在此子句集上應(yīng)用歸結(jié)， 把所得到的歸結(jié)式不斷地加入到子句集中， 繼續(xù)進(jìn)行歸結(jié)，當(dāng)子句集中包含空子句時，則認(rèn)為是已經(jīng)從 F推導(dǎo)出 g. 這種歸結(jié)反駁證明的核心思想是反證法， 空子句表示矛盾。在證明過程中用□表示。如果把要證的結(jié)論的否定加入到前提集合中能導(dǎo)出矛盾， 則證明了該結(jié)論。理論上可以證明，命題中歸結(jié)反駁證明方法是可靠的。 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 人工智能 命題邏輯歸結(jié)方法 例：證明 (P → Q) →( ～ Q → ～ P)} 前提集合 F={(P → Q) }, 結(jié)論 = (～ Q → ～ P)。 F中命題公式轉(zhuǎn)換成的子句集是 {～ P∨Q} ～ g 轉(zhuǎn)換成的子句集是 {～ Q, P } 把上述子句集組合在一起，得到初始子句集 Φ ={～ P∨Q, ～ Q, P } 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 人工智能 命題邏輯歸結(jié)方法 以下為歸結(jié)過程 1. ～ P∨ Q 2. ～ Q 3. P 1,2 歸結(jié) 4. Q 2,4 歸結(jié) 5 □ 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 人工智能 謂詞邏輯基礎(chǔ) 謂詞的基本概念 個體詞 : 表示具體的客體 , 如 : 小王 , 工程師 , 8, 自然數(shù) . 謂詞 : 表示個體的性質(zhì)和個體間的關(guān)系 , 小王是個工程師 8 是自然數(shù) 變量符號： v1, w2, table3, 常量符號 : A, Dog, Wang1. 函數(shù)符號 : f(x), g(u, v) 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 人工智能 定義：符號和項(xiàng) 由變量符號，常量符號，函數(shù)符號和邏輯常量組成的 合法字符串。 定義：謂詞和原子語句 謂詞是取值范圍為 {0（假）， 1（真） }的函數(shù)。 單獨(dú)一個謂詞構(gòu)成的語句為原子語句。 例 : P(x), Q(x,y), R(X,b) 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 人工智能 量詞 全稱量詞 對于日常生活和數(shù)學(xué)中出現(xiàn)的“一切的”、“任意的”、“所有的”、“每一個”、“都”、“凡”等詞統(tǒng)稱為全稱量詞，用符號“ ?”表示。并用 ?x， ?y表示個體域中的所有個體，用（ ?x ） F（ x），（ ?y） F（ y）等表示個體域中的所有個體具有性質(zhì) F。 存在量詞 對日常生活和數(shù)學(xué)中常用的“存在”、“存在一個”、“有一個”、“至少有一個”、“有些”、“有的”等詞統(tǒng)稱為存在量詞，用符號“ ?”表示。并用 ?x， ?y表示個體域中有的個體，用（ ?x） F（ x），（ ?y） F（ y）等表示個體域中有的個體具有性質(zhì) F。 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 人工智能 量詞的例 例 將下面的命題符號化： （ 1）所有人都是要死的。 （ 2）有的人活到 100歲以上。 其中：個體域 D為人類集合。 解 令 R（ x）： x是人 , P(x): x要死的； Q（ x）：活到 100歲以上。 則（ 1）可符號化為： ?x（ R（ x） ?P（ x）） （ 2）可符號化為 ?x（ M（ x） ∧ Q（ x）） 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 人工智能 使用量詞需要注意 在不同的個體域中 , 符號化的形式可能不一樣 . 使用量詞需要注意 : 多個量詞同時出現(xiàn)時 , 不能顛倒它們的次序 例如 : “ 對