離散數(shù)學(xué) ( 第3次 )

1、第3次作業(yè)一、填空題（本大題共20分，共 10 小題，每小題 2 分）1. 是否可以畫出一個(gè)簡(jiǎn)單的無向圖，使得各點(diǎn)度數(shù)與一下序列一致。（T or F）（1）2，2，2，2，2，2 ； （）（2）2，2，3，4，5，6 ； （）( 3) 1，2，3，4，4，5； （）2. 在根樹中，若從Vi到Vj可達(dá)，則稱Vi是Vj的_，Vj是Vi的_3. 設(shè)A=a,b,B=1,2,3，判斷下列集合是否是A到B的函數(shù)。F_1=a,1,b,2,F_2=a,1,b,1， F_3=a,1,a,2, F_4=a,34. 用列元法表示下列集合A=x|xN且x29，則可表示為（ ）。5. 設(shè)X=a,b,c,d,Y=1,2,

2、3,4,5，且有f=,，則 dom f為（ ）、R_f為 和f(x)為（ ）。6. 判斷下列命題正確與否：(1)正整數(shù)集N上的小于等于關(guān)系“”是良序關(guān)系。（ ）（2）In =1,2,n上的小于等于關(guān)系“”是良序關(guān)系。（ ）(3)整數(shù)集Z和實(shí)數(shù)集R上的小于等于關(guān)系“”是良序關(guān)系。（ ）7. 在由n個(gè)元素組成的集合上，可以有（ ）種不同的二元關(guān)系？若集合A,B的元數(shù)分別為|A|=m,|B|=n,試問從A到B有( )種不同的二元關(guān)系？8. 設(shè)R_1 和R_2 是集合A上的二元關(guān)系，試判斷下列命題是否正確？ ( ) ( ) ( )9. 設(shè)R_1和R_2是非空集合A上的等價(jià)關(guān)系，下列各式哪些是A上的等價(jià)

3、關(guān)系？哪些不是A上的等價(jià)關(guān)系 ？舉例說明：AA-R_1； ( ) R_1-R_2； ( )R_12； ( ) r(R_1-R_2)； ( )R_1R_2 ( )10. 對(duì)下述論斷判斷正確與否，在相應(yīng)括號(hào)中鍵入“Y”或“N”。設(shè)A=2,3,6,12,24,36，A上的整除關(guān)系是一偏序關(guān)系，用“”表示。(a）該偏序關(guān)系的哈斯圖是（ ）（b)“”=2,2,2,6,3,3,3,6,6,6,6,12,12,12,12,24,24,24,36,36 （ ）二、計(jì)算題（本大題共40分，共 4 小題，每小題 10 分）1. 試將公式化成等價(jià)的前束范式：xF(x)xQ(x)；2. z)R(x，y，z)z)Q(x

4、，z)(x)($x)P(x)(求等價(jià)于下面wff的前束合取范式與前束析取范式：(3. 試將公式P（PQ）化為析取范式和合取范式：4. 設(shè)f：RR，f（x）=x2-2；g：RR， g（x）=x+4。 (1)求gf，fg (2)問gf和fg是否為單射、滿射、雙射？ （3）求出f、g、gf和fg中的可逆函數(shù)的逆函數(shù)。三、簡(jiǎn)答題（本大題共20分，共 4 小題，每小題 5 分）1. 設(shè)G是有兩個(gè)奇度點(diǎn)的連通圖,設(shè)計(jì)一個(gè)構(gòu)造G的歐拉道路的算法。2. 設(shè)X=2,3,4,5，求集合 上的關(guān)系“”、dom及ran。3. 設(shè)A=1,2,3,4,5,R=,，畫出R的關(guān)系圖。4. 給定集合A=1,2,3,4,5，在集

5、合A上定義兩種關(guān)系：R=,，S=,，求RS和SR的矩陣。四、證明題（本大題共20分，共 2 小題，每小題 10 分）1. 證明:xy(P(x)Q(y) )=xP(x)yQ(y)2. 設(shè)是一個(gè)代數(shù)系統(tǒng)，*是R上的一個(gè)二元運(yùn)算，使得對(duì)于R中的任意元素a,b都有a*b=a+b+ab,試證明：0是幺元且是獨(dú)異點(diǎn)。答案：一、填空題（20分，共 10 題，每小題 2 分）1. 參考答案：（1）T （2）F （3） F解題方案：評(píng)分標(biāo)準(zhǔn)：2. 參考答案：祖先；后代解題方案：評(píng)分標(biāo)準(zhǔn)：3. 參考答案：F_1,F_2是函數(shù)，F(xiàn)_3,F_4不是函數(shù)。解題方案：若不強(qiáng)調(diào)是A到B的函數(shù)，則F_4是函數(shù)，其定義域?yàn)閍。

6、評(píng)分標(biāo)準(zhǔn)：4. 參考答案：1,2,3解題方案：評(píng)分標(biāo)準(zhǔn)：5. 參考答案：a,b,c,d 1,3,4 f(a)=1,f(b)=3,f(c)=4,f(d)=4解題方案：評(píng)分標(biāo)準(zhǔn)：6. 參考答案：正確 正確 錯(cuò)誤解題方案：整數(shù)集Z和實(shí)數(shù)集R上的小于等于關(guān)系“”不是良序關(guān)系 (因?yàn)閆或R本身無最小元) 。評(píng)分標(biāo)準(zhǔn)：7. 參考答案：2(n2 ) 2(mn) 解題方案：評(píng)分標(biāo)準(zhǔn)：8. 參考答案：（1）命題正確（2）命題正確（3）命題不正確解題方案：評(píng)分標(biāo)準(zhǔn)：9. 參考答案：（1）不是 （2）不是 （3） 是 （4） 不是 （5） 是解題方案：評(píng)分標(biāo)準(zhǔn)：10. 參考答案：Y N解題方案：評(píng)分標(biāo)準(zhǔn)：二、計(jì)算題

