離散數(shù)學(xué)及其應(yīng)用課件第2章第1節(jié)

離散數(shù)學(xué)及其應(yīng)用1第2章謂詞邏輯2.1謂詞邏輯的基本概念2.2謂詞合式公式2.3謂詞公式的解釋和分類2.4謂詞演算的關(guān)系式2.5前束范式2.6謂詞演算的推理22.1謂詞邏輯的基本概念2.1.1個體詞和謂詞定義2.1.1個體詞是指可以獨(dú)立存在的客體，可以是一個具體的事物或抽象的概念，是原子命題所描述的對象。

謂詞是用來說明個體的性質(zhì)或個體間的關(guān)系。例如，小王是個大學(xué)生

3大于23謂詞個體詞個體詞個體詞謂詞謂詞

形如“b是A”類型的命題可表達(dá)為A(b)；表示多個個體間關(guān)系的命題，可表達(dá)為B(a，b)，或P(a，b，c)定義2.1.2

和一個個體相聯(lián)系的謂詞稱為一元謂詞，和二個個體相聯(lián)系的謂詞稱為二元謂詞，和n個個體相聯(lián)系的謂詞稱為n元謂詞。

個體常元

表示具體的或特定的個體，如a，b，c，

等；個體變元

表示抽象的或泛指的個體，如x，y，z，

等。

謂詞常項(xiàng)

表示具體性質(zhì)或關(guān)系的謂詞，R(a)表示a是人；

謂詞變項(xiàng)

表示抽象或泛指的謂詞

，如：P(a)表示a具有P性質(zhì)。4謂詞表達(dá)式和命題函數(shù)定義2.1.3

一個原子命題可以用一個謂詞常項(xiàng)P和幾個個體常元，如a，b，c，

，表示成P(a，b，c，

)的形式。稱P(a，b，c，

)為原子命題或命題的謂詞表達(dá)式。

一個謂詞常項(xiàng)P和幾個個體變元如x，y，z，

表示成P(x，y，z，

)的形式，稱為命題函數(shù)，其中的個體變元可以代表任意一個個體。注意：命題的謂詞表達(dá)式是有真值的，命題函數(shù)的真值是不確定的。5例題寫出下列命題的謂詞表達(dá)式。

1.小王和小李是大學(xué)生。解：設(shè)A(x)：x是大學(xué)生。a：小王，b：小李。

A(a)

A(b)2.

北京是中國的首都。解：設(shè)F(x，y)：x是y的首都。a：北京，b：中國。F(a，b)3.如果你來，他就走。解：設(shè)P(x)：x來。Q(x)：x走。a：你，b：他。

P(a)

Q(b)6例題（續(xù)）4.如果3

2，2

1，則3

1。解：設(shè)B(x，y)：x

y。a：3，b：2，c：1。則

：

B(a，b)

B(b，c)

B(a，c)武漢位于北京和廣州之間。解：設(shè)Q(x，y，z)：y位于x和z之間。a：北京，b：廣州，c：武漢。Q(a，c，b)7個體域定義2.1.4命題函數(shù)中，個體變元的取值范圍稱為個體域或論述域。

個體域可以是有限的，也可以是無限的。把宇宙中一切事物作為對象的的集合稱為全總個體域。通常，沒有特別說明時，個體變元的論述域是指全總個體域。如：A(x)表示：x是大學(xué)生。個體域：華工計(jì)科1班學(xué)生，則A(x)是永真式。個體域：華工附中1班學(xué)生，則A(x)是永假式。個體域：xx公司員工，其中有些是大學(xué)生，有些不是大學(xué)生，則對有些人，A(x)為真，對有些人，A(x)為假。8例題給出執(zhí)行語句“If

P(x)then

x：=1”以后x的值，其中P(x)為語句“x

1”，且執(zhí)行到該語句時x的值如下：1)x=02)x=13)x=2解1)若x=0，P(x)為語句“0

1”，真值為0，不執(zhí)行賦值語句“x：=1”，所以x=0。2)若x=1，P(x)為語句“1

1”，真值為0，不執(zhí)行賦值語句“x：=1”，所以x=1。3)若x=2，P(x)為語句“2

1”，真值為1，執(zhí)行賦值語句“x：=1”，所以x=1。92.1.2量詞定義2.1.5表示個體常元或個體變元之間數(shù)量關(guān)系的詞稱為量詞。量詞有兩種：全稱量詞

