離散數(shù)學(xué)：第二章 謂詞邏輯

第二章謂詞邏輯用命題邏輯表示，則有P，Q|—R。但(P∧Q)→R并不是永真式，故上述推理形式是錯(cuò)誤的。在命題邏輯中，研究以原子命題為基本單位的復(fù)合命題之間的邏輯關(guān)系和推理。例如，著名的亞里士多德三段論蘇格拉底推理：

P：所有的人都會(huì)死的，

Q：蘇格拉底是人，

R：所以蘇格拉底會(huì)死的。錯(cuò)誤的原因：各命題的邏輯關(guān)系不是體現(xiàn)在原子命題之間，而是體現(xiàn)在構(gòu)成原子命題的內(nèi)部成分之間，即體現(xiàn)在命題結(jié)構(gòu)的更深層次上。前一章介紹的命題與命題演算是命題邏輯的內(nèi)容，其基本組成單位是原子命題。原子命題作為具有真假意義的陳述句至少是由主語和謂語兩部分組成。例如，電子商務(wù)是計(jì)算機(jī)技術(shù)的一個(gè)應(yīng)用系統(tǒng)。在這里“電子商務(wù)”是主語，而“是……”是謂語。當(dāng)主語改變?yōu)椤半娮诱?wù)”時(shí)就得到新的原子命題：電子政務(wù)是計(jì)算機(jī)技術(shù)的一個(gè)應(yīng)用系統(tǒng)。謂詞邏輯是對(duì)原子命題作進(jìn)一步分析，分析出其中個(gè)體詞、謂詞和量詞，研究它們形式結(jié)構(gòu)的邏輯關(guān)系，正確的推理形式和規(guī)則。定義2.1.1

在原子命題中，所描述的對(duì)象稱為個(gè)體；用以描述個(gè)體的性質(zhì)或個(gè)體間關(guān)系的部分，稱為謂詞。個(gè)體是指可以獨(dú)立存在的事物，它可以是具體的，也可以是抽象的。個(gè)體常元表示特定的個(gè)體，以a，b，c…或帶下標(biāo)的ai，bi，ci…表示；個(gè)體變?cè)硎静淮_定的個(gè)體，以x，y，z…或xi，yi，zi…表示。謂詞，當(dāng)與一個(gè)個(gè)體相聯(lián)系時(shí)，它刻劃了個(gè)體性質(zhì)；當(dāng)與兩個(gè)或兩個(gè)以上個(gè)體相聯(lián)系時(shí)，它刻劃了個(gè)體之間的關(guān)系。謂詞常元表示特定謂詞；謂詞變?cè)硎静淮_定的謂詞；都用大寫英文字母，如P，Q，R，…，或其帶上、下標(biāo)來表示。2.1謂詞邏輯中基本概念與表示一、個(gè)體、謂詞和命題的謂詞形式例子：張三是一個(gè)大學(xué)生，李四是一個(gè)大學(xué)生。這兩個(gè)命題可用不同符號(hào)P,Q表示，但P,Q的謂詞有同樣的屬性：“是一個(gè)大學(xué)生”。因此引入一個(gè)符號(hào)表示“是一個(gè)大學(xué)生”，再引入一種方法表示客體的名稱，這樣就能把“是一個(gè)大學(xué)生”這個(gè)命題的本質(zhì)屬性刻劃出來。（a）他是三好學(xué)生。謂詞指明客體性質(zhì)（b）7是質(zhì)數(shù)。（c）每天早晨做廣播操是好習(xí)慣。（d）5大于3。謂詞指明客體聯(lián)系（e）哥白尼指出地球繞著太陽轉(zhuǎn)。命題的謂詞形式定義2.1.2

一個(gè)原子命題用一個(gè)謂詞(如P)和n個(gè)有次序的個(gè)體常元(如a1，a2，…，an)表示成P(a1，a2，…，an)，稱它為該原子命題的謂詞形式或命題的謂詞形式。命題的謂詞形式的約定：

(a)對(duì)給定命題，小寫字母表示個(gè)體，大寫字母表示謂詞，規(guī)定把小寫

字母寫在大寫字母右側(cè)的圓括號(hào)()內(nèi)。

(b)命題的謂詞形式中的個(gè)體出現(xiàn)的次序影響命題的真值，不得隨意變動(dòng)，否則真值會(huì)有變化。

(c)用謂詞表達(dá)命題，必須包括客體和謂詞兩部分。例如：

“張三是一個(gè)大學(xué)生”

表示客體的性質(zhì)，可以表達(dá)為A(b)，

其中

謂詞A：“是一個(gè)大學(xué)生”，b:張三。

“a是小于b”表示兩個(gè)客體之間關(guān)系，表達(dá)為B(a,b),

其中謂詞B:“是小于”。

“點(diǎn)a在b與c之間”表示兩個(gè)客體之間關(guān)系，表達(dá)為L(zhǎng)(a,b,c)，其中謂詞L：“…在…和…之間”

。二、原子謂詞定義2.1.3

由一個(gè)謂詞(如P)和n

個(gè)個(gè)體變?cè)?x1，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元謂詞不是命題，只有當(dāng)其中的個(gè)體變?cè)锰囟▊€(gè)體或個(gè)體常元替代時(shí)，才能成為一個(gè)命題。論域把一個(gè)n元謂詞中的每個(gè)個(gè)體的論域綜合在一起作為它的論域，稱為n元謂詞的全總論域。當(dāng)一個(gè)命題沒有指明論域時(shí)，把全總論域作為其論域。采用一個(gè)謂詞如P(x)來限制個(gè)體變?cè)獂的取值范圍，并把P(x)稱為特性謂詞。n元謂詞中的每個(gè)個(gè)體變?cè)谀男┱撚蛉√囟ǖ闹担瑢?duì)命題的真值極有影響。例如：S(x)：x是大學(xué)生若x的論域?yàn)槟炒髮W(xué)計(jì)算機(jī)系全體同學(xué)，則S(x)為真。若x的論域?yàn)槟持袑W(xué)的全體同學(xué)，則S(x)為假。若x的論域?yàn)槟硠?chǎng)中的觀眾，則S(x)的真值不確定。由一個(gè)或者n個(gè)簡(jiǎn)單命題函數(shù)以及邏輯聯(lián)結(jié)詞組合而成的表達(dá)式稱為復(fù)合命題函數(shù)。邏輯聯(lián)結(jié)詞┐，

