離散數(shù)學(xué)課件

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

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

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

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

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

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

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

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

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

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

例：河南省北接河北省。

nLb

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

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

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

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

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

§2命題函數(shù)與量詞討論定義：

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

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

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

“

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

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

xA(x)或(

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

·

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

·

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

·?

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

·?

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

解：

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

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

“

”為存在量詞符號，讀作“存在一個(gè)”，“對于一些”，“對于某些”，“至少存在一個(gè)”，“這里存在著這樣的”等等?！?/p>

”表達(dá)式的讀法：

·

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

·

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

·?

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

·?

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

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

xM(x)；（b）

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

x(R1(x)

R2(x))

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

xP(x)

P(a1)

…

P(an)

xQ(x)

Q(a1)

…

Q(an)

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

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

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

xA,

xA也都是謂詞公式；

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

例1：任何整數(shù)或是正的，或是負(fù)的。

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

x(I(x)(R1(x)

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

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

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

x(M(x)

D(x))，

M(s)

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

xP(x),

x(P(x)Q(x))

。

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

約束變元：在量詞的轄域內(nèi)，且與量詞下標(biāo)相同的變元。自由變元：當(dāng)且僅當(dāng)不受量詞的約束。例：

xP(x,y),

x(P(x)

y(P(x,y))。

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

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

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

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

（b）改名時(shí)所用的變元符號在量詞轄域內(nèi)未出現(xiàn)的。

§4變元的約束例：

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

xP(x)zR(x,z)

，但不能改成

xP(x)xR(x,x)

，

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

（a）若在謂詞公式中出現(xiàn)有自由變元，則該公式為命題函數(shù)；

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

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

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

§4變元的約束舉例：例1：“沒有不犯錯(cuò)的人。”

解：設(shè)F(x)為“x犯錯(cuò)誤”，M(x)為“x是人”（特性謂詞）?？砂汛嗣}寫成：?(

x(M(x)

F(x)))

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

設(shè)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)對公式中出現(xiàn)該自由變元的每一處進(jìn)行代入，

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

例：“所有的人必死。”令D(x)，x是要死的。下面給出不同的個(gè)體域來討論：(ⅰ)個(gè)體域?yàn)椋簕人類}，則可寫成

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

命題可寫成

x(M(x)

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

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

xQ(x)TFF

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

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

對于存在量詞，其特性謂詞以與的形式加入?！?變元的約束例：設(shè)個(gè)體域?yàn)?{白虎（白貓），黃咪（黃貓），，}，同時(shí)令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.量詞對變元的約束，往往與量詞的次序有關(guān)。例：

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

§5謂詞演算的

等價(jià)式與蘊(yùn)含式

基本定義

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

AE

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

§5謂詞演算的

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

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

等價(jià)式與蘊(yùn)含式

命題邏輯謂詞邏輯

??Ｐ

Ｐ??Ｐ(x)

Ｐ(x)

Ｐ∨Ｐ

ＰＰ(x)∨Ｐ(x)

Ｐ(x)

....Ｐ→Ｑ

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

?Ｑ(x)→?Ｐ(x)

Ｐ

Ｐ∨ＱＰ(x)

Ｐ(x)∨Ｑ(x)

ＰΛＱ

ＰＰ(x)ΛＱ(x)

Ｐ(x)......

§5謂詞演算的

等價(jià)式與蘊(yùn)含式2.含有量詞的等價(jià)式和永真蘊(yùn)含式設(shè)個(gè)體域?yàn)椋篠={a1,a2,…an}，我們有：

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

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

§5謂詞演算的

等價(jià)式與蘊(yùn)含式例：設(shè)個(gè)體域?yàn)椋篘={0,1,2…}，

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

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

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

（1）量詞轉(zhuǎn)換律：

E25(Q3)?

xP(x)

x?P(x)E26(Q4)

?

xP(x)

x?P(x)下面證明：設(shè)個(gè)體域?yàn)椋篠={a1,a2,…an}§5謂詞演算的

等價(jià)式與蘊(yùn)含式

?

xP(x)

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

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

x?P(x)

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

例：否定下列命題：

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

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

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

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

?

x(N(x)E(x))

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

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

x(N(x)

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

等價(jià)式與蘊(yùn)含式結(jié)論：對于非量化命題的否定只需將動詞否定，而對于量化命題的否定不但對動詞進(jìn)行否定而且對量詞同時(shí)進(jìn)行否定，其方法是：

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

x

，

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

x

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

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謂詞演算的

等價(jià)式與蘊(yùn)含式證明E27(Q6)，設(shè)個(gè)體域?yàn)椋篠={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)，設(shè)個(gè)體域?yàn)椋篠={a1,a2,…an}

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

(?A(a1)

B)…(?A(an)

B)§5謂詞演算的

等價(jià)式與蘊(yùn)含式

