第一篇：离散数学课件作业

离散数学课件作业

第一部分 集合论

第一章 集合的基本概念和运算 1-1 设集合 A ={1，{2}，a，4，3}，下面命题为真是

[ ] A．2 ∈A； B．1 ∈ A； C．5 ∈A； D．{2}  A。

1-2 A,B 为任意集合，则他们的共同子集是

[ ] A．A； B．B； C．A∪B； D．

Ø。

1-3 设 S = {N，Z，Q，R}，判断下列命题是否成立 ？

（1）N  Q，Q ∈S，则 N  S

［

］

（2）-1 ∈Z，Z ∈S，则-1 ∈S

［

］

1-4 设集合 A ={3，4}，B = {4，3} ∩ Ø，C = {4，3} ∩{ Ø }，D ={ 3，4，Ø }，E = {x│x ∈R 并且 x2-7x + 12 = 0}，F = { 4，Ø，3，3}，试问哪两个集合之间可用等号表示 ？

1-5 用列元法表示下列集合

（1）A = { x│x ∈N 且 x2 ≤ 9 }（2）A = { x│x ∈N 且 3－x 〈 3 }

第二章 二元关系

2-1 给定 X =（3, 2，1），R 是 X 上的二元关系，其表达式如下： R = {〈x，y〉x，y ∈X 且 x ＜ y } 求：(1)domR =?;(2)ranR =?;(3)R 的性质。

2-2 设 R 是正整数集合上的关系，由方程 x + 3y = 12 决定，即 R = {〈x，y〉│x，y ∈Z+ 且 x + 3y = 12}，试求：（1）R 的列元表达式；（2）给出 dom（R。R）。

2-3 判断下列映射 f 是否是 A 到 B 的函数；并对其中的 f：A→B 指出他的性质，即是否单射、满射和双射，并说明为什么。

（1）A = {1，2，3}，B = {4，5}，f = {〈1，4〉〈2，4〉〈3，5〉}。（2）A = {1，2，3} = B，f = {〈1，1〉〈2，2〉〈3，3〉}。（3）A = B = R，f = x。（4）A = B = N，f = x2。（5）A = B = N，f = x + 1。

2-4 设 A ={1，2，3，4}，A 上的二元关系

R ={〈x，y〉︱（x-y）能被3整除}，则自然映射 g：A→A/R使 g(1)=

[

] A．｛1,2｝；

B．｛1,3｝；

C．｛1,4｝；

D．｛1｝。

2-5 设 A ={1，2，3}，则商集A/IA =

[

] A．｛3｝；

B．｛2｝；

C．｛1｝；

D．｛｛1｝，｛2｝，｛3｝｝。

2-6．设ｆ(x)＝x+1，ｇ(x)＝x-1 都是从实数集合Ｒ到Ｒ的函数，则ｆ。ｇ＝

[

]

A．x+1；

B．x-1；

C．x；

D．x2。

第三章 结构代数(群论初步)3-1 给出集合及二元运算，阐述是否代数系统，何种代数系统 ？

（1）S1 = {1，1/4,1/3,1/2,2，3，4}，二元运算 * 是普通乘法。（2）S2 = {a1，a2，……，an}，ai ∈R，i = 1，2，……，n ；

二元运算。定义如下：对于所有 ai，aj ∈S2，都有 ai。aj = ai。（3）S3 = {0，1}，二元运算 * 是普通乘法。

3-2 在自然数集合上，下列那种运算是可结合的 ［

］

A．x*y = max(x,y)；

B．x*y = 2x+y ； C．x*y = x2+y2 ；

D．x*y =︱x-y︱..3-3 设 Z 为整数集合，在 Z 上定义二元运算。，对于所有 x，y ∈Z 都有 x。y = x + y，试问〈Z。〉能否构成群，为什麽 ？

第二部分 图论方法 第四章 图

4-1 10 个顶点的简单图 G 中有 4 个奇度顶点，问 G 的补图中有几个偶数度顶点 ？

4-2 是非判断：无向图G中有10条边,4个3度顶点,其余顶点度数全是2,共有 8 个顶点.[ ]

4-3 填空补缺：1条边的图 G 中，所有顶点的度数之和为

[ ]

第五章 树

5-1 握手定理的应用（指无向树）

（1）在一棵树中有 7 片树叶，3 个 3 度顶点，其余都是 4 度顶点，问有()个？

（2）一棵树有两个 4 度顶点，3 个 3 度顶点，其余都是树叶，问有()片？

5-2 一棵树中有 i 个顶点的度数为 i（i=2，…k），其余顶点都是树叶(即一度顶点)，问树叶多少片？设有x片,则 x=

5-3 求最优 2 元树：用 Huffman 算法求带权为 1，2，3，5，7，8 的最优 2 元树

T。试问：（1）T 的权 W（T）？（2）树高几层 ？

5-4 以下给出的符号串集合中，那些是前缀码？将结果填入[ ]内.B1 = {0，10，110，1111} [ ] B2 = {1，01，001，000} [ ] B3 = {a，b，c，aa，ac，aba，abb，abc} [ ] B4 = {1，11，101，001，0011} [ ]

