人工智能課件2邏輯

1

第6章人工智能邏輯1第6章人工智能邏輯2第6章人工智能邏輯

6.1命題邏輯與謂詞邏輯

6.2

謂詞公式及其邏輯表達(dá)式

6.3

謂詞邏輯的演算律

6.4“非二值”邏輯

6.5

模糊邏輯2第6章人工智能邏輯6.1命題邏輯36.1命題邏輯與謂詞邏輯什么是邏輯？簡單地說，邏輯就是人們用以處理問題而抽象的一種思維規(guī)則或計(jì)算方法。本章主要對人工智能常用的謂詞邏輯以及非二值邏輯進(jìn)行了討論，扼要介紹了目前智能領(lǐng)域發(fā)展引用的多種邏輯。36.1命題邏輯與謂詞邏輯什么是邏輯？簡單地說，邏輯46.1.1命題邏輯命題邏輯的關(guān)系表達(dá)直觀、生動(dòng)而簡潔，它是謂詞邏輯得以發(fā)展的前導(dǎo)和基礎(chǔ)。把命題邏輯加以簡單的形式化，就能擴(kuò)展應(yīng)用于謂詞邏輯推理中。1.命題和個(gè)體

設(shè)有如下符號命名的語句：

①X：愛因斯坦是一位偉人。②Y：海水是甜的。③W：3+4=9上述X、Y、Z都是陳述性語句，分別具有肯定(True)或否定(False)意義的真值，我們把它們都稱之為命題。其中，諸如“愛因斯坦”，“海水”，數(shù)字“3”、“4”等，它們是命題中的行為中心對象，又稱為個(gè)體。

46.1.1命題邏輯命題邏輯的關(guān)系表達(dá)直觀、生動(dòng)而簡潔56.1.1命題邏輯

定義6.1

命題(Proposition)，即具有真(T)假(F)意義的陳述性語句。注意：

⑴命題一定是陳述性語句；如上述X、Y、W等。例如，下面句子是陳述性語句嗎？①請勿吸煙。②昨晚你看足球聯(lián)賽了嗎？③西湖好美呵?、泼}既可用自然語言(包括中、外文)形式表示，也可用大寫的英文字符或字符串來命名。⑶命題反映了人腦進(jìn)行思維的一種判斷，可見命題表達(dá)自身就含有智能特性。56.1.1命題邏輯定義6.1命題(Propos66.1.1命題邏輯（1）個(gè)體是命題中的中心對象，通常由名詞構(gòu)成。個(gè)體可以是具體的人物、物體、一組數(shù)字、地名等，也可以是某個(gè)抽象的概念。例如，機(jī)器人、海棠花、理想、快樂、智能等均可作為個(gè)體。（2）個(gè)體的取值范圍稱為個(gè)體域。個(gè)體域可以是有限的，也可以是無限的。

定義6.2

所謂個(gè)體，是指可以獨(dú)立存在的某個(gè)事物。

66.1.1命題邏輯（1）個(gè)體是命題中的中心對象，通常76.1.1命題邏輯6.謂詞及變元

為了對許多具有進(jìn)步影響人物都使用形同X命題方式贊揚(yáng)之，可使用一種類同數(shù)學(xué)函數(shù)的形式語言——用含有變量字符或字符串的謂詞來定義：表達(dá)為英文字符串形式：

GIANT(x).其被賦予的漢語解釋是：

x是一位偉人。把GIANT(x)稱為謂詞（Predicate），其中GIANT()是謂詞名；括號中的參量x叫做謂詞的變元，又稱之為項(xiàng)。GIANT(?)

謂詞名謂詞變元76.1.1命題邏輯6.謂詞及變元為了86.1.1命題邏輯6.謂詞及變元

這種由定義的謂詞名、變元，共同構(gòu)成了具有陳述性表達(dá)的形式化語句，稱為謂詞。一個(gè)謂詞可以有n（其中n=0,1,2,……）個(gè)變元，并稱之為n元謂詞。在謂詞中，謂詞名表達(dá)了語句中除主語個(gè)體之外的其余部分，常采用自然語言的謂語動(dòng)作詞根來表達(dá)；謂詞的變元可在相應(yīng)個(gè)體域集合中取值任意一個(gè)元素。GIANT(?)

謂詞名謂詞變元86.1.1命題邏輯6.謂詞及變元這種96.1.1命題邏輯6.謂詞及變元例2-1假如定義英文字符串“OCITY(x)

”

設(shè)其含意為：x是一座歷史名城。

解：這里x可以取值“西安”——

真值為T；x取值“深圳”真值為F。若取值“北京”則為T、“華盛頓”——T、“野玫瑰”——F、“機(jī)器人”為F等。由上例可見，當(dāng)使用特定的個(gè)體常量取代了謂詞中的變元，該謂詞就轉(zhuǎn)換成為一個(gè)命題；反之，如果把命題中有獨(dú)立結(jié)構(gòu)的個(gè)體常量替換成變元參量，則又可把命題轉(zhuǎn)換成為一個(gè)具有謂詞結(jié)構(gòu)的表達(dá)式了。96.1.1命題邏輯6.謂詞及變元例2-1假106.1.1命題邏輯3.謂詞的元和謂詞的階

下面先給出關(guān)于謂詞的元的定義，然后再舉例對定義加以解釋和說明。定義6.3

謂詞中包含個(gè)體或變元的數(shù)目，稱為謂詞的元或謂詞的目。例2-2比較下列謂詞或謂詞形式的命題：①LIKE(john，mary)；②ROBOT(john)；③ROBOT(mary)；

④ADDQ(x，y，z)。試解釋具體含義，并指出它們各是幾元謂詞。解：上述謂詞①②③意即“機(jī)器人約翰喜歡瑪麗”；②和③都只有一個(gè)個(gè)體，稱為一元謂詞；相應(yīng)①則稱為二元謂詞；④表示為表達(dá)式“x+y=z”，其中包含有3個(gè)變元，故稱為三元謂詞。依此類推，可推出關(guān)于n元謂詞的概念。

順便指出：在多元謂詞中，變元的排序很重要，一旦確定，就不可隨意交換。

106.1.1命題邏輯3.謂詞的元和謂詞的階下116.1.1命題邏輯3.謂詞的元和謂詞的階

定義6.4

謂詞表達(dá)形式中所包容相疊加的含義層次數(shù)數(shù)目，稱為謂詞的階。例2-3為了說明謂詞的階，我們來比較下列謂詞形式的命題：①LIFELESS(outer-stars)；外星球沒有智能生命。②INCORRECT(lifeless(outer-stars))；說“外星球沒有智能生命”是不確切的。解：在上述謂詞形式的命題中，謂詞①只有一層含義，稱為一階謂詞；謂詞②在前一層含義基礎(chǔ)上，又增加了一層新意，共有二層含義。故把謂詞②稱為二階謂詞。依此類推，可推出關(guān)于n階謂詞的概念。注意：在謂詞邏輯演算中，最重要的有三大類：即：命題邏輯演算、一階謂詞邏輯演算和二階謂詞演算。116.1.1命題邏輯3.謂詞的元和謂詞的階定126.1.1命題邏輯4.命題與謂詞邏輯的關(guān)系命題邏輯表示比較簡單，只能表達(dá)具體固定的情況，命題是謂詞邏輯特殊事例的生動(dòng)描述，謂詞邏輯可以靈活表現(xiàn)多種或變化的情況；謂詞表達(dá)是命題邏輯的抽象與推廣?？偟目磥?，命題和謂詞的知識表示形式可以相互轉(zhuǎn)換，而謂詞比命題有更強(qiáng)的表達(dá)能力。顯而易見，謂詞是一種描述個(gè)體群之間的相互關(guān)系、性質(zhì)及其邏輯結(jié)構(gòu)的數(shù)學(xué)表示。人們把采用這種表示的運(yùn)算，又稱為謂詞邏輯。比較起來：命題邏輯演算太簡單，只能解決具體容易的問題；二階謂詞演算又太復(fù)雜，以至迄今為止，尚未找到最根本有效的算法。

因此，在人工智能中，目前使用最多的還是一階謂詞邏輯演算。126.1.1命題邏輯4.命題與謂詞邏輯的關(guān)系136.1.2命題和謂詞邏輯基礎(chǔ)命題或謂詞邏輯推理演算，主要可利用連接詞和量詞，把單個(gè)的謂詞組合成為謂詞公式來完成?；诿}和謂詞邏輯可相互轉(zhuǎn)換的特性，這里約定：在后繼學(xué)習(xí)中，對命題和謂詞邏輯的相關(guān)公式表達(dá)、相關(guān)定理、定律的論證和推導(dǎo)等，不再加以嚴(yán)格區(qū)別。136.1.2命題和謂詞邏輯基礎(chǔ)命題或謂詞邏輯推理演算，主146.1.2命題和謂詞邏輯基礎(chǔ)1.連接詞(Connectives)

