《离散数学模拟试卷 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） 若乙与丙同时作案，则甲与丁同时作案或同未作案。 办案人员由此得出结论：甲是作案者。这个结论是否正确？为什么？