5-5(是非判断题)11阶无向连通图G中17条边，其任一棵生成树 T 中必有6条树枝 [ ]

5-6(是非判断题)二元正则树有奇数个顶点。[ ]

5-7 在某次通信中 a，b，c，d，e 出现的频率分别为 5%;10%;20%;30%;35%.求传输他们的最佳前缀码。

1、最优二元树 T； 2.每个字母的码字；

第三部分 逻辑推理理论

第六章 命题逻辑

6-1 判断下列语句是否命题，简单命题或复合命题。

（1）2月 17 号新学期开始。[ ]（2）离散数学很重要。[ ]（3）离散数学难学吗 ？ [ ]（4）C 语言具有高级语言的简洁性和汇编语言的灵活性。[ ]（5）x + 5 大于 2。[ ]（6）今天没有下雨，也没有太阳，是阴天。[ ]

6-2 将下列命题符号化.（1）2 是偶素数。

（2）小李不是不聪明，而是不好学。（3）明天考试英语或考数学。（兼容或）（4）你明天不去上海，就去北京。（排斥或）

6-3 分别用等值演算法,真值表法,主析取范式法,判断下列命题公式的类型.（1）﹃（p→q）∧ q；（2）（（p→q）∧ p）→q；（3）（p→q）∧ q。

以下两题(6-4;6-5)为选择题,将正确者填入[ ]内.6-4 令 p：经一堑；q：长一智。命题’’只有经一堑，才能长一智’’符号化为

[

] A． p→q；

B．

q→p；

C．

p∧q；

D．

﹁q→﹁p

6-5 p：天气好；q：我去游玩．命题 ”如果天气好，则我去游玩” 符号化为

［

］

A． p→q；

B．

q→p；

C．

p∧q；

D．

﹁q→p

6-6 证明题:用不同方法(必须有构造证明法)判断推理结果是否正确。

如果今天下雨，则明天不上体育课。今天下雨了。所以，明天没有上体育课。

第七章 谓词逻辑

7-1 在谓词逻辑中用 0 元谓词将下列命题符号化（1）这台机器不能用。

（2）如果 2 ＞ 3，则 2 ＞ 5。

7-2 填空补缺题：设域为整数集合Ｚ，命题xy彐z（x-y=z）的真值为（）

7-3 在谓词逻辑中将下列命题符号化（1）有的马比所有的牛跑得慢。（2）人固有一死。

《附录》习题符号集

Ø 空集, ∪ 并, ∩ 交,⊕ 对称差,～ 绝对补,∑ 累加或主析取范式表达式缩写，量词 ”所有”，－ 普通减法, ÷ 普通除法, ㏑ 自然对数, ㏒ 对数，﹃ 非，”每个”，∨ 析取联结词，∧ 合取联结词，彐 量词”存在”，”有的”。

2010年2月20号。

第二篇：离散数学网上形成性作业

10秋离散数学 网上形成性作业

作业一

一、单项选择题（共 8 道试题，共 80 分。）

1.本课程的教学内容分为三个单元，其中第三单元的名称是（A）． A.数理逻辑 B.集合论 C.图论 D.谓词逻辑

满分：10 分

2.本课程的教学内容按知识点将各种学习资源和学习环节进行了有机组合，其中第2章关系与函数中的第3个知识点的名称是（D）． A.函数

B.关系的概念及其运算 C.关系的性质与闭包运算 D.几个重要关系

满分：10 分

3.本课程所有教学内容的电视视频讲解集中在VOD点播版块中，VOD点播版块中共有（B）讲． A.18 B.20 C.19 D.17 满分：10 分

4.本课程安排了7次形成性考核作业，第3次形成性考核作业的名称是（C）． A.集合恒等式与等价关系的判定 B.图论部分书面作业 C.集合论部分书面作业 D.网上学习问答

满分：10 分

5.课程学习的平台左侧第1个版块名称是：（C）． A.课程导学 B.课程公告 C.课程信息 D.使用帮助

满分：10 分

6.课程学习的平台右侧第5个版块名称是：（A）．

A.典型例题 B.视频课堂 C.VOD点播 D.常见问题

满分：10 分

7.“教学活动资料”版块是课程学习的平台右侧的第（C）个版块． A.6 B.7 C.8 D.9 满分：10 分

8.课程学习的平台中“课程复习”版块下，放有本课程历年考试试卷的栏目名称是：（D）． A.复习指导 B.视频 C.课件 D.自测

离散数学是计算机科学与技术专业的一门必修课，是学习其它课程的的一门基础专业课，学好这门课对今后学习其他的专业课非常重要。我对学习的安排如下： 1 在学习过程中准备按三个阶段完成学习：（1）分章节，共七个内容，集合及其运算、关系与函数、图的基本概念与性质、几种特殊图、树及其应用、命题逻辑、谓词逻辑，分别掌（2）看网上论坛及相关资料进行知识再现及巩固；（3）通过习题进行自测。

