IT計(jì)算機(jī)課件離散數(shù)學(xué)2

一第二章干謂,詞邏_輯(PredicateLogic)

2.1謂詞的木既念與表示(Predicateanditsexpression)

2?2t胃詞公式與番刈譯(Predicateformulae)

2.3變兀的約束(Boundofvariable)

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

implicationsofpredicatecalculus)

2.5前束范式(Prenexnormalform)

2?6謂詞^寅算的推理理論(Inferencetheoryof

predicatecalculus)

2012-6-22

天津過＞丈學(xué)

第二章謂詞邏輯(PredicateLogic)

2.1謂詞的概念與表示(PredicateandItsExpression)

-命題邏輯的局限性：

在命題邏輯中，命題是命題演算的基本

單位，不再對原子命題進(jìn)行分解，因而無法

研究命題的內(nèi)部結(jié)構(gòu)、成分及命題之間的內(nèi)

在聯(lián)系，甚至無法處理一些簡單而又常見的

推理過程。

2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.1謂詞的概念與表示(PredicateandItsExpression)

■例如，下列推理:

所有的人都是要死的。

蘇格拉底是人。

蘇格拉底是要死的。

眾所周知,這是真命題。但在命題邏輯中，如

果用P,Q,R表示以上三個(gè)命題，則上述推理過

程為：(PAQ)-R。借助命題演算的推理理

論不能證明其為重言式。

2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.1謂詞的概念與表示(PredicateandItsExpression)

原因：命題邏輯不能將命題之間的內(nèi)在聯(lián)系

和數(shù)量關(guān)系反映出來。

解決辦法：將命題進(jìn)行分解。

燃622

第二章謂詞邏輯(PredicateLogic)

2.1謂詞的概念與表示(PredicateandItsExpression)

2.1謂詞的概念與表示(Predicateandits

expression)

2.1.1客體和謂詞

在謂詞邏輯中，可將原子命題劃分為客體

和謂詞兩部分。

客體：可以獨(dú)立存在的具體事物的或抽象的概

念。例如，電子計(jì)算機(jī)、李明、玫瑰花、黑

板、實(shí)數(shù)、中國、思想、唯物主義等，客體也

可稱之為主語。

2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.1謂詞的概念與表示(PredicateandItsExpression)

謂詞：用來刻劃客體的性質(zhì)或客體之間的相互關(guān)系的詞O

例如在下面命題中：

(1)張明是個(gè)勞動(dòng)模范。

(2)李華是個(gè)勞動(dòng)模范。［刻劃客體的性質(zhì)

(3)王紅是個(gè)大學(xué)生。,

(4)小李比小趙高2c

(5)點(diǎn)a在b與c之間。:刻劃客體之間的相互關(guān)系

(6)阿杜與阿寺同歲。,

“是個(gè)勞動(dòng)模范”、“是個(gè)美學(xué)生”、“…比…高2cm”、

2皿羊…與…之間”都是謂----------——

第二章謂詞邏輯(PredicateLogic)

2.1謂詞的概念與表示(PredicateandItsExpression)

■刻劃一個(gè)客體性質(zhì)的詞稱之為一元謂詞，刻劃n個(gè)客體

之間關(guān)系的詞稱之為n元謂詞.

■一般我們用大寫英文字母表示謂詞，用小寫英文字母

表示客體名稱，例如，將上述謂詞分別記作大寫字母F、

G、H、R,S則上述命題可表示為：

(1)F(a)a：張明(2)F(b)b：李華

(3)G(c)c：王紅(4)H(s,t)s：小李t：小趙

(5)R(a5b9c)(6)S(a,b)a:阿杜。b:阿寺。

其中(1)、(2)、(3)為一元謂詞，(4)、(6)為二元謂詞，

(5)為三兀謂詞。

2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.1謂詞的概念與表示(PredicateandItsExpression)

■注：

-(1)單獨(dú)一個(gè)謂詞并不是命題，在謂詞字母

后填上客體所得到的式子稱之為謂詞填式。

■(2)在謂詞填式中，若客體確定，則A(a工，

az-.an)就變成了命題

■(3)在多元謂詞表達(dá)式中，客體字母出現(xiàn)的

先后次序與事先約定有關(guān)，一般不可以隨意交

換位置(如,上例中H⑸t)與H(t,§)代表兩個(gè)不

同的命題)。

2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.1謂詞的概念與表示(PredicateandItsExpression)

■設(shè)謂詞H表示“是勞動(dòng)模范”，a表示客體名稱

張明,b表示客體名稱李華,c表示客體名稱這只老

