高等數(shù)學(xué)-第十七章數(shù)理邏輯

第十七章數(shù)理邏輯

第十七章數(shù)理邏輯17.1

命題與聯(lián)結(jié)詞

17.2

公式的相等與蘊(yùn)涵

17.3

謂詞與量詞2.1命題以及邏輯聯(lián)結(jié)詞

2.1.1命題

所謂命題是指一句有真假意義的話。例如：上海是中國(guó)最大的城市 今天是星期二 所有素?cái)?shù)都是奇數(shù) 1+1=2命題用大寫英文字母P，Q，…，P1，P2，…，表示。

如果一個(gè)命題是真的，就說它的真值是1；

如果一個(gè)命題是假的，就說它的真值是0。

也用“1”代表一個(gè)抽象的真命題，用“0”代表一個(gè)抽象的假命題。

定義2.1.1設(shè)P是一個(gè)命題，命題“P是不對(duì)的”稱為P的否定，記以

P，讀作非P。

P是真的當(dāng)且僅當(dāng)P是假的。例如：

P：吉大是中國(guó)最大的大學(xué)。

P：吉大不是中國(guó)最大的大學(xué)。定義2.1.2設(shè)P，Q是兩個(gè)命題，命題“P或者Q”稱為P，Q的析取，記以P

Q，讀作P或Q。規(guī)定P

Q是真的當(dāng)且僅當(dāng)P，Q中至少有一個(gè)是真的。例如：

P：今天下雨，Q：今天刮風(fēng)， P

Q：今天下雨或者刮風(fēng)。定義2.1.3設(shè)P，Q是兩個(gè)命題，命題“P并且Q”稱為P，Q的合取，記以P

Q，讀作P且Q。規(guī)定P

Q是真的當(dāng)且僅當(dāng)P和Q都是真的。例如，P：2

2=5，Q：雪是黑的，

P

Q：2

2=5并且雪是黑的。

定義2.1.4設(shè)P，Q是兩個(gè)命題，命題“如果P，則Q”稱為P蘊(yùn)涵Q，記以P

Q。規(guī)定，P

Q是假的當(dāng)且僅當(dāng)P是真的而Q是假的。例如，P：f(x)是可微的，Q：f(x)是連續(xù)的，

P

Q：若f(x)是可微的，則f(x)是連續(xù)的。由定義知，如果P是假命題，則不管Q是什么命題，命題“如果P，則Q”在命題邏輯中都被認(rèn)為是真命題。例如，P：2

2=5，Q：雪是黑的，

于是，命題“如果2

2=5，則雪是黑的”是真命題。定義2.1.5設(shè)P，Q是兩個(gè)命題，命題“P當(dāng)且僅當(dāng)Q”稱為P等價(jià)Q，記以P

Q。規(guī)定，P

Q是真的當(dāng)且僅當(dāng)P，Q或者都是真的，或者都是假的。例如， P：a2+b2=a2，

Q：b=0，

P

Q：a2+b2=a2當(dāng)且僅當(dāng)b=0。例2.1.1

如果你走路時(shí)看書，那么你會(huì)成為近視眼。令P：你走路；Q：你看書；R：你會(huì)成為近視眼。于是，上述語句可表示為（P

Q）

R。

例2.1.2

除非他以書面或口頭的方式正式通知我，否則我不參加明天的會(huì)議。

令P：他書面通知我；Q：他口頭通知我；R：我參加明天的會(huì)議。

于是，上述語句可表示為(P

Q)

R。

例2.1.3

設(shè)P，Q，R的意義如下：

P：蘋果是甜的；Q：蘋果是紅的；

R：我買蘋果。

試用日常語言復(fù)述下述復(fù)合命題：

(1)(P

Q)

R (2)(

P

Q)

R解：(1)如果蘋果甜且紅，那么我買。(2)我沒買蘋果，因?yàn)樘O果不甜也不紅。2.2命題公式

§2.2.1公式我們用大寫的英文字母P，Q，R，…等代表一個(gè)抽象的命題，或稱為命題符號(hào)。定義2.2.1命題符號(hào)稱為原子。例如，Q，S，…等都是原子。定義2.2.2

命題公式命題邏輯中的公式，是如下定義的一個(gè)符號(hào)串： (1) 原子是公式；

(2) 0、1是公式；

(3) 若G，H是公式，則(

G)，(G

H)， (G

H)，(G

H)，(G

H)是公式； (4) 所有公式都是有限次使用(1)，(2)，(3)

得到的符號(hào)串。規(guī)定：公式(

G)的括號(hào)可以省略，寫成

G。整個(gè)公式的最外層括號(hào)可以省略。五種邏輯聯(lián)結(jié)詞的優(yōu)先級(jí)按如下次序遞增：

，

，

，

，

例如，我們寫符號(hào)串

P

Q

R

Q

S

R

就意味著是如下公式： ((P

(Q

R))

(Q

((

S)

R)))§2.2.2解釋

定義2.2.3設(shè)G是命題公式，A1,…,An是出現(xiàn)在G中的所有原子。指定A1,…,An的一組真值，則這組真值稱為G的一個(gè)解釋。設(shè)G是公式，I是G的一個(gè)解釋，顯然，G在I下有真值，通常記為TI(G)。

例

G=P

Q，設(shè)解釋I，I’如下：

I： I’：

則TI(G)=1，TI’(G)=0PQ

11

PQ

10

定義2.2.4公式G在其所有可能的解釋下所取真值的表，稱為G的真值表。顯然，有n個(gè)不同原子的公式，共有2n個(gè)解釋。

例：G=(P

Q)

R，其真值表如下：

PQRG00010011010101111001101111001111

若公式G中出現(xiàn)的所有原子為A1，…，An，有時(shí)我們用{m1，…，mn}表示G的一個(gè)解釋I，其中

