離散數(shù)學(xué)謂詞邏輯

離散數(shù)學(xué)謂詞邏輯第1頁，課件共54頁，創(chuàng)作于2023年2月

謂詞、個體詞和量詞

例在命題邏輯中，對下述論斷無法判斷其正確性?！疤K格拉底三段論”：凡人都是要死的，蘇格拉底是人，所以蘇格拉底是要死的。類似的例還有許多。例如：所有的人都要呼吸,所有的正整數(shù)都大于0,

李莉是人,3是正整數(shù),所以李莉要呼吸。所以3大于0。第2頁，課件共54頁，創(chuàng)作于2023年2月

一、個體詞和謂詞在謂詞演算中，可將原子命題分解為謂詞與個體詞兩部分。定義2-1

個體是指可以獨(dú)立存在的客體。

注個體可以是抽象的，也可是具體的。個體通常在一個命題里表示思維對象。定義2-2

用來刻劃個體的性質(zhì)或個體之間關(guān)系的詞稱為謂詞，刻劃一個個體性質(zhì)的詞稱為一元謂詞；刻劃n個個體之間關(guān)系的詞稱為n元謂詞。

例1

（1）李明是學(xué)生；（2）張亮比陳華高；（3）陳華坐在張亮與李明之間。在這三個命題中，李明、張亮、陳華都是個體；“…是學(xué)生”是一元謂詞，“…比…高”是二元謂詞，“…坐…與…之間”是三元謂詞。第3頁，課件共54頁，創(chuàng)作于2023年2月通常，我們用大寫字母表示謂詞，小寫字母表示個體。上述命題可分別表示為Q（a）,P（b,c），

R（c,b,a）。一般地，一個由n個個體和n元謂詞所組成的命題可表示為F（a1,a2,…,an）,其中F表示n元謂詞,a1,a2,…,an

分別表示n個個體。

注意：a1,a2,…,an的排列次序是重要的。第4頁，課件共54頁，創(chuàng)作于2023年2月二、個體變元和命題函數(shù)個體常元

表示具體或特定的個體的個體詞稱為個體常元。個體變元表示抽象的，或泛指的（或者說取值不確定的）個體稱為個體變元。例2

設(shè)H是表示謂詞“…能夠到達(dá)山頂”，若個體w:王紅；t：老虎；s：汽車，則H（w），H（t），H（s）分別表示“王紅能夠到達(dá)山頂。”“老虎能夠到達(dá)山頂?！薄捌嚹軌虻竭_(dá)山頂?！边@里w、t、s均是個體常元。H（x）：x能夠到達(dá)山頂。這里的x是泛指的，不確定的，x可在一定的范圍內(nèi)取值。故x是個體變元。例3

L（x,y,z）表示“x+y=z”,其中x,y,z為個體變元。L（3，2，5）表示真命題“3+2=5”，而L（1，2，4）表示假命題“1+2=4”。第5頁，課件共54頁，創(chuàng)作于2023年2月定義2-3

由一個謂詞和若干個個體變元組成的命題形式稱為簡單命題函數(shù)，表示為P(x1,x2,…,xn)。由一個或若干個簡單命題函數(shù)以及邏輯聯(lián)結(jié)詞組成的命題形式稱為復(fù)合命題函數(shù)。例如

H(x)，L(x,y,z)均是簡單命題函數(shù)。在命題函數(shù)中，個體變元的取值范圍稱為個體域。例4

P(x,y)表示“2x+y=1”，若x,y的個體域為正整數(shù)集，則總是假；

若x,y的個體域為有理數(shù)集，則y=1―2x，對任意的有理數(shù)k，在x=k，y=1―2k時，P(k,1―2k)為真。

(P(x,y)∨L(x,y,z))

P(y,x)是一復(fù)合命題函數(shù)第6頁，課件共54頁，創(chuàng)作于2023年2月三、量詞和全總個體域量詞

在命題里表示數(shù)量的詞。

1.量詞

使用前面介紹的概念，還不足以表達(dá)日常生活中的各種命題。

