1、第一章數(shù)理邏輯,1.1命題1.2重言式1.3范式1.4聯(lián)結(jié)詞的擴(kuò)充與歸約1.5推理規(guī)則和證明方法1.6謂詞和量詞1.7謂詞演算的永真公式1.8謂詞演算的推理規(guī)則,1.1命題,1.1.1命題斷言是一陳述語(yǔ)句。一個(gè)命題是一個(gè)或真或假而不能兩者都是的斷言。如果命題是真,我們說(shuō)它的真值為真如果命題是假,我們說(shuō)它的真值是假。,例1下述都是命題:;(a)今天下雪;(b)3+3=6;(c)2是偶數(shù)而3是奇數(shù);(d)陳涉起義那天,杭州下雨;(e)較大的偶數(shù)都可表為兩個(gè)質(zhì)數(shù)之和。;以上命題,(a)的真值取決于今天的天氣,(b)和(c)是真,(d)已無(wú)法查明它的真值,但它是或真或假的,將它歸屬于命題。(e)目前尚

2、未確定其真假,但它是有真值的,應(yīng)歸屬于命題。,例2下述都不是命題:;(a)x+y4。(c)真好啊!;(b)x=3。(d)你去哪里?;(a)和(b)是斷言,但不是命題,因?yàn)樗恼嬷等Q于x和y的值。(c)和(d)都不是斷言,所以不是命題。,例3一個(gè)人說(shuō):“我正在說(shuō)謊”。他是在說(shuō)謊還是在說(shuō)真話呢?如果他講真話,那么他所說(shuō)的是真,也就是他在說(shuō)謊。我們得出結(jié)論如果他講真話,那么他是在說(shuō)謊。另一方面,如果他是說(shuō)謊,那么他說(shuō)的是假;因?yàn)樗姓J(rèn)他是說(shuō)謊,所以他實(shí)際上是在說(shuō)真話,我們得出結(jié)論如果他是說(shuō)謊,那么他是講真話。從以上分析,我們得出他必須既非說(shuō)謊也不是講真話。這樣,斷言“我正在說(shuō)謊”事實(shí)上不能指定它的

3、真假,所以不是命題。這種斷言叫悖論。,若一個(gè)命題已不能分解成更簡(jiǎn)單的命題,則這個(gè)命題叫原子命題或本原命題。例1中(a),(b),(d),(e)都是本原命題,但(c)不是,因?yàn)樗蓪懗伞?是偶數(shù)”和“3是奇數(shù)”兩個(gè)命題。命題和本原命題常用大寫字母P,Q,R:表示。如用P表示“4是質(zhì)數(shù)”,則記為;P:4是質(zhì)數(shù)。,1.1.2命題聯(lián)結(jié)詞命題和原子命題?？赏ㄟ^(guò)一些聯(lián)結(jié)詞構(gòu)成新命題,這種新命題叫復(fù)合命題。例如;P:明天下雪,Q:明天下雨是兩個(gè)命題,利用聯(lián)結(jié)詞“不”,“并且”,“或”等可分別構(gòu)成新命題:;“明天不下雪”;“明天下雪并且明天下雨”;“明天下雪或者明天下雨”等。,即;“非P”;“P并且Q”;“P

4、或Q”等。在代數(shù)式x+3中,x,3叫運(yùn)算對(duì)象,+叫運(yùn)算符,x+3表示運(yùn)算結(jié)果。在命題演算中,也用同樣術(shù)語(yǔ)。聯(lián)結(jié)詞就是命題演算中的運(yùn)算符,叫邏輯運(yùn)算符或叫邏輯聯(lián)結(jié)詞。常用的有以下5個(gè)。,1.否定詞,設(shè)P表示命題,那么“P不真”是另一命題,表示為P,叫做P的否定,讀做“非P”。從排中律知:如果P是假,則P是真,反之亦然。所以否定詞面具可以如右表所示定義。,這張表叫真值表,定義運(yùn)算符的真值表,指明如何用運(yùn)算對(duì)象的真值,來(lái)決定一個(gè)應(yīng)用運(yùn)算符的命題的真值。真值表的左邊列出運(yùn)算對(duì)象的真值的所有可能組合,結(jié)果命題的真值列在最右邊的一列。為了便于閱讀,我們通常用符號(hào)T(true)或1代表真,符號(hào)F(false

5、)或0代表假。一般在公式中采用T和F,在真值表中采用1和0。這樣,以上真值表可寫成,2.合取詞;,如果P和Q是命題,那么“P并且Q”也是一命題,記為PQ,稱為P和Q的合取,讀做“P與Q”或“P并且Q”。運(yùn)算符定義如下表所示:從真值表可知PQ是真當(dāng)且僅當(dāng)P和Q俱真。,例5P:王華的成績(jī)很好,Q:王華的品德很好。PQ:王華的成績(jī)很好并且品德很好。3.析取詞如果P和Q是命題,則“P或Q”也是一命題,記作PQ,稱為P和Q的析取,崐讀做“P或Q”。運(yùn)算符定義如右表所示。從真值表可知PQ為真,當(dāng)且僅當(dāng)P或Q至少有一為真。,例6;(a)P:今晚我寫字,Q:今晚我看書。PQ:今晚我寫字或看書“或”字常見(jiàn)的含義

