1.已知命题公式
(p?q)??(p?r)
（1）构造真值表；
（2）用等值演算法求公式的主析取范式。
解：（1）真值表
p q r p?q 0 p?r ?(p?r) (p?q)??(p?r) 0 1 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 0 0 1 0 1 1 1 0 0 1 1 0 1 1 0 0 1 1 1 1 1 0 0 （2）主析取范式
(p?q)??(p?r)
??(p?q)??(p?r)?(?p??q)?(?p??r)?((?p??q)?(?r?r))?(?p?(?q?q)??r)?((?p??q??r)?(?p??q?r)?(?p??q??r)?(?p?q??r)?m0?m1?m2
2．求公式
(p?(r?p))?(q?p) 的主合取范式及主析取范式。
3.设
f:R?R,f(x)?x2?2，g:R?R,g(x)?x?4,h:R?R,h(x)?x3?1，
R表示实数集。
其中
（1）求函数
f?g，g?f；
（2）
f,g,h哪些函数有反函数？如果有，求出这些反函数。
解：（1）
g?f(x)?f(g(x))?f(x?4)?(x?4)2?2?x2?8x?14 f?g(x)?g(f(x))?g(x2?2)?x2?2
（2）
g和h有反函数，g?1:R?R,g?1(x)?x?4；
h?1:R?R,h?1(x)?3x?1
，
4.设
A?{1,2,3,4,6,9,24,54}?>的哈斯图；
?为整除关系。
（1）画出偏序集 （2）求A中的极大元； （3）求子集B=｛3, 6, 9｝的上确界与下确界。 解：（1）哈斯图 24 4 2 6 54 9 3 （2）A中的极大元为 24，54；极小元为1；最大元：无；最小元：1 （3）求子集B=｛3, 6, 9｝的上确界为54，下确界为3。 5.设有向图 D如图所示，用邻接矩阵计算v1到v4长度小于或等于3的通路数。 解：有向图的邻接矩阵为 ?1?0A???1??1?2?13A???1??310001113010210110??1，?1?0?2A???10???0??30??3， 0??1?4?A?0??2??0??42113101110000? 0??0??0?11130? 0??0??0?题 v1到v3长度小于或等于3的通路数为 ?ai?13(i)14?0?1?1?2 6．设 Z6?{0,1,2,3,4,5}，给出模6加运算的运算的运算表。求单位元，求元素的逆元。解方程2?x?3。 ?的运算表为 ? 0 0 1 2 3 4 5 解：运算 0 1 2 3 4 5 1 1 2 3 4 5 0 2 2 3 4 5 0 1 3 3 4 5 0 1 2 4 4 5 0 1 2 3 5 5 0 1 2 3 4 （2）单位元为0，0的逆元为0，任一元素x的逆元为6-x。 （3）由 2?x?3得x?2?1?3?4?3?1 7. 设A＝{1，2，3，4，5}，R是A上的二元关系，且R＝{（2，1>，<2，5），<2，4>，<3，4)，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。 解：r(R)=R∪IA s(R)=R∪R-1 t(R)= {<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>,（2,2>,<5,5>} 2.设 A?{1,2,4,7,14,28}?， 为整除关系。 （1）画出偏序集 ?>的哈斯图； （2）求子集 B?{2,4,7}的极大元、极小元、上确界与下确界； 是否为分配格？请说明理由。 （3）判断 ?A,??参考答案: 解：（1）哈斯图 28 14 4 7 2 1 （2） B的极小元为2，7，极大元为4、7，上确界：28，下确界：1。 （3） ?A,??不是分配格，因为格中存在与五角格同构的子格。 四、简答题 1. 设 R?{?1,3?,(1,4?,?2,2?,?3,1?,?3,3),?4,1?}是A={1,2,3,4}上的二元关系。 （1）画出R的关系图； （2）写出R的关系矩阵； （3）讨论R的性质。 （4）R是否为函数 解：（1）R的关系图 1 3 （2）R的关系矩阵 4 2 ?0 ?0??1??1 01001000 1??0??0?0? （3）R非自反、非反自传、对称、非反对称 、非传递的 （4）R不是函数，不满足函数单值性的要求。 2.设集合 （1）画出 （2）讨论 （3）讨论 A?{2,3,6,8}RRRR的关系图，写出的性质； 上的关系 R?{?x,y?|x整除y}。 的关系矩阵； 是否为函数？说明理由。 解：（1）R的关系图： 2 6 8 3 ?1 ?0?R的关系矩阵 ?0??0 01001110 1??0? ?0?1? （2）R自反、非反自传、非对称、反对称 、传递 （3）R不是函数，因为有 ?2,6??R,?2,8??R，不满足单值性 为自然数集合， 3.设 f:N?N?N,其中Nf({1,2,3}) f(x)??x,x2? （1）求 （2）讨论 f是否为单射和满射的，如果不是说明理由。 解： （1） f({1,2,3})?{?1,1?,?2,4?,?3,9?} ?1,2??ranf （2） f是单射，不是满射，因为 4.设有向图 D如题图3所示，用邻接矩阵完成以下计算。 到 长度小于或等于3的通路数； （1） v1v3v2（2）到自身长度小于或等于3的回路数； （3）写出 D的可达矩阵，并说明D的连通性。 解：有向图的邻接矩阵为 题图3 ?0?0A???0??0?0?0A3???0??010112122010012101??0?01?2?，A???01???0??02??0?02??，A4???02???1??0121034313101121221?1?? 1??1?3?3?? 3??2?（1）v1到v3长度小于或等于3的通路数为 ?ai?1（2）v2到自身长度小于或等于3的回路数为 (i)14?0?1?1?2 ?ai?13(i)11?0?2?1?3 ?1?0?（3）P(D)??0??0 111111111?1?? 1??1?由可达矩阵可知D是单向连通的。 四、证明题 1.用一阶逻辑推理理论证明： 前提： 结论： ?x(F(x)?G(x))?x(F(x)?H(x))?x(G(x)?H(x))， 证明： （1） (?x)(F(x)?H(x)) 前提引入 F(y)?H(y) （3）?? （2） （3） ?x(F(x)?G(x)) 前提引入 （4） F(y)?G(y) （3）?? （5） F(y) （2）化简 G(y) （4）（5）假言推理 H(y) （2）化简 G(y)?H(y) 前提引入 ?x(G(x)?H(x)) (8) ?? （6） （7） （8） （9）
离散数学综合练习题2018(1)