在学习形式上，合理利用一切资源：（1）VOD点播、视频课堂、典型例题、常见问题、课程拓展、及网上论坛等进行初步学习；（2）利用课本上练习题进行自测学习等；（3）求教在线老师；（4）与同学进行讨论。做到反复练习并勤于思考，熟练记忆基本定理、结论及公式，掌握理论的基本应用，做好课后习题，认真及时地完成在线和离线课程形成性作业，掌握基本的解题方法。对教学要求的重点内容和题型反复练习。

作业二

一、单项选择题（共 10 道试题，共 100 分。）

1.设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，B={2, 4, 6}，则集合B的最大元、最小元、上界、下界依次为(D)． A.8、2、8、2 B.8、1、6、1 C.6、2、6、2 D.无、2、无、2

满分：10 分

2.集合A={1, 2, 3, 4, 5, 6, 7, 8}上的关系R={|x+y=10且x, yA}，则R的性质为（B）． A.自反的 B.对称的 C.传递且对称的 D.反自反且传递的 满分：10 分

3.若集合A＝{ a，{a}，{1，2}}，则下列表述正确的是(C)． A.{a，{a}}A B.{1，2}A C.{a}A D.A

满分：10 分

4.设A={a, b}，B={1, 2}，R1，R2，R3是A到B的二元关系，且R1={, }，R2={, , }，R3={, }，则（A）不是从A到B的函数． A.R2 B.R3 C.R1和R2 D.R1和R3

满分：10 分

5.集合A={1, 2, 3, 4}上的关系R={|x=y且x, yA}，则R的性质为（B）． A.不是自反的 B.不是对称的 C.传递的 D.反自反

满分：10 分

6.如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有（B）个． A.0 B.2 C.1 D.3

满分：10 分

7.设A={a，b，c}，B={1，2}，作f：A→B，则不同的函数个数为

D

． A.2 B.3 C.6 D.8

满分：10 分

8.设集合A = {1, 2, 3, 4, 5}上的偏序关系的哈斯图如右图所示，若A的子集B = {3, 4, 5}，则元素3为B的（B）． A.下界 B.最小上界 C.最大下界 D.最小元

满分：10 分

9.若集合A的元素个数为10，则其幂集的元素个数为（A）． A.1024 B.10 C.100 D.1

满分：10 分

10.设集合A = {1, a }，则P(A)=(D)． A.{{1}, {a}} B.{,{1}, {a}} C.{{1}, {a}, {1, a }} D.{,{1}, {a}, {1, a }}

满分：10 分

第三篇：江大《离散数学》第一次离线作业

江南大学现代远程教育2012年上半年第一阶段测试卷 考试科目:《离散数学》第一章至第六章（总分100分）时间：90分钟 __________学习中心（教学点）批次：层次：专业：学号：身份证号：姓名：得分：

一.填空题(每小题6分，共36分)

1.设全集R是实数集,A={x││x│≤3,x∈整数集I},B={x│0≤x≤4 x∈整数集I,},则 B–A=________，A=_________，A∩B=___________

2.已知集合A={φ,a,b,}，则A的幂集ρ(A)=_______________.3.设集合A={a,b},B={c,d,e},则A×B=

4.设R是集合A={a,b,c,}上的两个关系,其中R={(a,a),(a,b),(b,a),(b,c)},则R∪__是R的自反闭包, R∪___是R的对称闭包, R∪___是R的传递闭包,5.若半群(s,*)满足1)________________

2)________________

3)_________________

则(s,*)是Able群

6.循环群(Z10,+10)中____________为生成元,元素4的周期为______,逆元为_________.二.单项选择题(每题6分,共18分)

7.设集合A={a,b},ρ(A)是A的幂集,则下列表达式中不正确的是()

A.a∈AB.φAC.{{a}}∈ρ(A)D.{a}∈ρ(A)

8.设集合A={a,b,c} ,A上的关系R={(a,a),(b,b),(c,c),(a,b),(b,a)} ,关系S={(a,b),(b,c)},则关系R具有性质 , 关系S具有性质

(A)自反性、对称性和传递;非对称和非自反(B)自反性和对称性;非对称和非自反

(C)自反性和传递性;非自反(D)自反性、对称性和传递;非对称

9.下面代数系统(G,*)中,()不是群

A.G={0,1,2,3},*为模4加法B.G为偶数集,*为加法.C.G为有理数集合,*为加法D.G为有理数集合,*为乘法

三.计算题(每小题10分,共20分)

10.设集合A={a,b,c}, A上的关系R={(a,b),(a,c),(b,c)},关系S={(a,c),(b,a),(c,b)}

求关系R、关系R、关系R·S

11.设有6阶循环群S=(a),其中a是生成元, e是单位元,写出 S的所有非平凡子群

四．证明题（每题12，共24分）

12．设R是xoy平面上的全体点集，R上的关系，~ 定义如下：22-12-1

（x1，y1）~（x2，y2）3(x1-x2)+4(y1-y2)=0

（1）证明~是R上的等价关系（2）给出等价类 [（1，2）]~ 的几何意义