例如，上例公式G的真值表中第二個(gè)解釋就可以記為{

P，

Q，R}定義2.2.5公式G稱為恒真的(或有效的)，如果G在它的所有解釋下都是真的；

公式G稱為恒假的(或不可滿足的)，如果G在它的所有解釋下都是假的；公式G稱為可滿足的，如果它不是恒假的。考慮G1=

(P→Q)→P，G2=(P→Q)P，G3=P

P。從真值表可以看出G1對(duì)所有解釋具有“真”值，公式G3對(duì)所有解釋具有“假”值，而G2具有“真”和“假”值。PQG1PQG2PG30010000001101110101100111111G是恒真的當(dāng)且僅當(dāng)

G是恒假的。G是可滿足的當(dāng)且僅當(dāng)至少有一個(gè)解釋I，使G在I下為真。若G是恒真的，則G是可滿足的；反之不對(duì)。如果公式G在解釋I下是真的，則稱I滿足G；

如果G在解釋I下是假的，則稱I弄假G。在邏輯研究和計(jì)算機(jī)推理以及決策判斷中，人們對(duì)于所研究的命題，最關(guān)心的莫過于“真”、“假”問題，所以恒真公式在數(shù)理邏輯研究中占有特殊且重要的地位。判定問題能否給出一個(gè)可行方法，對(duì)任意的公式，判定其是否是恒真公式。因?yàn)橐粋€(gè)命題公式的解釋的數(shù)目是有窮的，所以命題邏輯的判定問題是可解的(可判定的，可計(jì)算的)，亦即，命題公式的恒真，恒假性是可判定的?！?.3 命題公式的等價(jià)關(guān)系

和蘊(yùn)涵關(guān)系

§2.3.1公式的等價(jià)定義2.3.1公式G，H說是等價(jià)的，記以G=H，如果G，H在其任意解釋I下，其真值相同。顯然，公式G，H等價(jià)的充要條件是公式G

H是恒真的。基本等價(jià)式1) (G

H)=(G

H)

(H

G)；2) (G

H)=(

G

H)；3) G

G=G，G

G=G； (等冪律)4)

G

H=H

G，G

H=H

G； (交換律)5)

G

(H

S)=(G

H)

S，

G

(H

S)=(G

H)

S； (結(jié)合律)基本等價(jià)式6) G

(G

H)=G，G

(G

H)=G； (吸收律)7)

G

(H

S)=(G

H)

(G

S)，

G

(H

S)=(G

H)

(G

S)； (分配律)8)

G

0=G，G

1=G； (同一律)9)

G

0=0，G

1=1； (零一律)10)

(G

H)=

G

H，

(G

H)=

G

H。 (摩根律)從上述眾多的等價(jià)公式可以看出，每一個(gè)命題公式的表達(dá)式是不唯一的，這種不唯一性使得人們?cè)谶M(jìn)行邏輯推理時(shí)可以有千變?nèi)f化的方式，即對(duì)于一個(gè)公式G，可根據(jù)如上等價(jià)公式，在等價(jià)的意義下，對(duì)其進(jìn)行推演，從而得到G的各種等價(jià)形式。經(jīng)驗(yàn)表明，自覺的使用邏輯規(guī)律和不自覺的使用是完全不一樣的，熟悉這些規(guī)律可以使我們的思維正確而敏銳。定義2.3.2完備集設(shè)Q是邏輯運(yùn)算符號(hào)集合，若所有邏輯運(yùn)算都能由Q中元素表示出來，而Q的任意真子集無此性質(zhì)，則稱Q是一個(gè)完備集?？梢宰C明，{

，

}，{

，

}都是完備集。

定義2.3.3與非式設(shè)P，Q是兩個(gè)命題，命題“P與Q的否定”稱為P與Q的與非式，記作P

Q。“”稱作與非聯(lián)結(jié)詞。P

Q為真當(dāng)且僅當(dāng)P，Q不同時(shí)為真。由定義可知：

P

Q=

(P

Q)。

定義2.3.4或非式設(shè)P，Q是兩個(gè)命題，命題“P或Q的否定”稱為P與Q的或非式，記作P

Q，

稱作或非聯(lián)結(jié)詞。P

Q為真當(dāng)且僅當(dāng)P，Q同時(shí)為假。由定義可知：

P

Q=

(P

Q){

}是完備集下面我們來說明{

}是完備集。

P=P

PP

Q=(P

P)

(Q

Q)P

Q=(P

Q)

(P

Q)讀者可以自己證明{

}也是完備集。

§2.3.2公式的蘊(yùn)涵

邏輯的一個(gè)重要功能是研究推理。固然，依靠等價(jià)關(guān)系可以進(jìn)行推理。但是，進(jìn)行推理時(shí)，不必一定要依靠等價(jià)關(guān)系，只需是蘊(yùn)涵關(guān)系就可以了。例如，若三角形等腰，則兩底角相等，

這個(gè)三角形等腰，

所以，這個(gè)三角形兩底角相等。又如，若行列式兩行成比例，則行列式值為0，

這個(gè)行列式兩行成比例，

所以，這個(gè)行列式值為0。上面兩個(gè)例子的推理關(guān)系涵義不同，但依據(jù)的推理規(guī)則相同，推理形式為：

若P則Q，P，所以Q。

推理的正確性與命題P，Q涵義無關(guān)，只決定于邏輯形式，命題邏輯中用公式表示命題，命題間演繹推理關(guān)系，反映為公式間邏輯蘊(yùn)涵關(guān)系。定義2.3.5蘊(yùn)涵設(shè)G，H是兩個(gè)公式。稱H是G的邏輯結(jié)果(或稱G蘊(yùn)涵H)，當(dāng)且僅當(dāng)對(duì)G，H的任意解釋I，如果I滿足G，則I也滿足H，記作G

