离散数学习题集含答案

离散数学试题答案试卷
填空 20 （题2分）
A B

C

1．设 （N：然数集E+ 正偶数） {012346}
2．ABC表示三集合文图中阴影部分集合表达式

3．设PQ 真值0RS真值1
真值 1
4．公式合取范式
5．解释I域D仅包含元素 I真值 1
6．设A{1234}A关系图R2 {<>
7．设A{abcd}偏序关系R哈斯图 R {<>} IA


8．图补图
9．设A{abcd} A二元运算：

*
a b c d
a
b
c
d
a b c d
b c d a
c d a b
d a b c
代数系统幺元 a 逆元元素 a b c d逆元分 a d c d
10．图示偏序集中格 c










二选择 20 （题 2分）
1列真命题（CD　　　）
A． B．C． D．
2列集合中相等（ BC ）
A．{43}B．{34}C．{433}D． {34}
3设A{123}A二元关系（ C ）
A． 23 B． 32 C． D．
4设RS集合A关系列说法正确（ A ）
A．RS 反 反
B．RS 反反 反反
C．RS 称 称
D．RS 传递 传递
5设A{1234}P（A）（A幂集）规定二元系
P（A） R（ D ）
A．A B．P(A) C．{{{1}}{{12}}{{123}}{{1234}}}
D．{{}{2}{23}{{234}}{A}}
6设A{{1}{13}{123}}A包含关系哈斯图（ C ）

7列函数双射（ A ）
A．f IE f (x) 2x B．f NNN f (n)
C．f RI f (x) [x] D．f IN f (x) | x |
（注：I—整数集E—偶数集 N—然数集R—实数集）
8图 中 v1v3长度3 通路（ D ）条

A． 0 B． 1 C． 2 D． 3
9图中Eular图Hamilton图图（ B ）

10棵树中7片树叶33度结点余4度结点该树（A ）4度结点
A．1 B．2 C．3 D．4
三证明 26
1R集合X反关系求证：R称传递仅
< a b> R中R中（8分）
1 证： R称性知R传递性
意 R称
R传递
2fg群< G2 *>态映射证明子群中C (8分)证
★★
★ < C ★> < G1 ★>子群
3 G (|V| v|E|e ) 面少k（k3）条边围成连通面图 证明彼森图（Peterson）图非面图（11分）
证：①设Gr面 （8分）
②彼森图样成立
彼森图非面图（3分）
四逻辑推演 16
CP规证明题（题 8分）
1
证明：① P（附加前提） ② T①I
③ P ④ T②③I
⑤ T④I ⑥ T⑤I
⑦ P ⑧ T⑥⑦I
⑨ CP
2
① P（附加前提） ② US①
③ P ④ US③
⑤ T②④I ⑥ UG⑤
⑦ CP
五计算 18
1设集合A{abcd}关系R{ < b a > < b c > < c d >}矩阵运算求出R传递闭包t (R) （9分）
解：


t (R){ < a c> < b b > < b c >
< b d > < c d > }
2图示赋权图表示某七城市预先算出间直接通信线路造价试出设计方案城市间够通信总造价　　（９分）

解： 库斯克（Kruskal）算法求产生优树算法略结果图：

树权C(T)23+1+4+9+3+1757总造价
试卷二试题答案
填空 20 （题2分）
1P：努力Q：失败非努力否失败翻译然努力失败翻译
2域D{12}指定谓词P公式真值 T
P (11)
P (12)
P (21)
P (22)
T
T
F
F
3设S{a1 a2 …a8}BiS子集B31表达子集
4设A{23456}二元关系R
R{<22><23><24><25><26><32><33><34><35><36><45><46><52><53><54><55><56>}（列举法）
R关系矩阵MR


5设A{123}A称反称关系R R{<12><13><21>} A称反称关系R R{<11><22><33>}
*
a b c
a
b
c
a b c
b b c
c c b
6设代数系统中A{abc}幺元 A 否幂等性 否 否称性

74阶群必 Klein四元群 群 循环群 群




8面偏序格分配格 B

9n结点完全图Kn边数 欧拉图充条件图中奇度结点连通
10公式根树表示
二选择 20 （题2分）
1述公式中重言式（ BD ）
A．B．
C． D．
2命题公式 中极项数（D）成真赋值数（ D ）
A．0 B．1 C．2 D．3
3设 （ D ）元素A．3 B．6 C．7 D．8
4设定义等价关系
R产 生划分（ B ）分块
A．4 B．5 C．6 D．9

5设S关系R关系图R具（ D ）性质

A．反性称性传递性 B．反反性反称性
C．反反性反称性传递性 D．反性
6设 普通加法法（ A ）域
A． B．
C． D． N
7面偏序集（ B ）构成格

8图中V1V4长度3 道路（ B ）条

A．1 B．2 C．3 D．4
9图中（ B ）欧拉图
10设10R实数集合普通法代数系统 （ C ）
A．群 B．独异点 C．半群
三证明 46
1 设RA二元关系
试证明RA等价关系SA等价关系（9分）
1（9分）
（1）S反R反
（2）S称

（3）S传递

（1）（2）（3）S等价关系
2逻辑推理证明：舞蹈者风度王华学生舞蹈者学生风度
证明：设P(x)：x 舞蹈者 Q(x) ：x风度 S(x)：x学生 a：王华
述句子符号化：
前提： 结： ……3分
① P ② P
③ US② ④ T①I
⑤ T③④I ⑥ T①I
⑦ T⑤⑥I ⑧ EG⑦
3AB函数定义函数意证明：fAB满射gB 单射（10分） 证明 ：



4图G中两奇数度结点两结点定连通（8分）
证明：设G中两奇数度结点分u v uv连通G少两连通分支G1G2 uv分属G1G2G1G2中含1奇数度结点图基定理矛盾uv定连通
5 设G具n结点简单图边数GHamilton图（8分）
证明： 证G中两结点n
反证法：存两结点uv 相邻令GV1具n2结点简单图边数G1GV1n2结点简单图题设矛盾G中两相邻结点度数少n
GHamilton图
四 计算 1设群里+6模6加法Z6{[0 ][1][2][3][4][5]}试求出子群相应左陪集解：子群<{[0]}+6><{[0][3]}+6><{[0][2][4]}+6><{Z6}+6>
{[0]}左陪集：{[0]}{[1]}{[2]}{[3]}{[4]}{[5]}
{[0][3]}左陪集：{[0][3]}{[1][4]}{[2][5]}
{[0][2][4]}左陪集：{[0][2][4]}{[1][3][5]}
2 权数149162536496481100构造棵优二叉树（7分）

试卷三试题答案
填空 20 （空 2分）
1 设 fg然数集N函数
2(x+1)
2 设A{abc}A二元关系R{< a a > < a b >< a c > < c c>}
s（R）
3 A{123456}A二元关系列举法
T
T关系图
T具 反称性反反性 性质
4 集合幂集
5 PQ真值0 RS真值1真值 1
6 合
7 设 P（x）：x素数 E(x)：x 偶数O(x)：x奇数 N (xy)：x整数y谓词然语言 意x果x素数存yy奇数y整x
8 谓词前束范式

二 选择 20 （题 2分）
1 述命题公式中重言式（ C ）
A B
C D
2 析取范式中含极项数（ C ）
A 2 B 3 C5 D0 E 8
3 定推理
① P ② US①
③ P ④ ES③
⑤ T②④I ⑥ UG⑤
推理程中错（ C ）
A①>② B②>③ C③>④ D④>⑤ E⑤>⑥
4 设S1{12…89}S2{2468}S3{13579}S4{345}
S5{35}条件X（ C ）集合相等
A XS2S5 BXS4S5 CXS1S2S4 DXS1…S5中集合等
5 设RSP关系P集合表示关系 （ A ）
A
B
C D
6 面函数（ B ）单射非满射
A
B
C
D
中R实数集Z整数集R+Z+分表示正实数正整数集
7设S{123}RS关系关系图R具（ D ）性质

A反称传递B什性质没C反反反称传递 D反称反称传递
8设（ A ）
A{{12}} B{12 } C{1} D{2}
9设A{1 2 3 }A（ D ）二元关系A23 B32 C D
10全体项合取式（ C ）A满足式 B矛盾式 C永真式 DABC
三 CP规证明 16 （题 8分）
1
① P（附加前提） ② T①I
③ P ④ T②③I
⑤ T④I ⑥ T⑤I
⑦ P ⑧ T⑥⑦I
⑨ CP
2

① P（附加前提） ② T①E
③ ES② ④ P
⑤ US④ ⑥ T③⑤I
⑦ EG⑥ ⑧ CP
四（14）
集合X{<12> <34> <56>… }R{<>|x1+y2 x2+y1}
1 证明RX等价关系 （10分）
2 求出X关R商集（4分）
1 证明：（1）反性：

（2）称性：


（3）传递性：





（1）（2）（3）知：RX先等价关系
2XR
五（10）
设集合A{ a b c d }关系R{< a b > < b a > < b c > < c d >}
求 1写出R关系矩阵关系图（4分）
2矩阵运算求出R传递闭包（6分）
关系图
2



t (R){ < a c> < b b > < b c > < b d > < c d > }
六（20）
1（10分）设fg函数证明函数
2（10分）设函数证明 左逆函数仅f入射函数
1（1）

（2）




2证明：




试卷四试题答案
填空 10 （题 2分）
1 PQ二命题真值0 仅 P真值1Q真值0
2 命题意定正实数存实数令F(x)：x实数命题逻辑谓词公式
3 谓词合式公式前束范式
4 量词辖域中出现 约束变元 指导变元交换变元符号公式余部分变种方法称换名规
5 设x谓词合式公式A客体变元A域DA(x)关y
yD某元素 称存量词消规记ES

二 选择 25 （题 分）
1 列语句命题（ AC ）
A明年中秋节晚晴天 B
C仅xy0 D正说谎
2 列命题中真值真命题（ AD ）
A 2+24仅3奇数 B2+24仅3奇数
C2+2≠4仅3奇数 D2+2≠4仅3奇数
3 列符号串合式公式（CD ）
ABCD
4 列等价式成立（ AD ）
AB
C D
5 Bwff（ BC ）
A称B前件 B称B效结
C仅D仅
6 AB二合式公式（ ABCDE ）
A重言式 B
C D E重言式
7 总死谓词公式表示（ C ）
（域全总体域）M(x)：xMortal(x)：x死
A B
CD
8 公式解释I：体域D{2}P(x)：x>3 Q(x)：x4A真值（ A ）A1 B0 C满足式 D法判定
9 列等价关系正确（ B ）
AB
CD
10 列推理步骤错（ C ）
① P ② US① ③ P
④ ES③ ⑤ T②④I ⑥ EG⑤
A②B④C⑤D⑥
三 逻辑判断30
1 等值演算法真值表法判断公式类型
（1）等值演算法

（2）真值表法 A重言式
P Q




A
1 1
1
1
1
1
1
1 0
0
1
0
0
1
0 1
1
0
0
0
1
0 0
1
1
1
1
1

2 列问题成立请证明成立请举出反例：（10分）
（1） 已知问成立？
（2） 已知问成立？
（1）成立取
AB定等价意等价公式
（2）成立 证明：
：

3 果厂方拒绝增加工资罢工会停止非罢工超年工厂撤换厂长问：厂方拒绝增加工资面罢工刚开始罢工否够停止（10分）
解：设P：厂方拒绝增加工资Q：罢工停止R罢工超壶年R：撤换厂长
前提： 结：
① P ② P
③ T①②I ④ P
⑤ T④I ⑥ T⑤E
⑦ T③⑥I 罢工会停止效结
四计算10
1 设命题A1A2真值1A3A4真值0求命题
真值（5分）
解：
2 利析取范式求公式类型（5分）
（1）
成真赋值矛盾式
五谓词逻辑推理 15
符号化语句：喜欢花喜欢杂草花杂草推证结
解：


证明：⑴ P ⑵ ES⑴
⑶ T⑵I ⑷ T⑵I
⑸ P ⑹ US⑸
⑺ T⑶⑹I ⑻ T⑺E
⑼ US⑷ ⑽ US⑻
⑾ T⑼⑽I ⑿ UG⑾
六证明：（10）
设域D{a b c}求证：

试卷五试题答案
填空15（空3分）
1设G9阶图结点度数56G中少 6 5度结点
2n阶完全图Kn点数X (Kn) n
3图 中v1v2长度2通路 2 条
4设[R+·]代数系统果①[R+]交换群 ②[R·]半群
③ +·分配·+分配均成立 称[R+·]环
5设代数系统满足幂等律
二选择15（题3分）
1 面四组数构成简单图度数列（ AB ）
A（22222） B（11223）C（11222） D（01333）
2 图中哈密顿图（ BD ）

3 果图D强连通图D欧拉图命题真值（ B ）A真B假
4 列偏序集（ C ）构成格

5 设*普通法[S*]（D）
A代数系统 B半群 C群 D
三证明 48
1（10）少2群中少2 相朋友数
证明：n顶点v1…vn表示n构成顶点集V{v1…vn}设图G（VE）
现证G中少两结点度数相
事实（1）G中孤立点数等2结成立
（2） G中孤立点G中少3顶点考虑孤立点设G中结点度数均等1G简单图顶点度数等n1G中n顶点度数取值12…n1鸽巢原理必然少两结点度数相
2（8）图G中恰两奇数度顶点两顶点连通
证：设G中两奇数度结点分uv uv连通少两连通分支G1G2uv分属G1G2G1G2中含奇数度结点握手定理矛盾uv必连通
3（8）证明6结点12条边连通面简单图中 面面数3
证：n6m12 欧拉公式nm+f2知 f2n+m26128
图基定理知：必面3条边围成
4（10）证明循环群态必循环群
证：设循环群[A·]生成元a态映射f态[f（A）*]
n1
n2
nk1时
nk时
表明f(A)中元素均表示[f(A)*]f(a) 生成循环群
5（12）设布尔代数定义运算*
求证[B*]阿贝尔群
（1） 交换律：
（2） 结合律：

：


（3） 幺：


（4） 逆：

综述：[B*]阿贝尔群
四计算22
1二叉树中
1） 求带权23578优二叉树T（5分）
2） 求T应二元前缀码（5分）
2 图示带权图中优投递路线求出投递路线长度（邮局D点）

（1）（5分）Huffman方法佳二叉树：


（2）（5分）佳前缀码：000001011011
2（12分）
图中奇数点EF d(E)3d(F)3d(EF)28 pEGF
复制道路EGGF图GG欧拉图
D开始找条欧拉回路：DEGFGEBACBDCFD
道路长度：
35+8+20+20+8+40+30+50+19+6+12+10+232


试卷六试题答案
填空 15 （题 3分）
1 n阶完全图结点v度数d(v) n1
2 设n阶图G中m条边结点度数kk+1G中Nkk度顶点Nk+1k+1度顶点N k n(k+1)2m
3 算式 二叉树表示

4 图出格Le补元 0
5组学生二二扳腕子赛法测定臂力
幺元 臂力者
二选择 15 （题 3分）
1设S{0123}≤等关系{S≤}
（ D ）A群B环C域D格
2设[{a b c}*]代数系统*运算：
*
a
b
c
a
a
b
c
b
b
a
c
c
c
c
c
零元（ C ）Aa Bb Cc D没

3右图 相完全图K5补图（ A ）

4棵树T7片树叶33度顶点余顶点均4度T（ A ）4度结点
A1 B2 C3 D4
5设[A+·]代数系统中+·普通加法法A（ D ）时[A+·]整环
A B
C D
三证明 50
1设G（nm）简单二部图（10分）
证：设G（VE）
完全二部图
时完全二部图边数m值
意简单二部图
2设G具n结点简单图G连通图（10分）
证：反证法：G连通妨设G分成两连通分支G1G2假设G1G2顶点数分n1n2显然


假设矛盾G连通
3记开1关0反映电路规律代数系统[{01}+·]加法运算法运算：
+
0
1



·
0
1
0
0
1
0
0
0
1
1
0
1
0
1
证明环域（14分）
（1）[{01}+·]环
①[{01}+]交换群
：+运算表知封闭性运算表称性知：+运算交换
群： （0+0）+00+（0+0）0 （0+0）+10+（0+1）1
（0+1）+00+（1+0）1 （0+1）+10+（1+1）0
（1+1）+11+（1+1）0 …… 结合律成立
幺：幺元0 逆：01逆元均身
②[{01}·]半群
：· 运算表知封闭
群： （0·0）·00·（0·0）0 （0·0）·10·（0·1） 0
（0·1）·00·（1·0）0 （0·1）·10·（1·1）0
（1·1）·11·（1·1）0
③·+分配律
Ⅰ 0·（x+y）00+0(0·x)+(0·y) Ⅱ 1·（x+y）
xy (x+y)0

（）

均
理证：
·+ 分配 ①②③[{01}+·]环
（2）[{01}+·]域
[{01}+·]限环需证明整环
①交环： 法运算表称性知法交换②含幺环：法幺元1
③零子：1·11≠0 [{01}+·]整环域
4 代数格≤然偏序[L≤]偏序格（16分）
证：（1 ）≤偏序关系 ≤ 然偏序
①反反性：代数格幂等关系：
②反称性： ：

③传递性：：


（2）L中存{xy}（）确界
设：
事实：

{x y }界c
{x y }界
理证确界情况
四10 (1)设布尔代数布尔表达式试写出析取范式合取范式（10分）
解：函数表：




0
0
0
0
0
0
1
1
0
1
0
0
0
1
1
1
1
0
0
0
1
0
1
1
1
1
0
1
1
1
1
1
析取范式：
合取范式：
五10
图示赋权图表示某七城市预先算出间直接通信成路造价（单位：万元）试出设计方案城市间够通信总造价

解： 库斯克（Kruskal）算法求产生优树算法：

结果图：
树权C(T)23+1+4+9+3+1757（万元）总造价
试卷七试题答案
填空 15 （题 3分）
1 (nm) 图G (VE) 边顶点数关系
2 n 奇数 时非完全图Kn欧拉图
3 已知棵树T三3顶点2度顶点余1度顶点T中 5 1度顶点
4 n阶完全图Kn点色数X(KN) n
5 组学生两两扳腕子赛测定臂力幺元 臂力者
二 选择 15 （题 3分）
1面四组数构成图度数列( B )
　 A 234567 B 12234
C 21112 D 33560

2图 邻接矩阵( C )

ABCD
3列图简单图( B )
AG1(V1E1) 中 V1{abcde}E1{abbeebaede}
BG2(V2E2)中V2V1E2{}
CG(V3E3) 中V3V1E3{abbeedcc}
DG(V4E4)中V4V1E4{（aa）（ab）（bc）（ec）（ed）}
4列图中欧拉图( B )

5中集合称差运算方程解（ A ）A B C D
三 证明 34
1 证明：少2 群中少2 相朋友数（8分）
证明：n顶点v1…vn表示n构成顶点集V{v1…vn}设图G（VE）
现证G中少两结点度数相事实（1）G中孤立点数等2结成立
（2）G中孤立点G中少3顶点现考虑孤立点设G中结点度数均等1G简单图顶点度数等n1G中顶点数值12…n1n1数取n1值n顶点度数少两结点度数相
2 图G中恰两奇数顶点两顶点连通（8分）
证：设G中两奇数度结点分uv uv连通中通路少两连通分支G1G2uv分属G1G2G1G2中含奇数度结点握手定理矛盾uv必连通
3 证明：6结点12条边连通面简单图中面面度3（8分）
证：n6m12 欧拉公式nm+f2知 f2n+m26128
图基定理知：必面3条边围成
4 证明循环群态必循环群（10分）
证：设循环群[A·]生成元a态映射f态
n1
n2
nk1时
nk时
表明f(A)中元素均表示f(a) 生成元循环群
四 中国邮递员问题13
求带权图G中优投递路线邮局v1点
解：图中4奇数结点
（2） 求两结点短路

找两条道路没相起点终点长度总短：
（3） 原图中复制出设图G图G中结点度数均偶数图G存欧拉回路欧拉回路C权长43





五 根树应 13
通讯中八进制数字出现频率：
0：301：202：15 3：104：105：56：57：5
求传输佳前缀码（写出求解程）
解：100频率排列权数

（4） Huffman算法求优二叉树：

（5） 前缀码 00000传送 500001传送 60001传送 7100传送 3101传送 4001传送 211传送 101传送 0 （频率越高传送前缀码越短）
六 10设B4{e a b ab }运算*表
*
























群（称作Klein四元群
证明：
（1） ：运算表知运算*封闭
（2） 群：证明里 4364等式需验证
：① e幺元含e等式定成立
②aba*bb*a果含ab等式成立含abab等式成立
③剩需验证含ab等式238等式：
(a*b)*aab*aba*(b*a)a*abb (a*b)*bab*baa*(b*b)a*ea
(a*a)*ae*aaa*(a*a)a*ea (a*a)*be*bba*(a*b)a*abb
(b*b)*ae*aab*(b*a)b*aba (b*b)*be*bbb*(b*b)b*eb
(b*a)*aab*abb*(a*a)b*eb (b*a)*bab*bab*(a*b)b*aba
（3） 幺： e幺元
（4） 逆：e 1e a 1a b 1b (ab) 1ab 群
试卷八试题答案
填空 15 （题 3分）
1 n阶完全图Kn边数
2 右图 邻接矩阵A
3 图偶图

*
a
b
c
a
a
b
c
b
b
a
c
c
c
c
c



4 完全二叉树中叶数nt边数m
5 设< {abc} * >代数系统* 运算：幺元 a 零元 c
abc逆元分 ab没

二选择 15 （题 3分）
6 图相完全图补图（ A ）


7 图G 分（ A ）
A222 B112 C212 D122

8 棵树T8顶点4度3度2度分枝点1余顶点均树叶T中（C ）片树叶 A3 B4 C5 D6
9 设代数系统中+·普通加法法A（ D ）时整环
A B
C D
10 设A{12…10 }面定义运算*关A封闭（ AC ）
A x*ymax(x y) Bx*y质数p数
Cx*ygcd(x y) (gcd (x y)表示xy公约数)
Dx*ylcm(x y) （lcm(x y) 表示xy公倍数）
二 证明 45
1设G（nm）简单二部图（8分）
设G（VE）
完全二部图
时完全二部图边数m值意简单二部图
2设G具n结点简单图G连通图（8分）
反证法：G连通妨设G分成两连通分支G1G2假设G1G2顶点数分n1n2显然

假设矛盾G连通
3设G阶数11简单图G中少非图（14分）
（1）n11时边数条必边数等28妨设G边数设Gk连通分支G中必回路（否Gk棵树构成森林棵树顶点数ni边数mi
矛盾）
面反证法证明G非面图
假设G面图G中回路G简单图回路长等3 G面少g ()条边围成点边面数关系：

矛盾G非面图
（2）n>11时考虑G具11顶点子图必非面图
果非面图非面图 果非面图非面图
4记开1关0反映电路规律代数系统[{01}+·]加法运算法运算：
+
0
1



·
0
1
0
0
1
0
0
0
1
1
0
1
0
1

证明环域（15分）
1）[{01}+·]环
①[{01}+]交换群
：+运算表知封闭性运算表称性知：+运算交换
群： （0+0）+00+（0+0）0 （0+0）+10+（0+1）1
（0+1）+00+（1+0）1 （0+1）+10+（1+1）0
（1+1）+11+（1+1）0 ……
结合律成立
幺：幺元0
逆：01逆元均身<{01}+>Abel群
②<{01}·>半群
：· 运算表知封闭
群： (0·0)·00·（0·0）0 （0·0）·10·（0·1）1
（0·1）·00·（1·0）1 （0·1）·10·（1·1）0
（1·1）·11·（1·1）0 …
③·+分配律

Ⅰ 0·（x+y）00+0(0·x)+(0·y)
Ⅱ 1·（x+y）
xy (x+y)0

（）

均
理证：
·+ 分配
①②③<{01}+·>环
（2）<{01}+·>域
<{01}+·>限环需证明整环
①交环： 法运算表称性知法交换
②含幺环：法幺元1
③零子：1·11≠0
[{01}+·]整环域



三 生成树应 10
1（10分）图示赋权图表示某七城市预先测算出间直接通信线路造价试出设计方案城市间够通信总造价　　





解： 库斯克（Kruskal）算法求产生优树算法略结果图：

树权C(T)23+1+4+9+3+1757总造价
2（10分）构造HAPNEWR应前缀码画出该前缀码应二叉树写出英文短语HAPPY NEW YEAR编码信息
二叉树知







HAPYNEWR应编码分
000001010011100101110111
显然{000001010011100101110111}前缀码
英文短语HAPPY NEW YEAR 编码信息
000 001 010 010 011 100 101 001 001 101 001 111


四 5
实数集合R表列二元远算否具左边列中性质请相应位填写YN

Max
Min
+
结合性



交换性



存幺元



存零元





Max
Min
+
结合性
Y
Y
Y
交换性
Y
Y
Y
存幺元
N
N
Y
存零元
N
N
N

试卷九试题答案
填空 30 （空 3分）
1 选择合适域谓词表达集合A直角坐标系中单位元（包括单位圆周）点集A
2 集合A{{}}幂集P(A)
3 设A{1234}A二元关系R{<12><21><23><34>}画出R关系图

4 设A{<12><2 4 ><3 3 >} B{<13><24><42>} {< 1 2 > < 2 4 > <3 3 > < 13 ><24> <42>} {< 1 4 > < 2 2 > }
5 设|A|3A 29 二元关系
6 A{123}关系R {< 1 1 > < 2 2 > <3 3 > 时R称反称
7 偏序集哈斯图 {}
8 设|X|n|Y|m（1）XY mn 函数
（2）n m满足 nm 时存双射 n 双射
9 理数真值 假
10 Q：海R：时间公式
然语言 海仅空
11 公式合取范式
12 集合A分划应满足
二 选择 20 （题 2分）
1 设全集I列相等集合（ AD ）
A B
C D
2 设S{NQR}列命题正确（ C ）
A B
C D
3 设C{{a}{b}{ab}}分（ B ）
AC{ab}B{ab}C{ab}{ab}DCC
4 列语句命题（ AE ）
A x13 B离散数学计算机系门必修课 C鸡三脚
D太阳系外星球生物 E算考硕士研究生？
5 合取范式（ BD ）
A B
C D
6 设|A|nA（C）二元关系
A2n Bn2 C Dnn E
7 7设r集合A相容关系简化关系图（图）
[I] r产生相容类（ BD ）
A B C D
[II] A完全覆盖（ C ）

A B
C D
8 集合A{1234}偏序关系图 哈斯图（ A ）

9 列关系中构成函数（ B ）
AB
C D
10N然数集定义（x3余数）
f（ D ）A满射单射B单射满射C双射D单射满射
三 简答题 15
1(10分)设S{1 2 3 4 6 8 12 24}S整关系问：（1）偏序集Hass
(1)≤{<12><13><14><16><18><112><124><24><26><28><212><224><36><312><324><48><412><424><612><624><824><1224>}
covS{<12><13><24><26><36><48><412><612> <824><1224>}
Hass图








（2）极元元1极元元 24
2（5分）设解释R：DR实数集DR中特定元素a0DR中特定函数特定谓词问公式涵义？真值？
解：公式A涵义：意实数xyz果x A真值： 真（T）
四 逻辑推理 10
者逻辑难学者少数学生喜欢果数学容易学逻辑难学果许学生喜欢逻辑数学难学








五10
设X{12345}X关系R{<11> < 1 2 > <2 4 > < 3 5 > < 4 2 > }Warshall方法求R传递闭包t (R)










六证明 15
1 限全序集必良序集（7分）
2 设复合函数果满射满射（8分）













试卷十试题答案
填空 10 （题 2分）
1 PQ二命题真值1仅 PQ真值相
2 公式中变元进行代入
公式
3 前束范式
4 设x谓词合式公式A客体变元A域DA（x）关y
称全称量词消规记US
5 非门逻辑网络

二 选择 30 （题 3分）
1 列符号串合式公式（ BC ）
A B
C D
2 列语句命题（ AC ）
A2素数Bx+5 > 6C球外星球D朵花呀
3 列公式重言式（ B ）
ABCD
4 列问题成立（ CD ）
A B
C D
5 命题逻辑演绎CP规（ C ）
A 推演程中便前提
B推演程中便前面演绎出某公式逻辑结果
C果演绎出公式形式B作前提设法演绎出C
D设含公式A命题公式B换中A
6 命题喜欢花逻辑符号化（ D ）
设D：全总体域F（x）：x花M(x) ：xH(xy)：x喜欢y
AB
CD
7 公式换名（ A ）
AB
CD
8 定公式D{ab}时解释（ BC ）该公式真值0
AP(a)0P(b)0BP(a)0P(b)1CP(a)1P(b)0DP(a)1P(b)1
9 面蕴涵关系成立（ BD ）
A
B
C
D
10列推理步骤错（ C ）
① P ② US①
③ ES② ④ UG③
⑤ EG④
A①→②B②→③C③→④D④→⑤

三 逻辑判断 28
1（8分）列命题相容？
① P ②A P ③B T①②I
④ P ⑤ T④E ⑥ T⑤I
⑦F T③⑥I 相容
2（10分）范式方法判断公式 否等价

两式等价
3（10分）列前提结否效？
天者天晴者雨果天晴电影电影书书时说明天雨
设P：天天晴Q：天雨R：书S：电影
符号化：
① P ② P ③ T①②I
④ T③I ⑤ P ⑥ T⑤E
⑦ T④⑥I 结效
四 计算 12
1（5分）定3命题：P：北京天津口Q：21R：15素数 求复合命题：真值
解：PQ真命题R假命题

2（7分）定解释I：D{23}L（xy）L( 2 2 ) L ( 3 3 ) 1 L ( 2 3 ) L (3 2 )0 求谓词合式公式真值








五 逻辑推理20
1（10分）理数实数某理数整数某实数整数
解：设R(x)：x实数Q(x)：x理数I(x)：x整数
符号化：前提：结：
① P ② ES①
③ P ④ US③
⑤ T②I ⑥ T④⑤I
⑦ T②I ⑧ T⑥⑦I
⑨ EG⑧
2（10分）符号化语句：病相信医生病相信骗子医生骗子推证结
解：F(x)：x病G(x)：x医生H(x)：x骗子L(xy)：x相信y
符号化：前提：
结：
⑴ P ⑵ ES⑴
⑶ T⑵I ⑷ T⑵I
⑸ P ⑹ US⑸
⑺ T⑶⑹I ⑻ T⑺E
⑼ US⑷ ⑽ US⑻
⑾ T⑼⑽I ⑿ UG⑾
卷十试题答案
填空 20 （题 2分）
1 够断真假阵述句 称命题
2命题P→Q真值0仅 P真值1Q真值0
3命题含4原子命题赋值 2416 种
4项析取式 永真式
5令P（x）：x质数E（x）：x偶数Q（x）：x奇数D（xy）：xy 汉语翻译
意两数xy果x偶数yy定偶数
6设S{ab c} S6集合表示 S110{ab}
7P（P()） 8
9设R集合A关系t（R）
10R 集合A偏序关系R满足 反性反称性传递性
二 选择 20 （题 2分）
1 列命题正确（ AD ）
A 满射满射 B满射满射
C单射单射D单射单射
2 设fg函数（ B ）时fg
A B
C D
3 列关系（ CD ）构成函数
A
B
C
D
4 列函数（ CD ）满射（ AD ）单射（ B ）双射般函数（ D ）
A B（3余数）
CD
5 设RS集合A关系列（ A ）断言正确
A 反反B称称
C传递传递D反称反称
6 设X集合|X|nX（ D ）种关系
An2 B2n C D

7 集合A{1234}偏序关系Hass图（ C ）

8 设集合A{12345}偏序关系Hass图

子集B{234}元（ A ）元（ A ）极元（ A ）极元（ A ）界（ A ）确界（ A ）界（ A ）确界（ A ）
A 42341144 B4523451144
C423451144 D4234114
9 设RS集合A关系列（ A ）断言正确
A 反反B称称
C传递传递D反称反称
10 设X集合|X|nX（ D ）种关系
An2 B2n C D
11 列推导错（ C ）A② B③ C④ D
① P ② US①
③ ES② ④ UG③
11没犯错误逻辑符号化（ BD ）
设H（x）：x P（x）：x犯错误
A B
C D
三 命题演绎28
1（10分）反证法证明




2（8分）CP规证明





3（10分）演绎推理：理数实数理数实数虚数实数虚数理数理数




四 8
化等价前束范式






五8
A{abcd}R{}A关系利矩阵法求R传递闭包画出t（R）关系图





六证明16
1 （8分）设A{1234} P（A）规定二元关系：
P（A）
证明RP（A）等价关系写出商集P（A）R





2 （8分）设fAA满射证明fIA






卷十二试题答案
填空 20 （空 2分）
1 设集合A{12345678910}定义A二元关系≤
x ≤ y x|y LCM（xy）
2 设定义A二元运算普通法法加法代数系统中运算*关 法 运算具封闭性
3 设集合S{αβγδζ}S运算*定义
*
α
β
γ
δ
ζ
α
α
β
γ
δ
ζ
β
β
δ
α
γ
δ
γ
γ
α
β
α
β
δ
δ
α
γ
δ
γ
ζ
ζ
δ
α
γ
ζ

代数系统中幺元 α β左逆元 δ
左逆元元素 γζ
4 群坯半群独异点群中 群 满足消律
5 设元素生成循环群|G|n
G
6 拉格朗日定理说明群子群建立G中等价关系
R |G|n |H|m mn关系
7 设f群群<*>态映射中幺元
f态核Ker(f )
二 选择 20 （题 2分）
1设f群群<*>态映射ker (f)（ B ）
A子群 BG子群 C包含 D包含G
2设 环a·b关+逆元（ BC ）
A(a)·(b) B(a)·b Ca·(b) Da·b
3设 代数系统Abel群果满足（ D ）域
A独异点·+分配B独异点零子·+分配
CAbel群零子 DAbel·+分配
4设代数系统+·普通加法法运算A（ A ）时域
A B
C D
5设格格诱导代数系统（ B ）成立
AB
C
D
6设偏序集定义：A（ A ）时格
A{1234612} B{1234681214} C{123…12} D{1234}
7设格诱导代数系统时（A ）模格A B
C D
8（ D ）中补元唯
A界格 B补格 C分配格 D补分配格
9布尔代数中仅（ C ）
A B C D
10设布尔代数fAnA函数（ CD ）
A f布尔代数 Bf表示成析取范式表示成合取范式
CA{01}f定表示成析取范式表示成合取范式
Df布尔函数定表示成析（合）取范式
三设A{12}A函数集合记AA 函数复合运算试出AA运算运算表指出AA中否幺元元素逆元
|A|2A224函数令中：


























AA中幺元逆元
四证明42
1 设代数系统*R二元运算0幺元独异点（8分）
证明：
[幺]

[] +·R封闭*R封闭
[群]

〈R*〉独异点
2 设n阶循环群G(a)设bak 元素b阶里dGCD ( n k )（10分）
证明：（1）

（2）b阶n1b阶m（1）（2）知元素b阶
3 证明果f态映射g态映射态映射（6分）

态映射
4 设含幺环意a·aa|A|≥3整环（8分）
证明：反证法：果整环|A|≥3
整环中零子矛盾
整环

5 K{ 1 2 5 10 11 22 55 110 }110整子集合证明：具全界110全界1代数系统< K LCM GCD ˊ >布尔代数（）（10分）
证明：代数系统 格诱导Hasst图
Hass图中存五元素格构子格
格分配格
（2）

元素补元补格
布尔代数
五布尔表达式 10
设布尔代数布尔表达式试写出析取范式合取范式（10分）
解：函数表：




0
0
0
0
0
0
1
1
0
1
0
1
0
1
1
1
1
0
0
1
1
0
1
1
1
1
0
1
1
1
1
0
析取范式：
合取范式：
试卷十三试题答案
填空 10 （题 2分）
1*表示求两数公倍数运算（Z表示整数集合）*运算幺元 1 零元 存
2代数系统中|A|>1果分幺元零元
关系
3 设群阿贝尔群充条件

4图完全关联矩阵







1
1
1
0
0

1
0
0
0
1

0
1
0
1
1

0
0
1
1
0

5图面图充条件 包含K3 3K52度结点构子图
五 选择 10 （题 2分）
1 面集合N子集（ AD ）集合普通加法运算封闭
A{x | x 幂16整} B{x | x 5互质}
C{x | x30子} D{x | x30倍数}
2 设中表示模3加法*表示模2法积代数幺元（ B ）A<00> B<01> C<10> D<11>
3 设集合S{1236}≤整关系代数系统< S ≤ >（ C ）
A域 B格布尔代数 C布尔代数 D代数系统
4 设n阶图Gm条边结点度数kk+1G中Nkk度结点
Nk（ D ）An·k Bn(k+1) Cn(k+1)m Dn(k+1)2m
5 棵树7片树叶33度结点余全4度结点
该树（ A ）4度结点A1 B2 C3 D4
三判断10 （题 2分）
1（ Y ）设S{12}S普通加法法运算封闭
2（Y）布尔格中A中意原子a非零元b中仅成立
3（ N ）设+·普通加法法域
4（ N ）条回路棵生成树少条公边
5（ N ）没T棵m叉树t片树叶i分枝点(m1)i t1
四证明 38
1（8分）代数系统*A二元运算eA中幺元果*结合元素右逆元（1）中元素右逆元必定左逆元
（2）元素逆元唯
证明：
（1）设ba右逆元cb右逆元

ba左逆元
（2）设元素a两逆元bc
a逆元唯
2（12分）设布尔代数果A定义二元运算☆阿贝尔群
证明：
[] 运算☆A封闭
[群]

☆满足结合性
[幺]
全界0A中关运算☆幺元
[逆]
A中元素身逆元
[交]
运算☆具交换性
Abel群
3（10分）证明环态象环
证明
设环关态映射f态象
Abel群易证Abel群
半群易证半群
现需证：分配


理证
环
4（8分）面少k(k≥3)条边围成连通面图
证明：
设Gr面


五应 32
1 （8分）某年级9门选修课程期末考试前必须提前9门课程考完天午考门课课程表示结点时选两门课程两点间边（图右）问少需天？
解：少考试天数
WelchPowell方法G着色：
第种颜色点 剩余点
第二种颜色点 剩余点
第三种颜色点
≤3
构成圈≥3
3
三天午考完全部九门课程
2 washall方法求图达矩阵判断图连通性（8分）
：

1：A[21]1 2： A[42]1
3： A[13]A[23]A[43]1
4： A[k4]1k1234
p中元素全1G强连通图然单连通弱连通
3 设abcdefg七分会讲语言：a：英b：汉英c：英西班牙俄d：日汉e：德西班牙f：法日俄g：法德否七座位安排圆桌旁均旁边交谈？（8分）
解：abcdefg 7结点表示7两
交谈条边连结图
图中Hamilton回路圆桌安排座位序
Hamilton回路a b d f g e c a
4 Huffman算法求出带权235789优二叉树T求W（T）
传递a b c d e f 频率分2 3 5 7 8 9求传输佳前缀码（8分）
解：(1)


（1） 0000传输a0001传输b001传输c01传输f10传输d11传输e
传输优前缀码{00000001001011011}




试卷十四试题答案
填空 10 （题 2分）
1设限布尔格诱导代数系统S布尔格中原子集合～

2集合S{αβγδ}二元运算*
*
α
β
γ
δ
α
δ
α
β
γ
β
α
β
γ
δ
γ
β
γ
γ
γ
δ
α
δ
γ
δ

+3
[0]
[1]
[2]
[0]
[0]
[1]
[2]
[1]
[1]
[2]
[0]
[2]
[2]
[0]
[1]

代数系统中幺元 β α逆元 　γ　　 　
3 设I整数集合Z3模3余类组成余类集Z3定义+3：
+3运算表 否构成群
4 设Gn阶完全图G边数m
5 果台计算机条加法指令计算四数现28数需计算少执行 9 次加法指令
五 选择 20 （题 2分）
1 理数集Q定义二元运算*Q中满足（ C ）
A 元素逆元 B唯逆元 C时逆元 D元素逆元

2 设S{01}*普通法< S * >（ B ）
A 半群独异点 B独异点群C群 D环群
3图 出格LL（ D ）
A分配格 B补格 C布尔格 D ABC
4 图D长度2通路（ B ）条
A0 B1 C2 D3
5Peterson图中少填加（ D ）条边构成Euler图
A1 B2 C4 D5


六 判断 10 （题 2分）
1 代数系统中果元素左逆元存定唯（ N ）
2 设群子群中幺元e中幺元（ Y ）
3 设 +·普通加法法代数系统域（ Y ）
4 设G面图|V|v |E|er面数ve + r2（ N ）
5 果图D欧拉图D强连通图（ Y ）
四证明 46
1 设半群e左幺元
群（10分）
证明：（1）

(2) e 幺元
事实：e左幺元现证e右幺元

（3）

（2）（3）知：群
2 循环群非子群循环群（10分）
证明：设循环群G(a)设子群存正整数m：意必
： ：
m正整数r0：
说明S中意元素幂 生成元循环群
3 设aHbH子群H群G中两左陪集证明：末末
（8分）
证明：集合列两种情况：
（1） （2）
少存时意
理证：
4 设含幺环|A|>3意
整环（时称布尔环）（8分）
证明：反证法：果整环三元素存
：整环中零子条件矛盾整环
5 图G连通G补图连通（10分）
证明：G< VE>连通设连通分支两种情况：
（1） u v分属两结点子集ViVjG(Vi) G(Vj)两连通分支(u v)G中u v 中连通
（2） u v 属结点子集Vi结点子集Vj中取点w(u w)(w v )均中邻接边( u w ) ( w v ) 组成路连接结点uvu v中连通
五布尔表达式 8
设布尔代数布尔表达式试写出析取范式合取范式
函数表：




0
0
0
0
0
0
1
1
0
1
0
0
0
1
1
1
1
0
0
0
1
0
1
1
1
1
0
1
1
1
1
1
析取范式：
合取范式：
六图应 16
1 构造结点v边数e奇偶性相反欧拉图（6分）
解：

2 假设英文字母aehnprwy出现频率分128157610510求传输佳前缀码出happy new year编码信息（10分）
根权数构造优二叉树：
解：传输佳前缀码图示happy new year编码信息：
10 011 0101 0101 001 110 111 0100 001 111 011 000
附：优二叉树求解程




试卷十五试题答案
填空 20 （空 2分）
6 果限集合An元素|2A| 2n
7 某集合101元素 2100 子集元素奇数
8 设S{a1a2…a8}BiS子集B17表达子集 {a4a8} 子集{a2a6a7}规定 B01000110（B70）
9 A1A2…An生成集形式 全集 集交 集
10 某三子组成集合A{S1S2S3}A兄弟关系具反反性称性传递性 性质
6良序集必全序集 限 全序集必良序集
7函数f 双射 f逆函数
七 选择 15 （题 3分）
1 集合幂集（ B ）
A
B
C
D
2 列结果正确（ BE ）
ABC
DEFA⊕AA
3 集合集范式（ A ）（ABC生成）
A B
C D
4 （ D ）
ABCD
5 列二元关系中函数（ B ）
A
B
C
三 15 Warshall算法集合A{12345}二元关系R{<11><12><24><35><42>}求t（R）

解：
1时[11]1 A
i2时M[12]M[42]1
3时A第三列全0A变 4时M[14]M[24]M[44]1
5时M[35]1 时

A 1 2 3
t (R){<11> <12><14><22><24><35><42><44>}
四15
集合C*定义关系
RC*等价关系出R等价类说明
证明：
称性：

反性：
传递性：

RC*等价关系
R两等价类：

五计算 15
1 设A{1234}S{{1}{23}{4}}A分划求S导出等价关系
R{< 1 1 > < 2 2> < 2 3 > < 3 2 > < 3 3 > < 4 4 > }
2 设Ｚ整数集关系Z等价关系求R模K等价关系商集ZR指出R秩（5分）
ZR{[0][1]…[k1]} R秩k
3 设A{12345}A偏序关系
求A子集{345}{123}界界确界确界（6分）
{345}：界：13确界：3界：确界：
{123}：界：1确界：1界：4确界：4
六证明 20
1 假定满射g入射f满射（10分）
证明：g入射存唯满射述c存g单射：均存f满射
2 设fgAB函数证明（10分）

文档香网(httpswwwxiangdangnet)户传

《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档