1、離散數(shù)學(xué)例4 設(shè) p：天冷，q：小王穿羽絨服，將下列命題符號化(1) 只要天冷，小王就穿羽絨服.(2) 因?yàn)樘炖?，所以小王穿羽絨服.(3) 若小王不穿羽絨服，則天不冷.(4) 只有天冷，小王才穿羽絨服.(5) 除非天冷，小王才穿羽絨服.(6) 除非小王穿羽絨服，否則天不冷.(7) 如果天不冷，則小王不穿羽絨服.(8) 小王穿羽絨服僅當(dāng)天冷的時候.2蘊(yùn)涵聯(lián)結(jié)詞的實(shí)例pq注意：注意： pq 與與 qp 等值（真值相同）等值（真值相同）pqpqqpqppqqpqp例6 寫出下列公式的真值表, 并求它們的成真賦值和成假 賦值: (1) (pq) r (2) (qp) qp (3) (pq) q3真值表

2、真值表4(1) A = (p q) r成真賦值成真賦值:000,001,010,100,110; 成假賦值成假賦值:011,101,111 p q rp q r (p q)r0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 00111111 10101010 11101010 真值表真值表15(2) B(qp) qp成真賦成真賦值值:00,01,10,11; 無成假賦值無成假賦值p q qp(qp) q(qp) qp0 00 11 01 1101100011111真值表真值表26(3) C ( p q) q的真值表的真值表成假賦值成假賦值:00,01,10,11

3、; 無成真賦值無成真賦值p q p p q ( p q) ( p q) q0 00 11 01 11100110100100000真值表真值表3主要內(nèi)容l命題、真值、簡單命題與復(fù)合命題、命題符號化l聯(lián)結(jié)詞, , , , 及復(fù)合命題符號化l命題公式及層次l公式的類型l真值表及應(yīng)用基本要求l深刻理解各聯(lián)結(jié)詞的邏輯關(guān)系, 熟練地將命題符號化l會求復(fù)合命題的真值l深刻理解合式公式及重言式、矛盾式、可滿足式等概念l熟練地求公式的真值表，并用它求公式的成真賦值與成假賦值及判斷公式類型7第一章 習(xí)題課基本概念(1) 文字命題變項(xiàng)及其否定的總稱(2) 簡單析取式 p, q, pq (3) 簡單合取式 p, q

4、, pq, (4) 析取范式 p, pq, pq, (pq) (qr)(5) 合取范式 p, pq, pq, (pq)(pqr)(6) 范式析取范式與合取范式的總稱范式不唯一，主唯一主析取范式由極小項(xiàng)(真)構(gòu)成的析取范式主合取范式由極大項(xiàng)(假)構(gòu)成的合取范式82.2 析取范式與合取范式 例如，n=3, 命題變項(xiàng)為 p, q, r 時， (pqr)(pqr) m1m3 主析取范式 (pqr)(pqr) M1M7主合取范式定理2.5 (主范式的存在惟一定理) 任何命題公式都存在與之等值的主析取 范式和主合取范式, 并且是惟一的例6 (1) 求公式 A=(pq)r的主析取范式和主合取范式 解 (pq

5、)r (pq)r （析取范式） (pq) (pq)(rr) (pqr)(pqr) m6m7 r (pp)(qq)r (pqr)(pqr)(pqr)(pqr) m1m3m5m7 , 代入并排序，得 (pq)r m1m3m5 m6m7 （主析取范式）10實(shí)例 (pq)r (pr)(qr) （合取范式） pr p(qq)r (pqr)(pqr) M0M2 qr (pp)qr (pqr)(pqr) M0M4 , 代入 并排序，得 (pq)r M0M2M4 （主合取范式）11實(shí)例1.求公式的成真成假賦值 設(shè)公式A含n個命題變項(xiàng), A的主析取范式有s個極小項(xiàng), 則A 有s個成真賦值, 它們是極小項(xiàng)下標(biāo)的二

6、進(jìn)制表示, 其余2n-s 個賦值都是成假賦值 例如 (pq)r m1m3m5 m6m7成真賦值為 001, 011, 101, 110, 111，成假賦值為 000, 010, 100. 類似地，由主合取范式也立即求出成假賦值和成真賦值. 12主范式的應(yīng)用13主范式的應(yīng)用2. 判斷公式的類型 設(shè)A含n個命題變項(xiàng). A為重言式 A的主析取范式含全部2n個極小項(xiàng) A的主合取范式不含任何極大項(xiàng), 記為1.A為矛盾式 A的主合析取范式含全部2n個極大項(xiàng) A的主析取范式不含任何極小項(xiàng), 記為0.A為非重言式的可滿足式 A的主析取范式中至少含一個、但不是全部極小項(xiàng) A的主合取范式中至少含一個、但不是全部極

