離散數(shù)學(xué)課件第二章(第1講)

第二章謂詞邏輯§1基本概念§2謂詞邏輯的翻譯§3謂詞公式的解釋§4謂詞演算的等價(jià)式與蘊(yùn)含式§5前束范式§6謂詞邏輯演的推理理論§1基本概念

在研究命題邏輯中，原子命題是命題演算中最基本的單位，不再對(duì)原子命題進(jìn)行分解.這樣會(huì)產(chǎn)生二大缺點(diǎn)：

（1）不能研究命題的結(jié)構(gòu)，成分和內(nèi)部邏輯的特征；

（2）也不可能表達(dá)二個(gè)原子命題所具有的共同特征，甚至在命題邏輯中無法處理一些簡(jiǎn)單又常見的推理過程。

例：蘇格拉底論證是正確的，但不能用命題邏輯的推理規(guī)則推導(dǎo)出來。

“所有的人總是要死的。P“蘇格拉底是人。Q“所以蘇格拉底是要死的?！盧1.謂詞《定義》：用以刻劃客體的性質(zhì)或關(guān)系的即是謂詞。

我們可把原子命題分解為二部分：主語（名詞，代詞）和謂語（動(dòng)詞）。例：張華是學(xué)生，李明是學(xué)生。則可把它表示成：

H:表示“是學(xué)生”，j:表示“張華”，m:表示“李明”，則可用下列符號(hào)表示上述二個(gè)命題：H(j)，H(m)。

H作為“謂詞”用大寫英文字母表示，j,m稱為“客體”或稱“個(gè)體”?？腕w一般用小寫的英文字母表示。分析：（1）若謂詞字母聯(lián)系著一個(gè)客體，則稱作一元謂詞；若謂詞字母聯(lián)系著二個(gè)客體，則稱作二元謂詞；若謂詞字母聯(lián)系著n個(gè)客體，則稱作n元謂詞。（2）客體的次序必須是有規(guī)定的。例：河南省北接河北省。

nLb寫成二元謂詞為：L(n,b)，但不能寫成L(b,n)。

2.命題函數(shù)客體在謂詞表達(dá)式中可以是任意的名詞。例：C—“是有顏色的?！?/p>

g：水果；y：樹葉；f：衣服。則C(g),C(y),C(f)都是命題。在上例中，如果用x表達(dá)任意的客體，則x表示客體變?cè)珻(x)表示“x是有顏色的”，則稱C(x)為命題函數(shù)?！抖x》由一個(gè)謂詞字母和一些非空的客體變?cè)募纤M成的表達(dá)式，稱為簡(jiǎn)單命題函數(shù)。

討論：

（a）當(dāng)簡(jiǎn)單命題函數(shù)僅有一個(gè)客體變?cè)獣r(shí)，稱為一元簡(jiǎn)單命題函數(shù)；

（b）若用某一特定客體去取代客體變?cè)螅瑒t命題函數(shù)就變?yōu)槊}；（c）命題函數(shù)中客體變?cè)娜≈捣秶Q為個(gè)體域（論述域）。（d）個(gè)體域（論述域）:用特定的集合表示的客體變?cè)娜≈捣秶?。例：P(x)表示x是素?cái)?shù)。這是一個(gè)命題函數(shù)。其值取決于個(gè)體域。個(gè)體域的給定形式有二種：①具體給定。如：｛j,e,t｝②全總個(gè)體域任意域：將各種個(gè)體域綜合在一起作為論述范圍的域稱全總個(gè)體域。命題函數(shù)可以轉(zhuǎn)變?yōu)槊}，有兩種方法：a)將x取定一個(gè)值。如：P(4)，P(5)b)將謂詞量化。如：xP(x)，xP(x)3.量詞（1）全稱量詞

“

”為全稱量詞符號(hào)，讀作“所有的”，“任意的”，“每個(gè)”。

例：“這里所有的都是蘋果”可寫成：

xA(x)或(

x)A(x)全稱量詞的幾種形式的讀法：

·

xP(x)：“對(duì)所有的x，x是…”；

·

x?P(x)：“對(duì)所有x，x不是…”；

·

?

xP(x)：“并不是對(duì)所有的x，x是…”；

·

?

x?P(x)：“并不是所有的x，x不是…”。例：將“對(duì)于所有x和所有y，如果x高于y，那么y不高于x”寫成命題表達(dá)形式。

解：G(x,y)：x高于y

xy(G(x,y)?G(y,x))

（2）存在量詞

“