6、有兩種:一種是“可兼或”,如上例中的或,它不排除今晚既看書又寫字這種情況。一種是“排斥或”,例如“人固有一死,或重于泰山,或輕于鴻毛”中的“或”,它表示非此即彼,不可兼得。運(yùn)算符表示可兼或,排斥或以后用另一符號(hào)表達(dá)。(b)P:今年是閏年;Q:今年她生孩子。PQ:今年是閏年或者今年她生孩子。,4.蘊(yùn)涵詞(涵常簡(jiǎn)寫作含),如果P和Q是命題,那么“P蘊(yùn)含Q”也是命題,記為PQ,稱為蘊(yùn)含式,讀做“P蘊(yùn)含Q”或“如果P,那么Q”。運(yùn)算對(duì)象P叫做前提,假設(shè)或前件,而Q叫做結(jié)論或后件。運(yùn)算符定義如右表所示。命題PQ是假,當(dāng)且僅當(dāng)P是真而Q是假。,例7(a)P:天不下雨,Q:草木枯黃。PQ:如果天不下雨,那么

7、草木枯黃。(b)R:G是正方形,S:G的四邊相等。RS:如果G是正方形,那么G的四邊相等。(c)W:桔子是紫色的,V:大地是不平的。WV:如果桔子是紫色的,那么大地是不平的。,在日常生活中用蘊(yùn)含式來(lái)斷言前提和結(jié)論之間的因果或?qū)嵸|(zhì)關(guān)系,如上例(a)和(b),這樣的蘊(yùn)含式叫形式蘊(yùn)含,然而,在命題演算中,一個(gè)蘊(yùn)含式的前提和結(jié)論并不需要有因果和實(shí)質(zhì)聯(lián)系,這樣的蘊(yùn)含式叫實(shí)質(zhì)蘊(yùn)含,如上例(c)中,桔子的顏色和大地的外形之間沒(méi)有因果和實(shí)質(zhì)關(guān)系存在,但蘊(yùn)含式WV是真,因?yàn)榍疤崾羌俣Y(jié)論是真。采用實(shí)質(zhì)蘊(yùn)含作定義,是因?yàn)樵谟懻撨壿嫼蛿?shù)學(xué)問(wèn)題中,這不僅是正確的,且方便應(yīng)用。,5.等值詞如果P和Q是命題,那么“P等值

8、于Q”也是命題,記為PQ,稱為等值式,讀做“P等值于Q”。運(yùn)算符定義如右表所示。把蘊(yùn)含式和等值式的真值表加以比較,易知如果PQ是真,那么PQ和QP俱真;反之如果PQ和QP俱真,那么PQ是真。由于這些理由,PQ也讀做“P*是Q的充要條件”或“P當(dāng)且僅當(dāng)Q”。,從以上5個(gè)定義可看出,聯(lián)結(jié)詞之意義由其真值表唯一確定,而不由命題的含義確定。使用以上5個(gè)聯(lián)結(jié)詞,可將一些語(yǔ)句翻譯成邏輯式。翻譯時(shí)為了減少圓括號(hào)(一般不用其它括號(hào))的使用,我們作以下約定:;運(yùn)算符結(jié)合力的強(qiáng)弱順序?yàn)?、,凡符合此順序的,括號(hào)均可省去。相同的運(yùn)算符,按從左至右次序計(jì)算時(shí),括號(hào)可省去。最外層的圓括號(hào)可以省去。例如:(PQ)R)(R

9、P)Q)可寫成;(PQR)RPQ但有時(shí)為了看起來(lái)清楚醒目,也可以保留某些原可省去的括號(hào)。,1.1.3命題變?cè)兔}公式通常,如果P代表真值未指定的任意命題,我們就稱P為命題變?cè)?如果P代表一個(gè)真值已指定的命題,我們就稱P為命題常元。但由于在命題演算中并不關(guān)心具體命題的涵義,只關(guān)心其真假值。因此,我們可以形式地定義它們。以“真”,“假”為其變域的變?cè)?稱為命題變?cè)?T和F稱為命題常元。,這種定義叫歸納定義,也叫遞歸定義。由這種定義產(chǎn)生的公式叫合式公式。,例9(a)說(shuō)明(P(PQ)是命題公式。;解(i)P是命題公式根據(jù)條款(1)(ii)Q是命題公式根據(jù)條款(1)(iii)(PQ)是命題公式根據(jù)(i

10、)(ii)和條款(2)(iv)(P(PQ)是命題公式根據(jù)(i)(iii)和條款(2),(b)以下不是命題公式,因?yàn)樗鼈儾荒苡尚纬梢?guī)則得出。Q,(PQ,PQ,(PQ)R)為了減少圓括號(hào)的使用,以后手寫命題公式時(shí),可按過(guò)去的約定省略。,例10(a)(PQ)P)的真值表如下所示:,因后兩列的真假值完全一致,所以它們是邏輯等價(jià)命題。,1.2重言式,我們著重研究重言式,它最有用,因?yàn)樗幸韵绿攸c(diǎn):(1)重言式的否定是矛盾式,矛盾式的否定是重言式,所以研究其一就可以了。(2)重言式的合取,析取,蘊(yùn)含,等值等都是重言式。這樣,由簡(jiǎn)單的重言式可推出復(fù)雜的重言式。(3)重言式中有許多非常有用的恒等式和永真蘊(yùn)含式