7、大項(xiàng).例7 用主析取范式判斷公式的類型:(1)A (pq)q (2) B p(pq) (3) C (pq)r解 (1) A ( pq)q ( pq)q 0 矛盾式(2) B p(pq) 1 m0m1m2m3 重言式(3) C (pq)r (pq)r (pqr)(pqr)(pqr)(pqr)(pqr)(pqr) m0m1m3 m5m7 非重言式的可滿足式14主范式的應(yīng)用3. 判斷兩個公式是否等值例8 用主析取范式判以下每一組公式是否等值 p(qr) 與 (pq)r p(qr) 與 (pq)r解 p(qr) = m0m1m2m3 m4m5 m7 (pq)r = m0m1m2m3 m4m5 m7 (

8、pq)r = m1m3 m4m5 m7顯見，中的兩公式等值，而的不等值.15主范式的應(yīng)用4. 解實(shí)際問題例9 某單位要從A,B,C三人中選派若干人出國考察, 需滿足下 述條件: (1) 若A去, 則C必須去; (2) 若B去, 則C不能去; (3) A和B必須去一人且只能去一人. 問有幾種可能的選派方案?解 記 p:派A去, q:派B去, r:派C去(1) pr, (2) qr, (3) (pq)(pq)求下式的成真賦值 A=(pr)(qr)(pq)(pq)16主范式的應(yīng)用求A的主析取范式 A=(pr)(qr)(pq)(pq) (pr)(qr)(pq)(pq) (pq)(pr)(rq)(rr)

9、 (pq)(pq) (pq)(pq)(pr)(pq) (rq)(pq)(pq)(pq) (pr)(pq)(rq)(pq) (pqr)(pqr)成真賦值:101,010結(jié)論: 方案1 派A與C去, 方案2 派B去17主范式的應(yīng)用由主析取范式確定主合取范式例10 設(shè)A有3個命題變項(xiàng), 且已知A= m1m3m7, 求A的主合取范式.解 A的成真賦值是1,3,7的二進(jìn)制表示, 成假賦值是在主析取范式中沒有出現(xiàn)的極小項(xiàng)的下角標(biāo)0,2,4,5,6的二進(jìn)制表示, 它們恰好是A的主合取范式的極大項(xiàng)的下角標(biāo), 故 A M0M2M4M5M618用成真賦值和成假賦值確定主范式由主合取范式確定主析取范式由主合取范式確

10、定主析取范式用真值表確定主范式用真值表確定主范式 1. A (AB) 附加律 2. (AB) A 化簡律3. (AB)A B 假言推理4. (AB)B A 拒取式 5. (AB)B A 析取三段論6. (AB)(BC) (AC) 假言三段論7. (AB)(BC) (AC) 等價三段論8. (AB)(CD)(AC) (BD) 構(gòu)造性二難 (AB)(AB) B 構(gòu)造性二難(特殊形式)9. (AB)(CD)( BD) (AC) 破壞性二難每個等值式可產(chǎn)生兩個推理定律如, 由AA可產(chǎn)生 AA 和 AA推理定律-重言蘊(yùn)涵式20例例1 用用0元謂詞將命題符號化元謂詞將命題符號化 (1) 墨西哥位于南美洲墨