所引入的連接詞共有五個(gè)。

⑴符號“?”稱為“否定”(Negation)或補(bǔ)，表示“非”的連接關(guān)系。即當(dāng)命題P為真時(shí)，則?P為假；反之，當(dāng)命題P為假，則?P為真。⑵符號“∧”稱為“合取”(Conjunction)，表示“與”(AND)或“同時(shí)”的關(guān)系。例如，P∧Q，讀作“P與Q”。⑶符號“∨”稱為“析取”(Disjunction)，它表示“或”(OR)的連接關(guān)系。例如，P∨Q，讀作“P或Q”。146.1.2命題和謂詞邏輯基礎(chǔ)1.連156.1.2命題和謂詞邏輯基礎(chǔ)1.連接詞(Connectives)

⑷符號“→”稱為“條件”(Conditional)或者“蘊(yùn)涵”(Implication)，它表示“如果……，則……”的定義關(guān)系。例如，在P→Q的表達(dá)式中，表示了“如果P，則Q”的條件推導(dǎo)關(guān)系。這里，又稱P為前件，稱Q后件。P表示了條件的前提；Q表示了邏輯結(jié)論。應(yīng)該強(qiáng)調(diào)指出，條件表達(dá)式有一個(gè)重要特性：當(dāng)前件P=F時(shí)，無論后件Q為何值(T或者F)，條件式P→Q真值總是為T；當(dāng)前件P=T時(shí)，條件式P→Q的真值總是與后件Q真值相同。⑸符號“”稱為“雙條件”(Biconditional)或者等價(jià)(Equivalence)連接關(guān)系。例如，表達(dá)式PQ，讀作“P當(dāng)且僅當(dāng)Q”。或者說它表示的含義為：P為真，當(dāng)且僅當(dāng)Q為真。156.1.2命題和謂詞邏輯基礎(chǔ)166.1.2命題和謂詞邏輯基礎(chǔ)1.連接詞(Connectives)

PQ?P

P∨Q

P∧Q

P→Q

PQ

FF

TF

F

T

T

FT

T

T

F

T?

FTF

F

T

F

FF

TT

F

T

T

T

T表2-1連接詞定義真值表

166.1.2命題和謂詞邏輯基礎(chǔ)176.1.2命題和謂詞邏輯基礎(chǔ)2.量詞(Quantifiers)

量詞，表示了個(gè)體與個(gè)體域之間的包含關(guān)系。

⑴全稱量詞(UniversalQuantifier)：用字符“x”表達(dá)，表示了該量詞作用的轄域?yàn)閭€(gè)體域中“所有的個(gè)體x”或“每一個(gè)體x都”要遵從所約定的謂詞關(guān)系。例2-4(x)(現(xiàn)代理工科大學(xué)生(x)→學(xué)習(xí)計(jì)算機(jī)應(yīng)用基礎(chǔ)(x))；解：該謂詞邏輯表達(dá)的含義是：“所有現(xiàn)代理工科的大學(xué)生x，都必須學(xué)習(xí)計(jì)算機(jī)應(yīng)用基礎(chǔ)課程”。

