北京科技大学远程教育学院《离散数学》综合练习一参考答案数理逻辑一、判断下列句子是否是命题，若是命题判断真值，并将其符号化。 1、今天天气真好！ 解：不是命题。 2、王华和张民是同学。 解：是命题。真值视实际情况而定。p：王华和张民是同学。 3、我一边吃饭，一边看电视。 解：是命题。真值视实际情况而定。p：我吃饭。q：我看电视。pq 4、没有不呼吸的人。 解：是命题。真值为 1。Mx：x 是人。Fx：x 呼吸。xMxFx二、求命题公式的真值表和成真赋值、成假赋值。 解： 0 0 0 0 1 1 10 0 1 0 1 1 10 1 0 0 1 1 10 1 1 0 1 1 11 0 0 0 1 0 01 0 1 0 1 1 11 1 0 1 0 0 01 1 1 0 1 1 1成真赋值：000，001，010，011，101，111；成假赋值 100，110三、用真值表、等值演算两种方法判别公式类型。 1、 证明：这两个代数系统不同构。证明：若〈A ，*〉，〈B ， 〉同构，则存在同构映射，又设 e 是〈A ，*〉的单位元，则  e  是〈B ， 〉中的单位元，与〈B ， 〉无单位元矛盾。《离散数学》综合练习四参考答案图论一、判断题 1、2，2，5，2，1，3可以构成图的度数序列。 （ F ） 2、n 阶无向完全图的边数为 nn－1。 （ F ） 3、生成子图与母图有相同的边集。 （ F ） 4、最小生成树是不唯一的。 （ T ） 5、有向完全图是强连通图。 （ T ）二、填空题 1、顶点和边都不相同的通路，称为 初级通路 。 2、无向树有 m 个树枝，则顶点数为 m +1 。 3、无向图顶点之间的连通关系具有自反性、 对称 性、 传递 性， 是 等价 关系。 4、A 是有向图 D 的邻接矩阵，若 A3中的元素 ，则 顶点 v i 到 v j 长度为 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+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 条 四、特殊图 判别下列各图是否是欧拉图和哈密尔顿图，说明理由。解：1 只是哈密尔顿图，aefbcghda 是哈密尔顿回路23是欧拉图，顶点度数都是偶数23也是哈密尔顿图 abcgdfea、abcdefghija 分别是哈密尔顿回路五、树 1、求下列各图的最小生成树。解：w = 1+1+2+3 = 7 w = 1+2+4+4 = 11（1） （2） （3） 2、求下列带权的最优二叉树，并求权数。（1）3，4，5，6，7，8，9（2）1，2，4，6，9，12解：（1）3，4，5，6，7，8，93，4，5，6，7，8，95，6，7，7，8，97，7，8，9，118，9，11，1411，14，1717，2542W =7+11+14+25+42=119 （2）1，2，4，6，9，12（2）1，2，4，6，9，121，2，4，6，9，12 3，4，6，9，12 6，7，9，12 9，12，13 13，21 34W =3+7+13+21+34=78 解： 0 0 0 1 0 10 0 1 1 0 10 1 0 1 1 00 1 1 1 1 11 0 0 0 0 11 0 1 0 0 11 1 0 1 1 01 1 1 1 1 1可满足式 2、解：A0 0 1 0 1 10 1 1 0 1 11 0 0 0 1 11 1 1 1 0 1永真式四、求命题公式的主析取范式和成真赋值、成假赋值。 解： 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：x<y。在解释 I 下判别公式真、假。 1、解：真值为假 2、解：真值为真六、 1、求前束范式解： 2、证明：证明：七、写出下面推理的证明，要求写出前提、结论，并注明 推理规则。 （1）如果乙不参加篮球赛，那么甲就不参加篮球赛。若乙参加篮球赛，那么甲和丙就参加篮球赛。因此，如果甲参加篮球赛，则丙就参加篮球赛。 解：p：甲参加篮球赛。q：乙参加篮球赛。r：丙参加篮球赛。前提： q p ，q  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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，都有 AA 和 A A，不能同时成立。 （ F ） 2、R1、R2是 A 上的具有自反性的二元关系，R1－R2也具有自反性。 （ 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、A－B∪AB = A 。 2、A 有 2 个元素，B 有 3 个元素，从 A 到 B 的二元关系有 2 6 个。 3、R 是 A 上的二元关系，RoR－1一定具有的性质是 对称性 。 4、fx= lnx 是从 R + 到 R 的函数。 5、f、g 都是从 A 到 A 的双射，(fog)－1 = g － 1 o f － 1 。三、集合 1、A={{a，{b}}，c，{c}，{a，b}}、B={{a，b}，c，{b}} 求 A∪B、A∩B、A－B、AB解： 2、A={{a，{b}}，c，Ø} 求 A 的幂集。解：PA={Ø，｛Ø｝，{{a，{b}}}，｛c｝，｛{a，{b}}，c｝，｛{a，{b}}，Ø｝，｛c，Ø｝}，A} 3、证明：A－B∪C = A－B∩A－C解： 四、二元关系（共 30 分） 1、A＝{a，b，c，b}，R＝{<a，b>，<b，a>，<b，c>，<c，d>} 用关系矩阵求 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 是否是从 AB 的函数，若是指出是否是单射、满射、双射， 如果不是说明理由。（1）A=｛1，2，3，4，5｝、B=｛5，6，7，8，9｝ f=｛1，8，3，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、 ， ， ， ， 、 都是 的函数。 ： ， ， ， ： ， ， ， 、 中哪个有反函数？若有则求出反函数。求出复合函数 、 。解： 是双射，有反函数，就是 自己。 ： ， ， ，： ， ， ，： ， ， ，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 = min｛x，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中，0 是 单位 元。4、F =｛f | f：AA｝，o 为函数的复合运算，F，o的单位元是 恒等函数 。5、f、g 都是从 A 到 A 的双射，(fog)－1 = g － 1 o f － 1 。6、在代数系统S，*中，元素 a、b 都有逆元，则a－1－1= a ，a*b－1=b － 1 *a － 1 。7、循环群有 生成 元，使循环群中元素都是该元素的方幂。8、V1=S1，o，V2=S2，*都有幺元，是 V1到 V2的同态，则把 V1中的单 位元映射到 V 2 中的单位元 。三、解答题 1、Q＋是正有理数集，×是普通乘法，Q+，×是否是半群、独异点、群？解：普通乘法有结合律，单位元是 1 ，但 0 没有逆元，Q+，×是独异点。 2、实数集 R 上的运算 * ，a*b=a＋b＋a×b，＋是普通加法，×是普通乘法。 验证：R，*只能是独异点。解： a，b，c R a*b*c = a＋b＋a×b * c = a＋b＋a×b＋c＋a＋b＋a×b×c= a＋b＋c＋a×b＋a×c＋b×c＋a×b×ca*b*c = a* b＋c＋b×c = a+b＋c＋b×c+a×b＋c＋b×c= a＋b＋c＋a×b＋a×c＋b×c＋a×b×c 运算 * 有结合律 由于运算 * 有交换律，设 e 是单位元。a  Ra*e = a＋e＋a×e = a，1+ a ×e = 0 ，e = 0设 a－1 是 * a 的逆元，a－1 * a = a－1 + a + a－1 × a = 01+ a a－1 =－a ，当 a  －1 时，a 有逆元。a = －1 无逆元，所以 Q+，×是独异点。 3、实数集 R 上的运算 * ，a*b=a＋b －2，＋是普通加法，是普通减法。 R，*是否是群？解： a，b，c  R，a*b*c = a＋b－2 * c = a＋b－2＋c－2 = a＋b＋c－4a*b*c = a * c＋b－2 = a＋b＋c－2－2 = a＋b＋c－4运算 * 有结合律由于运算 * 有交换律，设 e 是单位元。a  Ra*e = a＋e－2 = a，e－2 = 0 ，e = 2设 a－1 是 * a 的逆元，a－1 * a = a－1 + a －2 = 2a－1 = 4－a 所以 R，* 是群。四、求 8 阶循环群｛e，a，a2，…，a7｝的各阶子群。解：一阶子群｛e｝ 二阶子群｛e，a4｝ 四阶子群｛e，a2，a4，a6｝ 八阶子群｛e，a，a2，…，a7｝五、设代数系统〈A ，*〉有单位元，代数系统〈B ， 〉无单位元。