離散數(shù)學(xué)課件

第2章謂詞邏輯

2.1個(gè)體、謂詞與量詞

2.2謂詞公式

2.3謂詞演算的等價(jià)式與蘊(yùn)含式

2.4前束范式

2.5謂詞邏輯的推理理論返回總目錄第2章謂詞邏輯

2.1個(gè)體、謂詞與量詞

2.1.1個(gè)體考察下面的三個(gè)原子命題：

⑴

李玲是優(yōu)秀共產(chǎn)黨員。⑵

張華比李紅高。⑶

小高坐在小王和小劉的中間。上述命題中的李玲、張華、李紅、小高、小王、小劉等客體就是個(gè)體。所以可以這樣說，個(gè)體是指所研究對(duì)象中可以獨(dú)立存在的具體的或抽象的客體。它可以是獨(dú)立存在的人或物體，也可以是抽象的概念，如“馬列主義”，“資本主義”等。個(gè)體常用小寫英文字母或小寫英文字母帶下標(biāo)表示，叫做個(gè)體標(biāo)識(shí)符。

表示具體或特定個(gè)體的標(biāo)識(shí)符稱作個(gè)體常元，一般用小寫英文字母a、b、c、…或這些英文字母帶下標(biāo)表示。例如：李玲、張華、李紅、小高、小王、小劉可如下表示：

a：李玲

b：張華

c：李紅

d：小高

e：小王

f：小劉

a,b,c,d,e,f都是個(gè)體常元。將表示任意個(gè)體或泛指某類個(gè)體的標(biāo)識(shí)符稱為個(gè)體變?cè)?，常表示為x、y、z、…等或這些英文字母帶下標(biāo)。個(gè)體變?cè)淖兓秶Q為個(gè)體域或論域。個(gè)體域可以是有窮集合，也可以是無窮集合，包含任意個(gè)體域的個(gè)體域稱為全總個(gè)體域，它是由宇宙間一切對(duì)象組成的集合。在本書中，如無特別說明，所采用的都是全總個(gè)體域。

2.1.2謂詞在上面的三個(gè)原子命題中，⑴可以分解成為個(gè)體“李玲”和“…是優(yōu)秀共產(chǎn)黨員”兩部分。“…是優(yōu)秀共產(chǎn)黨員”是用來描述個(gè)體“李玲”的性質(zhì)的；⑵可以分解成為個(gè)體“張華”、“李紅”和“…比…高”兩部分?！啊取摺笔怯脕砻枋鰝€(gè)體“張華”和“李紅”的身高關(guān)系的；⑶可以分解成為個(gè)體“小高”、“小王”、“小劉”和“…坐在…和…的中間”兩部分?！啊凇汀闹虚g”是用來描述個(gè)體“小高”、“小王”、“小劉”的位置關(guān)系的。這些刻劃個(gè)體性質(zhì)或幾個(gè)個(gè)體關(guān)系的模式叫做謂詞。謂詞常用大寫英文字母表示，叫做謂詞標(biāo)識(shí)符。例如可以用F，G，H表示上面三個(gè)命題中謂詞：

F：…是優(yōu)秀共產(chǎn)黨員。

G：…比…高。

H：…坐在…和…的中間。

把與一個(gè)個(gè)體相關(guān)聯(lián)的謂詞叫做一元謂詞。F是一元謂詞；把與兩個(gè)個(gè)體相關(guān)聯(lián)的謂詞叫做二元謂詞。G是二元謂詞；把與三個(gè)個(gè)體相關(guān)聯(lián)的謂詞叫做三元謂詞。H是三元謂詞；…。一般的，把與n個(gè)個(gè)體相關(guān)聯(lián)的謂詞叫做n元謂詞。設(shè)F是一元謂詞，a是個(gè)體常元，用F(a)表示個(gè)體常元a具有性質(zhì)F；設(shè)G是二元謂詞，a,b是個(gè)體常元，用G(a,b)表示個(gè)體常元a和b具有關(guān)系G；…

于是上面三個(gè)命題就表示為：

F(a)：李玲是優(yōu)秀共產(chǎn)黨員。

G(b,c)：張華比李紅高。

H(d,e,f)：小高坐在小王和小劉的中間。將謂詞后面填上相關(guān)聯(lián)的個(gè)體常元所得的式子叫做謂詞填式。F(a)，G(b,c)，H(d,e,f)都是謂詞填式。謂詞填式表示的是命題。

類似的，用F(x)表示個(gè)體變?cè)獂具有性質(zhì)F；用G(x,y)表示個(gè)體變?cè)獂和y具有關(guān)系G；…，用P(x1,x2,…,xn)(n≥1)表示個(gè)體變?cè)獂1,x2,…,xn具有關(guān)系P。如果謂詞后面有n個(gè)個(gè)體變?cè)?，則稱為n元命題函數(shù)。例如F(x)、G(x，y)、P(x1,x2,…,xn)分別叫做一元命題函數(shù)、二元命題函數(shù)、n元命題函數(shù)(n≥1)。因?yàn)槊}函數(shù)中包含個(gè)體變?cè)虼嗣}函數(shù)沒有確定的真值，它不是命題。只要用個(gè)體常元取代所有的個(gè)體變?cè)?，就得到了命題。例如，用H(x,y)：x+y≥0，顯然此命題函數(shù)不是命題，因?yàn)樗鼰o法判斷真假。令

a：5,b：－7

