离散试题练习

失散试题练习1.求以下各公式的主析取范式和主合取范式：(P-Q)R(PR)(QR)-P2.证明：—Q_QR,_R,_SP=>_SL(B—C),C^(—DE)，—F—(D一E),A=>B—FPQ,P—R,Q—S=>RS3.设A二{1,2,,10}。以下哪个是A的区分？假如区分，贝陀们引诱的等价关系是什么？B={{1,3,6},{2,8,10},{4,5,7}};C={{1,5,7},{2,4,8,9},{3,5,6,10}};D={{1,2,7},{3,5,10},{4,6,8},{9}}4.R是A二{1,234,5,6}上的等价关系，R=IA-{<1,5>,<5,1>,<2,4>,<4,2>,<3,6>,<6,3>}求R引诱的区分5.设＜G,?＞是群，a,b?G,a=e，且a4?b=b?a5。试证a?b=b?a6.I上的二元运算*在I上；圭寸闭定义为：-a,b?I,a*b=a+b-2。试证：＜1,*＞为群。x(P(x)Q(x))二-xP(x)xQ(x)7.证明在有n个结点的树中，其结点度数之和是2n-28.设T=＜V,E＞M一棵树，若|V|＞1,则T中起码存在两片树叶。9.已知一棵无向树中有2个2度极点、1个3度极点、3个4度极点，其他极点度数都为1。问它有多少个1度极点？10.求循环群C12={e,a,a：,a11}中H={e,a：a8}的全部右陪集。11.设半群＜S,?＞中消去律建立，则＜S,?＞是可互换半群当且仅当222-a,bS,(a?b)=a?b12.设*是会合A上可联合的二元运算，且-a,b?A,若a*b=b*a，贝Ua=b;证明：-aA,a*a=a，即a是等幕元-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、以以下图所示的赋权图表示某七个城市VZ；W及早先算出它们之间的一些直接通讯线路造价，试给出一个设计方案，使得各城市之间可以通讯用真值表法证明P「Q=(P>Q)(Q>P)用先求主范式的方法证明(P-Q)(P-R)=(PT(QR)一次会议有20人参加，此中每一个人都在此中有不下10个朋友。这人围成一圆桌出席。有没有可能使随意相邻而坐的两个人都是朋友？为何？为庆贺九七香港回归祖国，四支足球队进行竞赛，已知状况以下，问结论能否有效？前提：(1)若A队得第一，则B队或C队获亚军；(2)若C队获亚军，则A队不可以获冠军；⑶若D队获亚军，则B队不可以获亚军；A队获第一；结论：(5)D队不是亚军。1.当每个结点的度数大于等于3时，不存在有7条边的简单连通平面图n-k+m=2d(v)>=n/2权数2，3，5，7，8结构一棵最优二叉树八.*①3.会合A={a,b}B=,计算AXP(B)设A={a,{a}}，以下命题错误的选项是( )。(1){a}P(A)(2){a}P(A)(3){{a}}P(A)(4){{a}}P(A)在0( )门之间写上正确的符号。(1)=(2)(3)(4)若会合S的基数|S|=5，则S的幕集的基数|P(S)|=( )。以下各会合中，哪几个分别相等( )。(1)A1={a,b}(2)A2={b,a}(3)A3={a,b,a}⑷A4={a,b,c}(5)A5二{x|(x-a)(x-b)(x-c)=O}(6)A6={x|x-(a+b)x+ab=O}设A={1,2,3,4,5,6},B={1,2,3}，从A到B的关系R={〈x,y>|x=y2},求(1)R⑵R-1举出会合A上的既是等价关系又是偏序关系的一个例子。（）会合A上的等价关系的三个性质是什么？（）会合A上的偏序关系的三个性质是什么？（）设S={1,2,3,4},A上的关系只={〈1,2〉〈〈2,1>2,3>,〈3,4>}求（1）RR（2）R-1设A={2,4,6},A上的二元运算*定义为：a*b=max{a,b}，则在独异点＜A,*＞中，单位元是( )，零元是( )。设A={3,6,9}，A上的二元运算*定义设〈G,*〉是一个群，则⑴若a,b,x?G,a*x=b,则x=( );(2)若a,b,x?Ga*x=a*b,则x=( )设G是一个哈密尔顿图，则G必定是( )。(1)欧拉图(2)树(3)平面图(4)连通图设G是一棵树，则G的生成树有( )棵。(1)0(2)1(3)