离散数学综合练习及答案

1、北京科技大学远程教育学院离散数学综合练习(一)参考答案数理逻辑一、判断下列句子是否是命题，若是命题判断真值，并将其符号化。 1、今天天气真好！ 解：不是命题。 2、王华和张民是同学。 解：是命题。真值视实际情况而定。p：王华和张民是同学。 3、我一边吃饭，一边看电视。 解：是命题。真值视实际情况而定。p：我吃饭。q：我看电视。pÙq 4、没有不呼吸的人。 解：是命题。真值为1。M(x)：x是人。F(x)：x呼吸。"x(M(x)®F(x)二、求命题公式的真值表和成真赋值、成假赋值。 解： Ù0 0 001110 0 101110 1 001110 1 10

2、1111 0 001001 0 101111 1 010001 1 10111成真赋值：000，001，010，011，101，111；成假赋值100，110三、用真值表、等值演算两种方法判别公式类型。 1、解： ®0 0 01010 0 11010 1 01100 1 11111 0 00011 0 10011 1 01101 1 1111可满足式 2、解： A0 010110 110111 000111 11101永真式四、求命题公式的主析取范式和成真赋值、成假赋值。 解： 0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 111111101 成真赋值

3、：000，001，010，011，100，101，111；成假赋值110五、解释I如下：D是实数集，特定元素a=0；特定函数f(x，y)=x-y；特定谓词F(x，y)：x<y。在解释I下判别公式真、假。 1、解：真值为假 2、解：真值为真六、 1、求前束范式解： 2、证明：证明：七、写出下面推理的证明，要求写出前提、结论，并注明 推理规则。 （1）如果乙不参加篮球赛，那么甲就不参加篮球赛。若乙参加篮球赛，那么甲和丙就参加篮球赛。因此，如果甲参加篮球赛，则丙就参加篮球赛。解：p：甲参加篮球赛。q：乙参加篮球赛。r：丙参加篮球赛。前提： Øq® Øp ，q &#

4、174; (pÙr) ，结论：p ® r证明： Øq® Øp 前提引入 p®q 置换 q ® (pÙr) 前提引入 Øq Ú (pÙr) 置换 (Øq Ú p ) Ù(Øq Ú r) 置换 Øq Ú r 化简 q ® r 置换 p ® r 假言三段论推理正确 （2）学会的成员都是专家。有些成员是青年人。所以，有些成员是青年专家。(个体域是人的集合)F(x)：x 是学会成员。G(x)：x 是专家。H

