第13章 命題演算

1、第第1313章章 命題演算命題演算 第三部分第三部分 知識的表示和推理知識的表示和推理對特征值加以約束對特征值加以約束 一個一個agentagent環(huán)境的某些信息是很難或者說是不可能環(huán)境的某些信息是很難或者說是不可能由圖標(biāo)來表述的。例如：由圖標(biāo)來表述的。例如： 普遍規(guī)律，如普遍規(guī)律，如“所有的藍(lán)色盒子都是可推動所有的藍(lán)色盒子都是可推動的的”。 否定信息，如否定信息，如“積木積木A A不在地板上不在地板上( (沒有說積木沒有說積木A A在哪兒在哪兒)”)”。 不確定信息，如不確定信息，如“或者積木或者積木A A在積木在積木B B上面，或上面，或者積木者積木A A在積木在積木C C上面上面”。 有

2、些這種難以表述的信息可以用公式表示為對特征有些這種難以表述的信息可以用公式表示為對特征值的約束，這些表示某個值的約束，這些表示某個agentagent所處世界的重要知識的所處世界的重要知識的約約束束常常被用來推斷那些不能被直接感知的特征值。常常被用來推斷那些不能被直接感知的特征值。 對特征值加以約束對特征值加以約束 使用基于特征中約束的計算推斷有關(guān)一個使用基于特征中約束的計算推斷有關(guān)一個agentagent當(dāng)前當(dāng)前(present)(present)狀態(tài)的信息，可以與從一個狀態(tài)的信息，可以與從一個agentagent行為的將來行為的將來(future)(future)狀態(tài)的計算作對照。狀態(tài)的計

3、算作對照。 第一個方法稱為第一個方法稱為“推理推理(reasoning)(reasoning)”，第二個稱為，第二個稱為“投影投影(projecting)(projecting)”。在以下幾章中，先不考慮投影。在以下幾章中，先不考慮投影的問題，而集中討論推理。的問題，而集中討論推理。 包含有關(guān)特征值的推理有幾項應(yīng)用。可以確信，當(dāng)包含有關(guān)特征值的推理有幾項應(yīng)用?？梢源_信，當(dāng)agent(agent(甚至是反應(yīng)型甚至是反應(yīng)型agent)agent)決定行動的時候，推理能增決定行動的時候，推理能增強(qiáng)它們的效力。例如，與強(qiáng)它們的效力。例如，與“原因原因”相聯(lián)系的特征可以從相聯(lián)系的特征可以從與與“癥狀癥狀

4、”相聯(lián)系的特征推斷出。這種方法是人工智能相聯(lián)系的特征推斷出。這種方法是人工智能應(yīng)用中的重要一類應(yīng)用中的重要一類專家系統(tǒng)專家系統(tǒng)(expert system)(expert system)的基礎(chǔ)。的基礎(chǔ)。 對特征值加以約束對特征值加以約束 用一個富有啟發(fā)件的例子來開始推理技術(shù)的討論。用一個富有啟發(fā)件的例子來開始推理技術(shù)的討論。設(shè)想一個能舉起一塊積木的機(jī)器人，假如那個木塊是可設(shè)想一個能舉起一塊積木的機(jī)器人，假如那個木塊是可舉的舉的( (即不是太重的即不是太重的) )，并且假設(shè)這個機(jī)器人有足夠的電，并且假設(shè)這個機(jī)器人有足夠的電池能源。假如以上條件都滿足，那么當(dāng)機(jī)器人試著舉起池能源。假如以上條件都滿足