符號：

x表示對個體域“所有的x”，“每一個x”，“一切x”等。存在量詞

符號：

x表示個體域中“存在這樣的x”，“某個x”，“至少有一個x”或“有一些x”等。

xF(x)表示個體域中所有個體都有性質(zhì)F

xF(x)表示個體域中存在個體有性質(zhì)F10例題假設(shè)F(x)表示x選修離散數(shù)學(xué)，x的個體域是這個班的同學(xué)，將下面的兩個命題符號化。這個班的所有學(xué)生都選修離散數(shù)學(xué)這個班有些學(xué)生選修離散數(shù)學(xué)解

當(dāng)個體域是這個班的同學(xué)時：

xF(x)

xF(x)若個體域是全總個體域時，要引入一個新的謂詞表示個體的取值范圍。稱這個表示個體范圍的謂詞為特性謂詞。11例題假設(shè)F(x)表示x選修離散數(shù)學(xué)，將下面的兩個命題符號化。這個班的所有學(xué)生都選修離散數(shù)學(xué)這個班有些學(xué)生選修離散數(shù)學(xué)解

（沒有特別說明時個體域是全總個體域）設(shè)特性謂詞S(x)：表示x是這個班的同學(xué)，

x(S(x)

F(x))

x(S(x)

F(x))注意：在使用全稱量詞時，

特性謂詞和表示個體性質(zhì)的謂詞構(gòu)成條件關(guān)系式；

在使用存在量詞時，特性謂詞和表示個體性質(zhì)的謂詞構(gòu)成合取關(guān)系式。12例題在個體域分別為：(a):自然數(shù)集合，(b):實(shí)數(shù)集合時，將下列命題符號化，并給出它們的真值。對于任意的x，均有x2?3x+2=(x?1)(x?2);存在x，使得x+5=2。解

假設(shè)F(x)：x2?3x+2=(x?1)(x?2)，G(x)：x+5=2。(a)個體域?yàn)樽匀粩?shù)集合。符號化為：

xF(x)，真值為1。符號化為：

xG(x)，真值為0。(b)個體域?yàn)閷?shí)數(shù)集合。符號化為：

xF(x)，真值為1。符號化為：

xG(x)，真值為1。13例題用謂詞邏輯將下列命題符號化。所有的偶數(shù)均能被2整除。解

設(shè)A(x)：x是偶數(shù)，B(x)：x能被2整除。

x(A(x)

B(x))這個班有些學(xué)生有電腦。解設(shè)A(x)：x是這個班的學(xué)生，B(x)：x有電腦。

x(A(x)

B(x))。14例題（續(xù)）沒有不犯錯誤的人。解設(shè)A(x)：x是人，B(x)：x犯錯誤。

x(A(x)

B(x))。盡管有人聰明，但未必一切人都聰明。解設(shè)A(x)：x是人，B(x)：x聰明。

x(A(x)

B(x))

x(A(x)

B(x))15例題（續(xù)）5.有些人喜歡某些體育運(yùn)動。解

設(shè)A(x)：x是人，B(y)：y是體育運(yùn)動，

C(x，y)：x喜歡y。

x(A(x)

y(B(y)

C(x，y)))。6.并非所有的工作都可以由一些機(jī)器人來完成。解設(shè)A(x)：x是工作，B(x，y)：x可以由y來完成，

R(x)：x是機(jī)器人。

x(A(x)

y(R(y)

B(x，y)))。16量詞當(dāng)論述域中的元素個數(shù)有限時，例如，論述域?yàn)閚個元素的集合{a1，a2，a3，

an}時，有

x

A(x)

A(a1)

A(a2)

A(a3)

A(an)

x

A(x)

A(a1)

A(a2)

A(a3)

A(an)17例題若P(x)是語句“x2>10”，論述域?yàn)椴怀^4的正整數(shù)，

xP(x)和

x

P(x)的真值是什么？

解

由于論述域?yàn)閧1，2，3，4}，命題

xP(x)為

x

P(x)

P(1)

P(2)

P(3)

P(4)而P(1)即“12>10”為假，所以

x

P(x)為假。命題

xP(x)為

x

P(x)

P(1)

P(2)

P(3)

P(4)而P(4)即“42>10”為真，所以

x

P(x)為真。18例題設(shè)P(x，y)表示“x+y>10”，論述域?yàn)閷?shí)數(shù)，

x

yP(x，y)和

y

xP