用a,b分別取代x,y，就得到H(a,b)，它表示5+(－7)≥0，這是個(gè)假命題，它的真值為假。其實(shí)，用個(gè)體常元取代命題函數(shù)的所有個(gè)體變?cè)玫降谋磉_(dá)式就是前面所說的謂詞填式。因?yàn)樗蓚€(gè)體常元取代命題函數(shù)中所有的個(gè)體變?cè)玫剑砸舶阎^詞填式叫做0元命題函數(shù)。F(a)，G(b,c)，H(d,e,f)都是0元命題函數(shù)，它們都是命題。于是命題邏輯中的命題均可以表示為謂詞邏輯中的0元命題函數(shù)(謂詞填式)，命題成為命題函數(shù)的特例。

【例2.1】將下列命題符號(hào)化，并討論它們的真值。⑴2與3都是偶數(shù)。⑵如果5大于3，則2大于6。解：⑴設(shè)F(x)：x是偶數(shù)。

a：2，b：3

該命題符號(hào)化為：F(a)∧F(b)F(b)表示3是偶數(shù)，它是個(gè)假命題。所以F(a)∧F(b)為假。⑵設(shè)G(x,y)：x大于ya：5，b：3，c：2，d：6

該命題符號(hào)化為：G(a,b)→G(c,d)

G(a,b)表示5大于3，它是真命題。G(c,d)表示2大于6，這是個(gè)假命題。所以G(a,b)→G(c,d)為假。

2.1.3量詞量詞分兩種。⑴

全稱量詞日常生活和數(shù)學(xué)中常用的“一切的”，“所有的”，“每一個(gè)”，“任意的”，“凡”，“都”等詞統(tǒng)稱為全稱量詞，將它們符號(hào)化為“

”。并用(

x)，(

y)等表示個(gè)體域里的所有個(gè)體，而用(

x)F(x)和(

y)G(y)等分別表示個(gè)體域中的所有個(gè)體都有性質(zhì)F和都有性質(zhì)G。⑵存在量詞

“存在”，“有一個(gè)”，“有些”，“至少有一個(gè)”等詞統(tǒng)稱為存在量詞，將它們符號(hào)化為“

”。并用(

x)，(

y)等表示個(gè)體域里有些個(gè)體，而用(

x)F(x)和(

y)G(y)等分別表示在個(gè)體域中存在個(gè)體具有性質(zhì)F和存在個(gè)體具有性質(zhì)G。全稱量詞與存在量詞統(tǒng)稱為量詞?！纠?.2】個(gè)體域是人類集合，對(duì)下列命題符號(hào)化。⑴

凡人要死。⑵

有的人是研究生。解：⑴

令F(x)：x要死。命題“凡人要死?！狈?hào)化為：(

x)F(x)⑵

令G(x)：x是研究生。

命題“有的人是研究生?！狈?hào)化為：(

x)G(x)

在命題函數(shù)前加上量詞(

x)和(

x)分別叫做個(gè)體變?cè)獂被全稱量化和存在量化。一般地說，命題函數(shù)不是命題，如果對(duì)命題函數(shù)中所有命題變?cè)M(jìn)行全稱量化或存在量化，該函數(shù)就變成了命題。這一結(jié)論在例2.2中得到驗(yàn)證。雖然對(duì)命題函數(shù)中所有命題變?cè)M(jìn)行量化后，該命題函數(shù)就變成了命題，但所得命題的真值與個(gè)體域的選定有關(guān)。請(qǐng)看下列例題：

【例2.3】對(duì)下列命題符號(hào)化，并在①，②，③三個(gè)個(gè)體域中考察命題的真值。命題：⑴

所有數(shù)小于5。⑵

至少有一個(gè)數(shù)小于5。個(gè)體域：①

-1，0，1，2，4

②

3，-2，7，8

③

15，20，24

解：設(shè)L(x)：x小于5。⑴

“所有數(shù)小于5?！狈?hào)化為：(

x)L(x)在個(gè)體域①，②，③中，它們的真值分別為：真，假，假。⑵

“至少有一個(gè)數(shù)小于5。”符號(hào)化為：(

x)L(x)在個(gè)體域①，②，③中，它們的真值分別為：真，真，假。命題函數(shù)中的個(gè)體變?cè)涣炕院笞兂擅}，其真值又與個(gè)體域的選定有關(guān)，這對(duì)命題函數(shù)的研究帶來了一定的困難，為了統(tǒng)一，我們今后使用全總個(gè)體域。而將其它個(gè)體域用一個(gè)謂詞來表示，叫做特性謂詞。特性謂詞加入的方法為：⑴

對(duì)全稱量詞，特性謂詞作為條件命題的前件加入。⑵

對(duì)存在量詞，特性謂詞作為合取項(xiàng)加入。

【例2.4】對(duì)下列命題在①，②兩個(gè)個(gè)體域中符號(hào)化。命題：⑴所有老虎是要吃人。⑵存在一個(gè)老虎要吃人。個(gè)體域：①所有老虎組成的集合。②全總個(gè)體域。解：設(shè)A(x)：x是要吃人的。個(gè)體域?yàn)樗欣匣⒌募稀＂欧?hào)化為(

x)A(x)⑵符號(hào)化為(

x)A(x)

個(gè)體域?yàn)槿倐€(gè)體域。設(shè)特性謂詞T(x)：x是老虎。⑴符號(hào)化為(

x)(T(x)→A(x))⑵符號(hào)化為(

x)(T(x)∧A(x))返回章目錄2.2謂詞公式

2.2.1謂詞公式我們把命題、命題變?cè)?、謂詞填式和命題函數(shù)叫做謂詞演算的原子公式。

