远程离散数学答库(北大).docVIP

本试卷共 2 页，第  PAGE 2 页 3、完全二部图 K3，4的边数为 [ D ] A．7； B．9； C．10； D．12。 4、p：天气好。q：我们去游泳。命题 ”除非天气好，否则我们不去游泳”符号化为[B] A．p→q； B．﹁p→﹁q； C．﹁q→﹁p； D．﹁p∧﹁q 5、G 是 8 阶无向简单连通图，则顶点之间的最大距离为 [ A ] A．7； B．8； C．9； D．10。 6、命题公式 ﹁（p→（p∨q））的类型是 [ B ] A．永真式； B．永假式； C．可满足式； D．不是正确的命题公式。 7、100 个分支点的 3-元正则树有多少个顶点 [D] A．100； B．200； C．300； D．301。 10、G 是11 阶无向简单连通图，则顶点之间的最大距离为 [ D ] A．7； B．8； C．9； D．10。 11、公式 p→（p∨q）的类型是 [ A ] A．永真式； B．永假式； C．可满足式； D．不是正确的命题公式。 15、非平凡无向树 T 是 [ C ] A．欧拉图； B．哈密尔顿图； C．二部图； D．非平面图。 16、10 阶无向简单图 G 中有 4 个奇数度顶点，其补图中必有 r 个奇数度顶点 [ C ] A．r = 4； B．r = 5； C．r = 6； D．r = 7 二、判断下列各题的是非（每题 3分，共21分） 1、x + 3y = 3y + x 不是命题。 [ x ] 3、根树中最长的初级通路的端点都是树叶。 [ 非 ] 5、n为大于等于3的奇数，无向完全图Kn是欧拉图。 [ 是 ] 6、无向连通图G的每一条边都可以成为他的某一生成树的树枝。 [ 非 ] 7、任何无向图中奇度顶点必有偶数个。 [ 是 ] 9、每条边都是桥的无向连通图必是树。 [ 是 ] 10、命题公式 p∨（(p→q)∧p）与公式 p 等值。 [ 是 ] 12、命题公式 A =﹁（p→q）∧q 的主析取范式为 A〈=〉∑（0）。 [ 非 ] 三、简答题（每题 3 分，共 9 分） 你认为完全图K4是否是哈密尔顿图，为什麽？是。因为存在哈密顿回路。 如何利用命题公式 A 的真值表求他的主合取范式。将表中的成假赋值变换成极大项。 非平凡无向图 G 是哈密顿图的必要条件。连通而没有割点。 你认为平凡图是否是哈密尔顿图，为什麽？是。因为符合定义。 重言式命题公式 A 的主合取范式中含有多少个极大项。不含极大项。 7、代数系统的定义。定义了二元运算的集合。 8、什麽叫自然映射。将集合中的元素映射到其商集的等价类。 9、R 是集合 A 上的关系，若 R ∩ R—1 = ?，R 必然具有何性质 ？反自反，反对称。 10、什麽是简单图。不含平行边及自环的图。 四、填空题（题中，IA 为恒等关系，ranR为关系的值域）（每题 3 分，共 21 分） 1、一阶逻辑公式 彐x F（x）→（彐x F（x）∨彐y G（y））的类型是 永真式 五、综合题 1、请在合适的逻辑中构造下面论题的证明： 若小王和小张去看电影，则小李也去。小赵不去看电影或小张去看电影。 小王去看电影。所以，若小赵去看电影，则小李也去。 p→q，﹁r∨s，p；r→q