離散數(shù)學習題

1、離散數(shù)學習題填空20% (每空2分)1、設f, g是自然數(shù)集N上的函數(shù)Vx三N, f(x)=x + 1, g(x)=2x,貝uf _g(x)=o2、設 A=a, b, c, A上二元關系 R= , , ,貝 U s ( R) = 。3、A=1, 2, 3, 4, 5, 6, A上二元關系T x, y R x y是素數(shù),則用列舉法T= ；T的關系圖為 ?T具有 性質。2A4、集 合 A=0 2，2 的 募 集5、P, Q 真值為 0 ; R, S 真值為 1。則 wff(P 八(R* S) T ( P V Q) A ( R A S)的 真值為 。6、 wff飛PaQ)R)t R 的 主 合 取

2、范 式 為 。7、設P (x): x是素數(shù)，E(x): x是偶數(shù)，O(x): x是奇數(shù) N (x,y): x可以整數(shù)y。則 謂詞wff Vx(P(x)-*三y(O(y)AN(y,x)的自然語言是8謂詞wff以為(切P(x,z)AP(y,z)T加Q(x,y,u)的前束范式為選才? 20% (每小題2分)1、下述命題公式中，是重言式的為()。A (pAq)T (p vq). B (pH q)修(pT q) A(q- p)；C 飛 p-q)八 q；D、(pLp)iq。2、wff(qL r的主析取范式中含極小項的個數(shù)為()。A、2;B、 3; C、5;D、0;3、給定推理-x(F(x) G(x) F(

3、y) G(y) xF(x) F(y) G(y) -xG(x).-x(F(x) G(x)= -xG(x)推理過程中錯在(A、，；B、，；C、，；D、，；4、設 Si=1 , 2,，8, 9, S2=2, 4, 6, 8, &=1 , 3,S=3, 5,在條件X * S1且X叱S3下x與( 、X=S或 S5 ；B、X=& 或C X=S, &或 S4；D、X 與 S, 、8。PUSDPESDTO) IUGE、- 5, 7, 9, S4=3, 4, 5,)集合相等。S5中任何集合都不等。5、設R和S是P上的關系，P是所有人的集合，R=|x,y八、是丫的父親S 土 X,y X X,y w P Ax是y的

4、母親則S。r表示關系()。 : x, y |x,y P x是y的丈夫A、 ,D R, f (x) =2x 1D、 o其中R為實數(shù)集，Z為整數(shù)集，R+, Z+分別表示正實數(shù)與正整數(shù)集。7、設S=1, 2, 3, R為S上的關系，其關系圖為則R具有（的性質。A、自反、對稱、傳遞;B、什么性質也沒有;C反自反、反對稱、傳遞;D、自反、對稱、反對稱、傳遞。8、設 S=641,2，則有（A、1,2 ; B、1,2 ;C、1 ; D、2。9、設 A=1 ,2 ,3 ,則 A 上有(A、23;B、32 ;C、2,D、10、全體小項合取式為（A、可滿足式； B、矛盾式;C永真式； D、A, B, C都有可能。

5、用CP規(guī)則證明16%（每小題8分）A B C D , D E F2、 X(P(X) Q(x)二 -xP(x) xQ(x)四、（14% 集合 X=, , , R=,|x 1 +y2=X2+y1。1、證明R是X上的等價關系。（10分）2、求出X關于R的商集。（4分）五、（10%設集合 A= a ,b , c , d 上關系 R= , , , 要求1、寫出R的關系矩陣和關系圖。（4分）2、用矩陣運算求出 R的傳遞閉包。（6分）六、（20%1、（ 10分）設f和g是函數(shù)，證明f c g也是函數(shù)。2、（10分）設函數(shù)g：STT f：TTS,證明f ： T T S有一左逆函數(shù)當且僅當f是 入射函數(shù)。、填空

6、20% （每空2分）4、1、:二 2,1答案:c, c , : b ,a , : c, a 反對稱性、反自反性；4、中,，2, 2, S2, 2 ； 5、1；6、（PQvR）a（-PvQvR）a（PvQvR）； 7、任意兒如果 x 是素數(shù)則存在一個 y,y 是奇數(shù)且 y 整除 x ；8. VxVyVz5urp（x, z） v-p（y, z） v Q（x, y, u）。選才i 20% （每小題2分）題目12345678910答案CCCCABDADC三、證明16%（每小題8分）1、P （附加前提）TIPTITITIPAA BA B，C DC DDD E D E FTICPFF2、-xP(x) Tx

7、Q(x)=一，x)P(x)_xQ(x)本題可證-x(P(x) Q(x)=(-xP(x)-； _xQ(x)P (附加前提)TEESPUSDTIEGDCP-(-xP(x) x(-P(x)-P-x(P(x) Q(x) P(a) Q(a) Q(a) xQ(x) 一(-xP(x)； _：.xQ(x)四、14%(1)證明：1、自反性：晨x，y*X,由于x + y = x + y:x, y ,二 x,y x R R自反2、對稱性：v xi, yiX , V , x2, y2 e R時 即x1 + y2 = x2 + yi 也即 x2 + yi = x1 + y故：x2,y2 , ,y1 三RR有對稱性3、傳

8、遞性：V X , V x2,Y2X V X當 x1，Yi,x3,、3R時即; + 丫3 = 乂3 + 丫2(2)(1)(2)xi2x23=x2.yix3y2即 Xi y3 = x3 y1故 x1, y1 二x3, y3 三RR有傳遞性由(1) (2) (3)知：R是X上的先等價關系。2、X/R= ： 1 ,2 r五、10%M R1、t 1 0 0A10 100 0 0 1 0 0 0,關系圖1010、0 10 1M D2 = M R 0M R =R0 0 0 0 0 0 0,0101M R3 = M R2M R =1010 10、0 1M 尸=M 2 M R =R R R 0 02 00 0,

9、二MR2M R5 = M R3 ,M R6 = M R41111、Mt(R) = M R M D2M d3M d4RRR11110 0 0 1工0 0 0 0t (R)= , , , , , , , , 六、20%f -g=y |x domf x domg y = f(x) y = g(x)1、（ 1）=二 x, y |x domf - domg y ; f(x)=g(x)令 h = f - gdomf - g = domh =x | x domf - domg, f (x) = g(x) h =； x, y | x - domf - domg y ; h(x)二 f (x); g(x) 又tx w domh若有y1, y2使得Vi =h(x) = f(x) =g(x) , y2 =h(x) = f (x) = g(x)由于f (或g)是函數(shù)，有y1 = V2 SPVx domh有唯一 y使得y = h(x) - f - g也是函數(shù)2、證明：=若f有一左逆g ,則對vtT g 7(t)=t故g7是入射，所以f是入射 O.廿f是入射，f :T