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

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

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

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

17.2

公式的相等與蘊涵

17.3

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

2.1.1命題

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

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

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

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

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

P，讀作非P。

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

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

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

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

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

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

Q：今天下雨或者刮風(fēng)。定義2.1.3設(shè)P，Q是兩個命題，命題“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是兩個命題，命題“如果P，則Q”稱為P蘊涵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是兩個命題，命題“P當(dāng)且僅當(dāng)Q”稱為P等價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

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

Q）

R。

例2.1.2

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

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

于是，上述語句可表示為(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)我沒買蘋果，因為蘋果不甜也不紅。2.2命題公式

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

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

(2) 0、1是公式；

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

G)，(G

H)， (G

H)，(G

H)，(G

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

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

G)的括號可以省略，寫成

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

，

，

，

，

例如，我們寫符號串

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的一個解釋。設(shè)G是公式，I是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個不同原子的公式，共有2n個解釋。

例：G=(P

Q)

R，其真值表如下：

PQRG00010011010101111001101111001111

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

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

P，

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

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

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

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

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

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

和蘊涵關(guān)系

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

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

，

}，{

，

}都是完備集。

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

Q?！啊狈Q作與非聯(lián)結(jié)詞。P

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

P

Q=

(P

Q)。

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

Q，

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

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

P

Q=

(P

Q){

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

}是完備集。

P=P

PP

Q=(P

P)

(Q

Q)P

Q=(P

Q)

(P

Q)讀者可以自己證明{

}也是完備集。

§2.3.2公式的蘊涵

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

這個三角形等腰，

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

這個行列式兩行成比例，

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

若P則Q，P，所以Q。

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

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

H也都不是公式。

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

H是恒真的。例如：(P

Q)

P，(P

Q)

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

…

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

…

Gn)

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

Q共同蘊涵Q。

定理2.3.1如果H1，…，Hm，P共同蘊涵公式Q，則H1，…，Hm共同蘊涵公式P

Q。例如，因為公式P

Q，Q

R，P共同蘊涵R，所以P

Q，Q

R共同蘊涵P

R。

定理2.3.1證明：因為(H1

…

Hm

P)

Q，所以公式(H1

…

Hm

P)

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

P1

(P2

P3)=(P1

P2)

P3于是，(H1

…

Hm

P)

Q=(H1

…

Hm)

(P

Q)。故(H1

…

Hm)

(P

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

Q?！?.3.3演繹

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

G1,G2,…,Gk

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

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

并且

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

有時也記為S

G。

例設(shè)S={P

Q，Q

R，P

M，

M}則下面的公式序列:

M，P

M，

P，P

Q，Q，Q

R，R

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

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

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

H1，I滿足H2，故I滿足

H1

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

(H1

H2)。

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

G1，…，Gk

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

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

S，顯然,G1

…

G1

是恒真公式，故S

G1

，即

G1

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

(2)設(shè)i<n時，命題成立。(3)當(dāng)i=n時，若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)式及蘊涵關(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是兩個公式。如果從S∪{G}可演繹出H，則從S可演繹出G

H。證明：因為從S∪{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。

基本蘊涵式

P

Q

PP

Q

QP

P

QQ

P

Q

P

(P

Q)Q

(P

Q)

(P

Q)

P基本蘊涵式

(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公式蘊涵的證明方法真值表法；證G

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

G有如下兩種方法：

1.G1

…

Gk

G

2.形式演繹法形式演繹法根據(jù)一些基本等價式和基本蘊涵式，從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若廠方拒絕增加工資，則罷工不會停止，除非罷工超過一年并且工廠經(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亦即，罷工不會停止。第三節(jié)謂詞邏輯§3.1 謂詞邏輯的基本概念§3.2 謂詞公式§3.3 謂詞公式的等價關(guān)系和蘊含關(guān)系

§3.4 范式

§3.5 例

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

凡人必死

張三是人

張三必死

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

P

Q

R

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

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

§3.1.1謂詞和量詞定義3.1.1

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

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

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

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

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

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)粘γ}“所有人都必死”的否定的理解，相差得實在太遠了。

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

H(x)

M(x)

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

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

§3.1.1謂詞和量詞定義3.1.3

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

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

x。這時，命題P就可確切地符號化如下：

x(H(x)

M(x))

命題P的否定命題為：

P=

(

x(H(x)

M(x)))

=

x(H(x)

M(x))

亦即“有一個人是不死的”。這個命題確實是“所有人都要死”的否定。

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

P：

x(H(x)

M(x))

Q：H(張三)

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

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

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

xG(x)是這樣一個命題“對任意x

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

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

xG(x)取1值

對任意x

D，G(x)都取1值；

xG(x)取0值

有一個x0

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

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

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

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

xG(x)取1值

有一個x0

D，使G(x0)取1值；

xG(x)取0值

對所有x

D，G(x)都取0值。

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

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

xG(x)等價于G(x1)

G(x2)

…

xG(x)等價于G(x1)

G(x2)

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

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

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

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

定義3.1.4

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

變量說是約束的，如果至少一個它的出現(xiàn)是約束的；變量說是自由的，如果至少一個它的出現(xiàn)是自由的。由定義可以看出一個變量可以既是約束變量又是自由變量。例如，上例中的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é)詞，括號組成的有意義的符號串(實際是下節(jié)定義的公式)中，我們可將其中出現(xiàn)的約束變量改為另一個約束變量，這種改名必須在量詞作用區(qū)域內(nèi)各處以及該量詞符號中實行，并且改成的新約束變量要有別于改名區(qū)域中的所有其它變量。顯然改名規(guī)則不改變原符號串的真值。

例:對于

x(P(x，y)

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

u(P(u，y)

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

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公式

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

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

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

3.

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

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

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

常量符號是項；2)

變量符號是項；3)

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

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

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

的符號串。

定義3.2.2若P(x1,…,xn)是n元謂詞符號，t1,…,tn是項，則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)生成的符號