13．设G={a+b3│a,b是整数}，二元运算*表示加法

（1）证明（G，*）是群

（2）（G，*）是Able群吗？

第四篇：离散数学

离散数学课件作业

第一部分 集合论

第一章集合的基本概念和运算

1-1 设集合 A ={1，{2}，a，4，3}，下面命题为真是[ B ]

A．2 ∈A；B．1 ∈ A；C．5 ∈A；D．{2}  A。

1-2 A,B,C 为任意集合，则他们的共同子集是[ D ]

A．C；B．A；C．B；D．Ø。

1-3 设 S = {N，Z，Q，R}，判断下列命题是否成立 ？

（1）N  Q，Q ∈S，则 N  S［不成立］

（2）-1 ∈Z，Z ∈S，则-1 ∈S［不成立］

1-4 设集合 A ={3，4}，B = {4，3} ∩ Ø，C = {4，3} ∩{ Ø }，D ={ 3，4，Ø }，2E = {x│x ∈R 并且 x-7x + 12 = 0}，F = { 4，Ø，3，3}，试问哪两个集合之间可用等号表示 ？

答：A = E；B = C；D = F

1-5 用列元法表示下列集合（1）A = { x│x ∈N 且 x2 ≤ 9 }

（2）A = { x│x ∈N 且 3－x 〈 3 }

答：（1）A = { 0，1，2，3 }；

（2）A = { 1，2，3，4，……} = Z+；

第二章二元关系

2-1 给定 X =（3, 2，1），R 是 X 上的二元关系，其表达式如下：

R = {〈x，y〉x，y ∈X 且 x≤ y }

求：(1)domR =?;(2)ranR =?;(3)R 的性质。

答：R = {<2，3>，<1,2>，<1,3>}；

DomR={R中所有有序对的x}={2,1,1}={2,1};

RanR={R中所有有序对的y}={3,2,3}={3,2}；

R 的性质:反自反,反对称,传递性质.2-2 设 R 是正整数集合上的关系，由方程 x + 3y = 12 决定，即

R = {〈x，y〉│x，y∈Z+ 且 x + 3y= 12}，试求：

（1）R 的列元表达式；（2）给出 dom（R。R）。

答：根据方程式有：y=4-x/3，x 只能取 3，6,9。

（1）R = {〈3，3〉,〈6，2〉,〈9，1〉}；

至于(2),望大家认真完成合成运算 R。R={<3,3>}.然后,给出 R。R 的定义域,即

（2）dom（R。R）= {3}。

2-3 判断下列映射 f 是否是 A 到 B 的函数；并对其中的 f：A→B 指出他的性质，即

是否单射、满射和双射，并说明为什么。

（1）A = {1，2，3}，B = {4，5}，f = {〈1，4〉〈2，4〉〈3，5〉}。

（2）A = {1，2，3} = B，f = {〈1，1〉〈2，2〉〈3，3〉}。

（3）A = B = R，f=x。

（4）A = B = N，f=x2。

（5）A = B = N，f = x + 1。

答：（1）是 A 到 B 的函数，是满射而不是单射；

（2）是双射；

（3）是双射；

（4）是单射，而不是满射；

（5）是单射而不是满射。

2-4 设 A ={1，2，3，4}，A 上的二元关系

R ={〈x，y〉︱（x-y）能被3整除}，则自然映射 g：A→A/R使 g(1)=[C]

A．｛1,2｝；B．｛1,3｝；C．｛1,4｝；D．｛1｝。

2-5 设 A ={1，2，3}，则商集A/IA =[D]

A．｛3｝；B．｛2｝；C．｛1｝；D．｛｛1｝，｛2｝，｛3｝｝。

2-6．设ｆ(x)＝x+1，ｇ(x)＝x-1 都是从实数集合Ｒ到Ｒ的函数，则ｆ。ｇ＝[C]

A．x+1；B．x-1；C．x；D．x2。

第三章 结构代数(群论初步)

3-1 给出集合及二元运算，阐述是否代数系统，何种代数系统 ？

（1）S1 = {1，1/4,1/3,1/2,2，3，4}，二元运算 *是普通乘法。

（2）S2 = {a1，a2，……，an}，ai ∈R，i = 1，2，……，n ；

二元运算。定义如下：对于所有 ai，aj ∈S2，都有 ai。aj = ai。

（3）S3 = {0，1}，二元运算 * 是普通乘法。

答：（1）二元运算*在S1上不封闭．所以，＂S1，*＂不能构成代数系统。

（2）由二元运算的定义不难知道。在 S2 内是封闭的，所以，〈S2。〉构成代数

系统；然后看该代数系统的类型：该代数系统只是半群。

（3）很明显，〈{0，1}，*〉构成代数系统；满足结合律，为半群；1是幺元，为独异

点；而 0 为零元；结论：仅为独异点，而不是群。

3-2 在自然数集合上，下列那种运算是可结合的［A］

A．x*y = max(x,y)；B．x*y = 2x+y ；