11、西哥位于南美洲 (2) 是無理數(shù)僅當(dāng)是無理數(shù)僅當(dāng) 是有理數(shù)是有理數(shù) (3) 如果如果23，則，則33，q：3y，G(x, y)：xy x(F(x)y(G(y)L(x,y)或者或者 x y(F(x) G(y)L(x,y) (2) 令令F(x)：x是無理數(shù)，是無理數(shù)，G(y)：y是有理數(shù)，是有理數(shù)，L(x,y)：xy x(F(x)y(G(y) L(x,y)或者或者 x y(F(x) G(y) L(x,y)例4 在一階邏輯中將下面命題符號化 (1) 沒有不呼吸的人 (2) 不是所有的人都喜歡吃糖23實(shí)例4解解 (1) F(x): x是人是人, G(x): x呼吸呼吸x(F(x)G(x) x(F(x)

12、G(x)(2) F(x): x是人是人, G(x): x喜歡吃糖喜歡吃糖 x(F(x)G(x)x(F(x)G(x)例5 設(shè)個體域?yàn)閷?shí)數(shù)域, 將下面命題符號化 (1) 對每一個數(shù)x都存在一個數(shù)y使得xy (2) 存在一個數(shù)x使得對每一個數(shù)y都有xy24實(shí)例5解解 L(x,y):xy(1) x yL(x,y)注意注意: 與與 不能隨意交換不能隨意交換顯然顯然(1)是真命題是真命題, (2)是假命題是假命題(2) x yL(x,y) (4) 沒有不愛吃糖的人25練習(xí)2 (5) 任何兩個不同的人都不一樣高任何兩個不同的人都不一樣高 (6) 不是所有的汽車都比所有的火車快不是所有的汽車都比所有的火車快設(shè)

13、設(shè)F(x): x是人，是人，G(x): x愛吃糖愛吃糖x(F(x)G(x) 或或 x(F(x)G(x)設(shè)設(shè)F(x):x是人是人, H(x,y), x與與y相同相同, L(x,y): x與與y一樣高一樣高 x(F(x)y(F(y)H(x,y)L(x,y) 或或 x y(F(x) F(y)H(x,y)L(x,y)設(shè)設(shè)F(x):x是汽車是汽車, G(y):y是火車是火車, H(x,y):x比比y快快 x y(F(x) G(y)H(x,y) 或或 x y(F(x) G(y)H(x,y)第二組 (1) 消去量詞等值式 設(shè)D =a1, a2, , an xA(x) A(a1)A(a2)A(an) xA(x

14、) A(a1)A(a2)A(an)265.1 一階邏輯等值式與置換規(guī)則例3 設(shè)個體域D=a,b,c, 消去下述公式中的量詞: (1) xy(F(x)G(y)27實(shí)例解法一解法一 x y(F(x)G(y) ( y(F(a)G(y) ( y(F(b)G(y) ( y(F(c)G(y) (F(a)G(a) (F(a)G(b) (F(a)G(c) (F(b)G(a) (F(b)G(b) (F(b)G(c) (F(c)G(a) (F(c)G(b) (F(c)G(c) 解法二解法二 x y(F(x)G(y) x(F(x)yG(y) 轄域縮小等值式轄域縮小等值式 x(F(x)G(a) G(b) G(c) (

15、F(a)G(a) G(b) G(c) (F(b)G(a) G(b) G(c) (F(c)G(a) G(b) G(c)28實(shí)例(2) x yF(x,y) x yF(x,y) x(F(x,a) F(x,b) F(x,c) (F(a,a) F(a,b) F(a,c) (F(b,a) F(b,b) F(b,c) (F(c,a) F(c,b) F(c,c)設(shè)個體域D=a,b,c, 消去下述公式中的量詞29求前束范式的實(shí)例(3) xF(x)y(G(x,y)H(y)或或 xF(x)y(G(z,y)H(y) 代替規(guī)則代替規(guī)則 x y(F(x)(G(z,y)H(y) 解解 xF(x)y(G(x,y)H(y) z

16、F(z)y(G(x,y)H(y) 換名規(guī)則換名規(guī)則 z y(F(z)(G(x,y)H(y) 轄域收縮擴(kuò)張轄域收縮擴(kuò)張規(guī)則（這個地方注意是規(guī)則（這個地方注意是 z ，要與后面的相同要與后面的相同）2. 定義定義6.5 冪集冪集：P(A)= x | x A 實(shí)例：實(shí)例：P()=, P()=, 計(jì)數(shù)：如果計(jì)數(shù)：如果 |A|=n，則，則 |P(A)|=2n.冪集里面的元素都是集合！切記！31文氏圖集合運(yùn)算的表示集合運(yùn)算的表示ABABABABABA BA BABA BA1. 集合的廣義并與廣義交 定義6.10 廣義并 A = x | z ( zA xz ) 廣義交 A= x | z ( zA xz )

17、實(shí)例 1, 1,2, 1,2,3=1,2,3 1, 1,2, 1,2,3=1 a=a， a=a a=a， a=a運(yùn)算一次減少一層括號32廣義運(yùn)算2. 廣義運(yùn)算的性質(zhì) (1) =，無意義 (2) 單元集x的廣義并和廣義交都等于x (3) 廣義運(yùn)算減少集合的層次（括弧減少一層） (4) 廣義運(yùn)算的計(jì)算：一般情況下可以轉(zhuǎn)變成初級運(yùn)算 A1, A2, , An=A1A2An A1, A2, , An=A1A2An 例例1 A=a,a,b，計(jì)算，計(jì)算A (AA). 解：解： A (AA) = a,b ( a,ba) = (a b) (a b) a) = (a b) (b a) = b33關(guān)于廣義運(yùn)算的說

18、明 1判斷下列命題是否為真 (1) 集合集合 (2) 是集合，不能用這個符號 (3) (4) 元素集合 (5) a, b a, b, c, a, b, c (6) a, b a, b, c, a, b (7) a, b a, b, a, b (8) a, b a, b, a,b a,b有兩層，不適合34練習(xí)1解解 (1)、(3)、(4)、(5)、(6)、(7)為真，其余為假為真，其余為假.定義7.2 設(shè)A,B為集合，A與B的笛卡兒積記作AB，且 AB = | xAyB.35笛卡兒積例例1 A=1,2,3, B=a,b,c A B =, B A =, A=, B= P(A) A = , /這里這

19、里 尖括號尖括號里面的是里面的是屬于屬于集合的元素集合的元素 所以與空集相乘為空集所以與空集相乘為空集 P(A) B = 證明 A(BC) = (AB)(AC)36性質(zhì)證明證證 任取任取 A(BC) xAyBC xA(yByC) (xAyB)(xAyC) ABAC (AB)(AC)所以有所以有A(BC) = (AB)(AC).例4 A=1,2,3,4, R=, R的關(guān)系矩陣MR和關(guān)系圖GR如下：37實(shí)例 0010000011000011RM例7 設(shè)R=, 則 R1 = , R = R2,3 = , R1 = 2,3 R = R3 = 2 38實(shí)例定理7.2 設(shè)F, G, H是任意的關(guān)系, 則(

20、1) (FG)H = F(GH)(2) (FG)1 = G1F139關(guān)系運(yùn)算的性質(zhì)證證 (1) 任取任取, (F G) H t (F GH) t ( s (FG)H) t s (FGH) s (F t (GH) s (FG H) F (G H) 所以所以 (F G) H = F (G H)例例 8 設(shè)設(shè)A = a,b,c,d, R = , 求求R的各次冪的各次冪, 分別用矩陣和關(guān)系圖表示分別用矩陣和關(guān)系圖表示. 0000000010100101000010000101001000001000010100102M40 0000100001010010M解解 R 與與 R2的關(guān)系矩陣分別是：的關(guān)系

21、矩陣分別是：冪的求法冪的求法R3和R4的矩陣是：因此M4=M2, 即R4=R2. 因此可以得到 R2=R4=R6=， R3=R5=R7=R0的關(guān)系矩陣是 41冪的求法 0000000010100101,000000000101101043MM 10000100001000010MR0, R1, R2, R3,的關(guān)系圖如下圖所示. 42關(guān)系圖R0R1R2=R4=R3=R5=例9 設(shè)A=a,b,c,d, R=, R和r(R), s(R), t(R)的關(guān)系圖如下圖所示. 43實(shí)例Rr(R)s(R)t(R)等價類 定義7.16 設(shè)R為非空集合A上的等價關(guān)系, xA，令 xR = y | yAxRy稱x

22、R 為x關(guān)于R的等價類, 簡稱為x的等價類, 簡記為x或 x44 等價類的性質(zhì)設(shè)R是非空集合A上的等價關(guān)系, 則 (1) xA, x是A的非空子集 (2) x,yA, 如果 xRy, 則 x = y (3) x,yA, 如果 x y, 則 x與y不交 (4) x | xA=A定義7.17 設(shè) R 為非空集合A上的等價關(guān)系, 以 R 的所有等價類作為元素的集合稱為A關(guān)于R的商集, 記做A/R, A/R = xR | xA實(shí)例 設(shè) A=1,2,8，A關(guān)于模3等價關(guān)系R的商集為 A/R = 1,4,7, 2,5,8, 3,6A關(guān)于恒等關(guān)系和全域關(guān)系的商集為： A/IA = 1, 2, , 8， A/

23、EA = 1,2,845商集與劃分定義定義7.18 設(shè)設(shè)A為非空集合為非空集合, 若若A的子集族的子集族( P(A)滿足滿足:(1) (2) x y(x,y xyxy=)(3) = A則稱則稱是是A的一個的一個劃分劃分, 稱稱中的元素為中的元素為A的的劃分塊劃分塊. 例10 設(shè) A a, b, c, d , 給定 1, 2, 3, 4, 5, 6如下： 1= a, b, c , d 2= a, b, c , d 3= a , a, b, c, d 4= a, b, c 5=, a, b , c, d 6= a, a , b, c, d 則 1和 2是A的劃分, 其他都不是A的劃分. 46劃分實(shí)

24、例47例例11 給出給出 A1,2,3上所有的等價關(guān)系上所有的等價關(guān)系實(shí)例實(shí)例1 123 31 1 123 351 123 321 123 341 123 331對應(yīng)對應(yīng) EA, 5 對應(yīng)對應(yīng) IA, 2, 3 和和 4分別對應(yīng)分別對應(yīng) R2, R3和和 R4. R2=,IA R3=,IA R4=,IA解解 先做出先做出A的劃分的劃分, 從左到右分別記作從左到右分別記作 1, 2, 3, 4, 5.2設(shè)A=1,2,3,4，在AA上定義二元關(guān)系R： ,R x+y = u+v，求R導(dǎo)出的劃分. 48練習(xí)2 A A=, , , , , , , , , , , , , , 根據(jù)根據(jù) 中的中的 x+y

25、= 2, 3, 4, 5, 6, 7, 8 將將A劃分成等價類：劃分成等價類： A/R=, , , , , , , , , , , , , , 1. 證明證明R在在A上自反上自反 任取任取x, x A . R 前提前提 推理過程推理過程 結(jié)論結(jié)論2. 證明證明R在在A上對稱上對稱 任取任取， R . R 前提前提 推理過程推理過程 結(jié)論結(jié)論49關(guān)系性質(zhì)的證明方法3. 證明R在A上反對稱 任取， RR . x = y 前提 推理過程 結(jié)論4. 證明R在A上傳遞 任取,， RR . R 前提 推理過程 結(jié)論50關(guān)系性質(zhì)的證明方法例1 設(shè)A=1,2,3, B=a,b, 求BA.51實(shí)例解解BA= f

26、0, f1, , f7, 其中其中 f0 = , f1 = , f2 = , f3 = , f4 = , f5 = , f6 = , f7 = ,例例2 判斷下面函數(shù)是否為單射判斷下面函數(shù)是否為單射, 滿射滿射, 雙射的雙射的, 為什么為什么?(1) f:RR, f(x) = x2+2x 1(2) f:Z+R, f(x) = lnx, Z+為正整數(shù)集為正整數(shù)集(3) f:RZ, f(x) = x (4) f:RR, f(x)=2x+1(5) f:R+R+, f(x)=(x2+1)/x, 其中其中R+為正實(shí)數(shù)集為正實(shí)數(shù)集. 解(1) f:RR, f(x)=x2+2x1 在x=1取得極大值0. 既

27、不是單射也不是滿射的(2) f:Z+R, f(x)=lnx 是單調(diào)上升的, 是單射的. 但不滿射, ranf=ln1, ln2, .(3) f:RZ, f(x)= x 是滿射的, 但不是單射的, 例如f(1.5)=f(1.2)=1(4) f:RR, f(x)=2x+1 是滿射、單射、雙射的, 因?yàn)樗菃握{(diào)函數(shù)并且ranf=R(5) f:R+R+, f(x)=(x2+1)/x 有極小值 f(1)=2. 該函數(shù)既不是單射的也不是滿射的例3 對于給定的集合A和B構(gòu)造雙射函數(shù) f:AB(1) A=P(1,2,3), B=0,11,2,3(2) A=0,1, B=1/4,1/2(3) A=Z, B=N(

28、4) , B=1,153實(shí)例23,2 A(1) A=,1,2,3,1,2,1,3,2,3,1,2,3. B=f0, f1, , f7, 其中 f0=, f1=, f2=, f3=,f4=, f5=,f6=, f7=,. 令 f:AB, f()=f0, f(1)=f1, f(2)=f2, f(3)=f3, f(1,2)=f4, f(1,3)=f5, f(2,3)=f6, f(1,2,3)=f754解答155(2) 令令 f:0,11/4,1/2, f(x)=(x+1)/4 01202)(,NZxxxxff：(4) 令令 f: :/2,3/2 1,1 f(x) = sinx 解答解答2(3) 將將

29、Z中元素以下列順序排列并與中元素以下列順序排列并與N中元素對應(yīng)：中元素對應(yīng)：Z： 0 11 2 2 3 3 N： 0 1 2 3 4 5 6 這種對應(yīng)所表示的函數(shù)是：這種對應(yīng)所表示的函數(shù)是：設(shè)R是A上的等價關(guān)系, 令 g:AA/R g(a)=a, aA稱 g 是從 A 到商集 A/R 的自然映射 不同的等價關(guān)系確定不同的自然映射, 恒等關(guān)系確定的自然映射是雙射, 其他自然映射一般來說只是滿射. 例如 A=1,2,3, R=,IA g: AA/R, g(1)=g(2)=1,2, g(3)=3解 (1) 由T=B, A, S, E, L知 cardT=5(2) 由B=, 可知 cardB=0.(3

30、) 由|A|=4 可知 cardC=cardP(A)=|P(A)|=24=16.57實(shí)例例例9 求下列集合的基數(shù)求下列集合的基數(shù)(1) T=x | x是單詞是單詞“BASEBALL”中的字母中的字母(2) B=x | xRx2=92x=8(3) C=P(A), A=1, 3, 7, 11基數(shù)就是不重復(fù)的元素的個數(shù)基數(shù)就是不重復(fù)的元素的個數(shù)1. 證明 f:AB是滿射的方法: 任取 yB, 找到 x (即給出x的表示)或者證明存在xA，使得f(x)=y. 2. 證明 f:AB是單射的方法 方法一 x1,x2A, f(x1)=f(x2) x1=x2 推理前提 推理過程 推理結(jié)論 方法二 x1,x2A

31、, x1x2 f(x1)f(x2) 推理前提 推理過程 推理結(jié)論 3. 證明 f:AB不是滿射的方法： 找到 yB, yranf 4. 證明 f:AB不是單射的方法：找到 x1,x2A, x1x2, 且 f(x1)=f(x2)58證明方法59練習(xí)練習(xí)66已知已知A=n7|nN, B=n109|nN, 求下列各題：求下列各題：(1) Card A(2) Card B(3) card (A B)(4) card (A B)解解 (1) 構(gòu)造雙射函數(shù)構(gòu)造雙射函數(shù) f:NA, f(n)=n7 , 因此因此 card A=0(2) 構(gòu)造雙射函數(shù)構(gòu)造雙射函數(shù) g:NA, g(n)=n109, 因此因此ca

32、rd B=0(3) 可數(shù)集的并仍舊是可數(shù)集，因此可數(shù)集的并仍舊是可數(shù)集，因此card(A B) 0, 但是但是 card(A B) card A=0, 從而得到從而得到 card(A B)= 0. (4) 因?yàn)橐驗(yàn)?與與109互素，互素，card(A B)=n7 109 | n N，與與(1) 類似得到類似得到 card(A B)= 060運(yùn)算表：表示有窮集上的一元和二元運(yùn)算運(yùn)算表：表示有窮集上的一元和二元運(yùn)算 運(yùn)算表運(yùn)算表 二元運(yùn)算的運(yùn)算表二元運(yùn)算的運(yùn)算表 一元運(yùn)算的運(yùn)算表一元運(yùn)算的運(yùn)算表1設(shè) 運(yùn)算為Q上的二元運(yùn)算， x, yQ, x y = x+y+2xy, (1) 判斷 運(yùn)算是否滿足交換

33、律和結(jié)合律，并說明理由.(2) 求出 運(yùn)算的單位元、零元和所有可逆元素的逆元.61練習(xí)1(1) 運(yùn)算可交換，可結(jié)合運(yùn)算可交換，可結(jié)合. 任取任取 x, y Q, x y = x+y+2xy = y+x+2yx = y x,任取任取 x, y, z Q, (x y) z = (x+y+2xy)+z+2(x+y+2xy)z = x+y+z+2xy+2xz+2yz+4xyz x (y z) = x+(y+z+2yz)+2x(y+z+2yz = x+y+z+2xy+2xz+2yz+4xyz62(2) 設(shè)設(shè) 運(yùn)算的單位元和零元分別為運(yùn)算的單位元和零元分別為 e 和和 ，則，則對于任對于任意意 x 有有

34、x e = x 成立，即成立，即 x+e+2xe = x e = 0 由于由于 運(yùn)算可交換，所以運(yùn)算可交換，所以 0 是幺元是幺元.對于任意對于任意 x 有有x = 成立，即成立，即 x+ +2x = x+2x = 0 = 1/2 給定給定 x，設(shè)，設(shè) x 的逆元為的逆元為 y, 則有則有 x y = 0 成立，即成立，即 x+y+2xy = 0 (x 1/2 )因此當(dāng)因此當(dāng)x 1/2時時， 是是x的逆元的逆元. xxy21 xx21 解答解答632下面是三個運(yùn)算表下面是三個運(yùn)算表(1) 說明那些運(yùn)算是可交換的、可結(jié)合的、冪等的說明那些運(yùn)算是可交換的、可結(jié)合的、冪等的. (2) 求出每個運(yùn)算的

35、單位元、零元、所有可逆元素的逆元求出每個運(yùn)算的單位元、零元、所有可逆元素的逆元練習(xí)練習(xí)2(1) * 滿足交換律，滿足結(jié)合律，不滿足冪等律. 不滿足交換律，滿足結(jié)合律，滿足冪等律. 滿足交換律，滿足結(jié)合律，不滿足冪等律.(2) * 的單位元為b，沒有零元， a1=c, b1=b,c1=a 的單位元和零元都不存在，沒有可逆元素. 的單位元為 a，零元為c，a1=a，b, c不是可逆元素. 說明：關(guān)于結(jié)合律的判斷需要針對運(yùn)算元素的每種選擇進(jìn)行驗(yàn)證，若|A|=n，一般需要驗(yàn)證n3個等式.單位元和零元不必參與驗(yàn)證.通過對具體運(yùn)算性質(zhì)的分析也可能簡化驗(yàn)證的復(fù)雜性.64解答65)()()(),()(|)(v

36、vNvNvvuGEvuGVuuvNv 的的閉閉鄰鄰域域的的鄰鄰域域)(|)(關(guān)關(guān)聯(lián)聯(lián)與與veGEeevI )()()()()()(,)(|)()(,)(|)(vvNvNvvvvNvvuDEvuDVuuvvvuDEuvDVuuvvDDDDDDD 的的閉閉鄰鄰域域的的鄰鄰域域的的先先驅(qū)驅(qū)元元集集的的后后繼繼元元集集8. 鄰域與關(guān)聯(lián)集鄰域與關(guān)聯(lián)集 v V(G) (G為無向圖為無向圖) （領(lǐng)域是相關(guān)聯(lián)的點(diǎn)，關(guān)聯(lián)集是相關(guān)聯(lián)的邊）v 的關(guān)聯(lián)集的關(guān)聯(lián)集 v V(D) (D為有向圖為有向圖)相關(guān)概念相關(guān)概念66例例1 無向圖無向圖G有有16條邊，條邊，3個個4度頂點(diǎn)，度頂點(diǎn)，4個個3度頂點(diǎn)，其余頂點(diǎn)度數(shù)均小于

37、度頂點(diǎn)，其余頂點(diǎn)度數(shù)均小于3，問問G的階數(shù)的階數(shù)n為幾？為幾？解解 本題的關(guān)鍵是應(yīng)用握手定理本題的關(guān)鍵是應(yīng)用握手定理. 設(shè)除設(shè)除3度與度與4度頂點(diǎn)外，還有度頂點(diǎn)外，還有x個頂點(diǎn)個頂點(diǎn)v1, v2, , vx， 則則 d(vi) 2，i =1, 2, , x，于是得不等式于是得不等式 32 24+2x得得 x 4, 階數(shù)階數(shù) n 4+4+3=11. 握手定理應(yīng)用握手定理應(yīng)用1 . V=v1, v2, , vn為無向圖G的頂點(diǎn)集，稱d(v1), d(v2), , d(vn)為G的度數(shù)列 2. V=v1, v2, , vn為有向圖D的頂點(diǎn)集， D的度數(shù)列：d(v1), d(v2), , d(vn)

38、D的出度列：d+(v1), d+(v2), , d+(vn) D的入度列：d(v1), d(v2), , d(vn) 3. 非負(fù)整數(shù)列d=(d1, d2, , dn)是可圖化的，是可簡單圖化的.易知：(2, 4, 6, 8, 10)，(1, 3, 3, 3, 4) 是可圖化的，后者又是可簡單圖化的，而(2, 2, 3, 4, 5)，(3, 3, 3, 4) 都不是可簡單圖化的，特別是后者也不是可圖化的67圖的度數(shù)列定義14.5 設(shè)G1=, G2=為兩個無向圖(兩個有向圖)，若存在雙射函數(shù)f:V1V2, 對于vi,vjV1, (vi,vj)E1 當(dāng)且僅當(dāng) (f(vi),f(vj)E2 （E1 當(dāng)

39、且僅當(dāng) E2 )并且, (vi,vj)（）與 (f(vi),f(vj)（）的重?cái)?shù)相同，則稱G1與G2是同構(gòu)的，記作G1G2. (即簡單說來就是可以讓點(diǎn)一一對應(yīng)即簡單說來就是可以讓點(diǎn)一一對應(yīng))68圖的同構(gòu)l 圖之間的同構(gòu)關(guān)系具有自反性、對稱性和傳遞性圖之間的同構(gòu)關(guān)系具有自反性、對稱性和傳遞性.l 能找到多條同構(gòu)的必要條件，但它們?nèi)皇浅浞謼l件：能找到多條同構(gòu)的必要條件，但它們?nèi)皇浅浞謼l件： 邊數(shù)相同，頂點(diǎn)數(shù)相同邊數(shù)相同，頂點(diǎn)數(shù)相同; 度數(shù)列相同度數(shù)列相同; 對應(yīng)頂點(diǎn)的關(guān)聯(lián)集及鄰域的元素個數(shù)相同，等等對應(yīng)頂點(diǎn)的關(guān)聯(lián)集及鄰域的元素個數(shù)相同，等等 若破壞必要條件，則兩圖不同構(gòu)若破壞必要條件，則兩圖不

40、同構(gòu)l 判斷兩個圖同構(gòu)是個難題判斷兩個圖同構(gòu)是個難題69例例2 畫出畫出K4的所有非同構(gòu)的生成子圖的所有非同構(gòu)的生成子圖實(shí)例實(shí)例702. 證明下圖不是哈密頓圖證明下圖不是哈密頓圖. (破壞必要條件破壞必要條件)方法一方法一. 利用定理利用定理15.6，取取 V1 = a, c, e, h, j, l，則，則 p(G V1) = 7 |V1| = 6 練習(xí)練習(xí) 2方法二方法二. G為二部圖，互補(bǔ)頂點(diǎn)子集為二部圖，互補(bǔ)頂點(diǎn)子集 V1 = a, c, e, h, j, l, V2 = b, d, f, g, i, k, m， |V1| = 6 7 = |V2|. 方法三方法三. 利用可能出現(xiàn)在哈密頓

41、回路上的邊至少有利用可能出現(xiàn)在哈密頓回路上的邊至少有n(n為階數(shù)為階數(shù))條條這也是哈密頓圖的一個必要條件，記為（這也是哈密頓圖的一個必要條件，記為（ ）. 此圖中，此圖中，n = 13，m = 21. 由于由于h, l, j 均為均為4度頂點(diǎn)，度頂點(diǎn)，a, c, e為為3度頂點(diǎn)，且它們關(guān)聯(lián)邊互不相同度頂點(diǎn)，且它們關(guān)聯(lián)邊互不相同. 而在哈密頓回路上，而在哈密頓回路上，每個頂點(diǎn)準(zhǔn)確地關(guān)聯(lián)兩條邊，于是可能用的邊至多有每個頂點(diǎn)準(zhǔn)確地關(guān)聯(lián)兩條邊，于是可能用的邊至多有21 (3 2+3 1) = 12. 這達(dá)不這達(dá)不到（到（ ）的要求）的要求. 例1 已知無向樹T中有1個3度頂點(diǎn)，2個2度頂點(diǎn)，其余頂點(diǎn)全是樹葉，試求樹葉數(shù)，并畫出滿足要求的非同構(gòu)的無向樹. 71例題解 解本題用樹的性質(zhì)m=n1，握手定理. 設(shè)有x片樹葉，于是 n = 1+2+x = 3+x, 2m = 2(n1) = 2(2+x) = 13+22+x解出x = 3，故T有3片樹葉.T 的度數(shù)列應(yīng)為 1, 1, 1, 2, 2, 3，易知3度頂點(diǎn)與1個2度頂點(diǎn)相鄰與和2個2度頂點(diǎn)均相