∧，∨，→和的意義與命題演算中的解釋類同。例2：H(x,y)：x比y長(zhǎng)得高；l：李四；c：張三；則┐H(l,c)：李四不比張三長(zhǎng)得高；

┐H(l,c)∧┐H(c,l)：李四不比張三長(zhǎng)得高且張三也不比李四長(zhǎng)得高，即張三和李四同樣高；

例1：S(x)：x

學(xué)習(xí)很好；W(x)：x

工作很好；則┐S(x)：x學(xué)習(xí)不是很好；

S(x)∧

W(x)：x的學(xué)習(xí)和工作都很好；

S(x)→W(x)：若x的學(xué)習(xí)很好，則x工作得很好；三、量詞利用n元謂詞和它的論域概念，有時(shí)不能用符號(hào)來準(zhǔn)確表達(dá)某些命題。為避免理解上的歧義，在謂詞邏輯中，引入表示不同數(shù)量的詞，即量詞。量詞是由邏輯學(xué)家Fray引入的，有了量詞后用邏輯符號(hào)表示命題的能力大大加強(qiáng)。

定義2.1.4

①符號(hào)稱為全稱量詞符，用來表達(dá)“對(duì)所有的”、“每一個(gè)”、“對(duì)任何一個(gè)”、“一切”等詞語；

x稱為全稱量詞，稱

x為指導(dǎo)變?cè)?。②符?hào)稱為存在量詞符，用來表達(dá)“存在一些”、“至少有一個(gè)”、“對(duì)于一些”、“某個(gè)”等詞語；

x

稱為存在量詞，稱

x為指導(dǎo)變?cè)?。③符?hào)!

稱為存在惟一量詞符，用來表達(dá)“恰有一個(gè)”、“存在惟一”等詞語；

!x稱為存在惟一量詞，稱x為指導(dǎo)變?cè)?/p>

。解：令M(x):x是人；H(x):x要呼吸。

(x)(M

(x)→H(x))②每個(gè)學(xué)生都要參加考試；解：令P(x):x是學(xué)生；Q(x):x要參加考試。

(x)(P

(x)→Q(x))③任何整數(shù)或是正的或是負(fù)的；解：令I(lǐng)(x):x是整數(shù)；R(x):x是正數(shù)；N(x):x是負(fù)數(shù)。

(x)(I(x)→(R

(x)∨N(x))例1：試用量詞、謂詞表示命題：①所有的人都是要呼吸的；例2：試用量詞、謂詞表示命題：①存在一個(gè)數(shù)是質(zhì)數(shù)；解令P(x):x是質(zhì)數(shù)；

(

x)(P

(x))②一些人是聰明的。解令M(x):x是人；R(x):x是聰明的。

(

x)(M

(x)∧R(x))③有些人早飯吃面包。解令M(x):x是人；E(x):x早飯吃面包。

(x)(M

(x)∧E(x))例3：試用量詞、謂詞表示命題：①所有大學(xué)生都熱愛祖國；解令S(x):x是大學(xué)生；L(x):x熱愛祖國。

(x)(S

(x)→L(x))②每個(gè)自然數(shù)都是實(shí)數(shù)解令N(x):x是自然數(shù)；R(x):x是實(shí)數(shù)。

(x)(N

(x)→R(x))③一些大學(xué)生有遠(yuǎn)大理想；解令S(x):x是大學(xué)生；I(x):x有遠(yuǎn)大理想。

(x)(S

(x)∧I(x))④有的自然數(shù)是素?cái)?shù)解令N(x):x是自然數(shù)；P(x):x是素?cái)?shù)。

(x)(N

(x)∧P(x))規(guī)律全稱量詞后跟一個(gè)條件式，特性謂詞作為其前件出現(xiàn)；存在量詞后跟一個(gè)合取式，特性謂詞作為一個(gè)合取項(xiàng)出現(xiàn)。若指明了論域，則不需要特性謂詞。(x)L

(x)，(x)R

(x)(x)I

(x)，(x)P

(x)謂詞前加上了量詞，稱為謂詞的量化。若一個(gè)謂詞中所有個(gè)體變?cè)剂炕?，則該謂詞就變成了命題。在謂詞被量化后，可以在整個(gè)個(gè)體域中考慮命題的真值。一、謂詞公式定義2.2.1

項(xiàng)由下列規(guī)則形成：①個(gè)體常元和個(gè)體變?cè)琼?xiàng)；②若f

是n元函數(shù)，且t1，t2，…，tn

是項(xiàng)，則f(t1，t2，…，tn)是項(xiàng)；③所有項(xiàng)都是有限次的使用①和②生成。2.2謂詞公式與翻譯為了方便處理數(shù)學(xué)和計(jì)算機(jī)科學(xué)的邏輯問題及謂詞表示的直覺清晰性，引進(jìn)項(xiàng)的概念。例1：令f(x,y)表示x+y,謂詞N(x)表示x是自然數(shù)。則f(2,3)表示個(gè)體自然數(shù)5，N(f(2,3))表示5是自然數(shù)。有了項(xiàng)的定義、函數(shù)的概念就可用來表示個(gè)體常元和變?cè)?/p>

函數(shù)的使用給謂詞表示帶來很大方便。例2：P(x):x是教授；f(x):x的父親；c:張強(qiáng)那么P(f(c))表示“張強(qiáng)的父親是教授”這一命題。例3：用謂詞表示命題：對(duì)任意整數(shù)x,x2-1=(x+1)(x-1)。解：令I(lǐng)(x)是整數(shù)，f(x)=x2-1,g(x)=(x+1)(x-1),E(x,y):x=y。則該命題可表示成：(

x)(I(x)→

E(f(x),g(x)))定義2.2.2

若P(x1，x2，…，xn)是n元謂詞，t1，t2，…，tn是項(xiàng)，則稱P(t1，t2，…，tn)為原子謂詞公式，簡(jiǎn)稱原子公式。定義2.2.3