虎,那么H(a)、H(b)、H(c)表示三個(gè)不同的命

題，但它們有一個(gè)共同的形式，即H(x).一般地，

H(x)表示客體x具有性質(zhì)H。這里x表示抽象的或

泛指的客體，稱為客體變元，常用小寫英文字母

x,y,z,…表示。相應(yīng)地，表示具體或特定的客體

的詞稱大客體常項(xiàng)，常用小寫英文字母a,b,c,…表

z]\o

2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.1謂詞的概念與表示(PredicateandItsExpression)

同理，客體變元x,y具有關(guān)系L,記作L(x,y);

客體變元x,y,z具有關(guān)系A(chǔ),記作A(x,y,z).

■H(x)、L(x,y)、A(x,y,z)本身并不是一個(gè)命題.只

有用特定的客體取代客體變元x,y,z后，它們才成為

命題。我們稱H(x)、L(x,y)、A(x,y,z)為命題函數(shù)。

一般地我們有

2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.1謂詞的概念與表示(PredicateandItsExpression)

■定義2.L1:由一個(gè)謂詞H和n個(gè)客體變元組成的表

達(dá)式H(X1,X2,…,Xn)稱為n元簡單命題函數(shù).

-由定義可知,11元謂詞就是有II個(gè)客體變元的命題

函數(shù).當(dāng)11=0時(shí)，稱為0元謂詞.因此，一般情況下，命題

函數(shù)不是命題;特殊情況0元謂詞就變成一個(gè)命題.

■復(fù)合命題函數(shù):由一個(gè)或幾個(gè)簡單命題函數(shù)以及

邏輯聯(lián)結(jié)詞組合而成的表達(dá)式.

2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.1謂詞的概念與表示(PredicateandItsExpression)

例1:若x的學(xué)習(xí)好，則x的工作好

設(shè)S(x):x學(xué)習(xí)好；W(x):x工作好

則有S(x)TW(x)

例2:將下列命題用0元謂詞符號化.

⑴2是素?cái)?shù)且是偶數(shù).

(2)如果2大于3,則2大于4.

⑶如果張明比李民高,李民比趙亮高，則張明比趙亮

高.

2012-6-22

第二章謂詞邏輯(PredicateLogic)

j.2.1謂詞的概念與表示(PredicateandItsExpression)

■解:⑴設(shè)F(x):x是素?cái)?shù).G(x):x是偶數(shù).

則命題符號化為：F(2)AG(2)

⑵設(shè)L(x,y)：x大于y.

則命題符號化為：L(2,3)TL(2,4)

(3)設(shè)H(x,y):x比y高.a:張明b:李民c：趙亮

則命題符號化為：H(a,b)AH(b,c).H(a,c)

注意:命題函數(shù)中，客體變元在哪些范圍內(nèi)取特定的

值，對命題的真值極有影響.

2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.1謂詞的概念與表示(PredicateandItsExpression)

例如：H(x,y)AH(y,z)->H(x,z)

■若H(x,y)解釋為：x大于y,當(dāng)x,y,z都在實(shí)數(shù)中取值時(shí),

則這個(gè)式子表示“若x大于y且y大于z,貝k大于

z”。這是一個(gè)永真式。

如果H(x,y)解釋為：“x是y的兒子”，當(dāng)x,y/都指人時(shí),

則這個(gè)式子表示“若x為y的兒子且y是z的兒子，

則x是z的兒子”。這是一個(gè)永假式。

如果H(x,y)解釋為："x距y10米”,當(dāng)羽y,z為平面上的

點(diǎn)，則這個(gè)式子表示“若x距ylO米且y距Z10米，則

x距Z10米”。這個(gè)命題的真值將由x,y,z的具體位

置而定，它可能是L也可能是0。

2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.1謂詞的概念與表示(PredicateandItsExpression)

■在命題函數(shù)中，客體變元的取值范圍稱為個(gè)體

域，又稱之為論域。個(gè)體域可以是有限事物的

集合，也可以是無限事物的集合。

■全總個(gè)體域：宇宙間一切事物組成的個(gè)體域稱

為全總個(gè)體域。

2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.1謂詞的概念與表示(PredicateandItsExpression)

■2.1.2量詞(Quantifiers)

■量詞：分為全稱量詞(V)和存在量詞Q)

L全稱量詞(TheUniversalQuantifiers)

對日常語言中的“一切”、“所有”、“凡”、

“每一

個(gè)”、“任意”等詞，用符號“V”表示，Vx

表示

對個(gè)體域里的所有個(gè)體，VxF(x)表示個(gè)體域