176.1.2命題和謂詞邏輯基礎(chǔ)2.量詞(Q186.1.2命題和謂詞邏輯基礎(chǔ)2.量詞(Quantifiers)⑵存在量詞(ExistentialQuantifier)：用字符“彐x”表達(dá)，表示了該量詞要求“存在于個(gè)體域中的某些個(gè)體x”或“某個(gè)個(gè)體x”，要服從所約定的謂詞關(guān)系。例2-5，(x)(彐y)(CLASSMATE(x,y)∧COLLEGEOFCOMPUTER(x)；解：該謂詞邏輯表達(dá)的意思是：在所有的計(jì)算機(jī)學(xué)院學(xué)生中，相對于每一位同學(xué)x，必然存在一個(gè)個(gè)體y，y同學(xué)與x滿足同班同學(xué)的關(guān)系。186.1.2命題和謂詞邏輯基礎(chǔ)2.量詞(196.1.3命題和謂詞邏輯舉例3.命題公式及其描述舉例：⑴小張既聰明，又勤奮，所以他的學(xué)習(xí)成績一直很好。P：小張聰明Q：小張勤奮R：小張學(xué)習(xí)成績一直很好得到：（P∧Q）→R196.1.3命題和謂詞邏輯舉例3.206.1.3命題和謂詞邏輯舉例⑵小王總是在圖書館看書，除非他病了或圖書館不開門。P：小王病了Q：圖書館開門R：小王在圖書館看書得到：?

（P∨?

Q）

R3.命題公式及其描述舉例：206.1.3命題和謂詞邏輯舉例⑵小王總是在圖書館看書，除216.1.3命題和謂詞邏輯舉例（1）若x是小張的父親，且y是小張的兄弟，則x也是y的父親。解：先設(shè)定謂詞，再設(shè)定變元，并將變元代之以常量，用連接詞運(yùn)算符連接并加以描述：設(shè)定謂詞：FATHER(x,y)：x是y的父親

BROTHER(y,w)：y是w的兄弟

常量：mz表示小張則可描述為：FATHER(x,mz)∧BROTHER(y,mz)→FATHER(x,y)4.謂詞公式及其描述舉例：216.1.3命題和謂詞邏輯舉例（1）若x是小張的父親，且226.1.3命題和謂詞邏輯舉例（2）*在那遙遠(yuǎn)的地方，有位好姑娘，人們走過她的身旁，都要回頭留戀地張望。解：(彐x){好姑娘(x)∧居住的地方(z，x)∧遙遠(yuǎn)的(z)∧(y)[人(y)∧行走經(jīng)過(y,z)→回頭留戀地張望(y)]}4.謂詞公式及其描述舉例：226.1.3命題和謂詞邏輯舉例（2）*在那遙遠(yuǎn)的地方，有6.2謂詞公式及其邏輯表達(dá)式6.2.1謂詞公式概念復(fù)習(xí)與擴(kuò)充：使用連接詞和量詞，把若干謂詞連接組合在一起，就得到了謂詞邏輯公式(PLF：PredicateLogicFormula)的表達(dá)。下面我們給出謂詞公式的相關(guān)各種概念與定義。定義6.5

僅能表達(dá)單一意義且不可再細(xì)劃分的簡單命題稱為原子命題。例如，一階零元(目)命題、一階一元命題、一階二元命題等都是原子命題。定義6.6用連接詞或者量詞把若干原子命題聯(lián)結(jié)組合在一起，就得到了命題公式(PF：PropositionFormula)，又稱之為命題合式公式。定義6.7采用參量變元來替代命題合式公式中的常量，就得到了原子謂詞公式，用連接詞或者量詞把若干原子謂詞聯(lián)結(jié)組合在一起，就得到了謂詞公式,又稱之為謂詞合式公式（PWFF：PredicateWell-FormedFormula），簡稱合式公式或WFF。

6.2謂詞公式及其邏輯表達(dá)式6.2.1謂詞公式概24

6.2.2謂詞公式概念

綜上所述，我們可以給出下述關(guān)于謂詞合式公式及其生成規(guī)則的定理。定理6.1

謂詞合式公式可依照下述遞歸(Recursion)過程得到：①原子公式是謂詞合式公式；②若A是謂詞合式公式，x是A中的任一個(gè)變元，則?A,(x)A和(彐x)A也都是合式公式；③若A、B都是謂詞合式公式，則?A,?B,A∧B,A∨B,A→B,AB也都是合式公式；④若有限次使用上述各步生成的公式，仍是合式公式。246.2.2謂詞公式概念綜上所述，25

6.2.2謂詞公式概念

注意：為了使合式公式WFF在連接和運(yùn)算中表達(dá)簡潔一致，對WFF還有如下規(guī)定：⑴WFF最外層括號可以省略；⑵括號內(nèi)連接符運(yùn)算優(yōu)先，連接符運(yùn)算優(yōu)先次序?yàn)?∧∨→；⑶同級連接符的運(yùn)算按照排列順序進(jìn)行。256.2.2謂詞公式概念26

6.2.2謂詞公式的解釋

謂詞公式的解釋：首先以個(gè)體域中任意常量來替換謂詞公式中的變元，使謂詞公式轉(zhuǎn)換為一組確定的命題公式；隨后賦予各命題邏輯以真值，就得到了對應(yīng)于該謂詞公式的某個(gè)含義的解釋。

由于存在多種組合情況，則一個(gè)謂詞公式可有許多個(gè)解釋。

266.2.2謂詞公式的解釋謂詞27定義：設(shè)D是謂詞公式P的非空個(gè)體域，若對P中的個(gè)體常量、函數(shù)和謂詞按如下規(guī)定賦值：

（1）為每個(gè)個(gè)體常量指派D中的一個(gè)元素；（2）為每個(gè)n元函數(shù)指派一個(gè)從Dn到D的一個(gè)映射，其中

Dn∈{(x1,x2,……xn)|x1,x2,……,xn∈D}

（3）為每個(gè)n元謂詞指派一個(gè)從Dn到{T,F}的映射則稱這些指派為P在D上的一個(gè)解釋。若某個(gè)解釋I使謂詞公式為真(T)，則稱I是該公式的一個(gè)正模型，簡稱模型；反之，若某個(gè)解釋I，使謂詞公式為假(F)，則稱I是該公式的一個(gè)反模型。27定義：設(shè)D是謂詞公式P的非空個(gè)體域，若對P中的個(gè)體常量、28例：設(shè)個(gè)體域D={1,2}，求公式A=(x)(彐y)P(x,y)在D上的解釋，并指出在每一種解釋下公式A的真值。解:由于公式A中沒有包含個(gè)體常量和函數(shù)，因此可以直接為謂詞指派真值，設(shè)有:

這就是公式A在D上的一個(gè)解釋。從這個(gè)解釋可以看出：當(dāng)x=1、y=1時(shí)，有P(x,y)的真值為T；當(dāng)x=2，y=1時(shí)，有P(x,y)的真值為T；即對x在D上的任意取值，都存在y=1使P(x,y)的真值為T。因此，在此解釋下公式A的真值為T。

P(1,1)P(1,2)P(2,1)P(2,2)TFTF28例：設(shè)個(gè)體域D={1,2}，求公式A=(x)(彐y29需要注意，一個(gè)謂詞公式在其個(gè)體域上的解釋不是唯一的。例如，對公式A，若給出另一組真值指派

這也是公式A在D上的一個(gè)解釋。從這個(gè)解釋可以看出：當(dāng)x=1、y=1時(shí)，有P(x,y)的真值為T；當(dāng)x=2、y=1時(shí)，有p(x,y)的真值為F；同樣當(dāng)x=1、y=2時(shí)，有P(x,y)的真值為T；當(dāng)x=2、y=2時(shí)，有P(x,y)的真值為F；即對x在D上的任意取值，不存在一個(gè)y使得P(x,y)的真值為T。因此，在此解釋下公式A的真值為F。實(shí)際上，A在D上共有16種解釋，這里就不再—一列舉。P(1,1)P(1,2)P(2,1)P(2,2)TTFF29需要注意，一個(gè)謂詞公式在其個(gè)體域上的解釋不是唯一的。例如30例：設(shè)個(gè)體域D=｛1，2｝，求公式B=（x）P（f（x），a）在D上的解釋，并指出在該解釋下公式B的真值。

解：設(shè)對個(gè)體常量a和函數(shù)f（x）的真值指派為：

對謂詞的真值指派為：

這里，由于已知指派a=1，所以P（1，2）和P（2，2）不可能出現(xiàn)，故沒有給它們指派真值。

上述指派是公式B在D上的一個(gè)解釋。在此解釋下有

當(dāng)x=1時(shí)，a=1使P（1，1）=T

當(dāng)x=2時(shí)，a=1使P（2，1）=T

即對x在D上的任意取值，都有P（f(x)，a）的真值為T。因此，在此解釋下公式B的真值為T。af(1)f(2)112P(1,1)P(1,2)P(2,1)P(2,2)T×T×

由上面的例子可以看出，謂詞公式的真值都是針對某一個(gè)解釋而言的，它可能在某一個(gè)解釋下真值為T，而在另一個(gè)解釋下為F。

30例：設(shè)個(gè)體域D=｛1，2｝，求公式B=（x）P（f（31

6.2.3

謂詞公式的永真性判定

人們?nèi)舭严胍瓿傻闹悄苋蝿?wù)表示為一個(gè)謂詞公式，從而把問題的求解轉(zhuǎn)化為求解該公式的真值問題：

如果某公式的真值總為T，則稱它是永真的；否則，就稱其為非永真或?yàn)榧?。這就是我們要討論的所謂永真性的問題。316.2.3謂詞公式的永真性判定32

6.2.3謂詞公式的永真性判定

下面使用謂詞公式的解釋概念，給出關(guān)于謂詞公式是否為永真的定義。

定義6.9

如果謂詞公式P對個(gè)體域D上的任何一個(gè)解釋都取得真值T，則稱P在D上是永真的；如果P在每個(gè)非空個(gè)體域上都是永真的，則稱P永真。定義6.10

對于謂詞公式P，若至少存在一個(gè)解釋，使得謂詞公式P在此解釋下的真值為T，則稱公式P是兼容的或可滿足的；反之，如果存在一個(gè)解釋集(Set)，使得謂詞公式P在其中的任何解釋下的真值都為F，則稱公式P對該解釋集是不兼容的或不可滿足的。326.2.3謂詞公式的永真性判定33

6.2.3

