離散數(shù)學(xué)（第二版） 課件 鄒麗娜 3.2謂詞公式

離散數(shù)學(xué)第3章謂詞邏輯3.1謂詞邏輯概述目錄3.2謂詞公式與解釋3.3謂詞公式的等值演算3.4謂詞推理自然語(yǔ)言用謂詞公式表示命題謂詞個(gè)體量詞個(gè)體常量個(gè)體變?cè)瘮?shù)用謂詞公式表示命題【用謂詞公式表示命題的一般步驟】用謂詞公式表示不含量詞的簡(jiǎn)單命題的方法和步驟：(1)找出命題中的謂詞，用符號(hào)表示；(2)找出命題的主要個(gè)體對(duì)象，并用符號(hào)表示；(3)謂詞公式，用邏輯連接詞連接謂詞；(4)檢查所寫(xiě)的謂詞公式是否表達(dá)了原命題的內(nèi)容。例如：馬麗的父親與蘇珊的父親是同事

個(gè)體常量：a表示瑪麗，b表示蘇珊

函數(shù)：f(x)表示x的父親

謂詞：P(x,y)表示x和y是同事

原命題表示為：P(f(a),f(c))用謂詞公式表示命題用謂詞公式表示下列命題（不含量詞）：

(1)3是素?cái)?shù)。(2)2是奇數(shù)。

(3)張明和劉浩是同學(xué)。(4)李嵐是長(zhǎng)跑冠軍。用謂詞公式表示命題例:將下列命題謂詞符號(hào)化2既是素?cái)?shù)又是偶數(shù)F(x)：x是素?cái)?shù)G(x)：x是偶數(shù)a:2F(a)G(a)如果楊慶是北京大學(xué)的學(xué)生，陳明也是北京大學(xué)的學(xué)生，那么楊慶與陳明是校友。

F(x):是北京大學(xué)的學(xué)生G(x,y):x與y是校友a(bǔ):楊慶,b:陳明F(a)

F(b)G(a,b)練習(xí)將下列命題在一階邏輯中用謂詞符號(hào)化(1)周杰倫是一個(gè)男歌星．(2)若６大于４且４大于２，則６大于２．解(1)令F(x):x是一個(gè)男人,G(x):x是歌星

a:周杰倫

符號(hào)化:F(a)

G(a).

(2)令G(x,y):x大于y

a:6,b:4,c:2

符號(hào)化:G(a,b)

G(b,c)→G(a,c).在謂詞前加上量詞，稱為謂詞的量化。若一個(gè)謂詞中所有個(gè)體變?cè)剂炕耍瑒t該謂詞就變成了命題。這是因?yàn)樵谥^詞被量化后，可以在整個(gè)個(gè)體域中考慮命題的真值了。3.2謂詞公式思考：

xF(x),xF(x),F(x)的聯(lián)系、區(qū)別？F(x)是不能確定真值的謂詞

xF(x),xF(x)都是命題x稱為約束變?cè)^詞公式表示含量詞的命題的方法和步驟(1)找出量詞，確定轄域；(2)表示全稱量詞及其轄域所描述的命題，具體如下：a)用A(x)表示所屬范圍；b)用B(x)表示去掉量詞后的命題；c)用形如

的公式表示原命題，(3)表示存在量詞及其轄域所描述的命題，具體如下：a)用A(x)表示所屬范圍；b)用B(x)表示去掉量詞后的命題；

c)用形如

的公式表示原命題(4)用邏輯聯(lián)結(jié)詞聯(lián)結(jié)各個(gè)子公式。(5)檢查例（1）所有人都呼吸.

（2）有的人吸煙.

含有量詞的命題（討論域?yàn)槿倐€(gè)體域）個(gè)體域?yàn)槿倐€(gè)體域.

設(shè)M(x):x是人；F(x):x呼吸；G(x):x吸煙（1）符號(hào)化為

x(M(x)

F(x))（真命題）

（2）符號(hào)化為

x(M(x)

G(x))（真命題）例（1）所有人都呼吸.

（2）有的人吸煙.個(gè)體域?yàn)槿祟惣希?）符號(hào)化為

xF(x)，其中F(x)：x呼吸（真命題）（2）符號(hào)化為

xG(x)，其中G(x)：x吸煙（真命題）

含有量詞的命題（討論域?yàn)榫唧w域）3.2謂詞公式謂詞邏輯符號(hào)化幾點(diǎn)說(shuō)明不同的個(gè)體域，符號(hào)化形式可能不一樣，命題真值也可能不同例如：

xG(x),其中G(x):x+9=6,當(dāng)個(gè)體域取自然數(shù)集時(shí)真值為０；當(dāng)個(gè)體域取實(shí)數(shù)集時(shí)真值為１.一般默認(rèn)是全總個(gè)體域，即包含一切個(gè)體特性謂詞：描述個(gè)體變?cè)≈捣秶闹^詞全稱量化中，特性謂詞常作為蘊(yùn)涵式的前件

x（M(x)F(x))存在量化中，特性謂詞常作為合取項(xiàng)之一

x(M(x)G(x))例

用謂詞公式表示下列命題：(1)每個(gè)計(jì)算機(jī)系的學(xué)生都學(xué)離散數(shù)學(xué)。(2)有人喜歡吃蘋(píng)果。例3.4

用謂詞公式表示下列命題：所有人都吃飯存在不吃飯的人(3)沒(méi)有不吃飯的人(4)不是所有的人都吃飯

