离散数学练习题 (2).doc

《离散数学练习题 (2).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、判断题，选择题与填空题（80分）1.(12分)下列等价关系和推理关系是否正确？(1)P(PQ)Q[](2)┐(PQR)┐P┐Q┐R[](3)PQ(┐PQ)(┐QP)[](4)(P→Q)(P→R)P→(RQ)[](5)"x(P(x)Q(x))"xP(x)"xQ(x))[](6)"xP(x)→$xQ(x))$x(P(x)→$xQ(x))[](7)┐$x(P(x)Q(x))"x┐P(x)"x┐Q(x)[](8)$x"yP(x,y)"y$xP(x,y)[](9)┐Q,(P→Q)┐P[](10)P→Q,┐(QR),RP[](11

2、)(P→Q)(R→S)(PR)(QS)[](12)(P→Q)(R→S)(┐Q┐S)(┐P┐R)[]2.(8分)下列公式哪些是永真式（a），哪些是永假式（b），哪些是非永真式（c），哪些是可满足式（d）？(1)((PQ)(PR))(P(QR))[](2)((┐P→Q)→(Q→P))[](3)"x(P(x)→P(x))→$y(Q(y)┐Q(y))[](4)"xP(x)→($x$yQ(x,y)→"xP(x))[]3.(6分)求标准（主）析取范式和标准（主）合取范式。(1)┐(P→Q)的标准析取范式是；(2)┐(P→Q)的标准

3、合取范式是；(3)(┐PR)→Q的标准合取范式是。4.(4分)A、B、C、D是任意四个集合，下列等式是否成立？(1)A－(B∪C)=(A－B)∩(A－C)[](2)(A－B)∪(B－A)=(A∪B)－(A∩B)[](3)(A－B)×(C－D)＝(A×C)－(B×D)[](4)(A∩B)×(C∩D)＝(A×C)∩(B×D)[]5.(14分)设X＝{1、2、3、4、5}，R＝{<1，2>、<2，3>、<3，4>}和S＝{<1，1>、<2，2>、<3，3>、<4，4>、<5，5>、<4，2>、<2，4>、<1，3>、<3，1

4、>}是X上的二元关系。(1)逆关系RC为；(2)复合关系RοS为；(3)自反闭包r(R)为；(4)对称闭包s(R)为；(5)传递闭包t(R)为；(6)等价关系S的等价类为。(7)关系R是否是X→X上的函数？[]6.(12分)整数集合Z在加法下构成一个无限循环群﹤Z,+﹥，G＝﹤a﹥＝{e、a、a2、a3、……、a16、a17}是一个阶数为18的有限循环群。(1)群﹤Z,+﹥中，30＝，3-1＝；(2)﹤Z,+﹥的所有生成元为；(3)G的所有生成元为；(4)群G中，元a3和元a8的次数分别是；(5)G的所有非平凡子群为；

5、(6)上面(4)中元素个数为6的子群的所有左陪集为。7.(10分)X＝{2,3,4,6,12,18,36,48,54,108,144,432}，是整除关系(ab当且仅当b是a的倍数)。(1)偏序集的极小元是，最小元是；(2)偏序集的极大元是，最大元是；(3)偏序集是否是格？[](4)求X的一个6个元素的子集Y=，使是格；(5)求X的一个4个元素的子集Z=，使是布尔代数。8.(14分)下图Ｇ中粗线表示Ｇ的生成树Ｔ。(1)顶点子集{ｖ2，ｖ3，ｖ4}的度数为；(2)图Ｇ是否欧拉图？[

6、](3)图Ｇ是否哈密尔顿图？[](4)图Ｇ中枝ｅ２＝（ｖ１，ｖ2）关于Ｔ的基本割集为；(5)图Ｇ中弦ｅ１０＝（ｖ５，ｖ7）关于Ｔ的基本回路为；(6)图Ｇ的点连通度等于；(7)图Ｇ是否可平面图？[]证明题（20分）9.(10分)设是一个群，是它的子群，定义集合G上的二元关系R＝{

7、aGbGa*b-1H},证明：关系R是等价关系，且。10.(10分)设G是一个(p，q)图，证明：G是树当且仅当G连通且q＝p－1。