7、（40分，共 4 題，每小題 10 分）1. 參考答案：xF(x)xQ(x)=xF(x)xQ(x)=xF(x)xQ(x)=x(F(x)Q(x)解題方案：評(píng)分標(biāo)準(zhǔn)：2. 參考答案：z)R(x，y，z)z)Q(x，z)(x)($x)P(x)( z)R(x，y，z)z)Q(x，z)(x)($x)P(x)(u)R(x，y，u)z)Q(x，z)(x)($x)P(x)($(u)R(x，y，u)z)Q(x，z)(x)( P(x)($(u)( P(x)Q(x，z)R(x，y，u)z)(x)($(前束合取范式u)(P(x) Q(x，z) R(x，y，u)(P(x) Q(x，z) R(x，y，u)(P(x) Q(

8、x，z) R(x，y，u)(P(x) Q(x，z) R(x，y，u)(P(x) Q(x，z)R(x，y，u)(P(x) Q(x，z) R(x，y，u)(P(x) Q(x，z) R(x，y，u)z)(x)($(前束析取范式解題方案：評(píng)分標(biāo)準(zhǔn)：3. 參考答案：（PQ）（PQ）=(（PQ）（PQ）)(（PQ）（PQ）)(等值律)=(（PQ）（PQ）) (（PQ）（PQ）) (蘊(yùn)涵律)=（PQ）(PQ) (分配律) 合取范式=(PP) (PQ)(QP)(QQ) (分配律)析取范式解題方案：評(píng)分標(biāo)準(zhǔn)：4. 參考答案：（1）fg =x,x2+8x+14|x R gf =x,x2 +2|xR （2）gf 和

9、 fg均是非單非滿函數(shù)。 （3）因?yàn)間是雙射，所以可逆，其逆函數(shù)為：g(-1) ( x)=x-4。解題方案：評(píng)分標(biāo)準(zhǔn)：三、簡(jiǎn)答題（20分，共 4 題，每小題 5 分）1. 參考答案：step1: 添加連接兩個(gè)奇度點(diǎn)的邊Step2: 調(diào)用一般的歐拉回路的算法Step3: 在回路中刪除添加的邊解題方案：評(píng)分標(biāo)準(zhǔn)：2. 參考答案：=,dom2,3,4ran3,4,5解題方案：評(píng)分標(biāo)準(zhǔn)：3. 參考答案：解題方案：評(píng)分標(biāo)準(zhǔn)：4. 參考答案：圖 3.6.1-2 RS的矩陣圖 3.6.1-3 SR的矩陣解題方案：因?yàn)殛P(guān)系可用圖形表示，所以復(fù)合關(guān)系也可用圖形表示。評(píng)分標(biāo)準(zhǔn)：四、證明題（20分，共 2 題，每小題 10 分）1. 參考答案：xy(P(x)Q(y) )=xy(P(x)Q(y) )=xP(x)yQ(y)=xP(x)yQ(y)=xP(x)yQ(y)解題方案：評(píng)分標(biāo)準(zhǔn)：2. 參考答案：對(duì)任意 aR，有0*a=0+a+0a=aa*0=a+0+a0=a故0是幺元。對(duì)任意 a,bR，有a*b=a+b+abR所以*是封閉的。對(duì)任意 a