合式謂詞公式當(dāng)且僅當(dāng)由下列規(guī)則形成的符號(hào)串：①原子公式是合式謂詞公式；②若A是合式謂詞公式，則(┐A)是合式謂詞公式；③若A，B是合式謂詞公式，則(A∧B)，(A∨B)，(A→B)和(A

B)都是合式謂詞公式；④若A是合式謂詞公式，x是個(gè)體變?cè)瑒t(x)A、(x)A都是合式謂詞公式；⑤僅有有限項(xiàng)次使用①、②、③和④形成的才是合式謂詞公式。合式謂詞公式是按上述規(guī)則由原子公式、聯(lián)結(jié)詞、量詞、圓括號(hào)和逗號(hào)組成的符號(hào)串，而且命題公式是它的一個(gè)特例。例如：(x)P(x)，(x)(P(x)∨R(x))，(x)(y)(P(x,y)→R(y))都是合式謂詞公式；而(x)(P(x)→R(x)，(x)(y)(∧P(x,y))都不是合式謂詞公式。稱合式謂詞公式為謂詞公式；可將合式謂詞公式最外層括號(hào)省略，但量詞后括號(hào)不可省略。二、謂詞邏輯的翻譯把一個(gè)文字?jǐn)⑹龅拿}，用謂詞公式表示出來，稱為謂詞邏輯的翻譯或符號(hào)化；①正確理解給定命題。必要時(shí)把命題改敘，使其中每個(gè)原子命題及原子命題之間的關(guān)系能明顯表達(dá)出來。②把每個(gè)原子命題分解成個(gè)體、謂詞和量詞；在全總論域中討論時(shí)，要給出特性謂詞。③找出恰當(dāng)量詞。應(yīng)注意全稱量詞(x)后跟條件式，存在量詞

(x)后跟合取式。④用恰當(dāng)?shù)穆?lián)結(jié)詞把給定命題表示出來。一般說，符號(hào)化的步驟如下：例1：把下列命題符號(hào)化：①張強(qiáng)和李林都是足球運(yùn)動(dòng)員。

②趙越是象棋迷或圍棋迷。

③李林比張強(qiáng)高。

F(x):x是足球運(yùn)動(dòng)員；a:張強(qiáng)；b:李林；

F(a)∧F(b)C(x):x是象棋迷；G(x)：x是圍棋迷；a：趙越

C(a)∨G(a)P(x,y)：x比y高；

a：李林；b：張強(qiáng)；

P(a，b)例2.將命題“沒有最大的自然數(shù)”符號(hào)化解：改敘為：“對(duì)所有的自然數(shù)x，如果x是自然數(shù)，則一定存在y,y也是自然數(shù)，并且y比x大。”令N(x):x是自然數(shù)；G(x，y)：x比y大；則原命題表示為：(x)(N(x)→(y)(N

(y)∧G(y，x)))例3.將“今天有雨雪，有些人會(huì)跌跤”符號(hào)化解：改敘“若今天下雨又下雪，則存在x,x是人且x會(huì)跌跤”

令

R:今天有雨；S:今天有雪；

M(x):x是人；F(x):x會(huì)摔跤；則本語句可表示為：R∧S→(x)(M

(x)∧F(x))例4.用謂詞表示命題“張強(qiáng)把一本新買到的離散數(shù)學(xué)書送給了李林?！苯猓毫頝(x):x是新的；B(x):x是買的；

G(x，y，z):x把y給了z；

a:張強(qiáng)；b：李林；c:離散數(shù)學(xué)書則原命題可表示成：

G(a，c，b)∧N(c)

∧B(c)若令P(x):x是新買到的；則原命題可表示成：G(a，c，b)∧P(c)這里給出了兩種不完全相同的符號(hào)化形式，表示了對(duì)命題描述的深刻程度不同，前者細(xì)微一些，后者粗糙一些。例5.人都要犯錯(cuò)誤。例6.李濤無書不讀。解：該命題可說成“對(duì)所有的x,如果x是人,則x要犯錯(cuò)誤”。設(shè)

H(x):x是人。

Q(x):x犯錯(cuò)誤。則命題可表示為(x)

(H(x)→Q(x))。此命題等價(jià)于“沒有不犯錯(cuò)誤的人”

則命題還可表示為┐(x)

(H(x)∧┐Q(x))解：該命題即是說“李濤所有的書都讀”。設(shè)P(x):x是書。Q(x,y):x讀y。a:李濤。則命題可表示為：(x)(P(x)→Q

(a,x))。例8.如果b2－4ac≥0,則實(shí)系數(shù)一元二次方程

ax2＋bx＋c＝0有實(shí)數(shù)解。例7.有些人聰明，但不是所有的人都聰明。解設(shè)H(x):x是人；B(x):x聰明。則命題可表示為：

(x)(H(x)∧B(x))∧┐((x

)(H(x)→B(x)))。解：設(shè)R(x):x是實(shí)數(shù),并將數(shù)學(xué)中的運(yùn)算符“＝”、“≠”、“＞”、“≥”等作謂詞使用,則命題可表示為：

R(a)∧R(b)∧R(c)∧(b2－4ac≥0)→(x)(R(x)∧(ax2＋bx＋c＝0))一、約束變?cè)c自由變?cè)x2.3.1

給定一個(gè)謂詞公式A，其中有一部分公式形如(x)B

(x)或(x)B

(x)，則稱它為A的x約束部分，稱B(x)為相應(yīng)量詞的作用域或轄域。轄域中，x的所有出現(xiàn)稱為約束出現(xiàn)，x稱為約束變?cè)籅中不是約束出現(xiàn)的其它個(gè)體變?cè)某霈F(xiàn)稱為自由出現(xiàn)，這些個(gè)體變?cè)Q為自由變?cè)?.3、約束變?cè)c自由變?cè)偃袅吭~后有括號(hào)，則括號(hào)內(nèi)的子公式就是該量詞的轄域；②若量詞后無括號(hào)，則與量詞鄰接的子公式為該量詞的轄域。確定量詞的轄域:例1指出下列各合式公式中的量詞轄域、個(gè)體變?cè)募s束出現(xiàn)和自由出現(xiàn)。①(x)(P(x)(y)Q(x，y))②(x)H(x)∧L(x，y)③(x)(y)(P(x，y)∨Q(y，z))∧(x)R(x，y)解：①(x)的轄域是(P(x)(y)Q(x,y))；(y)的轄域是Q(x,y)；