5、，那么當(dāng)機(jī)器人試著舉起這個它所握住的木塊時，它的手臂就移動?？梢杂枚@個它所握住的木塊時，它的手臂就移動?？梢杂枚堤卣鱽肀硎鲞@些不同的條件：值特征來表述這些不同的條件： x x1 1 ( BAT_OK ) ( BAT_OK ) (電池能源合適電池能源合適) ) x x2 2 ( LIFTABLE ) ( ( LIFTABLE ) (可舉的可舉的) ) x x3 3 ( MOVES ) ( ( MOVES ) (移動移動) )對特征值加以約束對特征值加以約束 假設(shè)機(jī)器人能感知以假設(shè)機(jī)器人能感知以BAT_OK(BAT_OK(通過讀量表通過讀量表) )和和MOVES(MOVES(通通過聯(lián)角傳感

6、器過聯(lián)角傳感器) )，但不能感知，但不能感知LIFTABLELIFTABLE。但知道。但知道LIFTABLELIFTABLE的值對機(jī)器人完成其必須完成的任務(wù)來說是很重要的。的值對機(jī)器人完成其必須完成的任務(wù)來說是很重要的。 從上面的描述，我們知道假如從上面的描述，我們知道假如BAT_OKBAT_OK和和LIFTABLELIFTABLE的值的值都為都為1 1，那么，那么MOVESMOVES也如此。所以，假如當(dāng)這個機(jī)器人試著也如此。所以，假如當(dāng)這個機(jī)器人試著要移動這塊積木時要移動這塊積木時MOVESMOVES值為值為0 0，那么我們知道或者，那么我們知道或者BAT_OKBAT_OK或者或者LIFTA

7、BLE(LIFTABLE(或者兩者或者兩者) )肯定值為肯定值為0 0。如果。如果BAT_OKBAT_OK被感知被感知到值為到值為1 1，那么，那么LIFTABLELIFTABLE值一定為值一定為0 0。 既然我們能如此推理，那么機(jī)器人也可如此。所需要既然我們能如此推理，那么機(jī)器人也可如此。所需要的是一種能用于表達(dá)特征中的約束和特征值的語言的是一種能用于表達(dá)特征中的約束和特征值的語言(language)(language)和能進(jìn)行必要推理的推理和能進(jìn)行必要推理的推理(inference)(inference)機(jī)制。機(jī)制。而而命題演算命題演算(propositional calculus)(pr

8、opositional calculus)作為布爾代數(shù)的作為布爾代數(shù)的一種延伸，為此提供了必要的工具。一種延伸，為此提供了必要的工具。 與這種語言相聯(lián)系的機(jī)制可以用來從這種與這種語言相聯(lián)系的機(jī)制可以用來從這種語句語句(statement)(statement)中推出中推出結(jié)論結(jié)論(consequence)(consequence)。既然邏輯語言在。既然邏輯語言在人工智能中是如此重要，那么，必須在表述基于使用這些人工智能中是如此重要，那么，必須在表述基于使用這些語言的更復(fù)雜和更具智能的語言的更復(fù)雜和更具智能的agentagent之前，對這些語言作更之前，對這些語言作更詳細(xì)的說明。詳細(xì)的說明。 首

9、先是一些定義。邏輯包含首先是一些定義。邏輯包含 一種語言一種語言( (具有一個句法用以規(guī)定在這種語言中具有一個句法用以規(guī)定在這種語言中什么是合法的表達(dá)式什么是合法的表達(dá)式) )。 推理規(guī)則推理規(guī)則用以操作這種語言中的語句。用以操作這種語言中的語句。 語義語義用以把這種語言中的要素和某些主題用以把這種語言中的要素和某些主題(subject matter)(subject matter)中的要素聯(lián)系起來。中的要素聯(lián)系起來。 對特征值加以約束對特征值加以約束 語言語言 下面從形式上描述命題演算中的組成元素。此刻最好下面從形式上描述命題演算中的組成元素。此刻最好不要把某種意義與這種語音的組成元素聯(lián)系起

10、來，把我們不要把某種意義與這種語音的組成元素聯(lián)系起來，把我們現(xiàn)在正在做的想象為對一個無意義的游戲規(guī)則的描述，以現(xiàn)在正在做的想象為對一個無意義的游戲規(guī)則的描述，以后我們再談?wù)撘饬x。以下是這種語言的組成元素：后我們再談?wù)撘饬x。以下是這種語言的組成元素： 原子原子(atom)(atom)：兩個最明顯的原子是兩個最明顯的原子是T T和和F F，還有可數(shù)的，還有可數(shù)的以大寫字母開頭的那些字符串的無限集合以大寫字母開頭的那些字符串的無限集合，如：，如： P P，Q Q，R R，P P1 1，P P2 2，ON_A_BON_A_B，等等。，等等。 聯(lián)結(jié)詞聯(lián)結(jié)詞(connective)(connective)

