離散數學課件

第二章謂詞邏輯§1謂詞的概念與表示法§2命題函數與量詞§3謂詞公式與翻譯§4變元的約束§5謂詞演算的等價式與蘊含式§6前束范式§7謂詞演算的推理理論§1謂詞的概念與表示法

在研究命題邏輯中，原子命題是命題演算中最基本的單位，不再對原子命題進行分解，這樣會產生二大缺點：

（1）不能研究命題的結構，成分和內部邏輯的特征；

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

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

“所有的人總是要死的。A“蘇格拉底是人。B“所以蘇格拉底是要死的?！盋§1謂詞的概念與表示法1.謂詞：《定義》：用以刻劃客體的性質或關系的即是謂詞。

我們可把陳述句分解為二部分：主語（名詞，代詞）和謂語（動詞）。例：張華是學生，李明是學生。則可把它表示成：

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

H作為“謂詞”（或者謂詞字母）用大寫英文字母表示，j,m為主語，稱為“客體”或稱“個體”。

§1謂詞的概念與表示法（1）謂詞填式：謂詞字母后填以客體所得的式子。例：H(a,b)（2）若謂詞字母聯系著一個客體，則稱作一元謂詞；若謂詞字母聯系著二個客體，則稱作二元謂詞；若謂詞字母聯系著n個客體，則稱作n元謂詞。（3）客體的次序必須是有規(guī)定的。

例：河南省北接河北省。

nLb

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

§2命題函數與量詞1.命題函數客體在謂詞表達式中可以是任意的名詞。

例：C—“總是要死的?！?/p>

j：張三；t：老虎；e：桌子。則C(j),C(t),C(e)均表達了命題。

在上面的例子中，C：表示“總是要死的”；x：表示變元（客體變元），則C(x)表示“x總是要死的”，則稱C(x)為命題函數?！抖x》由一個謂詞字母和一個非空的客體變元的集合所組成的表達式，稱為簡單命題函數。

§2命題函數與量詞討論定義：

（a）當簡單命題函數僅有一個客體變元時，稱為一元簡單命題函數；

（b）若用任何客體去取代客體變元之后，則命題函數就變?yōu)槊}；

（c）命題函數中客體變元的取值范圍稱為個體域（論述域）。例：P(x)表示x是質數。這是一個命題函數。其值取決于個體域。可以將命題函數命題，有兩種方法：§2命題函數與量詞a)將x取定一個值。如：P(4)，P(5)b)將謂詞量化。如：xP(x)，xP(x)個體域的給定形式有二種：①具體給定。如：｛j,e,t｝②全總個體域任意域：所有的個體從該域中取得?！?命題函數與量詞2.量詞（1）全稱量詞

“

”為全稱量詞符號，讀作“對于所有的”，“對任一個”，“對一切”。

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

xA(x)或(

x)A(x)幾種形式的讀法：

·

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

·

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

·?

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

·?

x?P(x)：“并不是所有的x，x不是…”?！?命題函數與量詞例：將“對于所有的x和任何的y，如果x高于y，那么y不高于x”寫成命題表達形式。

解：

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

G(x,y)：x高于y（2）存在量詞

“

”為存在量詞符號，讀作“存在一個”，“對于一些”，“對于某些”，“至少存在一個”，“這里存在著這樣的”等等。“

”表達式的讀法：

·

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

·

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

·?

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

·?

x?A(x)：不存在一個x,使x不是…。§2命題函數與量詞例：（a）存在一個人；（b）某個人很聰明；（c）某些實數是有理數將（a）,（b）,（c）寫成命題。解：規(guī)定：M(x)：x是人；C(x)：x是很聰明；

R1(x)：x是實數(特性謂詞)R2(x)：x是有理數。則（a）

xM(x)；（b）

x(M(x)C(x))；（c）

x(R1(x)

R2(x))

。（3）量化命題的真值：決定于給定的個體域給定個體域：{a1…an}以{a1…an}中的每一個代入

xP(x)

P(a1)

…

P(an)

xQ(x)

Q(a1)

…

Q(an)

§3謂詞公式與翻譯1.謂詞公式

原子謂詞公式：不出現命題聯結詞和量詞的謂詞命名式稱為原子謂詞公式，并用P(x1…xn)來表示。（P稱為n元謂詞，x1…xn稱為客體變元），當n=0時稱為零元謂詞公式。

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

xA,

xA也都是謂詞公式；

§3謂詞公式與翻譯⑸只有按⑴-⑷所求得的那些公式才是謂詞公式（謂詞公式又簡稱“公式”）。

例1：任何整數或是正的，或是負的。

解：設：I(x):x是整數；R1(x)：x是正數；R2(x)：x是負數。此句可寫成：