對(duì)于(y)的轄域而言，y為約束出現(xiàn)，x為自由出現(xiàn)；

對(duì)于(x)的轄域而言，x和y均為約束出現(xiàn)，x約束出現(xiàn)2次，

y約束出現(xiàn)1次。②(x)的轄域是H(x)，x為約束出現(xiàn)，L(x，y)中的x和y都是自由出現(xiàn)；

對(duì)于整個(gè)公式，x約束出現(xiàn)一次，自由出現(xiàn)一次，y自由出現(xiàn)一次。解：(x)的轄域?yàn)?y)(P(x,y)∨Q(y,z))；(y)的轄域?yàn)镻(x,y)∨Q(y,z)；

(x)的轄域?yàn)镽(x，y);

在(x)的轄域中，x和y為約束出現(xiàn)，z為自由出現(xiàn)；在(y)的轄域中，y為約束出現(xiàn)，x,z為自由出現(xiàn)；在(x)的轄域中，x為約束出現(xiàn)，y為自由出現(xiàn)；整個(gè)公式，

x為約束出現(xiàn)，y為約束出現(xiàn)又為自由出現(xiàn)，z為自由出現(xiàn)③(x)(y)(P(x，y)∨Q(y，z))∧(x)R(x，y)定義2.3.2設(shè)A為任意一個(gè)公式，若A中無自由出現(xiàn)的個(gè)體變?cè)瑒t稱A為封閉的合式公式，簡(jiǎn)稱閉式。若A中無約束變?cè)霈F(xiàn)，則稱A為開放公式，簡(jiǎn)稱開式。由閉式定義可知，閉式中所有個(gè)體變?cè)鶠榧s束出現(xiàn)。例如：(x)(P(x)Q(x))和(x)(y)(P(x)∨Q(x，y))是閉式，P(x)Q(x，y)和L(x，y，z)是開式，(x)(P(x)Q(x，y))和(y)(z)L(x，y，z)既不是閉式，也不是開式。

在一個(gè)公式中，有的個(gè)體變?cè)瓤梢允羌s束出現(xiàn)，又可以是自由出現(xiàn)，容易產(chǎn)生混淆。為了避免混淆，采用下面兩個(gè)規(guī)則：約束變?cè)拿?guī)則，將量詞轄域中某個(gè)約束出現(xiàn)的個(gè)體變?cè)跋鄳?yīng)指導(dǎo)變?cè)某杀据犛蛑形丛霈F(xiàn)過的個(gè)體變?cè)?，其余不變。自由變?cè)胍?guī)則，對(duì)某自由出現(xiàn)的個(gè)體變?cè)捎脗€(gè)體常元或用與原子公式中所有個(gè)體變?cè)煌膫€(gè)體變?cè)ゴ耄姨幪幋?。?.

將公式(x)(P

(x)Q

(x，y))∧R

(x，y)中的約束變?cè)拿＝猓?z)(P

(z)Q

(z，y))∧R

(x，y)(y)(P

(y)Q

(y，y))∧R

(x，y)(z)(P

(z)Q

(x，y))∧R

(x，y)(z)(P

(z)Q

(z，y))∧R

(z，y)xxx例2.

對(duì)公式(x)(P

(y)Q

(x，y))∧R

(x，y)中的自由變?cè)搿?x)(P

(z)Q

(x，z))∧R

(u

，z)(x)(P

(z)Q

(x，z))∧R

(x，y)(x)(P

(x)Q

(x，z))∧R

(x，x)xx解：在(x)的轄域中，y是自由變?cè)?

而在整個(gè)公式中，x與y都是自由變?cè)?，正確的代入是把z代入自由變?cè)獃，得：改名規(guī)則與代入規(guī)則的不同點(diǎn)：①施行的對(duì)象不同。改名是對(duì)約束變?cè)┬校胧菍?duì)自由變?cè)┬?。②施行的范圍不同。改名可以只?duì)公式中一個(gè)量詞及其轄域內(nèi)施行，即只對(duì)公式的一個(gè)子公式施行；而代入必須對(duì)整個(gè)公式同一個(gè)自由變?cè)乃凶杂沙霈F(xiàn)同時(shí)施行，即必須對(duì)整個(gè)公式施行。③施行后的結(jié)果不同。改名后，公式含義不變，因?yàn)榧s束變?cè)桓拿麨榱硪粋€(gè)個(gè)體變?cè)?，約束關(guān)系不改變。約束變?cè)荒芨拿麨閭€(gè)體常元；代入，不僅可用另一個(gè)個(gè)體變?cè)M(jìn)行代入，并且也可用個(gè)體常元去代入，從而使公式由具有普遍意義變成為僅對(duì)該個(gè)體常元有意義，即公式的含義改變了。定義2.3.3

若x1，x2，…，xn是不同個(gè)體變?cè)?，t1，t2，…，tn是項(xiàng)，則稱{x1/t1，x2/t2，…，xn/tn}是代換。

若

t是項(xiàng)，{x1/t1，x2/t2，…，xn/tn}是代換，則t{x1/t1，x2/t2，…，xn/tn}是t1，t2，…，tn分別代替t中x1，x2

，…，xn

的所有出現(xiàn)而得到的項(xiàng)，記為若A為公式，{x1/t1，x2/t2，…，xn/tn}是代換，則A{x1/t1，x2/t2，…，xn/tn}是用t1，t2，…，tn分別代替A中的x1，x2，…，xn的所有自由出現(xiàn)而得到的公式，記為

例3.

設(shè)t是，A是(x)P(x，y)Q(x，y，z)，則是；

而是(x)P(x，z)Q(a，z，x)。定義2.3.4

令A(yù)是任意的合式公式，x為自由出現(xiàn)。如果

x不出現(xiàn)在項(xiàng)t所含的任意個(gè)體變?cè)獃

