02-離散謂詞邏輯-1.1-1.3

1、第二章 謂詞邏輯1命題邏輯存在的問(wèn)題在命題邏輯中，把命題分解到原子命題為止，僅研究以原子命題為基本單位的復(fù)合命題之間的邏輯關(guān)系和推理。有些推理難以用命題演算確切表達(dá)。例如：“所有人總是要死的”“蘇格拉底是人”“所以蘇格拉底是要死的”PQRLs表示為：P, Q R 而(P Q) R并不是永真式命題邏輯存在的問(wèn)題問(wèn)題在于：各個(gè)命題之間的邏輯關(guān)系，不是體現(xiàn)在原子命題之間，而是體現(xiàn)在構(gòu)成原子命題的內(nèi)部成分之間，即體現(xiàn)在命題結(jié)構(gòu)的更深層次上所以，在研究某些推理時(shí)，有必要對(duì)原子命題做進(jìn)一步分析，分析出其中的個(gè)體詞、謂詞和量詞，研究它們的形式結(jié)構(gòu)和邏輯關(guān)系，正確的推理形式和規(guī)則這就是謂詞邏輯（Lp）的基本內(nèi)

2、容命題邏輯存在的問(wèn)題例如：“所有人總是要死的”“蘇格拉底是人”“所以蘇格拉底是要死的”“人”這個(gè)群體具有“是要死的”的特性“蘇格拉底”是“人”這個(gè)群體中的一個(gè)個(gè)體“蘇格拉底”具有“人”這個(gè)群體的“是要死的”特性第一節(jié) 個(gè)體、謂詞和量詞第一節(jié) 個(gè)體、謂詞和量詞命題是具有真假意義的陳述句，從語(yǔ)法上分析，一個(gè)陳述句由主語(yǔ)和謂語(yǔ)兩個(gè)部分組成。在謂詞邏輯中，為揭示命題內(nèi)部結(jié)構(gòu)及不同命題的內(nèi)部結(jié)構(gòu)關(guān)系，就按這兩個(gè)部分進(jìn)行分析主語(yǔ)稱為個(gè)體或客體謂語(yǔ)稱作謂詞個(gè)體和謂詞一、個(gè)體和謂詞定義：在原子命題中，所描述的對(duì)象，稱為個(gè)體用以描述個(gè)體性質(zhì)，或個(gè)體間關(guān)系的部分，稱為謂詞個(gè)體個(gè)體，是指可以獨(dú)立存在的事物，可以是具

3、體的，也可以是抽象的。例如：李明、香蕉、電視機(jī)、精神、思想，等表示特定的個(gè)體，稱為個(gè)體常元通常用 a, b, c, 或ai, bi, ci, 表示例如：李明、字母A、數(shù)字5表示不確定的個(gè)體，叫作個(gè)體變?cè)ǔＳ?x, y, z, 或xi, yi, zi, 表示例如：花朵、星星、男生、學(xué)校謂詞當(dāng)謂詞與一個(gè)個(gè)體相關(guān)時(shí)，刻劃了該個(gè)體的性質(zhì)例如：5是質(zhì)數(shù)，A是字母一元謂詞當(dāng)謂詞與兩個(gè)或兩個(gè)以上個(gè)體相關(guān)時(shí)，刻劃了個(gè)體間的關(guān)系例如：李明生于北京，10比5大二元謂詞謂詞一般用大寫字母 P, Q, R, 或 Pi, Qi, Ri, 表示命題的謂詞形式二、命題的謂詞形式單獨(dú)的個(gè)體和謂詞不能構(gòu)成命題命題的表示：將表