例如：對于命題“所有的正整數(shù)都是素數(shù)”和“有些正整數(shù)是素數(shù)”僅用個體詞和謂詞是很難表達(dá)的。

（1）全稱量詞

“x”

如“所有人都是要死的?！笨杀硎緸閤D（x），x的個體域為全體人的集合。

第7頁，課件共54頁，創(chuàng)作于2023年2月（2）存在量詞“

x”（3）存在唯一量詞“!x”如“有些有理數(shù)是整數(shù)?！绷睿?x）：x是整數(shù)；于是命題可表示為xＩ(x）其中x的個體域為有理數(shù)集合。

如“方程x+1=0存在唯一的整數(shù)解。” 令P（x）：x是x+1=0的整數(shù)解。則命題可表示為!xP（x），其中x的個體域為整數(shù)集。第8頁，課件共54頁，創(chuàng)作于2023年2月

2．全總個體域

含有量詞的命題的表達(dá)式的形式，與個體域有關(guān)。

含有量詞的命題的真值與個體域也有關(guān)。因此，為了方便，我們引入全總個體域的概念。

定義2―5

宇宙間所有的個體聚集在一起所構(gòu)成的集合稱為全總個體域。后面的討論中，除特殊說明外，均使用全總個體域。而對個體變化的真正取值范圍，用特性謂詞加以限制。

一般地，對全稱量詞，此特性謂詞作蘊(yùn)含的前件；對存在量詞，此特性謂詞常作合取項。第9頁，課件共54頁，創(chuàng)作于2023年2月

當(dāng)取x的個體域為全總個體域時，必須引入一個特性謂詞將人從全宇宙的一切事物中分離出來。

（1）對所有個體而言，如果它是人，則它是要死的。(2）存在著個體，它是人并且它活百歲以上。

令D（x）：x是要死的。則（1）可表示為xD（x）。令G（x）：x活百歲以上。則（2）可表示為xG（x）。例5

(1)“所有的人都是要死的。”(2)“有的人活百歲以上。”

當(dāng)x的個體域E為全體人組成的集合時，符號化上述命題。于是令M（x）：x是人。（1）x（M（x）D（x））（2）x（M（x）∧G（x））第10頁，課件共54頁，創(chuàng)作于2023年2月

四．命題符號化

例6

將下列命題符號化(使用全總

個體域)。(1)發(fā)光的不都是金子

解

令P（x）：x發(fā)光；G（x）：x是金子。

（2）所有運(yùn)動員都?xì)J佩某些教練。解

令P（x）：x是運(yùn)動員；T（x）：x是教練；Q（x，y）：x欽佩y。

則可表示為

或

則該命題可表示為

第11頁，課件共54頁，創(chuàng)作于2023年2月

（3）凡是實數(shù)均能比較大小。

解

令R（x）：x是實數(shù)；G（x,y)：x與y可比較大小.例7將下列命題符號化

（1）會叫的狗未必咬人。

解

令D（x）：x是狗；P（x）：x會叫；Q（x）：x咬人。

則可表示為

或表示為

則該命題可表示為

或者令Q（x,y）:x≥y;第12頁，課件共54頁，創(chuàng)作于2023年2月

（3）不是一切人都一樣高。

（2）一切人不是一樣高。

解

M(x)：x是人；G(x,y):x與y一樣高;H(x,y):x與y是不同的人。可表示為

可表示為

或者表示為第13頁，課件共54頁，創(chuàng)作于2023年2月謂詞演算公式

一、謂詞公式定義2-6

（謂詞公式的遞歸定義。）