(?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謂詞演算的

等價(jià)式與蘊(yùn)含式證明E24(Q10)和I19(Q19)

，設(shè)個(gè)體域?yàn)椋篠={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謂詞演算的

等價(jià)式與蘊(yùn)含式

(?A(a1)

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

B(an))

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

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

Q1

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

xP(x)

xP(x)

xPP

xPP

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

等價(jià)式與蘊(yùn)含式（5）含有多個(gè)量詞的永真式：

（?。┝吭~出現(xiàn)的次序直接關(guān)系到命題的含義：

“

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

下面列出對應(yīng)的表達(dá)式可以看出其不同處：

設(shè)x的個(gè)體域?yàn)椋簕a1,a2,…an}，

y的個(gè)體域?yàn)椋簕b1,b2,…bn}，

則：

xyP(x,y)

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

§5謂詞演算的

等價(jià)式與蘊(yùn)含式

(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的個(gè)體域{鞋子}，P(x,y):Ｘ和Ｙ配成一雙鞋子。

xyP(x,y)

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

等價(jià)式與蘊(yùn)含式（ⅱ）在含有多個(gè)量詞的謂詞公式中,

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

例：x,y的個(gè)體域?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謂詞演算的

等價(jià)式與蘊(yùn)含式同樣：

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

?

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

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

（ⅳ）兩個(gè)量詞

,所組成的謂詞公式的等價(jià)式和永真蘊(yùn)含式（8個(gè)）

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謂詞演算的

等價(jià)式與蘊(yùn)含式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）謂詞公式的對偶式《定義》

在一個(gè)謂詞公式A中（其中不出現(xiàn)

,詞）把公式A中

,,F,T,,,

變?yōu)楣紸*中

,,T,F,,,則稱A*是A的對偶式。《定理》

若謂詞公式A

B，則A*

B*

；若謂詞公式A

B，則B*

A*

（這里A,B有同樣的個(gè)體域）。§5謂詞演算的

等價(jià)式與蘊(yùn)含式例：

I17(Q13)

xA(x)

xB(x)

x(A(x)

B(x))I18(Q12)

xA(x)

xB(x)

x(A(x)

B(x))

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

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

《定理》

任何一個(gè)謂詞公式均和一個(gè)前束范式等價(jià)。

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

②利用約束變元的改名規(guī)則，③利用量詞轄域的擴(kuò)張收縮律,把量詞移到全式的最前面，這樣一定可得到等價(jià)的前束范式。§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.含有量詞的特殊永真式《定義》設(shè)A(x)是一個(gè)謂詞公式，x是其中的自由變元，若把y代入到A(x)里而不會產(chǎn)生變元的新的約束出現(xiàn)，則稱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束變元了，產(chǎn)生了新的約束出現(xiàn)。如有必要代入y，則應(yīng)先將式中的約束變元y改名。

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

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

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

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

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

xA(x)

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

A(x)

xA(x)

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

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

xA(x)A(c)

例：x的個(gè)體域?yàn)镮={整數(shù)}，P(x):x是偶數(shù)，Q(x):x是奇數(shù)。

xP(x)

xQ(x)T但

P(c)

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

A(c)

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

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

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

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

xP(x)P(y),

xQ(x)Q(y),

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

xP(x)P(y)

xQ(x)Q(y)

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

§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) 假設(shè)前提

(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例：下列結(jié)論能否從前提中推出：

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

(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ī)則時(shí),要注意嚴(yán)格按照它們的規(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謂詞演算的推理理論例：

二個(gè)量詞的推理比較復(fù)雜：

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

三個(gè)量詞的推理過程更為復(fù)雜

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

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

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

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

x(L(x)G(x))或x(L(x)G(x))例題選講(3)設(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í)。

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代數(shù)系統(tǒng)

第六章 格和布爾代數(shù)

§1格的概念

§2分配格

§3有補(bǔ)格

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

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

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

——稱為元素a和b的保交運(yùn)算，

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

和

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

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

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

,

>為由格所誘導(dǎo)的代數(shù)系統(tǒng)。68§1格的概念3.格的主要性質(zhì)：(1)格的對偶原理設(shè)<L,≤>是格，“≤”的逆關(guān)系“≥”與L組成的偏序集<L,≥>也是格。兩者互為對偶。前者的GLB，LUB恰好是后者的LUB，GLB。如有關(guān)于<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)（交換律）交和并運(yùn)算是可交換的。(5)（結(jié)合律）交和并運(yùn)算是可結(jié)合的。72§1格的概念(6)（冪等律）對L中每一個(gè)a，有a

a=a，a

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

(a

b)=a

a

(a

b)=a。73§2分配格

對格所定義的代數(shù)系統(tǒng)<L,

,

>，其運(yùn)算

和

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

,

>是由<L,≤>所誘導(dǎo)的代數(shù)系統(tǒng)。如果對任意的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分配格《定理》每個(gè)鏈均是分配格。證明：設(shè)<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有補(bǔ)格《定義》設(shè)<L,≤>是一個(gè)格，如果存在元素aL，對于任意的xL，都有：

a≤x

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

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

a

1=1

a=1，a

1=1

a=a，

a

0=0

a=a，a

0=0

a=0。證明：因?yàn)?≤a