里魁所有個(gè)體具有性質(zhì)F.符號稱為人…

1HI-

第二章謂詞邏輯(PredicateLogic)

[2.1謂詞的概念與表示(PredicateandItsExpression)

例3：在謂詞邏輯中將下列命題符號化.

(1)凡是人都呼吸。

(2)每個(gè)學(xué)生都要參加考試。

(3)任何整數(shù)或是正的或是負(fù)的。

解：(1)當(dāng)個(gè)體域?yàn)槿祟惣蠒r(shí)：

令F(x):x呼吸。則(1)符號化為VxF(x)

當(dāng)個(gè)體域?yàn)槿倐€(gè)體域時(shí)：

令M(x):x是人。則(1)符號化為

Vx(M(x).F(x)).

2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.1謂詞的概念與表示(PredicateandItsExpression)

(2)當(dāng)個(gè)體域?yàn)槿w學(xué)生的集合時(shí):

令P(x):x要參加考試。則(2)符號化為

VxP(x)

當(dāng)個(gè)體域?yàn)槿倐€(gè)體域時(shí)：

令S(x):x是學(xué)生。則(2)符號化為

Vx(S(x).P(x)).

2012-6-22

第二章謂詞邏輯(PredicateLogic)

.2.1謂詞的概念與表示(PredicateandItsExpression)

⑶當(dāng)個(gè)體域?yàn)槿w整數(shù)的集合時(shí)：

令P(x):x是正的。N(x):x是負(fù)的。則(3)符

號化為

Vx(P(x)VN(x))

當(dāng)個(gè)體域?yàn)槿倐€(gè)體域時(shí)：

令I(lǐng)(x):x是整數(shù)。則(3)符號化為

Vx(I(x)t(P(x)VN(x))).

2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.1謂詞的概念與表示(PredicateandItsExpression)

2.存在量詞(TheExistentialQuantifiers)

對日常語言中的“有一個(gè)”、“有的”、“存在

著”、

“至少有一個(gè)"、“存在一些”等詞，用符號

“三,,

表示，mx表示存在個(gè)體域里的個(gè)體，

3xF(x)表示存在個(gè)體域里的個(gè)體具有性質(zhì)F.

符號"才'稱為存在量詞.

例4：在謂詞邏輯中將下列命題符號化.

一些數(shù)是有理數(shù)------------------

育此人9壬而歸四一

第二章謂詞邏輯(PredicateLogic)

2.1謂詞的概念與表示(PredicateandItsExpression)

解：(1)令Q(x):x是有理數(shù)。貝I」(1)符號化為

3xQ(x)

(2)當(dāng)個(gè)體域?yàn)槿祟惣蠒r(shí)：

令G(x):x活百歲以上。則(2)符號化為

3xG(x)

當(dāng)個(gè)體域?yàn)槿倐€(gè)體域時(shí)：

令M(x):x是人。則(2)符號化為

3x(M(x)AG(x))

2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.1謂詞的概念與表示(PredicateandItsExpression)

有時(shí)需要同時(shí)使用多個(gè)量詞。

例5.命題“對任意的x,存在y,使得x+y=5"，取

個(gè)

體域?yàn)閷?shí)數(shù)集合，則該命題符號化為：

Vx3yH(x,y).

其中H(x,y):x+y=5.這是個(gè)真命題.

2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.1謂詞的概念與表示(PredicateandItsExpression)

3.使用量詞時(shí)應(yīng)注意的問題

(1)在不同的個(gè)體域，同一命題的符號化形式

可能相同也可能不同。

(2)在不同的個(gè)體域，同一命題的真值可能相

同也可能不同。(如,R(x)表示x為大學(xué)生。如

果個(gè)體域?yàn)榇髮W(xué)里的某個(gè)班級的學(xué)生，則

VxR(x)為真；若個(gè)體域?yàn)橹袑W(xué)里的某個(gè)班

級的學(xué)生,則VxR(x)為假?).

2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.1謂詞的概念與表示(PredicateandItsExpression)

(3)約定以后如不指定個(gè)體域，默認(rèn)為全總個(gè)體

域。對每個(gè)客體變元的變化范圍，用特性謂詞加

以限制.

特性謂詞:限定客體變元變化范圍的謂詞(如例3中

的M(x)).

一般而言，對全稱量詞，特性謂詞常作蘊(yùn)含的前

件，如(Vx)(M(x)fF(x))；對存在量詞，特性

謂詞常作合取項(xiàng)，如(3x)(M(x)AG(x)).

2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.1謂詞的概念與表示(PredicateandItsExpression)