11、。,1.2.2恒等式設(shè)A:A(P1,P2,Pn),B:B(P1,P2,Pn)是兩個(gè)命題公式,這里Pi(i=1,2,n)不一定在兩公式中同時(shí)出現(xiàn)。如果AB是重言式,則A與B對(duì)任何指派都有相同的真值。記為AB,叫做邏輯恒等式,讀做“A恒等于B”。容易看出,AB不過(guò)是上節(jié)的“A和B邏輯等價(jià)”的另一種描述方式而已。所以,AB也讀做“A等價(jià)于B”。請(qǐng)注意符號(hào)與符號(hào)意義不同。是邏輯聯(lián)結(jié)詞,而是表示A和B有邏輯等價(jià)這個(gè)關(guān)系的符號(hào),它的作用相當(dāng)于代數(shù)中的“=”。,表1.2-1邏輯恒等式,表1.2-1邏輯恒等式,1.2.3永真蘊(yùn)含式如果AB是一永真式,那么稱為永真蘊(yùn)含式,記為AB,讀做“A永真蘊(yùn)含B”。,永真蘊(yùn)

12、含式也可用真值表證明，但也可用以下辦法證明:(1)假定前件是真,若能推出后件是真,則此蘊(yùn)含式是真。(2)假定后件是假,若能推出前件是假,則此蘊(yùn)含式是真。,表1.22永真蘊(yùn)含式,1.2.4恒等式和永真蘊(yùn)含式的兩個(gè)性質(zhì)1.若AB,BC則AC;若AB,BC則AC。;這一性質(zhì)也可敘述為:邏輯恒等和永真蘊(yùn)含都是傳遞的。前者留給讀者自證,現(xiàn)證明后者。;證AB永真;BC永真,所以;(AB)(BC)永真。由公式I6得AC永真,既AC。;2.若AB,AC,則ABC。;證A是真時(shí),B和C都真,所以BC也真。因此ABC永真,則ABC。,2.替換規(guī)則(RuleofReplacement)設(shè)有恒等式AB,若在公式C中出

13、現(xiàn)A的地方,替換以B(不必每一處)而得到公式D,則CD。;如果A是合式公式C中完整的一部分,且A本身是合式公式,則稱A是C的子公式,規(guī)則中“公式C中出現(xiàn)A”意指“A是C的子公式”。這條規(guī)則的正確性是由于在公式C和D中,除替換部分外均相同,但對(duì)任一指派,A和B的真值相同,所以C和D的真崐值也相同,故CD。應(yīng)用這兩條規(guī)則和已有的重言式可以得出新的重言式。,(d)找出P(PQ)R的僅含和兩種聯(lián)結(jié)詞的等價(jià)表達(dá)式。,本定理常稱為對(duì)偶原理。,1.3范式,1.3.2主析取范式和主合取范式定義1.3-4在n個(gè)變?cè)幕痉e中,若每一個(gè)變?cè)c其否定不同時(shí)存在,而兩者之一必出現(xiàn)一次且僅出現(xiàn)一次,則這種基本積叫極小項(xiàng)

14、。n個(gè)變?cè)蓸?gòu)成2n個(gè)不同的極小項(xiàng)。例如3個(gè)變?cè)狿,Q,R可構(gòu)造8個(gè)極小項(xiàng)。我們把命題變?cè)闯?,命題變?cè)姆穸闯?,那么每一極小項(xiàng)對(duì)應(yīng)一個(gè)二進(jìn)制數(shù),因而也對(duì)應(yīng)一個(gè)十進(jìn)制數(shù)。,對(duì)應(yīng)情況如下:,定義1.3-5一個(gè)由極小項(xiàng)之和組成的公式,如果與給定的命題公式A等價(jià),則稱它是A的主析取范式。任何一個(gè)命題公式都可求得它的主析取范式,這是因?yàn)槿魏我粋€(gè)命題公式都可求得它的析取范式,而析取范式可化為主析取范式。例如,一個(gè)命題公式的真值表是唯一的,因此一個(gè)命題公式的主合取范式也是唯一的。兩個(gè)命題公式如果有相同的主合取范式,那么兩個(gè)命題公式是邏輯等價(jià)的。一個(gè)命題公式的主析取范式和主合取范式緊密相關(guān),在它們的簡(jiǎn)

15、記式中,代表極小項(xiàng)和極大項(xiàng)的足標(biāo)是互補(bǔ)的,即兩者一起構(gòu)成0,1,2,2n-1諸數(shù),例如APQR(1,3,5,6,7)=則APQR(0,2,4),下面列出極小項(xiàng)和極大項(xiàng)性質(zhì),1.3.3主析取范式的個(gè)數(shù),當(dāng)n=1時(shí),極小項(xiàng)有21=2個(gè),即P,P。主析取范式有:,當(dāng)n=2時(shí),極小項(xiàng)有22=4個(gè),即PQ,PQ,PQ,PQ。主析取范式有,共222=16個(gè)。以此類推,n個(gè)命題變?cè)?可構(gòu)造22n個(gè)不同的主析取范式(包括F)。這個(gè)數(shù)字增長(zhǎng)非?？?如n=3時(shí)223=256,n=4時(shí)224=65536。主合取范式和主析取范式是一一對(duì)應(yīng)的,因此,n個(gè)命題變?cè)?也可構(gòu)造22n個(gè)不同的主合取范式(包括T)。,1.4聯(lián)結(jié)