C．x*y = x2+y2 ；D．x*y =︱x-y︱..3-3 设 Z 为整数集合，在 Z 上定义二元运算。，对于所有 x，y ∈Z都有

x。y=x + y，试问〈Z。〉能否构成群，为什麽 ？

答：由题已知，集合Z满足封闭性；二元运算满足结合律，依此集合Z为半群；有幺元为 －5，为独异点.假设代数系统的幺元是集合中的元素 e,则一个方程来自于二元运算定义, 即e。x= e + x，一个方程来自该特殊元素的定义的性质,即e。x = x.由此而来的两个方程联立结果就有: e+x=x 成立.削去 x,e=0 的结果不是就有了吗!；每个元素都有逆.求每个元素的逆元素,也要解联方程,如同求幺元一样的道理；结论是：代数系统〈 Z。〉构成群。

第二部分图论方法

第四章 图

4-1 10 个顶点的简单图 G 中有 4 个奇度顶点，问 G 的补图中有几个偶数度顶点 ？ 答：因为10阶完全图的每个顶点的度数都是n-1=9――为奇数。这样一来，一个无向简单图 G 的某顶点的度数是奇数，其补图的相应顶点必偶数，因为一个偶数与一个奇数之和才是奇数．所以，Ｇ的补图中应有 10-4＝6 个奇数度顶点。

4-2 是非判断：无向图G中有10条边,4个3度顶点,其余顶点度数全是2,共有 8 个顶点.[是]

4-3 填空补缺：1条边的图 G 中，所有顶点的度数之和为[2]

第五章树

5-1握手定理的应用（指无向树）

（1）在一棵树中有 7 片树叶，3 个 3 度顶点，其余都是 4 度顶点，问有(有1个4度顶点)个？

（2）一棵树有两个 4 度顶点，3 个 3 度顶点，其余都是树叶，问有(9个1度顶点)片？

5-2 一棵树中有 i 个顶点的度数为 i（i=2，…k），其余顶点都是树叶(即一度顶点)，问树叶多少片？设有x片,则 x=

答：假设有 x 片树叶，根据握手定理和树的顶点与边数的关系，有关于树叶的方程，解方程得到树叶数 x = Σi（i—2）i + 2，（i = 2，3，……k）。

5-3 求最优 2 元树：用 Huffman 算法求带权为 1，2，3，5，7，8 的最优 2 元树 T。试问：（1）T 的权 W（T）？（2）树高几层 ？

答：用 Huffman 算法，以 1，2，3，5，7，8 为权，最优 2 元树 T ；然后，计算并回答所求问题：（1）T 的权 W（T）= 61；（2）树高几层：4 层树高。

5-4以下给出的符号串集合中，那些是前缀码？将结果填入[]内.B1 = {0，10，110，1111}[是]B2 = {1，01，001，000}[是]B3 = {a，b，c，aa，ac，aba，abb，abc}[非]B4 = {1，11，101，001，0011}[非]

5-5(是非判断题)11阶无向连通图G中17条边，其任一棵生成树 T 中必有6条树枝 [非]

5-6(是非判断题)二元正则树有奇数个顶点。[是]

5-7 在某次通信中 a，b，c，d，e 出现的频率分别为 5%;10%;20%;30%;35%.求传输他们的最佳前缀码。

1、最优二元树 T；2.每个字母的码字；

答：每个字母出现频率分别为：G、D、B、E、Y：14%，O：28%；(也可以不归一,某符号

出现次数即为权，如右下图).。100（近似）7.。563..4。282..2..2。..1..14141414111

1所以，得到编码如下：G（000），D（001），B（100），E（101），Y（01），O（11）。

第三部分逻辑推理理论

第六章 命题逻辑

6-1 判断下列语句是否命题，简单命题或复合命题。

（1）2月 17 号新学期开始。[真命题]

（2）离散数学很重要。[真命题]

（3）离散数学难学吗 ？[真命题]

（4）C 语言具有高级语言的简洁性和汇编语言的灵活性。[复合命题]

（5）x + 5 大于 2。[真命题]

（6）今天没有下雨，也没有太阳，是阴天。[复合命题]

6-2 将下列命题符号化.（1）2 是偶素数。

（2）小李不是不聪明，而是不好学。

（3）明天考试英语或考数学。（兼容或）

（4）你明天不去上海，就去北京。（排斥或）

答：（1）符号化为： p ∧ q。

（2）符号化为：p ∧ ﹃q。

（3）符号化为：p ∨ q。

（4）符号化为：（﹃p ∧ q）∨（p ∧ ﹃q）。

6-3分别用等值演算法,真值表法,主析取范式法,判断下列命题公式的类型.（1）﹃（p→q）∧ q；（2）（（p→q）∧ p）→q；（3）（p→q）∧ q。答：（1）0；

（2）Σ（0，1，2，3）；

（3）Σ（1，3）。

以下两题(6-4;6-5)为选择题,将正确者填入[]内.6-4 令 p：经一堑；q：长一智。命题’’只有经一堑，才能长一智’’符号化为[B]

A． p→q；B．q→p；C．p∧q；D．﹁q→﹁p

