离散试题练习

1、离散试题练习1.求下列各公式的主析取范式和主合取范式：Q)R (PP(QR)(PR) 证明：2.SSP=>, QQRR F D(E), F E),A=>B(D, A(B C)CSR, Q S => RQP, P列哪个是 的的划分？若是划分，则它们诱导AA二1,2,3.设,10 等价关系是什么？ 5,7; 1 ）（5,6,10;（2） （4.R 是 A=1,2,3,4,5,6 上的等价关系，R=I<1,5>,<5,1>,<2,4>,<4,2>,<3,6>,<6,3>A求R诱导的划分45。6.vl.试证 a

2、bab aG, ae,且 a b=b a,b5.设G, 是群，I上的二元运算*在I上；圭寸闭定义为：a,bl , a*b=a+b-2。试 证:、为群。x(P(x) Q(x) xP(x) xQ(x)7. 证明在有 n 个结点的树中，其结点度数之和是 2n-28. 设T=V,E是一棵树，若|V|1，则T中至少存在两片树叶。9. 已知一棵无向树中有 2个2度顶点、1 个 3度顶点、3个4度顶点， 其余顶点度数都为 1 。问它有多少个 1 度顶点？21148的所有右陪集。H=e,a中=e,a,a 10.求循环群C,a,a 12II.设半群S, 中消去律成立，则S, 是可交换半群当且仅当222, b=a

3、ba () a,bS若 A,a,b，且的二元运算上12.设*是集合A可结合a=b;a*b=b*a ，则证明：（1）aA,a*a=a，即 a 是等幕元 （2）a,bA,a*b*a=a;13.设集合A= a ,b , c , d 上关系R=< a,b > , < b , a > , < b , c > , < c , d >要求1、写出R的关系矩阵和关系图。（4分）2 、用矩阵运算求出R的传递闭包。（6 分）14、如下图所示的赋权图表示某七个城市V，V，V127及预先算出它们之间的一些直接通信 线路造价，试给出一个设计方案，使得各城 市之间能够通信（

4、9分）而且总造价最/小。v517)Q ( PQ ( PQ)用真值表法证明P) R(Pt(Q(P用先求主范式的方法证明(P f Q)tR)个朋友。这 10 一次会议有 20 人参加，其中每个人都在其中有不下人 围成一圆桌入席。有没有可能使任意相邻而坐的两个人都是朋 20 友？ 为什么？问四支足球队进行比赛， 已知情况如下， 为庆祝九七香港回归祖国， ? 结论是否有效 ;队获亚军B队或C若前提：(1) A队得第一，则；队不能获冠军队获亚军，则 若 CA(2);队不能获亚军B队获亚军，则D若.(4) A 队获第一 ； 结论 ： (5) D 队不是亚军1.当每个结点的度数大于等于3时，不存在有7条边的

5、简单连通平面图n-k+m=2d(v)>=n/22. 权数 2，3， 5， 7，8 构造一棵最优二叉树列命题错在0若集合 SA二a,b B=3. 集合)(BA X P,计算设 A二a,a, 误的是( )。(1) aP(A) (2) aP(A) (3) aP(A) (4) aP(A)( )之间写上正确的符号。 (1) = (2) (3) (4) 的基数|S|=5，则S的幕集的基数|P(S)|=()。 下列各集合中，哪几个分别相等 ()。(1) A1=a,b (2) A2=b,a (3) A3=a,b,a (4) A4=a,b,c2-(a+b)x+ab=0(5) A5=x|(x-a)(x-b)

6、(x-c)=0(6)A6=x|x设A= 1,2,3,4,5,6, B二1,2,3，从A到 B的关系R=x,y >2-1,求 |x=y(1)R (2) R 举出集合 A 上的既是等价关系又是偏序关系的一个例子。 ( ) 集合 A 上的等价关系的三个性质是什么？ ()集合 A 上的偏序关系的三个性质是什么？ ()设 S= 1 , 2 , 3 , 4 ，人上的关系R= 1,2 2,1 2,3 3,4-1 R (2) R(1)R 求设A=2,4,6 , A上的二元运算*定义为： a*b=maxa,b，则在独异点A,*中，单位 兀是（），零兀是（）。设 A=3,6,9 ，A 上的二元运算 *定义设G,*是一个群，则若 a,b,x G ax=b,则 x=( ); *x=()b ，则 x=a G a(2) 若 a,b,x* ( )。g是一个哈密尔顿图，则G一定是设 连通图(3)平面图(4) (2)(1) 欧拉图树棵。的生成树有()设G是一棵树，则G(4) 不能确定 (2) 1