H。注意：符號(hào)“”和“=”一樣，它們都不是邏輯聯(lián)結(jié)詞，因此，G=H，G

H也都不是公式。

是一種部分序關(guān)系。公式G蘊(yùn)涵公式H的充要條件是：公式G

H是恒真的。例如：(P

Q)

P，(P

Q)

Q定義2.3.6設(shè)G1,…,Gn，H是公式。稱H是G1,…,Gn的邏輯結(jié)果(或稱G1,…,Gn共同蘊(yùn)涵H)，當(dāng)且僅當(dāng)公式G1

…

Gn蘊(yùn)涵H。顯然，公式H是G1,…,Gn的邏輯結(jié)果的充要條件是：公式((G1

…

Gn)

H)是恒真的。例如，P，P

Q共同蘊(yùn)涵Q。

定理2.3.1如果H1，…，Hm，P共同蘊(yùn)涵公式Q，則H1，…，Hm共同蘊(yùn)涵公式P

Q。例如，因?yàn)楣絇

Q，Q

R，P共同蘊(yùn)涵R，所以P

Q，Q

R共同蘊(yùn)涵P

R。

定理2.3.1證明：因?yàn)?H1

…

Hm

P)

Q，所以公式(H1

…

Hm

P)

Q是恒真的。利用下面的基本等價(jià)公式：

P1

(P2

P3)=(P1

P2)

P3于是，(H1

…

Hm

P)

Q=(H1

…

Hm)

(P

Q)。故(H1

…

Hm)

(P

Q)是恒真的。所以H1，…，Hm共同蘊(yùn)涵P

Q?！?.3.3演繹

定義2.3.7設(shè)S是一個(gè)命題公式的集合(前提集合)。從S推出公式G的一個(gè)演繹是公式的一個(gè)有限序列：

G1,G2,…,Gk

其中，Gi或者屬于S，或者是某些

Gj(j<i)的邏輯結(jié)果。

并且

Gk就是G。我們稱公式G為此演繹的邏輯結(jié)果，或稱從S演繹出G。

有時(shí)也記為S

G。

例設(shè)S={P

Q，Q

R，P

M，

M}則下面的公式序列:

M，P

M，

P，P

Q，Q，Q

R，R

就是從S推出R的一個(gè)演繹。引理設(shè)G，H1，H2是公式。如果G蘊(yùn)涵H1，G蘊(yùn)涵H2，則G蘊(yùn)涵H1

H2。證明：任取G，H1，H2的一個(gè)解釋I。

若I滿足G，由假設(shè)知，I滿足

H1，I滿足H2，故I滿足

H1

H2。由I的任意性，所以G

(H1

H2)。

定理2.3.2設(shè)S是公式集合，G是一個(gè)公式。于是，從S演繹出G的充要條件是G是S的邏輯結(jié)果。證明：必要性，設(shè)從S演繹出G，令

G1，…，Gk

是這個(gè)演繹。對(duì)任意Gi(i=1，…，k)，往證Gi

是S的邏輯結(jié)果。對(duì)i用歸納法:(1)當(dāng)i=1時(shí)，因G1

S，顯然,G1

…

G1

是恒真公式，故S

G1

，即

G1

是S的邏輯結(jié)果。

(2)設(shè)i<n時(shí)，命題成立。(3)當(dāng)i=n時(shí)，若Gn

S，則S

Gn，歸納法完成。若Gn是某些Gj(j<n)的邏輯結(jié)果，不妨設(shè)

(Gj1

…

Gjh)

Gn

(1)

其中j1，…，jh都小于n。

由歸納假設(shè)知，S

Gjm，m=1，…，h。由引理知：S

(Gji

…

Gjh)(2)

根據(jù)(1)，(2)式及蘊(yùn)涵關(guān)系的傳遞性，得

S

Gn

即Gn是S的邏輯結(jié)果，歸納完成。

充分性，若G是S的邏輯結(jié)果，由演繹的定義知，G是如下演繹：

G1，…，Gk，G的邏輯結(jié)果，其中

G1

，…，Gk

是S中所有公式。

定理2.3.3設(shè)S是前提公式集合，G，H是兩個(gè)公式。如果從S∪{G}可演繹出H，則從S可演繹出G

H。證明：因?yàn)閺腟∪{G}可演繹出H，由定理2.3.2知，H是S∪{G}的邏輯結(jié)果。亦即

(G1

…

Gk

G)

H

其中G1，…，Gk

是S中所有公式。

由定理2.3.1知：

(G1

…

Gk)

(G

H)

即G

H是S的邏輯結(jié)果，再由定理2.3.2知，從S可演繹出G

H。

基本蘊(yùn)涵式

P

Q

PP

Q

QP

P

QQ

P

Q

P

(P

Q)Q

(P

Q)

(P

Q)

P基本蘊(yùn)涵式

(P

Q)

QP，Q

P

Q

P，P

Q

QP，P

Q

Q

Q，P

Q

PP

Q，Q

R

P

RP

Q，P

R，Q

R

R§2.3.4公式蘊(yùn)涵的證明方法真值表法；證G

H是恒真公式；利用一些基本等價(jià)式及蘊(yùn)涵式進(jìn)行推導(dǎo)；任取解釋I，若I滿足G，往證I滿足H；反證法，設(shè)結(jié)論假，往證前提假?！?.3.4公式蘊(yùn)涵的證明方法若給出前提集合S={G1，…，Gk}，公式G，證明S

G有如下兩種方法：

1.G1

…

Gk

G

2.形式演繹法形式演繹法根據(jù)一些基本等價(jià)式和基本蘊(yùn)涵式，從S出發(fā)，演繹出G，在演繹過程中遵循以下三條規(guī)則：規(guī)則1.可隨便使用前提。(根據(jù)演繹定義)規(guī)則2.可隨便使用前面演繹出的某些公式的邏輯結(jié)果。(根據(jù)演繹的定義)規(guī)則3.

