离散数学17.doc

常熟理工学院20 ~20 学年第学期
《离散数学》考试试卷(试卷库17卷)
试题总分: 100 分考试时限:120 分钟
题号
一
二
三
四
五
总分
阅卷人
得分
一、选择题(每题2分,共20分)
下列各命题中真值为真的命题有( )
(A)2+2=4当且仅当3是奇数(B)2+2=4当且仅当3不是奇数
(C)2+2≠4当且仅当3是奇数(D)2+2=4仅当3不是奇数
G=,其中,为集合对称差运算,则方程{1,2} x ={1,3}的解为( )
(A) (B) (C) (D)
设P={x|(x+1)4且xR},Q={x|5x+16且xR},则下列命题哪个正确( )
(A)QP (B)QP (C)PQ (D)P=Q
具有如下定义的代数系统,( )不构成群
(A),*是模11乘(B),*是模11乘
(C)(有理数集),*是普通加法(D)(有理数集),*是普通乘法
在如下各图中( )是欧拉图
下面给出的集合中,( )是前缀码
(A){0,10,110,101111} (B){1,11,101,001,0011}
(C){b,c,aa,ab,aba} (D){01,001,000,1}
下面联结词不具有交换律的是( )。
(A) (B) (C) (D)D
G=是强连通图,设|V|>1,当且仅当( )
(A) G中至少有一条通路(B) G中至少有一条回路
(C) G中有通过每个结点至少一次的回路(D) G中有通过每个结点至少一次的通路。
命题公式A与B是等价的,是指( )
(A) A和B有相同的原子变元。(B)A和B具有相同的真值
(C)A和B是可满足的(D)当A的真值为真时,B的真值也为真。
Z是整数集合,对于下列*运算,哪个代数系统是半群( )
(A) (B) (C) (D)
二、填空题(每题2分,共20分)
设,,请在下列每对集合中填入适当的符号:
(1) (2) 。
设R为集合A上的等价关系,对,集合= ,
称为元素a形成的R等价类,则,因为。
由n个命题变元组成的不等价的命题公式共有种。
设为偏序集,BÍA,若存在yÎB,使得,则称y为B的最大元。
如果个体域D={2,3},则消去全称量词"x后,("x)A(x) Û 。
设代数系统,其中A={a,b,c}
*
a b c
a
b
c
a b c
b b c
c c b
则幺元是;是否有等幂性。
A和B的笛卡尔积或直积的定义为:A´B={ }。
设r是集合A上的相容关系,若CÍA ,如果,称C是由相容关系r产生的相容类。
设是群的一个子群,如果G是有限群,|G|=n,|H|=m,则m和n的关系是。
在带权的图G的所有生成树中, 称作最小生成树。
三、判断题(每题1分,共10分)
("x)(F(y) →G(x)) Û F(y) →("x)G(x)。( )
,若,则必须( )
自然数集合与有理数集合