11、：、 和和 ，分別稱為：，分別稱為：“析取析取(disjunction)”(disjunction)”、“合取合取(conjunction)(conjunction)”、“蘊含蘊含(implication)(implication)”和和“非非(negation)(negation)” ” 。 語言語言 合式公式合式公式(well-formed formulas , wff)(well-formed formulas , wff)( (也稱為也稱為句子句子sentencesentence) )的語法：的語法： 任何原子都是一個合式公式。任何原子都是一個合式公式。 例如：例如： P P，R R，

12、P3P3 假如假如1 1和和2 2是合式公式，那么以下這些也是：是合式公式，那么以下這些也是： 1 1(1 1和和2 2的析取的析取) )； 1 12 2 ( (1 1和和2 2的合取的合取) )； 1 1 2 2 ( (蘊含蘊含) )； 1 1 ( (1 1的非的非) ) 。 不再有別的合式公式。不再有別的合式公式。 原子以及前面帶有原子以及前面帶有 符號的原子叫做符號的原子叫做文字文字(literal)(literal)。在在1 1 2 2中，中， 1 1被稱為被稱為蘊含的前項蘊含的前項(antecedent)(antecedent)，而，而2 2被稱為被稱為蘊含的后項蘊含的后項(cons

13、equent)(consequent)。 語言語言 注意以上例子中有語言外的分隔符注意以上例子中有語言外的分隔符“(” (” 和和 “ “)”)”的使用。它們根據(jù)遞歸定義把合式公式組成的使用。它們根據(jù)遞歸定義把合式公式組成次級次級(sub)(sub)合合式公式式公式。 有些邏輯處理把這兩個分隔符公式化為語言的組成有些邏輯處理把這兩個分隔符公式化為語言的組成部分，然而在此用得有點寬松并且較直觀。合式公式可部分，然而在此用得有點寬松并且較直觀。合式公式可以通過遞歸地使用它們的定義來識別。以通過遞歸地使用它們的定義來識別。例如：例如：是一個合式公式。首先，是一個合式公式。首先， P P和和Q Q是合

14、式公式，所以是合式公式，所以(PQ)(PQ)是合式公式；是合式公式；并且由于并且由于R R是一個合式公式，是一個合式公式， R R也是一個合式公式，因也是一個合式公式，因而，而， 是一個合式公式。是一個合式公式。 RQP )(RQP )(推理規(guī)則推理規(guī)則 從一些合式公式推出另一些合式公式可以有許多方法，稱它們?yōu)閺囊恍┖鲜焦酵瞥隽硪恍┖鲜焦娇梢杂性S多方法，稱它們?yōu)橥评硪?guī)則推理規(guī)則(rule of inference)(rule of inference)。一條推理規(guī)則的典型形式是：。一條推理規(guī)則的典型形式是：可以可以從從( (或從或從和和) )推出。下面是一些通用的推理規(guī)則：推出。下面是一些