6-5 p：天气好；q：我去游玩．命题 ”如果天气好，则我去游玩” 符号化为［B］

A． p→q；B．q→p；C．p∧q；D．﹁q→p

6-6证明题:用不同方法(必须有构造证明法)判断推理结果是否正确。

如果今天下雨，则明天不上体育课。今天下雨了。所以，明天没有上体育课。答：将公式分成前提及结论。

前提：（p→﹃q），p；

结论：﹃q；

证明：（1）（p→﹃q）前提引入

（2）p前提引入

（3）（p→﹃q）∧p（1）（2）假言推理

（4）﹃q

要证明的结论与证明结果一致，所以推理正确。

第七章谓词逻辑

7-1 在谓词逻辑中用 0 元谓词将下列命题符号化

（1）这台机器不能用。

（2）如果 2 ＞ 3，则 2 ＞ 5。

答：（1）﹃F（a）。

（2）L（a，b）→ H（a，z）。

7-2 填空补缺题：设域为整数集合Ｚ，命题xy彐z（x-y=z）的真值为（0）

7-3在谓词逻辑中将下列命题符号化

（1）有的马比所有的牛跑得慢。

（2）人固有一死。

答：（1）符号化为：彐x（F（x）∧ 彐y（G（y）∧ H（x，y）））。

（2）与（1）相仿，要注意量词、联结词间的搭配：

x（F（x）→y（G（y）→ H（x，y）））。

《附录》习题符号集

Ø 空集, ∪ 并, ∩ 交,⊕ 对称差,～ 绝对补,∑ 累加或主析取范式表达式缩写 , － 普通减法, ÷ 普通除法, ㏑ 自然对数, ㏒ 对数，﹃ 非，量词 ”所有”，”每个”，∨ 析取联结词，∧ 合取联结词，彐 量词”存在”，”有的”。

2010年8月12号。

第五篇：离散数学

离散数学试题（A卷答案）

一、（10分）

（1）证明(PQ)∧(QR)(PR)（2）求(P∨Q)R的主析取范式与主合取范式，并写出其相应的成真赋值和成假赋值。解：（1）因为((PQ)∧(QR))(PR)((P∨Q)∧(Q∨R))∨(P∨R)(P∧Q)∨(Q∧R)∨P∨R (P∧Q)∨((Q∨P∨R)∧(R∨P∨R))(P∧Q)∨(Q∨P∨R)(P∨Q∨P∨R)∧(Q∨Q∨P∨R)T 所以，(PQ)∧(QR)(PR)。

（2）(P∨Q)R(P∨Q)∨R(P∧Q)∨R (P∨(Q∧Q)∨R)∧((P∧P)∨Q∨R)(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)M2∧M4∧M6 m0∨m1∨m3∨m5

所以，其相应的成真赋值为000、001、011、101、111：成假赋值为：010、100、110。

二、（10分）分别找出使公式x(P(x)y(Q(y)∧R(x，y)))为真的解释和为假的解释。

解：设论域为{1，2}。

若P(1)＝P(2)＝T，Q(1)＝Q(2)＝F，R(1，1)＝R(1，2)＝R(2，1)＝R(2，2)＝F，则 x(P(x)y(Q(y)∧R(x，y)))x(P(x)((Q(1)∧R(x，1))∨(Q(2)∧R(x，2))))(P(1)((Q(1)∧R(1，1))∨(Q(2)∧R(1，2))))∧(P(2)((Q(1)∧R(2，1))∨(Q(2)∧R(2，2))))(T((F∧F)∨(F∧F)))∧(T((F∧F)∨(F∧F)))(TF)∧(TF)F 若P(1)＝P(2)＝T，Q(1)＝Q(2)＝T，R(1，1)＝R(1，2)＝R(2，1)＝R(2，2)＝T，则 x(P(x)y(Q(y)∧R(x，y)))x(P(x)((Q(1)∧R(x，1))∨(Q(2)∧R(x，2))))(P(1)((Q(1)∧R(1，1))∨(Q(2)∧R(1，2))))∧(P(2)((Q(1)∧R(2，1))∨(Q(2)∧R(2，2))))(T((T∧T)∨(T∧T)))∧(T((T∧T)∨(T∧T)))(TT)∧(TT)T

三、（10分）

在谓词逻辑中构造下面推理的证明：每个喜欢步行的人都不喜欢做汽车，每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车，因而有的人不喜欢步行。

解

论域：所有人的集合。A(x)：x喜欢步行；B(x)：x喜欢坐汽车；C(x)：x喜欢骑自行车；则推理化形式为：

x(A(x)B(x))，x(B(x)∨C(x))，xC(x)xA(x)下面给出证明：(1)xC(x)

P(2)xC(x)

T(1)，E(3)C(c)

T(2)，ES(4)x(B(x)∨C(x))

P(5)B(c)∨C(c)

T(4)，US(6)B(c)

T(3)(5)，I(7)x(A(x)B(x))

P(8)A(c)B(c)

T(7)，US(9)A(c)