定義2.2.1按下列規(guī)則構(gòu)成的表達(dá)式稱為謂詞演算的合式公式，簡(jiǎn)稱謂詞公式。⑴謂詞演算的原子公式是合式公式。⑵若A是合式公式，則?A是合式公式。⑶若A和B是合式公式，則(A∧B)，(A∨B)，(A→B)和(A?B)是合式公式。⑷如果A是合式公式，x是A中出現(xiàn)的任意個(gè)體變?cè)?，則(

x)A，(

x)A是合式公式。⑸只有有限次地應(yīng)用⑴、⑵、⑶、⑷所得的公式是合式公式。謂詞公式也有以下約定：⑴最外層的括號(hào)可以省略。⑵如果按?、∧、∨、→、?在運(yùn)算中的優(yōu)先級(jí)別，省略括號(hào)后不改變?cè)瓉淼倪\(yùn)算次序，可以省略括號(hào)，但量詞后面括號(hào)不能省略。下面舉例說明如何用謂詞公式表達(dá)自然語言中的命題。

【例2.5】并非每個(gè)實(shí)數(shù)都是有理數(shù)。解：設(shè)R(x)：x是實(shí)數(shù)

Q(x)：x是有理數(shù)該命題符號(hào)化為：?(

x)(R(x)→Q(x))【例2.6】沒有不犯錯(cuò)誤的人。解：設(shè)M(x)：x是人

F(x)：x犯錯(cuò)誤此命題可以理解為：存在一些人不犯錯(cuò)誤，這句話是不對(duì)的。此時(shí)，符號(hào)化為：?(

x)(M(x)∧?F(x))

也可以理解為：任何人都是要犯錯(cuò)誤的。此時(shí)，符號(hào)化為：(

x)(M(x)→F(x))

【例2.7】并不是所有的兔子都比所有的烏龜跑得快。解：設(shè)F(x)：x是兔子。

G(x)：x是烏龜。

H(x,y)：x比y跑得快。該命題符號(hào)化為：?(

x)(

y)(F(x)∧G(y)→H(x,y))2.2.2約束變?cè)c自由變?cè)x2.2.2如果A是謂詞公式B的一部分且是謂詞公式，則稱A是B的子公式。定義2.2.3緊接量詞以后的最小子公式叫做該量詞的轄域或作用域。定義2.2.4量詞(

x)和(

x)中的x叫做該量詞的指導(dǎo)變?cè)蜃饔米冊(cè)?。定義2.2.5量詞(

x)和(

x)的轄域內(nèi)x的一切出現(xiàn)叫約束出現(xiàn)，x叫做約束變?cè)患s束變?cè)酝獾钠渌冊(cè)某霈F(xiàn)叫自由出現(xiàn)，自由出現(xiàn)的變?cè)凶杂勺冊(cè)??！纠?.10】說明下列各式量詞的轄域，找出約束變?cè)妥杂勺冊(cè)?。?/p>

(

x)P(x)→Q(y)⑵(

x)(P(x)∧(

y)Q(x,y))⑶(

x)P(x)∧(

y)Q(x,y)⑷(

x)(

y)(P(x,y)∧Q(y,z))?(

x)R(x,y)⑸(

x)P(x)∨R(x,y)

解：⑴(

x)的轄域?yàn)镻(x)，x是約束變?cè)?，y是自由變?cè)?。?

x)的轄域?yàn)镻(x)∧(

y)Q(x,y)，(

y)的轄域?yàn)镼(x,y)，x和y都是約束變?cè)瑹o自由變?cè)?。?

x)的轄域?yàn)镻(x)，(

y)的轄域?yàn)镼(x,y)，P(x)中的x和Q(x,y)中的y是約束變?cè)琎(x,y)中的x是自由變?cè)?。?

x)的轄域?yàn)?

y)(P(x,y)∧Q(y,z))，(

y)的轄域?yàn)镻(x,y)∧Q(y,z)，(

x)的轄域?yàn)镽(x,y)，x是約束變?cè)?，z是自由變?cè)?P(x,y)∧Q(y,z))中的y是約束變?cè)?，R(x,y)中的y是自由變?cè)＂?

x)的轄域?yàn)镻(x)，y是自由變?cè)琍(x)中x是約束變?cè)?，R(x,y)中x是自由變?cè)Ｓ衫?.10可以看出，在一個(gè)公式中，同一個(gè)變?cè)瓤梢允羌s束的，又可以是自由的，容易混淆。因?yàn)?

x)P(x)與(

y)P(y)，(

x)P(x)與(

y)P(y)都具有相同意義，所以約束變?cè)c表示該變?cè)姆?hào)無關(guān)。根據(jù)這個(gè)特點(diǎn)，可以對(duì)約束變?cè)獡Q名。為了使換名后的公式中出現(xiàn)的變?cè)词羌s束的，要么是自由的，我們提出如下的換名規(guī)則：⑴對(duì)約束變?cè)梢該Q名，其更改變?cè)Q的范圍是量詞的指導(dǎo)變?cè)约霸摿吭~轄域中的所有該變?cè)?，公式的其余部分不變。⑵換名時(shí)一定要更改成轄域中沒有出現(xiàn)的變?cè)?，最好是公式中沒有的變量名?！纠?.11】對(duì)(

x)(

y)(P(x,y)∧Q(y,z))?(

x)R(x,y)中的約束變?cè)獃換名。解：用u置換約束變?cè)獃。換名后為：

(

x)(

u)(P(x,u)∧Q(u,z))?(

x)R(x,y)

不能換成：

(

x)(

u)(P(x,u)∧Q(y,z))?(

x)R(x,y)

也不能換成：(

x)(

z)(P(x,z)∧Q(z,z))?(

x)R(x,y)

對(duì)公式中的自由變?cè)部梢赃M(jìn)行更改，用來解決公式中約束變?cè)c自由變?cè)耐麊栴}。這種更改叫做代入，代入規(guī)則是：⑴

對(duì)于謂詞公式中的自由變?cè)梢源?，代入時(shí)需對(duì)公式中該變?cè)杂沙霈F(xiàn)的每處進(jìn)行。⑵

代入的變?cè)c原公式中其他變?cè)拿Q不能相同。

