2020奥鹏吉大20年9月课程考试《离散数学》期末作业考核试题参考答案.docx

1、吉林大学网络教育学院2019-2020 学年第二学期期末考试离散数学大作业参考答案 综合题 (共 3 题 ，总分值 30 分 )1. 设A 是m 元集合，B 是n 元集合。问A 到 B 共有多少个不同的二元关系？设A=a，b，B=1， 2，试写出 A 到 B 上的全部二元关系。 （10 分）答：a 到 b 的二元关系是ab 的子集，即P(ab)的元素，故有 2 (mn种)二元关系就是（x,y），所以（1，a）（1,b）（2,a）（2,b）2. 指出下列表达式中的自由变量和约束变量，并指明量词的作用域：（1）(xP(x)$xQ(x)(xP(x)Q(y)（2）$xy(P(x)Q(y)zR(z)（3

2、）A(z)(xyB(x，y，a)（4）x A(x)yB(x，y)（5）($xF(x)yG(x，y，z)$zH(x，y，z) （10 分）3. 设下面所有谓词的定义域都是a，b，c。试将下面谓词公式中的量词消除，写成与之等价的命题公式。(1) xR(x)$xS(x) (2) x(P(x)Q(x)(3)xP(x)xP(x) （10 分） 答：二 证明题 (共 4 题 ，总分值 40 分 )4. 对任意集合A，B，证明： (1)AB 当 且 仅 当 r(A) r(B)； (2)r(A)r(B)r(AB)； （10 分） 答：证明： （ I ）证明： 必要性 ， 任取 江 p(A.， 则 汇 A可由

3、坟主， 故 x B， 从而 江 p(B).丁是p( A汒 p(B ) 心分性， 任取x乏A付I知 x芒且也 就 是 A己B,( 2 ) 证明；x忑A， 于是有x作 p(A )。由于p(A) ,; p(B)， 故 x E pB)， 由此任取Xe p(A) U p(B)， 则X e p(A)或 X e国B. . x仁 A 或X呻;. x三(A U B): . X芒p(A U B)所以p(A) U p( B) 三p( A U B, )5. 若集合A 上的关系R，S 具有对称性，证明：RS 具有对称性的充要条件为RS= SR。 （10 分） 答：充分性： 若 R S= S飞 往证 R. s 具有对称性

4、对 于任慈x3y幻A，若 （X,y)乏 贮 S , 则存在 a EA, 满足（凡 a) ER. (a., / ）乏 ,S又 R. S 具对称性， 所 以有(y啦 S(a, x) 芒 R所以(y七 x芒 S R,又 S R= R屯， 故 (y 1 x)RS ,因此 R心 具有对称仁必要 性 ： 若 R S 具有对 称性 往证 R心 S 屯先证 R 江 S，比 对于任慈 (x, y)丘贮S ， 因 R 心 具有对称性， 则 有 .(y , x)R心， 则存在旺 A， 满 足 y , a) 豆 R,(a,x)I:; s. 又 凡 S 具有对称性， 肵以有(X , a压 S, a,y 注 R,所以(x

5、, y）芒 .S R， 故 R 汒 S .R :再让 S lllR.Si 对于任窟(x, y) ES R, 则存在 a EA , 满足(x., .a) E S. (.a . y)E R. 又 R, S 具有对称性， 所以有 ( y, a.) E R. (a, X）E S , 故 (y , X) E R 心， 因 RS 具有对称性于 所以(x,y) E R 心故s.R 己贮 S:因此， 贮 S = S.R 得证。6. 设R 是非空集合A 上的关系，如果1） 对任意a A，都有a R a ；2） 若 aRb，aRc，则 bRc ；证明：R 是等价关系。 （10 分） 答：7. 证明：映射的乘法满足

6、结合律，举例说明：映射的乘法不满足交换律。 （10 分） 答：设 n 阶矩阵为 A=(aij),B=(bij),C=(cij),AB=(dij),BC=(eij),(AB)C=(fij),A(BC)=(gij) 由矩阵的乘法得dij=ai1*b1j+ai2*b2j+.+ain*bnj,i,j=1,2,.,n, eij=bi1*c1j+bi2*c2j+.+bin*cnj,i,j=1,2,.,n, fij=di1*c1j+di2*c2j+.+din*cnj,i,j=1,2,.,n, gij=ai1*e1j+ai2*e2j+.+ain*enj,i,j=1,2,.,n, 故 对 任 意 i,j=1,2

7、,.,n 有 , fij=di1*c1j+di2*c2j+.+din*cnj=(ai1*b11+ai2*b21+.+ain*bn1)*c1j+(ai1*b11+ai2*b21+.+ain*bn1)*c2j+.+(ai1*b1n+ai2*b2 n+.+ain*bnn)*cnj=ai1(b11*c1j+b12*c2j+.+b1n*cnj)+ai2(b21*c1j+b22*c2j+.+b2n*cnj)+.+ain(bn1*c1j+bn2*c2j+.+bnn*cnj)=ai1*e1j+ai2*e2j+.+ain*enj=gij故(AB)C=A(BC).三 问答题 (共 6 题 ，总分值 30 分 )8

8、. 请给出集合的分配率。 （5 分） 答：9. 设A=f，f，B=1，求r（A），r（B）。 （5 分） 答：r（A）=f，r（B）=110. 请给出集合的De Morgan 率。 （5 分） 答：或11. 设 A=1，f，B=f，请求出r（A），r（B） （5 分） 答：r（A）=1，r（B）=012. 设 A=1，2，3，4，B=2，4，5，6，求AB，A-B。 （5 分） 答：AB=（1，2），（1，4），（1，5），（1，6），（2，2），（2，4），（2，5），（2，6），（3，2），（3，4），（3，5），（3，6），（4，2），（4，4），（4，5），（4，6）， A-B=（1，5），（1，6），（3，5），（3，6），13. 设 A=1,2,3，B=2,3,4，求A B，A A。 （5 分）答 ： AB=（1，2），（1，3），（1，4），（2，2），（2，3），（2，3），（3，2），（3，3），（3，4），AA=（1，1），（1，2），（1，3），（2，1），（2，2），（2，3），（3，1），（3，2），（3，3）