5、(x)：x 是青年人。前提："x( F(x)® G(x)，$x( F(x)Ù H(x)结论：$x( F(x)Ù H(x)Ù G(x)证明： $x( F(x)Ù H(x) 前提引入 F(c)Ù H(c) EI "x( F(x)® G(x) 前提引入 F(c)® G(c) UI F(c) 化简 G(c) 假言推理 F(c)Ù H(c)Ù G(c) 合取 $x( F(x)Ù H(x)Ù G(x) EG推理正确离散数学综合练习(二)参考答案集合、关系、函数一、判断

6、题 1、对任意集合A，都有AÎA和AÍ A，不能同时成立。 （ F ） 2、R1、R2是A上的具有自反性的二元关系，R1R2也具有自反性。 （ F ） 3、A上恒等关系IA具有自反性、对称性、反对称性、传递性。 （ T ） 4、f：A®B，g：B®C，若fog是A®C的满射，则f、g都是满射。 （ F ） 5、A =1，2，3，4，f是从A到A的满射，则也是从A到A的单射。 （ T ）二、填空题 1、(AB)AB = A 。 2、A有2个元素，B有3个元素，从A到B的二元关系有 26 个。 3、R是A上的二元关系，RoR1一定具有的性质是 对称

7、性 。 4、f(x)= lnx 是从 R+ 到 R 的函数。 5、f、g都是从A到A的双射，(fog)1 = g1of1 。三、集合 1、A=a，b，c，c，a，b、B=a，b，c，b 求AB、AB、AB、AÅB解： 2、A=a，b，c，Ø 求A的幂集。解：P(A)=Ø，Ø，a，b，c，a，b，c，a，b，Ø，c，Ø，A 3、证明：A(BC) = (AB)(AC)解：四、二元关系（共30分） 1、Aa，b，c，b，R<a，b>，<b，a>，<b，c>，<c，d> 用关系矩阵求R4，写出R

8、4的集合表示。 2、指出二元关系满足哪种性质，不满足哪种性质，说明理由。解：满足反对称性；不满足自反性，反自反性，对称性，传递性 3、A =1，2，3，4，5，6，S =1，2，3，4，5，6 画出由S产生的等价关系的关系图。解： 4、画出偏序集的哈斯图，并指出最大元、最小元、极大元、极小元。1，2，3，12整除关系解：最大元：无；最小元、极小元：1；极大元：7，8，9，10，11，12五、函数 1、确定以下各题中f是否是从A®B的函数，若是指出是否是单射、满射、双射， 如果不是说明理由。（1）A=1，2，3，4，5、B=5，6，7，8，9 f=<1，8>，<3，9

9、>，<4，10>，<2，6>，<5，9>解：f 是函数，由<3，9>，<5，9> f 不是单射，也不是满射。（2）A=1，2，3，4，5、B=5，6，7，8，9 f=<1，7>，<2，6>，<4，8>，<1，9>，<5，10>解：由<1，7>，<1，9>，f 不是函数。（3）A、B都是实数集，f(x) = x3。解：f 是函数， f 是单射，也是满射，f 是双射。（4）A、B都是正整数集，解：f 是函数， f 是单射，不是满射。2、，、都是的函数

10、。 ：， ：， 、中哪个有反函数？若有则求出反函数。求出复合函数、。解： 是双射，有反函数，就是 自己。：，：，：，3、A、B都是有n个元素的集合，f：A®B的函数。 证明：f是单射 Û f是满射。证明：Þ设f是单射，由于，所以 有n 个元素，又 ，而 也只有 n 个元素，所以 Ü 设f是满射，若 f 不是单射，则 ，由于 中只有 n 个元素，所以 ，与 矛盾。离散数学综合练习(三)参考答案代数系统一、判断题1、0，±1，±2，±n对普通加法封闭。 （F）2、在非负整数集Z+上定义运算·，x·y = mi

11、nx，y，1是运算的幺元。（T）3、实数集与普通乘法构成的代数系统中每个元素都有逆元素。 （F）4、在代数系统<Z，+，0>中，0是零元。 （F）5、非负整数集Z+与普通加法构成的代数系统是群。 （F）6、M是n阶可逆矩阵的集合，×是矩阵乘法，<M，×>是群。 （T）7、循环群的子群是循环群。 （T）8、代数系统<Z，+>是代数系统<R*，+>的子代数。 （F）二、填空题1、A =x | x = 3n ，nÎN，对 乘法 运算封闭。2、<R*，+>构成的代数系统是 半群 。3、在代数系统<Z，+，0

12、>中，0是 单位 元。4、F =f | f：A®A，o为函数的复合运算，<F，o>的单位元是 恒等函数 。5、f、g都是从A到A的双射，(fog)1 = g1of1 。6、在代数系统<S，*>中，元素a、b都有逆元，则(a1)1= a ，(a*b)1=b1*a1 。7、循环群有 生成 元，使循环群中元素都是该元素的方幂。8、V1=<S1，o>，V2=<S2，*>都有幺元，j是V1到V2的同态，则j把V1中的单 位元映射到 V2中的单位元 。三、解答题 1、Q是正有理数集，×是普通乘法，<Q+，×>是

13、否是半群、独异点、群？解：普通乘法有结合律，单位元是 1 ，但 0 没有逆元，<Q+，×>是独异点。 2、实数集R上的运算 * ，a*b=aba×b，是普通加法，×是普通乘法。 验证：<R，*>只能是独异点。解： "a，b，cÎ R (a*b)*c = (aba×b) * c = (aba×b)c(aba×b)×c= abca×ba×cb×ca×b×ca*(b*c) = a* (bcb×c) = a+(bcb×c

14、)+a×(bcb×c)= abca×ba×cb×ca×b×c运算 * 有结合律 由于运算 * 有交换律，设 e 是单位元。"a Î Ra*e = aea×e = a，(1+ a )×e = 0 ，e = 0设 a1 是 * a 的逆元，a1 * a = a1 + a + a1 × a = 0(1+ a )a1 =a ，当 a ¹ 1时，a 有逆元。a = 1 无逆元，所以 <Q+，×>是独异点。 3、实数集R上的运算 * ，a*b=ab 2，是

15、普通加法，-是普通减法。 <R，*>是否是群？解： "a，b，c Î R，(a*b)*c = (ab2) * c = (ab2)c2 = abc4a*(b*c) = a * (cb2) = a(bc2)2 = abc4运算 * 有结合律由于运算 * 有交换律，设 e 是单位元。"a Î Ra*e = ae2 = a，e2 = 0 ，e = 2设 a1 是 * a 的逆元，a1 * a = a1 + a 2 = 2a1 = 4a 所以 <R，*> 是群。四、求8阶循环群e，a，a2，a7的各阶子群。解：一阶子群e 二阶子群e，a4

16、四阶子群e，a2，a4，a6 八阶子群e，a，a2，a7五、设代数系统A ，*有单位元，代数系统B ，无单位元。 证明：这两个代数系统不同构。证明：若A ，*，B ，同构，则存在同构映射j，又设 e 是A ，*的单位元，则 j( e ) 是B ，中的单位元，与B ，无单位元矛盾。离散数学综合练习(四)参考答案图论一、判断题 1、(2，2，5，2，1，3)可以构成图的度数序列。 （ F ） 2、n阶无向完全图的边数为n(n1)。 （ F ） 3、生成子图与母图有相同的边集。 （ F ） 4、最小生成树是不唯一的。 （ T ） 5、有向完全图是强连通图。 （ T ）二、填空题 1、顶点和边都不相同

17、的通路，称为 初级通路 。 2、无向树有m个树枝，则顶点数为 m +1 。 3、无向图顶点之间的连通关系具有自反性、 对称 性、 传递 性， 是 等价 关系。 4、A是有向图D的邻接矩阵，若A3中的元素，则 顶点vi到vj 长度为 3 的通路有 2 条 。 5、A是有向图D的邻接矩阵，Bk=A+A2+Ak中元素bij¹0，则顶点vi到 vj 可达 。三、解答题 1、在图1中（1）求邻接矩阵A；（2）计算A2、A3、A4；（3）求B4=A+A2+A3+A4；（4）v1到v2长度为2、3的通路各有多少条？（5）v1到v2长度小于等于4的通路有多少条？解：（1）（2），（3）B4=A+A2

18、+A3+A4（4）v1到v2长度为2、3的通路分别有1、2条（5）v1到v2长度小于等于4的通路有7条 2、有向图的邻接矩阵（1）画出这个有向图；（2）求；（3）中长度为2的回路有多少条？（4）中到长度小于等于2的通路有多少条？（5）中的元素说明什么？解：（1）画出这个有向图；（2）（3）中长度为2的回路有2条（4）中到长度小于等于2的通路有2条（5）中的元素说明到长度等于2的通路有1条四、特殊图 判别下列各图是否是欧拉图和哈密尔顿图，说明理由。（3）（1）（2）解：(1) 只是哈密尔顿图，aefbcghda 是哈密尔顿回路(2)(3)是欧拉图，顶点度数都是偶数(2)(3)也是哈密尔顿图 abcgdfea、abcdefghija 分别是哈密尔顿回路五、树 1、求下列各