(1）命題常元、命題變元和簡單命題函數(shù)都是謂詞公式。（2）如果A是謂詞公式，則A也是謂詞公式。（3）如果A和B是謂詞公式，則（A∨B）,(A∧B）,(A→B),(AB)也是謂詞公式。（4）如果A是謂詞公式，x是A中的個體變元，則

和

也是謂詞公式。（5）只有由使用上述四條規(guī)則有限次而得到的才是謂詞公式。第14頁，課件共54頁，創(chuàng)作于2023年2月

例1

蘇格拉底三段論可用謂詞公式表示。

令M（x）：x是人；D（x）：x是要死的；a：蘇格拉底

例2

給出“x+y≥3”的謂詞公式的表示形式。

解

令P（x,y,z）：x+y≥z

則上述表達(dá)式可用謂詞公式表示為P（x,y,3）。

則三段論可表示為

(x（M（x）D（x））∧M（a）)D（a）

第15頁，課件共54頁，創(chuàng)作于2023年2月二、約束變元和自由變元

個體變元有自由變元和約束變元之分.

例3

“x是整數(shù)”可以表示為Q（x），它是一個命題函數(shù)，而不是命題。

例4

“

x<y”可表示為“P（x,y）”也是一個命題函數(shù)，而不是命題。

例5

“凡是有理數(shù)都可以表示成分?jǐn)?shù)?！绷頠（x）：x是有理數(shù)；F（x）：x可以表示為分?jǐn)?shù)

這是一個真值確定的命題。符號化表示為

第16頁，課件共54頁，創(chuàng)作于2023年2月例6

“某些人對某些藥物過敏”令H(x)：x是人;M(y):y是藥;S(x，y)：x對y過敏。

當(dāng)x的出現(xiàn)不是約束出現(xiàn)時，稱x的出現(xiàn)是自由出現(xiàn)。自由出現(xiàn)的變元是自由變元。

公式中約束出現(xiàn)的變元是約束變元

符號化表示為

也是一個真值確定的命題。

在謂詞公式中，形如或的那一部分稱為公式的x約束部分。而A（x）稱為量詞x或x的轄域。x在公式的x約束部分的任一出現(xiàn)都稱為x的約束出現(xiàn)。

第17頁，課件共54頁，創(chuàng)作于2023年2月

x,y,z在公式中的所有出現(xiàn)均是約束出現(xiàn)，故它們均是約束變元。

例7

指出下列各公式中的量詞轄域及自由變元和約束變元。

解

是的轄域。是的轄域.