的量詞(y)或(y)

的轄域內(nèi)，則稱項(xiàng)t

對(duì)A中的x是自由的或可代入的。解：項(xiàng)f(x,w)對(duì)A中的y不是自由的：y出現(xiàn)在了項(xiàng)f(x,w)中的個(gè)體變?cè)獂的量詞(x)的轄域內(nèi).

例1.設(shè)

A為(x)P

(x，y)(z)Q

(x，z)，考察項(xiàng)f(x,w)對(duì)A中的y，項(xiàng)g(y,z)對(duì)A中的y，項(xiàng)h(x,z)對(duì)A中的x，項(xiàng)y對(duì)A中的x是否是自由的？項(xiàng)g(y,z)對(duì)A中的y是自由的：y不出現(xiàn)在項(xiàng)g(y,z)中的個(gè)體變?cè)獄的量詞(z)的轄域內(nèi)。項(xiàng)h(x,z)對(duì)A中的x不是自由的：x出現(xiàn)在了項(xiàng)h(x,z)的個(gè)體變?cè)獂的量詞(x)和個(gè)體變?cè)獄的量詞(z)的轄域內(nèi)。項(xiàng)y對(duì)A中的x是自由的：在公式A中沒有量詞(y)和(y)。解：項(xiàng)g(y,z)對(duì)A中的y是自由的：y不出現(xiàn)在項(xiàng)g(y,z)中的個(gè)體變?cè)獄的量詞(z)的轄域內(nèi)。因此，=(x)P

(x，g(y，z))(z)Q

(x，z)項(xiàng)y對(duì)A中的x是自由的：在公式A中沒有量詞(y)和(y)。因此，=(x)P

(x，y)(z)Q

(y，z)

例1.A為(x)P

(x，y)(z)Q

(x，z)，考察項(xiàng)f(x,w)對(duì)A中的y，項(xiàng)g(y,z)對(duì)A中的y，項(xiàng)h(x,z)對(duì)A中的x，項(xiàng)y對(duì)A中的x是否是自由的？從約束變?cè)母拍羁梢钥闯?，P(x1,x2,……xn)是n元謂詞，它有n個(gè)互相獨(dú)立的自由變?cè)Ｈ魧?duì)其中k個(gè)變?cè)M(jìn)行約束，則成為n-k元謂詞。因此，謂詞公式中如果沒有自由變?cè)霈F(xiàn)，則該式就成為一個(gè)命題。例如，(x)P(x,y,z)是二元謂詞

(z)(x)P(x,y,z)是一元謂詞一個(gè)公式的約束變?cè)褂玫拿Q符號(hào)是無關(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;(t)A(t)表示一切t都使得t不小于0;

這三個(gè)命題在實(shí)數(shù)域中都表示假命題：“一切實(shí)數(shù)均不小于0”。量詞作用域中的約束變?cè)?dāng)論域的元素是有限時(shí)，個(gè)體變?cè)乃锌赡艿娜〈强擅杜e的。設(shè)論域元素為a1,a2,……an，則：

(x)A(x)A(a1)

∧

A(a2)∧……

∧

A(an)(x)A(x)A(a1)∨A(a2)∨……

∨

A(an)例.求下列公式的真值：

(1)(x)(P(x)∨Q(x))，其中P(x)

:x=1,Q(x)

:x=2而且論域是{1,2}。

(2)(x)(P(x)∧Q(x))，其中P(x)

:x=1,Q(x)

:x=2而且論域是{1,2}。

(3)(x)(P→Q(x))∨R(a)，其中

P

:2>1,Q(x)：x<=3,R(x)：x>5,

a:5,

論域是{-2,3,6}。解：

(1)(x)(P(x)∨Q(x))(P(1)∨Q(1))∧(P(2)∨Q(2))

(T∨F)∧(F∨T)T(3)(x)(P→Q(x))∨R(a)(x)(T→Q(x))∨F

(x)(T→Q(x))

(x)(F∨

Q(x))

(x)

Q(x)

Q(-2)∧Q(3)

∧Q(6)

T

∧T

∧F

F(2)(x)(P(x)∧Q(x))

(P(1)∧

Q(1))∨

(P(2)∧

Q(2))

(T∧

F)∨

(F∧

T)F定義2.4.1

謂詞邏輯的一個(gè)解釋I

由下面四部分組成：①非空個(gè)體域DI；②DI

中部分特定元素a′，b′，…；③DI上的一些特定函數(shù)f′，g′，…；④DI上特定謂詞P′，Q′，…。2.4謂詞邏輯的解釋與其賦值

給定一個(gè)文字?jǐn)⑹龅拿}，可以符號(hào)化為謂詞公式。反之，給定一個(gè)謂詞公式，它表達(dá)怎樣的意義？這涉及謂詞邏輯的語義問題。只有對(duì)謂詞公式中的抽象符號(hào)給出解釋和賦值后，公式才有意義，公式可能真或假。解釋是針對(duì)謂詞邏輯中的符號(hào)，其對(duì)應(yīng)關(guān)系如下：①個(gè)體變?cè)獂，y，…在DI

內(nèi)取值；②個(gè)體常元a，b，…被解釋成a′，b′，…；③函數(shù)符號(hào)f，g，…被解釋成f′，g′，…；④謂詞符號(hào)P，Q，…被解釋成P′，Q′，…。

在一個(gè)具體解釋中，個(gè)體常元、函數(shù)符號(hào)和謂詞符號(hào)的數(shù)量一般是有限的，并且其解釋一旦確定就不再改變，只是個(gè)體變?cè)闹翟趥€(gè)體域DI內(nèi)變化，量詞符或僅作用于DI中的元素。例1設(shè)公式為(x)(y)(z)E

(f(x，z)，y)，試說明它在下面解釋中的具體含義。②解釋Q：DQ為正有理數(shù)全體，a

?=1，f?(p,q)=p*q，g?(p,q)=p/

q，E?(p，q):p=q，其中p，q是DQ中的元素。①解釋N：DN為含有0在內(nèi)的全體自然數(shù)，a

?=0,f?(i，j)=i+j，