”為存在量詞符號(hào)，讀作“存在一個(gè)”，“有些”，“某些”，“至少存在一個(gè)”等等。存在量詞的幾種形式的讀法：

·

xA(x)：存在x,使x是…；

·

x?A(x)：存在x,使x不是…；

·

?

xA(x)：不存在x,使x是…；

·

?

x?A(x)：不存在x,使x不是…。為什么將謂詞量化，命題函數(shù)可以轉(zhuǎn)變?yōu)槊}？設(shè)給定個(gè)體域：{a1…an},以{a1…an}中的每一個(gè)個(gè)體代入

則：

xP(x)

P(a1)

…

P(an)

xQ(x)

Q(a1)

…

Q(an)

例如：Q(x)表示:x<5

{-1,0,3}{-3,6,2}{15,30}

xQ(x)TFF

xQ(x)TTF注：個(gè)體域不同，則表示同一命題的值不同。4.謂詞公式

原子謂詞公式：不出現(xiàn)命題聯(lián)結(jié)詞和量詞的謂詞命名式稱為原子謂詞公式，并用P(x1…xn)來表示。（P稱為n元謂詞，x1…xn稱為客體變?cè)?/p>

《定義》（謂詞公式的歸納法定義）⑴原子謂詞公式是謂詞公式；⑵若A是謂詞公式，則?A也是謂詞公式；⑶若A,B都是謂詞公式，則(AB),(AB),(AB),(AB)都是謂詞公式；⑷若A是謂詞公式，x是任何變?cè)?，則

xA,

xA也都是謂詞公式；⑸當(dāng)且僅當(dāng)有限次地應(yīng)用⑴-⑷所求得的那些公式才是謂詞公式。5.自由變?cè)c約束變?cè)?1)轄域：緊跟在量詞后面括號(hào)內(nèi)的謂詞公式，叫做相應(yīng)量詞的作用域或轄域。例：

x(P(x)),

x(P(x)Q(x))

P(x)是全稱量詞的轄域，P(x)Q(x)是存在量詞的轄域。若量詞后括號(hào)內(nèi)為原子謂詞公式，則括號(hào)可以省去。例：

x(P(x))

xP(x)

轄域舉例①在

xP(x)Q(x)中,x的轄域是P(x);②在

y(C(y)∧x(T(x)uQ(x,u)))中,u的轄域是：Q(x,u);x的轄域是：T(x)uQ(x,u);y的轄域是：

C(y)∧x(T(x)uQ(x,u)).(2)自由變?cè)c約束變?cè)s束變?cè)何挥诹吭~的轄域內(nèi)，并且與量詞下標(biāo)相同的變?cè)?。自由變?cè)寒?dāng)且僅當(dāng)不受量詞約束的變?cè)＠?/p>

xP(x,y),

xP(x)Q(y)

在謂詞公式

xP(x,y)中，x是約束變?cè)瑈是自由變?cè)?。在謂詞公式

xP(x)Q(y)中，x是約束變?cè)?，y是自由變?cè)?。注：自由變?cè)梢晕挥诹吭~的轄域內(nèi)，也可以不在量詞的轄域內(nèi)。(3)區(qū)別是命題還是命題函數(shù)的方法

（a）若謂詞公式中有自由變?cè)瑒t該公式為命題函數(shù)；（b）若謂詞公式中的變?cè)际羌s束變?cè)?，則該公式為命題?；蛘哒f若謂詞公式中沒有自由變?cè)霈F(xiàn)，則該公式是一個(gè)命題。例：

xP(x,y,z)是二元命題函數(shù)

yxP(x,y,z)是一元命題函數(shù)

yxP(x,y)是命題(4)約束變?cè)母拿?guī)則

我們認(rèn)為xP(x,y)和zP(z,y)是等價(jià)的謂詞公式，所以任何謂詞公式對(duì)約束變?cè)伎梢愿拿?。但是，不能用同一個(gè)變?cè)ケ硎局^詞公式中的二個(gè)不同變?cè)?。例如：xP(x,y)和yP(y,y)是不等價(jià)的。約束變?cè)母拿?guī)則：

（a）改名時(shí)所用的變?cè)?hào)在量詞轄域內(nèi)未出現(xiàn)的；（b）在改名時(shí)要把公式中所有相同的約束變?cè)客瑫r(shí)改掉。例：xP(x)yR(x,y)可改寫成:xP(x)zR(x,z)但不能改成:xP(x)xR(x,x)因?yàn)樵谥^詞公式xR(x,x)中，前面的x原為自由變?cè)?，現(xiàn)在變?yōu)榧s束變?cè)恕?5)自由變?cè)拇胍?guī)則