x(M(x)E(x))命題符號(hào)化例：將下列命題符號(hào)化凡是學(xué)生都需要學(xué)習(xí)和考試F(x):x是學(xué)生；G(x):x學(xué)習(xí)；H(x):x考試

x(F(x)G(x)H(x))所有的汽車(chē)都比馬車(chē)跑得快P(x)：x是汽車(chē)；Q(y)：y是馬車(chē)；G(x,y)：x比y跑得快。

x

y(P(x)

Q(y)

G(x,y))

1.將下列命題符號(hào)化所有的汽車(chē)都比馬車(chē)跑得快有的汽車(chē)比有的馬車(chē)跑得快所有汽車(chē)比有的馬車(chē)跑得快有的汽車(chē)比所有馬車(chē)跑的快有的汽車(chē)不比所有馬車(chē)跑得快并非所有汽車(chē)都比所有馬車(chē)跑的快P(x)：x是汽車(chē)；Q(y)：y是馬車(chē)；G(x,y)：x比y跑得快。2.找出下列公式中的量詞轄域、是否存在自由變?cè)?，公式是否為閉公式(1)兔子比烏龜跑得快．(2)并非所有的兔子比所有的烏龜跑得快．(3)有的兔子比有的烏龜跑得快．設(shè)F(x):x是兔子,G(y):y是烏龜,H(x,y):x比y跑得快.(1)

x

y(F(x)

G(y)→H(x,y))(2)

x

y(F(x)

G(y)→H(x,y))或

x

y(F(x)

G(y)

H(x,y))(3)

x

y(F(x)

G(y)

H(x,y))例題3.5：命題符號(hào)化例3.5：將下列命題符號(hào)化(4)有的兔子不比有的烏龜跑得快．設(shè)F(x):x是兔子,G(y):y是烏龜,H(x,y):x比y跑得快.(4)

x

y(F(x)

G(y)

H(x,y))(5)沒(méi)有兩個(gè)跑得同樣快的兔子F(x):x是兔子，L(x,y):x和y跑得同樣快

xy(F(x)F(y)L(x,y))命題符號(hào)化注意事項(xiàng)根據(jù)命題的實(shí)際意義選取全稱量詞或存在量詞多個(gè)量詞同時(shí)出現(xiàn)時(shí)，不能隨意顛倒順序符號(hào)化：對(duì)任意的x，存在著y，使得x+y=5給定實(shí)數(shù)域F(x,y)：x+y=5

xyF(x,y)不同于y

xF(x,y)TF(1)存在小于５的奇數(shù)(2)并非每個(gè)實(shí)數(shù)都是有理數(shù)(3)沒(méi)有不犯錯(cuò)誤的人F(x):x<5,G(x):x是奇數(shù)

x(F(x)

G(x))(2)R(x):x是實(shí)數(shù),Q(x):x是有理數(shù)

x(R(x)→Q(x))或

x(R(x)

Q(x))

(3)M(x):x是人,F(x):x犯錯(cuò)誤

x(M(x)

F(x))或

x(M(x)→F(x))練習(xí)(4)參加考試的人未必都能取得好成績(jī)．(5)有學(xué)生選修過(guò)本校開(kāi)設(shè)的每一門(mén)數(shù)學(xué)課。練習(xí)F(x):x是參加考試的人,G(x):x取得好成績(jī)

x(F(x)→G(x))或

x(F(x)

G(x))(5)s(x):x是學(xué)生,M(y):y是本校開(kāi)設(shè)的數(shù)學(xué)課,E(x,y):x選修y

x(s(x)

y(M(y)→E(x,y)))

量詞的轄域【量詞的轄域】含有量詞的公式中，被某個(gè)量詞量化的子公式(或整個(gè)公式)稱為該量詞的轄域。在

x和

x的轄域中，x的所有出現(xiàn)都稱為約束變?cè)珹中不是約束出現(xiàn)的其它變項(xiàng)均稱為自由變?cè)?

x(P(x,y)

Q(x,z))

R(x)

x(F(x,y,z)

yG(x,y))

例

指出下列公式的約束變?cè)?、自由變?cè)傲吭~的轄域練習(xí)是閉公式不是閉公式閉公式的意義：任何一個(gè)閉公式都表示一個(gè)命題；一個(gè)含有自由變?cè)墓讲荒鼙硎疽粋€(gè)命題。3.7練習(xí)謂詞公式的解釋（由符號(hào)到自然語(yǔ)言）3.8DI={安娜,布朗,比爾,卡特,查理,戴西,戴維,杜威}

F(x):x是一個(gè)學(xué)生；G(x,y):x與y是老鄉(xiāng),H(x,y):x與y是同學(xué)；F(x),G(a,y)及H(x,y)含有自由變?cè)?，即不是閉公式，因而不是命題。解釋：令a=安娜，F(xiàn)(a):

安娜是一個(gè)學(xué)生；

x

yG(x,y)

:在論域中有兩個(gè)對(duì)象是老鄉(xiāng)；

xF(x)

:在論域中的所有對(duì)象都是學(xué)生；3.9練習(xí)去取經(jīng)都會(huì)遇到妖怪(())構(gòu)造一個(gè)可以使公式為真的解釋和一個(gè)為假的解釋解釋I１：個(gè)體域D1為整數(shù)集Z;

H(x,y)：x大于y解釋：對(duì)D中的每一個(gè)數(shù)，都存在一個(gè)比它小的數(shù)。是真命題

解釋I2：個(gè)體域D2為正整數(shù)集Z+;

H(x,