4、示個(gè)體的小寫字母，寫在表示謂詞的大寫字母右側(cè)的括號(hào)里。命題的謂詞形式“李明是大學(xué)生”其中：李明是個(gè)體，用a表示“是大學(xué)生”是謂詞，用S表示則該命題表示為 S(a)：李明是大學(xué)生“張華出生在北京”其中：張華和北京是個(gè)體，用a表示張華，用b表示北京“出生在”是謂詞，用B表示則該命題表示為 B(a, b)：張華出生在北京命題的謂詞形式定義：一個(gè)原子命題，用一個(gè)謂詞P和n個(gè)有次序的個(gè)體常元 a1, a2, , an 表示成P (a1, a2, , an)，稱為（原子）命題的謂詞形式注意：命題的謂詞形式中的個(gè)體出現(xiàn)的次序影響命題的真值。例如：P：比大，則 P(10, 5)：10比5大，真值為真而P(5,

5、 10)：5比10大，真值為假原子謂詞三、原子謂詞將原子命題的謂詞形式進(jìn)行抽象，例如n個(gè)個(gè)體常元a1, a2, , an 替換成n個(gè)個(gè)體變?cè)獂1, x2, , xn，這樣便得到了一種關(guān)于命題結(jié)構(gòu)的新表達(dá)形式 P (x1, x2, , xn) ，稱為n元原子謂詞 。例如： S(a) S(x) ：x是學(xué)生原子謂詞定義：由一個(gè)謂詞P和n個(gè)個(gè)體變?cè)獂1, x2, , xn組成的P (x1, x2, , xn) 稱為n元原子謂詞或n元命題函數(shù)簡(jiǎn)稱n元謂詞 。個(gè)體變?cè)娜≈捣秶凶鱾€(gè)體域或論域當(dāng)n=1時(shí)，稱為一元謂詞當(dāng)n=2時(shí)，稱為二元謂詞特別的，當(dāng)n=0時(shí)，稱為零元謂詞，即命題原子謂詞n元謂詞并不是命題

6、，只有當(dāng)所有的命題變?cè)加脗€(gè)體常元替代時(shí)，才能成為一個(gè)命題而個(gè)體變?cè)谀膫€(gè)論域取值，對(duì)命題的真值有影響例如： S(x) ：x是大學(xué)生若x的論域是某大學(xué)的全體學(xué)生，則S(x) 為真若x的論域是某小學(xué)的全體學(xué)生，則S(x) 為假若x的論域是商場(chǎng)的全體顧客，則S(x)的真值不確定原子謂詞把一個(gè)n元謂詞中的每個(gè)個(gè)體的論域綜合在一起作為n元謂詞的全總論域當(dāng)一個(gè)命題未指定論域時(shí)，一般將全總論域作為其論域。這時(shí)往往需要一個(gè)一元謂詞 P(x) 來(lái)限定個(gè)體變?cè)獂的取值范圍，將 P(x) 稱為特性謂詞。例如： S(x) ：x是學(xué)生N(x) ：x是自然數(shù)量詞四、量詞對(duì)謂詞的理解，如 S(x) ：x是學(xué)生（x是某單位

7、的職工）可以理解為：某單位的職工都是學(xué)生或者：某單位存在一些職工是學(xué)生為了避免歧義，表達(dá)“所有的”或者“存在一些”等表示數(shù)量的詞，我們引進(jìn)量詞這個(gè)概念。量詞定義1： ：全稱量詞符。表示“所有的”、“對(duì)每一個(gè)”、 “對(duì)任何一個(gè)”等詞語(yǔ)x ：稱為全稱量詞，x叫作指導(dǎo)變?cè)? x) P(x)( x) P(x) ( x) P(x) ( x) P(x)對(duì)于一切x，P(x)為真對(duì)于一切x， P(x)為真并非對(duì)于一切x，P(x)為真并非對(duì)于一切x， P(x)為真量詞定義2： ：存在量詞符。表示“存在一些”、“至少有一個(gè)”、 “對(duì)于一些”等詞語(yǔ)x ：稱為存在量詞，x叫作指導(dǎo)變?cè)?x) P(x)(x) P(x)

8、(x) P(x) (x) P(x)存在x，使P(x)為真存在x，使 P(x)為真并非存在x，使P(x)為真并非存在x，使 P(x)為真量詞定義3：!：存在唯一量詞符。表示“存在唯一” 等詞語(yǔ)!x：稱為存在唯一量詞，x叫作指導(dǎo)變?cè)?!x) P(x)(!x) P(x) (!x) P(x) (!x) P(x)存在唯一的x，使P(x)為真存在唯一的x，使 P(x)為真并非存在唯一的x，使P(x)為真并非存在唯一的x，使 P(x)為真量詞例2.1 試用量詞、謂詞表示下述命題所有學(xué)生都熱愛(ài)祖國(guó)S(x)：x是學(xué)生（特性謂詞）L(x)：x熱愛(ài)祖國(guó)命題表示為：(x) ( S(x) L(x) )對(duì)于全稱量詞，特性

