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

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

個體常量：a表示瑪麗，b表示蘇珊

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

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

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

(1)3是素數(shù)。(2)2是奇數(shù)。

(3)張明和劉浩是同學(xué)。(4)李嵐是長跑冠軍。用謂詞公式表示命題例:將下列命題謂詞符號化2既是素數(shù)又是偶數(shù)F(x)：x是素數(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:陳明F(a)

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

a:周杰倫

符號化:F(a)

G(a).

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

a:6,b:4,c:2

符號化:G(a,b)

G(b,c)→G(a,c).在謂詞前加上量詞，稱為謂詞的量化。若一個謂詞中所有個體變元都量化了，則該謂詞就變成了命題。這是因為在謂詞被量化后，可以在整個個體域中考慮命題的真值了。3.2謂詞公式思考：

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

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

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

c)用形如

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

（2）有的人吸煙.

含有量詞的命題（討論域為全總個體域）個體域為全總個體域.

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

x(M(x)

F(x))（真命題）

（2）符號化為

x(M(x)

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

（2）有的人吸煙.個體域為人類集合（1）符號化為

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

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

含有量詞的命題（討論域為具體域）3.2謂詞公式謂詞邏輯符號化幾點說明不同的個體域，符號化形式可能不一樣，命題真值也可能不同例如：

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

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

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

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

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

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

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

x

y(P(x)

Q(y)

G(x,y))

1.將下列命題符號化所有的汽車都比馬車跑得快有的汽車比有的馬車跑得快所有汽車比有的馬車跑得快有的汽車比所有馬車跑的快有的汽車不比所有馬車跑得快并非所有汽車都比所有馬車跑的快P(x)：x是汽車；Q(y)：y是馬車；G(x,y)：x比y跑得快。2.找出下列公式中的量詞轄域、是否存在自由變元，公式是否為閉公式(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：命題符號化例3.5：將下列命題符號化(4)有的兔子不比有的烏龜跑得快．設(shè)F(x):x是兔子,G(y):y是烏龜,H(x,y):x比y跑得快.(4)

x

y(F(x)

G(y)

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

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

xyF(x,y)不同于y

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

x(F(x)

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

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

x(R(x)

Q(x))

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

x(M(x)

F(x))或

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

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

x(F(x)

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

x(s(x)

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

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

x和

x的轄域中，x的所有出現(xiàn)都稱為約束變元，A中不是約束出現(xiàn)的其它變項均稱為自由變元.

x(P(x,y)

Q(x,z))

R(x)

x(F(x,y,z)

yG(x,y))

例

指出下列公式的約束變元、自由變元及量詞的轄域練習(xí)是閉公式不是閉公式閉公式的意義：任何一個閉公式都表示一個命題；一個含有自由變元的公式不能表示一個命題。3.7練習(xí)謂詞公式的解釋（由符號到自然語言）3.8DI={安娜,布朗,比爾,卡特,查理,戴西,戴維,杜威}

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

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

x

yG(x,y)

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

xF(x)

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

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

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

H(x,