《离散数学试题与答案试卷一》由会员分享，可在线阅读，更多相关《离散数学试题与答案试卷一（6页珍藏版）》请在金锄头文库上搜索。
1、离散数学试题与答案试卷一 - 教育文库 离散数学试题与答案试卷一 一、填空 20% （每小题2分） 1设 A?x|(x?N)且(x?5),B?x|x?E且x?7（N：自然数集，E+ 正偶数） 则 A?B? 。 2A，B，C表示三个集合，文图中阴影部分的集合表达式为 。 3设P，Q 的真值为0，R，S的真值为1，则 A B C ?(P?(Q?(R?P)?(R?S)的真值= 。 4公式(P?R)?(S?R)?P的主合取范式为 。 5若解释I的论域D仅包含一个元素，则 ?xP(x)?xP(x) 在I下真值为 。 6设A=1，2，3，4，A上关系图为 则 R2 = 。 7设A=a，b，c，d，其上偏序
2、关系R的哈斯图为 则 R= 。 8图的补图为 。 9设A=a，b，c，d ，A上二元运算如下： * a b c d a b c d a b c d b c d a c d a b d a b c 那么代数系统的幺元是 ，有逆元的元素为 ，它们的逆元分别为 。 10下图所示的偏序集中，是格的为 。 二、选择 20% （每小题 2分） 1、下列是真命题的有（ ） A a?a； B?,?； C ?,?； D ?。 2、下列集合中相等的有（ ） A4，3?；B?，3，4；C4，?，3，3；D 3，4。 3、设A=1，2，3，则A上的二元关系有（ ）个。 A 23 ； B 32 ； C 23?32?2；
3、 D 3。 4、设R，S是集合A上的关系，则下列说法正确的是（ ） A若R，S 是自反的， 则R?S是自反的； B若R，S 是反自反的， 则R?S是反自反的； C若R，S 是对称的， 则R?S是对称的； D若R，S 是传递的， 则R?S是传递的。 5、设A=1，2，3，4，P（A）（A的幂集）上规定二元系如下 R?s,t?|s,t?p(A)?(|s|?|t|则P（A）/ R=（ ） AA ；BP(A) ；C1，1，2，1，2，3，1，2，3，4； D?，2，2，3，2，3，4，A 6、设A=?，1，1，3，1，2，3则A上包含关系“?”的哈斯图为（ ） 7、下列函数是双射的为（ ） Af :
4、I?E , f (x) = 2x ； Bf : N?N?N, f (n) = ； Cf : R?I , f (x) = x ； Df :I?N, f (x) = | x | 。 （注：I整数集，E偶数集， N自然数集，R实数集） 8、图 中 从v1到v3长度为3 的通路有（ ）条。 A 0； B 1； C 2； D 3。 9、下图中既不是Eular图，也不是Hamilton图的图是（ ） 10、在一棵树中有7片树叶，3个3度结点，其余都是4度结点则该树有（ ）个4度结点。 A1； B2； C3； D4 。 三、证明 26% 、R是集合X上的一个自反关系，求证：R是对称和传递的，当且仅当 和在R
5、中有在R中。（8分） 、f和g都是群到的同态映射，证明是的一个子群。其中C=x|x?G1且f(x)?g(x) (8分) 、G= (|V| = v，|E|=e ) 是每一个面至少由k（k?3）条边围成的连通平面图，则 e?k(v?2)k?2， 由此证明彼得森图（Peterson）图是非平面图。（11分） 四、逻辑推演 16% 用CP规则证明下题（每小题 8分） 1、A?B?C?D,D?E?F?A?F 2、?x(P(x)?Q(x)?xP(x)?xQ(x) 五、计算 18% 1、设集合A=a，b，c，d上的关系R= , , , 用矩阵运算求出R的传递闭包t (R)。 （9分） 2、如下图所示的赋权图
6、表示某七个城市v1,v2,?,v7及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。 （分） 试卷二试题与答案 一、填空 20% （每小题2分） 1、 P：你努力，Q：你失败。“除非你努力，否则你将失败”的翻译为 ；“虽然你努力了，但还是失败了”的翻译为 。 2、论域D=1，2，指定谓词P P (1,1) T P (1,2) T P (2,1) F P (2,2) F 则公式?x?yP(y,x)真值为 。 2、 设S=a1 ，a2 ，a8，Bi是S的子集，则由B31所表达的子集是 。 3、 设A=2，3，4，5，6上的二元关系R?x,y?|x?
7、y?x是质数，则R= （列举法）。 R的关系矩阵MR= 。 5、设A=1，2，3，则A上既不是对称的又不是反对称的关系R= ；A上既是对称的又是反对称的关系R= 。 6、设代数系统，其中A=a，b，c, * a b c a b c a b c b b c c c b 则幺元是 ；是否有幂等 性 ；是否有对称性 。 7、4阶群必是 群或 群。 8、下面偏序格是分配格的是 。 9、n个结点的无向完全图Kn的边数为 ，欧拉图的充要条件是 。 10、公式(P?(?P?Q)?(?P?Q)?R的根树表示为 。 二、选择 20% （每小题2分） 1、在下述公式中是重言式为（ ） A(P?Q)?(P?Q)；B(P?Q)?(P?Q)?(Q?P)； 第 页 共 页
