離散數(shù)學課件

第2章謂詞邏輯

2.1個體、謂詞與量詞

2.2謂詞公式

2.3謂詞演算的等價式與蘊含式

2.4前束范式

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

2.1個體、謂詞與量詞

2.1.1個體考察下面的三個原子命題：

⑴

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

張華比李紅高。⑶

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

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

a：李玲

b：張華

c：李紅

d：小高

e：小王

f：小劉

a,b,c,d,e,f都是個體常元。將表示任意個體或泛指某類個體的標識符稱為個體變元，常表示為x、y、z、…等或這些英文字母帶下標。個體變元的變化范圍稱為個體域或論域。個體域可以是有窮集合，也可以是無窮集合，包含任意個體域的個體域稱為全總個體域，它是由宇宙間一切對象組成的集合。在本書中，如無特別說明，所采用的都是全總個體域。

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

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

G：…比…高。

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

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

于是上面三個命題就表示為：

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

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

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

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

a：5,b：－7

用a,b分別取代x,y，就得到H(a,b)，它表示5+(－7)≥0，這是個假命題，它的真值為假。其實，用個體常元取代命題函數(shù)的所有個體變元所得到的表達式就是前面所說的謂詞填式。因為它由個體常元取代命題函數(shù)中所有的個體變元而得到，所以也把謂詞填式叫做0元命題函數(shù)。F(a)，G(b,c)，H(d,e,f)都是0元命題函數(shù)，它們都是命題。于是命題邏輯中的命題均可以表示為謂詞邏輯中的0元命題函數(shù)(謂詞填式)，命題成為命題函數(shù)的特例。

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

a：2，b：3

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

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

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

2.1.3量詞量詞分兩種。⑴

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

”。并用(

x)，(

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

x)F(x)和(

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

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

”。并用(

x)，(

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

x)F(x)和(

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

凡人要死。⑵

有的人是研究生。解：⑴

令F(x)：x要死。命題“凡人要死?！狈柣癁椋?

x)F(x)⑵

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

命題“有的人是研究生?！狈柣癁椋?

x)G(x)

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

x)和(

x)分別叫做個體變元x被全稱量化和存在量化。一般地說，命題函數(shù)不是命題，如果對命題函數(shù)中所有命題變元進行全稱量化或存在量化，該函數(shù)就變成了命題。這一結論在例2.2中得到驗證。雖然對命題函數(shù)中所有命題變元進行量化后，該命題函數(shù)就變成了命題，但所得命題的真值與個體域的選定有關。請看下列例題：

【例2.3】對下列命題符號化，并在①，②，③三個個體域中考察命題的真值。命題：⑴

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

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

-1，0，1，2，4

②

3，-2，7，8

③

15，20，24

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

“所有數(shù)小于5?！狈柣癁椋?

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

“至少有一個數(shù)小于5?！狈柣癁椋?

x)L(x)在個體域①，②，③中，它們的真值分別為：真，真，假。命題函數(shù)中的個體變元被量化以后變成命題，其真值又與個體域的選定有關，這對命題函數(shù)的研究帶來了一定的困難，為了統(tǒng)一，我們今后使用全總個體域。而將其它個體域用一個謂詞來表示，叫做特性謂詞。特性謂詞加入的方法為：⑴

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

對存在量詞，特性謂詞作為合取項加入。

【例2.4】對下列命題在①，②兩個個體域中符號化。命題：⑴所有老虎是要吃人。⑵存在一個老虎要吃人。個體域：①所有老虎組成的集合。②全總個體域。解：設A(x)：x是要吃人的。個體域為所有老虎的集合。⑴符號化為(

x)A(x)⑵符號化為(

x)A(x)