x(I(x)(R1(x)

R2(x))。例2：試將蘇格拉底論證符號化：“所有的人總是要死的。因為蘇格拉底是人，所以蘇格拉底是要死的?！?/p>

解：設M(x)：x是人；D(x)：x是要死的；

M(s)：蘇格拉底是人；D(s)：蘇格拉底是要死的?！?謂詞公式與翻譯寫成符號形式：

x(M(x)

D(x))，

M(s)

D(s)2.由于對個體描述性質的刻劃深度不同，可翻譯成不同形式的謂詞公式?！?變元的約束1.轄域：緊接在量詞后面括號內的謂詞公式。例：

xP(x),

x(P(x)Q(x))

。

若量詞后括號內為原子謂詞公式，則括號可以省去。2.自由變元與約束變元

約束變元：在量詞的轄域內，且與量詞下標相同的變元。自由變元：當且僅當不受量詞的約束。例：

xP(x,y),

x(P(x)

y(P(x,y))。

§4變元的約束3.約束變元的改名規(guī)則

任何謂詞公式對約束變元可以改名。我們認為xP(x,y)和zP(z,y)是一等價的謂詞公式，但是需注意，不能用同一變元去表示同一謂詞公式中的二個變元。例如：yP(y,y)是不正確的。

下面介紹約束變元的改名規(guī)則：

（a）在改名中要把公式中所有相同的約束變元全部同時改掉；

（b）改名時所用的變元符號在量詞轄域內未出現的。

§4變元的約束例：

xP(x)yR(x,y)可改寫成

xP(x)zR(x,z)

，但不能改成

xP(x)xR(x,x)

，

xR(x,x)中前面的x原為自由變元，現在變?yōu)榧s束變元了。4.區(qū)別是命題還是命題函數的方法

（a）若在謂詞公式中出現有自由變元，則該公式為命題函數；

（b）若在謂詞公式中的變元均為約束出現，則該公式為命題。例：

xP(x,y,z)是二元謂詞，

yxP(x,y,z)是一元謂詞，而謂詞公式中如果沒有自由變元出現，則該公式是一個命題。

§4變元的約束舉例：例1：“沒有不犯錯的人?！?/p>

解：設F(x)為“x犯錯誤”，M(x)為“x是人”（特性謂詞）。可把此命題寫成：?(

x(M(x)

F(x)))

x(M(x)F(x))例2：“x是y的外祖父”“x是z的父親且z是y的母親”

設P(z)：z是人；F(x,z)：x是z的父親；M(z,y)：z是y的母親。

則謂詞公式可寫成：z(P(z)F(x,z)M(z,y))。5.代入規(guī)則：對公式中的自由變元的更改叫做代入。

(a)對公式中出現該自由變元的每一處進行代入，

(b)用以代入的變元與原公式中所有變元的名稱不能相同。§4變元的約束6.個體域（論述域，客體域）:用特定的集合表示的被約束變元的取值范圍。(1)個體域不同，則表示同一命題的謂詞公式的形式不同。

例：“所有的人必死?！绷頓(x)，x是要死的。下面給出不同的個體域來討論：(ⅰ)個體域為：{人類}，則可寫成

xD(x)；(ⅱ)個體域為任意域（全總個體域），則人必須首先從任意域中分離出來，設M(x)，x是人，稱M(x)為特性謂詞。

命題可寫成

x(M(x)

D(x))§4變元的約束（2）個體域不同，則表示同一命題的值不同。Q(x):x<5

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

xQ(x)TFF

xQ(x)TTF（3）對于同一個體域，用不同的量詞時，特性謂詞加入的方法不同。

對于全稱量詞，其特性謂詞以前件的方式加入；

對于存在量詞，其特性謂詞以與的形式加入?！?變元的約束例：設個體域為:{白虎（白貓），黃咪（黃貓），，}，同時令C(x)：x是貓（特性謂詞）；B(x)：x是黑色的；A(x)：x是動物。（ⅰ）描述命題：“所有的貓都是動物”。即：

x(C(x)

A(x))（T）（真命題）寫成

x(C(x)

A(x))（F）則為假命題了?！選(C(x)

A(x))TT

T

TT

x(C(x)

A(x))TTFFF（ⅱ）描述命題：“一些貓是黑色的”。

x(C(x)

B(x))FFFFF而x(C(x)

B(x))FFTTT§4變元的約束7.量詞對變元的約束，往往與量詞的次序有關。例：

yx(x<y-2))表示任何y均有x，使得x<y-2。

§5謂詞演算的

等價式與蘊含式

基本定義

《定義》A，B為二個謂詞公式，E為它們共同個體域，若對A和B的任一組變元進行賦值，使得A和B的值相同，則稱A和B遍及E是互為等價的，記為AB或

AE

B《定義》給定謂詞公式A，E是A的個體域。若給A中客體變元指派E中的每一個客體名稱所得命題的值均為真，則稱A在E中是永真的。若E為任意域則稱A是永真的。

§5謂詞演算的

等價式與蘊含式《定義》給定謂詞公式A，E是A的個體域。若給A中客體變元指派E中每一個客體名稱，在E中存在一些客體名稱，使得指派后的真值為“T”，則A稱是可滿足的。《定義》若給A中客體變元指派個體域中任一客體名稱，使命題的值均為“F”，則稱A是永假的。

1.不含量詞的謂詞公式的永真式:只要用原子謂詞公式去代命題公式的永真式中的原子命題變元，則在第一章中永真蘊含式和等價公式均可變成謂詞演算中的永真式：§5謂詞演算的

等價式與蘊含式

命題邏輯謂詞邏輯

??Ｐ

Ｐ??Ｐ(x)

Ｐ(x)

Ｐ∨Ｐ

ＰＰ(x)∨Ｐ(x)

Ｐ(x)

....Ｐ→Ｑ

?Ｑ→?ＰＰ(x)→Ｑ(x)

?Ｑ(x)→?Ｐ(x)

Ｐ

Ｐ∨ＱＰ(x)

Ｐ(x)∨Ｑ(x)

ＰΛＱ

ＰＰ(x)ΛＱ(x)

Ｐ(x)......

§5謂詞演算的

等價式與蘊含式2.含有量詞的等價式和永真蘊含式設個體域為：S={a1,a2,…an}，我們有：

xA(x)A(a1)A(a2)…A(an)

xA(x)A(a1)A(a2)…A(an)上例說明：若個體域是有限的，則可省掉量詞。若個體域是無限的，則可將上述概念推廣從而省去量詞，不過要注意這是由無限項組成的命題。

§5謂詞演算的

等價式與蘊含式例：設個體域為：N={0,1,2…}，

P(x)表示：x>3,則可寫出：

xP(x)P(0)P(1)…P(i)…

xP(x)P(0)P(1)…P(i)…下面分類介紹在謂詞公式中含有量詞的等價式和永真蘊含式。

（1）量詞轉換律：

E25(Q3)?

xP(x)

x?P(x)E26(Q4)

?

xP(x)

x?P(x)下面證明：設個體域為：S={a1,a2,…an}§5謂詞演算的

等價式與蘊含式

?

xP(x)

?(P(a1)P(a2)…P(an))

?P(a1)?P(a2)…?P(an)

x?P(x)

下面舉例說明量化命題和非量化命題的差別:否定形式不同