T(6)(8)，I(10)xA(x)

T(9)，EG

四、（10分）

下列论断是否正确？为什么？(1)若A∪B＝A∪C，则B＝C。(2)若A∩B＝A∩C，则B＝C。(3)若AB＝AC，则B＝C。

解(1)不一定。例如，令A＝{1}，B＝{1，2}，C＝{2}，则A∪B＝A∪C，但B＝C不成立。(2)不一定。例如，令A＝{1}，B＝{1，2}，C＝{1，3}，则A∩B＝A∩C，但B＝C不成立。(3)成立。因为若AB＝AC，对任意的x∈B，当x∈A时，有x∈A∩BxABxAC＝(A∪C)－(A∩C)x∈A∩Cx∈C，所以BC；当xA时，有xA∩B，而x∈Bx∈A∪B，所以x∈A∪B－A∩B＝ABx∈AC，但x A，于是x∈C，所以BC。

同理可证，C B。

因此，当AB＝AC时，必有B＝C。

五、（10分）若R是集合A上的自反和传递关系，则对任意的正整数n，R＝R。

证明 当n＝1时，结论显然成立。设n＝k时，Rk＝R。当n＝k＋1时，Rk+1＝Rk*R＝R*R。下面由R是自反和传递的推导出R*R＝R即可。

由传递性得R*RR。另一方面，对任意的∈R，由R自反得∈R，再由关系的复合得∈R*R，从而RR*R。因此，R＝R*R。

由数学归纳法知，对任意的正整数n，Rn＝R。

n

六、（15分）设函数f：R×RR×R，f定义为：f()＝。

(1)证明f是单射。(2)证明f是满射。(3)求逆函数f。

(4)求复合函数f－1f和ff。

证明(1)对任意的x，y，x1，y1∈R，若f()＝f()，则＝，x＋y＝x1＋y1，x－y＝x1－y1，从而x＝x1，y＝y1，故f是单射。

(2)对任意的∈R×R，令x＝uw2uw2－

1，y＝

uw2，则f()＝<

uw2＋

uw2，uw2－>＝，所以f是满射。

uw2－1(3)f()＝<－1，uw2>。

xyxy2xy(xy)2(4)ff()＝f(f())＝f()＝<－1－1，>＝ ff()＝f(f())＝f()＝＝<2x，2y>。

七、（15分）设X＝{1，2，3，4}，R是X上的二元关系，R＝{<1，1>，<3，1>，<1，3>，<3，3>，<3，2>，<4，3>，<4，1>，<4，2>，<1，2>}(1)画出R的关系图。(2)写出R的关系矩阵。

(3)说明R是否是自反、反自反、对称、传递的。解(1)R的关系图如图所示：(2)R的关系矩阵为：

10M(R)111011101100 00(3)对于R的关系矩阵，由于对角线上不全为1，R不是自反的；由于对角线上存在非0元，R不是反自反的；由于矩阵不对称，R不是对称的；

经过计算可得 102M(R)111011101100M(R)，所以R是传递的。00

八、（10分）若是群，H是G的非空子集，则是的子群对任意的a、b∈H有a*b－1∈H。证明 必要性：对任意的a、b∈H，由是的子群，必有b－1∈H，从而a*b－1∈H。充分性：由H非空，必存在a∈H。于是e＝a*a∈H。任取a∈H，由e、a∈H得a－1＝e*a－1∈H。

对于任意的a、b∈H，有a*b＝a*(b)∈H，即a*b∈H。又因为H是G非空子集，所以*在H上满足结合律。综上可知，是的子群。

九、（10分）给定二部图G＝，且|V1∪V2|＝m，|E|＝n，证明n≤m/4。

证明 设|V1|＝m1，则|V2|＝m－m1，于是n≤m1(m－m1)＝m1m－m22

2－

1－1

－1

m12。因为(m2m1)20，即4mm1m1，所以n≤m2/4。离散数学试题（B卷答案）

一、（20分）用公式法判断下列公式的类型：(1)(P∨Q)(PQ)(2)(PQ)(P∧(Q∨R))解：（1）因为(P∨Q)(PQ)(P∨Q)∨(P∧Q)∨(P∧Q)

(P∧Q)∨(P∧Q)∨(P∧Q)m1∨m2∨m3 M0

所以，公式(P∨Q)(PQ)为可满足式。

（2）因为(PQ)(P∧(Q∨R))((P∨Q))∨(P∧Q∧R))

(P∨Q)∨(P∧Q∧R))

(P∨Q∨P)∧(P∨Q∨Q)∧(P∨Q∨R)(P∨Q)∧(P∨Q∨R)

(P∨Q∨(R∧R))∧(P∨Q∨R)(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)M0∧M1

m2∨m3∨m4∨m5∨m6∨m7

所以，公式(PQ)(P∧(Q∨R))为可满足式。

二、（15分）在谓词逻辑中构造下面推理的证明：每个科学家都是勤奋的，每个勤奋又身体健康的人在事业中都会获得成功。存在着身体健康的科学家。所以，存在着事业获得成功的人或事业半途而废的人。

