离散数学试卷二试题与答案

《离散数学试卷二试题与答案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、试卷二试题与答案一.填空1、设P：你努力，Q：你失败。2、“除非你努力，否则你将失败”的符号化为；3、"虽然你努力了，但还是失败了”的符号化为2、论域D={1,2）,指定谓词PP(l,l)P(l,2)P(2,1)P(2,2)TTFF贝恢式Vx3yP（y,x）真值为。3设A二{2,3,4,5,6}上的二元关系尺={<兀,）‘>1兀是质数},则R=（列举法）。R的关系矩阵Mr=4、设A={1,2,3）,则A上既不是对称的又不是反对称的关系R二A上既是对称的乂是反对称的关系R二5、设代数系统vA,*>,其中A={a,b,c},*abcaabcbbbccccb则

2、幺元是对称性。6.4阶群必是7、卜•而偏序格是分配格的是；是否有幕等性；是否有群或群。(A)（C）8、n个结点的无向完全图©的边数为,欧拉图的充要条件是二、选择1、在下述公式中是重言式为（）A.（PaQ）t（P/Q）；B.（P㈠Q）㈠（（PtQ）人（0TP））；c.~*（PtQ）八Q；d.Pt（PvQ）。），成真赋值的个数为（）。2、命题公式（「PtQ）t（-iQvP）屮极小项的个数为（A・0；B・1：C.2；D.3o3、设$={P{1}，{1，2}},则2s有（）个元素。A.3；B.6；C・7；D・8o4、设S={1,2,3},定义SxS上的等价关系

3、R={«a,b>,eSx5,gSxS,q+d=h+c}则山R产生的SxS上一个划分共有（）个分块。A・4；B・5；C・6；D・9。5、设S={h2,3},s上关系R的关系图为则R具有（）性质。A.自反性、对称性、传递性；B.反自反性、反对称性；C.反自反性、反对称性、传递性；D.自反性。6、设+，。为普通加法和乘法，贝U（）是域。AS=[xx=a+Z?V3,a,beQ}BS={xx=2n,a,bEZ}8.在如下的有向图中，从V]到V4长度为A.1；）欧拉图。9、在如下各图中（[BJ[D)10、1()、设R

4、是实数集合，“x”为普通乘法，则代数系统是()。A.群；B.独异点；C.半群。三、证明1、设R是A上一个二元关系，5={1(a,beA)a(对于某一个cw4,有va.c>g/?且g/?)}试证明若R是A上一个等价关系，则S也是A上的一个等价关系。2、用逻辑推理证明：所有的舞蹈者祁很有风度，王华是个学生且是个舞蹈者。因此有些学生很有风度。3、若无向图GP只冇两个奇数度结点，则这两个结点一定连通。m=—(h—1)(/1—2)+24、设G是具有n个结点的无向简单图，其边数2，则G是HamiltonSo四、计算1、1、设A={1,2

5、,3,4),S={{1),{2,3},(4)),为A的一个分划,求由S导岀的等价关系。(4分)2、设z为整数集，关系R={a.heZA.a=h(nodk)}为z上等价关系，求R的模K等价关系的商集Z/R,并指出R有秩。(5分)3、设A={1,2,3,4,5},A上的偏序关系为求A的子集{3,4,5}和{1,2,3},的上界，下界，上确界和下确界。(6分)4、权数1,4,9,625,36,49,64,81,100构造一棵最优二叉树。试卷二参考答案：一、填空]、一iPtQ；2、T3、R={v2,2>,v2,3>,v2,4>,v2,5>,v2,6

6、>,v3,2>,v3,3>,v3,4>,v3,5>,v3,6>,v4,5>,v4,6>,<5,2>,<5,3>,<5,4>,<5,5>,<5,6>}；"11111、111110001111111,00000丿4、R={vl,2>,vl,3>,v2」>}；R={<1,1>,<2,2>,<3,3>)5、a；否；有6、Klein四元群;循环群7、B—n{n-1)8、2；图中无奇度结点且连通二、选择题目12345678910答案B、DD；DDBDABBBB、C三、证明1、(1)S自反的VqwA,由r自反，・・・(va,a>w/?)人(wR),/.

7、,a>eS(2)S对称的/a,heAg5=>(gR)a(gR)…S定义=>(gR)a(g/?)…R对称=>gS•••/?传递(3)S传递的Vf7,Z?,CGA6SaeS=>(vo,d>€R)a(GR)a(€R)a(GR)=>(eR)a(eR)・・R传递=^>eS…S定义由(1)、(2)>(3)得;S是等价关系。2>证明：设P(x)：x是个舞蹈者：Q(x):x很有风度；S(x)：x是个学生；a：王华上述句子符号化为

8、：前提：VHPgTQd))、S(a)/P(a)结论.3x(S(x)a0(x))