如果需要演繹出的公式是P

Q的形式，則我們可將P做為附加前提使用，而力圖去演繹出Q。(根據(jù)定理2.3.3)。

例2.3.1證明{(P

Q)，(P

R)，(Q

S)}

S

R

P

Q 規(guī)則1

P

Q 規(guī)則2，根據(jù)1 Q

S 規(guī)則1

P

S 規(guī)則2，根據(jù)2，3

S

P 規(guī)則2，根據(jù)4 P

R 規(guī)則1

S

R 規(guī)則2，根據(jù)5，6 S

R 規(guī)則2，根據(jù)7。

例2.3.2證明{P

(Q

S)，

R

P，Q}

R

S

R

P 規(guī)則1 R 規(guī)則3 P 規(guī)則2，根據(jù)1，2 P

(Q

S) 規(guī)則1 Q

S 規(guī)則2，根據(jù)3，4 Q 規(guī)則1 S 規(guī)則2，根據(jù)5，6 R

S 規(guī)則3，根據(jù)2，7例2.3.3若廠方拒絕增加工資，則罷工不會(huì)停止，除非罷工超過一年并且工廠經(jīng)理辭職。問：如果廠方拒絕增加工資，而罷工又剛剛開始，罷工是否能停止?令 P：廠方拒絕增加工資；

Q：罷工停止；

R：工廠經(jīng)理辭職；

S：

罷工超過一年。

于是， G1：(P

(R

S))

Q G2：P G3：

S H：

Q我們要證明：H是{G1，G2，G3}的邏輯結(jié)果。1.

S 規(guī)則12.

S

R 規(guī)則2，根據(jù)13.

(R

S) 規(guī)則2，根據(jù)24.

P 規(guī)則15.

P

(R

S) 規(guī)則2，根據(jù)3，46.(P

(R

S))

Q 規(guī)則17.

Q 規(guī)則2，根據(jù)5，6亦即，罷工不會(huì)停止。第三節(jié)謂詞邏輯§3.1 謂詞邏輯的基本概念§3.2 謂詞公式§3.3 謂詞公式的等價(jià)關(guān)系和蘊(yùn)含關(guān)系

§3.4 范式

§3.5 例

§3.6 謂詞邏輯的應(yīng)用§3.1謂詞邏輯的基本概念§3.1.1謂詞和量詞例如，邏輯學(xué)中著名的三段論：

凡人必死

張三是人

張三必死

在命題邏輯中就無法表示這種推理過程?！?.1.1謂詞和量詞因?yàn)?，如果用P代表“凡人必死”這個(gè)命題，Q代表“張三是人”這個(gè)命題，R代表“張三必死”這個(gè)命題，則按照三段論，R應(yīng)該是P和Q的邏輯結(jié)果。但是，在命題邏輯中，R卻不是P和Q的邏輯結(jié)果，因?yàn)楣?/p>

P

Q

R

顯然不是恒真的，解釋{P，Q，

R}就能弄假上面的公式。

§3.1.1謂詞和量詞定義3.1.1

可以獨(dú)立存在的物體稱為個(gè)體。（它可以是抽象的，也可以是具體的。）如人、學(xué)生、桌子、自然數(shù)等都可以做個(gè)體。在謂詞演算中，個(gè)體通常在一個(gè)命題里表示思維對(duì)象?！?.1.1謂詞和量詞定義3.1.2

設(shè)D是非空個(gè)體名稱集合，定義在Dn上取值于{1，0}上的n元函數(shù)，稱為n元命題函數(shù)或n元謂詞。其中Dn表示集合D的n次笛卡爾乘積。一般地，一元謂詞描述個(gè)體的性質(zhì)，二元或多元謂詞描述兩個(gè)或多個(gè)個(gè)體間的關(guān)系。0元謂詞中無個(gè)體，理解為就是命題，這樣，謂詞邏輯包括命題邏輯?！?.1.1謂詞和量詞下面我們舉一個(gè)謂詞的例子：

令G(x，y)：“x高于y”，于是，G(x，y)是一個(gè)二元謂詞。將x代以個(gè)體“張三”，y代以個(gè)體“李四”，則G(張三，李四)就是命題：“張三高于李四”。隨便將x，y代以確定的個(gè)體，由G(x，y)都能得到一個(gè)命題。但是，G(x，y)不是命題，而是一個(gè)命題函數(shù)即謂詞。§3.1.1謂詞和量詞于是，用謂詞的概念可將三段論做如下的符號(hào)化：令

H(x)表示“x是人”，

M(x)表示“x必死”。則三段論的三個(gè)命題表示如下：

P：H(x)

M(x)

Q：H(張三)

R：M(張三)§3.1.1謂詞和量詞例如我們想得到“命題”P的否定“命題”，應(yīng)該就是“命題”

P。但是，

P=

(H(x)

M(x))

=

(

H(x)

M(x))

=H(x)

M(x)亦即，“命題”P的否定“命題”是“所有人都不死”。這和人們?nèi)粘?duì)命題“所有人都必死”的否定的理解，相差得實(shí)在太遠(yuǎn)了。

§3.1.1謂詞和量詞其原因在于，命題P的確切意思應(yīng)該是：“對(duì)任意x，如果x是人，則x必死”。但是

H(x)

M(x)

中并沒有確切的表示出“對(duì)任意x”這個(gè)意思，亦即H(x)

M(x)不是一個(gè)命題。因此，在謂詞邏輯中除引進(jìn)謂詞外，還需要引進(jìn)“對(duì)任意x”這個(gè)語句，及其對(duì)偶的語句“存在一個(gè)x”。

§3.1.1謂詞和量詞定義3.1.3

