2.1謂詞和量詞

2.2謂詞公式

2.3謂詞演算的永真公式

2.4謂詞邏輯的推理理論第2章謂詞邏輯2.1.1謂詞

定義2.1.1

刻畫單個個體的特性或者多個個體間關(guān)系的模式稱為謂詞(predicate)。

通常，一元謂詞用于刻畫個體的特性，由一個表示個體特性的大寫字母(稱為特性謂詞符、一元謂詞符、一元關(guān)系符)和一個個體常元或變元組成的表達式表示，如P(a)、Q(x)等。2.1謂詞和量詞二元謂詞用于刻畫兩個個體之間的關(guān)系，由一個表示兩個個體關(guān)系的大寫字母(稱為二元謂詞符、二元關(guān)系符)和兩個個體常元或變元組成的表達式表示，如Q(a,b)、Q(x，y)、R(a,x)等。

……

n元謂詞用于刻畫n個個體之間的關(guān)系，由一個表示n個個體關(guān)系的大寫字母(稱為n元謂詞符、n元關(guān)系符)和n個個體常元或變元組成的表達式表示，如R(a1,a2,…,an)、R(x1,x2,…,xn)等。

根據(jù)以上約定，謂詞就可以簡單地描述為是由一個謂詞符和若干具有有固定次序的個體常元或變元組成的表達式。帶有n(n≥0)個個體的謂詞稱為n

元謂詞。

例如，“x是偶數(shù)”可以用謂詞P(x)表示，P(2)、P(3)分別表示“2是偶數(shù)”、“3是偶數(shù)”?！皒小于y”可以用謂詞Q(x，y)表示，Q(5，7)、Q(6，5)分別表示“5小于7”、“6小于5”。“x在y和z之間”可以用謂詞R(x,y,z)表示，R(a,b,c)表示“a在b和c之間”。

設(shè)有謂詞P(x1,x2…,xn)，D1，D2，…，Dn是個體域集合，其中x1∈D1，x2∈D2，…，xn∈Dn。n元謂詞P(x1,x2,…,xn)是從D1×D2×…×Dn到集合{T，F(xiàn)}上的一個n元函數(shù)，因此，也把P(x1,x2…,xn)稱做n

元命題函數(shù),如圖2.1.1所示。圖2.1.1有時關(guān)系符直接采用特殊的習慣符號，如=、≠、<、>、≤、≥、、等，其表達方式也可采用中綴表示法，如x≤y、x≠y等。

謂詞也可以用前面介紹的聯(lián)結(jié)詞進行組合，這里聯(lián)結(jié)詞的意義與命題邏輯完全相同。例如，S(x)表示“x是學習委員”，W(x)表示“x是離散數(shù)學課代表”，則S(x)∧W(x)表示“x既是學習委員又是離散數(shù)學課代表”。

從謂詞的定義可以看出，謂詞P(x1,x2…,xn)僅是一個函數(shù)，因此它沒有真假值。若將謂詞符P指定一個確定的n元關(guān)系，每個個體變元均代入相應(yīng)個體域中確定的個體常元，則得到一個具有確定真假值的命題。2.1.2量詞

使用2.1.1節(jié)所講的謂詞還不能很好地表達日常生活中的所有命題，如“所有的人都要呼吸”、“有些有理數(shù)是自然數(shù)”等。為了刻畫這類表示全稱判斷或特稱判斷的命題，需要引入量詞(quantifier)。

1.全稱量詞

x表示“對于所有的x”、“對于任一x”或“對于每一個x”，這里符號稱為全稱量詞(universalquantifier)，x是量詞的作用變元(指導(dǎo)變元)。

2.存在量詞

x表示“存在某個x”或“至少有一個x”，這里符號稱為存在量詞(existentialquantifier)，x是量詞的作用變元(指導(dǎo)變元)。

在謂詞P(x)或Q(x,y)等前面加上全稱量詞或者存在量詞，稱個體變元x被全稱量化或存在量化。對于一個謂詞，如果為謂詞符指定具體含義，為每個個體變元指定論域，則謂詞中的所有變元都被量詞量化，則該命題成為一個具有真假值的命題。如果論域是全總個體域，則(a)“所有的人都是要死的”實際上等價于“對于一切x，如果x是人，那么x是要死的”，各概念間的關(guān)系如圖2.1.3所示，應(yīng)該表示為x(H(x)→

D(x))，而不能表示為x(H(x)∧D(x)),(b)“有些人不怕死”實際上等價于“存在一些x，x是人，并且x不怕死”，各概念間的關(guān)系如圖2.1.3所示，應(yīng)該表示為x(H(x)∧F(x))，而不能表示為x(H(x)→F(x))。圖2.1.2圖2.1.3以上例子中的H(x)是特性謂詞，用以刻畫論述個體是“人”這一特性。特性謂詞的作用是限定論域為一個滿足該謂詞的所有個體構(gòu)成的一個特定的論域。例如，例4中特性謂詞H(x)的作用如圖2.1.4所示。圖2.1.4把特性謂詞加入到公式時，有以下兩條規(guī)則：