1， 又因(a

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

1≤1，

∴a

1=1。由交換律：1

a＝a

1=1。 因?yàn)閍≤a，a≤1，∴a

a≤a

1，即：a≤a

1，又a

1≤a，∴a

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

b=1和a

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

和

是可交換的，∴補(bǔ)元是相互的。

（2）

，即在有界格中，1和0互為補(bǔ)元；

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

,

,->，稱此代數(shù)系統(tǒng)為布爾代數(shù)。例：設(shè)S是一個(gè)非空有限集，<(S),>是一個(gè)格，且是一個(gè)布爾格。由<(S),>所誘導(dǎo)的代數(shù)系統(tǒng)為

<(S),

,

,->是一個(gè)布爾代數(shù)。其中“

,

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

,

,->是由有限布爾格<A,≤>所誘導(dǎo)的一個(gè)有限布爾代數(shù)，S是布爾格<A,≤>中的所有原子的集合，則<A,

,

,->和<(S),

,

,~>同構(gòu)。討論定理：(1)當(dāng)布爾代數(shù)<A,

,

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

,

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

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

,

,~,

,S>，其中S={a,b,c}，在這個(gè)布爾代數(shù)中的元素分三種情況：（ⅰ）界：全上界S，全下界

；（ⅱ）{a},,{c}單個(gè)元素集合的元素；（ⅲ）二，三個(gè)元素作為集合的元素，但它們均可用單個(gè)元素的集合的元素來表述：{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布爾代數(shù)(3)A中除0外的每個(gè)元素，都可以唯一地表示成原子的并。該定理可得以下兩個(gè)推論：a)<B,*,

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

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

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

(A)是A的冪集,可以驗(yàn)

證,<

(A),∪,∩,~,

,A>是個(gè)布爾代數(shù),稱此為集合代數(shù),其中運(yùn)算為∪,∩,~,最小元

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

,0,1>是一個(gè)布爾代數(shù),稱之為命題代數(shù)。其中運(yùn)算為∨,∧,

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

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

1abaaabaa

2abaabbba

3abababaa

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

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

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

(2).E(G)={e1，…，em}為有限的邊集合,ei稱為邊，每個(gè)ei都有V中的結(jié)點(diǎn)對與之相對應(yīng),稱E為邊集。

即每條邊是連結(jié)V中的某兩個(gè)點(diǎn)的。§1圖的基本概念(3).若Ｇ中每一條邊e與有序偶對<vi,vj>或無序偶對(vi,vj)相關(guān)系，則可說邊e連接結(jié)點(diǎn)vi和vj(4).可用e＝<vi,vj>或e＝(vi,vj)，以結(jié)點(diǎn)來表示圖的邊，這樣可把圖簡化成：Ｇ＝<Ｖ，Ｅ>。例：有圖如下，試寫成定義表達(dá)式Ｇ＝〈Ｖ，Ｅ〉，其中Ｖ＝{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)有向邊：在圖中對應(yīng)有序偶對的邊（或者：在圖中帶有箭頭方向的邊或弧線）§1圖的基本概念(2)無向邊：在圖中對應(yīng)無序偶對的邊（或：在圖中不帶箭頭的邊）(3)鄰接結(jié)點(diǎn)：由一條邊（有向或無向）連接起來的結(jié)點(diǎn)偶對

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

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

：ｅ＝＝n(n-1)

（沒有自回路）

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

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

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

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

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

Ｖ，Ｅ’

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

Ｖ或Ｅ’

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

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

〉也是Ｇ的生成子圖。它們統(tǒng)稱為平凡子圖?！抖x》：設(shè)Ｇ＝〈Ｖ，Ｅ〉，Ｇ’＝〈Ｖ’，Ｅ’〉是Ｇ的子圖，若有另一個(gè)圖Ｇ’’＝〈Ｖ’’，Ｅ’’〉，且滿足關(guān)系Ｅ’’＝Ｅ－Ｅ’，Ｖ’’為E’’中邊的相關(guān)結(jié)點(diǎn)的集合，即（Ｖ’’

Ｖ），則稱：Ｇ’’為Ｇ’關(guān)于Ｇ的補(bǔ)圖（相對補(bǔ)圖）。例：§1圖的基本概念

ＧＧ’Ｇ’關(guān)于Ｇ的補(bǔ)圖Ｇ’’《定義》：給定一個(gè)圖Ｇ，由Ｇ中的所有結(jié)點(diǎn)和使Ｇ成為完全圖的邊所組成的圖，稱為Ｇ的補(bǔ)圖（絕對補(bǔ)圖），記為:§1圖的基本概念

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