例：否定下列命題：

(a)上海是一個小城鎮(zhèn)A(s)(b)每一個自然數都是偶數

x(N(x)E(x))上述二命題的否定為：

(a)上海不是一個小城鎮(zhèn)?A(s)

(b)有一些自然數不是偶數

?

x(N(x)E(x))

x?(N(x)E(x))

x?(N(x)E(x))

x(N(x)

?E(x))§5謂詞演算的

等價式與蘊含式結論：對于非量化命題的否定只需將動詞否定，而對于量化命題的否定不但對動詞進行否定而且對量詞同時進行否定，其方法是：

x的否定變?yōu)?/p>

x

，

x的否定變?yōu)?/p>

x

。（2）量詞轄域的擴張及其收縮律

E27(Q6)

xA(x)

P

x(A(x)

P)(Q7)

xA(x)

P

x(A(x)

P)E28(Q9)

xA(x)

P

x(A(x)

P)(Q8)

xA(x)

P

x(A(x)

P)P為不含有變元Ｘ的任何謂詞公式§5謂詞演算的

等價式與蘊含式證明E27(Q6)，設個體域為：S={a1,a2,…an}

xA(x)

P(A(a1)A(a2)…A(an))

P

(A(a1)

P)(A(a2)

P)…(A(an)

P)

x(A(x)

P)

E30

(Q14)

xA(x)B

x(A(x)B)

E31

(Q15)

xA(x)B

x(A(x)B)

E32(Q16)A

xB(x)

x(AB(x))

E33

(Q17)A

x

B(x)

x(AB(x))證明E30(Q14)，設個體域為：S={a1,a2,…an}

x(A(x)B)(A(a1)B)…(A(an)B)

(?A(a1)

B)…(?A(an)

B)§5謂詞演算的

等價式與蘊含式

(?A(a1)

…?A(an))B

x?A(x)B

?

x(A(x)B)

xA(x)B（3）量詞分配律E24(Q10)

x(A(x)

B(x))

xA(x)

xB(x)E23

(Q11)

x(A(x)B(x))

xA(x)

xB(x)

I18(Q12)

x(A(x)

B(x))xA(x)

xB(x)I17(Q13)

xA(x)

xB(x)x(A(x)

B(x))E29(Q18)

x(A(x)

B(x))

xA(x)

xB(x)I19(Q19)

xA(x)

xB(x)x(A(x)

B(x))§5謂詞演算的

等價式與蘊含式證明E24(Q10)和I19(Q19)

，設個體域為：S={a1,a2,…an}E24(Q10)

x(A(x)

B(x))

(A(a1)

B(a1))….

(A(an)

B(an))

(A(a1)…A(an))

(B(a1)…B(an))

xA(x)

x

B(x)I19(Q19)

xA(x)

xB(x)?

xA(x)

xB(x)

x?A(x)

xB(x)

(?A(a1)…?A(an))(B(a1)…B(an))

(?A(a1)

B(a1))…(?A(a1)

B(an))

……

(?A(an)

B(a1))…(?A(an)

B(an))§5謂詞演算的

等價式與蘊含式

(?A(a1)

B(a1))…(?A(an)

B(an))

x(?A(x)B(x))

x(A(x)B(x))（4）量詞的添加和除去的永真蘊含式

Q1

xP(x)P(y)Q2P(y)xP(x)Q5

xP(x)

xP(x)

xPP

xPP

(P為不含x變元）Y是ｘ個體域中任一元素§5謂詞演算的

等價式與蘊含式（5）含有多個量詞的永真式：

（?。┝吭~出現的次序直接關系到命題的含義：

“

xy”表示：“無論選定一個什么樣的x值總能找到一個y能使x和y…”“yx”表示：“只選取一個y值，以致無論怎樣選定一個x，能夠使y和x…”

下面列出對應的表達式可以看出其不同處：

設x的個體域為：{a1,a2,…an}，

y的個體域為：{b1,b2,…bn}，

則：

xyP(x,y)

yP(a1,y)…yP(an,y)

§5謂詞演算的

等價式與蘊含式

(P(a1,b1)

…

P(a1,bn))…

(P(an,b1)

…

P(an,bn))yxP(x,y)

xP(x,b1)

…

xP(x,bn)

(P(a1,b1)

…P(an,b1))…

(P(a1,bn)

…P(an,bn))例：x,y的個體域{鞋子}，P(x,y):Ｘ和Ｙ配成一雙鞋子。

xyP(x,y)

TyxP(x,y)F§5謂詞演算的

等價式與蘊含式（ⅱ）在含有多個量詞的謂詞公式中,

xy,xy的位置是可以改變的,且不影響命題的真值。

例：x,y的個體域為N={0,1,2…}，則

xyP(x,y)

yP(0,y)…yP(i,y)…

(P(0,0)P(0,1)…P(0,j)…)…(P(i,0)P(i,1)…P(i,j)…)…(P(0,0)P(1,0)…P(i,0)…)(P(0,1)P(1,1)…P(i,1)…)…

xP(x,0)

xP(x,1)…

xP(x,j)…

yxP(x,y)

§5謂詞演算的

等價式與蘊含式同樣：

xyP(x,y)yxP(x,y)（ⅲ）量詞轉換律的推廣應用:把?深入到謂詞公式前面去的方法。

?

xyzP(x,y,z)x?yzP(x,y,z)xy?

zP(x,y,z)xyz?P(x,y,z)

（ⅳ）兩個量詞

,所組成的謂詞公式的等價式和永真蘊含式（8個）

x

yP(x,y)

y

xP(x,y)

x

yP(x,y)yxP(x,y)

y

xP(x,y)xyP(x,y)yxP(x,y)

xyP(x,y)§5謂詞演算的

等價式與蘊含式xyP(x,y)

yxP(x,y)

xyP(x,y)

yxP(x,y)

yxP(x,y)

xyP(x,y)

xyP(x,y)

yxP(x,y)（6）謂詞公式的對偶式《定義》

在一個謂詞公式A中（其中不出現

,詞）把公式A中

,,F,T,,,

變?yōu)楣紸*中