【例2.12】對(duì)(

x)(P(y)∧R(x,y))→(

y)Q(y)中的自由變?cè)獃進(jìn)行代入。解：用z代換y，代入后為：

(

x)(P(z)∧R(x,z))→(

y)Q(y)

不能換成：(

x)(P(x)∧R(x,x))→(

y)Q(y)

或(

x)(P(z)∧R(x,y))→(

y)Q(y)

2.3謂詞演算的等價(jià)式與蘊(yùn)含式定義2.3.1設(shè)A是謂詞公式，如果對(duì)A的任何賦值，A都為真，則稱A是有效的或永真的。定義2.3.2

設(shè)A是謂詞公式，如果對(duì)A的任何賦值，A都為假，則稱A是不可滿足的或永假的。定義2.3.3

設(shè)A是謂詞公式，如果至少有一組賦值使A為真，則稱A是可滿足的。根據(jù)定義2.3.1和定義2.3.3，如果一個(gè)謂詞公式是有效的，它一定是可滿足的。返回章目錄

定義2.3.4設(shè)A、B是任意兩個(gè)謂詞公式，對(duì)A、B的任何賦值，若其真值相同，則稱A與B是等價(jià)的，記作A

B；若A→B是有效的，則稱A蘊(yùn)含B，記作A

B。設(shè)A、B是任意兩個(gè)謂詞公式。當(dāng)A

B時(shí)，由定義2.3.1和定義2.3.4知A?B是永真式。反之，當(dāng)A?B是永真式時(shí)，A

B。所以，也可以用A?B是永真式描述A

B。

1．命題邏輯中的等價(jià)式的推廣⑴命題演算中的所有等價(jià)式都是謂詞演算中的等價(jià)式。從定義2.2.1可以看出，命題演算的合式公式都是謂詞演算的合式公式。再根據(jù)定義2.3.4，命題演算中的所有等價(jià)式都是謂詞演算中的等價(jià)式。⑵命題邏輯中的等價(jià)式的推廣在命題邏輯中，重言式的同一分量出現(xiàn)的每一處都用同一合式公式置換，其結(jié)果仍是重言式(定理1.4.2)。在謂詞邏輯中可以推廣為：在永真的謂詞公式中，命題變?cè)霈F(xiàn)的每一處都用同一謂詞公式置換，其結(jié)果仍是永真式。例如：

因?yàn)?(p∨q)

?p∧?q，故?(p∨q)?(?p∧?q)為永真式，用(

x)P(x)代替p，(

y)R(y)代替q，得到永真式：

?((

x)P(x)∨(

y)R(y))?(?(

x)P(x)∧?(

y)R(y))所以

?((

x)P(x)∨(

y)R(y))

?(

x)P(x)∧?(

y)R(y)2．消去量詞等價(jià)式設(shè)個(gè)體域?yàn)橛邢藜?/p>

a1，a2，…，an

，A(x)是含自由變?cè)獂的任意謂詞公式，有下列等價(jià)式成立：

(

x)A(x)

A(a1)∧A(a2)∧…∧A(an)(

x)A(x)

A(a1)∨A(a2)∨…∨A(an)3．量詞否定等價(jià)式設(shè)A(x)是含自由變?cè)獂的任意謂詞公式。則

?(

x)A(x)

(

x)?A(x)?(

x)A(x)

(

x)?A(x)

約定，量詞之前的否定聯(lián)結(jié)詞，不是否定該量詞，而是否定該量詞及其轄域。

這兩個(gè)等價(jià)式可在有限個(gè)體域上證明，設(shè)個(gè)體域?yàn)?/p>

a1，a2，…，an

?(

x)A(x)

?(A(a1)∧A(a2)∧…∧A(an))

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

(

x)?A(x)?(

x)A(x)

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

?A(a1)∧?A(a2)∧…∧?A(an)

(

x)?A(x)

當(dāng)個(gè)體域?yàn)闊o限集時(shí)，等價(jià)式也是成立的。但因?yàn)榍闆r復(fù)雜，僅作以下說明：對(duì)等價(jià)式?(

x)A(x)

(

x)

A(x)，?(

x)A(x)表示：并不是所有的x都有性質(zhì)A。(

x)?A(x)表示：存在x沒有性質(zhì)A。顯然“并不是所有的x都有性質(zhì)A”和“存在x沒有性質(zhì)A”是相同的，所以?(

x)A(x)

(

x)?A(x)。對(duì)等價(jià)式?(

x)A(x)

(

x)?A(x)來說，“不存在某個(gè)x有性質(zhì)A”和“所有的x都沒有性質(zhì)A”是相同的。4．量詞作用域的擴(kuò)展與收縮等價(jià)式設(shè)A(x)是含自由變?cè)獂的任意謂詞公式。B是不含變?cè)獂的謂詞公式，則

(

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)A(x)→B(

x)(B→A(x))

B→(

x)A(x)(

x)(B→A(x))

B→(

x)A(x)【例2.13】證明(

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)→B5．量詞分配等價(jià)式設(shè)A(x)和B(x)是含自由變?cè)獂的任意謂詞公式，則

(

x)(A(x)∧B(x))

(

x)A(x)∧(

x)B(x)(

x)(A(x)∨B(x))

(

x)A(x)∨(

x)B(x)

前者可以理解為：“所有的x有性質(zhì)A和性質(zhì)B”和“所有的x有性質(zhì)A且所有的x有性質(zhì)B”是等同的。后者可以利用前者來證明。

【例2.14】證明(

x)(A(x)∨B(x))

(

x)A(x)∨(

x)B(x)

解：因?yàn)?

x)(?A(x)∧?B(x))

(

x)?A(x)∧(

x)?B(x)而(

x)(?A(x)∧?B(x))