g?(i，j)=i*j，h?(i)=i+1，E?(i，j)：i=j，其中i，j是DN中的元素。在此解釋下公式的含義為：對(duì)DN中的任意i，j，存在DN中的k，使得i+k=j。真值為F。在此解釋下公式的含義為：對(duì)DQ中的任意i，j，存在DQ中的k，使得i*k=j。

真值為T。賦值定義2.4.2

解釋I中的一個(gè)賦值是一個(gè)從項(xiàng)的全體到DI

的具有下列性質(zhì)的函數(shù)v，使得：①對(duì)任意個(gè)體常元a，有v(a)=a′。②v(f(t1，t2，…，tn))=f?(v(t1)，v(t2)，…，v(tn))，其中f為n元函數(shù)，t1，t2，…，tn為任意項(xiàng)。賦值提供了對(duì)每個(gè)項(xiàng)指派D中元素作為它的解釋的一個(gè)規(guī)則。在給定解釋中存在不同的賦值，并且當(dāng)一個(gè)賦值v對(duì)所有個(gè)體變?cè)闹荡_定后，則任意項(xiàng)的值也就確定了。例2.

在例1的解釋N中，設(shè)公式為(x)(y)(z)E

(f(x，z)，y)解釋N：DN為含有0在內(nèi)的全體自然數(shù)，a

?=0,

f?(i，j)=i+j，g?(i，j)=i*j，h?(i)=i+1，

E?(i，j)：i=j，其中i，j是DN中的元素。令賦值v

是：v(x)=i,v(y)=j,v(z)=k,……,

其中i,j,k,…是DN中的元素。于是

v(f(x,y))=f?(v(x)，v(y))=i+j，

v(g(x,y))=g?(v(x)，v(y))=i*j，

v(h(x))=h?(v(x))=i+1，

……….

以此類推，可以得到在解釋I中各項(xiàng)在賦值下的值。定義2.4.3

在一個(gè)解釋I中，稱v和v′是幾乎等同賦值或者

x-等同賦值，如果對(duì)任意元素y,

有v(y)=v?(y)，其中y≠x.由定義可知，若v和v?

是x-等同賦值，那么它們除了在x處可能不等，對(duì)其余個(gè)體變?cè)加邢嗤闹?。?duì)于x,它們的賦值也是可以相同的，因此一個(gè)賦值v總是與自己是x-等同賦值。如果一個(gè)賦值使某公式為真，則稱該賦值滿足本公式。例如，在解釋N中，令v(x)=i,v(y)=j，其中i,j為DN中元素，則有：公式E(f(x,y),f(x,y))的意義是：i+j=i+j,這是真命題，也即是說賦值v滿足本公式;

公式E(f(x,y),g(x,y))的意義是：i+j=i*j,這是假命題，也即是說賦值v不滿足本公式。解釋N：DN為含有0在內(nèi)的全體自然數(shù)，a

?=0,

f?(i，j)=i+j，g?(i，j)=i*j，h?(i)=i+1，

E?(i，j)：i=j，其中i，j是DN中的元素。①v滿足原子公式P(t1,t2,…,tn),如果P?(v(t1),v(t2),…,v(tn))在I

中為真；②v滿足┐B，如果v不滿足B；③v滿足B∧C，如果v滿足B也滿足C；④v滿足B∨C，如果或者v滿足B或者v滿足C；⑤v滿足B→C，如果或者v滿足┐B或者滿足C；⑥v滿足BC，如果v滿足B→C且也滿足C→B；

⑦v滿足(x)A，如果對(duì)于任意與v是x-等同賦值的v?,均有v?滿足A；

⑧v滿足(x)A，如果存在一個(gè)與v是x-等同賦值的v?，有v?滿足A；定義2.4.4

令A(yù)是謂詞邏輯的公式，I是謂詞邏輯的一個(gè)解釋，稱I中的賦值v滿足A，是指以下八條歸納地成立：在解釋I中，對(duì)任何公式A，賦值v或者滿足A或者不滿足A，二者必居其一。①E(g(x,y),g(z,w))；②(x)(E(x,y)→E(y,x))；③(x)E(x,a)；④(x)

E(x,y).例2.4.2

在解釋N中，討論賦值是否滿足下列公式：解釋N：DN為含有0在內(nèi)的全體自然數(shù)，a?=0,f?(i,j)=i+j,g?(i,j)=i*j，h?(i)=i+1，E?(i,j)：i=j，其中i，j是DN中的元素。解：①在解釋N中，凡是使v(x)*v(y)=v(z)*v(w)成立的賦值v

都滿足公式E(g(x,y),g(z,w)),否則不滿足。例如，令v1(x)=1,v1(y)=2,v1(z)=2,v1(w)=1,1*2=2*1成立，

則v1滿足公式

E(g(x,y),g(z,w))；令v2(x)=1,v2(y)=2,v2(z)=2,v2(w)=2,由于1*2≠2*2,

則v2不滿足公式E(g(x,y),g(z,w))。解：②

(x)(E(x,y)→E(y,x))(x)(┐E(x,y)∨E(y,x))

.

在解釋N中，令賦值v1為v1(x)=1,v1(y)=2，則由于1≠2，即v1不滿足E(x,y),

于是v1滿足┐E(x,y)，即v1滿足┐E(x,y)∨E(y,x)

故v1滿足E(x,y)→E(y,x)。

所有與v1是x-等同賦值的v1?僅在x處和v1的賦值可能有所不同。而這些v1?或者滿足┐E(x,y)(當(dāng)v1?(x)≠2，v1?(y)=2時(shí))，或者滿足E(y,x)(當(dāng)v1?(x)=2，v1?(y)=2時(shí))。所以v1?滿足┐E(x,y)∨E(y,x)

，即

v1?滿足E(x,y)→E(y,x)。依定義知，v1滿足公式(x)(E(x,y)→E(y,x))。進(jìn)一步分析，可得N中每個(gè)賦值v都滿足這個(gè)公式。例2.4.2

在解釋N中，討論賦值是否滿足下列公式：解釋N：DN為含有0在內(nèi)的全體自然數(shù)，a?=0,f?(i,j)=i+j,g?(i,j)=i*j，h?(i)=i+1，E?(i,j)：i=j，其中i，j是DN中的元素。解：③(x)E(x,a).

