牡丹江师范学院《离散数学》2019-2020学年期末试卷.pdfVIP

牡丹江师范学院 《离散数学》2019-2020学年第一学期 期末考试 一：填空题 （30分） 1．设X {1，3，5，9，15，45}，R是X上的整除关系，则R是X上的偏序，其 最大元是 ，极小元是 。 5．树是不包含 的 图。 二：应用题 （30分） 1.下列各整数集合对于整除关系 “ ”都构成偏序集．判断哪些偏序集能构成 格?并说明理由。 1)L {l，2，3，4，5} 2)L {1，2，3，6，12} 3)L l l，2，3，4，6，9，12，18，36} 2 3 n 4)L {1，2，2，2，…，2} 2.设A {2，3，5，12，19}，等价关系R { x ,y  x ,y A  x  y (mod3)} ，写出 各元素的等价类，并求A／R。 3.用等价变换法证明：(P  Q)  ((R  Q)  ((P  R)  Q)) 是永真式。 三：分析题 （40分） 1.若无向图C是欧拉图，G 中是否存在割边?为什么? 2.设A是一个集合，X P(A)，R是X上元素之间的包含关系，试证明(X，R)是偏 序集。(注：P(A)为A 的幂集) 3.设有n个村庄要修路，(1)若要使所有村庄之间都有通路，问需在两村之间至 少修几条路?(2)若要使任意两村庄之间有一条直接的路，则至少修几条路?(3) 若修一条连接所有村庄的环路，问有多少种修路方案? 4.设有推理： (a)没有不守信用的人是可信赖的； (b)有些可以信赖的人是受过教育的人； (c)因此有些受过教育的人是守信用的。 试构造推理的证明，要求把推理的前提，结论符号化为谓词形式，并写出推 理过程。(个体域：人的集合) 提示：设F(x)表示x是守信用的人；G(x)表示x是可信赖的人；H(x)表示x 是受过教育的人。