謂詞公式的永真性判定

根據(jù)上述定義，就能總結(jié)得出如下判斷謂詞公式是否為

永真的定理。定理6.2

如果謂詞合式公式WFF對于個(gè)體域中的任何一個(gè)解釋I都有

(I)WFF（I）=T成立，則該公式WFF是一個(gè)永真公式。類同上述，可否引入關(guān)于“永假的”、“非永真的”、“非永假的”概念與定義，并得出關(guān)于謂詞公式永真性問題的若干定理呢？

永假公式——定理6.3

如果謂詞合式公式WFF對于個(gè)體域中的任何一個(gè)解釋I都有

(I)WFF（I）=F成立，則該公式WFF是一個(gè)永假公式。336.2.3謂詞公式的永真性判定34

6.2.3

謂詞公式的永真性判定

非永真公式——定理6.4

如果謂詞合式公式WFF在個(gè)體域中存在解釋I，使得

(彐I)WFF（I）=F

成立，則該公式WFF是一個(gè)非永真公式；并且該解釋I是此公式的一個(gè)反模型。非永假公式——定理6.5

如果謂詞合式公式WFF在個(gè)體域中存在解釋I，使得

(彐I)WFF（I）=T成立，則該公式WFF是一個(gè)非永假公式；并且該解釋I是此公式的一個(gè)模型。由定義6.10可知，非永假公式可叫做是兼容的或可滿足的，而永假公式又稱為不可滿足的或不兼容的。

346.2.3謂詞公式的永真性判定356.3*謂詞邏輯的演算律

常用的謂詞邏輯演算律主要有兩大類：一類是邏輯等價(jià)律，另一類是邏輯蘊(yùn)涵律。下面分別加以介紹。

6.3.1

謂詞邏輯等價(jià)律

定義6.11

設(shè)P與Q是兩個(gè)謂詞公式，D是它們共同的個(gè)體域，若P與Q對于D上的任何一個(gè)解釋都有相同的真值，則稱公式P和Q在D上是邏輯等價(jià)的，記為P

Q

；如果D是任意個(gè)體域，則稱公式P和Q是邏輯等價(jià)的，記作PQ。356.3*謂詞邏輯的演算律常用的謂詞邏輯演36謂詞邏輯等價(jià)律(一)E1?

?PP雙重否定律E2P∧PP吸收律㈠（又稱等冪律）E3P∨PPE4P∧QQ∧P交換律

E5

P∨QQ∨PE6

(P∧Q)∧RP∧(Q∧R)結(jié)合律

E7

(P∨Q)∨RP∨(Q∨R)E8P∧(Q∨R)(P∧Q)∨(P∧R)分配律

E9P∨(Q∧R)(P∨Q)∧(P∨R)36謂詞邏輯等價(jià)律(一)E1??PP37謂詞邏輯等價(jià)律(二)E10P∧(P∨Q)P吸收律㈡E11P∨(P∧Q)PE12

?(P∧Q)?P∨?Q德·摩根定律E13

?(P∨Q)?P∧?QE14P→Q?P∨Q

蘊(yùn)涵化歸律E15PQ(P→Q)∧(Q→P)等價(jià)律E16P∧TP謂詞與真值演算律E17P∧FFE18P∨TTE19P∨FP37謂詞邏輯等價(jià)律(二)E10P∧(P∨Q)38謂詞邏輯等價(jià)律(三)E20P∧?PF補(bǔ)余律E21

P∨?PTE22P→(Q→R)P∧Q→R輸出律E23(P→Q)∧(P→?Q)?P

歸謬律E24P→Q?Q→?P

逆反律E25

(x)AA（A中不含x）E26

(x)AAE27(x)(P(x)∧Q(x))(x)P(x)∧(x)Q(x)量詞分配律E28(x)(P(x)∨Q(x))(x)P(x)∨(x)Q(x)E29

?(x)P(x)(x)?P(x)

量詞轉(zhuǎn)換律E30

?(x)P(x)(x)?P(x)38謂詞邏輯等價(jià)律(三)E20P∧?PF謂詞邏輯等價(jià)律(四)E31(x)P(x)∧A

(x)(P(x)∧A)

量詞轄域擴(kuò)張、收縮律E32(x)P(x)∨A

(x)(P(x)∨A)

（A中不含x）E33(x)P(x)∧A

(x)(P(x)∧A)

（A中不含x）E34

(x)P(x)∨A

(x)(P(x)∨A)（A中不含x）E35

(x)(y)P(x,y)

(y)(x)P(x,y)量詞交換律E36

(x)(

y)P(x,y)

(

y)(x)P(x,y)E37

(x)P(x)→A

(x)(P(x)→A)量詞轉(zhuǎn)換及擴(kuò)張、收縮律E38

(x)P(x)→A

(x)(P(x)→A)（A中不含x）E39A→(x)P(x)(x)(A→P(x))E40A→(x)P(x)