(4)一般來說，當(dāng)多個(gè)量詞同時(shí)出現(xiàn)時(shí)，它們的順

序不能隨意調(diào)換。如：

在實(shí)數(shù)域上用H(x,y)表示x+y=5,則命題“對于任

意的x,都存在y使得x+y=5"可符號化為：

VxmyH(x,y),其真值為1.若調(diào)換量詞順序后為：

3yVxH(x,y),其真值為0。

⑸當(dāng)個(gè)體域?yàn)橛邢藜蠒r(shí)，如D={ai,a2an},對任

意謂詞A(x),有

2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.1謂詞的概念與表示(PredicateandItsExpression)

(Vx)A(x)oA(ai)AA(a2)A...AA(an)

(3x)A(x)今A?)VA(a2)V...VA(an)

例6：在謂詞邏輯中將下列命題符號化.

(1)所有的人都長頭發(fā)。

(2)有的人吸煙。

(3)沒有人登上過木星。

(4)清華大學(xué)的學(xué)生未必都是高素質(zhì)的。

解：令M(x):x是人。(特性謂詞)

(1)令F(x):x長頭發(fā)。則符號化為：

(Vx)(M(x)fF(x))

2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.1謂詞的概念與表示(PredicateandItsExpression)

(2)令S(x):x吸煙。則符號化為：

(3x)(M(x)AS(x))

(3)令D(x):x登上過木星。則符號化為：

1(Bx)(M(x)AD(x))

(4)令Q(x):x是清華大學(xué)的學(xué)生。H(x):x是高素

質(zhì)的。則符號化為：

1(Vx)(Q(x)-H(x))

2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.1謂詞的概念與表示(PredicateandItsExpression)

小結(jié):本節(jié)將原子命題進(jìn)行分解，分為客體和謂詞

兩部分.進(jìn)而介紹了客體和謂詞、一元謂詞和n元

謂詞、命題函數(shù)、全稱量詞和存在量詞等概念。

重點(diǎn)掌握一元謂詞和n元謂詞的概念、全稱量詞

和存在量詞及量化命題的符號化。

作業(yè)：1.預(yù)習(xí)第二章§2.2,§2.3

2.習(xí)題2.1

?Back4

大第2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.2謂詞公式與翻譯(Predicateformulae)

■2.2謂詞公式與翻譯(Predicateformulae)

■n元謂詞A(x］，X2…X，稱為謂詞演算的原子公式。

定義2.2.1謂詞演算的合式公式，可由下述各條組成：

(1)原子公式是合式公式。

(2)若A是合式公式，則(1A)也是合式公式。

(3)若A,B是合式公式，貝U(AAB),(AvB),

(A->B),(A3B)也是合式公式。

(4)若A是合式公式，x是A中出現(xiàn)的任何變元，則

(Vx)A,(3x)A,也是合式公式。

(5)只有有限次應(yīng)用(1)?(4)得到的公式是合式公式.

2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.2謂詞公式與翻譯(Predicateformulae)

例1:在謂詞邏輯中將下列命題符號化.

(1)凡正數(shù)都大于零。

(2)存在小于2的素?cái)?shù)。

(3)沒有不能表示成分?jǐn)?shù)的有理數(shù)。

(4)并不是所有參加考試的人都能取得好成績。

解：(1)令F(x):x是正數(shù)。M(x):x大于零。則

符號化為：(X/x)(F(x)fM(x))

2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.2謂詞公式與翻譯(Predicateformulae)

(2)令E(x):x小于2。S(x):x是素?cái)?shù)。則符號化為:

(3x)(E(x)AS(x))真值為0。

(3)令D(x):x是有理數(shù)。F(x):x能表示成分?jǐn)?shù)。

則符號化為：(Vx)(D(x)-F(x))或

-1(3x)(D(x)A-iF(x))真值為1。

(4)令M(x)：x是人.Q(x):x參加考試。H(x):x取得

好成績。則符號化為：

-I(Vx)(M(x)AQ(x)-?H(x))或

(3x)(M(x)AQ(x)AnH(x))

2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.2謂詞公式與翻譯(Predicateformulae)

■例2：在謂詞邏輯中將下列命題符號化.

(1)所有運(yùn)動(dòng)員都?xì)J佩某些教練.

(2)有些運(yùn)動(dòng)員不欽佩教練.

設(shè)：L(x):x是運(yùn)動(dòng)員J(y):y是教練

A(x,y):x欽佩y

(1)(Vx)(L(x)—>(By)(J(y)AA(x,y)))

(2)Gx)(L(x)A(Vy)(J(y)fA(x,y)))