在解釋N中，令賦值v1,v1(x)=0,而v(a)=0，則v1滿足E(x,a)。取與v1是x-等同賦值的v1?,v1?(x)=1,則v1?不滿足E(x,a)。可見v1不滿足公式(x)E(x,a).

進(jìn)一步分析，可得N中任何賦值v都不滿足該公式。④(x)E(x,y).

在解釋N中，令賦值v1,v1(x)=1,v1(y)=2,知v1不滿足E(x,y)。若取與v1是x-等同賦值的v1?,使v1?(x)=2,v1?(y)=2,則v1?滿足E(x,y)。根據(jù)定義知，v1滿足公式(x)E(x,y)。因此，N中任何賦值v都滿足本公式。例2.4.2

在解釋N中，討論賦值是否滿足下列公式：解釋N：DN為含有0在內(nèi)的全體自然數(shù)，a?=0,f?(i,j)=i+j,g?(i,j)=i*j，h?(i)=i+1，E?(i,j)：i=j，其中i，j是DN中的元素。定義2.5.1如果在解釋I中每個(gè)賦值v都滿足公式A，則A在解釋I中稱為真；如果不存在在I中滿足A的任何賦值，則A在解釋I中稱為假。前者記作I|=A，后者記作I|=┐A。2.5真與邏輯有效由定義知，對(duì)一個(gè)特殊公式A，若I中有些賦值滿足A，有些賦值不滿足A，則該公式在I中既不永真也不永假。根據(jù)賦值和真的定義，可以推知：在給定解釋中，一個(gè)公式A是假，當(dāng)且僅當(dāng)┐A是真。故不存在公式A，使得A和┐A在I中都真。證明：令v是I

中任意賦值。由已知條件知，v滿足A和(A→B)。再由滿足定義，v或者滿足┐A或者滿足B；又知v滿足A，也即v不滿足┐A。因此，v必須滿足B.

由于v的任意性，則有I|=B。定理2.5.1

若I|=A∧(A→B)，則I|=B。定理2.5.2

I|=┐(A→B)當(dāng)且僅當(dāng)I|=A且I|=┐B。證明：必要性：設(shè)I|=┐(A→B)

A∧┐B

。

v是I

中任意賦值，于是v不滿足A→B。根據(jù)滿足定義，可知v既不滿足┐A也不滿足B。可見v滿足A且不滿足B。由v的任意性，則I|=A且I|=┐B。充分性：由I|=A且I|=┐B知，在I中每個(gè)賦值都滿足A且滿足┐B。即滿足A∧┐B

┐(A→B)。定理2.5.3

I|=A當(dāng)且僅當(dāng)I|=(x)A，其中x為任意個(gè)體變?cè)ＷC明：必要性：設(shè)I|=A。

v是I

中任意賦值，于是v滿足A。

由于所有賦值都滿足A，因此與v是x-等同賦值的v’也滿足A。根據(jù)滿足定義知，v滿足(x)A。

由v的任意性，可知

I|=(x)A。充分性：設(shè)I|=(x)A。

v是I中任意賦值，v滿足(x)A

。由于v與v自己是x-等同賦值以及滿足定義，可知v滿足A。由v的任意性，有I|=A。推論2.5.1

I|=A當(dāng)且僅當(dāng)I|=(x1)(x2)…(xn)A，其中

x1，x2，…，xn是任意n個(gè)個(gè)體變?cè)?。由定?.5.3得知，在解釋I中，A(x)為真當(dāng)且僅當(dāng)(x)A

為真。這表明，當(dāng)考察有自由變?cè)霈F(xiàn)的公式真或假時(shí)，就有一種表示全稱量詞在此被省略了的意義。

在命題邏輯中有永真式，在謂詞邏輯中也有類似概念，而且兩者之間還有密切的關(guān)系。定義2.5.2

令A(yù)為命題邏輯中的公式，其中出現(xiàn)的命題變?cè)獮镻1，P2，…，Pn。B1，B2，…，Bn是謂詞邏輯中的公式，用Bi(1≤i≤n)處處代入A中的Pi而得到謂詞邏輯中公式A?

，記為，稱A?為A在謂詞邏輯中的代入實(shí)例。若A為永真式，則稱A?為謂詞邏輯的永真式。

例如，(x)A(x)→(x)A(x)是P→P

的代入實(shí)例，并且是謂詞邏輯中的永真式。謂詞邏輯中永真式的性質(zhì)定理2.5.4

謂詞邏輯的永真式在謂詞邏輯的任何解釋I中都為真。定理2.5.5

令I(lǐng)是謂詞邏輯的一個(gè)解釋，A是謂詞邏輯的公式。如果v和w都是賦值，并且對(duì)A中的每個(gè)自由變?cè)獂，有v(x)＝w(x)。那么v滿足A當(dāng)且僅當(dāng)w滿足A。推論2.5.2

如果A是謂詞邏輯中閉式，且I是謂詞邏輯的一個(gè)解釋，則或者I|=A或者I|=┐A。定義2.5.3

謂詞邏輯的一個(gè)公式A稱為邏輯有效的，如果公式A在謂詞邏輯的每個(gè)解釋下都是真；稱A是矛盾的，如果它在每個(gè)解釋下都是假的。前者記為|=A，后者記為|=┐A。

推論由定義2.5.3及定理2.5.4知，謂詞邏輯的永真式都是邏輯有效的。作為定理2.5.1的推論，有：若|=A∧(A→B)，則|=B。即，若公式A和A→B是邏輯有效的，則B也是邏輯有效的。作為定理2.5.3的推論，有：|=A當(dāng)且僅當(dāng)|=(x)A。即，A是邏輯有效的當(dāng)且僅當(dāng)(x)A是邏輯有效的。例1.判斷下列公式是否為邏輯有效：①(x)A→(x)A，其中A為任何公式，x為任意個(gè)體變?cè)?。?x)(y)G(x，y)→(y)(x)G(x，y)解：①本公式是邏輯有效的。令I(lǐng)是謂詞邏輯的任意解釋，v是I中任意賦值。由于(x)A

