华中农业大学《离散数学》2017-2018学年第一学期期末试卷B卷.doc

华中农业大学《离散数学》2017-2018年第一学期期末试卷B卷 一、 1.　用将公式化成主范式的方法，证明 　　　　　（P →Q）Ù（ P → R ）ÛP →(Q ÙR). 2.　证明： 二、符号化下列命题，并论证结论的有效性。 如果小张努力工作，则小王或小刘感到愉快；如果小王愉快，则小张不努力工作；如果小李愉快，则小刘不愉快。所以，如果小张努力工作，则小李不愉快。 三、对任意的x,y,z属于集合X，如果xRy且yRz，就有 ù(xRz)。则称X上的关系R是反传递的，证明：R是反传递的，当且仅当R2∩R为空。　 四、已知X={a，b，c，d，e，f，g}，偏序集〈X，R〉的哈斯图如下： f g e d b c a 　　1.　写出偏序关系R。 　　2.　能否对偏序集〈X，R〉添加一个有序对，得到R1，使得对子集Q={d，e，f，g}有上界和最小上界，并说明你的结论。 五、给定代数系统U=〈I，+〉，+是通常数的加法运算，在I中定义关系R如下： xRy∣x-y∣<30 试确定R是否为U中的同余关系？为什么？ 六、画出不超过五个元素的格的哈斯图，判断其中哪些是分配格？哪些是模格？哪些是布尔代数？为什么？ 七、用floyd算法求下图中任意两个顶点间的最短路径。 4 2 7 2 2 6 1 3 V2 V3 V4 V6 V5 V1 八、1. 下图是否为二分图？为什么？ 6 8 7 4 1 2 3 5 2. 试画出顶点数、边数分别是奇数、偶数和偶数、奇数的两个欧拉图。