2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.2謂詞公式與翻譯(Predicateformulae)

■例3：在謂詞邏輯中將下列命題符號化.

(1)那位戴眼鏡的用功的大學(xué)生在看這本大而厚的巨著.

(2)P63(7)

解：(1)設(shè)：S(x):x是大學(xué)生.A(x):x戴眼鏡.

B(x):x用功.D(x):x是巨著.F(x,y):x看y.

E(y)：y是大的?G(y):y是厚的?a:那位b:這本

⑴符號化為：

A(a)AB(a)AS(a)AD(b)AE(b)AG(b)AF(azb)

2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.2謂詞公式與翻譯(Predicateformulae)

(2)設(shè)：P(x,y):x在y連續(xù).Q(x,y):x大于y.

(2)符號化為：

P(f,a)^(VE)(Q(￡,0)^((36)Q(6,0)A

(Vx)(Q(6,|x-gQ(￡,|/(x)一/娜

oP(f,a)—(V￡)66)”x)(Q(&0)f

(Q@0)A(Q(6,|x9布Q(&|/(%)-施刈

2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.2謂詞公式與翻譯(Predicateformulae)

■小結(jié)：本節(jié)介紹了謂詞合式公式的概念,

重點(diǎn)掌握謂詞公式的翻譯.

作業(yè)：P411,2

?Back4

2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.3變元的約束(Boundofvariable)

2.3變元的約束(Boundofvariable)

2.3.1變元的約束

2.3.2約束變元的換名與自由變元的代入

2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.3變元的約束(Boundofvariable)

2.3.1變元的約束(Boundofvariable)

定義231:在謂詞公式中，形如(Vx)P(x)和Qx)P(x)

的部分，稱為謂詞公式的x約束部分.(Vx)P(x)或

Qx)P(x)中的X叫做量詞的指導(dǎo)變元或作用變

元，P(x)稱為相應(yīng)量詞的作用域或轄域。

2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.3變元的約束(Boundofvariable)

在Vx和mx的轄域中，x的所有出現(xiàn)都稱為約束出

現(xiàn)，相應(yīng)的x稱為約束變元;P(x)中除約束變元以

外出現(xiàn)的變元稱為是自由變元。

例1：1、Vx(H(x,y)^3y(W(y)AL(x,y,z)))

2、Vx(H(x)fW(y))3y(F(x)AL(x,y,z))

2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.3變元的約束(Boundofvariable)

■說明:

(l)n元謂詞公式A(X]x2...xn)中有n個(gè)自由變元，若

對其中的k(kSi)個(gè)‘進(jìn)行約束，則構(gòu)成了元謂詞;

如果一個(gè)公式中沒有自由變元出現(xiàn)，則該公式就

變成了一個(gè)命題

(2)一個(gè)公式的約束變元所使用的名稱符號是無關(guān)

緊要的，如(Vx)M(x)與(Vy)M(y)意義相同.

2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.3變元的約束(Boundofvariable)

■2.3.2約束變元的換名與自由變元的代入規(guī)則

在例1中，一個(gè)變元在同一個(gè)公式中既是自由

出現(xiàn)又是約束出現(xiàn),這樣在理解上容易發(fā)生混淆.為

了避免這種混亂，可對約束變元進(jìn)行換名.

換名規(guī)則：(對約束變元而言)

對約束變元進(jìn)行換名，使得一個(gè)變元在一個(gè)公式中

只呈一種形式出現(xiàn).

2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.3變元的約束(Boundofvariable)

⑴約束變元可以換名，其更改的變元名稱范圍是量

詞中的指導(dǎo)變元以及該量詞作用域中所出現(xiàn)的

該變元，公式的其余部分不變.

(2)換名時(shí)一定要更改為作用域中沒有出現(xiàn)的變元

名稱.

2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.3變元的約束(Boundofvariable)

■例1:Vx(P(x)—R(x,y))AL(x,y)

換名為Vt(P(t)一R(t,y))AL(x,y)

■Vx(H(x,y)^3y(W(y)AL(x,y,z)))

換名為Vx(H(x,y)f玉(W(s)AL(x凡z)))

大第2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.3變元的約束(Boundofvariable)

■代入規(guī)則(對自由變元而言)

對公式中自由變元的更改稱為代入

⑴對于謂詞公式中的自由變元可以作代入,代入時(shí)

需要對公式中出現(xiàn)該自由變元的每一處進(jìn)行；

(2)用以代入的變元與原公式中所有變元的名稱不

能相同.

例如對例1中的公式Vx(P(x)-R(x,y))AL(x,y)

自由變元y用z來代入，得

Vx(P(x)-R(x/))AL(x,z)

2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.3變元的約束(Boundofvariable)

■小結(jié)：本節(jié)介紹了約束變元、自由變元的概念,

重點(diǎn)掌握約束變元的換名與自由變元的代入.

作業(yè)：P43:2,3

?Back4

2012-6-22

第二章謂詞邏輯(PredicateLogic)

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

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

implicationsofpredicatecalculus)

2.4.1謂詞的等價(jià)和永真的概念

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

2012-6-22

第二章謂詞邏輯（PredicateLogic）

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

241謂詞的等價(jià)和永真的概念

定義241:給定任意的謂詞公式A,其個(gè)體域?yàn)镋,對于A的

所有賦值，公式A都為真，則稱A在E上是永真的（或有效

的）;若對于A的所有賦值，公式A都為假，則稱A在E上是

永假的（或不可滿足的）;若至少存在著一種賦值使得公

式A為真，則稱A在E上是可滿足的.

■定義2.4.2:給定任何兩個(gè)謂詞公式A、B,設(shè)它們有共

同的個(gè)體域E,若對A和B的任一組變元進(jìn)行賦值，所

得命題的真值相同，則稱謂詞公式A和B在E上等價(jià)，

并記為A毋B

2012-6-22

第二章謂詞邏輯(PredicateLogic)

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

■工、命題公式的推廣

在命題公式中成立的式子，用謂詞公式去代換其

中相應(yīng)的命題變元，得到的公式依然成立

如：Vx(P(x)->Q(x))oVx(-|P(x)vQ(x))

1P(x)vqQ(x)="|(P(x)/\Q(x))等

■2、量詞與i之間的關(guān)系

n(Vx)P(x)o(3x)-IP(x)

-|(3x)P(x)o(Vx)-|P(x)

2012-6-22

第二章謂詞邏輯(PredicateLogic)

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

■3、量詞轄域的擴(kuò)張與收縮

量詞轄域中如果有合取或析取項(xiàng)，且其中有一個(gè)

是命題，則可將該命題移至量詞轄域之外。如:

(Vx)(A(x)VB)u>(Vx)A(x)VB

(Vx)(A(x)AB)=(Vx)A(x)AB

(3x)(A(x)VB)o(3x)A(x)VB

(3x)(A(x)AB)O(3X)A(X)AB

大第2012-6-22

第二章謂詞邏輯(PredicateLogic)

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

■量詞轄域的擴(kuò)張

(VxA(x)fB)Gx)(A(x)fB)

(Gx)A(x)fB)o(Vx)(A(x)-B)