(

x)?(A(x)∨B(x))

?(

x)(A(x)∨B(x))(

x)?A(x)∧(

x)?B(x)

?(

x)A(x)∧?(

x)B(x)

?((

x)A(x)∨(

x)B(x))所以?(

x)(A(x)∨B(x))

?((

x)A(x)∨(

x)B(x))于是(

x)(A(x)∨B(x))

(

x)A(x)∨(

x)B(x)6．量詞與聯(lián)結(jié)詞的蘊(yùn)含式設(shè)A(x)和B(x)是含自由變?cè)獂的任意謂詞公式。

(

x)A(x)∨(

x)B(x)

(

x)(A(x)∨B(x))(

x)(A(x)∧B(x))

(

x)A(x)∧(

x)B(x)(

x)(A(x)→B(x))

(

x)A(x)→(

x)B(x)(

x)(A(x)

B(x))

(

x)A(x)

(

x)B(x)

對(duì)第一式作如下說明：令A(yù)(x)表示x有一支鋼筆，B(x)表示x有一支鉛筆，個(gè)體域是2000級(jí)計(jì)算機(jī)1班全體同學(xué)。全班每個(gè)同學(xué)都有一支鋼筆或每個(gè)同學(xué)都有一支鉛筆，當(dāng)然可以推出全班每個(gè)同學(xué)有一支鋼筆或有一支鉛筆。但反過來是不對(duì)的。第二式可用第一式推出?！纠?.15】證明

(

x)(A(x)∧B(x))

(

x)A(x)∧(

x)B(x)

解：

由第一式可得：

(

x)?A(x)∨(

x)

B(x)

(

x)(?A(x)∨?B(x))而

(

x)?A(x)∨(

x)?B(x)

?(

x)A(x)∨?(

x)B(x)

?((

x)A(x)∧(

x)B(x))(

x)(?A(x)∨?B(x))

(

x)?(A(x)∧B(x))

?(

x)(A(x)∧B(x))故有

?((

x)A(x)∧(

x)B(x))

?(

x)(A(x)∧B(x))由雙條件否定等價(jià)式有

(

x)(A(x)∧B(x))

(

x)A(x)∧(

x)B(x)第三、四式可以類似推出。7．多個(gè)量詞的使用⑴約定：(

x)(

y)A(x,y)表示(

x)((

y)A(x,y))⑵一般地說，多個(gè)量詞相連時(shí)，同名量詞是無序的，即改變它們的次序，命題真值不變。異名量詞是有序的，即改變它們的次序，命題真值發(fā)生變化。對(duì)后者作如下的說明：令A(yù)(x,y)表示x+y=10，個(gè)體域?yàn)檎麛?shù)集合I。

(

x)(

y)A(x,y)表示對(duì)任一整數(shù)x，存在整數(shù)y，使x+y=10。這是一個(gè)真命題。

(

y)(

x)A(x,y)表示存在整數(shù)y，對(duì)任一整數(shù)x，有x+y=10。這是一個(gè)假命題。因?yàn)橥吭~是無序的，所以有：

(

x)(

y)A(x,y)

(

y)(

x)A(x,y)(

x)(

y)A(x,y)

(

y)(

x)A(x,y)

異名量詞有下列的蘊(yùn)含關(guān)系：

(

y)(

x)A(x,y)

(

x)(

y)A(x,y)(

x)(

y)A(x,y)

(

y)(

x)A(x,y)

⑶具有兩個(gè)量詞的謂詞公式還有下列的蘊(yùn)含式：

(

x)(

y)A(x,y)

(

y)(

x)A(x,y)(

y)(

x)A(x,y)

(

x)(

y)A(x,y)(

x)(

y)A(x,y)

(

y)(

x)A(x,y)(

y)(

x)A(x,y)

(

x)(

y)A(x,y)

2.4前束范式定義2.4.1一個(gè)公式，如果量詞均在全式的開頭，它們的作用域延伸到整個(gè)公式的末尾，則稱為前束范式。根據(jù)這個(gè)定義前束范式可表示成如下形式：

(□v1)(□v2)…(□vn)A

其中：□是

或

vi是個(gè)體變?cè)琲=1,…,nA是不含量詞的謂詞公式返回章目錄

例如：(

x)(

y)(F(x)∨G(y)→L(x,y))(

y)(

x)(

z)(?H(x,y)∧F(x)→L(x,z))都是前束范式。而

(

x)F(x)∨(

y)(G(y)→L(x,y))(

y)(

x)(?H(x,y)∧F(x))→(

z)L(x,z)都不是前束范式。定理2.4.1任何謂詞公式,都可以化成與其等價(jià)的前束范式。本定理的證明從略。利用上一節(jié)介紹的等價(jià)式、2.2節(jié)介紹的代入規(guī)則和換名規(guī)則可以求出任何謂詞公式的前束范式。

【例2.16】求公式(

x)F(x)→(

x)G(x)

的前束范式。解：(

x)F(x)→(

x)G(x)

?(

x)F(x)∨(

x)G(x)

(

x)?F(x)∨(

x)G(x)

(

x)(?F(x)∨G(x)) (前束范式)

(

x)(F(x)→G(x)) (前束范式)

從本例可以看出，謂詞公式的前束范式并不惟一。【例2.17】把公式(

y)G(x,y)→(

x)F(x,y)化為等價(jià)的前束范式。解：(

y)G(x,y)→(

x)F(x,y)

(

t)G(x,t)→(

s)F(s,y)

(

t)(

s)(G(x,t)→F(s,y))

定義2.4.2一個(gè)謂詞公式A，如果具有如下形式稱為前束合取范式。

(□v1)(□v2)…(□vn)((A11∨A12∨…∨)∧(A21∨A22∨…∨)∧

…(Am1∨Am2∨…∨))