16、詞的擴(kuò)充與歸約,1.4.1聯(lián)結(jié)詞的擴(kuò)充,1.一元運(yùn)算,2.二元運(yùn)算,在未運(yùn)算前,P和Q的值是屬于表中結(jié)果3和4,即屬于8種之一。以上8種結(jié)果任兩種(包括自己對(duì)自己)經(jīng)運(yùn)算,仍得以上8種結(jié)果之一。,*1.4.3其它主范式前邊介紹了主析取范式和主合取范式,聯(lián)結(jié)詞擴(kuò)充后,也可由極小項(xiàng)和聯(lián)結(jié)詞構(gòu)成主異或范式,由極大項(xiàng)和聯(lián)結(jié)詞構(gòu)成主等值范式。例如,因?yàn)閷?duì)任一指數(shù),任兩個(gè)不同的極小項(xiàng)mi和mj不可能同時(shí)為真,因此mimj與mimj是等價(jià)的,故由主析取范式可轉(zhuǎn)寫成主異或范式。類似地,任兩個(gè)不同的極大項(xiàng)Mi和Mj不可能同時(shí)為假,因此MiMj和MiMj是等價(jià)的,故主合取范式可轉(zhuǎn)寫成主等值范式。主異或范式和主等值

17、范式也是唯一的。,1.5推理規(guī)則和證明方法,1.5.1推理規(guī)則像前幾節(jié)那樣確定命題演算,本質(zhì)上和簡(jiǎn)單的開(kāi)關(guān)代數(shù)一樣,簡(jiǎn)單的開(kāi)關(guān)代數(shù)是命題演算的一種應(yīng)用?，F(xiàn)在,我們從另一角度研究命題演算,即從邏輯推理角度來(lái)理解命題演算。先考察4個(gè)推理的例子,在每一例子中,橫線上的是前提,橫線下的是結(jié)論。右側(cè)是例子的邏輯符表示。設(shè)x屬于實(shí)數(shù),P:x是偶數(shù),Q:x2是偶數(shù)。,例1中,若不管命題的具體涵義,那么它所應(yīng)用的推理規(guī)則就是,中間部分是左側(cè)規(guī)則的另一種寫法,右側(cè)是此推理規(guī)則所對(duì)應(yīng)的永真蘊(yùn)含式。從這個(gè)永真蘊(yùn)含式可看出,它正是代表“如果P并且PQ是真,則Q是真”的意義,這里P和Q表示任意命題。所以,它恰好代表左側(cè)

18、的推理規(guī)則。這條推理規(guī)則叫假言推理,從形式上看結(jié)論Q是從PQ中分離出來(lái)的,所以又叫分離規(guī)則。它是推理規(guī)則中最重要的一條。,對(duì)任一永真蘊(yùn)含式AB來(lái)說(shuō),如果前提A為真,則可保證B為真,因此不難看出,任一個(gè)永真蘊(yùn)含式都可作為一條推理規(guī)則。例如,P(PQ)Q代表以下規(guī)則,叫做析取三段論。,定義1.4-1若H1H2HnC,則稱C是H1,H2,Hn的有效結(jié)論。特別若AB,則稱B是A的有效結(jié)論。定義說(shuō)明:若H1H2HnC,則從H1H2Hn推出C,這樣的推理是正確的。但注意推理正確不等于結(jié)論為真,結(jié)論的真假還取決于前提H1H2Hn的真假,前提為真時(shí),結(jié)論C為真;前提為假時(shí),C可能真也可能假,這就是定義中只說(shuō)C

19、是H1H2Hn的有效結(jié)論而不說(shuō)是正確結(jié)論的原因。有效”是指結(jié)論的推出是合乎推理規(guī)則的。,例2所以錯(cuò)誤,是Q(PQ)P不是永真蘊(yùn)含式,不能用作推理規(guī)則,換言之,P不是Q和(PQ)的有效結(jié)論。這種錯(cuò)誤叫肯定后件的錯(cuò)誤。例3所以錯(cuò)誤,其理由類似于例2,這種錯(cuò)誤叫做否定前件的錯(cuò)誤。最常用的推理規(guī)則,見(jiàn)表1.5-1。,表1.5-1最常用的推理規(guī)則,下面再介紹兩條規(guī)則:;(1)規(guī)則P:在推導(dǎo)的任何步驟上都可以引入前提。;(2)規(guī)則T:在推導(dǎo)中,如果前面有一個(gè)或多個(gè)公式永真蘊(yùn)含S,則可把S引進(jìn)推導(dǎo)過(guò)程。這兩條規(guī)則,一般都認(rèn)為是理所當(dāng)然的,而不作為規(guī)則單獨(dú)提出,但為了提高我們思維的精密性,以便劃清允許或不允許

20、的操作,筆得認(rèn)為有必要列出。,例5(a)考慮下述論證:;如果這里有球賽,則通行是困難的。如果他們按時(shí)到達(dá),則通行是不困難的。他們按時(shí)到達(dá)了。所以這里沒(méi)有球賽。前3個(gè)斷言是前提,最后一斷言是結(jié)論,要求我們從前提推出結(jié)論。設(shè)P:這里有球賽,Q:通行是困難的,R:他們按時(shí)到達(dá)。這論證能表達(dá)如下:,證,列出前提和結(jié)論叫論證(Argument),它未必是有效的。證明(Proof)則是有效論證的展開(kāi),從上例可看出,它由一系列公式(叫公式序列)組成,它們或者是前提,或者是公理,或者是居先公式的結(jié)論,這些結(jié)論都必須根據(jù)推理規(guī)則得出。,(b)證明RS是前提CD,CR,DS的有效結(jié)論。,證,上述證明過(guò)程,本質(zhì)上和

