离散数学(三).doc

一、判断题 1、偏序集合的哈斯图一定是连通图（错） 2、任意一个谓词公式都与一个前束范式等到价。（对） 3、设R是非空集合A上的关系，R在A上是传递的，当且仅当R 4、若有向图D是强连通，则D必为欧拉图。 5、设R是集合A上的传递关系，则R是传递的. 6、设A*、Ｂ*分别是命题公式Ａ和Ｂ的对偶式，若ＡＢ，则Ａ*Ｂ*　 7、在推理中：“如果你上课用心听讲，那么你考试及格：你上课不用心听讲，所以你考试不及格”，中的结论是有效的 8、Ａ、Ｂ为集合，Ａ-B=A当且仅当Ｂ＝Φ 9、若Ａ、Ｂ为集合，当Ａ∪Ｂ＝Ａ∪C且Ａ∩Ｂ＝Ａ∩Ｃ时，则Ｂ＝Ｃ 11、集合Ａ上的恒等关系，IA是对称的反对称的. 12、可数个可数集的并一定是可数的 13、在推理“如果我参加马拉松赛，那么我很疲劳；但我不疲劳，所以我没有参加比赛中，结论是有效的 14、A、Ｂ是非空集合，若｛Ａ－Ｂ，Ｂ－Ａ｝是集合，Ａ∪Ｂ的一个划分，则Ａ∩Ｂ＝Φ 15、设Ａ，Ｂ分别是命题公式Ａ、Ｂ的对偶式，若ＡＢ，则ＡＢ 16、Ｒ、Ｓ是Ａ上的二元关系，若Ｒ和Ｓ是自反的，则ＲS也是自反的 17、设Ａ是集合，Ｐ（Ａ）Ｐ（Ａ） 18、偏序集合的哈斯图一定是连通图 19、若Ｒ１Ｒ２是非空集合Ａ上的等价关系，则Ｒ１Ｒ2也是Ａ上的等价关系 20、若Ｒ、Ｓ是Ａ上的二元系，若Ｒ和Ｓ是对称的，则RS也是对称的 21、设Ｒ、Ｓ是集合Ａ上的关系，若Ｒ和Ｓ是传递的，则Ｒ∩Ｓ是传递 22、设Ａ*是命题公式Ａ的对偶式，则（Ａ*）*＝Ａ 23、不是自反的关系一定是反自反的 24、集合（0，1），０）是等势的。 25、设A, 是偏序集，BA，若bB是B的最小元，则b是B的极小元，下界，下确界。 26、若有向图Ｄ是欧拉图，则Ｄ必是强连通图 27、设A, 是偏序集，BA，，则a是B的上确界，且aB，则a是B的最大元。 则a是B的极大元、上界、上确界。 28、设A, 是偏序集，BA，若bB是B的最大元，b是B的极大元，上界，上确界。 29、设Ｒ是Ａ上的二元系，若Ｒ是对称的，则r(R),t(R)也是对称的 30、若图Ｇ中恰有两个奇度数结点，则这两个结点是连通的。 31、若集合Ａ上的关系Ｒ是对称的，则Ｒ的逆关系Ｒ-1也是对称的 32、若Ｒ和Ｓ是集合Ａ上的两对称关系，则RS也是对称的。 33、设Ｒ和Ｓ是集合Ａ上的关系，Ｒ和Ｓ是传递的，则Ｒ∪Ｓ是传递。 34、对于代数系统Ｒ，*,Ｒ是实数集合，＊是普通乘法运算，则每个元素均有逆元 35、若Ｒ和Ｓ是集合Ａ上的两传递关系，则RS也是传递的。 36、设R和S是集合A上的等价关系，则R∪S一定是等介的。 37、设R、S是集合A的关系，由s(R∪S)=s(R)∪s(S) 38、设R、S是集合A的关系，由s(R∪S)=r(R)∪r(S) 39、任意一个谓词公式都与一个前束范式等价。 40、若无向图中恰有两个度为奇数的结点，则这两个结点必连能。 41、在有向图中，结点间的可达关系是等价关系。 42、若图G不连通，则G必连通。 二、选择题 1.对任意集合A,B,C下属正确的是：A.若A∈B,BC则A∈C 2.设A-B=Φ,则有:C.AB 3.设A={{1,2,3},{4,5},{6,7,8}}则有:C.{{4，5}}A 4.设A={a,{a}}下列选项错误的是: B. {a}P(A) 5.集合A={1,2,.,10 }上的关系R={x,y︱∈A} 则R有性质: B.对称的 6.设A={a,b,c},B={1,2},f:AB,则不同的函数个数为：B.个 7.函数的复合满足:B.结合律 8.为满射,则必是： C. 满射 9.若是满射则:C.g是满射 10.Z是整数集合,f定义为z→z则:A.单射 公倍数 12.任何无向图中结点间的连通关系是: B.等价关系 13.设是强连通图，当且仅当：D. D中有通过美各界的至少一次的回路 三、填空题 6.集合A的基数为m，则其幂集P(A)的基数为: 7.一棵树上有两个结点度数为2，一个基点度数为3，三个结点度数为4,度数为1的结点有 9个. 8.R是集合A上的等价关系则对任一元素a∈A,由a形成R等价类={x︱∈A,aRx} 四、证明下列各题 3.证明:对于任意集合A,B,C，(A∩ B)∪C=A∩(B∪C)的充要条件是CA. 证:∈C,则x∈(A∩B)∪Cx∈A∩(B∪C)x∈A 即CA 若CA,则(A∩B)∪C=(A∪C)∩(B∪C) = A∩(B∪C) ∴结论成立。 5.若A∩B≠Φ,证明: 证: (1) (2)同理可证： .6.若A∩B≠Φ,证明: 证: 7.设R.S.T均为A上的二次关系， 证明 证: 8.设A.B.C是集合,证明: 证: 9.A,B为任意集合,证明: (1) (1) 证:(1) (2) 11.设R是A上的关系,