离散数学期末试题B答案及评分标准.doc

考试纪律承诺本人自愿遵守学校考试纪律，保证以诚信认真的态度作答试卷。如有违纪，愿接受学校相关纪律处分。 本人签名： 北 京 工 商 大 学离散数学试卷(B)答案及评分标准 题 号一二三四五六七总 分得 分 学院 专业班级 学号 姓名 密封线 （1、请勿在密封线之上答题；2、请在答题纸上方留下相同密封距离）一、（本大题共30分）给定集合X=1,2,3,4，且X中的关系R：R=, , , 请回答以下各问题：1.写出R的关系矩阵。（6分）2.画出R的关系图。（6分）3.求包含R的最小的等价关系，并写出由其确定的划分。（6分）4.分别用关系矩阵表示出R的自反闭包r(R)、对称闭包s(R) 。（6分）45.求传递闭包t(R)。（写出计算步骤）（6分）321解 (1) . (2)（6分） （6分）(3)法一：直接由等价关系与划分之间的一一对应可知，包含R的最小等价关系为, , IA, （3分）对应的划分为1, 2,3, 4. （6分）法二：包含R的最小的等价关系就是tsr(R), 计算过程如下： （1分）,（2分）从而即=包含R的最小的等价关系，（3分）故其对应的划分为1, 2,3, 4. （6分）(4) , （3分）. （6分）(5) （2分）, （4分） （6分）学院 专业班级 学号 姓名 密封线 （1、请勿在密封线之上答题；2、请在答题纸上方留下相同密封距离）二、(10分) 设R是集合A上的二元关系，证明R在A上反对称当且仅当RR-1IA.证明：“”： 设任意, 则且.则 且.从而, .又因为R是反对陈关系，所以必有x=y, 即IA, 故RR-1IA. （5分）“”：设, R, 则, ，即, . 已知RR-1IA, 所以x=y, 故由定义可知，R是反对称的。 （10分）三、在命题逻辑中用构造证明下列推理的有效性。（10分）：如果天气晴朗，并且没有考试，则他们就外出郊游；结果他们并没有外出郊游，而且也没有考试。所以天气不好。解：设P表示“天气晴朗”，Q表示“他们要考试”，R表示“他们外出郊游”。则上述推理可以表示为 （5分）证明如下(1) P规则(2) P规则(3) (1)(2)拒取式(4) (3)等价置换(5) P规则(6) (4)(5)析取三段论故此推理有效。（10分）四、（10分）在一阶谓词逻辑中符号化下列命题。没有最小的有理数。个体域：实数集合解：Q(x): x是有理数， S(x, y): x比 y小， （5分）则原命题可以表示为如下形式：.（10分）五、利用真值表法，按P，Q，R顺序求下列命题公式：(PR) (QR)的主析取范式。(10分)解：命题公式的真值表为：PQR上式11111101101110010111010100110001（5分）所以原命题公式的主合取范式为： （10分）六、下图给出了一个有向图。（1）求其邻接矩阵A；（10分）（2）求该图中所有长度为2的路的条数。（10分）解: (1) 邻接矩阵(2) 根据矩阵的乘法运算知故图中所有长度为2 的路的条数为1+1+2+1+1+1+1+1+1=10.七、(10分) 一颗无向树T有5片树叶，3个2度分支点，其余的分支点都是3度顶点，问T有几个顶点？ 学院 专业班级 学号 姓名 密