2022年2022年离散数学期末考试试题 .pdf
《2022年2022年离散数学期末考试试题 .pdf》由会员分享,可在线阅读,更多相关《2022年2022年离散数学期末考试试题 .pdf(12页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、离散试卷及答案第 1 页 共 12 页离散数学试题 (A 卷及答案)一、证明题( 10 分)1)(P(QR) (QR)(PR)R 证明: 左端(P Q R) (QP)R) (P Q) R)(QP) R) ( (PQ)R) (QP)R)( (PQ) (QP)R ( (PQ)(P Q)R T R(置换)R 2)x(A(x)B(x)xA(x)xB(x) 证明: x(A(x)B(x)x( A(x) B(x)x A(x) xB(x)xA(x) xB(x)xA(x)xB(x) 二、求命题公式(P(QR)(PQ R)的主析取范式和主合取范式(10 分)证明: (P(QR)(PQ R)(P(QR) (P QR
2、) (P(Q R)) (PQR) (PQ)(PR) (PQ R) (PQ R)(P Q R)(PQ R) (PQ R) (PQ R) m0 m1 m2 m7 M3 M4 M5 M6 三、推理证明题(10 分)1) CD, (C D)E, E(AB), (AB)(RS)RS 证明: (1) (CD)E (2) E(AB) (3) (CD)(AB) (4) (AB)(RS) (5) (CD)(RS) (6) C D (7) R S 2) x(P(x)Q(y) R(x) , xP(x)Q(y) x(P(x)R(x) 证明( 1) xP(x) (2)P(a) (3)x(P(x)Q(y) R(x) (4
3、)P(a)Q(y) R(a) (5)Q(y)R(a) (6)Q(y) (7)R(a) (8)P(a) (9)P(a)R(a) (10)x(P(x) R(x) (11)Q(y) x(P(x) R(x) 四、设m是一个取定的正整数,证明:在任取m1 个整数中,至少有两个整数,它们的差是m的整数倍证明设1a,2a,1ma为任取的m1 个整数,用m去除它们所得余数只能是0,1,m1,由抽屉原理可知,1a,2a,1ma这m1 个整数中至少存在两个数sa和ta,它们被m除所得余数相同,因此sa和ta的差是m的整数倍。五、已知A 、B、C 是三个集合,证明A-(B C)=(A-B) (A-C) (15 分)
4、证明xA-(BC)xAx(BC)xA( xBxC)(xAxB )( xAxC)x(A-B)x(A-C) x(A-B)( A-C) A-(BC)=(A-B)( A-C)六、已知R、S 是 N 上的关系,其定义如下:R=| x,yNy=x2 ,S=| x,yNy=x+1 。求 R-1、R*S、S*R、R 1,2 、S1,2(10 分)解: R-1=| x,yNy=x2 ,R*S=| x,yNy=x2+1 ,S*R=| x,yNy=(x+1)2 ,七、若 f:A B和 g:B C是双射,则( gf )-1=f-1g-1(10 分) 。名师资料总结 - - -精品资料欢迎下载 - - - - - -
5、- - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页,共 12 页 - - - - - - - - - 离散试卷及答案第 2 页 共 12 页证明:因为f 、g 是双射,所以gf :AC是双射,所以gf 有逆函数( gf )-1:CA。同理可推f-1g-1:CA是双射。因为 f-1g-1存在 z( g-1 f-1)存在 z( f g) gf (gf )-1,所以( gf )-1=f-1g-1。R 1,2=,,S1,2=1,4。八、 (15 分)设 是半群,对A中任意元a和b,如ab必有a*bb*a,证明:(1) 对A中每个元a,有a*aa。(2)
6、 对A中任意元a和b,有a*b*aa。(3) 对A中任意元a、b和c,有a*b*ca*c。证明由题意可知,若a*bb*a,则必有ab。(1) 由(a*a)*aa*(a*a) ,所以a*aa。(2) 由a*(a*b*a) (a*a)*(b*a) a*b*(a*a) (a*b*a)*a,所以有a*b*aa。(3) 由(a*c)*(a*b*c) (a*c*a)*(b*c) a*(b*c)(a*b)*c(a*b)*(c*a*c)(a*b*c)*(a*c) ,所以有a*b*ca*c。九、给定简单无向图G,且 |V| m,|E| n。试证:若n21mC2,则G是哈密尔顿图证明若n21mC2,则 2nm23
7、m6 (1) 。若存在两个不相邻结点u 、 v 使得 d( u ) d( v )m,则有 2nVwwd)(m(m2)(m3) mm23m6,与( 1)矛盾。所以,对于G中任意两个不相邻结点u 、 v 都有 d( u ) d( v) m,所以G是哈密尔顿图。离散数学试题 (B 卷及答案)一、证明题( 10 分)1)(P Q)(P(Q R) (PQ)(PR)T 证明左端(P Q)(P(QR) (P Q)(PR)( 摩根律 ) (P Q)(PQ)(PR) (P Q)(PR)( 分配律 ) (P Q)(PR) (P Q)(PR) ( 等幂律 ) T ( 代入 ) 2)x(P(x)Q(x) xP(x)x
8、(P(x) Q(x) 证明x(P(x)Q(x) xP(x)x(P(x)Q(x) P(x)x(P(x) Q(x) P(x)x(P(x) Q(x)xP(x) xQ(x)x(P(x) Q(x) 二、求命题公式(PQ)(PQ) 的主析取范式和主合取范式(10 分)解: (PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ) (PPQ)(QP Q)(PQ)M1m0 m2 m3 三、推理证明题(10 分)1)(P(QS) (RP)QRS 证明: (1)R 附加前提(2)RP P (3)P T(1)(2),I (4)P(QS) P (5)QS T(3)(4),I (6)Q P (7)S T(5)(
9、6),I (8)RS CP 2) x(P(x) Q(x) ,xP(x)x Q(x) 证明: (1)xP(x) P (2)P(c) T(1),US (3)x(P(x) Q(x) P (4)P(c)Q(c) T(3),US (5)Q(c) T(2)(4),I (6)x Q(x) T(5),EG 四、例 5 在边长为 1 的正方形内任意放置九个点,证明其中必存在三个点,使得由它们组成的三角形(可能是退化的)面积不超名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页,共 12 页 - -
10、 - - - - - - - 离散试卷及答案第 3 页 共 12 页过 1/8 (10 分) 。证明: 把边长为 1 的正方形分成四个全等的小正方形,则至少有一个小正方形内有三个点,它们组成的三角形(可能是退化的)面积不超过小正方形的一半,即1/8 。五、已知A 、B、C 是三个集合,证明A(BC)=(AB)(AC) (10 分)证明: x A (BC) x A x(BC) x A ( xBxC )( x A xB)( x A xC) x(AB)x A C x(A B)( AC) A( BC)=(AB )( AC)六、=A1,A2, An 是集合 A的一个划分,定义R=|a 、bAi,I=1
11、,2, n,则 R是 A上的等价关系(15 分) 。证明:a A必有 i 使得 aAi,由定义知aRa ,故 R自反。a,b A,若 aRb ,则 a,b Ai,即 b,a Ai,所以 bRa,故 R对称。a,b,c A,若 aRb 且 bRc,则 a,b Ai及 b,c Aj。因为 i j 时 AiAj=,故 i=j ,即 a,b,c Ai,所以 aRc,故 R传递。总之 R 是 A 上的等价关系。七、若 f:A B是双射,则f-1:B A是双射( 15 分) 。证明 :对任意的 xA,因为 f 是从 A到 B的函数,故存在yB,使 f , f-1。所以 ,f-1是满射。对任意的 xA ,若
12、存在y1,y2B,使得 f-1且 f-1, 则有 f 且f。因为 f 是函数,则y1=y2。所以, f-1是单射。因此 f-1是双射。八、设 是群, 和是的子群,证明:若ABG,则AG或BG(10 分)。证明假设AG且BG,则存在a A,a B,且存在b B,b A(否则对任意的a A,a B,从而A B,即ABB,得BG,矛盾。)对于元素a*b G,若a*b A,因A是子群,a-1A,从而a-1 * (a*b) bA,所以矛盾,故a*b A。同理可证a*b B,综合有a*b ABG。综上所述,假设不成立,得证AG或BG。九、若无向图G是不连通的,证明G的补图 G 是连通的( 10 分) 。证
13、明设无向图G是不连通的,其k个连通分支为1G 、2G 、kG 。任取结点 u 、 vG,若 u 和 v 不在图G的同一个连通分支中,则 u , v 不是图G的边,因而 u , v 是图 G 的边;若 u 和 v 在图G的同一个连通分支中,不妨设其在连通分支iG (1 i k)中,在不同于iG 的另一连通分支上取一结点w ,则 u , w 和 w , v 都不是图G的边,因而 u , w 和 w , v 都是 G 的边。综上可知,不管那种情况,u 和 v 都是可达的。由u 和 v 的任意性可知,G 是连通的。一、选择题 .( 每小题 2 分,总计 30) 1.给定语句如下:(1)15 是素数(质
14、数)(2)10 能被 2 整除, 3 是偶数。(3)你下午有会吗?若无会,请到我这儿来!(4)2x+30. (5)只有 4 是偶数, 3 才能被 2 整除。(6) 明年 5 月 1 日是晴天。以上 6 个语句中, 是简单命题的为 (A), 是复合命题的为 (B), 是真命题的为 (C), 是假命题的是 (D), 真值待定的命题是 (E)A: (1)(3)(4)(6) (1)(4)(6) (1) (6) B: (2)(4) (2)(4)(6) (2)(5) C: (1)(2)(5)(6) 无真命题( 5) D: (1)(2) 无假命题(1)(2)(4)(5) E: (4)(6) ( 6) 无真值
15、待定的命题2. 将下列语句符号化:(1)4 是偶数或是奇数。 (A)设 p:4 是偶数, q:4 是奇数名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页,共 12 页 - - - - - - - - - 离散试卷及答案第 4 页 共 12 页(2)只有王荣努力学习,她才能取得好成绩。(B )设 p:王荣努力学习,q:王荣取得好成绩(3)每列火车都比某些汽车快。(C)设 F(x):x是火车, G(y):y是汽车, H(x,y):x比 y 快。A: p q p q p q B: p
16、 q q p p q C: xy (F(x)G(y) (H(x,y)x (F(x)y(G(y) H(x,y)x (F(x)y(G(y) H(x,y) 3. 设 S=1,2,3,下图给出了S上的 5 个关系 , 则它们只具有以下性质:R1是( A),R2是(B),R3是(C) 。A B C: 自反的,对称的,传递的反自反的,对称的自反的反对称的对称的自反的,对称的,反对称的,传递的4. 设S=,1 ,1 ,2 ,则有(1) (A) S (2) (B)S (3) P(S) 有( C)个元数。(4) (D)既是 S的元素,又是 S的子集A: 1,2 1 B: 1,2 1 C: 3 6 7 8 D:
17、1 二、证明(本大题共2 小题,第 1 小题 10 分,第 2 小题 10 分,总计 20 分)1、用等值演算算法证明等值式 (p q) (p q)p 2、构造下面命题推理的证明如果今天是星期三,那么我有一次英语或数学测验;如果数学老师有事,那么没有数学测验;今天是星期三且数学老师有事,所以我有一次英语测验。三、计算(本大题共4 小题,第 1 小题 5 分,第 2 小题 10 分,第 3 小题 15 分,总计 30 分)1、设212,,个体域为为,整除为xxQyxyxP,求公式:xQyxPyx,的真值。2、设集合AA,4, 3 ,2, 1上的关系4, 3,3 , 2,1 , 2,2, 1,1
18、, 1R,求出它的自反闭包,对称闭包和传递闭包。3、设,24,12,8 ,4,2 , 1A上的整除关系212121,aaAaaaaR整除,R是否为A上的偏序关系?若是,则:1、画出R的哈斯图;(10 分)2、求它的极小元,最大元,极大元,最大元。(5 分)四、 用推导法求公式pqp的主析取范式和主合取范式。(本大题 10分)答案:一、 选择题1.A: B: C: D: E: 2.A: B: C: 3.A: B: C: 4.A: B: C: D: 二、证明题1.证明左边((p q) p)( (p q) q) )(分配律) p ( (pq)q) ) (吸收律 ) p ( (pq) (q q) )(
19、分配律) p ( (pq) 1)(排中律)名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页,共 12 页 - - - - - - - - - 离散试卷及答案第 5 页 共 12 页 p (p q) (同一律) p (吸收律)2. 解: p:今天是星期三。 q:我有一次英语测验。 r:我有一次数学测验。 s:数学老师有事。前提: p(q r) , sr , ps 结论: q 证明: ps 前提引入p 化简p(q r) 前提引入qr 假言推理s 化简sr 前提引入r 假言推理q 析
20、取三段论推理正确。三、计算1. ,1,12,21,112,121,212,22xyP x yQ xyPyQPyQPQPQPQPQ1,11,1,21,2,10,2,21,11,20110011101PPPPQQ该公式的真值是1,真命题。或者TTTFTTTFTFFTTTTQPQPQPQPxQxPxQxPxxQyxPyx22, 221 ,212, 111 , 12,1 ,2、4, 4,3, 3,2, 2,4, 3,3, 2,1 ,2,2, 1,1 , 1)(Rr3, 4,2, 3,4, 3,3 ,2,1 ,2,2, 1,1 , 1)(Rs4, 1,4 ,2,2, 2,3, 1,4, 3,3 ,2,1
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2022年2022年离散数学期末考试试题 2022 离散数学 期末 考试 试题
限制150内