1、离散数学试题 E参考答案一、填空题(每空4分，共20分)1.设p: 天下雨，q: 天刮风，r: 我去书店，则命题“如果天不下雨并且不刮风，我就去书店”的符号化形式为_(pq)r_。2.设F(x): x是人，G(x): x用右手写字，命题“有的人并不用右手写字”在谓词逻辑中符号化的形式为_$x(F(x)G(x)_。3. 以1，1，1，1，2，2，4为无向树的度数列，可以生成_2_棵非同构的无向树。4. 设A=a,b,c ，则A上共有_5_个不同的等价关系。5. 设A=1, 2, 3，在A上定义二元运算如下：x,yA, x*y=minx,y,则*的运算表为*123111121223123二、计算题
2、(共50分)1.求(qp)pr的主析取范式（写出过程）。（8分）解：(qp)pr(qp)pr(qpr)(ppr)(pqr)(pr) 4分(pqr)(pr)(qq)(pqr)(pqr)(pqr)(pqr)(pqr) 8分2.已知无向图G有11条边，2度与3度结点各2个，其余都是4度结点，求G中共有几个结点。（写出过程）（8分）解：设有x个4度结点,则有握手定理有4x+2(2+3)=211解得：x=3答：图G中共有7个结点。12341125图11234112523468图6123411252图21234112523图3123411252346图51234112523图441234112523468
3、图7123411252346811图812341125234681911图93.求一棵带权为1，1，1，2，2，3，4，5的最优二元树T，并计算W(T)。(8分)解：解题过程如上图图1图9。W(T)=4.设二元关系R=,求：(9分) domR ranR 解： domR=a,b,c; ranR= a,b,c; =,=, =,5. (9分)设A=a, b, c, d, e, f,则R是A上的等价关系,其中 (1)求a的等价类；(2)求c的等价类 ；(3)求商集A/R。解：(1)=a,b;(2) =c,d,e;(3) 商集.6. 设为非零实数集。以下各式右边的运算为普通的四则运算。（8分）(1) a
4、,b, ；(2) a,b,；(3) a,b, 。试确定以集合与以上三个二元运算构成的三个代数系统中哪些是群，是群的求其单位元，及每个元素的逆元。解：只有代数系统是群。群单位元是1。对于任何的，则a逆元是。四、证明题(共30分)1. (8分)在命题逻辑构造下面推理的形式证明：前提：；结论：。证明：编号 公式 根据 r P qr P q T析取三段论 pq P p T拒取式2. (7分)设A、B为二集合，已知，证明：。其中，P(A), P(B)分别为A与B的幂集。证明：xP(A), 由幂集的定义则xA；又由于，则xB;再由幂集的定义则xP(B)。因此，。3. (8分) 设R是集合A上的关系，证明R是A上的传递关系的充分必要条件是。证明：必要性（）。任取，由的定义则存在，使得，而R是A上的传递关系，所以，故。充分性（）。，若，则；又因为，则，因此，R是A上的传递关系。4设是布尔代数。若。证明ab。（7分）证明：因为 （同一律）= （已知） （分配律） （互补律） （同一律）所以，ab。7