語句“對(duì)任意x”稱為全稱量詞，記以

x；語句“存在一個(gè)x”稱為存在量詞，記以

x。這時(shí)，命題P就可確切地符號(hào)化如下：

x(H(x)

M(x))

命題P的否定命題為：

P=

(

x(H(x)

M(x)))

=

x(H(x)

M(x))

亦即“有一個(gè)人是不死的”。這個(gè)命題確實(shí)是“所有人都要死”的否定。

§3.1.1謂詞和量詞三段論的三個(gè)命題，在謂詞邏輯中是如下這樣表示的：

P：

x(H(x)

M(x))

Q：H(張三)

R：M(張三)以后可以證明：在謂詞邏輯中，R是P和Q的邏輯結(jié)果。

§3.1.1謂詞和量詞設(shè)G(x)是一元謂詞，任取x0

D，則G(x0)是一個(gè)命題。于是

xG(x)是這樣一個(gè)命題“對(duì)任意x

D，都有G(x)”。故對(duì)命題

xG(x)的真值做如下規(guī)定：

xG(x)取1值

對(duì)任意x

D，G(x)都取1值；

xG(x)取0值

有一個(gè)x0

D，使G(x0)取0值?！?.1.1謂詞和量詞

xG(x)是命題“存在一個(gè)x0

D，使得G(x0)成立”。對(duì)命題

xG(x)的真值規(guī)定如下：

xG(x)取1值

有一個(gè)x0

D，使G(x0)取1值；

xG(x)取0值

對(duì)所有x

D，G(x)都取0值。

§3.1.1謂詞和量詞當(dāng)D={x0

，x1，…}是可數(shù)集合時(shí)，

xG(x)等價(jià)于G(x1)

G(x2)

…

xG(x)等價(jià)于G(x1)

G(x2)

…§3.1.1謂詞和量詞對(duì)于一個(gè)謂詞，如果其中每一個(gè)變量都在一個(gè)量詞作用之下。則它就不再是命題函數(shù)，而是一個(gè)命題了。但是，這種命題和命題邏輯中的命題畢竟有所不同。因?yàn)榻K歸這種命題里還有變量，當(dāng)然這種變量和命題函數(shù)中的變量還有區(qū)別。使用量詞時(shí)應(yīng)注意以下幾個(gè)問題：

1.量詞的論域，即D中都有那些元素；

2.在多重量詞時(shí)，應(yīng)注意量詞的順序；

3.量詞的作用域?！?.1.2改名規(guī)則

定義3.1.4

在一個(gè)由謂詞，量詞，邏輯聯(lián)結(jié)詞，括號(hào)組成的有意義的符號(hào)串(實(shí)際是指下一節(jié)將嚴(yán)格定義的公式)中，變量的出現(xiàn)說是約束的，當(dāng)且僅當(dāng)它出現(xiàn)在使用這個(gè)變量的量詞范圍之內(nèi)；變量的出現(xiàn)說是自由的，當(dāng)且僅當(dāng)這個(gè)出現(xiàn)不是約束的。例如，

x(P(x，y)

Q(x，z))

R(x)。從左向右算起，變量x的第一，第二次出現(xiàn)是約束的，第三次出現(xiàn)是自由的；變量y，z的出現(xiàn)是自由的。

§3.1.2改名規(guī)則

定義3.1.5

變量說是約束的，如果至少一個(gè)它的出現(xiàn)是約束的；變量說是自由的，如果至少一個(gè)它的出現(xiàn)是自由的。由定義可以看出一個(gè)變量可以既是約束變量又是自由變量。例如，上例中的x既是約束變量，又是自由變量；y，z只是自由變量。

§3.1.2改名規(guī)則

顯然，

xG(x)與

yG(y)的真值一樣，

xG(x)與

yG(y)的真值一樣，亦即，謂詞邏輯中的命題的真值，與命題中的約束變量的記法無關(guān)。這就引出了謂詞邏輯中的改名規(guī)則。

§3.1.2改名規(guī)則

在由謂詞，量詞，邏輯聯(lián)結(jié)詞，括號(hào)組成的有意義的符號(hào)串(實(shí)際是下節(jié)定義的公式)中，我們可將其中出現(xiàn)的約束變量改為另一個(gè)約束變量，這種改名必須在量詞作用區(qū)域內(nèi)各處以及該量詞符號(hào)中實(shí)行，并且改成的新約束變量要有別于改名區(qū)域中的所有其它變量。顯然改名規(guī)則不改變?cè)?hào)串的真值。

例:對(duì)于

x(P(x，y)

Q(x，z))，可改名為

u(P(u，y)

Q(u，z))。但下面的改名都是不對(duì)的：

a.

u(P(u，y)

Q(x，z))

b.

x(P(u，y)

Q(u，z))

c.

u(P(x，y)

Q(x，z))

d.

y(P(y，y)

Q(y，z))

e.

z(P(z，y)

Q(z，z))§3.2謂詞公式

§3.2.1公式

在形式化中，我們將使用如下四種符號(hào)：1.

常量符號(hào)：用小寫英文字母a，b，c，…表示，當(dāng)個(gè)體名稱集合D給出時(shí)，它可以是D中某個(gè)元素。2.

變量符號(hào)：用小寫英文字母x，y，z，…表示，當(dāng)個(gè)體名稱集合D給出時(shí)，D中任意元素可代入變量符號(hào)?！?.2.1公式

3.

函數(shù)符號(hào)：用小寫英文字母f，g，…表示，當(dāng)個(gè)體名稱集合D給出時(shí)，n元函數(shù)符號(hào)f(x1，…，xn)可以是Dn到D的任意一個(gè)映射。4.