,,T,F,,,則稱A*是A的對偶式?！抖ɡ怼?/p>

若謂詞公式A

B，則A*

B*

；若謂詞公式A

B，則B*

A*

（這里A,B有同樣的個體域）?！?謂詞演算的

等價式與蘊含式例：

I17(Q13)

xA(x)

xB(x)

x(A(x)

B(x))I18(Q12)

xA(x)

xB(x)

x(A(x)

B(x))

§6前束范式《定義》一個公式，如果量詞均非否定地在全式的開頭，它們的作用域延伸到整個公式的末尾，則稱此公式叫前束范式。例：

xyz(?Q(x,y)R(z))(前束范式)

《定理》

任何一個謂詞公式均和一個前束范式等價。

證明：①利用量詞轉換把?深入到原子謂詞公式前,

②利用約束變元的改名規(guī)則，③利用量詞轄域的擴張收縮律,把量詞移到全式的最前面，這樣一定可得到等價的前束范式。§6前束范式例：

xP(x)R(x)yP(y)R(x)

y(P(y)R(x))例：把

xP(x)

xQ(x)

變成前束范式。

xP(x)

xQ(x)

?

xP(x)

xQ(x)

x?P(x)

xQ(x)

x(?P(x)

Q(x))

§7謂詞演算的推理理論1.含有量詞的特殊永真式《定義》設A(x)是一個謂詞公式，x是其中的自由變元，若把y代入到A(x)里而不會產生變元的新的約束出現，則稱A(x)對于y是自由的。例：下面A(x)對于y是自由的：

①A(x)

zP(z)Q(x,z),這里x為自由變元,若用y去取代A(x)中的x,A(y)

zP(z)Q(y,z),這里y也仍為自由變元；§7謂詞演算的推理理論②下面A(x)對于y不是自由的：

A(x)

y(S(x)S(y)),x為自由變元，若用y代入A(x)的x中去得：

A(y)

y(S(y)S(y))

，y變?yōu)榧s束變元了，產生了新的約束出現。如有必要代入y，則應先將式中的約束變元y改名。

z(S(x)S(z))然后代入y z(S(y)S(z))y仍為自由變元。歸結：判定A(x)對于y是自由的，只要看公式A(x)中

y,y的轄域內有沒有x的自由出現就行：若有x的自由出現則A(x)對于y不是自由的，若無的x自由出現則一定可以肯定A(x)對于y是自由的?！?謂詞演算的推理理論下面分別介紹四個推理規(guī)則（1）全稱指定規(guī)則（US規(guī)則）。

如果對個體域中所有客體x,A(x)成立，則對個體域中某個任意客體c，A(c)成立。該規(guī)則表示成：

xA(x)A(c)(x,c個體域)

（2）全稱推廣規(guī)則（UG規(guī)則）如果能夠證明對個體域中每一個客體c，命題A(c)都成立，則可得到結論

xA(x)

成立。該規(guī)則表示成：

A(x)

xA(x)

§7謂詞演算的推理理論（3）存在指定規(guī)則（ES規(guī)則）

如果對于個體域中某些客體A(x)成立，則必有某個特定的客體c，使A(c)成立。該規(guī)則表示成：

xA(x)A(c)

例：x的個體域為I={整數}，P(x):x是偶數，Q(x):x是奇數。

xP(x)

xQ(x)T但

P(c)

Q(c)F§7謂詞演算的推理理論（4）存在推廣規(guī)則（EG規(guī)則）如果對個體域中某個特定客體c，有A(c)成立，則在個體域中，必存在x，使A(x)成立。該規(guī)則表示成：

A(c)

xA(x)2推論規(guī)則及使用說明命題邏輯中的P,T,CP規(guī)則和簡接證明法，都可以引用到謂詞邏輯的推論規(guī)則中來，不過要注意對量詞做適當處理，其方法是：用US,ES在推導中去掉量詞，用UG,EG使結論量化。

§7謂詞演算的推理理論規(guī)則使用說明：

（1）在使用ES,US時一定要是前束范式

（2）推導中連續(xù)使用US規(guī)則可用相同變元

xP(x)P(y),

xQ(x)Q(y),

（3）推導中既ES用，又用US，則必須先用ES，后用US方可取相同變元，反之不行。

xP(x)P(y)

xQ(x)Q(y)

（4）推導中連續(xù)使用ES規(guī)則時，使用一次更改一個變元。

§7謂詞演算的推理理論例：證明蘇格拉底論證

x(M(x)D(x))M(s)

D(s)(1)M(s)P(2)

x(M(x)D(x))P(3)M(s)D(s)US(4)D(s)T例：證：

x(H(x)M(x)),xH(x)

xM(x)§7謂詞演算的推理理論(1)

xH(x) P(2)H(c)ES(3)

x(H(x)M(x)) P(4)H(c)M(c) US(5)M(c) T(6)xM(x) EG例：證:

x(P(x)Q(x))xP(x)

xQ(x)(1)

xP(x) 引入前件

(2)

x(P(x)Q(x)) P(3)P(c)Q(c) ES

§7謂詞演算的推理理論

(4)P(c) US(5)Q(c) T(6)

xQ(x) EG(7)

xP(x)xQ(x)CP例：證明：

?x(P(x)Q(x)),

xP(x)?xQ(x)(1)??xQ(x) 假設前提

(2)

xQ(x) T(3)Q(c) US(4)

xP(x) P

§7謂詞演算的推理理論

(5)P(c) US(6)P(c)Q(c) T(7)

x(P(x)Q(x)) UG(8)?x(P(x)Q(x)) P(9)

x(P(x)Q(x))?x(P(x)Q(x))T(10)F例：下列結論能否從前提中推出：

x(P(x)Q(x)),?Q(a)x?P(x)a為x個體域中一個元素

(1)?Q(a) P(2)x(P(x)Q(x)) P§7謂詞演算的推理理論(3)P(a)Q(a) US(4)?P(a) T(5)