21、數(shù)學(xué)中所見(jiàn)過(guò)的是一致的,不過(guò)這里每一語(yǔ)句是形式化的,并且都是根據(jù)推理規(guī)則得出的。這樣,就不容易產(chǎn)生推理錯(cuò)誤,可確保我們無(wú)誤地構(gòu)造出有效論證的證明。若論證是不正確的,則不能構(gòu)造出這樣的證明,反之亦然。掌握這種形式方法,對(duì)提高我們邏輯分析能力極為重要。,1.無(wú)義證明法證明P是假,那么PQ是真。2.平凡證明法證明Q是真,那么PQ是真。無(wú)義證明法和平凡證明法應(yīng)用的次數(shù)較少,但對(duì)有限的或特殊的情況,它們常常是重要的。,例6(a)定理:如果4x+6y=97,那么x或y不是整數(shù)。證4x+6y=97,可改寫為2x+3y=。2x+3y不是整數(shù),所以x或y不是整數(shù)。這是直接證明法。(b)一個(gè)完全數(shù)是一個(gè)整數(shù),它等

22、于它的所有因子(除本身外)的和。如6是一個(gè)完全數(shù),因?yàn)?=1+2+3,同樣28也是。,定理:一個(gè)完全數(shù)不是一個(gè)質(zhì)數(shù)。;證其逆反如下:一個(gè)質(zhì)數(shù)不是一個(gè)完全數(shù)。假設(shè)P是一質(zhì)數(shù),那么P2并且P恰有兩個(gè)因子1和P,所以小于P的所有因子的總和是1。這得出P不是一個(gè)完全數(shù)。這是間接證明法。,6.P1P2Pn(PQ)形式命題的證明根據(jù)公式E22,P1P2Pn(PQ)等價(jià)于P1P2PnPQ,所以,只須證明P1P2PnPQ這個(gè)方法叫CP規(guī)則,也叫演譯定理,因P移作前提,常使證明簡(jiǎn)化,所以經(jīng)常應(yīng)用。,PQ(PQ),反證法有時(shí)使證明很方便,但它不是必不可少的證明法,總可以用CP規(guī)則代替它,因?yàn)槿粢炎C得,則由CP規(guī)則

23、得,由前提三段論得,H1H2HnC,*1.5.3推理的其它問(wèn)題,把公理用聯(lián)結(jié)起來(lái),求出所得式子的主合取范式,隨意地取出若干個(gè)極大項(xiàng)并用聯(lián)結(jié)之,這樣得出的式子,便是推論。因?yàn)橹骱先》妒綖檎?其每一合取項(xiàng)為真,因此,若干個(gè)合取項(xiàng)之積也是真,所以它是這些公理的推論。如果有m個(gè)合取項(xiàng),可得2m-1個(gè)(0個(gè)合取項(xiàng)不包括在內(nèi))不同的推論。,這里有一推論為,1.6謂詞和量詞,在命題演算中,原子命題是演算的基本單位,不再對(duì)原子命題進(jìn)行分解。故無(wú)法研究命題內(nèi)部的成分,結(jié)構(gòu)及其邏輯特征。例如:“所有的人總是要死的”“蘇格拉底是人”“所以蘇格拉底是要死的”憑直覺(jué)這個(gè)蘇格拉底論證是正確的,但無(wú)法用命題演算表達(dá)出來(lái)。為

24、了深入研究形式邏輯中的推理問(wèn)題,所以有必要將命題演算擴(kuò)充而引入謂詞演算。,1.6.1謂詞,例1(a)5是質(zhì)數(shù)x是質(zhì)數(shù)(b)張明生于北京x生于y(c)7=32x=yz右側(cè)是每個(gè)例子的模式,“是質(zhì)數(shù)”刻畫x的性質(zhì),“生于”刻畫x和y的關(guān)系,“=”刻畫x,y,z的關(guān)系。,我們把“5”“張明”“北京”“7”“3”“2”叫做個(gè)體,代表個(gè)體的變?cè)袀€(gè)體變?cè)??？坍媯€(gè)體的性質(zhì)或幾個(gè)個(gè)體間關(guān)系的模式叫謂詞?！笆琴|(zhì)數(shù)”“生于”“:=:”都是謂詞。謂詞一般用大寫字母P,Q,R,表示,個(gè)體用小寫字母a,b,c,等表示。單獨(dú)的個(gè)體和謂詞不能構(gòu)成命題,故不能將它們分開(kāi)以表示命題。設(shè)F表示“是質(zhì)數(shù)”,則“x是質(zhì)數(shù)”表示為F

25、(x);G表示“生于”,則“x生于y”表示為G(x,y);H表示“=”,則“x=yz”表示為H(x,y,z)。F(x),G(x,y),H(x,y,z)等叫謂詞命名式,簡(jiǎn)稱謂詞。,一個(gè)個(gè)體變?cè)闹^詞叫一元謂詞,兩個(gè)個(gè)體變?cè)闹^詞叫二元謂詞,一般地,n個(gè)個(gè)體變?cè)闹^詞叫n元謂詞,記為P(x1,x2,xn)。一般謂詞用設(shè)定的字母表示,常用的謂詞則用特定的符號(hào)表示。例如:xy,可寫成(x,y)或L(x,y)(L表示小于)x=yz,可寫成=(x,y,z)(要事先說(shuō)明)但最常用的仍寫成xy,x=yz,稱為謂詞的中綴記法。不管怎樣記法,變?cè)拇涡蚴侵匾?例如(x,y)與(y,x)不一樣。,一個(gè)字母代表一特