謂詞符號(hào)：用大寫英文字母P，Q，R，…表示，當(dāng)個(gè)體名稱集合D給出時(shí)，n元謂詞符號(hào)P(x1，…，xn)可以是Dn上的任意一個(gè)謂詞。

定義3.2.1項(xiàng)謂詞邏輯中的項(xiàng)，被遞歸定義為：1)

常量符號(hào)是項(xiàng)；2)

變量符號(hào)是項(xiàng)；3)

若f(x1,…,xn)是n元函數(shù)符號(hào)，t1,…,tn

是項(xiàng)，則f(t1,…,tn)是項(xiàng)；4)

所有項(xiàng)都是有限次使用1)，2)，3)生成

的符號(hào)串。

定義3.2.2若P(x1,…,xn)是n元謂詞符號(hào)，t1,…,tn是項(xiàng)，則P(t1,…,tn)是原子。

定義3.2.3公式

謂詞邏輯中的公式，被遞歸定義如下：1)

原子是公式；2)

若G，H是公式，則(

G)，(G

H)，(G

H)，

(G

H)，(G

H)是公式；3)

若G是公式，x是G中的自由變量，則

xG，

xG是公式；4)

所有公式都是有限次使用1)～3)生成的符號(hào)

串。

§3.2.2解釋

定義3.2.4

謂詞邏輯中公式G的一個(gè)解釋I，是由非空區(qū)域D和對(duì)G中常量符號(hào)，函數(shù)符號(hào)，謂詞符號(hào)以下列規(guī)則進(jìn)行的一組指定組成：1.

對(duì)每個(gè)常量符號(hào)，指定D中一個(gè)元素；2.

對(duì)每個(gè)n元函數(shù)符號(hào)，指定一個(gè)函數(shù)，即指

定Dn到D的一個(gè)映射；3.

對(duì)每個(gè)n元謂詞符號(hào)，指定一個(gè)謂詞，即指

定Dn到{0，1}的一個(gè)映射。

§3.2.2解釋

今后我們對(duì)討論的公式做如下規(guī)定：公式中無自由變量，或?qū)⒆杂勺兞靠醋龀Ａ俊?/p>

例:給出如下兩個(gè)公式：

1)G=

x(P(f(x))

Q(x，f(a)))

2)H=

x(P(x)

Q(x，a))給出如下的解釋I：

D={2，3}

a

2

f(2)f(3)

32

P(2)P(3)Q(2,2)Q(2,3)Q(3,2)Q(3,3)

011101例:TI(G) =TI((P(f(2))

Q(2，f(2)))

(P(f(3))

Q(3，f(2))))

=TI((P(3)

Q(2，3))

(P(2)

Q(3，3)))

=(1

1)

(0

0)

=1TI(H) =TI(P(2)

Q(2，2)

P(3)

Q(3，2))

=0

1

1

0

=0定義3.2.5

公式G稱為可滿足的，如果存在解釋I，使G在I下取1值，簡(jiǎn)稱I滿足G。若I不滿足G，則簡(jiǎn)稱I弄假G。

定義3.2.6

公式G稱為是恒假的(或不可滿足的)，如果不存在解釋I滿足G；公式G稱為恒真的，如果G的所有解釋I都滿足G。

§3.3謂詞公式的等價(jià)關(guān)系和蘊(yùn)含關(guān)系

§3.3.1公式的等價(jià)和蘊(yùn)涵

定義3.3.1

公式G，H稱為等價(jià)，記以G=H，如果公式G

H是恒真的。由定義顯然可以看出：公式G，H等價(jià)的充要條件是：對(duì)G，H的任意解釋I，G，H在I下的真值相同。因?yàn)閷?duì)任意公式G，H，在解釋I下，G，H就是兩個(gè)命題，所以命題邏輯中給出的基本等價(jià)式，在謂詞邏輯中仍然成立。

§3.3.1公式的等價(jià)和蘊(yùn)涵

定義3.3.2

設(shè)G，H是公式，稱G蘊(yùn)涵H，或H是G的邏輯結(jié)果，如果公式G

H是恒真的，并記以G

H。顯然，對(duì)任意兩個(gè)公式G，H，G蘊(yùn)涵H的充要條件是：對(duì)任意解釋I，若I滿足G，則I必滿足H。同樣，命題邏輯中的基本蘊(yùn)涵式仍成立。

§3.3.1公式的等價(jià)和蘊(yùn)涵

令G1=

x(H(x)

M(x))，G2=H(a)，H=M(a)

證明：H是G1

G2的邏輯結(jié)果。因?yàn)?，設(shè)I是G1

，G2，H的一個(gè)解釋(I指定a為張三)，且I滿足G1

G2，即I滿足

x(H(x)

M(x))

H(a)

所以，I滿足M(a)。否則，令M(a)在I下為假，而H(a)在I下為真，于是H(a)

M(a)在I下為假，故

x(H(x)

M(x))在I下為假，矛盾!

故M(a)在I下為真命題，而I指定a為“張三”，故M(張三)為真命題。§3.3.1公式的等價(jià)和蘊(yùn)涵

由于謂詞邏輯中的恒真(恒假)公式，要求所有解釋I都滿足(弄假)該公式。而解釋I依賴于一個(gè)非空集合D。由于集合D可以是無窮集合，而集合D的“數(shù)目”也可能是無窮多個(gè)，因此，所謂公式的“所有”解釋，實(shí)際上是無法考慮的。這就使得謂詞邏輯中公式的恒真，恒假性的判斷變得異常困難。1936年Church和Turing分別獨(dú)立地證明了：對(duì)于謂詞邏輯，判定問題是不可解的。

設(shè)G(x)是一元謂詞符號(hào)，若公式

xG(x)是恒真公式，則這件事實(shí)可被敘述為如下的一個(gè)真命題：對(duì)任意一元謂詞G(x)，命題

