西南大学网络与继续教育学院课程考试试题卷类别： 网教 专业： 计算应用技术 课程名称【编号】： 离散数学【0004】 A 卷大作业 满分：100 分一、 大作业题目1. 简述集合的直观含义，给出集合的最常见三种运算 . 设全集U={a , b , c , d}，A={a , b}, B={b, c}, 分别计算A∪B , A∩B , A.答：集合：在一定范围内, 集合(set)是其具有某种特定性质的对象汇集成的一个整体, 其中的每一个对象都称为该集合的元素(element).2. 请给出所有 9 个逻辑联接词的名称和运算符号，并写出命题公式(¬p∨q )→r的真值表.答：（1）否定联结词（2）合取联结词（3）析取联结词（4）异或联结词（5）条件联结词（6）双条件联结词（7）与非联结词（8）或非联结词（9）条件否定联结词在任何指派下均取真的命题公式称为永真式或重言式(tautology)；在任何指派下均取假的命题公式称为永假式或矛盾式(contradiction)；至少有一种指派使其为真的命题公式称为可满足式(contingency,satisfactablef ormula)；至少有一种指派使其为真同时至少有一种指派使其为假的命题公式称为中性式(neutralformula)。根据定义知，命题公式 为中性式。很容易验证，命题公式 为永真式，为永假式。命题公式的分类如下：显然， 永真的充要条件是 永假； 永真的充要条件是 和 均永真。 3. 请给出递归关系的思想，并解答下述问题：某人举步上楼梯，每步跨 1 个台阶或 2 个台- 1 - 阶，设上 n 个台阶的不同方式数为 an. 求出关于 an的初始条件以及递归关系. 解：显然，初始条件为 a1 =1，a2 = 2。容易知道 an=an-1 +an-2(n≥3)4. 请给出图的定义，并证明：有n个人，每个人恰有 3 个朋友，则n是偶数. 　证：用 n 个节点代表 n 个人，两个人是朋友则在相应的两个节点之间连一条无向边，于是得到一 个 n 阶 图 , 其 中 每 个 节 点 的 度 数 均 为 3. 由 于 每 个 节 点 度 数 为 3, 根 据 握 手 定 理 知, 其中 m 为 G 的边数. 于是 n 必为偶数. 证毕5. 请给出无向树的定义，并解答下列问题：设G是一棵无向树且有 3 个 3 度节点，1 个 2 度节点，其余均为 1 度节点.(1)求出该无向树共有多少个节点.(2)画出两棵不同构的满足上述要求的无向树.. 答：不含有圈的连通无向图称为无向树(tree). 无向树的边称为树枝(branch)，度为 1 的节点称为叶(leaf)，每个连通分支均是无向树的无向图称为森林(forest)。无向树在图论中称为树，也可以称为自由树。含 个节点的(无向、有向、根)树称为 阶树。不含任意节点的图称为空树。二、大作业要求大作业共需要完成三道题：第 1 题必做，满分 30 分；第 2-3 题选作一题，满分 30 分；第 4-5 题选作一题，满分 40 分.- 2 -