15、通用的推理規(guī)則： 合式公式合式公式2 2可以根據(jù)合式公式可以根據(jù)合式公式1 1和和1 1 2 2推出推出( (稱之為稱之為假言假言推理或演繹推理推理或演繹推理(modus ponens)(modus ponens) )。 合式公式合式公式1 12 2可以根據(jù)兩個合式公式可以根據(jù)兩個合式公式1 1和和2 2推出推出( (引入引入) ) 合式公式合式公式2 21 1可以根據(jù)合式公式可以根據(jù)合式公式1 12 2推出推出( (交換交換) ) 合式公式合式公式1 1可以根據(jù)合式公式可以根據(jù)合式公式1 12 2推出推出( (消除消除) ) 合式公式合式公式1 12 2可以根據(jù)單個合式公式可以根據(jù)單個合式公

16、式1 1或單個合式公式或單個合式公式2 2推出推出( (引入引入) ) 合式公式合式公式1 1可以根據(jù)合式公式可以根據(jù)合式公式（1 1）推出）推出( (消除消除) ) 驗證定義驗證定義 合式公式序列合式公式序列1 1 ，2 2 ，n n 被稱為是從被稱為是從一個合式公式集合一個合式公式集合得出的得出的驗證驗證(proof)(proof)( (或或演繹，演繹，deductiondeduction) )，當(dāng)且僅當(dāng)在序列中的每個當(dāng)且僅當(dāng)在序列中的每個i i或者是在或者是在中，或者可以從處于這個序列中的較前的一個中，或者可以從處于這個序列中的較前的一個( (或多個或多個) )合式公式運用若干推理規(guī)則中

17、的一條推出合式公式運用若干推理規(guī)則中的一條推出。假如有一個。假如有一個從從推出推出n n的驗證，就說的驗證，就說n n是集合是集合的一個的一個定理定理(theorem)(theorem)。用下面的標(biāo)記來表示。用下面的標(biāo)記來表示n n可以從可以從得到驗證：得到驗證： n n 驗證和定理的概念是與一個所使用的特定推理規(guī)則驗證和定理的概念是與一個所使用的特定推理規(guī)則集合相關(guān)的。如果我們用字母集合相關(guān)的。如果我們用字母R R來表示推理規(guī)則集合，來表示推理規(guī)則集合，那么我們可以用如下符號寫出這樣的事實：那么我們可以用如下符號寫出這樣的事實： n n可以用可以用R R中的推理規(guī)則從中得到驗證：中的推理規(guī)則

18、從中得到驗證： R R n n 例如：給定一個合式公式的集合例如：給定一個合式公式的集合：P,R,PP,R,P Q Q，下面，下面的序列是一個的序列是一個QRQR驗證它表達(dá)了上面所述的推理規(guī)則：驗證它表達(dá)了上面所述的推理規(guī)則：P,P P,P Q,Q,R,Q Q,Q,R,Q R R 驗證的概念可以基于一個偏序，也可以基于一個序列。驗證的概念可以基于一個偏序，也可以基于一個序列。這種偏序可以由一個樹結(jié)構(gòu)來表示。驗證樹中的每個節(jié)點這種偏序可以由一個樹結(jié)構(gòu)來表示。驗證樹中的每個節(jié)點都標(biāo)上一個合式公式，并且必須或者與都標(biāo)上一個合式公式，并且必須或者與中的一個合式公中的一個合式公式對應(yīng)，或者用若干推理規(guī)則

19、中的一條從樹的父節(jié)點推出。式對應(yīng)，或者用若干推理規(guī)則中的一條從樹的父節(jié)點推出。被標(biāo)記的樹是一個根節(jié)點標(biāo)記的驗證。圖下是一個驗證樹被標(biāo)記的樹是一個根節(jié)點標(biāo)記的驗證。圖下是一個驗證樹的例子。的例子。 驗證定義驗證定義 語義語義 解釋解釋 語義語義(semantics)(semantics)必須把邏輯語言的要素與必須把邏輯語言的要素與論域論域(domain of discourse )(domain of discourse )的要素聯(lián)系起來。這種聯(lián)系的要素聯(lián)系起來。這種聯(lián)系就是我們用就是我們用“意義意義”(meaning)(meaning)這一詞所指的。就命題這一詞所指的。就命題邏輯來說，我們把原

20、子與關(guān)于這個世界的邏輯來說，我們把原子與關(guān)于這個世界的命題命題(proposition)(proposition)聯(lián)系起來聯(lián)系起來( (因而有命題邏輯的稱謂因而有命題邏輯的稱謂) )。 舉例說，我們可以把原子舉例說，我們可以把原子BAT_OKBAT_OK與命題與命題“電池是電池是充了電的充了電的”聯(lián)系起來聯(lián)系起來( (我們并沒有被迫要用助記原子串我們并沒有被迫要用助記原子串來做出這種聯(lián)系，也可以用另外的代替來做出這種聯(lián)系，也可以用另外的代替) )。 原子與命題的聯(lián)系被稱為原子與命題的聯(lián)系被稱為解釋解釋(interpretation)(interpretation)。在給定的解釋中，與一個原子相

21、聯(lián)系的命題被稱為這在給定的解釋中，與一個原子相聯(lián)系的命題被稱為這個原子的個原子的指稱指稱(denotation)(denotation)。語義語義 給定一個解釋，原子為真或假值。假如原子給定一個解釋，原子為真或假值。假如原子與命與命題題P P相聯(lián)系，那么對這個世界來說，只有相聯(lián)系，那么對這個世界來說，只有P P為真時我們才為真時我們才說說為真；反之它就為假。特殊原子為真；反之它就為假。特殊原子T T總是為真，而特殊總是為真，而特殊原子原子F F總是為假。總是為假。 假如一個假如一個agentagent有傳感裝置，這個裝置可以用來決定有傳感裝置，這個裝置可以用來決定各種有關(guān)這個世界的命題的真假，

22、那么當(dāng)感覺特征各種有關(guān)這個世界的命題的真假，那么當(dāng)感覺特征x1x1值值為為1 1時，與此相應(yīng)的有關(guān)這個世界的命題也為真，并且與時，與此相應(yīng)的有關(guān)這個世界的命題也為真，并且與此相聯(lián)系的命題邏輯原子此相聯(lián)系的命題邏輯原子( (也許是也許是x1x1) )也為真。因此，我也為真。因此，我們不用通過在某種輸入們不用通過在某種輸入“線線”上的一個值上的一個值l l或或0 0來為來為agentagent表述感覺到的信息，而是能用一個在表述感覺到的信息，而是能用一個在agentagent的記憶結(jié)構(gòu)的記憶結(jié)構(gòu)( (稱為稱為知識庫，知識庫，knowledge baseknowledge base) )中的命題演算

23、原子來表中的命題演算原子來表述它。述它。 一個原子一個原子x1x1在在agentagent的知識庫中出現(xiàn)就意味著這個的知識庫中出現(xiàn)就意味著這個agentagent把與此相聯(lián)系的命題在它的世界中當(dāng)作真。把與此相聯(lián)系的命題在它的世界中當(dāng)作真。 解解釋釋 命題真值表命題真值表 語義語義 在某種解釋下給定原子的值，我們可以用一個在某種解釋下給定原子的值，我們可以用一個真真值表值表(truth table)(truth table)來計算在同樣解釋下的任何合式公來計算在同樣解釋下的任何合式公式的值。這個真值表建立了命題聯(lián)結(jié)詞的語義式的值。這個真值表建立了命題聯(lián)結(jié)詞的語義( (意義意義) )。設(shè)設(shè)1 1

24、和和2 2是合式公式，那么真值表規(guī)則就是：是合式公式，那么真值表規(guī)則就是： 假如假如1 1 為真并且為真并且2 2也為真，那么也為真，那么(1 12 2) )就為真；否則，它就為假。就為真；否則，它就為假。 假如假如1 1 為真或者為真或者2 2為真，或兩者都為真，為真，或兩者都為真，那么那么(1 12 2) )就為真；否則，它就為假。就為真；否則，它就為假。 假如假如1 1 為假，那么為假，那么1 1 就為真；否則，就為真；否則，它就為假。它就為假。 的語義是以的語義是以和和來定義的。具體地說，來定義的。具體地說，(1 1 2 2) )是是( (1 12 2) )的替換形式和等價形式。的替換