其中：□是

或

vi是個(gè)體變?cè)琲=1,…,n

Aij是原子公式或其否定。例如

(

x)(

y)(

z)((?F(x)∨H(x,y)∨G(x))∧(F(x)∨L(x,z)))是前束合取范式。

定理2.4.2每個(gè)謂詞公式都可化為與其等價(jià)的前束合取范式。證明從略。

【例2.18】將((

x)F(x)∨(

x)G(x))→(

x)(F(x)∨G(x))化為與其等價(jià)的前束合取范式。解：

((

x)F(x)∨(

x)G(x))→(

x)(F(x)∨G(x))

(

x)(F(x)∨G(x))→(

y)(F(y)∨G(y))

(

x)(

y)((F(x)∨G(x))→(F(y)∨G(y)))

(

x)(

y)(?(F(x)∨G(x))∨(F(y)∨G(y)))

(

x)(

y)((?F(x)∧?G(x))∨(F(y)∨G(y)))

(

x)(

y)((?F(x)∨F(y)∨G(y))∧(?G(x)∨F(y)∨G(y)))

定義2.4.3一個(gè)謂詞公式A，如果具有如下形式稱為前束析取范式。

(□v1)(□v2)…(□vn)((A11∧A12∧…∧)∨(A21∧A22∧…∧)∨

…(Am1∧Am2∧…∧))

其中：□是

或

vi是個(gè)體變?cè)琲=1,…,n

Aij是原子公式或其否定。定理2.4.3每一個(gè)謂詞公式A都可以化為與它等價(jià)的前束析取范式。證明從略。返回章目錄

2.5謂詞邏輯的推理理論在謂詞演算中，C是一組前提A1，A2，…，An的有效結(jié)論，仍然定義為A1∧A2∧…∧An

C。命題演算推理中的P規(guī)則、T規(guī)則、置換規(guī)則、合取引入規(guī)則、所有的等價(jià)式和蘊(yùn)含式在謂詞推理中都是對(duì)的，都可以使用；另外，2.3節(jié)中介紹的謂詞演算中的等價(jià)式與蘊(yùn)含式也可以在謂詞推理中使用。除此之外，還有以下的規(guī)則。⑴全稱指定規(guī)則(US規(guī)則)(

x)A(x)

A(c)

此式成立的條件是：①c是個(gè)體域中任一個(gè)體。②用c取代A(x)中x時(shí)，一定在x出現(xiàn)的所有地方進(jìn)行取代。全稱指定規(guī)則說明：若個(gè)體域中的所有個(gè)體都滿足謂詞A，則個(gè)體域中任一個(gè)體c也滿足謂詞A。利用這個(gè)規(guī)則，可以從帶有全稱量詞的前提中，推導(dǎo)出不帶全稱量詞的特殊結(jié)論。它體現(xiàn)了在邏輯推理中由一般到特殊的推導(dǎo)方法。⑵全稱推廣規(guī)則(UG規(guī)則)A(y)

(

x)A(x)

此式成立的條件是：

①

y是個(gè)體域中任一個(gè)體且對(duì)y，A(y)為真。②

x是不出現(xiàn)在A(y)中的個(gè)體變?cè)?。例如，個(gè)體域?yàn)閷?shí)數(shù)集合R，G(x,y)表示x>y，設(shè)A(y)

(

x)G(x,y)，顯然A(y)滿足條件①，一定能推出(

z)A(z)

(

z)(

x)G(x,z)

(

z)(

x)(x>z)，這是一個(gè)真命題。若推成(

x)A(x)

(

x)(

x)G(x,x)

(

x)(

x)(x>x)，就產(chǎn)生了錯(cuò)誤，因?yàn)檫@是一個(gè)假命題。錯(cuò)誤的原因是違背了條件②。⑶存在指定規(guī)則(ES規(guī)則)(

x)A(x)

A(c)

此式成立的條件是：①c是個(gè)體域中的某個(gè)確定的個(gè)體，而不是個(gè)體變?cè)?。②c是不出現(xiàn)在A(x)中的個(gè)體。

存在指定規(guī)則說明，若個(gè)體域中存在一些個(gè)體滿足謂詞A，則至少有某個(gè)確定的個(gè)體c滿足謂詞A。例如，設(shè)個(gè)體域?yàn)檎麛?shù)集合I，A(x)表示x是奇數(shù)，B(x)表示x是偶數(shù)。

(

x)A(x)

A(c)，它表示：若存在一些整數(shù)是奇數(shù)，令c為3，則c是奇數(shù)。這個(gè)推理是對(duì)的。

(

x)B(x)

B(d)，它表示：若存在一些整數(shù)是偶數(shù)，令d為4，則d是偶數(shù)。這個(gè)推理也是對(duì)的。因此有下列推理成立：

(

x)A(x)∧(

x)B(x)

A(c)∧B(d)而下列推理是錯(cuò)誤的：

(

x)A(x)∧(

x)B(x)

A(c)∧B(c)(

x)A(x)∧(

x)B(x)

A(d)∧B(d)

因?yàn)?不能既是奇數(shù)，又是偶數(shù)；同樣，4也不能既是奇數(shù)，又是偶數(shù)。錯(cuò)誤的原因是違背了條件②。⑷存在推廣規(guī)則(EG規(guī)則)A(c)

(

x)A(x)

此式成立的條件是：①

c是個(gè)體域中確定的個(gè)體。②

x不能是出現(xiàn)在A(c)中的個(gè)體變?cè)?。存在推廣規(guī)則說明：對(duì)于個(gè)體域中的某個(gè)個(gè)體c滿足謂詞A，當(dāng)然有(

x)A(x)。