26、定謂詞,例如F代表“是質(zhì)數(shù)”,則稱此字母為謂詞常元。若字母代表任意謂詞,則稱此字母為謂詞變?cè)?。我們通常不加區(qū)分,但一般從上下文可看出它的含義。謂詞命名式中個(gè)體變?cè)娜≈捣秶凶稣撌鲇蚧騻€(gè)體域。容易看出,空集不能作為論述域,所以,以后談到論述域都至少有一個(gè)個(gè)體。例1(a)的論述域是正整數(shù),(c)的論述域是實(shí)數(shù),(b)中x的變域是人類,y的變域是地名集,所以論述域分別是人類和地名集。,謂詞命名式中,若謂詞是常元,個(gè)體變?cè)哉撌鲇蛑械哪骋粋€(gè)體,就成為一個(gè)命題。例如F(5)是真,F(4)是假,G(張明,北京)是真(假定張明生于北京),所以謂詞命名式是一個(gè)命題函數(shù)。設(shè)x+y=z表示為P(x,y,z),

27、若取定x為3,即P(3,y,z),可改記為P(y,z)成為二元謂詞,再取定y為4,即P(4,z),可改記為P(z),成為一元謂詞,再取定z為5,即P(5),可改記為P而成為命題?？梢?jiàn)命題是0元謂詞,所以謂詞是命題概念的擴(kuò)充,命題是謂詞的一種特殊情況。,例2(a)y(yy+1)(c)y(yy+1);(b)y(y=3)(d)y(y=3);如果論述域是整數(shù),則(a)是真,(b)是假,(c)和(d)是真。設(shè)F(x)表示“x是質(zhì)數(shù)”,將謂詞F(x)變?yōu)槊}有兩種方法,第一種是將x取定一個(gè)值,例如4,那么F(4)是命題(假),這種方法的本質(zhì)是給變?cè)约s束。第二種是將謂詞量化,例如xF(x)(假),xF(x

28、)(真),這種方法的本質(zhì)也是給變?cè)约s束,不過(guò)約束方法不一樣。所以量化的作用是約束變?cè)?量化后所得命題的真值與論述域有關(guān),例如y(y=3),如果論述域是正整數(shù),這一命題是真,如果論述域是大于4的整數(shù),則這一命題是假。對(duì)不同的個(gè)體變?cè)?用不同的論述域是可以的,但有時(shí),不同的個(gè)體變?cè)黄鹩懻摃r(shí),用不同的論述域甚感不便,于是我們?cè)O(shè)想有一個(gè)集合,它包括謂詞中各個(gè)體變?cè)乃袀€(gè)體域,我們稱它為全總個(gè)體域。用了全總個(gè)體域以后,個(gè)體變?cè)≈捣秶恢铝?但不同論述對(duì)象須用不同的特性謂詞加以再刻畫。,設(shè)F(x)表示“x是不怕死的”,D(x)表示“x是要死的”,M(x)表示“x是人”。如果論述域是全人類,則;“

29、人總是要死的”譯為xD(x)。;“有些人不怕死”譯為xF(x)。;如果是全總個(gè)體域,則分別譯為;x(M(x)D(x)x(M(x)F(x),（1）（2）,(2)式可表達(dá)為“存在一些x,x是人并且是不怕死的”。各概念間的關(guān)系如圖1.6-2所示。,圖1.6-2,特性謂詞怎樣加入到斷言中去,有以下兩條規(guī)則:(1)對(duì)全稱量詞,特性謂詞作為蘊(yùn)含式之前件而加入之。(2)對(duì)存在量詞,特性謂詞作為合取項(xiàng)而加入之。第一條規(guī)則不易理解,例如“人總是要死的”譯為x(M(x)D(x)似乎也不錯(cuò),其實(shí)不對(duì),這主要由于量化斷言的真假與論述域有關(guān),現(xiàn)在是全總個(gè)體域,域中除人外,還有不是人的x,上述的意義是“所有的x,都是人并

30、且都是要死的”,所以它是不正確的。,(b)凡是實(shí)數(shù),不是大于零就是等于零或小于零。解設(shè)R(x)表示“x是實(shí)數(shù)”,(x,0),=(x,0),(x,0)分別表示x大于,等于,小于零。則上句可譯為:x(R(x)(x,0)=(x,0)(x,0),(c)在ALGOL-60程序設(shè)計(jì)語(yǔ)言中,一維整數(shù)數(shù)組arrayA150中的每一項(xiàng)均不為零,可以表示為x(I(x)x1x50Ax0)這里I(x)表示“x是整數(shù)”。其它謂詞就用中綴記法。;多元謂詞可以多重量化,方法與一元謂詞的量化一致。,例4(a)對(duì)于所有的自然數(shù),均有x+yx。設(shè)F(x,y)表示x+yx,N(x)表示“x是自然數(shù)”。則上句可譯為:xy(N(x)N

31、(y)F(x,y)如果F(x,y)表示xy,則上句可譯為xy(N(x)N(y)F(x+y,x)就是說(shuō),翻譯時(shí),允許把個(gè)體和運(yùn)算符組成的式子,諸如x+y,x+2,x2等,作為個(gè)體(因?yàn)樗鼈兇韨€(gè)體),填入謂詞命名式的個(gè)體位上。,(b)某些人對(duì)某些食物過(guò)敏。設(shè)F(x,y)表示“x對(duì)y過(guò)敏”,M(x)表示“x是人”,G(x)表示“x是食物”。于是上句可譯為xy(M(x)G(y)F(x,y),(3)如果論述域是不可數(shù)無(wú)限,諸如實(shí)數(shù)集合,則無(wú)法表達(dá)。以上展開(kāi)式?？蓭椭覀兙唧w理解xP(x)和xP(x)。,1.6.4謂詞公式不出現(xiàn)命題聯(lián)結(jié)詞和量詞的謂詞命名式P(x1,x2,xn)稱為謂詞演算的原子公式。此

32、表示法也包括n=0的情況,此時(shí)P(x1,x2,xn)即為原子命題公式P。由原子公式出發(fā),我們可定義謂詞演算的合式公式,簡(jiǎn)稱公式。(1)謂詞演算的原子公式是謂詞演算公式。,1.6.5自由變?cè)c約束變?cè)o接于量詞之后最小的子公式叫量詞的轄域。例如:(1)xP(x)Q(x)(2)x(P(x,y)Q(x,y)P(y,z)x的轄域是P(x),x的轄域是(P(x,y)Q(x,y),轄域不是原子公式,其兩側(cè)必須有括號(hào),否則,不應(yīng)有括號(hào)。在量詞x,x的轄域內(nèi)變?cè)獂的一切出現(xiàn)叫約束出現(xiàn),稱這樣的x為約束變?cè)Ｔ谝还街?變?cè)姆羌s束出現(xiàn)叫變?cè)淖杂沙霈F(xiàn),稱這樣的變?cè)獮樽杂勺冊(cè)?一個(gè)公式中,一個(gè)約束變?cè)姆?hào)是

