离散数学考试题及答案

1、命题公式(，p,q)?，r在赋值011下的真值为 。 M,M,M,M,M2、含3个命题变项的命题公式的主合取范式为, 03467 mmm,,则它的主析取范式为 。(示成的形式) 125 3、“有的学生学习努力”符号化为 。 (设P(x):x是学生;Q(x):x学习努力) APA、={a,b,c},A的幂集= 。 4，， 5、设R是A上的二元关系，若R是自反的、对称的和传递的，则R是A 上 的等价关系的 条件。 6、A={1,2,3},S={<1,2>,<2,1>,<3,3>},R={<1,3>,<2,2>,<3,2>} 则SοR= . Ax()7、设公式含自由出现的个体变项,B不含的出现，则由量词收缩xx ,,,xAxB(())与扩张等值式 . 8、T={x|x是单词“student”中的字母}，则T的基数为 。 9、设在有向图G中顶点的度数之和为n, 边数为m,则n和m的关系为 。 10、一棵无向树T有5片树叶，3个2度分支点，其余的分支点都是3度顶点，则T的顶点个数为 . 得分 阅卷人 ()pqr,，,二、求公式的主析取范式和主合取范式(10 分) 第 1 页 共 8 页 得分 阅卷人 三、演绎证明: ，,,，,qprprs,,前提: qs, 结论:(10 分) 得分 阅卷人 四、给出A={a,b,c}上所有的等价关系(10分) 第 2 页 共 8 页 得分 阅卷人 五、A={1,2,3,4}, R={<1,2>,<2,1>,<2,3>}, 求闭包r(R),s(R),t(R)及它们的关系阵、关系图。(10分) 得分 阅卷人 AR,,AR,六、已知偏序集的哈斯图如下，求和的集合表达 式，并指出该偏序集的极大元、极小元、最大元、最小元。(10分) 第 3 页 共 8 页 得分 阅卷人 vv七、求下图的邻接矩阵并求到长度为1，2，3，4的通路24 数(10分) 得分 阅卷人 八、在通信中要传输字母a、b、c、d、e、f、g，它们出现 的频率分别为a:35%，b:20%，c:15%，d:10%,e:10%， f:5%,g:5% 设计一个传输上述字母的最佳前缀码。(10分) 第 4 页 共 8 页 [考核类型] [三基类] [教师答题时间, 10 分钟] 1、0 mmm,,2、 125 ，,xPxQx(()())3、 4、{,，{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}, 5、充要 6、{<1,2>,<2,3>,<3,2>} ，,xAxB()7 8、6 9、n=2m 10、11 二、计算题(10分)[考核类型] [三基类] [教师答题时间, 5 分钟] 解:真值表: 5分 ()pqr,，, p q r 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 0 主析取范式:(，p?，q ?r)?(，p ?q?r)?(p ?，q?r)?(p ?q ?，r) 3分 主合取范式:|(p?q?r) ?(p?，q?r)?(，p?q?r)?(，p?，q?，r) 2分 第 5 页 共 8 页 三、演绎证明(10 分)[考核类型] [一般综合题] [教师答题时间, 5分钟] 1、，q?p (前提引入) 2、q,p (1置换) 3、r?，p (前提引入) 4、p,r (3置换) 5、q,r (2 4假言三段论 )每个前提引入和结论1分其它2分 6、r,s (前提引入) 7、q,s (5 6假言三段论 ) 四、计算题(10分)[考核类型] [三基类] [教师答题时间, 7 分钟] 解: 先给出A的所有划分 ,E,这些划分和A上的等价关系一一对应:对应于全域关系，对应于恒等1A2 RRR,,I,,,,,关系，分别对应于等价关系，其中 234A234 R,I={,,} 3A R,I={,} 每个图和关系一起2分 4A 五、计算题(10分)[考核类型] [三基类] [教师答题时间, 5分钟] 第 6 页 共 8 页 1100,, ,,1110,,r(R),{<1,2>,<2,1>,<2,3>},I 图略 4分 M,Ar(A),,0010 ,,0000,, 0100,, ,,1010,,s(R) ={<1,2>,<2,1>,<2,3>，<3 ,2 >} 图略 3分 M,s(A),,0100 ,,0000,, 1110,, ,,1110,,t(R)= {<1,2>,<2,1>,<2,3>，<1,1>,<2,2>,<1,3>} 图略 M,t(A),,0000 ,,0000,,3分 六、计算题(10分) [考核类型] [三基类] [教师答题时间, 3 分钟] 解A={1,2,3,4,5 } 2分 ,IR={<2,3>,<2,5>,<3,5>,<2,4>,<4,5>,<1,3>,<1,5>,<1,4>} A 4分 极大值:5; 极小值:1,2;最大值:5;最小值:无 每个1分 七、计算题(10分)[考核类型] [一般综合题] [教师答题时间, 6 分钟] 解:邻接矩阵 0210 0010A, 0001 0011 0021 00012A, 0011 0012 0013 00113A, 0012 0023 第 7 页 共 8 页 0034 00124A, 2分 0023 0035 vv所以到长度为1，2，3，4的通路数分别为0，1，1，2 ( 2分) 24 八、计算题(10分) [考核类型] [综合题] [教师答题时间, 5 分钟] (5分) 前缀码为 (5分 第 8 页 共 8 页