发布时间 : 星期三 文章(完整word版)离散数学期末考试题(附答案和含解析3)更新完毕开始阅读65d92220f7335a8102d276a20029bd64793e626d
一、单项选择题
2.设集合A={1，2，3}，下列关系R中不是等价关系的是（ D ） ．A.R={<1,1>,<2,2>,<3,3>}； B.R={<1,1>,<2,2>,<3,3>,<3,2>,<2,3>}； C. R={<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>}； D. R={<1,1>,<2,2>,<3,3>,<1,2 >}. 3．在公式（?
x）F（x，y）→（? y）G（x，y）中变元x是（ B ）
A．自由变元；(前面无?或?量词) B．既是自由变元，又是约束变元； C．约束变元；(前面有?或?量词) D．既不是自由变元，又不是约束变元. 4．设A={{1，2，3}，{4，5}，{6，7，8}}，下列选项正确的是（ C ） A．1∈A； B．{1，2，3}?A； C．{{4，5}}?A； D．?∈A. 5.设论域为{l，2}，与公式(?x)A(x)等价的是( A )
A.A(1)?A(2)； B. A(1)?A(2)； C.A(1)∧A(2)； D. A(2)?A(1).
6.一棵树有5个3度结点，2个2度结点，其它的都是l度结点，那么这棵树的结点数是( B ) A.13 ； B.14 ； C.16 ； D.17 . //设一度结点数为n,则有：5×3+2×2+n=2[(5+2+n)-1] 解得：n=7, 所以这棵树的结点数为：m=5+2+7=14. 7．设A是偶数集合，下列说法正确的是（ A ） A．
8．下列图是欧拉图的是（ D ）
B．
D．
10.下面不满足结合律的运算是( C ) ．．．(a?A.a?b?min(a,b)； B.a?b?max(a,b)； C.a?b?2二、填空题
b)；D.a?b?2ab
12.设f∶R→R,f(x)=x+3,g∶R→R,g(x)=2x+1,则复合函数(f?g)(x)? 2x?4 ,
(g?f)(x)?2x?7
//(f?g)(x)?f(g(x))=f(2x+1)=(2x+1)+3=2x+4 //(g?f)(x)?=g(f(x))=g(x+3)=2(x+3)+1=2x+7
1
//备注：f?g=f?g(x)=g(f(x))
13．设S是非空有限集，代数系统
对∪运算的单位元是
?，零元是 S 。
14．设
{3} , ran(A∪B)= {2,3,4,5} //关系R的定义域：domR={?x|y(
17. 在根树中，若每一个结点的出度 最多为（或≤）m,则称这棵树为m叉树。如果每一个结点的出度 都为（或=）m或0，则称这棵树为完全m叉树。如果这棵树的叶 都在同一层 ，那么称为正则m叉树。 18． y?(x?y)modn，则在 ?>中，1的阶是 6 ，4的阶是 3 。 //单位元是e=0 19. n点完全图记为Kn，那么当 n ≤ 4 时，Kn是平面图，当 n ≥ 5 时，Kn是非平面图。 20. 若图中存在 回路 ，它经过图中所有的结点恰好 一次 ，则称该图为汉密尔顿图(哈密顿图) 。 // 欧拉图 三、计算题 21. 求命题公式(?P?Q)?(?Q?P)的主析取范式。 解： (?P?Q)?(?Q?P)?(P?Q)?(?Q?P) ??(P?Q)?(?Q?P)?(?P??Q)?(?Q?P) ?(?P??Q)?((P??P)??Q)?(P?(Q??Q)) ?(?P??Q)?(P??Q)?(?P??Q)?(P?Q)?(P??Q)) ?(?P??Q)?(P??Q)?(P?Q))=m00?m10?m11=?(0,2,3) 22. 设A={1,2,3,4}，给A上的二元关系R={<1,2>,<2,1>,<2,3>,<3,4>}，求R的 传递闭包。 解：由R={<1,2>,<2,1>,<2,3>,<3,4>}，得 ?0??1MR??0??0?100?， ?010?001??000?? 从而 ?1??02MR??0??0?010?， ?101?000??000???0??13MR??0??0?101??10??010?， ?014MR???00000????000??0010??，于是 01?00??00?? 2 R2={<1,1>,<1,3>,<2,2>,<2,4>}，R3={<1,2>,<1,4>,<2,1>,<2,3>}， 2R4={<1,1>,<1,3>,<2,2>,<2,4>}=R，故 t(R)?R?R2?R3?R4=｛<1,1>,<1,2>,<1,3>,<1,4>,<2,1>,<2,2>，<2,3>， <2,4>，<3,4>} 23.设A={1，2，3，4，6，8，12，24}，R为A上的整除关系，试画 元、最小元、极大元、极小元。 解： 24.求下图所示格的所有5元子格。 A中的最大元为24、最小元为1、极大元为24、极小元为1。 解：所有 5元子格如下： 26.用矩阵的方法求右图中结点v1，v3之间长度为2的路径的数目。//教材P289、290 所以，图中结点v1，v3之间长度为2的路径的数目有3条。 //备注：邻接矩阵中所有元素之和等于边数。通路（v1->v1,v2,v3,v4…）与回路（v1->v1,v2->v2,v->v3…） 3 四、证明题 27. 在整数集Z上定义：a?b?a?b?1,?a,b?Z，证明： 证明：（1）对于?a,b?Z，有a?b（2）对于?a,b,c?Z，有 ?a?b?1?Z，所以运算?是封闭的。 (a?b)?c?(a?b?1)?c?a?b?1?c?1?a?b?c?2， a?(b?c)?a?(b?c?1)?a?b??c?1?1?a?b?c?2， 即(a?b)?c?a?(b?c)，故运算?是可结合的。 （3）?1是单位元，因为?a?Z，a（4）?a?Z，由a?(?2?a)?(?1)?a?1?1?a，(?1)?a??1?a?1?a. ?a?2?a?1??1， (?2?a)?a??2?a?a?1??1，可知 ?2?a是a的逆元。 综上所述， 28. 设R为N×N上的二元关系，??a,b?,?c,d证明：因为??a,b??N??N?N， ?a,b?R?c,d??b?d，证明R为等价关系。 ?N，b?b，所以?a,b?R?a,b?，故R具有自反性。 ??a,b?,?c,d??N?N，若?a,b?R?c,d?，则b?d，即d?b， 故?c,d?R?a,b?，所以R具有对称性。 ??a,b?,?c,d?,?e,f??N?N，若?a,b?R?c,d?，?c,d?R?e,f?， 则b?d，d?f从而b?f，故?a,b?R?e,f?，所以R具有对称性。 综上所述，R为等价关系。 五、综合应用题 29．在谓词逻辑中构造下面推理的证明：每个在学校读书的人都获得知识。所以如果没有人获得知识就没有人在学校 读书。（个体域：所有人的集合） 证明：设S（x）:x是 在学校读书的人， G（x）：x是获得知识的人。 前提：（?x）(S(x)?G(x))； 结论：?(?x)G(x)??(?x)S(x) 推理过程如下： （1）（?x）(S(x)?G(x)) P （2）S(c)?G(c) US（1） （3）?(?x)G(x) P（附加前提） （4）(?x)?G(x) T(3)E (5) (6) (7) ?G(c) US(4) ?S(c) T(2)(5)I (?x)?S(x) UG(6) (8) ?(?x)S(x) T(7)E 4