對(duì)謂詞公式中的自由變?cè)母慕凶龃搿?/p>

(a)用以代入的變?cè)c原公式中所有變?cè)拿Q不能相同。

(b)對(duì)公式中出現(xiàn)該自由變?cè)拿恳惶幎歼M(jìn)行代入?！?謂詞公式的翻譯一般來說，將自然語言翻譯成謂詞公式主要有以下幾個(gè)步驟：

（1）確定個(gè)體域，如無特別說明，一般使用全總個(gè)體域；（2）根據(jù)個(gè)體域，分析命題中的個(gè)體、個(gè)體性質(zhì)以及各個(gè)個(gè)體間的關(guān)系，確定謂詞；（3）根據(jù)表示數(shù)量的詞確定量詞；如果使用全總個(gè)體域，則要加入特性謂詞。（4）利用聯(lián)結(jié)詞將整個(gè)命題符號(hào)化。例：某個(gè)人很聰明。令C(x)：x很聰明。下面給出不同的個(gè)體域來討論命題的翻譯：①個(gè)體域?yàn)椋簕人類}則可翻譯為:

xC(x)；②個(gè)體域?yàn)槿我庥颍ㄈ倐€(gè)體域），則人必須首先從任意域中分離出來。設(shè)M(x)表示：x是人，M(x)為特性謂詞。

則可翻譯為:

x(M(x)

C(x))特性謂詞：用來限制個(gè)體變?cè)≈捣秶闹^詞。(2)對(duì)于同一個(gè)體域，用不同的量詞時(shí)，特性謂詞加入的方法不同。

對(duì)于全稱量詞，其特性謂詞以條件聯(lián)結(jié)詞的前件的方式加入；

對(duì)于存在量詞，其特性謂詞以合取的形式加入。注:(1)個(gè)體域不同，表示同一命題的謂詞公式的形式不同。

例：（1）每個(gè)學(xué)生都要參加考試。令S(x)：x是學(xué)生（特性謂詞）T(x):x要參加考試

可翻譯為:

x(S(x)

T(x))

（2）一些人是聰明的。令M(x):x是人（特性謂詞）C(x)：x是聰明的。可翻譯為:

x(M(x)∧C(x))

解：設(shè)I(x):x是整數(shù)；（特性謂詞）R1(x)：x是正數(shù)；R2(x)：x是負(fù)數(shù)。此句可翻譯為：

x(I(x)(R1(x)

R2(x))。例：任何整數(shù)或是正的，或是負(fù)的。例：試將蘇格拉底論證符號(hào)化：“所有的人總是要死的。因?yàn)樘K格拉底是人，所以蘇格拉底是要死的?！?/p>

解：設(shè)M(x)：x是人；（特性謂詞）D(x)：x是要死的；

M(s)：蘇格拉底是人；D(s)：蘇格拉底是要死的。則翻譯為：

x(M(x)

D(x))，M(s)

D(s)例：“沒有不犯錯(cuò)的人。”

解：設(shè)F(x)為“x犯錯(cuò)誤”，M(x)為“x是人”（特性謂詞）。則可翻譯為：?(

x(M(x)

?

F(x)))也可以翻譯為：

x(M(x)F(x))解：T(x):x坐頭等艙J(x):x坐經(jīng)濟(jì)艙F(x):x家境富裕前提：x(T(x)

J(x)),

x(T(x)

F(x))

,

xF(x),

xF(x)

例：每個(gè)乘客或坐頭等艙或坐經(jīng)濟(jì)艙；每個(gè)乘客當(dāng)且僅當(dāng)其家境富裕時(shí)坐頭等艙；有些乘客家境富裕；并非所有的乘客都家境富裕。因此，有些乘客坐經(jīng)濟(jì)艙。（個(gè)體域?yàn)槿w乘客構(gòu)成的集合）結(jié)論：

xJ(x)則 可翻譯為：

(x)(S(x)L(x)H(x)G(x)S(x))由于對(duì)個(gè)體描述性質(zhì)的刻劃深度不同，可翻譯成不同形式的謂詞公式。例

：在南京高校學(xué)習(xí)的學(xué)生，未必都是南京籍的學(xué)生。設(shè)S(x)：x是南京高校學(xué)習(xí)的學(xué)生。F(x)：x是南京籍的學(xué)生。則翻譯為：

x(S(x)F(x))

本題也可加深刻劃：S(x)：x是學(xué)生。L(x)：x在學(xué)習(xí)。