1、.離散數(shù)學(xué)形成性考核作業(yè)4姓名：嚴(yán)先貴學(xué)號(hào) 1944201250206得分：教師簽名：離散數(shù)學(xué)綜合練習(xí)書面作業(yè)要求：學(xué)生提交作業(yè)有以下三種方式可供選擇：1. 可將此次作業(yè)用 A4 紙打印出來，手工書寫答題，字跡工整，解答題要有解答過程，完成作業(yè)后交給輔導(dǎo)教師批閱2. 在線提交 word 文檔3. 自備答題紙張，將答題過程手工書寫，并拍照上傳一、公式翻譯題1請(qǐng)將語句“小王去上課，小李也去上課”翻譯成命題公式設(shè)： P:小王去上課。Q：小李去旅游。則 P Q2請(qǐng)將語句“他去旅游，僅當(dāng)他有時(shí)間”翻譯成命題公式設(shè)： P:他去旅游Q：他有時(shí)間則 P Q3請(qǐng)將語句“有人不去工作”翻譯成謂詞公式設(shè) A （x）

2、： x 是人B（x）：去工作x(A(x)B(x)4請(qǐng)將語句“所有人都努力學(xué)習(xí)”翻譯成謂詞公式設(shè) A （x）： x 是人B（x）：努力學(xué)習(xí)x(A(x) B(x).二、計(jì)算題1設(shè) A=1,2,1,2，B=1,2,1,2 ，試計(jì)算（1）(A B)；（2）(AB)；（3）A×B解（1）（ A B）= 1,2（2）（ AB）= 1,2（3） A×B=< 1 ，1， 1 ，22設(shè) A=1 ，2，3，4，5 ，R=< x，y>|xA，yA 且 x+y 4 ，S=< x，y>|x A，- 1- 1，r(S)， s(R)y A 且 x+y<0 ，試求 R，

3、S，R?S，S?R， R ，S解： R=1，1， 1，2， 1，3， 2，1， 2，2， 3，1，S=R?S=S?R=R-1=1，1， 2，1， 3，1， 1，2， 2，2， 1，3S-1 =r(S)= 1，1， 2，2， 3， 3， 4，4， 5，5s(R)= 1， 1， 1，2， 1，3， 2， 1， 2，2， 3，13設(shè) A=1, 2, 3, 4, 5, 6, 7, 8 ，R 是 A 上的整除關(guān)系， B=2, 4, 6 (1) 寫出關(guān)系 R 的表示式；(2) 畫出關(guān)系 R 的哈斯圖；(3) 求出集合 B 的最大元、最小元解： R=1，1， 1，2， 1，3， 2，1， 2，2， 3，1，

4、S=R?S=S?R=.R-1=1，1， 2，1， 3，1， 1，2， 2，2， 1，3S-1 =r(S)= 1，1， 2，2， 3， 3， 4，4， 5，5s(R)= 1， 1， 1，2， 1，3， 2， 1， 2，2， 3，1.4設(shè)A=1, 2, 3, 4, 5, 6, 7, 8，R是A上的整除關(guān)系， =2, 4, 6 B(1) 寫出關(guān)系 R 的表示式；(2 ) 畫出關(guān)系 R 的哈斯圖；(3) 求出集合 B 的最大元、最小元解： (1) R=1，1，1，2， 1，3，1，4， 1，5，1，6， 1，7，1，8，2，2， 2，4，2，6，2 ，8，3，3 ， 3，6， 4，4， 4，8，5，5

5、， 6，6， 7，7， 8，8 (2 ) 關(guān)系 R 的哈斯圖84632571(3) 集合 B 的沒有最大元，最小元是 24設(shè) G=<V，E>，V= v1，v2，v3，v4，v5 ，E= ( v1 ,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v ,v )，(v ,v ) ，試3545(1)給出 G 的圖形表示；(2)寫出其鄰接矩陣；(3)求出每個(gè)結(jié)點(diǎn)的度數(shù)；(4)畫出其補(bǔ)圖的圖形解： (1)v1v2v5.v3v4.(2) 鄰接矩陣為0010000110110110110100110(3) v1 結(jié)點(diǎn)度數(shù)為1， v2 結(jié)點(diǎn)度數(shù)為2， v3 結(jié)點(diǎn)度數(shù)為3， v4 結(jié)點(diǎn)度數(shù)

6、為2， v5 結(jié)點(diǎn)度數(shù)為2(4) 補(bǔ)圖圖形為v1v2v5v3v45圖 G=<V, E>，其中 V= a, b, c, d, e ，E= ( a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (c, d), (d, e) ，對(duì)應(yīng)邊的權(quán)值依次為 2、1、2、3、6、1、4 及 5，試（1）畫出 G 的圖形；（2）寫出 G 的鄰接矩陣；（3）求出 G 權(quán)最小的生成樹及其權(quán)值解：（1）G 的圖形如下：（2）寫出 G 的鄰接矩陣.3）G 權(quán)最小的生成樹及其權(quán)值6設(shè)有一組權(quán)為 2, 3, 5, 7, 17, 31，試畫出相應(yīng)的最優(yōu)二叉樹，計(jì)算該最優(yōu)二

7、叉樹的權(quán).6331117175523權(quán)為2*5+3*5+5*4+7*3+17*2+31=1317 求 PQ R 的析取范式，合取范式、主析取范式，主合取范式8設(shè)謂詞公式 ( x)( P(x, y)(z)Q( y, x, z)(y)R( y, z) （1）試寫出量詞的轄域；.（2）指出該公式的自由變?cè)图s束變?cè)?設(shè)個(gè)體域?yàn)?D= a1, a2 ，求謂詞公式 (y)( x)P(x,y)消去量詞后的等值式；三、證明題1對(duì)任意三個(gè)集合 A, B 和 C，試證明：若 A B = A C，且 A，則B=C證明：（1）對(duì)于任意a ，b ，其中 a A，b ，因?yàn)锳B=A C，A BB必有 a ，b AC ，

8、其中 b C ，因此 BC 。（ 2）同理，對(duì)于任意 a ，c A C ，其中 a A ，c C ，因?yàn)?AB=AC，必有 a ，c A B，其中 c ，因此C。BB由（ 1）、（ 2）得： B = C 2試證明：若 R 與 S 是集合 A 上的自反關(guān)系，則 RS 也是集合 A 上的自反關(guān)系證明：若 R 與 S 是集合 A 上的自反關(guān)系，則任意x A, x,x R,x,x S,.從而 x,x R S,注意 x 是 A 的任意元素，所以RS 也是集合 A 上的自反關(guān)系。k3設(shè)連通圖 G 有 k 個(gè)奇數(shù)度的結(jié)點(diǎn)， 證明在圖 G 中至少要添加條邊才能使其成為歐拉圖證明：由定理 3.1.2，任何圖中度數(shù)為奇數(shù)的結(jié)點(diǎn)必是偶數(shù)， 可知 k 是偶數(shù)又根據(jù)定理 4.1.1 的推論，圖 G