規(guī)則1：對于全稱量詞，特性謂詞作為條件式的前件加入；

規(guī)則2：對于存在量詞，特性謂詞作為合取式的合取項加入。

定義2.2.1

謂詞邏輯的合式公式(簡稱謂詞公式)可由下述步驟生成：

(ⅰ)原子公式是謂詞公式。

(ⅱ)如果A和B是謂詞公式，則A、(A∧B)、(A∨B)、(A→B)、(A

B)是謂詞公式。

(ⅲ)如果A是謂詞公式，并且A中有未被量化的個體變元x，則xA(x)和xA(x)是謂詞公式。2.2謂詞公式

(ⅳ)只有有限次應(yīng)用步驟(ⅰ)、(ⅱ)和(ⅲ)所得到的公式才是謂詞公式。

由上述定義可知，任何一個命題公式都是謂詞公式。書寫謂詞公式時，規(guī)定與命題邏輯相同，可以將最外層的括號略去，但緊跟量詞后面的括號不能略去。

需要注意條款(ⅲ)的適用條件，例如，由xP(x,y)可以生成y

xP(x,y)，但是不能生成x

yP(x,y)。

定義2.2.2

若B是謂詞公式A的一個連續(xù)段且B也是謂詞公式，則稱B是A的一個子公式。

在例1中，F(xiàn)(x)、B(y)、G(y,x)、(B(y)∧G(y,x))、

y(B(y)∧G(y,x))、(F(x)→y(B(y)∧G(y,x)))、x(F(x)→

y(B(y)∧G(y,x)))等均為x(F(x)→y(B(y)∧G(y,x)))的子公式。

下面舉例說明如何用謂詞公式表示自然語言表達的命題。約束變元的換名規(guī)則如下：

(1)對某個約束變元換名時，需對量詞的作用變元以及該量詞轄域內(nèi)所有受該量詞約束的約束變元一起換名。

(2)換名后的變元符號應(yīng)是量詞轄域內(nèi)未出現(xiàn)的符號，最好是整個公式中未出現(xiàn)的符號。2.3.1謂詞公式的賦值

謂詞公式中通常包括謂詞符、個體變元、個體常元、命題變元和聯(lián)結(jié)詞。2.3謂詞演算的永真公式

定義2.3.1

對于一個謂詞公式，若給它指定一個個體域E，再給所有謂詞符均指派出確定的關(guān)系(具體的特性或關(guān)系)，給所有命題變元指派出確定命題(或者指定T或F)，并為所有自由變元分別指派E上確定的個體，則稱為對謂詞公式的一個賦值(指派或結(jié)識)。

謂詞公式經(jīng)過賦值之后就變成了具有確定真值的命題。

定義2.3.2

設(shè)A是謂詞公式，如果對于特定論域E上的任何賦值，A的真值都為真，則稱謂詞公式A在E上永真；如果對于特定論域E上的任何賦值，A的真值都為假，則稱謂詞公式A在E上永假；若特定論域E上存在一種賦值，使得A的真值都為真，則稱謂詞公式A在E上可滿足。

定義2.3.3

設(shè)A是謂詞公式，如果對于任何賦值，A的真值都為真，則稱謂詞公式A是永真式；如果對于任何賦值，A的真值都為假，則稱謂詞公式A是永假式；若存在一種賦值，使得A的真值為真，則稱謂詞公式A是可滿足式。

由定義可知，對于任意謂詞公式A，若A是永真式，則A在特定論域E上永真；若A是永假式，則A在特定論域E上永假；若A在特定論域E上可滿足，則A是可滿足式。

構(gòu)造謂詞公式P(x)∧xP(x)的真值表，見表2.3.1。表2.3.1

定義2.3.4

給定任意兩個謂詞公式A和B，若對于任何賦值，A和B的真值均相同，則稱謂詞公式A和B等價，記為A

B。

定義2.3.5

給定任意兩個謂詞公式A和B，若A→B是永真式，則稱A蘊含B，記為A

B。

類似于命題邏輯，對于謂詞公式A、B、C，有如下結(jié)論：

(1)A

B當且僅當A

B是重言式；

(2)A

B當且僅當A

B且B

A；

(3)A

B且B

C，則A

C；

(4)A

B且B

C，則A

C。2.3.2謂詞演算的基本永真式