(x)(A→P(x))E41P∨﹁QRPQ∨R復(fù)合化歸律E42PQ∨RP∧QRE43P(QR)P∧QRE44(PQ)R(PR)∧(QR)(P∨R)∧(QR)謂詞邏輯等價(jià)律(四)E31(x)P(x)∧A(x406.3*謂詞邏輯的演算律6.3.2

謂詞邏輯蘊(yùn)涵律定義6.12

在謂詞公式P與Q中，若P→Q是永真的，則稱P永真蘊(yùn)涵Q；并稱P為前提，Q為P的邏輯結(jié)論，記作PQ。

406.3*謂詞邏輯的演算律6.341謂詞邏輯蘊(yùn)涵律I1PP∨Q；QP∨Q；QPQ附加律

I2P∧QP；

P∧QQ化簡律I3P，P→QQ假言推理I4(P→Q)∧?Q

?P

拒取式推理I5

?P

，P∨QQ析取三段論推理I6(P→Q)∧(Q→R)P→R假言三段論推理I7P→Q(Q→R)→(P→R)I8(P→Q)∧(R→S)

P∧R→Q∧SI9(PQ)∧(QS)

PRI10

P∨Q，P→Q，Q→RR二難推理I11

(x)P(x)P(y)

全稱固化律(y為個(gè)體域中的個(gè)體常量)I12

(x)P(x)P(y)

存在固化律41謂詞邏輯蘊(yùn)涵律I1PP∨Q；QP∨42

⑴P規(guī)則：在進(jìn)行推理的任何步驟上，都可以引入前提P。⑵T規(guī)則：在進(jìn)行推理時(shí)，若同時(shí)有一個(gè)或多個(gè)謂詞公式永真(T)蘊(yùn)含公式S，則可把S引入推理過程中。⑶CP規(guī)則：若從公式C和前提集合P能推出S來，則由P可推出：P→S。6.3.3幾條重要的推理規(guī)則42⑴P規(guī)則：在進(jìn)行推理的任何步驟上，都可以43⑷反證法規(guī)則：PQ，當(dāng)且僅當(dāng)P∧?QF。即要證明Q成為P的邏輯結(jié)論，其充要條件是后一式必須成立。由反證法規(guī)則推廣之，可得到如下定理：定理6.6Q為P1，P2，……，PN的邏輯結(jié)論，當(dāng)且僅當(dāng)（P1∧P2∧…∧PN∧?QF

順便指出，這是一條使用了反證法的定理，也是迄今實(shí)現(xiàn)機(jī)器定理證明一種較為可靠的傳統(tǒng)途徑。

6.3.3幾條重要的推理規(guī)則43⑷反證法規(guī)則：PQ，當(dāng)且僅當(dāng)P∧?QF。即446.4“非二值”邏輯

正如計(jì)算機(jī)中使用“0”和“1”兩個(gè)代碼來解釋世界一樣，人們在基于符號的命題與謂詞邏輯中，試圖只使用“F”和“T”二個(gè)真值來描述智能特性。因此，人們把這種邏輯描述，又常稱之為二值邏輯或標(biāo)準(zhǔn)邏輯。但是，發(fā)展中的世界，事物運(yùn)動(dòng)變化，氣象萬千，是否“非真即假”二值邏輯就能全部包容呢？事實(shí)上，在“T”和“F”兩極之間，世界萬物還有著無限精彩表現(xiàn)。例如，依據(jù)研究需要，還可以定義“三值”以及多值邏輯、隨機(jī)表達(dá)邏輯、時(shí)態(tài)邏輯、模態(tài)邏輯、模糊邏輯等。由于這些邏輯的特性往往都不是二值的，故統(tǒng)稱其為多值邏輯，或稱為“非二值”邏輯。

446.4“非二值”邏輯正如計(jì)算機(jī)中使用“0”和“1”456.4“非二值”邏輯6.4.1多值邏輯的演算定義T(P)來表示命題P為真的程度。則：即T(P)是某個(gè)介于0到1之間的任意實(shí)數(shù)，稱T(P)為命題P的真度。

按如下規(guī)則來進(jìn)行連接詞的邏輯運(yùn)算：

（1）（2）（3）（4）（5）

456.4“非二值”邏輯6.4.1多值邏輯的演算466.4.1多值邏輯的演算例如，對于，除了可用上面給出的定義計(jì)算外，還可以按下述某個(gè)定義的規(guī)則來計(jì)算其值：

466.4.1多值邏輯的演算476.4.1多值邏輯的演算計(jì)算還可以按下述某個(gè)定義的規(guī)則來計(jì)算其值：

……476.4.1多值邏輯的演算48

那么在實(shí)際應(yīng)用中應(yīng)選用哪種定義來計(jì)算T(P→Q)

呢？一般要具體情況具體分析對待，即選擇更貼切實(shí)際情況的那一種。應(yīng)該指出：上述關(guān)于連接詞運(yùn)算規(guī)則的定義，只是作為一種數(shù)理邏輯概念象征性的引入，并未深入加以嚴(yán)格證明。讀者在應(yīng)用中可以繼續(xù)延伸甚至發(fā)揮這種思想，從而提出新的或自己獨(dú)到的數(shù)學(xué)理念，以便進(jìn)行相關(guān)研究工作。

6.4.1多值邏輯的演算48那么在實(shí)際應(yīng)用中應(yīng)選用哪種定義來計(jì)算49

三值邏輯是多值邏輯的一種，顧名思義，即限定命題真值具有“真”、“假”、和介于“真”與“假之間共三個(gè)狀態(tài)值的邏輯。6.4.2三值邏輯及其布可閥（Bochvar）邏輯49三值邏輯是多值邏輯的一種，顧名思義，即限定PQ

?PP∨QP∧QP→QPQ001001100.510.5010.501110100.500.50.500.50.50.50.50.50.50.5110.510.510.510.5100100010.5010.50.50.51101111表2-4一種特定計(jì)算規(guī)則的三值邏輯真值表

PQ?PP∨QP∧QP→QP51

關(guān)于布可閥（Bochvar）邏輯，我們可以通過朗讀下面由四個(gè)命題構(gòu)成的一首小詩來說明：6.4.2三值邏輯及其布可閥（Bochvar）邏輯

這是一個(gè)黃昏的早晨。

我走在那寬敞的羊腸小道上。

溫暖的寒風(fēng)撲面。

樹陰中陽光燦爛。

51關(guān)于布可閥（Bochvar）邏輯，我們可以通52

例如，有人寫了以下一個(gè)隨意命題

X：這個(gè)命題是假的。請問，單就命題“X”自身的真值來判斷，其真值是“真”還是“假”呢？為什么？

可見，Bochvar邏輯常常表現(xiàn)出與某種矛盾狀態(tài)有關(guān)，有時(shí)人們稱之為語義悖論問題。

6.4.2三值邏輯及其布可閥（Bochvar）邏輯52例如，有人寫了以下一個(gè)隨意命題6.4.2三53

人們在智能活動(dòng)與研究中，除了廣泛地使用著諸如命題和謂詞等確定性邏輯之外，還常常使用一些非確定性、估計(jì)的或預(yù)測性的邏輯。例如，在科學(xué)研究與數(shù)據(jù)挖掘分析中，常常使用概率統(tǒng)計(jì)規(guī)律、關(guān)聯(lián)規(guī)則以及粗集(RoughSets)理論；在規(guī)劃管理中使用了運(yùn)籌學(xué)、Bayes決策以及證據(jù)理論；在日常推理和智能控制中使用了模糊邏輯等。事實(shí)上，非確定性是現(xiàn)實(shí)世界中事物發(fā)展的一種必然現(xiàn)象，反映了事物發(fā)展變化的一種不確定的客觀規(guī)律。因而研究各種非確定性、估計(jì)的或預(yù)測性的邏輯理論與方法也就顯得格外重要。

6.4.3一種非確定性邏輯——概率邏輯53人們在智能活動(dòng)與研究中，除了廣泛地使用著諸如命54

模糊邏輯(FuzzyLogic)理論首先由L.A.Zadeh于1965年提出，1978年繼而又提出了可能性理論。從而在世界上為人們更好地利用模糊知識，實(shí)施不確定性的智能推理，提供了一種重要的數(shù)學(xué)描述武器和可行的技術(shù)方法。6.5模糊邏輯54模糊邏輯(FuzzyLogic)理論首先由55模糊邏輯是一種常見的信息表達(dá)形式。例如，有人贊賞對面走過來的一位女孩：“姑娘好漂亮，真如花兒一樣?！边@里的“漂亮”、“如……一樣”就是一種達(dá)到某個(gè)境界或某種程度的模糊邏輯表達(dá)。6.5模糊邏輯6.5.1模糊性概念55模糊邏輯是一種常見的信息表達(dá)形式。例如，有人贊賞對面走過56

人們使用的自然語言中，諸如:“高”、“矮”、“胖”、“瘦”；“年青”、“年老”、“美麗”、“瀟灑”；“好”、“壞”；“抓緊”、“放松”、“差不多”、“幾乎”、“很”……等等。這些都不是精確數(shù)字測量或具體特定界限的表達(dá)，而是模糊邏輯特性的描述表示。6.5模糊邏輯56人們使用的自然語言中，諸如:6.5模糊邏輯57

模糊真值體現(xiàn)在討論的命題主體，在所描述的模糊集合的隸屬度上，其值取為[0，1]中的任意實(shí)數(shù)。6.5模糊邏輯6.5.2*模糊邏輯表達(dá)例：①小劉是個(gè)大個(gè)子。

②小張家離單位很遠(yuǎn)。

③小王總是那么樂觀。其中，“大個(gè)子”、“很遠(yuǎn)”、“總是那么樂觀”等都缺乏明確的邊界，屬于模糊謂詞。57模糊真值體現(xiàn)在討論的命題主體，在所描述的模糊集合的58事實(shí)上，人們可用一種數(shù)學(xué)“三元組”進(jìn)行事物的模糊表示，其數(shù)學(xué)表達(dá)形式為：（對象，屬性?屬性值?，程度）也可表示為：（對象，屬性，屬性值）6.5模糊邏輯6.5.2*模糊邏輯表達(dá)例:一個(gè)三元組的表達(dá)式為：（王五，體形，胖?0.8?).請問：這是什么意思？58事實(shí)上，人們可用一種數(shù)學(xué)“三元組”進(jìn)行事物的模糊表示，其59