9、謂詞作為蘊(yùn)涵式的前件出現(xiàn)(x) ( S(x) L(x) )量詞凡是實(shí)數(shù)，不是大于零，就是等于零或小于零R(x)：x是實(shí)數(shù)（特性謂詞）B(x)：x大于零E(x)：x等于零S(x)：x小于零命題表示為：(x) ( R(x) B(x)E(x)S(x) )量詞一些大學(xué)生有遠(yuǎn)大理想S(x)：x是大學(xué)生（特性謂詞）P(x)：x有遠(yuǎn)大理想命題表示為：(x) ( S(x) P(x) )對(duì)于存在量詞，特性謂詞作為合取項(xiàng)出現(xiàn)( x) ( S(x) P (x) )量詞所有的貓都是動(dòng)物 （1）對(duì)任何個(gè)體域來(lái)講，命題（1）都為真。設(shè)個(gè)體域E是 花虎，黃咪， 遍及個(gè)體域E命題（1）為真。令命題（1）正確的表達(dá)成：(x)

10、( C(x) A(x) )用個(gè)體域中任何元素去取代個(gè)體變?cè)獂，則都會(huì)獲得一個(gè)真命題若選用合取式的形式把它表示成 (x) ( C(x) A(x) )用個(gè)體域中的 去取代變?cè)獂，則由C(x) A(x) 所得到的命題真值必定都為假不可以選用合取式來(lái)表達(dá)“所有的A是B” 形式的命題總結(jié)：量詞與特性謂詞的搭配還有一定的規(guī)律，即全稱量詞后跟一個(gè)條件式，特性謂詞作為其前件出現(xiàn)；存在量詞后跟一個(gè)合取式，特性謂詞作為一個(gè)合取項(xiàng)出現(xiàn)C（x）：x是貓A（x）：x是動(dòng)物量詞一些貓是黑色的 （2）設(shè)個(gè)體域E仍然是 花虎，黃咪， 并設(shè)“花虎”是雜色的，“黃咪”是黃色的令在這種情況下個(gè)體域E中沒(méi)有黑色的貓，因此命題（2）的

11、真值為假用合取式把命題（2）正確的表達(dá)成：(x) ( C(x) B(x) ) （3）由于個(gè)體域中沒(méi)有黑色的貓，所以命題（3）的真值為假若選用條件命題公式的形式把它表示成 ( x) ( C(x) B(x) )用個(gè)體域中的 去取代變?cè)獂，則由C(x) B(x) 所得到的命題真值為真。（前件為假，善意推定）不可以選用條件命題公式的形式來(lái)表達(dá)“一些A是B” 形式的命題B（x）：x是黑色的 C（x）：x是貓總結(jié)：量詞與特性謂詞的搭配還有一定的規(guī)律，即全稱量詞后跟一個(gè)條件式，特性謂詞作為其前件出現(xiàn)；存在量詞后跟一個(gè)合取式，特性謂詞作為一個(gè)合取項(xiàng)出現(xiàn)量詞沒(méi)有不犯錯(cuò)誤的人P(x)：x是人（特性謂詞）W(x)：

