离散数学综合练习及答案.doc

北京科技大学远程教育学院离散数学综合练习(一)参考答案数理逻辑一、判断下列句子是否是命题，若是命题判断真值，并将其符号化。 1、今天天气真好！ 解：不是命题。 2、王华和张民是同学。 解：是命题。真值视实际情况而定。p：王华和张民是同学。 3、我一边吃饭，一边看电视。 解：是命题。真值视实际情况而定。p：我吃饭。q：我看电视。pq 4、没有不呼吸的人。 解：是命题。真值为1。M(x)：x是人。F(x)：x呼吸。x(M(x)F(x)二、求命题公式的真值表和成真赋值、成假赋值。 解： 0 0 001110 0 101110 1 001110 1 101111 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 成真赋值：000，001，010，011，100，101，111；成假赋值110五、解释I如下：D是实数集，特定元素a=0；特定函数f(x，y)=x-y；特定谓词F(x，y)：xy。在解释I下判别公式真、假。 1、解：真值为假 2、解：真值为真六、 1、求前束范式解： 2、证明：证明：七、写出下面推理的证明，要求写出前提、结论，并注明 推理规则。 （1）如果乙不参加篮球赛，那么甲就不参加篮球赛。若乙参加篮球赛，那么甲和丙就参加篮球赛。因此，如果甲参加篮球赛，则丙就参加篮球赛。解：p：甲参加篮球赛。q：乙参加篮球赛。r：丙参加篮球赛。前提： q p ，q (pr) ，结论：p r证明： q p 前提引入 pq 置换 q (pr) 前提引入 q (pr) 置换 (q p ) (q r) 置换 q r 化简 q r 置换 p r 假言三段论推理正确 （2）学会的成员都是专家。有些成员是青年人。所以，有些成员是青年专家。(个体域是人的集合)F(x)：x 是学会成员。G(x)：x 是专家。H(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推理正确离散数学综合练习(二)参考答案集合、关系、函数一、判断题 1、对任意集合A，都有AA和A A，不能同时成立。 （ F ） 2、R1、R2是A上的具有自反性的二元关系，R1R2也具有自反性。 （ F ） 3、A上恒等关系IA具有自反性、对称性、反对称性、传递性。 （ T ） 4、f：AB，g：BC，若fog是AC的满射，则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一定具有的性质是 对称性 。 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、AB解： 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， 用关系矩阵求R4，写出R4的集合表示。 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是否是从AB的函数，若是指出是否是单射、满射、双射， 如果不是说明理由。（1）A=1，2，3，4，5、B=5，6，7，8，9 f=，解：f 是函数，由， f 不是单射，也不是满射。（2）A=1，2，3，4，5、B=5，6，7，8，9 f=，解：由，f 不是函数。（3）A、B都是实数集，f(x) = x3。解：f 是函数， f 是单射，也是满射，f 是双射。（4）A、B都是正整数集，解：f 是函数， f 是单射，不是满射。2、，、都是的函数。 ：， ：， 、中哪个有反函数？若有则求出反函数。求出复合函数、。解： 是双射，有反函数，就是 自己。：，：，：，3、A、B都是有n个元素的集合，f：AB的函数。 证明：f是单射 f是满射。证明：设f是单射，由于，所以 有n 个元素，又 ，而 也只有 n 个元素，所以 设f是满射，若 f 不是单射，则 ，由于 中只有 n 个元素，所以 ，与 矛盾。离散数学综合练习(三)参考答案代数系统一、判断题1、0，1，2，n对普通加法封闭。 （F）2、在非负整数集Z+上定义运算，xy = minx，y，1是运算的幺元。（T）3、实数集与普通乘法构成的代数系统中每个元素都有逆元素。 （F）4、在代数系统中，0是零元。 （F）5、非负整数集Z+与普通加法构成的代数系统是群。 （F）6、M是n阶可逆矩阵的集合，是矩阵乘法，是群。 （T）7、循环群的子群是循环群。 （T）8、代数系统是代数系统的子代数。 （F）二、填空题1、A =x | x = 3n ，nN，对 乘法 运算封闭。2、构成的代数系统是 半群 。3、在代数系统中，0是 单位 元。4、F =f | f：AA，o为函数的复合运算，的单位元是 恒等函数 。5、f、g都是从A到A的双射，(fog)1 = g1of1 。6、在代数系统中，元素a、b都有逆元，则(a1)1= a ，(a*b)1=b1*a1 。7、循环群有 生成 元，使循环群中元素都是该元素的方幂。8、V1=，V2=都有幺元，j是V1到V2的同态，则j把V1中的单 位元映射到 V2中的单位元 。三、解答题 1、Q是正有理数集，是普通乘法，是否是半群、独异点、群？解：普通乘法有结合律，单位元是 1 ，但 0 没有逆元，是独异点。 2、实数集R上的运算 * ，a*b=abab，是普通加法，是普通乘法。 验证：只能是独异点。解： a，b，c R (a*b)*c = (abab) * c = (abab)c(abab)c= abcabacbcabca*(b*c) = a* (bcbc) = a+(bcbc)+a(bcbc)= abcabacbcabc运算 * 有结合律 由于运算 * 有交换律，设 e 是单位元。a Ra*e = aeae = 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 无逆元，所以 是独异点。 3、实数集R上的运算 * ，a*b=ab 2，是普通加法，-是普通减法。 是否是群？解： 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 所以 是群。四、求8阶循环群e，a，a2，a7的各阶子群。解：一阶子群e 二阶子群e，a4 四阶子群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、顶点和边都不相同的通路，称为 初级通路 。 2、无向树有m个树枝，则顶点数为 m +1 。 3、无向图顶点之间的连通关系具有自反性、 对称 性、 传递 性， 是 等价 关系。 4、A是有向图D的邻接矩阵，若A3中的元素，则 顶点vi到vj 长度为 3 的通路有 2 条 。 5、A是有向图D的邻接矩阵，Bk=A+A2+Ak中元素bij0，则顶点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+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、求下列各图的最小生成树。解：w = 1+1+2+3 = 7 w = 1+2+4+4 = 11 2、求下列带权的最优