33、無(wú)關(guān)緊要的。如公式xP(x),若將x改為y,得yP(y),它與原公式有相同的意義,這同定積分中積分變量可以改變類似。所以一公式中的約束變?cè)强梢愿牡?改名規(guī)則如下:(1)若要改名,則該變?cè)诹吭~及其轄域中的所有出現(xiàn)均須一起更改,其余部分不變。(2)改名時(shí)所選用的符號(hào),必須是量詞轄域內(nèi)未出現(xiàn)的符號(hào),最好是公式中未出現(xiàn)的符號(hào)。,例如:xP(x)Q(x)yP(y)Q(x),x(A(x)B(x,y)C(x)D(w)z(A(z)B(z,y)C(x)D(w)。但x(A(x)B(x,y)C(x)D(w)不可改名為y(A(y)B(y,y)C(x)D(w)。,定義1.7-2如果兩謂詞公式A和B,在任意論述域上

34、都等價(jià),則稱A和B等價(jià),記為AB。定義1.7-3給定任一謂詞公式A,如果在論述域E上,對(duì)公式A中的謂詞和個(gè)體變?cè)M(jìn)行定義1.7-1中的兩種指派,所得命題;(1)都真,則稱A在E上有效或在E上永真。(2)至少有一個(gè)是真,則稱A在E上可滿足。(3)都假,則稱A在E上永假或在E上不可滿足。,定義1.7-4給定任一謂詞公式A,如果在任意論述域上,對(duì)上述兩種指派,(1)A永真,則稱A永真或有效。(2)A至少在一個(gè)域上可滿足,則稱A可滿足。(3)A永假,則稱A永假或不可滿足。若謂詞公式A的個(gè)體域是有限的,謂詞的解釋也有限,則可用真值表判定謂詞公式A是否永真。例如:,設(shè)P(x)僅可解釋為A(x):x是質(zhì)數(shù),

35、B(x):x是合數(shù)。論述域是3,4,判定謂詞公式P(x)xP(x)是否永真。解(見(jiàn)右表)所以,P(x)xP(x)非永真式。當(dāng)謂詞的解釋和個(gè)體變?cè)臄?shù)量稍大,用真值表判定就難以實(shí)現(xiàn)。一般利用推導(dǎo)方法,因此,如同命題演算一樣,首先要求出基本的永真公式,以作為推導(dǎo)的根據(jù)。,1.7.2謂詞演算的基本永真公式,1.命題演算的永真公式也是謂詞演算的永真公式,基本的就是列于表1.2-1,表1.2-2的恒等式和永真蘊(yùn)含式。,2.含有量詞的謂詞演算的基本永真公式。(i)xAAxAA這里A是不含自由變?cè)獂的謂詞公式,因?yàn)锳的真值與x無(wú)關(guān),所以上述等價(jià)式成立。(ii)xP(x)P(y)或xP(x)P(x)P(y)x

