《离散数学试题与答案试卷一》由会员分享，可在线阅读，更多相关《离散数学试题与答案试卷一（85页珍藏版）》请在金锄头文库上搜索。
1、0000离散数学试题与答案试卷一一、填空20%（每小题2 分）1设 A x | ( xN )且 ( x5), B x | x E 且 x7 （ N：自然数集， E+正偶数）则AB。2A ，B ， C 表示三个集合，文图中阴影部分的集合表达式为。AB3设 P，Q 的真值为0，R， S 的真值为1，则C(P(Q(RP)( RS) 的真值 =。4公式 ( PR)(SR)P 的主合取范式为。5若解释 I 的论域 D 仅包含一个元素，则xP( x)xP( x)在 I 下真值为。6设 A=1 ， 2，3， 4 ，A 上关系图为则 R2=。7设 A=a ， b，c， d ，其上偏序关系R 的哈斯图为则R=。
2、8图的补图为。9设 A=a ， b，c， d， A 上二元运算如下：-998880000*abcdaabcdbbcdaccdabddabc那么代数系统 的幺元是，有逆元的元素为，它们的逆元分别为。10下图所示的偏序集中，是格的为。二、选择 20%（每小题2 分）1、下列是真命题的有（）A a a；B , ；C, ；D 。2、下列集合中相等的有（）A 4，3；B，3，4 ；C4， ，3，3 ；D 3， 4。3、设 A=1 ，2， 3 ，则 A 上的二元关系有（）个。A23；B32；C 23 3； D 32 2。4、设 R，S 是集合 A 上的关系，则下列说法正确的是（）A 若 R， S 是自反的
3、，则 RS 是自反的；B 若 R， S 是反自反的，则 R S 是反自反的；C若 R， S 是对称的，则 RS 是对称的；D 若 R， S 是传递的，则 RS 是传递的。5、设 A=1 ，2， 3， 4 ， P（ A ）（A 的幂集）上规定二元系如下-998880000Rs,t | s,t p( A)(| s | | t | 则 P（A ） / R=（）A A； B P(A) ； C 1， 1 ， 2 ， 1 ，2， 3 ， 1 ， 2， 3， 4 ；D ，2 ， 2 ，3 ， 2 ， 3， 4 ， A6、设 A=，1 ，1，3，1， 2，3 则 A 上包含关系“”的哈斯图为（）7、下列函数是
4、双射的为（）A f : IE , f (x) = 2x；B f : NN N,f (n) = ；C f : RI , f (x) = x；D f :IN, f (x)= | x | 。（注： I整数集， E偶数集， N 自然数集， R实数集）8、图 中 从 v1 到 v3 长度为 3的通路有（）条。A 0；B1；C2；D3。9、下图中既不是Eular 图，也不是Hamilton 图的图是（）10、在一棵树中有7 片树叶， 3 个 3 度结点，其余都是4 度结点则该树有（）个 4度结点。A 1； B2；C3；D4 。三、证明26%-998880000、 R 是集合 X 上的一个自反关系，求证：R
5、 是对称和传递的，当且仅当 和 在 R 中有 在 R 中。（ 8 分）、 f 和 g 都是群 到 的同态映射， 证明 是 的一个子群。其中C= x | xG1且 f ( x) g ( x)(8 分)、 G=(|V| = v ， |E|=e ) 是每一个面至少由 k（ k3）条边围成的连通平面ek (v2)k2Peterson）图是非平面图。 （ 11 分）图，则， 由此证明彼得森图（四、逻辑推演16%用 CP 规则证明下题（每小题8 分）1、ABCD,DEFA F2、 x(P(x) Q( x)xP(x)xQ (x)五、计算18%1、设集合A=a ， b， c， d 上的关系R= , , , 用
6、矩阵运算求出 R 的传递闭包t (R) 。（9 分）2、如下图所示的赋权图表示某七个城市v1 , v2 , ,v7 及预先算出它们之间的一些直接通信线路造价， 试给出一个设计方案， 使得各城市之间能够通信而且总造价最小。（分）试卷一答案：一、填空20% （每小题 2 分）1、0 ，1，2，3，4，6 ； 2、( BC) A；3、1； 4、( P S R) ( PS R)；5、 1； 6、, , , ； 7、 ,IA ；8、-9988800009、 a ； a , b , c ,d ； a , d , c , d ； 10、 c;二、选择20%（每小题2 分）题目12345678910答案CDB
7、、CCADCADBA三、证明 26%1、 证：“”a, b, c X若 , R由 R对称性知, c, aR ，由 R 传递性得 R“”若 R ， R 有 R任 意a, b X， 因R 若 RR所以 R 是对称的。若 R ， R则 Rb, cRR即 R 是传递的。2、 证a, bC，有f (a)g( a), f (b) g(b)，又f (b 1 )f 1 (b) , g(b 1 )g 1 (b)f (b 1 )f 1 (b)g 1 (b)g(b 1 )f (a b 1 )f (a) *f 1 (b)g(a) * g (b 1 )g (a b 1 )a b 1C3、 证：是 的子群。r2e2ed(
8、 Fi ) rk设 G 有 rr个面，则i 1，即k 。而 v e r 2 故2 v e r v e2ek(v2)ke2 。（8 分）即得kek( v2)彼得森图为 k5, e15, v 10k2 不成立，这样-998880000所以彼得森图非平面图。（ 3 分）二、 逻辑推演16%1、 证明： A A BABCD C D D D E D E F F AF2、证明 xP (x) P( c)x(P( x)Q( x) P(c) Q(c) Q(c) xQ (x)xP (x)xQ(x)P（附加前提）T IPT IT IT IPT ICPP（附加前提）USPUST IUG CP三、 计算 18%1、 解：01001010M R1010MR2MRM R0101000100000000，000