個體域為全總個體域。設特性謂詞T(x)：x是老虎。⑴符號化為(

x)(T(x)→A(x))⑵符號化為(

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

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

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

x)A，(

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

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

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

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

F(x)：x犯錯誤此命題可以理解為：存在一些人不犯錯誤，這句話是不對的。此時，符號化為：?(

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

也可以理解為：任何人都是要犯錯誤的。此時，符號化為：(

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

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

G(x)：x是烏龜。

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

x)(

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

x)和(

x)中的x叫做該量詞的指導變元或作用變元。定義2.2.5量詞(

x)和(

x)的轄域內x的一切出現(xiàn)叫約束出現(xiàn)，x叫做約束變元；約束變元以外的其它變元的出現(xiàn)叫自由出現(xiàn)，自由出現(xiàn)的變元叫自由變元?！纠?.10】說明下列各式量詞的轄域，找出約束變元和自由變元。⑴

(

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)的轄域為P(x)，x是約束變元，y是自由變元。⑵(

x)的轄域為P(x)∧(

y)Q(x,y)，(

y)的轄域為Q(x,y)，x和y都是約束變元，無自由變元。⑶(

x)的轄域為P(x)，(

y)的轄域為Q(x,y)，P(x)中的x和Q(x,y)中的y是約束變元，Q(x,y)中的x是自由變元。⑷(

x)的轄域為(

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

y)的轄域為P(x,y)∧Q(y,z)，(

x)的轄域為R(x,y)，x是約束變元，z是自由變元，(P(x,y)∧Q(y,z))中的y是約束變元，R(x,y)中的y是自由變元。⑸(

x)的轄域為P(x)，y是自由變元，P(x)中x是約束變元，R(x,y)中x是自由變元。由例2.10可以看出，在一個公式中，同一個變元既可以是約束的，又可以是自由的，容易混淆。因為(

x)P(x)與(

y)P(y)，(

x)P(x)與(

y)P(y)都具有相同意義，所以約束變元與表示該變元的符號無關。根據(jù)這個特點，可以對約束變元換名。為了使換名后的公式中出現(xiàn)的變元要么是約束的，要么是自由的，我們提出如下的換名規(guī)則：⑴對約束變元可以換名，其更改變元名稱的范圍是量詞的指導變元，以及該量詞轄域中的所有該變元，公式的其余部分不變。⑵換名時一定要更改成轄域中沒有出現(xiàn)的變元名，最好是公式中沒有的變量名?！纠?.11】對(

x)(

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

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

(

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)

對公式中的自由變元也可以進行更改，用來解決公式中約束變元與自由變元的同名問題。這種更改叫做代入，代入規(guī)則是：⑴

對于謂詞公式中的自由變元可以代入，代入時需對公式中該變元自由出現(xiàn)的每處進行。⑵

代入的變元與原公式中其他變元的名稱不能相同。

【例2.12】對(

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

y)Q(y)中的自由變元y進行代入。解：用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謂詞演算的等價式與蘊含式定義2.3.1設A是謂詞公式，如果對A的任何賦值，A都為真，則稱A是有效的或永真的。定義2.3.2

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

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

定義2.3.4設A、B是任意兩個謂詞公式，對A、B的任何賦值，若其真值相同，則稱A與B是等價的，記作A

B；若A→B是有效的，則稱A蘊含B，記作A

B。設A、B是任意兩個謂詞公式。當A

B時，由定義2.3.1和定義2.3.4知A?B是永真式。反之，當A?B是永真式時，A

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

B。

1．命題邏輯中的等價式的推廣⑴命題演算中的所有等價式都是謂詞演算中的等價式。從定義2.2.1可以看出，命題演算的合式公式都是謂詞演算的合式公式。再根據(jù)定義2.3.4，命題演算中的所有等價式都是謂詞演算中的等價式。⑵命題邏輯中的等價式的推廣在命題邏輯中，重言式的同一分量出現(xiàn)的每一處都用同一合式公式置換，其結果仍是重言式(定理1.4.2)。在謂詞邏輯中可以推廣為：在永真的謂詞公式中，命題變元出現(xià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．消去量詞等價式設個體域為有限集

a1，a2，…，an

，A(x)是含自由變元x的任意謂詞公式，有下列等價式成立：

(

x)A(x)

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

x)A(x)

A(a1)∨A(a2)∨…∨A(an)3．量詞否定等價式設A(x)是含自由變元x的任意謂詞公式。則

?(

x)A(x)

(

x)?A(x)?(

x)A(x)

(

x)?A(x)

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

這兩個等價式可在有限個體域上證明，設個體域為

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)

當個體域為無限集時，等價式也是成立的。但因為情況復雜，僅作以下說明：對等價式?(

x)A(x)

(

x)

A(x)，?(

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

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

x)A(x)

(

x)?A(x)。對等價式?(

x)A(x)

(

x)?A(x)來說，“不存在某個x有性質A”和“所有的x都沒有性質A”是相同的。4．量詞作用域的擴展與收縮等價式設A(x)是含自由變元x的任意謂詞公式。B是不含變元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)(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．量詞分配等價式設A(x)和B(x)是含自由變元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和性質B”和“所有的x有性質A且所有的x有性質B”是等同的。后者可以利用前者來證明。

【例2.14】證明(

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)∨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)結詞的蘊含式設A(x)和B(x)是含自由變元x的任意謂詞公式。

(

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)

對第一式作如下說明：令A(x)表示x有一支鋼筆，B(x)表示x有一支鉛筆，個體域是2000級計算機1班全體同學。全班每個同學都有一支鋼筆或每個同學都有一支鉛筆，當然可以推出全班每個同學有一支鋼筆或有一支鉛筆。但反過來是不對的。第二式可用第一式推出?！纠?.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))由雙條件否定等價式有