(B-(Vx)A(x))o(Vx)(B-A(x))

(Bf0x)A(x))o0x)(B-A(x))

另有多個(gè)公式見課本70頁

第二章謂詞邏輯(PredicateLogic)

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

■4、量詞分配等值式

設(shè)A(x)、B(x)是任意的含自由出現(xiàn)個(gè)體變元x的

公式，則

(1)Vx(A(x)AB(x))oVxA(x)AVxB(x)

(2)3x(A(x)VB(x))o3xA(x)V3xB(x)

(3)Vx(A(x)VB(x))VxA(x)VVxB(x)

(4)3x(A(x)AB(x))<^3xA(x)A3xB(x)

2012-6-22

第二章謂詞邏輯(PredicateLogic)

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

■5.謂詞演算蘊(yùn)含式

■VxA(x)VVxB(x)nVx(A(x)VB(x))

3x(A(x)AB(x))=3xA(x)A3xB(x)

6.多個(gè)量詞的使用

多個(gè)量詞同時(shí)出現(xiàn)時(shí),其順序是至關(guān)重要的.

2012-6-22

第二章謂詞邏輯(PredicateLogic)

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

VxVyP(x,y)=VyVxP(x，y)

Uu

3yVxP(x,y)3xVyP(x，y)

uu

Vx3yP(x,y)Vy3xP(x，y)

uu

3y3xP(x,y)o3x3yP(x,y)

2012-6-22

第二章謂詞邏輯(PredicateLogic)

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

■小結(jié)：本節(jié)介紹了謂詞公式的概念及謂詞演算

的等價(jià)式與蘊(yùn)涵式，重點(diǎn)掌握謂詞演算的等價(jià)

式與蘊(yùn)涵式

■作業(yè):P50:1(1),(3)；2,3(1)；4

?Back4

2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.5前束范式(PrenexNormalForm)

2.5前束范式(Prenexnormalform)

2.5.1前束范式(Prenexnormalform)