25、形式和等價形式。 語義語義 命命題題真真值值表表 例：假設(shè)例：假設(shè)P P為假，為假， Q Q為假，為假， R R為真。為真。 ？PRQP)( 假如一個假如一個agentagent使用使用n n種特征種特征( (與命題相對應(yīng)與命題相對應(yīng)) )來描述它來描述它的世界，并且這些特征是用一個相應(yīng)的的世界，并且這些特征是用一個相應(yīng)的n n個原子的集合表個原子的集合表述在這個述在這個agentagent世界模型中，那么它的世界就會有世界模型中，那么它的世界就會有2 2n n種不種不同的情形同的情形只要這個只要這個agentagent能辨別，因為能辨別，因為n n個原子都可以個原子都可以有真值或假值，故存在

26、著有真值或假值，故存在著2 2n n種不同的情形。這個世界所能種不同的情形。這個世界所能有的每一種情形都對應(yīng)于一個解釋。給定有的每一種情形都對應(yīng)于一個解釋。給定n n個原子的值個原子的值( (解解釋釋) )，那么這個，那么這個agentagent就可以用真值表找到任何合式公式的就可以用真值表找到任何合式公式的值。值。相反的過程又是怎樣的呢相反的過程又是怎樣的呢? ? 語義語義 可滿足性與模型可滿足性與模型 一個合式公式在一種解釋下被指派為真值，那么這一個合式公式在一種解釋下被指派為真值，那么這種解釋滿足這個合式公式。一種滿足一個合式公式的解種解釋滿足這個合式公式。一種滿足一個合式公式的解釋被稱

27、為這個釋被稱為這個合式公式的一個模型合式公式的一個模型。一種解釋滿足在一。一種解釋滿足在一個合式公式集合中的每一個合式公式被稱為這個個合式公式集合中的每一個合式公式被稱為這個合式公合式公式集合的模型式集合的模型。因為一種解釋給每一個原子指派一個值，。因為一種解釋給每一個原子指派一個值，所以我們可以判定一種解釋是否滿足任何一個原子。我所以我們可以判定一種解釋是否滿足任何一個原子。我們可以用真值表來判定一種解釋是否滿足一個包含原子們可以用真值表來判定一種解釋是否滿足一個包含原子的合式公式。的合式公式。 假如合式公式如我們所期望的那樣值為真，那么我假如合式公式如我們所期望的那樣值為真，那么我們必須排

28、除所有這樣的解釋，在這些解釋中們必須排除所有這樣的解釋，在這些解釋中BAT_OKBAT_OK和和LIFTABLELIFTABLE為真，而為真，而MOVESMOVES為假。每個為假。每個“約束合式公式約束合式公式”都告訴我們一些有關(guān)這個世界可能的情形，并且排除一都告訴我們一些有關(guān)這個世界可能的情形，并且排除一些可能的模型些可能的模型( (每個模型都與這個世界的一種可能情形每個模型都與這個世界的一種可能情形相對應(yīng)相對應(yīng)) )。一般說來，描述這個世界的合式公式越多，一般說來，描述這個世界的合式公式越多，模型就越少模型就越少! ! 語義語義 可能沒有任何解釋可以滿足一個合式公式可能沒有任何解釋可以滿足

29、一個合式公式( (或或一個合式公式的集合一個合式公式的集合) )，在這種情況下，這個合式，在這種情況下，這個合式公式公式( (或合式公式的集合或合式公式的集合) )被說成是被說成是不一致的不一致的(inconsistent)(inconsistent)或或不可滿足的不可滿足的(unsatisfiable)(unsatisfiable)。 不可滿足的合式公式的例子如不可滿足的合式公式的例子如F F和和PPP (P (沒沒有一種解釋可以使這些合式公式為真有一種解釋可以使這些合式公式為真) )。 一個不可滿足的合式公式集合的例子是一個不可滿足的合式公式集合的例子是P P Q Q， P P Q Q，

30、P QP Q， P P Q(Q(用真用真值表可證實沒有一種解釋可以使所有這些合式公值表可證實沒有一種解釋可以使所有這些合式公式為真式為真) )。 可可滿滿足足性性與與模模型型 語義語義 永永真真性性 假如一個合式公式在它的組成原子的所有解釋下都假如一個合式公式在它的組成原子的所有解釋下都為真，那么它是永真的為真，那么它是永真的( (因而，因而，一個永真的合式公式是空一個永真的合式公式是空的的，它沒有告訴我們?nèi)魏斡嘘P(guān)這個世界可以是怎樣的情，它沒有告訴我們?nèi)魏斡嘘P(guān)這個世界可以是怎樣的情形形) )。下面是一些永真的合式公式的例子：。下面是一些永真的合式公式的例子： P P P ( P (這與這與PP

31、PP相同相同) ) T T (P (P P)P) Q T Q T ( P ( P Q ) Q ) P P P P P P ( Q ( Q P ) P ) 用真值表來確定一個合式公式的永真性要化費大量用真值表來確定一個合式公式的永真性要化費大量的時間，因為這個合式公式必須要針對所有原子值的組的時間，因為這個合式公式必須要針對所有原子值的組合來計算。合來計算。 語義語義 等價等價 當(dāng)且僅當(dāng)兩個合式公式的真假值在所有的解釋當(dāng)且僅當(dāng)兩個合式公式的真假值在所有的解釋中都是相同的，那么我們可以說它們是中都是相同的，那么我們可以說它們是等價的等價的。用。用符號符號“”表示等價。可以用真值表來驗證下面的表示等