【例2.19】證明蘇格拉底論證：凡人要死。蘇格拉底是人，蘇格拉底要死。設(shè)：

H(x)：x是人。

M(x)：x是要死的。

s：蘇格拉底。本題要證明：(

x)(H(x)→M(x))∧H(s)

M(s)

證明：

⑴

(

x)(H(x)→M(x)) P

⑵

H(s)→M(s) US⑴

⑶

H(s) P

⑷

M(s) T⑵⑶假言推理【例2.20】證明(

x)(H(x)→M(x))，(

x)H(x)

(

x)M(x)

證明： ⑴(

x)H(x) P ⑵H(c) ES⑴ ⑶(

x)(H(x)→M(x)) P ⑷H(c)→M(c) US⑶ ⑸M(c) T⑵⑷假言推理 ⑹(

x)M(x) EG⑸

若把⑴,⑵寫在⑶,⑷的后面，得到如下的推理： ⑴(

x)(H(x)→M(x)) P ⑵H(c)→M(c)US⑴ ⑶(

x)H(x)P ⑷H(c) ES⑶ ⑸M(c)T⑵⑷假言推理 ⑹(

x)M(x)EG⑸

這個(gè)推理在邏輯上是錯(cuò)誤的。因?yàn)棰浦械腸為個(gè)體域中一個(gè)個(gè)體，用ES規(guī)則由⑶推到⑷不能選擇⑵中的c，因?yàn)樗x的個(gè)體和⑵中的個(gè)體c不一定是同一個(gè)個(gè)體，故推理是錯(cuò)誤的。

【例2.21】證明(

x)(A(x)∨B(x))，(

x)?A(x)

(

x)B(x)

證明：用直接法證明。 ⑴(

x)(A(x)∨B(x)) P ⑵A(s)∨B(s)US⑴ ⑶(

x)?A(x)P⑷?A(s)US⑶ ⑸B(s) T⑵⑷析取三段論 ⑹(

x)B(x) EG⑸

用歸謬法證明。⑴?(

x)B(x)P(附加前提) ⑵(

x)?B(x) T⑴量詞否定等價(jià)式 ⑶?B(s) US⑵ ⑷(

x)(A(x)∨B(x)) P ⑸A(s)∨B(s) US⑷ ⑹A(s) T⑶⑸析取三段論 ⑺(

x)?A(x) P ⑻?A(s) US⑺ ⑼A(s)∧?A(s)(矛盾) T⑹⑻合取引入【例2.22】用CP規(guī)則證明：

(

x)(F(x)∨G(x))

(

x)F(x)∨(

x)G(x)原題可改寫成：(

x)(F(x)∨G(x))

?(

x)F(x)→(

x)G(x)

證明：

⑴

?(

x)F(x) P(附加前提)

⑵(

x)

F(x) T⑴量詞否定等價(jià)式

⑶

?F(c) ES⑵

⑷(

x)(F(x)∨G(x)) P

⑸

F(c)∨G(c) US⑷

⑹

G(c) T⑶⑸析取三段論

⑺

(

x)G(x) EG⑹

⑻

?(

x)F(x)→(

x)G(x) CP【例2.23】設(shè)個(gè)體域?yàn)槿倐€(gè)體域。證明推理：學(xué)術(shù)會(huì)的成員都是工人并且是專家。有些成員是青年人。所以有的成員是青年專家。首先將命題符號(hào)化：

F(x)：x是學(xué)術(shù)會(huì)成員。

G(x)：x是專家。

H(x)：x是工人。

R(x)：x是青年人。本題要證明：(

x)(F(x)→G(x)∧H(x)),(

x)(F(x)∧R(x))

(

x)(F(x)∧R(x)∧G(x))

證明：

⑴

(

x)(F(x)∧R(x)) P

⑵

F(c)∧R(c) ES⑴

⑶

F(c) T⑵化簡(jiǎn)律

⑷

(

x)(F(x)→G(x)∧H(x)) P

⑸

F(c)→G(c)∧H(c) US⑷

⑹

G(c)∧H(c) T⑶⑸假言推理⑺

R(c) T⑵化簡(jiǎn)律⑻

G(c) T⑹化簡(jiǎn)律⑼F(c)∧R(c)∧G(c) T⑵⑺⑻合取引入⑽(

x)(F(x)∧R(x)∧G(x)) EG⑼返回總目錄返回章目錄第3章集合

3.1集合的基本概念

3.2集合的運(yùn)算

3.3集合恒等式

3.4集合的覆蓋與劃分

3.5笛卡爾積返回總目錄第3章集合3.1集合的基本概念一些確定的、能區(qū)分的對(duì)象的全體是集合，通常用大寫的英文字母表示。組成集合的對(duì)象叫做集合的元素或成員，常用小寫的英文字母表示。集合的元素必須是確定的。所謂確定的，是指任何一個(gè)對(duì)象是不是集合的元素是明確的、確定的，不能模棱兩可。集合的元素又是能區(qū)分的，能區(qū)分的是指集合中的元素是互不相同的。如果一個(gè)集合中有幾個(gè)元素相同，算做一個(gè)。例如集合

1,2,3,3

和

1,2,3

是同一集合。

集合的元素是任意的對(duì)象，對(duì)象是可以獨(dú)立存在的具體的或抽象的客體。它可以是獨(dú)立存在的數(shù)、字母、人或其它物體，也可以是抽象的概念，當(dāng)然也可以是集合。例如集合

1,2,

3

,

1,2

的元素

3

和

1,2

就是集合。集合的元素又是無序的，即

1,2,3

和

3,1,2

是同一集合。設(shè)S是集合，a是S的一個(gè)元素，記為a

S，讀做“a屬于S”，也可讀做“a在S中”。如果a不是S的元素，記為a