1.命題邏輯的等價式和蘊含式在謂詞邏輯中的推廣應(yīng)用

對于命題邏輯中的任一等價公式(蘊含式)，對其應(yīng)用代入規(guī)則，即用謂詞邏輯的任意公式代入命題邏輯等價公式(蘊含式)的某個命題變元，所得結(jié)果是謂詞邏輯的一個等價公式(蘊含式)。

2.量詞的否定律

(1)

(2)

證明

(1)設(shè)論域為D，t是任一賦值。如果t使得

xP(x)為真，則t使得xP(x)為假，即存在個體a∈D，使得P(a)為假，從而有P(a)為真，故有x

P(x)為真。如果t使得xP(x)為假，則t使得xP(x)為真，即對于任一個體a∈D，均有P(a)為真，從而有P(a)為假，故有

x

P(x)為假。綜上所述，xP(x)x

P(x)成立。這里再給出等價公式xP(x)x

P(x)在一個有限論域上的證明。設(shè)有限論域D={a1,a2,…,an}，則有

同理可證(2)。

證畢

3.量詞轄域的擴張與收縮律

證明(5)

證畢

其他留作練習。

4.量詞的分配律

證明

(1)設(shè)t是謂詞公式x(P(x)∧Q(x))的任一賦值,其論域為D。

如果t使得x(P(x)∧Q(x))為真，則對于任一個體a∈D，使得P(a)∧Q(a)為真，即P(a)和Q(a)的真值均為真,從而有xP(x)和xQ(x)均為真，即xP(x)∧xQ(x)為真。

如果t使得x(P(x)∧Q(x))為假，則存在個體a∈D，使得P(a)∧Q(a)為假，即P(a)或Q(a)的真值為假,從而有xP(x)或xQ(x)為假，即xP(x)∧xQ(x)為假。

綜上所述，x(P(x)∧Q(x))xP(x)∧xQ(x)成立。

(5)任給一個賦值t，設(shè)其個體域為D。

假設(shè)在t下，x(P(x)→xQ(x)的真值為F，則xP(x)為T，xQ(x)為F。由xQ(x)為F，得到存在a∈D，使得Q(a)為F，又因為xP(x)為T，有P(a)為T,從而推出P(a)→Q(a)為F，即x(P(x)→Q(x))為F。由否定后件法得到，x(P(x)→Q(x))xP(x)→xQ(x)。

(8)xP(x)→xQ(x)

xP(x)∨xQ(x)

x

P(x)∨xQ(x)

x(

P(x)∨Q(x))

x(P(x)→Q(x))

5.多重量詞律

對于多個量詞的情況，量詞出現(xiàn)的先后次序不能隨意調(diào)換。為了便于說明，這里只討論兩個量詞的情況，其他量詞的使用方法與此類似。

若設(shè)P(x,y)表示x和y是同鄉(xiāng)，x的論域為一班學生，y的論域為二班學生,則x

yP(x,y)表示“一班每個學生和二班每個學生都是同鄉(xiāng)”，y

xP(x,y)表示“二班每個學生和一班每個學生都是同鄉(xiāng)”，二者都表示“一班和二班所有的學生都是同鄉(xiāng)”，含義相同,所以x

yP(x,y)

y

xP(x,y)。

x

yP(x,y)表示“一班的某些學生和二班的某些學生是同鄉(xiāng)”，例如，一班的小明和二班的小強是同鄉(xiāng)，也可以說“二班的某些學生和一班的某些學生是同鄉(xiāng)”，即y

xP(x,y)，所以x

yP(x,y)y

xP(x,y)。

x

yP(x,y)表示“對于一班任意學生，二班至少有一個學生和他是同鄉(xiāng)”，y

xP(x,y)則表示“二班存在某個學生，和一班所有學生是同鄉(xiāng)”。顯然，二者的含義是不同的，如果后者為真，則前者也為真，即y

xP(x,y)x

yP(x,y),但是如果前者為真，后者不一定為真，即x

yP(x,y)y

xP(x,y)，所以二者不等價。對于二元謂詞前置量詞，可以有以下8個等價公式和蘊含公式。其關(guān)系如圖2.3.1所示。

(1)x

yP(x,y)y

xP(x,y)。

(2)x

yP(x,y)y

xP(x,y)。

(3)y

xP(x,y)x

yP(x,y)。

(4)x

yP(x,y)y

xP(x,y)。

(5)y

xP(x,y)x

yP(x,y)。

(6)x

yP(x,y)y

xP(x,y)。

(7)y

xP(x,y)x

yP(x,y)。

(8)x

yP(x,y)y

xP(x,y)。

圖2.3.1謂詞邏輯中常用的等價公式和蘊含公式如表2.