R(z）是z的轄域。第18頁，課件共54頁，創(chuàng)作于2023年2月解

P（x，y）－>yQ（x，y，z）是x的轄域，在這一部分中，x是約束出現(xiàn)，故x是約束變元，在P（x，y）中的y是自由出現(xiàn)，故y為自由變元。但Q（x，y，z）是y的轄域，因而在Q（x，y，z）中y卻是約束出現(xiàn)，故此時y是約束變元，z是自由變元。在S（x，z）中x，z是自由變元。第19頁，課件共54頁，創(chuàng)作于2023年2月

三、換名規(guī)則和代入規(guī)則

1.換名規(guī)則

對約束變元進(jìn)行換名，使得一個變元在一個公式中只呈一種形式出現(xiàn)。

（1）約束變元換名時，該變元在量詞及其轄域中的所有出現(xiàn)均須同時更改，公式的其余部分不變；（2）換名時，一定要更改為該量詞轄域中沒有出現(xiàn)過的符號，最好是公式中未出現(xiàn)過的符號。第20頁，課件共54頁，創(chuàng)作于2023年2月

解

需對x，y換名

錯誤法：

例8

對公式進(jìn)行換名，使各變元只呈一種形式出現(xiàn)。第21頁，課件共54頁，創(chuàng)作于2023年2月

2.代入規(guī)則對于公式中自由變元的更改叫做代入。

的x,y的自由出現(xiàn)分別用w,t代入得

（1）對于謂詞公式中的自由變元可以代入，代入時須對該自由變元的所有自由出現(xiàn)同時進(jìn)行代入；（2）代入時所選用的變元符號與原公式中所有變元的符號不相同。例如對例8中公式

第22頁，課件共54頁，創(chuàng)作于2023年2月謂詞公式的等值和蘊(yùn)含

指派

一組代入到謂詞公式中，并使得謂詞公式成為命題的確定的個體和命題稱為公式的一組指派。一、公式的類型

一個謂詞公式一般含有個體變元、命題變元和謂詞，只有當(dāng)公式中的自由變元用某個體域中確定的個體代入，命題變元用確定的命題代入后，原公式才變成為一個命題。

定義2-7

給定謂詞公式A，其個體域為E，如果對于任一組指派，公式A的值總是為真，則稱A在E上式永真的。如果對于公式A的任一組指派，公式A的值總是為假，則稱A在E上是永假的。如果至少存在著一組指派，使公式A的值為真，則稱A在E上是可滿足的。

第23頁，課件共54頁，創(chuàng)作于2023年2月

例1

試說明下列各公式的類型（個體域取為全總個體域）（1）（2）（3）F(x)（其中F(x):x+6=5）（4）

解

(1)永真公式(2)可滿足公式(3)可滿足公式(4)永假公式第24頁，課件共54頁，創(chuàng)作于2023年2月解

（1）可滿足公式。

（2）永假公式。

（3）永真公式。

（4）可滿足公式。

例2試說明下列各公式的類型。（1）（2）（3）（4）P（x，y）其中x，y的個體域為R；謂詞P（x，y）：x=y；Q是命題變元.第25頁，課件共54頁，創(chuàng)作于2023年2月

定義2-8

設(shè)A、B是兩個公式，它們有共同的個體域E，若對于A和B的任意一組指派，兩公式都具有相同的真值，則稱公式A和B在E上等值，記作A

B。定義2-9對于公式A和B，若AB1，則稱公式A蘊(yùn)含公式B，記作AB。

謂詞演算中的等值式和蘊(yùn)涵式在命題演算中，任一等值式或蘊(yùn)涵式，其中同一命題變元，當(dāng)用同一命題公式取代時，其結(jié)果仍是等值式或蘊(yùn)涵式。

二、公式的等值與蘊(yùn)含1.命題公式的推廣第26頁，課件共54頁，創(chuàng)作于2023年2月

將此情況推廣到謂詞公式中，用謂詞公式去取代命題演算中等值式或蘊(yùn)涵式的命題變元時，便得到謂詞演算的等值式或蘊(yùn)涵式。

例如

例如又例如

第27頁，課件共54頁，創(chuàng)作于2023年2月2.全稱量詞和存在量詞間轉(zhuǎn)化的等值式

（其中A(x)是任意的公式）對個體域是有限時，給出其證明。證明

設(shè)個體域,則第28頁，課件共54頁，創(chuàng)作于2023年2月

3.量詞轄域擴(kuò)展與收縮的等值式1.

證明

設(shè)個體域,則第29頁，課件共54頁，創(chuàng)作于2023年2月（2）①②③④證明第30頁，課件共54頁，創(chuàng)作于2023年2月

證明（1）①

“個體域中每一個體x，使得A(x)與B(x)均為真”與

“個體域中每一個體x，使得A(x)為真且每一個體x使得B(x)為真”具有相同的含義.

4.量詞分配等值式與蘊(yùn)涵式（1）①②第31頁，課件共54頁，創(chuàng)作于2023年2月（1）②證明

由①得第32頁，課件共54頁，創(chuàng)作于2023年2月證明

（2）②

由（2）①得（2）①②即

即故第33頁，課件共54頁，創(chuàng)作于2023年2月證明

（1）5.量詞與聯(lián)結(jié)詞的關(guān)系第34頁，課件共54頁，創(chuàng)作于2023年2月證明因此在個體域中必存

在某個體a使B(a)為假，但A(a)為真。證明

設(shè)為假，則為真，為假。于是為假，因此為假。故由此 永真。第35頁，課件共54頁，創(chuàng)作于2023年2月謂詞演算的推理理論

一、推理規(guī)則

命題演算中的推理規(guī)則，可在謂詞推理理論中應(yīng)用。在謂詞演算中，推理的形式結(jié)構(gòu)仍為

若是永真式，則稱由前提邏輯的推出結(jié)論C，在此,C均為謂詞公式。第36頁，課件共54頁，創(chuàng)作于2023年2月與量詞有關(guān)的推理規(guī)則1.US(全稱特定化規(guī)則)使用此規(guī)則時要注意：

（1）x是A(x)中的自由變元；（2）y為任意不在A(x)中約束出現(xiàn)的個體變元；（3）c為任意的個體常元。

關(guān)于（2）的反例：

設(shè)則,x,y的個體域為R，是一真命題.

若應(yīng)用US得，則是錯誤的。正確的做法是換成第37頁，課件共54頁，創(chuàng)作于2023年2月

使用此規(guī)則時應(yīng)注意： （1）c是使A為真的特定個體常元； （2）如果A(x)中有其他自由變元出現(xiàn)，且x是隨其他自由變元變化的，那么不能使用此規(guī)則。

2. ES（存在特定化規(guī)則）3.UG（全稱一般化規(guī)則）

使用此規(guī)則時注意:(1)y在A(y)中自由出現(xiàn)，且y取任何值時A均為真。

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

第38頁，課件共54頁，創(chuàng)作于2023年2月4、EG（存在一般化規(guī)則）

使用此規(guī)則時注意:(1)C是個體域中某個確定的個體。

(2)代替C的x不能已在A(c)中出現(xiàn)。第39頁，課件共54頁，創(chuàng)作于2023年2月二、推理規(guī)則的應(yīng)用

例1

證明蘇格拉底的三段論。

解

令M(x):x是人;D(x):x是要死的;c:蘇格拉底。于是蘇格拉底三段論可表示為：證明（1）M(c)前提（2） 前提（3）（1）；US（4）D(c) (1),(3);第40頁，課件共54頁，創(chuàng)作于2023年2月例2

證明

（3） C(a)∧

Q(a)

（2）；ES證明

（1） 前提

（2） 前提

（4） （1）；US

（5）C(a) （3）；I1

（6）W(a)∧

R(a)（4）,（5）；I11

（7）Q(a) （3）；I2

（8）R(a) （6）；I2

（9）Q(a)∧R(a)（7）,（8）；I9

（10）

（9）；EG第41頁，課件共54頁，創(chuàng)作于2023年2月例3

證明證明（1） 附加前提

（2） （1）；E

（6）Q(c)

（3）,（5）；I10

（7）

（6）；EG

（3）

（2）；ES

（4）

前提

(5)（4）；US第42頁，課件共54頁，創(chuàng)作于2023年2月例4

證明

（1） 附加前提

（2） （1）；E10

證法一

:(間接證明法)

（3） （2）；I1

（4） （2）；I2

（5） （4）；I19

（6） （3）；E18

（7） （6）；ES

（8） （5）；US

（9） （7）（8）；I9

（10） （9）；E10

（11） 前提

（12） （11）；US

（13） （10）（12）;I9第43頁，課件共54頁，創(chuàng)作于2023年2月證法二（1） 附加前提

（2） （1）；E18

（3） 前提

（4） （2）；ES

（5） （3）；US

（6） （4）（5）；I10

（7） （6）；EG

（8） （1）（7）；CP

（9） （8）；E11，E6

原題可轉(zhuǎn)化為證明第44頁，課件共54頁，創(chuàng)作于2023年2月

（2） （1）；I1

例5

指出下面推理的錯.

（3） （1）；I2

（4） （2）；ES

（5） （3）；ES

（6） （4）（5）；I9

（7） （6）；EG

因此

（1） 前提證明第45頁，課件共54頁，創(chuàng)作于2023年2月例6

指出下面推理的錯誤.設(shè)D(x,y)表示“x可被y整除”,個體域為{5,7,10,11}.因為D(5，5)和D(10,5)為真，所以xD(x,5)為真.因為D(7，5)和D(11,5)為假，所以xD(x,5)為假.

但有下面的推理過程：(1)xD(x,5)前提(2)D(z,5)(1);ES(3)xD(x,5)(2);UG

因此，xD(x,5)