32、價?？梢杂谜嬷当韥眚炞C下面的等價：等價： 德德. .摩根定律：摩根定律： 換質(zhì)換位定律：換質(zhì)換位定律： 假如假如1 1和和2 2是等價的，那么下面的公式是是等價的，那么下面的公式是永真的：永真的： 由于這個事實，由于這個事實，1 12 2這個標(biāo)記常常被用作這個標(biāo)記常常被用作為為(1 1 2 2) () (2 2 1 1) )的縮寫。的縮寫。 2 21 12 21 1) )( ( 2 21 12 21 1) )( ( ) )( () )( (1 12 22 21 1 )()(1221 語義語義 涵蘊涵蘊 如果在集合如果在集合中，每一個合式公式都為真的所有中，每一個合式公式都為真的所有解釋下合式公

33、式解釋下合式公式值為真值為真，那么我們說，那么我們說邏輯涵蘊邏輯涵蘊(logically entail)(logically entail) ，并且，并且從從中中邏輯地派生邏輯地派生(logical follow)(logical follow)， 是是的一個的一個邏輯推論邏輯推論(logical (logical consequence)consequence)。用符號。用符號 來指稱邏輯涵蘊來指稱邏輯涵蘊，并且寫為，并且寫為。下面是一些例子。下面是一些例子。 P P P P P P，P P Q Q Q Q F F ( (是任何合式公式是任何合式公式!)!) PQ PQ P P在最后的兩個例

34、子中，把標(biāo)記稍微作了簡縮。在最后的兩個例子中，把標(biāo)記稍微作了簡縮。當(dāng)當(dāng)為為單個時，常常這么做單個時，常常這么做。 語義語義 邏輯涵蘊在人工智能中是很重要的，因為它提供了邏輯涵蘊在人工智能中是很重要的，因為它提供了一種強(qiáng)有力的方法來說明一種強(qiáng)有力的方法來說明: : 如果有關(guān)一個世界的命題是如果有關(guān)一個世界的命題是真的，那么另一些所關(guān)注的命題真的，那么另一些所關(guān)注的命題( (也許是不能被感覺到的也許是不能被感覺到的) )也必須是真的。也必須是真的。 例如，假設(shè)我們感覺一些特征，把它們與公式例如，假設(shè)我們感覺一些特征，把它們與公式BAT_OKBAT_OK和和MOVESMOVES相聯(lián)系，并且用公式相聯(lián)

35、系，并且用公式BAT_OK BAT_OK LIFTABLE LIFTABLE MOVESMOVES來表述有關(guān)這個世界的知識。就是說，來表述有關(guān)這個世界的知識。就是說，我們有三個公式，其中兩個描述一個特定的世界的情景，我們有三個公式，其中兩個描述一個特定的世界的情景，其中另一個描述有關(guān)這個世界的一般知識。其中另一個描述有關(guān)這個世界的一般知識。 根據(jù)真值表知道根據(jù)真值表知道LIFTABLELIFTABLE由這三個公式邏輯涵蘊。由這三個公式邏輯涵蘊。既然根據(jù)這種涵蘊，既然根據(jù)這種涵蘊，LIFTABLELIFTABLE在所有這三個公式都為在所有這三個公式都為真的解釋中為真，那么它在我們預(yù)期的解釋真的解

36、釋中為真，那么它在我們預(yù)期的解釋(intended (intended interpretation)(interpretation)(即我們把它與機(jī)器人世界相聯(lián)系的即我們把它與機(jī)器人世界相聯(lián)系的) )中中一定為真。所以，這個作為我們預(yù)期的解釋的一部分命一定為真。所以，這個作為我們預(yù)期的解釋的一部分命題，即題，即“積木是不可舉的積木是不可舉的”必須是真的必須是真的! ! 涵涵蘊蘊 語義語義 涵涵蘊蘊 因為涵蘊對于決定有關(guān)這個世界的命題是真還因為涵蘊對于決定有關(guān)這個世界的命題是真還是假是一個強(qiáng)勁的工具，所以對我們來說，研究怎是假是一個強(qiáng)勁的工具，所以對我們來說，研究怎樣把信息表述為合式公式，并且

37、怎樣有效地產(chǎn)生出樣把信息表述為合式公式，并且怎樣有效地產(chǎn)生出涵蘊的合式公式是至關(guān)重要的。涵蘊的合式公式是至關(guān)重要的。 可以總用真值表來做這件事，但是我們要尋求可以總用真值表來做這件事，但是我們要尋求更簡便的方法。一個富有吸引力的可以替代涵蘊的更簡便的方法。一個富有吸引力的可以替代涵蘊的是是推理推理(inference)(inference)。雖然它們是根本不同的概念，。雖然它們是根本不同的概念，但是它們可以由但是它們可以由合理性合理性(soundness)(soundness)和和完備性完備性(completeness)(completeness)的概念聯(lián)結(jié)起來。的概念聯(lián)結(jié)起來。 語義語義 合

38、理性和完備性合理性和完備性 把推理與涵蘊聯(lián)系起來有兩個重要的定義：把推理與涵蘊聯(lián)系起來有兩個重要的定義： 1)1)假如對任意合式公式的集合假如對任意合式公式的集合和合式公式和合式公式，R R 蘊含著蘊含著 ，那么我們說推理規(guī)則集合，那么我們說推理規(guī)則集合R R是是合理的合理的(sound)(sound)。 2)2)假如對任意合式公式的集合假如對任意合式公式的集合和合式公式和合式公式，當(dāng)有當(dāng)有 時，存在用推理規(guī)則集合時，存在用推理規(guī)則集合R R從從推出推出的驗證（的驗證（ R R ），那么就說），那么就說R R是是完備的完備的(complete)(complete)。 當(dāng)推理規(guī)則是合理和完備的時