事實(shí)上，一般只在工程應(yīng)用中才使用精確的測量數(shù)字表達(dá)。而在人類日常智能活動(dòng)中，精確的測量數(shù)字表達(dá)并不符合人的思維習(xí)慣，故基本上都以模糊性表達(dá)為主。但是在人工智能應(yīng)用領(lǐng)域，模糊性語言具有連續(xù)多值多義的特點(diǎn)，機(jī)器難于完成理解，也就很難直接在機(jī)器中進(jìn)行邏輯計(jì)算、知識判斷與識別。因此，探討和研究基于模糊數(shù)學(xué)理論的知識模糊表達(dá)與推理，其意義十分重大。雖然模糊理論發(fā)展至今才40年的時(shí)間，已經(jīng)取得許多長足的進(jìn)步與發(fā)展，仍然有許多新理論和新技術(shù)尚待學(xué)者們不斷挖掘和完善充實(shí)。6.5模糊邏輯6.5.3*關(guān)于模糊邏輯的討論59事實(shí)上，一般只在工程應(yīng)用中才使用精確的測量60

第6章人工智能邏輯1第6章人工智能邏輯61第6章人工智能邏輯

6.1命題邏輯與謂詞邏輯

6.2

謂詞公式及其邏輯表達(dá)式

6.3

謂詞邏輯的演算律

6.4“非二值”邏輯

6.5

模糊邏輯2第6章人工智能邏輯6.1命題邏輯626.1命題邏輯與謂詞邏輯什么是邏輯？簡單地說，邏輯就是人們用以處理問題而抽象的一種思維規(guī)則或計(jì)算方法。本章主要對人工智能常用的謂詞邏輯以及非二值邏輯進(jìn)行了討論，扼要介紹了目前智能領(lǐng)域發(fā)展引用的多種邏輯。36.1命題邏輯與謂詞邏輯什么是邏輯？簡單地說，邏輯636.1.1命題邏輯命題邏輯的關(guān)系表達(dá)直觀、生動(dòng)而簡潔，它是謂詞邏輯得以發(fā)展的前導(dǎo)和基礎(chǔ)。把命題邏輯加以簡單的形式化，就能擴(kuò)展應(yīng)用于謂詞邏輯推理中。1.命題和個(gè)體

設(shè)有如下符號命名的語句：

①X：愛因斯坦是一位偉人。②Y：海水是甜的。③W：3+4=9上述X、Y、Z都是陳述性語句，分別具有肯定(True)或否定(False)意義的真值，我們把它們都稱之為命題。其中，諸如“愛因斯坦”，“海水”，數(shù)字“3”、“4”等，它們是命題中的行為中心對象，又稱為個(gè)體。

46.1.1命題邏輯命題邏輯的關(guān)系表達(dá)直觀、生動(dòng)而簡潔646.1.1命題邏輯

定義6.1

命題(Proposition)，即具有真(T)假(F)意義的陳述性語句。注意：

⑴命題一定是陳述性語句；如上述X、Y、W等。例如，下面句子是陳述性語句嗎？①請勿吸煙。②昨晚你看足球聯(lián)賽了嗎？③西湖好美呵?、泼}既可用自然語言(包括中、外文)形式表示，也可用大寫的英文字符或字符串來命名。⑶命題反映了人腦進(jìn)行思維的一種判斷，可見命題表達(dá)自身就含有智能特性。56.1.1命題邏輯定義6.1命題(Propos656.1.1命題邏輯（1）個(gè)體是命題中的中心對象，通常由名詞構(gòu)成。個(gè)體可以是具體的人物、物體、一組數(shù)字、地名等，也可以是某個(gè)抽象的概念。例如，機(jī)器人、海棠花、理想、快樂、智能等均可作為個(gè)體。（2）個(gè)體的取值范圍稱為個(gè)體域。個(gè)體域可以是有限的，也可以是無限的。

定義6.2

所謂個(gè)體，是指可以獨(dú)立存在的某個(gè)事物。

66.1.1命題邏輯（1）個(gè)體是命題中的中心對象，通常666.1.1命題邏輯6.謂詞及變元

為了對許多具有進(jìn)步影響人物都使用形同X命題方式贊揚(yáng)之，可使用一種類同數(shù)學(xué)函數(shù)的形式語言——用含有變量字符或字符串的謂詞來定義：表達(dá)為英文字符串形式：

GIANT(x).其被賦予的漢語解釋是：

x是一位偉人。把GIANT(x)稱為謂詞（Predicate），其中GIANT()是謂詞名；括號中的參量x叫做謂詞的變元，又稱之為項(xiàng)。GIANT(?)

謂詞名謂詞變元76.1.1命題邏輯6.謂詞及變元為了676.1.1命題邏輯6.謂詞及變元

這種由定義的謂詞名、變元，共同構(gòu)成了具有陳述性表達(dá)的形式化語句，稱為謂詞。一個(gè)謂詞可以有n（其中n=0,1,2,……）個(gè)變元，并稱之為n元謂詞。在謂詞中，謂詞名表達(dá)了語句中除主語個(gè)體之外的其余部分，常采用自然語言的謂語動(dòng)作詞根來表達(dá)；謂詞的變元可在相應(yīng)個(gè)體域集合中取值任意一個(gè)元素。GIANT(?)

謂詞名謂詞變元86.1.1命題邏輯6.謂詞及變元這種686.1.1命題邏輯6.謂詞及變元例2-1假如定義英文字符串“OCITY(x)

”

設(shè)其含意為：x是一座歷史名城。

解：這里x可以取值“西安”——

真值為T；x取值“深圳”真值為F。若取值“北京”則為T、“華盛頓”——T、“野玫瑰”——F、“機(jī)器人”為F等。由上例可見，當(dāng)使用特定的個(gè)體常量取代了謂詞中的變元，該謂詞就轉(zhuǎn)換成為一個(gè)命題；反之，如果把命題中有獨(dú)立結(jié)構(gòu)的個(gè)體常量替換成變元參量，則又可把命題轉(zhuǎn)換成為一個(gè)具有謂詞結(jié)構(gòu)的表達(dá)式了。96.1.1命題邏輯6.謂詞及變元例2-1假696.1.1命題邏輯3.謂詞的元和謂詞的階

下面先給出關(guān)于謂詞的元的定義，然后再舉例對定義加以解釋和說明。定義6.3

謂詞中包含個(gè)體或變元的數(shù)目，稱為謂詞的元或謂詞的目。例2-2比較下列謂詞或謂詞形式的命題：①LIKE(john，mary)；②ROBOT(john)；③ROBOT(mary)；

④ADDQ(x，y，z)。試解釋具體含義，并指出它們各是幾元謂詞。解：上述謂詞①②③意即“機(jī)器人約翰喜歡瑪麗”；②和③都只有一個(gè)個(gè)體，稱為一元謂詞；相應(yīng)①則稱為二元謂詞；④表示為表達(dá)式“x+y=z”，其中包含有3個(gè)變元，故稱為三元謂詞。依此類推，可推出關(guān)于n元謂詞的概念。

順便指出：在多元謂詞中，變元的排序很重要，一旦確定，就不可隨意交換。

106.1.1命題邏輯3.謂詞的元和謂詞的階下706.1.1命題邏輯3.謂詞的元和謂詞的階

定義6.4

謂詞表達(dá)形式中所包容相疊加的含義層次數(shù)數(shù)目，稱為謂詞的階。例2-3為了說明謂詞的階，我們來比較下列謂詞形式的命題：①LIFELESS(outer-stars)；外星球沒有智能生命。②INCORRECT(lifeless(outer-stars))；說“外星球沒有智能生命”是不確切的。解：在上述謂詞形式的命題中，謂詞①只有一層含義，稱為一階謂詞；謂詞②在前一層含義基礎(chǔ)上，又增加了一層新意，共有二層含義。故把謂詞②稱為二階謂詞。依此類推，可推出關(guān)于n階謂詞的概念。注意：在謂詞邏輯演算中，最重要的有三大類：即：命題邏輯演算、一階謂詞邏輯演算和二階謂詞演算。116.1.1命題邏輯3.謂詞的元和謂詞的階定716.1.1命題邏輯4.命題與謂詞邏輯的關(guān)系命題邏輯表示比較簡單，只能表達(dá)具體固定的情況，命題是謂詞邏輯特殊事例的生動(dòng)描述，謂詞邏輯可以靈活表現(xiàn)多種或變化的情況；謂詞表達(dá)是命題邏輯的抽象與推廣?？偟目磥恚}和謂詞的知識表示形式可以相互轉(zhuǎn)換，而謂詞比命題有更強(qiáng)的表達(dá)能力。顯而易見，謂詞是一種描述個(gè)體群之間的相互關(guān)系、性質(zhì)及其邏輯結(jié)構(gòu)的數(shù)學(xué)表示。人們把采用這種表示的運(yùn)算，又稱為謂詞邏輯。比較起來：命題邏輯演算太簡單，只能解決具體容易的問題；二階謂詞演算又太復(fù)雜，以至迄今為止，尚未找到最根本有效的算法。