x?P(x) UG在使用US,ES,UG,EG這四條規(guī)則時,要注意嚴格按照它們的規(guī)定去使用?！?謂詞演算的推理理論書中例4證明：(1)x(y(S(x,y)M(y))z(P(z)R(x,z)) P(2)y(S(b,y)M(y))z(P(z)R(b,z)) US(1)(3)(z)P(z) 附加前提(4)z(P(z)) T(3)(5)P(a) US(4)(6)P(a)R(b,a) T(5)(7)(P(a)R(b,a)) T(6)(8)z(P(z)R(b,z)) UG(7)(9)z(P(z)R(b,z)) T(8)§7謂詞演算的推理理論(10)y(S(b,y)M(y)) T(2)(9)(11)y(S(b,y)M(y)) T(10)(12)(S(b,c)M(c)) US(11)(13)S(b,c)M(c) T(12)(14)S(b,c)M(c) T(13)(15)y(S(b,y)M(y)) UG(14)(16)xy(S(x,y)M(y)) UG(15)(17)(z)P(z)xy(S(x,y)M(y)) CP(3)(16) §7謂詞演算的推理理論例：

二個量詞的推理比較復雜：

xP(x)

x(P(x)Q(x)R(x)),

xP(x),

xQ(x)

x

y(R(x)R(y))(1)

xP(x) P(2)P(w) ES(3)P(w)Q(w) T(4)

xP(x)

x(P(x)Q(x)R(x)) P(5)

x(P(x)Q(x)R(x)) T§7謂詞演算的推理理論(6)P(w)Q(w)R(w) US(7)R(w) T(8)xR(x) EG(9)

xQ(x) P(10)Q(z) ES(11)P(z)Q(z) T(12)P(z)Q(z)R(z) US

§7謂詞演算的推理理論(13)R(z) T(14)

yR(y) EG(15)

xR(x)

yR(y) T(16)

x

y(R(x)R(y)) T

三個量詞的推理過程更為復雜

第二章小結學習第二章要注意以下幾點：(1)同一個命題在不同個體域內可能有不同的符號化形式，同時也可能有不同的真值，因而在將一個命題符號化之前，必須弄清個體域。(2)在將命題符號化時，要特別注意量詞與聯結詞的搭配。經常的情況是全稱量詞與蘊含詞搭配，存在量詞與合取詞搭配。因此有下面兩種形式的公式：

x(A(x)B(x))① x(A(x)B(x))②而

x(A(x)B(x)) ③ x(A(x)B(x))④第二章小結③與①，④與②的含義完全不同。(3)記住主要的等價式。會用約束變元和自由變元換名規(guī)則進行等價演算，求出給定公式的前束范式。(4)在謂詞演算的推理證明中，要特別注意US，UG，ES，EG規(guī)則成立的條件。例題選講例1.符號化下列命題：(1)沒有不犯錯誤的人；(2)發(fā)光的不都是金子；(3)在南京高校學習的學生，未必都是南京籍的學生。解：(1)設M(x)：x是人。Q(x)：x犯錯誤。本題符號化為：

x(M(x)Q(x))或者：(x)(M(x)Q(x))(2)設L(x)：x是發(fā)光的東西。G(x)：x是金子。

x(L(x)G(x))或x(L(x)G(x))例題選講(3)設S(x)：x是南京高校學習的學生。

F(x)：x是南京籍的學生。則

x(S(x)F(x))

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

H(x)：x在南京高校。

G(x)：x是南京籍的人。則

(x)(S(x)L(x)H(x)G(x)S(x))例題選講例2.寫出

x(F(x)G(x))(xF(x)xG(x))的前束范式。解：原式x(F(x)G(x))((x)F(x)(x)G(x)) (x)(F(x)G(x))((x)F(x)(x)G(x)) (x)((F(x)G(x))G(x))(x)F(x)

(x)((F(x)G(x))(x)F(x) (x)((F(x)G(x))(y)F(y) (x)(y)(F(x)G(x)F(y))作業(yè)P8 1，5P11 1，5P18 4(c)，6，7(a),(b)P23 1，2，6，8(c),(d)P29 2，3P39 1，2(b)，3(b)，4(c),(f)，5(b)P46 1(a),(b)，2(a)，4(a)P59 1(d)(g)(h)，2(d)(i)(l)P62 1(f)(g)，5作業(yè)P65 1(c)，2(c)，4P72 6，7P75 1(b)(c)P79 1(a)(d)，2(a)，3(b)64代數系統

第六章 格和布爾代數

§1格的概念

§2分配格

§3有補格

§4*布爾代數65§1格的概念1.偏序集合格《定義》格是一個偏序集合

，其中每一對元素都擁有一個最小上界和最大下界。通常用

表示a和b的最大下界，用表示a和b的最小上界。即：

——稱為元素a和b的保交運算，

——稱為元素a和b的保聯運算。66§1格的概念例：以下均為偏序集合格（D為整除關系，Sn為n的因子集合）。67§1格的概念2.代數系統格《定義》：設是一個格，如果在A上定義兩個二元運算

和

，使得對于任意的a，bA，a

b等于a和b的最小上界，a

b等于a和b的最大下界，那么就稱<L,

,

>為由格所誘導的代數系統。68§1格的概念3.格的主要性質：(1)格的對偶原理設<L,≤>是格，“≤”的逆關系“≥”與L組成的偏序集<L,≥>也是格。兩者互為對偶。前者的GLB，LUB恰好是后者的LUB，GLB。如有關于<L,≤>的有效命題，將“≤”換成“≥”，“

”換成“

”，“

”換成“

”，便能得到<L,≥>的有效命題。反之亦然。69§1格的概念(2)對格<L,≤>中任意a和b，有a≤a

b及a

b≤a。(3)<L,≤>是格。對任意a,b,c,dL，如a≤b，c≤d，則

a

c≤

b

d，a

c≤b

d7071§1格的概念(4)（交換律）交和并運算是可交換的。(5)（結合律）交和并運算是可結合的。72§1格的概念(6)（冪等律）對L中每一個a，有a

a=a，a

a=a。(7)（吸收律）對L中任意a，b， 有a

(a

b)=a

a

(a

b)=a。73§2分配格

對格所定義的代數系統<L,

,

>，其運算

和

不一定滿足分配律。《定義》設<L,

,

>是由<L,≤>所誘導的代數系統。如果對任意的a,b,cL，滿足：

a

(b

c)=(a

b)

(a

c)及 a

(b

c)=(a

b)

(a

c)則稱<L,≤>是分配格。74§2分配格討論定義：(1)定義中的兩式互為對偶式。(2)如<L,≤>非為分配格，則有下面的分配不等式：

a

(b

c)≤(a

b)

(a

c)a

(b

c)≥

(a

b)

(a

c)

以及模不等式：

a≤ca

(b

c)≤(a

b)

c75§2分配格《定義》如對L中任意a，b，c有：

a≤ca

(b

c)＝(a

b)

c則稱<L,≤>為模格。例：76§2分配格《定理》如果格中交對并是分配的，那么并對交也是分配的，反之亦然。證明：已知a

(b

c)＝(a

b)

(a

c)

(a

b)

(a

c)=((a

b)

a)

((a

b)

c) =a

((a

b)

c) =a

((a

c)

(b

c)) =(a

(a

c))

(b

c) =a

(b

c)即：并對交也是分配的。77§2分配格《定理》分配格是模格。證明：由于a

(b

c)＝(a

b)

(a

c)(1)若a≤c，則a

c=c，代入上式得

a

(b

c)＝(a

b)

c(2)若a

(b

c)＝(a

b)

c，則

a≤a

(b

c)＝(a

b)

c≤c，即：a≤c

∴分配格是模格78§2分配格《定理》每個鏈均是分配格。證明：設<L,≤>是鏈。對任意a，b，cL(1)若a≤b或a≤c，則a

(b

c)＝a，

(a

b)

(a

c)＝a即：a

(b

c)＝(a

b)

(a

c)(2)若a≥b且a≥c，則

a

(b

c)＝b

c，

(a

b)

(a

c)＝b

c即：a

(b

c)＝(a

b)

(a

c)。得證。79§3有補格《定義》設<L,≤>是一個格，如果存在元素aL，對于任意的xL，都有：

a≤x

則稱a為格<L,≤>的全下界，記格的全下界為0。例：80§3有補格《定理》如果格<L,≤>有全上界（全下界），那么它是唯一的。證明：（反證法）設有兩個全上界a和b，則由定義

a≤b，且b≤a，由“≤”的反對稱性，a＝b。《定義》設<L,≤>是一個格，格中存在全上界和全下界，則稱該格為有界格。81§3有補格《定理》如果<L,≤>是有界格，全上界和全下界分別是1和0，則對任意元素aL，有：

a

1=1

a=1，a

1=1

a=a，

a

0=0

a=a，a

0=0

a=0。證明：因為1≤a

1， 又因(a

1)L且1是全上界，∴a

1≤1，

∴a

1=1。由交換律：1

a＝a

1=1。 因為a≤a，a≤1，∴a

a≤a

1，即：a≤a

1，又a

1≤a，∴a

1=a。仿此可得另兩式。82§3有補格《定義》設<L,≤>是一個有界格，對于L中的一個元素a，如果存在bL，使得a

b=1和a

b=0，則稱元素b是元素a的補元。討論定義：（1）∵

和

是可交換的，∴補元是相互的。

（2）

，即在有界格中，1和0互為補元；

（3）由定義可知L中一個元素的補元不一定是唯一的；例：83東南大學遠程教育離散數學第五十三講主講教師：仲新宇84§3有補格《定義》在一個有界格中，如果每個元素都至少有一個補元素，則稱此格為有補格。討論定義：（1）在有補格中，每一個元素一定存在補元（不一定是一個補元）；（2）有補格一定是有界格，而有界格不一定是有補格。請看下例：85§3有補格《定義》在一個有界格中，如果每個元素都至少有一個補元素，則稱此格為有補格。討論定義：（1）在有補格中，每一個元素一定存在補元（不一定是一個補元）；（2）有補格一定是有界格，而有界格不一定是有補格。請看下例：86§3有補格《定理》在有界分配格中，若有一個元素有補元，則必是唯一的。證明：87§4布爾代數《定義》一個有補分配格稱為布爾格?！抖x》一個格<L,≤>如果它既是有補格，又是分配格，則它為有補分配格。我們把有補分配格中任一元素a的唯一補元記為a。討論定義：(1)布爾格中，每個元素有唯一的補元。(2)我們可以定義L上的一個一元運算，稱為補運算，記為“-”。-88§4布爾代數《定義》由布爾格<L,≤>，可以誘導一個包括交，并和補運算的代數系統<L,

,

,->，稱此代數系統為布爾代數。例：設S是一個非空有限集，<(S),>是一個格，且是一個布爾格。由<(S),>所誘導的代數系統為

<(S),

,

,->是一個布爾代數。其中“

,

,-”分別是集合的交、并、補運算。89§4布爾代數《定理》對于布爾代數中任意兩個元素a,b，必定有90§4布爾代數證明：91§4布爾代數《定理》設<A,

,

,->是由有限布爾格<A,≤>所誘導的一個有限布爾代數，S是布爾格<A,≤>中的所有原子的集合，則<A,

,

,->和<(S),

,

,~>同構。討論定理：(1)當布爾代數<A,

,

,->的載體A的基數|A|是有限數時,則稱之為有限布爾代數。(2)設<A,

,

,->是一個布爾代數，a∈A,如果a蓋住0，則稱元素a是該布爾代數的一個原子。

例如：92東南大學遠程教育離散數學第五十四講主講教師：仲新宇93§4布爾代數例：<(S),

,

,~,

,S>，其中S={a,b,c}，在這個布爾代數中的元素分三種情況：（?。┙纾喝辖鏢，全下界

；（ⅱ）{a},,{c}單個元素集合的元素；（ⅲ）二，三個元素作為集合的元素，但它們均可用單個元素的集合的元素來表述：{a,b}={a}

,{a,c}={a}

{c},{b,c}=

{c},{a,b,c}={a}

{c}。

{a,c}{a,b,c}{a,b}{b,c}{a}{c}?94§4布爾代數(3)A中除0外的每個元素，都可以唯一地表示成原子的并。該定理可得以下兩個推論：a)<B,*,

,’,0,1>與<p(S),∪,∩,~,?,S>同構，|p(S)|=2|s|所以，|B|=2|s|

，故任一有限布爾代數載體的基數是2的冪。b)任一有限布爾代數和它的原子集合S構成的冪集集合代數<p(S),∪,∩,~,?,S>同構，但后者又與任一基數相同的冪集集合代數同構，故具有相同載體基數的有限布爾代數都同構。

95§4布爾代數格有界格有補格布爾代數分配格結合律吸收律交換律冪等律同一律零一律互補律分配律德·摩根律雙重否定律96§4布爾代數例：設A是一非空集合,

(A)是A的冪集,可以驗

證,<

(A),∪,∩,~,

,A>是個布爾代數,稱此為集合代數,其中運算為∪,∩,~,最小元

,最大元A。S是命題公式的全體,則<S,∨,∧,

,0,1>是一個布爾代數,稱之為命題代數。其中運算為∨,∧,

,最小元是恒假公式0,最大元是恒真公式1。97§4布爾代數因此，從邏輯觀點看，布爾代數是命題演算系統。從集合論觀點看，布爾代數是集合代數。從抽象代數的觀點看，布爾代數是一個代數系統。98第三篇小結通過本篇的學習應該達到以下基本要求：(1)給定集合與運算的解析表達式，寫出該運算的運算表。(2)給定集合和運算，判別該集合對運算是否封閉。(3)給定二元運算，說明運算是否滿足交換律、結合律、冪等律、分配律和吸收律。(4)給定集合S上的二元運算，求出該運算的幺元、零元、冪等元和所有可逆元素的逆元。(5)給定集合S和二元運算*，能判定<S,*>是否構成半群、獨異點和群。99第三篇小結(6)給定半群S和子集B，判定B是否為S的子半群；給定獨異點V和子集B，判定B是否為V的子獨異點，給定群G和子集H，判定H是否為G的子群。(7)求循環(huán)群的所有生成元。(8)給定代數系統V1=<S1,o>，V2=<S2，*>，其中“o”和”*“為二元運算，判定：S1

S2是否為V1到V2的同態(tài)映射。如果是，說明是否為單同態(tài)、滿同態(tài)和同構，并求出同態(tài)象(V1)。(9)判別格、分配格、有界格、有補格和布爾格。求有界格的全上界、全下界和給定元素的補元。100例題選講例1.設：S＝{a,b}，則S上可以定義多少個二元運算？其中有4個運算如下表所示，則有哪些滿足交換律，哪些滿足冪等律，哪些有幺元，哪些有零元？

1abaaabaa

2abaabbba

3abababaa

4abaabbab101例題選講例2.對以下定義的集合和運算判別它們能否構成代數系統？如能，請說明是構成哪一種代數系統？(1)，＋為普通加法；(2)，*為普通乘法；(3)，≤為小于等于關系；102例題選講東南大學遠程教育離散數學第五十五講主講教師：仲新宇第四篇 圖論圖論是近年來發(fā)展迅速而又應用廣泛的一門新興學科。它最早起源于一些數學游戲的難題研究，如1736年歐拉（L.Euler)所解決的哥尼斯堡七橋問題。以及在民間廣為流傳的一些游戲問題：例如迷宮問題、棋盤上馬的行走路線問題等等。這些古老的問題當時吸引了許多學者的注意，從而在這些問題研究的基礎上，又提出了著名的四色猜想和環(huán)游世界各國的問題。第四篇 圖論圖論不斷發(fā)展，它在解決運籌學，網絡理論，信息論，控制論，博奕論以及計算機科學等各個領域的問題時，顯示出越來越大的效果。對于這樣一門應用廣泛的學科，其包含的內容是豐富的，本篇我們只準備介紹基本的概念和定理，為今后有關學科及課程的學習和研究提供方便。第四篇 圖論