(

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

(

x)A(x)∧(

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

x)(

y)A(x,y)表示(

x)((

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

(

x)(

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

(

y)(

x)A(x,y)表示存在整數(shù)y，對任一整數(shù)x，有x+y=10。這是一個假命題。因為同名量詞是無序的，所以有：

(

x)(

y)A(x,y)

(

y)(

x)A(x,y)(

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)

⑶具有兩個量詞的謂詞公式還有下列的蘊含式：

(

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

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

其中：□是

或

vi是個體變元，i=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é)介紹的等價式、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)) (前束范式)

從本例可以看出，謂詞公式的前束范式并不惟一?！纠?.17】把公式(

y)G(x,y)→(

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

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一個謂詞公式A，如果具有如下形式稱為前束合取范式。

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

…(Am1∨Am2∨…∨))

其中：□是

或

vi是個體變元，i=1,…,n

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

(

x)(

y)(

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

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

【例2.18】將((

x)F(x)∨(

x)G(x))→(

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

((

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一個謂詞公式A，如果具有如下形式稱為前束析取范式。

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

…(Am1∧Am2∧…∧))

其中：□是

或

vi是個體變元，i=1,…,n

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

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

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

x)A(x)

A(c)

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

(

x)A(x)

此式成立的條件是：

①

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

x是不出現(xiàn)在A(y)中的個體變元。例如，個體域為實數(shù)集合R，G(x,y)表示x>y，設A(y)

(

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

z)A(z)

(

z)(

x)G(x,z)

(

z)(

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

x)A(x)

(

x)(

x)G(x,x)

(

x)(

x)(x>x)，就產(chǎn)生了錯誤，因為這是一個假命題。錯誤的原因是違背了條件②。⑶存在指定規(guī)則(ES規(guī)則)(

x)A(x)

A(c)

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

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

(

x)A(x)

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

(

x)B(x)

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

(

x)A(x)∧(

x)B(x)

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

(

x)A(x)∧(

x)B(x)

A(c)∧B(c)(

x)A(x)∧(

x)B(x)

A(d)∧B(d)

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

(

x)A(x)

此式成立的條件是：①

c是個體域中確定的個體。②

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

x)A(x)。

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

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⑸

這個推理在邏輯上是錯誤的。因為⑵中的c為個體域中一個個體，用ES規(guī)則由⑶推到⑷不能選擇⑵中的c，因為它要選的個體和⑵中的個體c不一定是同一個個體，故推理是錯誤的。

【例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⑴量詞否定等價式 ⑶?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⑴量詞否定等價式

⑶

?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】設個體域為全總個體域。證明推理：學術會的成員都是工人并且是專家。有些成員是青年人。所以有的成員是青年專家。首先將命題符號化：

F(x)：x是學術會成員。

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⑵化簡律

⑷

(

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

⑸

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

⑹

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

R(c) T⑵化簡律⑻

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

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

3.1集合的基本概念

3.2集合的運算

3.3集合恒等式

3.4集合的覆蓋與劃分

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

1,2,3,3

和

1,2,3

是同一集合。

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

1,2,

3

,

1,2

的元素

3

和

1,2

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

1,2,3

和

3,1,2

是同一集合。設S是集合，a是S的一個元素，記為a

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

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

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

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

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ù)

C=

x|x是復數(shù)

A=

x|x

I∧0＜x∧x＜5

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

Q=

x|P(x)

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

S=

x|A(x)

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

S

時，則A(a)為真；反之，當A(a)為真，則a

S。即a

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

N=

1,2,3,…

這是對的。在離散數(shù)學中，認為自然數(shù)是由0開始的，即

N=

0,1,2,3,…

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

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

A=

a,b,c

，A

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

0,1,2,3,…

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

定義3.1.1設A，B是任意的集合，當A的每一元素都是B的元素時，則稱A是B的子集，也稱A包含在B內或B包含A。記為A

B或B

A。當A不是B的子集時，記為A?B。

A

B用謂詞公式表示為：A

B

(

x)(x

A→x

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

(

x)(x

A∧x

B)

例如：設A=

1

，B=

1,2

，C=

1,2,3

則

A

AA

B，B

C，A

CC?B

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

A。

②傳遞性。即對任意集合A、B、C，當A

B和B

C時，A

C。

定義3.1.2設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)

例如：設A=

1,2

，B=

1,

2

，C=

2,1

則A=C，A≠B

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

定義3.1.3設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)

例如：設A=

a

，B=

a,b

，C=

a,b,c

則

A

B，B

C，A

CA

A

又如，自然數(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空集是任意集合的子集。

證明：設A是任意集合。對任意對象x，由空集的定義知，x

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

?→x

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

(

x)(x

?→x

A)為真，故?

A

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

A；對任意集合A，A

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

推論

空集是惟一的。

證明：設有兩個空集?1和?2，由定理3.1.1有?1

?2和