Q(x)：x是勤奋的；x是科学家；C(x)：解：论域：所有人的集合。H(x)：x是身体健康的；S(x)：x是事业获得成功的人；F(x)：x是事业半途而废的人；则推理化形式为：

x(S(x)Q(x))，x(Q(x)∧H(x)C(x))，x(S(x)∧H(x))

x(C(x)∨F(x))下面给出证明：

(1)x(S(x)∧H(x))

P(2)S(a)∧H(a)

T(1)，ES(3)x(S(x)Q(x))

P(4)S(a)Q(a)

T(1)，US(5)S(a)

T(2)，I(6)Q(a)

T(4)(5)，I(7)H(a)

T(2)，I(8)Q(a)∧H(a)

T(6)(7)，I(9)x(Q(x)∧H(x)C(x))

P(10)Q(a)∧H(a)C(a)

T(9)，Us(11)C(a)

T(8)(10)，I(12)xC(x)

T(11)，EG(13)x(C(x)∨F(x))

T(12)，I

三、（10分）设A＝{，1，{1}}，B＝{0，{0}}，求P(A)、P(B)－{0}、P(B)B。解

P(A)＝{，{}，{1}，{{1}}，{，1}，{，{1}}，{1，{1}}，{，1，{1}}} P(B)－{0}＝{，{0}，{{0}}，{0，{0}}－{0}＝{，{0}，{{0}}，{0，{0}} P(B)B＝{，{0}，{{0}}，{0，{0}}{0，{0}}＝{，0，{{0}}，{0，{0}}

四、（15分）设R和S是集合A上的任意关系，判断下列命题是否成立？(1)若R和S是自反的，则R*S也是自反的。(2)若R和S是反自反的，则R*S也是反自反的。(3)若R和S是对称的，则R*S也是对称的。(4)若R和S是传递的，则R*S也是传递的。(5)若R和S是自反的，则R∩S是自反的。(6)若R和S是传递的，则R∪S是传递的。

解

(1)成立。对任意的a∈A，因为R和S是自反的，则∈R，∈S，于是∈R*S，故R*S也是自反的。

(2)不成立。例如，令A＝{1，2}，R＝{<1，2>}，S＝{<2，1>}，则R和S是反自反的，但R*S＝{<1，1>}不是反自反的。

(3)不成立。例如，令A＝{1，2，3}，R＝{<1，2>，<2，1>，<3，3>}，S＝{<2，3>，<3，2>}，则R和S是对称的，但R*S＝{<1，3>，<3，2>}不是对称的。

(4)不成立。例如，令A＝{1，2，3}，R＝{<1，2>，<2，3>，<1，3>}，S＝{<2，3>，<3，1>，<2，1>}，则R和S是传递的，但R*S＝{<1，3>，<1，1>，<2，1>}不是传递的。

(5)成立。对任意的a∈A，因为R和S是自反的，则∈R，∈S，于是∈R∩S，所以R∩S是自反的。

五、（15分）令X＝{x1，x2，…，xm}，Y＝{y1，y2，…，yn}。问(1)有多少个不同的由X到Y的函数？

(2)当n、m满足什么条件时，存在单射，且有多少个不同的单射？(3)当n、m满足什么条件时，存在双射，且有多少个不同的双射？

解

(1)由于对X中每个元素可以取Y中任一元素与其对应，每个元素有n种取法，所以不同的函数共n个。

(2)显然当|m|≤|n|时，存在单射。由于在Y中任选m个元素的任一全排列都形成X到Y的不同的单射，故不同的单射有Cnm!＝n(n－1)(n―m―1)个。

(3)显然当|m|＝|n|时，才存在双射。此时Y中元素的任一不同的全排列都形成X到Y的不同的双射，mm故不同的双射有m!个。

六、（5分）集合X上有m个元素，集合Y上有n个元素，问X到Y的二元关系总共有多少个？ 解

X到Y的不同的二元关系对应X×Y的不同的子集，而X×Y的不同的子集共有个2mn，所以X到Y的二元关系总共有2mn个。

七、（10分）若是群，则对于任意的a、b∈G，必有惟一的x∈G使得a*x＝b。

证明 设e是群的幺元。令x＝a－1*b，则a*x＝a*(a－1*b)＝(a*a－1)*b＝e*b＝b。所以，x＝a－1*b是a*x＝b的解。

若x∈G也是a*x＝b的解，则x＝e*x＝(a*a)*x＝a*(a*x)＝a*b＝x。所以，x＝a*b是a*x

－

1－1

－1

－1＝b的惟一解。

八、（10分）给定连通简单平面图G＝，且|V|＝6，|E|＝12。证明：对任意f∈F，d(f)＝3。证明

由偶拉公式得|V|－|E|＋|F|＝2，所以|F|＝2－|V|＋|E|＝8，于是d(f)＝2|E|＝24。若存在f∈

fFF，使得d(f)＞3，则3|F|＜2|E|＝24，于是|F|＜8，与|F|＝8矛盾。故对任意f∈F，d(f)＝3。