第七章 圖論§1圖的基本概念§2路與回路§3圖的矩陣表示§4歐拉圖和漢密爾頓圖§5平面圖§6樹與生成樹§1圖的基本概念1.基本名詞和定義《定義》一個圖G是一個三元組<V(G),E(G),ΦG>,其中V(G)為有限非空結點（或叫頂點）集合,E(G)是邊的集合，ΦG是從邊集E到結點偶對集合上的函數。討論定義：

(1).V(G)={V1，V2，…，Vn}為有限非空集合,Vi稱為結點,簡稱V是點集。

(2).E(G)={e1，…，em}為有限的邊集合,ei稱為邊，每個ei都有V中的結點對與之相對應,稱E為邊集。

即每條邊是連結V中的某兩個點的?！?圖的基本概念(3).若Ｇ中每一條邊e與有序偶對<vi,vj>或無序偶對(vi,vj)相關系，則可說邊e連接結點vi和vj(4).可用e＝<vi,vj>或e＝(vi,vj)，以結點來表示圖的邊，這樣可把圖簡化成：Ｇ＝<Ｖ，Ｅ>。例：有圖如下，試寫成定義表達式Ｇ＝〈Ｖ，Ｅ〉，其中Ｖ＝{v1,v2,v3,v4,v5}Ｅ＝{x1,x2,x3,x4,x5,x6}§1圖的基本概念例：對有向圖可表示為：Ｇ＝〈Ｖ、Ｅ〉，其中Ｖ＝｛a、b、c、d｝ Ｅ＝｛<a,b>,<b,a>,<b,d>,<d,a>,<d,d>,<c,c>｝下面定義一些專門名詞：(1)有向邊：在圖中對應有序偶對的邊（或者：在圖中帶有箭頭方向的邊或弧線）§1圖的基本概念(2)無向邊：在圖中對應無序偶對的邊（或：在圖中不帶箭頭的邊）(3)鄰接結點：由一條邊（有向或無向）連接起來的結點偶對