xG(x)都是真的。但是，如果想把這個(gè)命題加以否定，則在謂詞邏輯中是辦不到的。因?yàn)椋?)這個(gè)命題的否定，應(yīng)該是如下命題：有一個(gè)一元謂詞G(x)，使得命題

xG(x)是假的。2)公式

xG(x)的否定是公式

(

xG(x))。而后一個(gè)公式表示的命題是：公式

xG(x)是恒假的，亦即，對(duì)任意一元謂詞G(x)，命題

xG(x)都是假的。

1)和2)所表示出的事實(shí)相差得太遠(yuǎn)了。發(fā)生這件事的原因是：用“公式

xG(x)是恒真的”來表達(dá)命題“對(duì)任意一元謂詞G(x)，命題

xG(x)都是真的”是不確切的。確切地，后一個(gè)命題，應(yīng)該用“公式

G(

xG(x))是恒真的”來表達(dá)。

這個(gè)公式中，不僅有關(guān)于個(gè)體變量x的量詞，而且有關(guān)于謂詞變量(即謂詞符號(hào)，亦即原子)的量詞。由這樣的公式組成的系統(tǒng)就稱為高階邏輯。高階邏輯中，不僅判定問題不可解，甚至連一個(gè)完備的公理系統(tǒng)都沒有?！?.3.2謂詞演算的推理理論前提引入規(guī)則：在證明的任何步驟上都可以引用前提。結(jié)論引入規(guī)則：在證明的任何步驟上所得到的結(jié)論都可以在其后的證明中引用。置換規(guī)則：在證明的任何步驟上，公式的子公式都可以用與之等價(jià)的其他公式置換。代入規(guī)則：在證明的任何步驟上，恒真公式中的任一原子都可以用一公式代入，得到的仍是恒真的公式。全稱特定化規(guī)則(US)：

xA(x)

A(y)

這里的A(y)是將A(x)中的x處代以y。要求y在A(x)中不約束出現(xiàn)。這里自由變量y也可以寫成個(gè)體常量c，這時(shí)c為個(gè)體域中任意一個(gè)確定的個(gè)體。

這個(gè)規(guī)則的意思是說，如果個(gè)體域的所有元素都具有性質(zhì)A，則個(gè)體域中的任一個(gè)元素具有性質(zhì)A。

存在特定化規(guī)則(ES)：

xA(x)

A(c)

存在特定化規(guī)則(ES)：

xA(x)

A(c)

這里c是個(gè)體域中的某個(gè)確定的個(gè)體。這個(gè)規(guī)則是說，如果個(gè)體域中存在有性質(zhì)A的元素，則個(gè)體域中必有某一元素c具有性質(zhì)A。

但是，如果

xA(x)中有其它自由變量出現(xiàn)，且x是隨其它自由變量的值而變，那么就不存在唯一的c使得A(c)對(duì)自由變量的任意值都是成立的。這時(shí)，就不能應(yīng)用存在特定化規(guī)則。

例如，

x(x=y)中，x、y的論域是實(shí)數(shù)集合。若使用ES規(guī)則，則得c=y，即在實(shí)數(shù)集中有一實(shí)數(shù)c，等于任意實(shí)數(shù)y。結(jié)論顯然不成立，這是因?yàn)锳(x)：x=y中的x依賴于自由變量y，此時(shí)不能使用ES規(guī)則。另外，要注意的是，如果

xP(x)和

xQ(x)都真，則對(duì)于某個(gè)c和某個(gè)d，可以斷定

P(c)

Q(d)必真，但不能斷定P(c)

Q(c)為真。

全稱一般化規(guī)則(UG)：A(x)

yA(y)

這個(gè)規(guī)則是說，如果個(gè)體域中任意一個(gè)個(gè)體都具有性質(zhì)A，則個(gè)體域中的全體個(gè)體都具有性質(zhì)A。這里要求x必須為自由變量，并且y不出現(xiàn)在A(x)中。存在一般化規(guī)則(EG)：A(c)

yA(y)

這個(gè)規(guī)則是說，如果個(gè)體域中某一元素c具有性質(zhì)A，則個(gè)體域中存在著具有性質(zhì)A的元素。這里要求y不在A(c)中出現(xiàn)。

證明： （1）

x(P(x)

Q(x))

前提 （2）P(c)

Q(c) (1)；US

（3）P(c)

前提 （4）Q(c) (2),(3)

例3.3.1

證明:

x(P(x)

Q(x))

P(c)

Q(c)證明：用反證法，假設(shè)

xQ(x)成立。

x

P(x)

前提

P(y) (1)；US

xQ(x)

假設(shè)

x

Q(x) (3)

Q(y) (4)；US

P(y)

Q(y) (2)，(5)

例3.3.2證明：

x(P(x)

Q(x)),

x

P(x)

xQ(x)

(P(y)

Q(y)) (6)

x(P(x)

Q(x))

前提

P(y)

Q(y) (8),US (P(y)

Q(y))

(P(y)

Q(y)) (7),(9)

因?yàn)?P(y)

Q(y))

(P(y)

Q(y))是恒假公式，所以

x(P(x)

Q(x))，

x

P(x)

xQ(x)。

（1）

x(F(x)

G(x))

前提（2）F(c)

G(c) （1），ES（3）F(c) （2）（4）

y(H(y)

I(y))

前提（5）H(c)

I(c) （4）（6）H(c) （5）（7）F(c)

H(c)

（3）,（6）（8）

x(F(x)

H(x))

（7），EG。

例3.3.3指出下面推理中的錯(cuò)誤。

§3.4范式定義3.4.1

謂詞邏輯中公式G稱為前束范式，如果G有如下形狀：

Q1x1…QnxnM

其中

Qixi或者是

xi，或者是

xi，i=1，…，n，M是不含量詞的公式，Q1x1…Qnxn稱為首標(biāo)，M稱為母式。例如，

