第 1 周习 题 一1.判断下列各语句是否为命题，若是命题请指出是简单命题还是复合命题：(1) 是无理数. 是简单命题(4) . 不是简单命题(7)4 是素数当且仅当三角形有三条边. 是复合命题(9)太阳系以外的星球上有生物. 是简单命题(14)4 是偶素数. 是复合命题(17)王大明与王小明是兄弟. 是简单命题2.将上题中的命题符号化，并讨论它们的真值.(1) 是无理数. p:“ 是无理数.” 真命题(4) . (7) 4 是素数当且仅当三角形有三条边. p: “4 是素数.”q:“三角形有三条边.”pq，假命题(9) 太阳系以外的星球上有生物. p:“太阳系以外的星球上有生物.”, 真值现在不知道.(14) 4 是偶素数.p:“4 是偶数.”，q:“4 是素数.” pq， 假命题(17)王大明与王小明是兄弟.p:“王大明与王小明是兄弟.” 真值视具体情况而定.5.将下列命题符号化： R ={1，2，2，1}9.设 R={0，1，0，2，0，3，1，2，1，3，2，3}， 求 RR，R1.RR={0，2，0，3，1，3}R1={1，0，2，0，3，0，2，1，3，1，3，2}12.设 X={0，1，2，3}，R 是 X 上的关系： R={0，0，0，3，2，0， 2，1，2，3，3，2}试给出 R 的关系图和关系矩阵.，第 8 周13.设 X={1，2，3}，在图 4.14 中给出了 12 种 x 上的关系，对于每个关系图写出相应的关系矩阵，并说出它具有的性质．(1)(2)(5)(6)(7) (1) ，有对称性 (2) ，有反对称性、传递性(5) ，无性质 (6) ，有对称性(7) ，有自反性、反对称性第 9 周17.设 X={a，b，c，d}，X 上的等价关系 R={a，b，b，a，c，d， d，c}∪IX画出 R 的关系图，并求出 X 的各元素的等价类.[a] = [b] ={a，b}，[c] = [d] ={c，d}20.对于下列集合的整除关系画出哈斯图： (增加求极大元、极小元、最大元、最小元)(1) {1，2，3，4，6，8，12，24}最大元、极大元：24最小元、极小元：1(2) {1，2，3，4，5，6，7，8，9}最大元：无极大元：5，6，7，8，9最小元、极小元：1第 10 周24.在下列的关系中哪些能构成函数?(1) {x1，x2| x1，x2N∧x1+x2<10} 不是函数 (2) {y1，y2| y1，y2R∧y2=y12} 是函数(3) {y1，y2| y1，y2R∧y22=y1} 是函数28.给定函数 f 和集合 A 如下：(1)f：RR，f(x)=x，A={8}(3)f：NN×N，f(x)=x，x+1，A={5}(5)f：ZN，f(x)=|x|，A={2，3}(7)f：SR，S=[0，+]，f(x)= ，A= ，对以上每一组 f 和 A，分别回答以下问题：(a)f 是不是满射，单射或双射的?如果 f 是双射的，求 f 的反函数.(b)求 A 在 f 下的像 f(A). (1)f：RR，f(x)=x，A={8}双射。f1(x)=x f(A) ={8}(3)f：NN×N，f(x)=x，x+1，A={5}是单射，不是满射。f(A)= {5，6}(5)f：ZN，f(x)=|x|，A={2，3}是满射，不是单射。f(A)= {1，2}(7)f：SR，S=[0，+]，f(x)= ，A= ，是单射，不是满射。f(A)= ，32. 设 f，g，hRR，且有 f(x)=x+3，g(x)=2x+1， ，求 fg，gf，ff，gg，hf，gh，fh，ghffg(x)=2x+7，gf (x)=2x+4，ff (x)=x+6， gg (x)=4x+3hf (x)= +3，gh (x)=x+ ，fh (x)= + ，ghf(x)=x+ 34.设 f：RR，f(x)=x2－2；g：RR，g(x)=x+4； h：RR，h(x)=x3－1(1)求 gf(x)=(x+4)2－2，fg=x2+2(2)问 gf 和 fg 是否为单射，满射，双射的? 都不是单射，满射，双射(3)f，g，h 中哪些函数有反函数?如果有，求出该反函数.g，h 有反函数。g1(x)=x－4，第 11 周习题五2.判断下列集合对所给的二元运算是否封闭：(1)整数集合 Z 上的减法运算. 封闭(2)非零整数集合 Z*上的除法运算. 不封闭(3)全体 n×n 实矩阵集合 M，Mn(R)上的矩阵加法和矩阵乘法， 其中，n≥2. 矩阵加法和矩阵乘法都封闭(5)在全体正实数集合 R+上规定  为： ab=a+b－a－b， a，bR 不封闭(6)nZ+，nZ={nz | z Z}上的加法和乘法运算. 加法和乘法都封闭3.对于上题中封闭的二元运算判断是否适合交换律，结合律和分配律.(1)整数集合 Z 上的减法运算. 没有交换律和结合律(2)非零整数集合 Z*上的除法运算. 没有交换律和结合律 (3)全体 n×n 实矩阵集合 M，Mn(R)上的矩阵加法和矩阵乘法， 其中，n≥2. 矩阵加法有交换律和结合律；矩阵乘法有结合律；矩阵乘法对矩阵加法有分配律.(5)在全体正实数集合 R+上规定  为： ab=a+b－a－b， a，bR没有交换律和结合律(6)nZ+，nZ={nz | z Z}上的加法和乘法运算.加法和乘法有交换律，结合律；乘法对加法有分配律.4.对习题 2 中封闭的二元运算找出它的单位元，零元和所有可逆元素的逆元.(1)整数集合 Z 上的减法运算. 没有单位元，零元和可逆元.(2)非零整数集合 Z*上的除法运算. (3)全体 n×n 实矩阵集合 M，Mn(R)上的矩阵加法和矩阵乘法， 其中，n≥2. 矩阵加法：n 阶零矩阵是单位元，无零元，－M 是 M 的逆元.矩阵乘法：n 阶单位矩阵是单位元，n 阶零矩阵是零元，M 可逆时 M－1是 M 的逆元.(5)在全体正实数集合 R+上规定  为： ab=a+b－a－b， a，bR (6)nZ+，nZ={nz | z Z}上的加法和乘法运算. 加法：0 是单位元，无零元，－nz 是 nz 的逆元.6. S=Q×Q，Q 为有理数集，* 为 S 上的二元运算， a，b，x，y S，a，b*x，y=ax，ay+b(1) *运算在 S 上是否可交换，可结合?是否为幂等的? 不可交换，可结合，不是幂等的.(2) *运算是否有单位元，零元?如果有，请指出，并求 S 上所有可 逆元素的逆元.1，0是单位元，无零元， 时a，b的逆元是 ，8．令 S={a，b}，S 上有 4 个二元运算关 * ，·和口，分别由表 5.11确定.(1)这 4 个运算中哪些运算满足交换律、结合律、幂等律?*，，·有交换律；*，，□有结合律；□有幂等律.(2)求每个运算的单位元，零元及所有可逆元素的逆元.* 无单位元，a 是零元，无逆元.  a 是单位元，无零元，a－1= a，b－1= b.11.设 V={Z，+，}，其中+和分别代表普通加法和乘法，对下面给定的每个集合确定它是否构成 V 的子代数，为什么?(1) S1={2n | nZ} 是 V 的子代数.(2) S2={2n+1 | nZ} 不是 V 的子代数. (3) S3={－1，0，1} 不是 V 的子代数.第 12 周习 题 六1.对以下各小题给定的集合和运算判断它们是哪一类代数系统(只判 别半群，独异点)：(1) S1= ，*为普通乘法. 不是代数系统.(2) S2={a1，a2，，an}， ai，ajS2，ai * aj = ai. 半群.(3) S3={0，1}，*为普通乘法. 独异点.(4) S4={1，2，3，6}，x，y S4，xy，x*y 分别表示求 x 和 y 的 最小公倍数和最大公约数. (5) S5={0，1}，*为模 2 加法.4.设 G={0，1，2，3}，为模 4 乘法，即 x，yG，xy=(xy)mod4. 问G，构成什么代数系统(半群，独异点，群)？是半群，独异点，不是群.5.设 Z 为整数集合，在 Z 上定义二元运算，x，yZ 有 xy=x+y－2. 问 Z 与  运算能否构成群?为什么?可结合，单位元是 2，x 的逆元是 4－x .7.设 G={a，b，c}，在 G 上定义二元运算  如表 6．5 所示 (1)验证 G ，为群.可结合，单位元是 a，a－1= a，b－1= c，c－1= b..第 13 周7.设 G={a，b，c}，在 G 上定义二元运算  如表 6．5 所示 (2) G ，是否为循环群?如果是，找出它的生成元.是循环群，b，c 是生成元.8.证明循环群都是交换群.11.设 G 是模 20 整数加群.(1)求 G 的所有生成元. 1，3，7，9，11，13，17，19(2)求 G 的所有子群. 1 阶子群｛0｝2 阶子群｛0，10｝4 阶子群｛0，5，10，15｝ 5 阶子群｛0，4，8，12，16｝10 阶子群｛0，2，4，6，8，10，12，14，16，18｝20 阶子群 G补充：求 10 阶循环群{e，a1，a2，，a9}的全部子群.1 阶子群｛e｝2 阶子群｛e，a5｝5 阶子群｛e，a2，a4，a6，a8｝10 阶子群{e，a1，a2，，a9}第 14 周习 题 七1.设无向图 G= V，E{y，正}， V={v1，v2，…，v6}， E={(v1，v2)，(v2，v2)，(v2，v4)，(v4，v5)，(v3，v4)，(v1，v3)}.(1) 画出 G 的图形.(2) 求 G 中各顶点的度数，并验证握手定理.d(v1)=2，d(v2)=4，d(v3)=2，d(v4)=3，d(v5)=1，d(v6)=02+4+2+3+1+0=12 是边数的 2 倍。 (1)王威是 100 米冠军，又是 200 米冠军.p:“王威是 100 米冠军.”、q:“王威是 200 米冠军.” pq(3)虽然天气很冷，老王还是来了.p:“天气冷.”、q:“老王来了.” pq(5)如果天下大雨，他就乘公共汽车上班. p:“天下雨.”、q:“他乘公共汽车上班.” pq(7)除非天下大雨，否则他不乘公共汽车上班.p:“天下雨.”、q:“他乘公共汽车上班.” qp8.判断下列命题公式的类型(用真值表)：(4) (pq)  (qp). 永真式(5) ( pq)  (qp). 可满足式(7) (p∨p)  ((q∧q)∧r). 永假式第 2 周9.用等值演算法和真值表法判断下面公式的类型：(1) ((p∧q) p). 永假式(2) ((p q)∧(q p))(p  q) 可满足式17.用等值演算求下列各公式的主析取范式与成真赋值：(1) ( pq)  (q∨p). 0，2，3 成真赋值 00，10，11 (3) (p∨(q∧r))  (p∨q∨r) . 0，1，2，3，4，5，6，7 全部赋值都是成真赋值18.(1)用真值表法求下列各式的主析取范式： (3) 求出 G 中奇度顶点的个数，验证它满足握手定理的推论.奇度顶点的个数是 2(4) 指出图中的平行边、环、孤立点、悬挂顶点(度数为 1 的顶点)、 悬挂边(悬挂顶点关联的边).无平行边，v2处有环，v6是孤立点，v5是悬挂顶点，(v4，v5)是悬挂边.(5) G 是多重图吗?是简单图吗？G 不是多重图，不是简单图.2.设无向图 G 中有 12 条边，已知 G 中 3 度顶点有 6 个，其余顶点 的度数均小于 3，问 G 中至少有几个顶点? 9 个顶点.8.下列各图中各有几个顶点?(1) 14 条边，每个顶点的度数都是 4. 7 个顶点.(2) 24 条边，5 个 4 度顶点，4 个 5 度顶点，其余顶点的度数 都是 2. 13 个顶点.11．有向图 D=<V，E>如图 7.19 所示.(1) D 中有多少条不同的初级回路?有多少条不同的简单回路(这里 认为两条回路有一条边不同就是不同的回路)?4 条不同的初级回路，5 条不同的简单回路.(2) 求 a 到 d 的短程线及距离.短程线 aee2d，距离 d=<a，d>=2(3) 求 d 到 a 的短程线及距离.短程线 de1eba，距离 d=< d，a>=3(4) D 是哪类连通图? 单向连通图. 本题中规定至少有一条边不同的回路为不同的回路.12.有向图 D 如图 7.20 所示.(1) D 中 v1到 v4长度为 4 的通路有多少条? 4 条(2) D 中 v1到 v1长度为 3 的回路有多少条? 1 条(3) D 中长度为 4 通路总数为多少?其中有多少条是回路? 16 条，其中 3 条回路.(4) D 中长度小于等于 4 的通路为多少条?其中有多少条是回路？ 46 条，其中 8 条回路.要求本题用邻接矩阵的前 4 次幂来解. 第 15 周习 题 八2.(1) 无向树 T 中有 7 片树叶，3 个 3 度顶点，其余都是 4 度顶点， 问 T 中有几个 4 度顶点? 1 个 4 度顶点.(2) 无向树 T 中有 2 个 4 度顶点，3 个 3 度顶点，其余都是树叶， 问 T 中有几片树叶? 9 片树叶.(3) 一棵无向树 T 中有 ni个顶点的度数为 i，i = 2，3，…，k，而其余顶点都是树叶，问 T 中有几片树叶? 4.在图 8.19 所示图中，实边所示的生成子图是该图的一棵生成树 T.(1) 指出 T 的所有弦，及每条弦对应的基本回路，以及对应 T 的基 本回路系统.c，e，f，h 是 T 的弦.基本回路 Cc= cba，Ce= ebad，Cf= fgd，Ch= hbadg。基本回路系统｛Cc，Ce，Cf，Ch｝(2)指出了的所有树枝，及每条树枝对应的基本割集，以及 T 对应 的基本割集系统. a，b，d，g 是 T 的树枝.基本割集 Sa=｛a，c，e，h｝，Sb=｛b，c，e，h｝， Sd=｛d，f，e，h｝，Sg=｛g，f，h｝基本割集系统｛Sa，Sb，Sd，Sg｝5.求图 8.20 所示 2 个带权图中的最小生成树，并计算它们的权. 图 8.20 W=1+1+2+3+3=10 W=4+7+8+9=28第 16 周6.画一棵带权为 0.5，1，2，3.5，4，5，6.8，7.2，10 的最优 2 元树， 并计算它的权. WT=1.5+305+7+9+13.8+16.2+23.8+40=114.88.设 7 个字母在通信中出现的频率如下： a: 35% b: 35% c: 35% d: 35% e: 35% f: 35% g: 35%(1) 以频率(或乘 100)为权，求最优 2 元树.(2) 利用所求 2 元树找出每个字母的前缀码.11 传 a，01 传 b，101 传 c，100 传 e，0001 传 f，0000 传 g(3) 传输 10 000 个按上述比例出现的字母需要传输多少个二进 制数位?比用长度为 3 的等长码子传输省了多少个二进制数位?35002+20002+15003+10003+10003+5004+ 500 4=25500需要传输 25500 个二进制数位，节省了 4500 个二进制数位. 9.图 8.21 所示的 2 元树表达一个算式(1) 给出这个算式的表达式.(2) 给出算式的波兰符号法表达式.(3) 给出算式的逆波兰符号法表达式.第 17 周习 题 九1.判断下列命题是否正确：(1)完全图 Kn(n≥1)都是欧拉图. 不正确 (3)完全图 Kn(n≥1)都是哈密尔顿图. 不正确4.画一个无向欧拉图，使它具有：(1) 偶数个顶点，偶数条边. (2) 奇数个顶点，奇数条边.(3) 偶数个顶点，奇数条边. (4) 奇数个顶点，偶数条边.6.画一个无向图，使它：(1)既是欧拉图，又是哈密尔顿图.(2)是欧拉图，而不是哈密尔顿图.(3)是哈密尔顿图，而不是欧拉图.(4)既不是欧拉图，也不是哈密尔顿图.9.今有 a，b，c，d，e，f，g 7 个人，已知下列事实：a 会讲英语；b 会讲英语和汉语；c 会讲英语、意大利语和俄语；d 会讲日语和汉语；e 会讲德语和意大利语；f 会讲法语、日语和俄语；g 会讲法语和德语. 试问这 7 人应如何排座位，才能使每个人都能和他身边的人交谈?做无向图 G=<V，E>，V 为此人群中的成员，E={(u，v)|，u与 u 有共同语言}如下图所示，该图存在哈密尔顿回路，如图中实线边所示回路为哈密尔顿回路 C=abdfgeca.按他们在 C 中顺序 安排座位即可.第 18 周习 题 十1.求图 10.15 所示平面图各面的次数.R1，R2，R0，的次数分别为 7，3，102.证明图 10.16 所示各图均为平面图. 图 4 图 5 图 6图 1、2、3 分别是图 4、5、6 的平面嵌入。3.证明图 10.17 所示无向图 G 为平面图，且为极大平面图.容易找出图 10．17 所示图的平面嵌入，所以它是平面图，且每个面的次数都是 3，所以它是极大平面图. (a) (p∧q)∨(p∧r). 1，3，6，7 (2)用主析取范式求下列各式的主合取范式：(a) (p∧q)∨r. 主析取范式 1，3，5，6，7 主合取范式 0，2，4第 3 周25.构造下面推理的证明： (1)前提：(p∧q)，q∨r，r 结论：p证明：①q∨r 前提引入②r 前提引入③q ①② 析取三段论④(p∧q) 前提引入⑤p∨q ④ 置换⑥p ③⑤ 析取三段论推理正确(2)前提：p(qs)，q，p∨r 结论：rs证明：①p(qs) 前提引入②p∨r 前提引入③rp ② 置换 ④r(qs) ①③ 假言三段论⑤q(rs) ④ 置换⑥q 前提引入⑦rs ⑤⑥ 假言推理推理正确(3)前提：pq 结论：p (p∧q)证明：①pq 前提引入②p∨q ① 置换③(p∨p)∧(p∨q) ② 置换④p∨(p∧q) ③ 置换⑤p(p∧q) ④ 置换推理正确26.用归谬法证明 25 题中的(1)，用附加前提证明法证明 25 的(2)与(3).25.(2)证明：①p(qs) 前提引入②p∨r 前提引入③r 附加前提引入④p ②③ 假言推理⑤qs ①④ 假言推理 ⑥q 前提引入⑦s ⑤⑥ 假言推理推理正确25.(3)证明：证明：①pq 前提引入②p 附加前提引入③q ①② 假言推理④p∧q ②③ 合取推理正确27.如果他是理科学生，他必学好数学.如果他不是文科学生，他必是理科学生.他没有学好数学.所以他是文科学生.上述推理是否正确?证明你的结论.设 p：他是理科学生. q：他是文科学生. r：他必学好数学.前提：pr，qp，r结论：q证明：①pr 前提引入②r 前提引入③p ①② 拒取式④qp 前提引入⑤q ③④ 拒取式 第 4 周习 题 二l.在一阶逻辑中将下面命题符号化：(1)有的整数是自然数.F(x)：x 是整数，G(x)：x 是自然数．x(F(x)∧G(x))(2)没有小于零的自然数.F(x)：x 小于零. G(x)：x 是自然数．x(G(x)F(x))2.取个体域为整数集，给定下列各公式：(1) xy(xy=0)(2) xy(xy=1)给出各公式的涵义，并讨论它们的真值.(1)对任意的整数 x，存在整数 y，使得 xy=0. 真命题(2)对任意的整数 x，存在整数 y，使得 xy=1. 假命题3.在下列各式中，哪些是指导变项? x，y，z 的哪些出现是自由的?哪些出现是约束的?(1) y (F(x，y) G(y，a) )y 是指导变项，出现是约束的. x 是自由的.(3) F(z)  (xyG(x，y，z))z 是自由的. x，y 是指导变项，出现是约束的.7.设解释 I：个体域 D 为自然数集，a = 0，f(x，y)=x+y， g(x，y)=xy ，F(x，y) 为 x=y .在 I 下，下列哪些公式为真? (1) xF(g(x，a)，x) x(x0 = x) 假命题(2) xy (F(f(x，a)，y) F(f(y，a)，x)) xy (x = y  y = x) 真命题8.设解释 I：个体域 D 为实数集合，a=0，f(x，y)=x－y， F(x，y) 为 x<y.在 I 下，下列哪些公式为真?(1) xF(f(a，x)，a) x( x<0 ) 假命题(3) xyz(F(x，y) F(f(x，z)，f(y，z)))  xyz( (x<y)  (xz) < (yz)) 真命题第 5 周4.给定解释 I 如下：个体域 D={a，b}， F(a，a)=1，F(a，b)=0，F(b，a)=0，F(b，b)=1.求下列各式在 I 下的真值：(1) x yF(x，y) 真值 1(3) x yF(x，y) 真值 010.求下列各式的前束范式：(2) xF(y，x)  yG(x，y) vu F(y，v)  G(x，u)(3) x(F(x，y)  yG(x，y)) xy (F(x，z)  G(x，y))第 6 周习 题 三4.确定下列命题是否为真：(1)    真 (2)   假(3)   {} 真 (4)   {} 真 (5) {a，b}  {a，b，c，{a，b，c}} 真(6) {a，b}  {a，b，c，{a，b，c}} 真(7) {a，b}  {a，b，{{a，b，c}}} 真(8) {a，b}  {a，b，{{a，b，c}}} 假5.求下列集合的幂集：(1) {1，2，3} P(A)={  ， {1} ， {2} ， {3} ， {1 ， 2} ， {2 ， 3} ， {1 ， 3} ，{1，2，3}}(2) {1，{2，3}}P(A)= { ，{1}，{{2， 3}}，{1，{2，3}}}(5) {{1，2}，{2，1，1}，{2，1，1，2}}P(A)={ ，{{1，2}}}6.设 E={1，2，3，4，5，6}，A={1，4}，B={1，2，5}，C={2，4} 求 A∪B，A∩B，A－B，ABA∪B={1，2，4，5}，A∩B={1}，A－B ={4}，AB ={2，4，5}13.设 A，B，C 是集合，证明：(1) (A－B)－C=A－(B∪C)证明：(2) (A－B)－C=(A－C)－(B－C)证明：(3) (A－B)－C=(A－C)－B证明： 14.设 A，B，C 是集合，证明：C  A∧C  B  C  A∩B证明： x C，由 C  A∧C  B，则 x A∩B，C  A∩B x  C 由 C  A∩B，x  A∧x B，则 x  C  A∧C  B15.设 P，Q 为集合，证明：P  Q  P－Q  ~P证明：P－Q  ~P  P∩~Q  ~P  P  ~(P∩~Q)  P  ~P∪Q  P  Q第 7 周习 题 四1.已知 A={，{}}，求 A×P(A){，，，｛｝，，｛｛｝｝，，｛，｛｝｝，，｛｝，，｛｝，｛｝，｛｝，｛｛｝｝，｛｝，｛，｛｝｝}4.列出集合 A={1，2，3}上的恒等关系 IA，全域关系 EA， 小于等于关系 LA，整除关系 DA.LA={1，1，1，2，1，3，2，2，2，3，3，3}DA={1，1，1，2，1，3，2，2，3，3}6.设 A={1，2，4，6}，列出下列关系 R：(1) R={x，y| x，yA∧x+y2 }R={1，1，1，4，1，6，2，2，2，4，4，6，6，6，2，1，4，1，6，1，4，2，6，2，6，4}(2) R={x，y| x，yA∧|x－y|A}