(4)（ｎ，ｅ）圖：具有ｎ個結點（頂點），ｅ條邊的圖(5)有向圖：在Ｇ中每一條邊均為有向邊(5)有向完全圖：在n個結點的有向圖G=<V,E>中，如果

E＝V×V，則稱G為有向完全圖。例：東南大學遠程教育離散數學第五十六講主講教師：仲新宇§1圖的基本概念對有向簡單完全圖講

：ｅ＝＝n(n-1)

（沒有自回路）

§1圖的基本概念(6)無向圖：每一條邊均為無向邊的圖(7)無向完全圖：每兩個結點之間均有連線的無向圖。n個結點的無向完全圖的邊數為：例：

§1圖的基本概念(8)混合圖：既有有向邊，又有無向邊的圖(9)互相鄰接的邊：連接于同一結點的二條（或若干條）邊例：§1圖的基本概念(10)閉路（自回路）：圖中起始且終止于同一結點的邊(閉路的箭頭方向是沒有意義的)例：(11)多重邊（平行邊）：二個結點之間方向相同的二條（多條）邊例：§1圖的基本概念《定義》：含有多重邊的圖稱為多重圖，非多重圖稱為線圖。簡單圖：無自回路的線圖稱為簡單圖。由定義可見，簡單圖是沒有自回路和多重邊的圖。例：§1圖的基本概念《定義》：有權圖（賦權圖）Ｇ是一個三元組〈Ｖ、Ｅ、ｇ〉或四元組〈Ｖ、Ｅ、ｆ、ｇ〉，其中Ｖ為結點集合，Ｅ為邊的集合，f是定義在Ｖ上的函數，g是定義在邊集合Ｅ上的函數。實際上，有權圖可以用一句話概括：每一條邊或結點均注上數字的圖（數字可以為整數、正實數）例：給出一個有權圖Ｇ＝〈Ｖ、Ｅ、ｆ、ｇ〉，其圖如下：其中Ｖ＝{v1,v2,v3}