x

y

z(P(x，y)

Q(x，z))

x

y

zP(x，y，z)§3.4.1前束范式

設(shè)G是公式，其中自由變量有且僅有一個(gè)x，記以G(x)，H是不含變量x的公式，于是有：1)

x(G(x)

H)=

xG(x)

H1’)

x(G(x)

H)=

xG(x)

H2)

x(G(x)

H)=

xG(x)

H2’)

x(G(x)

H)=

xG(x)

H3)

(

xG(x))=

x(

G(x))4)

(

xG(x))=

x(

G(x))引理1

1)

設(shè)I是G(x)和H的一個(gè)解釋。若

x(G(x)

H)在I下取1值，則在I下，對(duì)任意x

D，G(x)

H都是真命題。若H是真命題，則

xG(x)

H是真命題；若H是假命題，則必然是對(duì)每個(gè)x

D，G(x)都是真命題，故

xG(x)取1值。所以

xG(x)

H在I下取1值。若

x(G(x)

H)在I下取0值，則必有一個(gè)x0

D，使G(x0)

H在I下取0值。故G(x0)為假命題，并且H為假命題。所以

xG(x)取0值。從而

xG(x)

H在I下取0值。

證明：

（1）‘的證明設(shè)I是G(x)和H的一個(gè)解釋。若

x(G(x)

H)在I下取1值，則在I下，存在x0

D，G(x0)

H是真命題。若H是真命題，則

xG(x)

H是真命題；若H是假命題，則必然有G(x0)是真命題，故

xG(x)取1值。所以

xG(x)

H在I下取1值。若

x(G(x)

H)在I下取0值，則在I下對(duì)任意的x

D，使G(x)

H在I下取0值。故G(x)和H都為假命題，所以

xG(x)

H在I下取0值。（3）的證明若I滿足

(

xG(x))，則I弄假

xG(x)。則必有某一個(gè)x0

D，G(x0)

是假命題，于是

G(x0)

是真命題，即

x(

G(x))在I下是真命題，故I滿足

x(

G(x))若I弄假

(

xG(x))，則I滿足

xG(x)。即對(duì)任意的x

D，有G(x)是真命題。也就是對(duì)任意的x

D，

G(x)是假命題，于是

x(

G(x))是假命題，故I弄假

x(

G(x))。若I滿足

(

xG(x))，則I弄假

xG(x)。故對(duì)任意x

D，G(x)都是假命題，從而

G(x)都是真命題，故I滿足

x(

G(x))若I弄假

(

xG(x))，則I滿足

xG(x)。故有x0

D，使得G(x0)是真命題。從而

G(x0)是假命題，故I弄假

x(

G(x))。證明：

設(shè)G，H是兩個(gè)公式，其中自由變量有且只有一個(gè)x，分別記以G(x)，H(x)，于是有：1)

xG(x)

xH(x)=

x(G(x)

H(x))2)

xG(x)

xH(x)=

x(G(x)

H(x))3)

xG(x)

xH(x)=

x

y(G(x)

H(y))4)

xG(x)

xH(x)=

x

y(G(x)

H(y))引理2設(shè)I是G(x)和H(x)的一個(gè)解釋。若

xG(x)

xH(x)在I下取1值，則在解釋I下，對(duì)任意x

D，G(x)、H(x)都是真命題，所以G(x)

H(x)是真命題，即對(duì)任意x

D，G(x)

H(x)是真命題，所以

x(G(x)

H(x))在I下取1值。若

xG(x)

xH(x)在I下取0值，則

xG(x)為假，或

xH(x)為假，若

xG(x)為假，必有一個(gè)x0

D，使G(x0)在I下取0值，所以G(x0)

H(x0)為假命題，所以

x(G(x)

H(x))在I下取0值。若

xH(x)為假，同理可證。1)證明：

xG(x)

xH(x)

=

xG(x)

yH(y)

改名規(guī)則=

x(G(x)

yH(y))

引理1

=

x

y(G(x)

H(y))

引理13)證明：

對(duì)任意公式G，都存在與其等價(jià)的前束范式。

證明：通過如下算法，可將公式G化成等價(jià)的前束范式。1.

使用基本等價(jià)

(K

H)=(K

H)

(H

K)

(K

H)=

K

H

可將公式G中的

和

刪除。定理3.4.12.

使用

(

H)=H，摩根律，引理1，可將公式中所有否定號(hào)

放在原子之前。3.

如果必要的話，則將約束變量改名。4.

使用引理1，2將所有量詞都提到公式的最左邊。于是，將公式G在等價(jià)意義下化成了一個(gè)前束范式。

x

y(

z(P(x,z)

P(y,z))

uQ(x,y,u))=

x

y(

(

z(P(x,z)

P(y,z)))

uQ(x,y,u))=

x

y(

z(

P(x,z)

P(y,z))

uQ(x,y,u))=

x

y

z(

P(x,z)

P(y,z)

uQ(x,y,u))=

x

y

z

u(

P(x,z)

P(y,z)

Q(x,y,u))例3.4.1定義3.4.2

設(shè)G是一個(gè)公式，Q1x1…QnxnM是與G等價(jià)的前束范式，其中M為合取范式形式。若Qr是存在量詞，并且它左邊沒有全稱量詞，則取異于出現(xiàn)在M中所有常量符號(hào)的常量符號(hào)c，并用c代替M中所有的xr，然后在首標(biāo)中刪除Qrxr?！?.4.2Skolem范式

若Qs1,…,Qsm是所有出現(xiàn)在Qrxr左邊的全稱量詞(m

1，1

s1<s2<…<sm<r)，則取異于出現(xiàn)在M中所有函數(shù)符號(hào)的m元函數(shù)符號(hào)f(xs1,…,xsm)，用f(xs1,…,xsm)