离散数学期末考试题

成都理工大学20072008学年第一学期 离散数学考试试卷 大题 一二三四五六七八九总分 得分 一、填空题（本大题共10小题，每小题2分，共20分） 1. 解释（0，1）使命题公式 的真值为 。 2. 两个重言式的析取是_ 式，一个重言式和一个永 假式的合取式是_式。 3设p:小王走路,q:小王听音乐,在命题逻辑中，命题“小王边走路边听音 乐”的符号化形式为_。 4. 设 是火车， 是汽车， 比 快，则“火车都比汽车快”可符号化为 。 5. A上的等价关系R的定义是。 6. 设A=1，2，3，R=, 是A上的关系，则R满足下列性 质的哪几条：自反的，对称的，传递的，反自反的，反对称的。 。 7. 设Z是整数集，在Z上定义二元运算*为a*b=a+b+ab，其中+和是数的 加法和乘法，则代数系统的幺元是，零元是。 8. 若h是A=S，到A=S，的同态，则h（ab）=。 9. R，+，是环，则R，+是交换群，R，是。 10无向图G有16条边，有3个4度结点，4个3度结点，其余结点的度数 均小于3，则G至少有 个结点。 二、选择题（本大题共10小题，每小题1分，共10分） 1下列语句中，不是命题的有（ ）。 A. 5能被2整除。 B.太阳系以外的星球上有生物。 C. 现在开会吗？ D.小李在宿舍里。 2与谓词公式 PQ等价的公式是（ ）。 A. PQ B. PQ C. PQ D. PQ 3下述不是偏序集合的是（ ）。 AI， BR， C1，2，3，6 整除 D2，4，8，16，倍数 4设R为实数集，函数f：RR，f(x)=2x，则f是（ ）。 A满射函数 B单射函数 C双射函数 D非单射非满 5. 设个体域为整数，下列公式中真值为1的是( )。 Axy(x + y = 1); Bxy(x + y = 1); Cxy(x + y = 1); D xy(x + y = 1)。 6设集合X为人的全体，在X上定义关系R、S为R=|a，bXa 是b的父亲，S=|a，bXa是b的母亲，那么关系|a，b X a是b的祖母的表达式为（ ）。 AR S BR-1 S CS R DR S-1 7. 满足谓词P(x,y)：xy0的整数集Z上的二元关系具有（ ）性质？ A反自反、对称 B反对称、传递 C反对称 D自反、对称、传递 8. I为整数集，下列系统中不是代数系统的有（ ）。 A. B. C. D. 都不是 9任何图中必定有偶数个（ ）： A、度数为偶数的结点 B、入度为偶数的结点 C、度数为奇数的结点 D、出度为奇数的结点 10下列图形中为欧拉图的是（ ） 三、（本大题共10分） 求(PQ)(PQ)的主析取范式和主合取范式。 四、（本大题共10分） 用谓词推理理论来论证下述推证： 每个有理数都是实数,有的有理数是整数.因此,有的实数是整数。 五、（本大题共10分） 设 为群，任意a,b,cA, 证明 a*b=a*c，则 b=c。 六、（本大题共10分） 设R,， S,，分别是定义 为从AB和从BC的关系，其中ABC1,2,3,4。 求RS，SR，RR，SS。 七、（本大题共10分） 设A1，2，3，4，6，8，12，24，R为A上整除关系，试画 的哈斯图，并求A中的最大元，最小元，极大元，极小元。 八、（本大题共10分） 设无向图G=，V=v1，v2v6， E=v1v2,v1v3,v1v4,v2v5,v2v4,v2v3,