36、P(x)P(x)xP(x)這兩個(gè)公式是根據(jù)量詞的含義得出的。前一公式的意義是:如果斷言“對(duì)一切x,P(x)是真”成立,那么對(duì)任一確定的x,P(x)是真。后一公式的意義是:如果對(duì)某一確定的x,P(x)是真,那么斷言“存在一x,使P(x)是真”成立。,(v)量詞的分配形式:x(A(x)B(x)xA(x)xB(x)x(A(x)B(x)xA(x)xB(x)x(A(x)B(x)xA(x)xB(x)xA(x)xB(x)x(A(x)B(x)第個(gè)等價(jià)式的成立是由于對(duì)一切x,A(x)B(x)是真,等價(jià)于對(duì)一切x,A(x)是真并且對(duì)一切x,B(x)是真。,第個(gè)公式,我們首先證明它是不等價(jià)的。設(shè)A(x)和B(x)分

37、別解釋為“x是奇數(shù)”和“x是偶數(shù)”,論述域是自然數(shù)N,則xA(x)是真,xB(x)是真,所以xA(x)xB(x)是真,但x(A(x)B(x)是假,所以第個(gè)公式不等價(jià)。再說(shuō)明第個(gè)公式是成立的,因?yàn)榇嬖谝粁使A(x)B(x)是真,所以存在一x使A(x)是真,同時(shí)存在一x使B(x)是真。,(vi)量詞對(duì)及的處理只須應(yīng)用它們對(duì),的恒等式即可推出。例如,(vii)關(guān)于多個(gè)量詞的永真式:xyP(x,y)yxP(x,y)xyP(x,y)yxP(x,y)yxP(x,y)xyP(x,y)xyP(x,y)yxP(x,y)xyP(x,y)yxP(x,y),注意xyP(x,y)yxP(x,y)是不成立的。例如:設(shè)P(

38、x,y)表x+y=0,論述域是有理數(shù)集合。則xy(x+y=0)是真,但yx(x+y=0)是假。由此可知,量詞的次序是重要的,但第和公式例外。以上7組公式,當(dāng)論述域都是有限時(shí),則可將謂詞公式展開(kāi)為命題公式證明。例如公式,xA(x)Px(A(x)P),表1.7-1含有量詞的永真公式概要表,(b)對(duì)公式A:F(x,y)MF(u,x)中的F,欲代以B:G(x1)H(x2,s)H(t,x2),則只需x,y,u不是B內(nèi)的約束變?cè)?而s,t不是A內(nèi)的約束變?cè)?。代入結(jié)果為(G(x)H(y,s)H(t,y)M(G(u)H(x,s)H(t,x)若原式是永真式,則代入后仍得永真式;若原式是非永真式,則代入后可能變化

39、。另外,命題演算中的代入規(guī)則是本規(guī)則的特例。,2.替換規(guī)則設(shè)A(x1,x2,xn)B(x1,x2,xn),而A是公式C中的子公式,將B替換C中之A不必每一處得D,則CD。,為了證明不是永真的,只需找出一個(gè)論述域及域上謂詞的一種解釋,使上式是假即可?，F(xiàn)設(shè)論述域是整數(shù)集合,P(x)表示x=0,Q(x)表示xx。于是xP(x)是假,因而xP(x)xQ(x)是真,但xP(x)是真,xQ(x)是假,xP(x)xQ(x)是假。故(xP(x)xQ(x)(xP(x)xQ(x)是假。,1.8謂詞演算的推理規(guī)則,1.8.1術(shù)語(yǔ)“A(x)對(duì)y是自由的”的意義在敘述推理規(guī)則之前,先介紹術(shù)語(yǔ)“A(x)對(duì)y是自由的”的意

40、義?？疾煲韵轮^詞公式:,為了強(qiáng)調(diào)這些謂詞公式對(duì)自由變?cè)獂的依賴關(guān)系,可以分別記為B(x),C(x),D(x)。記法中省略了其它自由變?cè)Ｈ绻紸(x)中,x不出現(xiàn)在量詞y或y的轄域之內(nèi),則稱A(x)對(duì)y是自由的。例如在(2)式中,C(x)對(duì)y是不自由的,在(1),(3)式中,B(x)和D(x)對(duì)y是自由的。如果需要將A(x)中的x代以y,則代入后所得的式子記以A(y),但代入之前須觀察A(x)對(duì)y是否自由,如果不自由,不能代入。,例如,將x代以y。(1)式可以代入,得B(y):yP(y)Q(y)R(z)(3)式可以代入,得D(y):yP(y)Q(y,y)(2)式不可以,代入后得C(y):yP

41、(y,y)Q(y,y)。P(x,y)中的x原來(lái)是自由的,現(xiàn)在成了約束的,所以不能代入。如果有必要代入y,則應(yīng)先將式中的約束變?cè)獃改名,例如,把(2)式改名為:zP(x,z)Q(x,y)然后代入得zP(y,z)Q(y,y)這里所講的就是前節(jié)所講的代入規(guī)則(i),讀者可以對(duì)比一下,以便更好地領(lǐng)會(huì)它們。,1.8.2謂詞演算中的推理規(guī)則命題演算中所有推理規(guī)則都是謂詞演算中的推理規(guī)則;另外,謂詞演算中的所崐有永真蘊(yùn)含式,恒等式和代入規(guī)則也都可作為推理規(guī)則?，F(xiàn)著重對(duì)以下4條給出詳細(xì)解釋。(1)全稱指定規(guī)則(UniversalSpecification)簡(jiǎn)記為US。,應(yīng)用這一規(guī)則的條件是:A(x)對(duì)于y必須是自由的。,這一規(guī)則也可寫為:,它的意義是,全稱量詞可以刪除。,(2)存在指定規(guī)則(ExistentialSpecification)簡(jiǎn)記為ES。,它的意義是:如果已證明xA(x),那么我們可以假設(shè)某一確定