39、候，可以通過尋找一當(dāng)推理規(guī)則是合理和完備的時候，可以通過尋找一個驗證而不是用真值表來確定一個合式公式是否由一個個驗證而不是用真值表來確定一個合式公式是否由一個合式公式的集合導(dǎo)出。合式公式的集合導(dǎo)出。 當(dāng)推理規(guī)則合理時，假如找到了一個當(dāng)推理規(guī)則合理時，假如找到了一個從從導(dǎo)出的導(dǎo)出的驗證，那么我們知道驗證，那么我們知道是從是從邏輯地導(dǎo)出的。邏輯地導(dǎo)出的。 當(dāng)推理規(guī)則完備時，我們知道最終能夠通過一個完當(dāng)推理規(guī)則完備時，我們知道最終能夠通過一個完備的搜索過程搜尋一個驗證來確定備的搜索過程搜尋一個驗證來確定從從導(dǎo)出導(dǎo)出( (當(dāng)它如此當(dāng)它如此做的時候做的時候) )。 不管是在命題演算還是在謂詞演算不管是在

40、命題演算還是在謂詞演算( (將在后面研究將在后面研究) )中，用驗證的方法來替換真值表法通常節(jié)省了巨大的計中，用驗證的方法來替換真值表法通常節(jié)省了巨大的計算量。算量。 語義語義 合合理理性性和和完完備備性性 命題可滿足性問題命題可滿足性問題 為一個公式找一個模型的問題是一個命題為一個公式找一個模型的問題是一個命題可滿足性可滿足性問題問題(propositional satisfiability , PSAT)(propositional satisfiability , PSAT)。 在下一章中要說明任何公式可以被寫為一些文字析在下一章中要說明任何公式可以被寫為一些文字析取的合取。一些文字的析取被稱為一個子句，一個寫成取的合取。一些文字的析取被稱為一個子句，一個寫成子句合取的公式叫做子句合取的公式叫做合取范式合取范式(conjuncti