S，讀做“a不屬于S”，也可讀做“a不在S中”。例如：①26個(gè)英文字母組成一個(gè)集合，任一英文字母是該集合的元素。②直線上的所有點(diǎn)組成實(shí)數(shù)集合R，每一個(gè)實(shí)數(shù)是集合R的元素。③陜西科技大學(xué)全體學(xué)生組成一個(gè)集合，該校的每一個(gè)學(xué)生是這個(gè)集合的元素。

3.1.1集合的表示法集合有三種表示法。第一種表示法是列舉法：在花括號(hào)“

”中列舉出該集合的元素，元素之間用逗號(hào)隔開。例如：

I5=

1,2,3,4,5

I+=

1,2,3,…

I=

0,1,-1,2,-2,…

S=

T,F

第二種表示法是描述法：用謂詞界定集合的元素。例如：

Q=

x|x是有理數(shù)

R=

x|x是實(shí)數(shù)

C=

x|x是復(fù)數(shù)

A=

x|x

I∧0＜x∧x＜5

若用P(x)表示x是有理數(shù)，那么Q又可表示為：

Q=

x|P(x)

一般地說，集合可用描述法表示為：

S=

x|A(x)

其中，A(x)是謂詞顯然，當(dāng)a

S

時(shí)，則A(a)為真；反之，當(dāng)A(a)為真，則a

S。即a

S的充分必要條件是A(a)為真。在中學(xué)的教科書中將自然數(shù)定義為：

N=

1,2,3,…

這是對(duì)的。在離散數(shù)學(xué)中，認(rèn)為自然數(shù)是由0開始的，即

N=

0,1,2,3,…

我們把這種由0開始的自然數(shù)集叫做擴(kuò)展的自然數(shù)集。離散數(shù)學(xué)中使用擴(kuò)展的自然數(shù)集。本書的自然數(shù)集是指擴(kuò)展的自然數(shù)集。

具有有限個(gè)元素的集合叫有限集，否則叫無限集。有限集元素的個(gè)數(shù)稱為該集合的基數(shù)，也叫集合的勢(shì)。有限集A的基數(shù)記為|A|。例如：設(shè)

A=

a,b,c

，A

是有限集，A的基數(shù)|A|=3。無限集也有基數(shù)的概念。無限集的基數(shù)比有限集的基數(shù)要復(fù)雜的多，本書將在5.3節(jié)中介紹。擴(kuò)展的自然數(shù)集N=

0,1,2,3,…

是無限集。整數(shù)集合I、有理數(shù)集合Q、實(shí)數(shù)集合R和復(fù)數(shù)集合C都是常見的無限集。3.1.2子集和集合的相等

定義3.1.1設(shè)A，B是任意的集合，當(dāng)A的每一元素都是B的元素時(shí)，則稱A是B的子集，也稱A包含在B內(nèi)或B包含A。記為A

B或B

A。當(dāng)A不是B的子集時(shí)，記為A?B。

A

B用謂詞公式表示為：A

B

(

x)(x

A→x

B)A?B用謂詞公式表示為：A?B

(

x)(x

A∧x

B)

例如：設(shè)A=

1

，B=

1,2

，C=

1,2,3

則

A

AA

B，B

C，A

CC?B

可以證明，集合的包含有下列性質(zhì)：①自反性。即對(duì)任意集合A，A

A。

②傳遞性。即對(duì)任意集合A、B、C，當(dāng)A

B和B

C時(shí)，A

C。

定義3.1.2設(shè)A，B是集合，如果A

B且B

A，則稱A與B相等。記為A=B。如果A與B不相等，記為A≠B。集合相等也可用謂詞公式表示為：

A=B

A

B∧B

A

(

x)(x

A→x

B)∧(

x)(x

B→x

A)

(

x)(x

A?x

B)

例如：設(shè)A=

1,2

，B=

1,

2

，C=

2,1

則A=C，A≠B

由集合相等的定義可以看出，集合相等有下列性質(zhì)：①自反性:即對(duì)任意集合A，A=A。②對(duì)稱性:即對(duì)任意集合A、B，當(dāng)A=B時(shí)，B=A。③傳遞性:即對(duì)任意集合A、B、C，當(dāng)A=B和B=C時(shí)，A=C。

定義3.1.3設(shè)A，B是集合，如果A

B且A≠B，則稱A是B的真子集。記為A

B。如果A不是B的真子集，記為A

B。真子集用謂詞公式表示為：

A

B

A

B∧A≠B

(

x)(x

A→x

B)∧(

x)(x

B∧x

A)

例如：設(shè)A=

a

，B=

a,b

，C=

a,b,c

則

A

B，B

C，A

CA

A

又如，自然數(shù)集是整數(shù)集合的真子集，也是有理數(shù)集合和實(shí)數(shù)集合的真子集，即N

I，N

Q，N

R。

定義3.1.4不包含任何元素的集合叫空集。記為??？占梢员硎緸椋?/p>

?=

x|P(x)∧

P(x)

其中，P(x)為任意謂詞空集?是不包含任何元素的集合，所以，|?|=0。

定理3.1.1空集是任意集合的子集。

證明：設(shè)A是任意集合。對(duì)任意對(duì)象x，由空集的定義知，x

?為假，由條件聯(lián)結(jié)詞的定義知，x

?→x

A為真。根據(jù)全稱推廣規(guī)則有

(

x)(x

?→x

A)為真，故?

A

根據(jù)定理3.1.1，空集是任意集合的子集，即?

A；對(duì)任意集合A，A

A。一般地說，任意集合A至少有兩個(gè)子集，一個(gè)是空集?，另一個(gè)是它本身A。

推論

空集是惟一的。

證明：設(shè)有兩個(gè)空集?1和?2，由定理3.1.1有?1

?2和