Ｅ＝{e1,e2}§1圖的基本概念(12)孤立結點：不與任何結點相連接的結點(13)零圖：僅包含孤立結點的圖，又稱（ｎ，０）圖(14)平凡圖：只有一個結點的圖（1，0）圖《定義》：在有向圖中，對于任何結點v，以v為始點的邊的條數，稱為結點v的引出度數，記作；以v點為終點的邊的條數稱為v的引入度數，記作結點的v的引入度數和引出度數之和稱為v的度數，用deg（v）表示。由定義可見：度數deg（v）＝

對無向圖講：結點的度數等于和該結點關聯的邊的條數§1圖的基本概念例：(15)正則圖：所有結點均具有同樣度數的簡單無向圖例：§1圖的基本概念《定理》：每個圖中，結點度數的總和等于邊數的兩倍?！?圖的基本概念例：若圖Ｇ有n個頂點，（n+1）條邊，則Ｇ中至少有一個結點的度數≥３。證明：設Ｇ中有n個結點分別為v1,v2,…,vn，則由握手定理：

而結點的平均度數=∴結點中至少有一個頂點的度數≥３§1圖的基本概念《推論》：(1)在圖中，所有度數之和必為偶數；(2)在圖中，度數為奇數的結點必定有偶數個。§1圖的基本概念《定理》：在任何有向圖中，所有結點的入度之和等于所有結點的出度之和?！?圖的基本概念２．子圖和圖的同構：《定義》：設Ｇ＝<Ｖ，Ｅ>，Ｇ’＝<Ｖ’，Ｅ’>是二個圖若Ｖ’

Ｖ，Ｅ’

Ｅ,則稱Ｇ’是Ｇ的子圖；若Ｖ’

Ｖ或Ｅ’

Ｅ,則稱Ｇ’是Ｇ的真子圖；若Ｖ’＝Ｖ，Ｅ’

Ｅ,則稱Ｇ’是Ｇ的生成子圖(支撐子圖)。例：Ｇ圖如下：Ｇ的真子圖：支撐子圖：§1圖的基本概念說明：（1）Ｇ也是Ｇ的生成子圖；（2）Ｇ’＝〈Ｖ，

〉也是Ｇ的生成子圖。它們統稱為平凡子圖?！抖x》：設Ｇ＝〈Ｖ，Ｅ〉，Ｇ’＝〈Ｖ’，Ｅ’〉是Ｇ的子圖，若有另一個圖Ｇ’’＝〈Ｖ’’，Ｅ’’〉，且滿足關系Ｅ’’＝Ｅ－Ｅ’，Ｖ’’為E’’中邊的相關結點的集合，即（Ｖ’’

Ｖ），則稱：Ｇ’’為Ｇ’關于Ｇ的補圖（相對補圖）。例：§1圖的基本概念

ＧＧ’Ｇ’關于Ｇ的補圖Ｇ’’《定義》：給定一個圖Ｇ，由Ｇ中的所有結點和使Ｇ成為完全圖的邊所組成的圖，稱為Ｇ的補圖（絕對補圖），記為:§1圖的基本概念

Ｇ《定義》：設Ｇ＝〈Ｖ、Ｅ〉和Ｇ’＝〈Ｖ’，Ｅ’〉是兩個圖，若存在一雙射函數：ｇ：Ｖ→Ｖ＇，當且僅當e’＝{g(vi),g(vj)}是Ｇ’中的一條邊，才能使e＝{vi,vj}是Ｇ中的一條邊，則稱Ｇ’和Ｇ同構。§1圖的基本概念討論定義：（1）Ｇ’和Ｇ是互為同構的；（2）對無向圖講“一一對應”是指保持結點之間的鄰接關系；（3）對有向圖講“一一對應”不但