因此，在人工智能中，目前使用最多的還是一階謂詞邏輯演算。126.1.1命題邏輯4.命題與謂詞邏輯的關(guān)系726.1.2命題和謂詞邏輯基礎(chǔ)命題或謂詞邏輯推理演算，主要可利用連接詞和量詞，把單個(gè)的謂詞組合成為謂詞公式來完成?；诿}和謂詞邏輯可相互轉(zhuǎn)換的特性，這里約定：在后繼學(xué)習(xí)中，對命題和謂詞邏輯的相關(guān)公式表達(dá)、相關(guān)定理、定律的論證和推導(dǎo)等，不再加以嚴(yán)格區(qū)別。136.1.2命題和謂詞邏輯基礎(chǔ)命題或謂詞邏輯推理演算，主736.1.2命題和謂詞邏輯基礎(chǔ)1.連接詞(Connectives)

所引入的連接詞共有五個(gè)。

⑴符號“?”稱為“否定”(Negation)或補(bǔ)，表示“非”的連接關(guān)系。即當(dāng)命題P為真時(shí)，則?P為假；反之，當(dāng)命題P為假，則?P為真。⑵符號“∧”稱為“合取”(Conjunction)，表示“與”(AND)或“同時(shí)”的關(guān)系。例如，P∧Q，讀作“P與Q”。⑶符號“∨”稱為“析取”(Disjunction)，它表示“或”(OR)的連接關(guān)系。例如，P∨Q，讀作“P或Q”。146.1.2命題和謂詞邏輯基礎(chǔ)1.連746.1.2命題和謂詞邏輯基礎(chǔ)1.連接詞(Connectives)

⑷符號“→”稱為“條件”(Conditional)或者“蘊(yùn)涵”(Implication)，它表示“如果……，則……”的定義關(guān)系。例如，在P→Q的表達(dá)式中，表示了“如果P，則Q”的條件推導(dǎo)關(guān)系。這里，又稱P為前件，稱Q后件。P表示了條件的前提；Q表示了邏輯結(jié)論。應(yīng)該強(qiáng)調(diào)指出，條件表達(dá)式有一個(gè)重要特性：當(dāng)前件P=F時(shí)，無論后件Q為何值(T或者F)，條件式P→Q真值總是為T；當(dāng)前件P=T時(shí)，條件式P→Q的真值總是與后件Q真值相同。⑸符號“”稱為“雙條件”(Biconditional)或者等價(jià)(Equivalence)連接關(guān)系。例如，表達(dá)式PQ，讀作“P當(dāng)且僅當(dāng)Q”?；蛘哒f它表示的含義為：P為真，當(dāng)且僅當(dāng)Q為真。156.1.2命題和謂詞邏輯基礎(chǔ)756.1.2命題和謂詞邏輯基礎(chǔ)1.連接詞(Connectives)

PQ?P

P∨Q

P∧Q

P→Q

PQ

FF

TF

F

T

T

FT

T

T

F

T?

FTF

F

T

F

FF

TT

F

T

T

T

T表2-1連接詞定義真值表

166.1.2命題和謂詞邏輯基礎(chǔ)766.1.2命題和謂詞邏輯基礎(chǔ)2.量詞(Quantifiers)

量詞，表示了個(gè)體與個(gè)體域之間的包含關(guān)系。

⑴全稱量詞(UniversalQuantifier)：用字符“x”表達(dá)，表示了該量詞作用的轄域?yàn)閭€(gè)體域中“所有的個(gè)體x”或“每一個(gè)體x都”要遵從所約定的謂詞關(guān)系。例2-4(x)(現(xiàn)代理工科大學(xué)生(x)→學(xué)習(xí)計(jì)算機(jī)應(yīng)用基礎(chǔ)(x))；解：該謂詞邏輯表達(dá)的含義是：“所有現(xiàn)代理工科的大學(xué)生x，都必須學(xué)習(xí)計(jì)算機(jī)應(yīng)用基礎(chǔ)課程”。