2.5.2前束析取范式和前束合取范式(Prenex

disjunctivenormalform&Prenex

conjunctivenormalform)

第二章謂詞邏輯(PredicateLogic)

2.5前束范式(PrenexNormalForm)

2.5.1前束范式(Prenexnormalform)

■定義251:任何一個(gè)謂詞公式A,如果具有如下形式:

(□X1)(DX2)...(DXI1)B

其中口可能是量詞V或量詞」Xi(i=L…n)是客體變

元，B是不含量詞的謂詞公式，則稱A是前束范式。

-說明:前束范式的量詞均在全式的開頭,它們的作用域

延伸到整個(gè)公式的末尾。

■例1:3x3y((F(x)AG(y))AnH(x,y))V

Vx3y(F(x,y)AG(y,z))V3xH(x9y5z)X

2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.5前束范式(PrenexNormalForm)

■定理2.51:任何一個(gè)謂詞公式，均和一個(gè)前束范

式等價(jià)。

前束范式的求法：

第一步：否定深入。即利用量詞轉(zhuǎn)化公式，把否定聯(lián)結(jié)

詞深入到命題變元和謂詞填式的前面。

第二步：改名。即利用換名規(guī)則、代入規(guī)則更換一些變

元的名稱，以便消除混亂。

第三步：量詞前移。即利用量詞轄域的收縮與擴(kuò)張把量

詞移到前面。這樣便可求出與公式等價(jià)的前束范式。

2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.5前束范式(PrenexNormalForm)

例2:求下列公式的前束范式。

(1)(Vx)F(x)A^(3X)G(X)

(2)(Vx)F(x)v^(3x)G(x)

(3)(Vx)F(x).「Gx)G(x)

(4)(3x)F(x).「(Vx)G(x)

(5)((Vx)廠(％〃)t(加G(y))f(Vx)a(x,y)

(6)](Vx){C2)f

(3x)(Vy)[5(x.y)A(Vy)(^(y.x)fB(x,y))]}

2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.5前束范式(PrenexNormalForm)

■解：(1)(VX)F(X)A^(3X)G(X)

o(Vx)F(x)A(Vx)「G(x)(量詞轉(zhuǎn)換律)

o(Vx)(尸(x)△-iG(x))(量詞分配)

(2)(Vx)F(x)v^(3x)G(x)

o(Vx)/(x)v(X/x)「G(x)(量詞轉(zhuǎn)換律)

o(Vx)F(x)v(“卜G(y)(換名)

o(X/x)(尸(x)v(Vy)[G(y))(轄域擴(kuò)張)

o(Vx)(Vj)(F(x)v「G(y))(轄域擴(kuò)張)

2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.5前束范式(PrenexNormalForm)

⑸((Vx)尸(x,y)->(十)G(y))一(Vx)〃(xj)

oT[(x/x)/(x,y)VGv)G(y))V(X/x)H(x,y)

o((Vx)F(x,y)A「(》)G(y))v(Vx)H(x,y)

o((Vx)F(x,y)A(Vy)^G(y))v(Vx)/f(x,y)

今((VX)F(X5Z)A(VJ/)—IG(J))v(Vx)//(x5z)(代入)

O((VX)F(X5Z)A(Vy)^G(y))v(")〃?,z)(換名)

o(Vx)(Vy)(F(x,z)八[G(y))v(V，)H?,z)(轄域擴(kuò)張)

。(7%)(四)((尸(》/)八[60；))\/(5)〃。,2))(轄域擴(kuò)張)

o(VxXVy)(Vt)((F(x,z)△[G(y))v〃?/))(轄域擴(kuò)張)

2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.5前束范式(PrenexNormalForm)

(6)「(Vx){(刀

(3x)(yy)[B(x,y)Ax)f

(3x)(\/y)[B(x9y)A(Vy)(「/(，x)vB(x,y))]]

o(3x){(3j)^(x,y)A

(Vx)(3j)[^5(x?y)v(刀)(4('x)A》))]}

2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.5前束范式(PrenexNormalForm)

(6)續(xù)

oQx){(刀人

(Vx)(3j；)[^B(x,y)v(By)(A(y,x)A~.B(X,J；))]}

oQx){(刀)4(x,y)人

(VM)(3V)[-IB(W9V)vQz)(4(z,〃)A-I5(M?Z))]}(換名)

O(3X)(3J)(VM)(3V)(3Z){J(x,j)A

v(A(z,u)Az))]}

2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.5前束范式(PrenexNormalForm)

2.5.2前束析取范式和前束合取范式(Prenexdisjunctive

normalform&Prenexconjunctivenormalform)

■在前束范式的基礎(chǔ)上，可以定義前束析(合)取范式.

■定義262:任何一個(gè)謂詞公式A,如果具有如下形式則

稱為前束合取范式：

(□xi)(□x2)...(Dxn)[(AiiVA12V...VAiki)A

(AllVA22V...VA2k2)A...A(AmlVAmlV...VAmkm)]其

中n大于等于l,Aij(j=L…,ki,i=l,2,3,…,m)為原子謂詞公

式或其否定，口為量詞V或量詞1Xi(i=l,...n)為客

體變元.

2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.5前束范式(PrenexNormalForm)

■任何一個(gè)謂詞公式A,如果具有如下形式則稱為

前束析取范式：

(□xi)(□x2)...(Dxn)[(AnAA12A...AAiki)V

(AllAA22A...AA2k2)V...V(AmlAAmlA...AAmkm)]

其中11大于等于l,Aij(j=L…,ki,i=l,23…,m)為原子

謂詞公式或其否定，口為量詞V或量詞三，Xi

(i=L…n)為客體變元.

■定理262:每一個(gè)謂詞公式都可以轉(zhuǎn)化為與其等

價(jià)的前束析(合)取范式.

2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.5前束范式(PrenexNormalForm)

例2:求下列公式的前束析取范式和前束合取范式.

(1)((VX)F(X9J)F(十)G(y))f(Vx)H(x,y)

(2)](V%){(—)/(%/)-

0x)(Vy)[5(x,y)A(Vy)(/(y，x)fB(x,y))]}