→(x)A

┐(x)A

∨

(x)A

，

則考慮以下兩種情況：

a.若v不滿足(x)A,則v滿足┐(x)A，即v滿足┐(x)A∨(x)A；b.若v滿足(x)A，則每個(gè)與v是x-等同賦值的v’滿足A。顯然，存在一個(gè)與v是x-等同賦值的v’滿足A，于是v滿足(x)A。故v滿足┐(x)A

∨

(x)A。由I和v的任意性可知，公式┐(x)A

∨

(x)A是邏輯有效的。也即,公式(x)A→(x)A是邏輯有效的。例1.判斷下列公式是否為邏輯有效：②(x)(y)G(x，y)→(y)(x)G(x，y)解：

②(x)(y)G(x，y)→(y)(x)G(x，y)

本公式不是邏輯有效的。只需構(gòu)造一個(gè)解釋及其不滿足此公式的賦值即可。令DI為整數(shù)全體，G(x,y)：x>y。顯然不管是哪個(gè)賦值，閉式(x)(y)G(x,y)在這一解釋下都是真的，而(y)(x)G(x,y)是假的。即：每個(gè)賦值滿足公式前件，不滿足后件。因此不存在賦值滿足給定公式。故它在這個(gè)解釋I下不是真的，從而它不是邏輯有效的。2.6謂詞邏輯中的等價(jià)式定義2.6.1

令A(yù)和B是謂詞邏輯中的公式，若|=A

B，則稱A和B是等價(jià)的，也記為AB。由于永真式都是邏輯有效的，故命題邏輯中的等價(jià)式(即命題定律)在謂詞邏輯中都成立。定理2.6.1

有關(guān)量詞否定的兩個(gè)等價(jià)式：

①┐(x)A(x)┐A②┐(x)A(x)┐A證明①┐(x)A(x)┐A。令I(lǐng)為任意解釋，v為I中任意賦值。再證v滿足(x)┐A→┐(x)A

┐(x)

┐A∨┐(x)A.分兩種情況討論:

a.若v滿足┐(x)┐A,

則v滿足┐(x)┐A∨┐(x)A，即v滿足(x)┐A→┐(x)A;

先證v滿足┐(x)A→(x)┐A

(x)A∨(x)┐A.分兩種情況討論:

a.若v滿足(x)A,則v滿足(x)A∨(x)┐A，即v滿足┐(x)A→(x)┐A;

根據(jù)滿足的定義知，v滿足公式┐(x)A(x)┐A

。由I和v的任意性知，┐(x)A(x)┐A是邏輯有效的，即┐(x)A(x)┐A。b.若v滿足┐(x)A,則v不滿足(x)A，即存在與v是x-等同賦值的v?不滿足A,

于是v?滿足┐A，也即是存在與v是x-等同賦值的v?滿足┐A，即v滿足(x)┐A.

則v滿足(x)A∨(x)┐A，即v

滿足┐(x)A→(x)┐A。

b.若v不滿足┐(x)┐A,則v滿足(x)┐A,則存在與v是x-等同賦值的v?滿足┐A，

即v?不滿足A,

于是v不滿足(x)A,即v滿足┐(x)A,則v滿足(x)┐A→┐(x)A.

對(duì)于多重量詞前置┐，可反復(fù)應(yīng)用該定理，將逐次右移。

例如：┐(x)(y)(z)P(x，y，z)(x)(y)(z)┐P(x，y，z)定理2.6.2

有關(guān)量詞轄域縮小或擴(kuò)大的兩組八個(gè)等價(jià)式。令B為沒有x出現(xiàn)的公式，A(x)為有x自由出現(xiàn)的公式，則有：

①(x)(A(x)∨B)(x)A(x)∨B②(x)(A(x)∧B)(x)A(x)∧B③(x)(A(x)→B)(x)A(x)→B(x)(A(x)→B)(x)(┐A(x)∨B)(x)┐A(x)∨B┐(x)A(x)∨B(x)A(x)→B

④(x)(B→A(x))B→(x)A(x)⑤(x)(A(x)∨B)(x)A(x)∨B⑥(x)(A(x)∧B)(x)A(x)∧B⑦(x)(A(x)→B)(x)A(x)→B⑧(x)(B→A(x))B→(x)A(x)定理2.6.3

有關(guān)量詞分配律的兩個(gè)等價(jià)式：①(x)(A(x)∧B(x))(x)A(x)∧(x)B(x)②(x)(A(x)∨B(x))(x)A(x)∨(x)B(x)注意：(x)對(duì)∨和(x)對(duì)∧都不滿足分配律，即以下公式不成立：①(x)(A(x)∨B(x))(x)A(x)∨(x)B(x)②(x)(A(x)∧B(x))(x)A(x)∧(x)B(x)令解釋P，Dp為全體素?cái)?shù)；E(x):x為偶數(shù)O(x):x為奇數(shù)①(x)(E(x)∨O(x))：對(duì)于任意素?cái)?shù)x,x是偶數(shù)或者x是奇數(shù)，這個(gè)語句為真；

(x)E(x)∨(x)O(x)：對(duì)所有素?cái)?shù)x都是偶數(shù)，或者所有素?cái)?shù)x都是奇數(shù)，這是假語句。在解釋P中(x)(A(x)∨B(x))(x)A(x)∨(x)B(x)為假，故它不是邏輯有效的。注意：(x)對(duì)∨和(x)對(duì)∧都不滿足分配律，即公式不成立：①(x)(A(x)∨B(x))(x)A(x)∨(x)B(x)②(x)(A(x)∧B(x))(x)A(x)∧(x)B(x)令解釋N，DN為全體自然數(shù)；E(x):x為偶數(shù)O(x):x為奇數(shù)②(x)(E(x)∧O(x))：存在自然數(shù)x,它既是偶數(shù)又是奇數(shù),這是假語句；

(x)E(x)∧(x)O(x)：有些自然數(shù)x是偶數(shù)，并且有些自然數(shù)x是奇數(shù)，這是真語句。在解釋N中(x)(A(x)∧B(x))(x)A(x)∧(x)B(x