176.1.2命題和謂詞邏輯基礎(chǔ)2.量詞(Q776.1.2命題和謂詞邏輯基礎(chǔ)2.量詞(Quantifiers)⑵存在量詞(ExistentialQuantifier)：用字符“彐x”表達(dá)，表示了該量詞要求“存在于個(gè)體域中的某些個(gè)體x”或“某個(gè)個(gè)體x”，要服從所約定的謂詞關(guān)系。例2-5，(x)(彐y)(CLASSMATE(x,y)∧COLLEGEOFCOMPUTER(x)；解：該謂詞邏輯表達(dá)的意思是：在所有的計(jì)算機(jī)學(xué)院學(xué)生中，相對于每一位同學(xué)x，必然存在一個(gè)個(gè)體y，y同學(xué)與x滿足同班同學(xué)的關(guān)系。186.1.2命題和謂詞邏輯基礎(chǔ)2.量詞(786.1.3命題和謂詞邏輯舉例3.命題公式及其描述舉例：⑴小張既聰明，又勤奮，所以他的學(xué)習(xí)成績一直很好。P：小張聰明Q：小張勤奮R：小張學(xué)習(xí)成績一直很好得到：（P∧Q）→R196.1.3命題和謂詞邏輯舉例3.796.1.3命題和謂詞邏輯舉例⑵小王總是在圖書館看書，除非他病了或圖書館不開門。P：小王病了Q：圖書館開門R：小王在圖書館看書得到：?

（P∨?

Q）

R3.命題公式及其描述舉例：206.1.3命題和謂詞邏輯舉例⑵小王總是在圖書館看書，除806.1.3命題和謂詞邏輯舉例（1）若x是小張的父親，且y是小張的兄弟，則x也是y的父親。解：先設(shè)定謂詞，再設(shè)定變元，并將變元代之以常量，用連接詞運(yùn)算符連接并加以描述：設(shè)定謂詞：FATHER(x,y)：x是y的父親

BROTHER(y,w)：y是w的兄弟

常量：mz表示小張則可描述為：FATHER(x,mz)∧BROTHER(y,mz)→FATHER(x,y)4.謂詞公式及其描述舉例：216.1.3命題和謂詞邏輯舉例（1）若x是小張的父親，且816.1.3命題和謂詞邏輯舉例（2）*在那遙遠(yuǎn)的地方，有位好姑娘，人們走過她的身旁，都要回頭留戀地張望。解：(彐x){好姑娘(x)∧居住的地方(z，x)∧遙遠(yuǎn)的(z)∧(y)[人(y)∧行走經(jīng)過(y,z)→回頭留戀地張望(y)]}4.謂詞公式及其描述舉例：226.1.3命題和謂詞邏輯舉例（2）*在那遙遠(yuǎn)的地方，有6.2謂詞公式及其邏輯表達(dá)式6.2.1謂詞公式概念復(fù)習(xí)與擴(kuò)充：使用連接詞和量詞，把若干謂詞連接組合在一起，就得到了謂詞邏輯公式(PLF：PredicateLogicFormula)的表達(dá)。下面我們給出謂詞公式的相關(guān)各種概念與定義。定義6.5

僅能表達(dá)單一意義且不可再細(xì)劃分的簡單命題稱為原子命題。例如，一階零元(目)命題、一階一元命題、一階二元命題等都是原子命題。定義6.6用連接詞或者量詞把若干原子命題聯(lián)結(jié)組合在一起，就得到了命題公式(PF：PropositionFormula)，又稱之為命題合式公式。定義6.7采用參量變元來替代命題合式公式中的常量，就得到了原子謂詞公式，用連接詞或者量詞把若干原子謂詞聯(lián)結(jié)組合在一起，就得到了謂詞公式,又稱之為謂詞合式公式（PWFF：PredicateWell-FormedFormula），簡稱合式公式或WFF。

6.2謂詞公式及其邏輯表達(dá)式6.2.1謂詞公式概83

6.2.2謂詞公式概念

綜上所述，我們可以給出下述關(guān)于謂詞合式公式及其生成規(guī)則的定理。定理6.1

謂詞合式公式可依照下述遞歸(Recursion)過程得到：①原子公式是謂詞合式公式；②若A是謂詞合式公式，x是A中的任一個(gè)變元，則?A,(x)A和(彐x)A也都是合式公式；③若A、B都是謂詞合式公式，則?A,?B,A∧B,A∨B,A→B,AB也都是合式公式；④若有限次使用上述各步生成的公式，仍是合式公式。246.2.2謂詞公式概念綜上所述，84

6.2.2謂詞公式概念

注意：為了使合式公式WFF在連接和運(yùn)算中表達(dá)簡潔一致，對WFF還有如下規(guī)定：⑴WFF最外層括號可以省略；⑵括號內(nèi)連接符運(yùn)算優(yōu)先，連接符運(yùn)算優(yōu)先次序?yàn)?∧∨→；⑶同級連接符的運(yùn)算按照排列順序進(jìn)行。256.2.2謂詞公式概念85

6.2.2謂詞公式的解釋

謂詞公式的解釋：首先以個(gè)體域中任意常量來替換謂詞公式中的變元，使謂詞公式轉(zhuǎn)換為一組確定的命題公式；隨后賦予各命題邏輯以真值，就得到了對應(yīng)于該謂詞公式的某個(gè)含義的解釋。

由于存在多種組合情況，則一個(gè)謂詞公式可有許多個(gè)解釋。

266.2.2謂詞公式的解釋謂詞86定義：設(shè)D是謂詞公式P的非空個(gè)體域，若對P中的個(gè)體常量、函數(shù)和謂詞按如下規(guī)定賦值：

（1）為每個(gè)個(gè)體常量指派D中的一個(gè)元素；（2）為每個(gè)n元函數(shù)指派一個(gè)從Dn到D的一個(gè)映射，其中

Dn∈{(x1,x2,……xn)|x1,x2,……,xn∈D}

（3）為每個(gè)n元謂詞指派一個(gè)從Dn到{T,F}的映射則稱這些指派為P在D上的一個(gè)解釋。若某個(gè)解釋I使謂詞公式為真(T)，則稱I是該公式的一個(gè)正模型，簡稱模型；反之，若某個(gè)解釋I，使謂詞公式為假(F)，則稱I是該公式的一個(gè)反模型。27定義：設(shè)D是謂詞公式P的非空個(gè)體域，若對P中的個(gè)體常量、87例：設(shè)個(gè)體域D={1,2}，求公式A=(x)(彐y)P(x,y)在D上的解釋，并指出在每一種解釋下公式A的真值。解:由于公式A中沒有包含個(gè)體常量和函數(shù)，因此可以直接為謂詞指派真值，設(shè)有:

這就是公式A在D上的一個(gè)解釋。從這個(gè)解釋可以看出：當(dāng)x=1、y=1時(shí)，有P(x,y)的真值為T；當(dāng)x=2，y=1時(shí)，有P(x,y)的真值為T；即對x在D上的任意取值，都存在y=1使P(x,y)的真值為T。因此，在此解釋下公式A的真值為T。

P(1,1)P(1,2)P(2,1)P(2,2)TFTF28例：設(shè)個(gè)體域D={1,2}，求公式A=(x)(彐y88需要注意，一個(gè)謂詞公式在其個(gè)體域上的解釋不是唯一的。例如，對公式A，若給出另一組真值指派

這也是公式A在D上的一個(gè)解釋。從這個(gè)解釋可以看出：當(dāng)x=1、y=1時(shí)，有P(x,y)的真值為T；當(dāng)x=2、y=1時(shí)，有p(x,y)的真值為F；同樣當(dāng)x=1、y=2時(shí)，有P(x,y)的真值為T；當(dāng)x=2、y=2時(shí)，有P(x,y)的真值為F；即對x在D上的任意取值，不存在一個(gè)y使得P(x,y)的真值為T。因此，在此解釋下公式A的真值為F。實(shí)際上，A在D上共有16種解釋，這里就不再—一列舉。P(1,1)P(1,2)P(2,1)P(2,2)TTFF29需要注意，一個(gè)謂詞公式在其個(gè)體域上的解釋不是唯一的。例如89例：設(shè)個(gè)體域D=｛1，2｝，求公式B=（x）P（f（x），a）在D上的解釋，并指出在該解釋下公式B的真值。

解：設(shè)對個(gè)體常量a和函數(shù)f（x）的真值指派為：

對謂詞的真值指派為：

這里，由于已知指派a=1，所以P（1，2）和P（2，2）不可能出現(xiàn)，故沒有給它們指派真值。

上述指派是公式B在D上的一個(gè)解釋。在此解釋下有

當(dāng)x=1時(shí)，a=1使P（1，1）=T

當(dāng)x=2時(shí)，a=1使P（2，1）=T

即對x在D上的任意取值，都有P（f(x)，a）的真值為T。因此，在此解釋下公式B的真值為T。af(1)f(2)112P(1,1)P(1,2)P(2,1)P(2,2)T×T×

由上面的例子可以看出，謂詞公式的真值都是針對某一個(gè)解釋而言的，它可能在某一個(gè)解釋下真值為T，