解：

2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.5前束范式(PrenexNormalForm)

小結(jié)：本節(jié)介紹了謂詞公式的前束范式、前束

析取范式和前束合取范式.重點(diǎn)掌握前束析取

范式和前束合取范式求法。

作業(yè)：P53(2),(4)

?Back4

大第2012-6-22

第二章謂詞邏輯(PredicateLogic)

?2.6謂詞演算的推理理論

2.6謂詞演算的推理理論(Inferencetheoryof

predicatecalculus)

2.6.1推理規(guī)則(Rulesofinference)

2.6.2證明舉例(Examplesofproof)

2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.6謂詞演算的推理理論

2.6.1推理規(guī)則(Rulesofinference)

在謂詞演算中，推理的形式結(jié)構(gòu)仍為

HiAH2AH3A....AHn^>C

若HcHzAHs'jHnfC是永真式，則稱由前提

周用2再3,….，為邏輯的推出結(jié)論C,但在謂詞邏

輯中，HbH2,H3,....,Hn,C均為謂詞公式。

命題演算中的推理規(guī)則，可在謂詞推理理論中應(yīng)用。

2012-6-22

第二章謂詞邏輯（PredicateLogic）

2.6謂詞演算的推理理論

與量詞有關(guān)的四條重要推理規(guī)則:

1、全稱指定規(guī)則（US規(guī)則）

2、全稱推廣規(guī)則（UG規(guī)則）

3、存在指定規(guī)則（ES規(guī)則）

4、存在推廣規(guī)則（EG規(guī)則）

注意：只能對前束范式適用上述規(guī)則。

2012-6-22

第二章謂詞邏輯(PredicateLogic)

*2.6謂詞演算的推理理論

■1.全稱指定規(guī)則(US)：

VxP(x)

??.P(c)

使用此規(guī)則時(shí)要注意：

(1)X是P(x)中的自由變元；

(2)c是論域中的某個(gè)任意的客體.

2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.6謂詞演算的推理理論

■2.全稱推廣規(guī)則(UG)：

P(y)

?二VxP(x)

使用此規(guī)則時(shí)注意：

(1)y在P(y)中自由出現(xiàn)，且y取任何值時(shí)P均為真。

(2)x不在P(y)中約束出現(xiàn).

2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.6謂詞演算的推理理論

■3.存在指定規(guī)則(ES):

玉P(x)

???P(c)

注:C是論域中的某些客體,C并不是任意的

使用此規(guī)則時(shí)應(yīng)注意:

c是使P為真的特定客體;

大第2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.6謂詞演算的推理理論

⑷存在推廣規(guī)則(EG):

P(c)

:.3xP(x)

使用此規(guī)則時(shí)注意：

(1)C是個(gè)體域中某個(gè)確定的個(gè)體。

(2)代替C的x不能已在P(c)中出現(xiàn)。

2012-6-22

第二章謂詞邏輯(PredicateLogic)

2.6謂詞演算的推理理論

262證明舉例(Example