《离散数学模拟试卷 a》由会员分享,可在线阅读,更多相关《离散数学模拟试卷 a(5页珍藏版)》请在金锄头文库上搜索。
1、离散数学模拟试卷离散数学模拟试卷 A 一、单项选择题 (每题 2 分,共 20 分。 ) 1、前提PQ, QR, R 的结论是( ) 。 A. Q B. P C. PQ D. PR 2、下列语句为命题的是( ) 。 暮春三月,江南草长。 这是多么可爱的风景啊! 大家想做什么,就做什么,行吗? 请勿践踏草坪! 、设无向图 G 有 12 条边,已知 G 中 3 度结点有 6 个,其余结点度数均小于 3,则 G 中结 点数至少为( ) 。 A.6 B 8 C 9 D12 、在下列选项中,不是群的是( ) 。 (,) ,为有理数集,为加法运算。 (,*) ,为非零实数集,*为乘法运算。 全体实对称矩阵
2、集合,对于矩阵的加法运算。 (,*) ,为有理数集,*为乘法运算。 、设 ,P(P(A),以下不正确的是( ) 。 , 包含于 , 包含于 、设集合, ,下列关系中不是等价关系的是( ) 。 (,) , (,) , (,) (,) , (,) , (,),(,) , (,) (,) , (,) , (,), (1, 4) (,) , (,) , (,),(,) , (,) , (,),(,) , (,), (,) 、在下列关于图论的命题中,正确的是( ) 。 A哈密尔顿图一定是欧拉图。 B无向完全图 Kn(n=3) 都是欧拉图。 C度数为奇数的结点个数为 0 个或 2 个的连通的无向图 G 可
3、一笔画出。 D哈密尔顿图是平面图。 、设 T 是有 n 个结点的完全二叉树,则 T 叶子数为( ) 。 An1 B2n1 C(n+1)/2 D(n+2)/3 、对于如下某个偏序集的哈斯图,其中集合a,b,c,e的最大元是( ) 。 Ac Bd Ce D无、命题公式 A 和 B 是等价的,是指( ) 。 AA 和 B 有相同的原子变元。 BA 和 B 都是可满足的。 C当 A 的真值为真时,B 的真值也为真。 DA 和 B 有相同的真值。 二、填空题 (每空 1 分,共 15 分。 ) 1、设 R 为非空集合 A 上的二元关系,如果 R 满足( ) 、 ( ) 、 ( ) ,则称 R 为 A 上
4、的一个 偏序关系。 2、设为有理数集,笛卡尔积 S=QQ,*是 S 上的二元运算: (a, b) , (x, y)S , 有 (a, b)*(x, y)=(ax , y+b) ,则*运算的单位元为( ) ,(a, b)S ,a0,则(a, b)的 逆元是( ) 。 3、 一个无向图的欧拉回路要求经过图中 ( ) 一次且仅一次, 哈密尔顿回路要求经过图中 ( ) 一次且仅一次。 4、无向图结点之间的连通性,是节点集之间一个( )关系。 5、对于有向图的连通性,若有向图 D 是( ) ,则它必是单向连通, 若有向图 D 是单向连通, 则它一定是( ) 。 6、若集合 A=1, 2, 3上的二元关系
5、 R1 和 R2 的关系图如下所示, 则 R1oR2 =( ) ,R2o R1=( ) 。 7、用 Q 和 PQ 同时代入合式公式 P(PQ)中的 P 和 Q,所得代换实例为( ) 。 8、设 p:小王走路,q:小王听音乐,在命题逻辑中,命题“小王边走路边听音乐”的符号化形式为 ( ) 。 9、树是平面图,它有( )个面。 三、计算题 (每题 5 分,共 10 分) 1、 设集合 A=1,2,3,4,5上的二元关系 R 如下图所示: 试判断 R 是否是 A 上的等价关系,若是,写出各元素的等价类;若不是,请写出理由。2、设无向图 G 如下所示:求最小生成树 T。 四、构造下列推理的证明 (每题
6、 5 分,共 15 分) 1、(PQ) ,QR,R P 2、x(F(x) A(x)) ,x(A(x)B(x),x B(x) x F(x) 3、求|(PQ)(PQ)的析取范式 五、证明题(每题 10 分,共 20 分) 1、 设 R 是一个二元关系,设 S= |存在某个 C,使R 且R,证明 R 是 一个等价关系,则 S 也是一个等价关系。 设 为群,任意 a,b,cA, 证明 a*b=a*c,则 b=c。 六、应用题(每题 10 分,共 20 分) 1、 已知关于人员 a,b,c,d,e,f 和 g 的下述事实: a 说英语; b 说英语和西班牙语; c 说英语,意大利语和俄语; d 说日语和
7、西班牙语; e 说德语和意大利语; f 说法语,日语和俄语; g 说法语和德语。 试问: 上述7人中是否任意两人都能交谈 (如有必要, 可由其余5人中所组成的译员链帮忙) ? 2、符号化下列命题并推证其结论: 没有不守信用的人是可以信赖的,有些可以信赖的人是受过教育的人,因此,有些受过 教育的人是可守信用的。 (个体域:所有人的集合)离散数学模拟试卷离散数学模拟试卷 B 一、 判断题(每题 2 分,共 20 分) 1、哈密尔顿图是平面图。 ( ) 2、设 A、B 为集合,若 B,则 AB 包含于 A。 ( ) 3、若 R 为集合 A 上的非对称关系,则 R 2 亦然。 ( ) 4、若 g of
8、 为内射且 f 为满射,则 g 为内射。 ( ) 5、若:且,包含于,则 。 ( ) 6、 “这是多么可爱的风景啊! ”这个语句是命题。 ( ) 7、若 R1,R2 为集合 A 上的相容关系,则 R1R2 亦然。 ( ) 8、简单无向图的邻接矩阵是一个对角线元素全为“0”的 01 矩阵。 ( ) 9、度数为奇数的结点个数为 0 个或 2 个的连通的无向图 G 可一笔画出。 ( ) 10、设 T 是有 n 个结点的完全二叉树,则 T 叶子数为(n+1)/2。 ( ) 二、填空题(每题 2 分,共 20 分) 1、P(,1) = _。 2、若集合 A=1, 2, 3上的二元关系 R1 和 R2 的
9、关系图如下所示, 则 R1oR2 = _,R2o R1= _。 3、用 P 和 PQ 同时代入合式公式 P(PQ)中的 P 和 Q,所得代换实例为 _。 4、设 F(x):x 是人,H(x,y):x 与 y 一样高,在一阶逻辑中,命题“人都不一样高” 的符号化形式为_。 5、若图 G 如下: 图 G 是_。 6、设为有理数集,笛卡尔积 S=QQ,*是 S 上的二元运算: (a, b) , (x, y)S , 有 (a, b)*(x, y)=(ax , y+b) ,则*运算的单位元为_,(a, b)S ,a0,则 (a, b)的逆元是 _。 7、无向图结点之间的连通性,是节点集之间一个_ 关系。
10、三、计算题 (共 20 分) 1、证明 A=1, 1关于数的乘法作成一个交换群。 2、证明:非平凡的树至少有两个叶子。 四、证明题 (每题 10 分,共 20 分) 1、.在一阶逻辑中,构造下面的证明:前提: ,F(a) 结论: 2、 设是群的子群, N=x|xG,xHx 1 =H,证明: 是的一个子群。 五、应用题 (每题 10 分,共 20 分) 1、现需涉及一个有 6 个元件的电路,把 6 个元件分成两组,每组 3 个元件,设计要求每组 中的任一个元件必须与另一组中的所有元件用导线连接。 问能否设计电路使导线交叉?如果 能,画出设计方案,如果不能,说明理由,并画出一个导线交叉最少的设计方案。 2、某案涉及甲、乙、丙、丁四个,根据已有线索,已知: (1) 若甲、乙均未作案,则丙、丁也均未作案; (2) 若丙、丁均未作案,则甲、乙也均未作案; (3) 若甲与乙同时作案,则丙与丁有一人且只有一人作案; (4) 若乙与丙同时作案,则甲与丁同时作案或同未作案。 办案人员由此得出结论:甲是作案者。这个结论是否正确?为什么?