12、x犯錯(cuò)誤命題表示為： (x) ( P(x) W (x) ) (x) ( P(x) W (x) )量詞有些人對(duì)食物過(guò)敏P(x)：x是人（特性謂詞）Q(x)：x對(duì)食物過(guò)敏命題表示為： (x) ( P(x) Q (x) )或者： P(x)：x是人， F(x)：x是食物 Q(x, y)：x對(duì)y過(guò)敏命題表示為：(x) (y) (P(x)F(y) Q (x, y)量詞若一個(gè)謂詞中的所有個(gè)體變?cè)剂炕?，該謂詞就變成了命題。例如：P(x)：x是人， F(x)：x是食品Q(x, y)：x對(duì)y過(guò)敏 P(x)F(y)Q (x, y) 不是命題 而(x) (y) (P(x)F(y)Q (x, y) 是命題(x) (

13、y) (P(x)F(y) Q (x, y) 也是命題第二節(jié) 謂詞公式與翻譯第二節(jié) 謂詞公式與翻譯一、謂詞公式項(xiàng)定義：項(xiàng)由下列規(guī)則組成 個(gè)體常元和個(gè)體變?cè)琼?xiàng)若f是n元函數(shù)，且t1, t2, , tn是項(xiàng)，則f(t1, t2, , tn)是項(xiàng)所有項(xiàng)都由1) 2)生成項(xiàng)例如：f(x, y) 表示x+y，N(x)表示x是自然數(shù) N( f(2,3) ) 即 N(5) 表示5是自然數(shù)P(x)：x是教授，f(x)：x的父親，a：李明P( f(a) )：李明的父親 是教授I(x)：x是整數(shù)，f(x)=x2-1，g(x)=(x+1)(x-1)E(x, y)：x=y 則 x2-1=(x+1)(x-1)(x是整數(shù)

14、)表示為： (x) ( I(x) E( f(x), g(x) ) )謂詞表示個(gè)體的性質(zhì)，它的取值T,F函數(shù)表示個(gè)體經(jīng)過(guò)運(yùn)算后得到的值，可能是任意值謂詞公式謂詞公式P (x1, x2, , xn)是n元原子謂詞， t1, t2, , tn是項(xiàng)，稱P (t1, t2, , tn)是原子謂詞公式，簡(jiǎn)稱原子公式合式謂詞公式是由下列規(guī)則形成的字符串原子公式是合式謂詞公式若A是合式謂詞公式，則( A)是合式謂詞公式若A、B是合式謂詞公式，則(AB)，(AB)，(AB)，(AB) 也是合式謂詞公式若A是合式謂詞公式，x是個(gè)體變?cè)?，則(x) A和 (x) A都是合式謂詞公式只有有限次使用1)4)形成的才是合式

15、謂詞公式謂詞公式例如：(x) P(x)， (x)(S(x) P(x)， P(x)Q(f(x) 都是合式謂詞公式(x) (P(x) Q(x)， (x)( P(x)等都不是合式謂詞公式命題公式是合式謂詞公式的一個(gè)特例謂詞公式的翻譯二、謂詞公式的翻譯（符號(hào)化）把一個(gè)文字?jǐn)⑹龅拿}用謂詞公式表述出來(lái)正確理解命題把每個(gè)原子命題分解成個(gè)體、謂詞和量詞在全總論域討論時(shí)，要給出特性謂詞找出恰當(dāng)量詞全稱量詞將特性謂詞作為蘊(yùn)涵式的前件存在量詞將特性謂詞作為合取項(xiàng)用恰當(dāng)?shù)穆?lián)結(jié)詞把命題表示出來(lái)謂詞公式的翻譯例2.2 用謂詞公式表述下述命題張三和李四都是大學(xué)生個(gè)體：a：張三，b：李四謂詞：S(x)：x是大學(xué)生符號(hào)化為：

16、S(a) S(b)李華是象棋迷或圍棋迷個(gè)體：a：李華謂詞：P(x)：x是象棋迷，Q(x)：x是圍棋迷符號(hào)化為：P(a) Q(a)謂詞公式的翻譯湯姆和杰克是親兄弟個(gè)體：a：湯姆，b：杰克謂詞：B(x, y)：x和y是親兄弟符號(hào)化為： B(a, b)沒(méi)有最大的自然數(shù)可理解為：對(duì)于任何一個(gè)自然數(shù)，都存在比它大的自然數(shù)謂詞：N(x)：x是自然數(shù)，B(x, y)：x比y大符號(hào)化為： (x) ( N(x) (y)(N(y)B(y, x) )謂詞公式的翻譯今天有雨雪，有些人會(huì)跌跤謂詞：R：今天有雨，S：今天有雪，P(x)：x是人F(x)：x會(huì)跌跤符號(hào)化為： RS (x)( P(x) F(x) )盡管有人聰明

17、，但未必所有人都聰明謂詞：P(x)：x是人，F(xiàn)(x)：x聰明符號(hào)化為： (x)( P(x)F(x) ) (x) ( P(x) F(x) )第三節(jié) 約束變?cè)c自由變?cè)谌?jié) 約束變?cè)c自由變?cè)x：給定一個(gè)謂詞公式A，其中包含子公式形如(x)B(x)或(x)B(x) ，則稱它為A的x約束部分稱B(x)為相應(yīng)量詞的作用域或轄域在轄域B(x)中，x的所有出現(xiàn)稱為約束出現(xiàn)，x為約束變?cè)狟(x)中不是約束出現(xiàn)的其他個(gè)體變?cè)Q為自由出現(xiàn)，這些變?cè)Q為自由變?cè)s束變?cè)c自由變?cè)_定量詞的轄域：若量詞后面有括號(hào)則括號(hào)內(nèi)的子公式就是該量詞的轄域若量詞后面無(wú)括號(hào)則與量詞鄰接的子公式就是該量詞的轄域約束變?cè)c自由變