串。

§3.2.2解釋

定義3.2.4

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

對每個常量符號，指定D中一個元素；2.

對每個n元函數(shù)符號，指定一個函數(shù)，即指

定Dn到D的一個映射；3.

對每個n元謂詞符號，指定一個謂詞，即指

定Dn到{0，1}的一個映射。

§3.2.2解釋

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

例:給出如下兩個公式：

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值，簡稱I滿足G。若I不滿足G，則簡稱I弄假G。

定義3.2.6

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

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

§3.3.1公式的等價和蘊涵

定義3.3.1

公式G，H稱為等價，記以G=H，如果公式G

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

§3.3.1公式的等價和蘊涵

定義3.3.2

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

H是恒真的，并記以G

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

§3.3.1公式的等價和蘊涵

令G1=

x(H(x)

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

證明：H是G1

G2的邏輯結(jié)果。因為，設(shè)I是G1

，G2，H的一個解釋(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公式的等價和蘊涵

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

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

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

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

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

xG(x)的否定是公式

(

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

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

xG(x)都是假的。

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

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

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

G(

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

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

xA(x)

A(y)

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

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

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

xA(x)

A(c)

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

xA(x)

A(c)

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

但是，如果

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

例如，

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

xP(x)和

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

P(c)

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

Q(c)為真。

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

yA(y)

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

yA(y)

這個規(guī)則是說，如果個體域中某一元素c具有性質(zhì)A，則個體域中存在著具有性質(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)

因為(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指出下面推理中的錯誤。

§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是公式，其中自由變量有且僅有一個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的一個解釋。若

x(G(x)

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

D，G(x)

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

xG(x)

H是真命題；若H是假命題，則必然是對每個x

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

xG(x)取1值。所以

xG(x)

H在I下取1值。若

x(G(x)

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

D，使G(x0)

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

xG(x)取0值。從而

xG(x)

H在I下取0值。

證明：

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

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下對任意的x

D，使G(x)

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

xG(x)

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

(

xG(x))，則I弄假

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

D，G(x0)

是假命題，于是

G(x0)

是真命題，即

x(

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

x(

G(x))若I弄假

(

xG(x))，則I滿足

xG(x)。即對任意的x

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

D，

G(x)是假命題，于是

x(

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

x(

G(x))。若I滿足

(

xG(x))，則I弄假

xG(x)。故對任意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是兩個公式，其中自由變量有且只有一個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)的一個解釋。若

xG(x)

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

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

H(x)是真命題，即對任意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)為假，必有一個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)證明：

對任意公式G，都存在與其等價的前束范式。

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

使用基本等價

(K

H)=(K

H)

(H

K)

(K

H)=

K

H

可將公式G中的

和

刪除。定理3.4.12.

使用

(

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

放在原子之前。3.

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

使用引理1，2將所有量詞都提到公式的最左邊。于是，將公式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是一個公式，Q1x1…QnxnM是與G等價的前束范式，其中M為合取范式形式。若Qr是存在量詞，并且它左邊沒有全稱量詞，則取異于出現(xiàn)在M中所有常量符號的常量符號c，并用c代替M中所有的xr，然后在首標(biāo)中刪除Qrxr。§3.4.2Skolem范式

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

1，1

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