离散数学练习题.doc

判断题，选择题与填空题（80分）1.(12分) 下列等价关系和推理关系是否正确？ (1) P (P Q) Q (2) (P Q R) P Q R (3) P Q (P Q) (Q P) (4) (PQ) (PR) P(R Q) (5) x(P(x) Q(x) xP(x) x Q(x) (6) xP(x)$x Q(x) $x(P(x)$x Q(x) (7) $x(P(x) Q(x) xP(x) xQ(x) (8) $xyP(x,y) y$xP(x,y) (9) Q,(PQ) P (10) PQ,(Q R),R P (11) (PQ) (RS) (P R) (Q S) (12) (PQ) (RS) ( Q S) (P R) 2.(8分) 下列公式哪些是永真式（a），哪些是永假式（b），哪些是非永真式（c），哪些是可满足式（d）？(1) (P Q) (P R) ( P (Q R) (2) (PQ) ( QP) (3) x(P(x) P(x)$y (Q(y) Q(y) (4) xP(x)($x$y Q(x,y)x P(x) 3.(6分) 求标准（主）析取范式和标准（主）合取范式。(1) (PQ) 的标准析取范式是 ；(2) (PQ) 的标准合取范式是 ；(3) (P R) Q的标准合取范式是 。4.(4分) A、B、C、D是任意四个集合，下列等式是否成立？(1) A(BC)=(AB) (AC) (2) (AB)(BA)=(AB)(AB) (3) (AB)(CD)(AC)(BD) (4) (AB)(CD)(AC) (BD) 5.(14分) 设X1、2、3、4、5，R、和S、是X上的二元关系。(1) 逆关系RC为 ；(2) 复合关系RS为 ；(3) 自反闭包r(R)为 ；(4) 对称闭包s(R)为 ；(5) 传递闭包t(R)为 ；(6) 等价关系S的等价类为 。(7) 关系R是否是XX上的函数？ 6. (12分) 整数集合Z在加法下构成一个无限循环群Z,+，Gae、a、a2、a3、a16、a17是一个阶数为18的有限循环群。(1) 群Z,+中，30 ，3-1 ； (2) Z,+的所有生成元为 ；(3) G的所有生成元为 ； (4) 群G中，元a3和元a8的次数分别是 ； (5) G的所有非平凡子群为 ； (6) 上面(4)中元素个数为6的子群的所有左陪集为 。7. (10分) X2,3,4,6,12,18,36,48,54,108,144,432， 是整除关系(a b当且仅当b是a的倍数)。(1) 偏序集的极小元是 ，最小元是 ；(2) 偏序集的极大元是 ，最大元是 ；(3) 偏序集是否是格 ？ (4) 求X的一个6个元素的子集Y= ，使是格；(5) 求X的一个4个元素的子集Z= ，使是布尔代数。8.(14分) 下图中粗线表示的生成树。(1) 顶点子集2，3，4的度数为 ；(2) 图是否欧拉图？ (3) 图是否哈密尔顿图？ (4) 图中枝（，2）关于的基本割集为 ；(5) 图中弦（，7）关于的基本回路为 ；(6) 图的点连通度等于 ；(7) 图是否可平面图？ 证明题（20分）9.(10分) 设是一个群，是它的子群，定义集合G上的二元关系R|