18、元例2.3 指出下面合式公式的量詞轄域、個(gè)體變?cè)募s束出現(xiàn)和自由出現(xiàn)(x) ( P(x) (y) Q(x, y) )(x)的轄域是( P(x) (y) Q(x, y) )其中x和y都是約束出現(xiàn)(y)的轄域是Q(x, y)其中x是自由出現(xiàn)，y是約束出現(xiàn)對(duì)應(yīng)整個(gè)公式來(lái)說(shuō)，x約束出現(xiàn)1次，自由出現(xiàn)1次，y約束出現(xiàn)2次約束變?cè)c自由變?cè)?x) H(x) L (x, y)(x)的轄域是H(x)其中x是約束出現(xiàn)對(duì)于整個(gè)公式而言，x約束出現(xiàn)1次，自由出現(xiàn)1次，y自由出現(xiàn)1次約束變?cè)c自由變?cè)?x) (y)(P(x, y) Q (y, z) (x) R (x, y)(x)的轄域是(y)(P(x, y) Q (

19、y, z)其中x和y是約束出現(xiàn)，z為自由出現(xiàn)(y)的轄域是 (P(x, y) Q (y, z)其中x和z是自由出現(xiàn)，y為約束出現(xiàn)(x)的轄域是R(x, y)其中x是約束出現(xiàn)，y是自由出現(xiàn)對(duì)于整個(gè)公式而言，x和y既為約束出現(xiàn)又為自由出現(xiàn)，z為自由出現(xiàn)約束變?cè)c自由變?cè)粋€(gè)公式的約束變?cè)褂玫拿Q符號(hào)是無(wú)關(guān)緊要的。故： (x) P(x) 與(y) P(y) 具有相同的意義。設(shè)A（x）表示x不小于0，那么：(x) A(x)表示一切x都使得x不小于0(y) A(y)表示一切y都使得y不小于0(z) A(z)表示一切z都使得z不小于0這三個(gè)命題在實(shí)數(shù)域中都表示假命題“一切實(shí)數(shù)均不小于0”；同理(x)P(x) 與(y)P(y)的意義亦相同。為此：我們可以對(duì)公式中的約束變?cè)拿Q符號(hào)，這種遵守一定規(guī)則的更改，稱為約束變?cè)母拿＜s束變?cè)c自由變?cè)獮榱吮苊鈧€(gè)體變?cè)茸鳛榧s束變?cè)?，又作為自由變?cè)霈F(xiàn)代來(lái)的混亂，引入以下兩個(gè)規(guī)則：約束變?cè)拿?guī)則：將量詞轄域中的某個(gè)約束出現(xiàn)的個(gè)體變?cè)约跋鄳?yīng)的指導(dǎo)變?cè)?，改名為本轄域中未曾出現(xiàn)過(guò)的個(gè)體變?cè)ㄗ詈檬枪街袥](méi)有出現(xiàn)過(guò)的個(gè)體變?cè)?，其他不變。目的：使得一個(gè)變?cè)谝粋€(gè)公式中只呈一種形式出現(xiàn)（呈自由出現(xiàn)或呈約束出現(xiàn)）約束變?cè)c自由變?cè)?.4