2024离散数学练习题

2024-06-19

2024离散数学练习题（精选9篇）

2024离散数学练习题第1篇

1、下列句子是简单命题的是（）

A)3是素数。B)2x+3<

5C)张三跟李四是同学吗？D)我在说谎。

2、下列公式不是永真式的是（）．．

A)((p∧q))→p)∨rB)p→(p∨q∨r)

C)┓(q→r)∧rD)(p→q)→(┓q→┓p)

3、设命题公式G<=>┓(p→q)，H<=>p→(q →┓p)，则G与H的关系是()。

A)G<=>HB)H→GC)H => GD)G => H4、下列命题不为真的是（）．

A)Φ  ΦB)Φ∈Φ

C){a,b}∈{a,b,c,{a,b}}}D){a,b}{a,b,c,{a,b}}

5、1到300之间（包含1 和1000）不能被3、5和7整除的数有（）个。

13、下列运算在指定集合上不符合交换律的是（）。

A)复数C集合上的普通加法B)n阶实矩阵上的乘法 C)集合S的幂集上的∪D)集合S的幂集上的

14、下列集合对所给的二元运算封闭的是（）

A)正实数集合R+和。运算，其中。运算定义如下：a,b∈R+，a。b=ab-a-b B)n∈Z+，nZ={nZ|z∈Z}，nZ关于普通的加法运算 C)S={2x-1|x∈Z+}关于普通的加法运算

D)S={x|x=2n, n∈Z+}，S关于普通的加法运算

15、设V=,其中*定义如下：a，b∈Z, a*b=a+b-2 ,则能构成的代数系统是（）。

A)半群、独异点、群B)半群、独异点C)半群D)二元运算

上有○

A)138B)120C)68D)1246、设A, C, B, D为任意集合，以下命题一定为真的是（）

A)A∪B= A∪C =>B=C B)A×C= A×B =>B= C

C)A∪(B×C)=(A∪B)×(A∪C)D)存在集合A,使得A  A ×A7、设A={1,2,3,4}，R={<1,3>,<1,4>,<2,3>,<2,4>,<3,4>} 是A上的关系，则R的性质是（）

A)既是对称的也是反对称的 B)既不是对称的也不是反对称的 C)是对称的但不是反对称的D)不是对称的但是反对称的8、设R是A上的关系，则R在A上是传递的当且仅当（）

则这4个运算中满足幂等律的是（）

17、在上述四个运算中有单位元的是（）

18、在上述四个运算中有零元的是（）

19、与命题公式P（QR）等值的公式是()

A)(PQ)RB)(PQ)RC)(PQ)RD)P(QR)

20、下列集合都是N的子集，能够构成代数系统V=的子代数的是（）

A)｛x| x∈N∧x与5互为素数｝B)｛x| x∈N∧x是30的因子｝ C){x| x∈N∧x是30的倍数}D){x|x=2k+1, k∈N }

二、填空题(1分/空，共20分。请将正确答案填在相应的横线上。)

1、公式┓(p∨q)→p的成假赋值为00__,公式┓(q→p)∧p的成真赋值为。

2、设Ａ，Ｂ为任意命题公式，Ｃ为重言式，若Ａ∧Ｃ<=>Ｂ∧Ｃ，那么Ａ<->Ｂ是重言式（重言式、矛盾式或可满足式）。

3、f：N->N×N，f(x)=,A={5},B={<2,3>,<7,8>},则f(x)是A)IA  RB)R=R-1C)R∩IA ΦD)R。RR9、设A={1,2,3,4,5,6,7,8},R为A上的等价关系R={|x,y ∈ A ∧ x=y(mod 3)}

其中，x=y(mod 3)叫做x与y模3相等，即x除以3的余数与y除以3的余数相等。则1的等价类，即[1]，为（）

A){1,4,7}B){2,5,8}C){3,6}D){1,2,3,4,5,6,7,8}

10、当集合A=Φ且B≠Φ时，则BA结果为（）

A)ΦB){Φ} C){Φ, {Φ}}D)错误运算

11、函数f:R→R,f(x)= x2-2x+1,则f(x)是（）函数。

A)单射B)满射C)双射D)不是单射，也不是满射

12、设X={a,b,c,d},Y={1,2,3}，f={,,}，则以下命题正确的是()

A)f是从X到Y的二元关系，但不是从X到Y的函数 B)f是从X到Y的函数，但不是满射的，也不是单射的 C)f是从X到Y的满射，但不是单射 D)f是从X到Y的双射

双射）函数，A在f下的像f(A)＝_{<5,6>}_，B在f下的完全原像f-1(B)=____。

4、已知公式A中含有3个命题变项p,q,r，并且它的成真赋值为000，011，110，则A的主合取范式为（用极大项表示）__M∧_M∧_M∧_M∧_M，主析取范式为（用极小项表示）

5、公式x(F(x,y)→yG(x,y,z))的前束范式为_

6、列出从集合A={1,2}到B={1}的所有二元关系。

7、设A为集合且∣A∣=n，则A共有nP(A)有n

8、设 f，g，h ∈RR 且f(x)=x+3, g(x)=2x+1, h(x)=x/2, 则复合函数

⑦ x(F(x)∧G(x)→H(x))前提引入 ⑧ F(a)∧G(a)→H(a)T ⑦UI⑨ F(a)∧G(a)T ③ ⑥合取(10)H(a)T ⑧ ⑨ 假言推理

f。g。h(x)=__，f。g。h(x)=_____。

9、含有n个命题变项的公式共有_____个不同的赋值，最多可以生成___个不同的真值表；n个命题变项共可产生___n_____个极小项（极大项）；含n个命题变项的所有有穷多个合式公式中，与它们等值的主析取范式（主合取范式）共有___2^2___种不同的情况。

10、已知集合A={,{}}，则A的幂集P(A)＝_____。

五、设A={1,2,3,4}，在A×A上定义二元关系R，，∈A×A，R<=>u+y=x+v

(1)证明R是A×A上的等价关系

(2)确定由R引起的对A×A的划分。(5分)

三、利用公式的主合取范式判断下列公式是否等值。（5分）

p→(q→r)与(p∧q)∨r p→(q→r)

<=>p∨(q∨r)<=>p∨q∨r <=>M6

(p∧q)∨r

<=>(p∨q)∨r <=>p∨q)∨r <=>M6

(1)证明:  ∈ A×A => x+y=y+x=> ∈ R∴R是自反的  ∈ A×A , R => x+v=y+u=> R∴R是对称的  ,∈ A×A , R ∧ R=> x+v=y+u ∧ u+n=v+m

=> x+v+u+n=y+u+v+m => x+n=y+m => R ∧∴R是传递的(2)

解:{{<1,1>,<2,2>,<3,3>,<4,4>},{<1,2>,<2,3>,<3,4>},{<1,3>,<2,4>},{<1,4>,<4,1>},{<3,1>,<4,2>},{<2,1>,<3,2>,<4,3>}}

四、符号化命题，并推理证明(给出每个符号的准确含义，及每一步推理的根据)。（5分）

每个科学工作者都是刻苦钻研的。每个刻苦钻研而又聪明的人在他的事业中都将获得成功。华有为是科学工作者并且是聪明的，所以华有为在他的事业中将获得成功。

六、A= {1,2,3,4,6,8,12}，R是A上的整除关系，请作出偏序集的哈斯图，给出关系矩阵，并

求出A的极大元、极小元、最大元和最小元。若B={2,3,4}，求出B的上界，下界，最小上界，最大下界。（5分）

解:

首先符号化：M(x)：x是科学工作者；F(x)：x是刻苦钻研的；G(x)：x是聪明的；H(x)：x

在事业中获得成功；a：华有为。

前提： x(M(x)→F(x)），x(F(x)∧G(x)→H(x)),M(a)∧ G(a)

结论：H(a)

证明：① M(a)∧ G(a)前提引入 ② M(a)T ①化简规则 ③ G(a)T ①化简规则 ④ x(M(x)→F(x)）前提引入 ⑤ M(a)→F(a)T ④

⑥ F(a)T ② ⑤ 假言推理

解:A的极大元为8、12,极小元为1，无最大元，最小元为1。

B的上界为12，下界为1，最小上界为12，最大下界为1。

七、在自然推理系统P中构造下面推理的证明。（5分）(1)前提：(p∨q)→(r∧s),(s∨t)→u

结论：p→u(2)前提：x(F(x)→(G(a)∧ R(x)))，x F(x).九、证明下列恒等式 A-(B∪C)=(A-B)∩(A-C)。（5分）证明：A-(B∪C)

结论： x(F(x)∧ R(x)).(1)证明：① p附加前提引入规则② p ∨ q①附加规则③(p ∨ q)→(r ∧ s)前提引入

④ r ∧ s②③ 假言推理⑤ s④化简规则⑥ s ∨ t⑤附加规则⑦(s ∨ t)→ u前提引入

⑧ u⑥ ⑦假言推理

(2)证明：① x F(x)前提引入② F(b)① EI③ x(F(x)→(G(a)∧ R(x)))前提引入④ F(b)→(G(a)∧ R(b))③ UI

⑤ G(a)∧ R(b)② ④假言推理⑥ R(b)⑤化简⑦ F(b)∧ R(b)②⑥合取⑧x(F(x)∧ R(x))⑦EG

八、设有理数集合Q上的 * 运算定义如下：a，b∈Q, a*b=a+b-ab。请指出该运算的性质，并求出其单位元、零元及所有可能的逆元。（5分）

解：(1)因为a*b=a+b-ab =b+a-ba=b*a，所以运算满足交换律。

(2)因为(a*b)*c=(a+b-ab)*c= a+b-ab+c-(a+b-ab)c=a+b+c-ab-bc-ac+abca*(b*c)=a*(b+c-bc)=a+b+c-bc-a(b+c-bc)= a+b+c-ab-bc-ac+abc故运算满足结合律。

(3)任意x∈Q，因为x*x=x+x-xx=2x+x2≠x，故不满足幂等律(4)因为对a∈Q，有a*0=a+0-a0=a，所以0是单位元。(5)因为对a∈Q，有a*1=a+1-a=1，所以1是零元。

(6)对a∈Q，令a*x=a+x-ax=0，则有x=a/(a-1)。所以当a≠1时，其逆元为a=a/(a-1)，1没有逆元。

1＝A∩～(B∪C)＝A∩～B∩～C = A∩A∩～B∩～C ＝(A∩～B)∩(A∩～C)=(A-B)∩(A-C)

十、设A,B为任意集合，证明：AB<=>P(A)P(B)。（5分）证明：先证明充分性（=>）

X∈P(A)=> XA=> XB=> X∈P(B)再证明必要性（<=）

x∈A=> {x}A=> {x}∈P(A)=> {x}∈P(B)=> {x}B=>x∈B 综上所述，AB<=>P(A)P(B)

2024离散数学练习题第2篇

一、简要回答下列问题：

1．什么是消去环？请举一例。

2．请给出公式R→P的真值表。

3．什么是恒真公式？举一例。

4.什么是子句？什么是短语？

5．请给出命题xG(x)的真值规定

6．什么是最优树？

7．什么是群？举一例。

8．给出环的定义。举一例。

9．什么是整区？举一例。

10．什么是半序格？请举一例。

二、对任意集合A，B，证明：

(1)AB当且仅当(A) (B)；

(2)(A)(B)(AB)；

(3)(A)(B)=(AB)；

举例说明：(A)∪(B)≠(A∪B)

三、证明：映射的乘法满足结合律，举例说明：映射的乘法不满足交换律。

四、判断下列公式是恒真？恒假？可满足？

a)(P(QR))(P(QR))；

b)P(P(QP))；

c)(QP)(PQ)；

d)(PQ)(PQ)。

离散数学课程教学探讨第3篇

关键词：图,出度,入度,关联矩阵,邻接矩阵

离散数学是研究离散量的结构及其相互关系的数学学科, 是现代数学的一个重要分支。它在各学科领域, 特别在计算机科学技术领域有着广泛的应用, 同时离散数学也是计算机专业的许多专业课程, 如程序设计、数据结构操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。通过离散数学的学习, 不但可以掌握处理离散结构的描述工具和方法, 为后续课程的学习创造条件, 而且可以提高抽象思维和严格的逻辑推理能力, 为将来参与创新性的研究和开发工作打下坚实的基础。

高等教育出版社出版的离散数学教材, 是面向21世纪课程教材, 是普通高等教育“十一五”国家级规划教材。该教材相比其修订版及其他教材具有明显优点:语言组织简练易懂, 内容中心突出, 知识体系清晰, 知识点分布更加合理等。

下面是笔者在教学过程中发现的一个小问题, 在这里提出来和大家一起探讨。本书第五部分图论中第275页有如下定义:

定义14.4:设G=为无向图, ∀ν∈V, 称ν作为边的端点的次数之和为ν的度数, 简称为度, 记作dG (ν) 。在不发生混淆时, 略去下标G, 简记为d (ν) 。设D=为有向图, ∀ν∈V, 称ν作为边的始点的次数之和为ν的出度, 记作dD- (ν) , 简记为d- (ν) 。称ν作为边的终点的次数之和为ν的人度, 记作dD+ (ν) , 简记为dD+ (ν) 。称d- (ν) +d+ (ν) 为ν的度数, 记作dD (ν) , 简记作d (ν) 。

而在第288-289页图的矩阵表示中有如下定义:

定义14.24:设有向图D=中无环, V={ν1, ν2, …, νn}, E={e1, e2, …, en}, 令:

则称 (mij) n×m为D的关联矩阵, 记作M (D) 。

作为例题, 书中给出了图:

的关联矩阵:

并得到矩阵M (D) 具有如下的性质:

1) 每一列恰好有一个+1和一个-1。

2) -1的个数等于+1个数, 都等于边数m, 这正是有向图握手定理的内容。

3) 第i行中, +1的个数等于d+ (νi) , -1的个数等于dD- (νi) 。

4) 平行边所对应的列相同。

由定义14.4和定义14.24, 我们发现结论和定义出现了矛盾。如结论3为:+1的个数等于d+ (νi) , -1的个数等于dD- (νi) 。按照定义14.24中1和-1的定义, 该结论可解释为:νi作为边ei的始点的次数之和等于d+ (νi) , νi作为边ei的终点的次数之和等于d- (νi) 。而这与定义14.4中, 称ν作为边的始点的次数之和为的出度, 简记为d- (ν) 。称ν作为边的终点的次数之和为ν的人度, 简记为d+ (ν) 相矛盾。另外, 我们再看如下定义:

定义14.25:有向图D=, V={ν1, ν2, …, νn}, 令aij[1]为顶点νi邻接到顶点νj边的条数, 记作A (D) , 或简记为A。

作为例题, 书中给出了图:

邻接矩阵:

并且得到矩阵A具有如下的性质:

于是, , 即A (D) 中所有元素之和等于边数, 这也正是有向图握手定理的内容。

事实上, 因为a[1]ij为顶点νi邻接到顶点νj边的条数, 则有表示顶点νi作为边的始点的个数, 即顶点νi的出度, 由定义14.4, 即为d- (ν) , 因此 (1) 矛盾。类似的, 定义14.4也与 (2) 矛盾。

修改的方法很多, 比如:我们可以修改定义14.4, 但这不是很明智的。该文的修改主要是针对定义14.24中mij的取法以及上述两个例题及相关结论的修改。

定义14.24:设有向图D=中无环, V={ν1, ν2, …, νn}, E={e1, e2, …, en}, 令:

则称 (mij) n×m为D的关联矩阵, 记作M (D) 。

则图的关联矩阵改为:

此时其性质3仍然可以保持不变。

对于定义14.25:我们只需将性质 (1) 和 (2) 作如下修改:

这样一来, 我们的定义14.4、14, 24、14.25和相应的例题及结论则能保持一直, 既增加了本书的可读性, 同时, 读者在理解时也能轻松许多。

参考文献

[1]屈婉玲, 耿素云, 张立昂.离散数学[M].北京:高等教育出版社, 2008.

[2]左孝凌, 李为鑑, 刘永才.离散数学[M].上海:上海科学技术文献出版社, 1982.

浅谈《离散数学》的教学第4篇

摘要：为了激发学生的学习热情，培养其思维能力和应用能力，根据离散数学课程教学的特点，笔者结合课程教学经验，对离散数学教学进行了研究.文章提出一些教学方法和手段的改革，在实际教学中起到了一定的作用，提高了教学质量.

关键词：离散数学，教学方法，教学手段

【中图分类号】O158-4

On the Teaching "Discrete Mathematics" in

Chenxue Gang Zhou Jiquan

（North China Electric Power University Mathematics， Beijing， 102206， China）

Abstract： In order to stimulate students' enthusiasm for learning， develop their thinking skills and ability， according to the characteristics of Discrete Mathematics Instruction， author of Teaching experience， discrete mathematics teaching were studied. This paper presents some of the reform of teaching methods and means， in the actual teaching has played a certain role in enhancing the quality of teaching.

Keywords： discrete mathematics， teaching methods， teaching means

《离散数学》是计算机科学中重要的基础理论课程之一，它不仅是许多计算机专业课的必备基础，而且对培养学生抽象思维能力和逻辑推理能力有着重要的作用.然而采用以往的教学方法，教学效果往往不够理想.一方面，离散数学知识的分散性令许多学生感到无从下手.另一方面，在传统的离散数学教学中，往往采用“纯数学”教学方法，学生不能很好地体会离散数学对计算机科学的重要意义，所以学习积极性不高.因此，通过教学方法和手段的改革来激发和增强学生的学习兴趣，从而培养学生的创新思维和综合能力，是离散数学教学中非常迫切的需求.本文结合作者近年来从事离散数学课程教学的经验，从教学内容、教学方法、教学手段等方面进行了一些初步探讨.

1精选教学内容

《离散数学》教学内容主要包括数理逻辑、集合论、代数结构及图论等几大分支.各分支均有悠久历史.如果这几部分的内容都要详细讲授，时间上来不及，所以在在教学过程中对讲授内容的选择应当有所侧重.比如简单介绍集合论的理论基础，重点是如何利用集台论的方法解决实际应用问题.在二元关系这部分，重点是二元关系的几个与性质相关问题的论证方法的训练.在数理逻辑上通过将一般命题公式和一阶逻辑公式化成范式，达到强化训练学生逻辑演算能力.图论部分重点放在基本概念的理解和实际问题的处理上，通过对相关定理及其证明思路的理解来体会图论的研究方法.代数系统这部分内容重点放在群论上，尤其要在代数系统、群、子群、循环群、变换群、正规子群的概念及相关问题的理解上下功夫.

2 教学方法探讨

2.1 增加讨论课

老师首先选定讨论的课题，学生分组准备查询相关的文献，并形成自己观点.在讨论课上大家共同交流探讨，从而加深对这门课程的认识.最后各小组完成论文的书写.该方法不仅可以提高学生对离散数学重要性的认识，还可以提高学生互相协作的能力以及书写论文的能力.

2.2 增加趣味性，激发学生的学习兴趣.

“兴趣是最好的老师”，只有激发起学生的学习兴趣，他们才有真正自主学习的欲望.在教学过程中，根据具体的知识点，介绍它的发展史或者引入趣味问题，增加了学生学习离散数学的兴趣，拓宽了学生们的知识面，提高了学生对离散数学课程学习的积极性与主动性.

2.3 注重归纳与小结

离散数学的内容虽然多且散，但通过归纳和小结，可以用一条主线贯穿始终.离散数学讨论的内容主要包含系统中涉及到的静态（基本概念）与动态（运算、操作、推理）.如集合论中是元素（静态）及其上的运算（动态）；代数系统中是集合（静态）及运算（动态）；数理逻辑中是公式（静态）和推理（动态）.通过归纳与小结，学生能够理清头绪，提高学习效率.

3 教学手段改革

3.1 教学网站建设

信息技术对提高教学质量具有重要的影响，必须予以高度重视.为了提高教学质量，我们建设了一个教学支撑网站，一方面大力推进信息技术在教学中的实际运用，促进教学手段和教学方法现代化；另一方面以此提高教与学的效率.

3.2 重视学生作业，定时测验

离散数学的知识不经过学生的独立思考和多做练习是无法牢固掌握的，因此一定要给学生留一定数量的课后习题.但大部分学生不可能把课本上的习题全部做完，教师也不可能完全批阅.这就要求教师布置作业要选其精华，选题必须要有一定的深度和广度，要覆盖所学的内容，尽量选有启发性质的习题.对于学生的作业，要认真仔细批改，将作业中暴露出来的普遍问题，要进行课堂讲评.通过讲评作业，帮助学生澄清模糊和错误的认识.

3.3 新的考核方式

传统的考核方法就是试卷考试，考察学生的基本知识和基本技能，以及解难题的能力.我们尝试做了一些考核方法的改革，把原来的试卷考试和平时的考核两部分，改成了三部分成绩的统一，即添加了一个新的内容：写离散数学的论文.把它的评定结果作为成绩的一个重要部分.所写论文必须要求观点明确、主题鲜明和论述严谨，并且具有一定的创新.

4 结束语

总之，要把离散数学这一门课教好，教师就要不断研究新的教学方法和手段，认真掌握教学规律，借助于现代化教学手段，提倡“启发”式教学.教师只要具有扎实的理论功底，并具有对学生高度负责的精神，就一定能够达到良好的教学效果.

参考文献：

[1]赵青杉，孟国艳.关于离散数学教学改革的思考[J].忻州師范学院学报，2005，21（5）：6 .

[2]耿素云，屈婉玲.离散数学[M].北京：高等教育出版社，2001.

[3]翁梅，刘倩，冯志慧等.“离散数学”课程教学实践与探索[J].计算机教育，2004（12）：62—63.

[4]钟敏，时念云.改革课程实验提高离散数学教学质量 [J].计算机教育，2008，18.

[5] 张艳华，周雪琴，马新娟，王举辉，张立红. 基于卓越工程师的“离散数学”教学改革探索[J]. 当代教育理论与实践. 2013（12）

离散数学习题五第5篇

1.设个体域D={a,b,c}，在D中消去公式x(F(x)yG(y))的量词。甲乙用了不同的演算过程：

甲的演算过程如下： x(F(x)yG(y))x(F(x)(G(a)G(b)G(c)))(F(a)(G(a)G(b)G(c)))

(F(b)(G(a)G(b)G(c)))(F(c)(G(a)G(b)G(c)))(F(a)F(b)F(c))(G(a)G(b)G(c))乙的演算过程如下：

x(F(x)yG(y))xF(x)yG(y)(F(a)F(b)F(c))(G(a)G(b)G(c))

显然，乙的演算过程简单，试指出乙在演算过程中的关键步骤。

解：乙在演算中的关键步骤是，在演算开始就利用量词辖域收缩与扩张等值式，将量词的辖域缩小，因而演算简单。

2.设个体域D={a,b,c}，消去下列各式的量词：

(1)xy(F(x)G(y))(2)xy(F(x)G(y))(3)xF(x)yG(y)(4)（xF(x,y)yG(y))

解：

（1）(F(a)F(b)F(c))(G(a)G(b)G(c))（2）(F(a)F(b)F(c))(G(a)G(b)G(c))（3）(F(a)F(b)F(c))(G(a)G(b)G(c))（4）(F(a,y)F(b,y)F(c,y))(G(a)G(b)G(c))在（1）（2）（4）中均将量词的辖域缩小，所以演算结果都比较简单

3.设个体域D={1,2}，请给出两种不同的解释I1和I2，使得下面公式在I1下都是真命题，而在I2下都是假命题。（1）x(F(x)G(x))（2）x(F(x)G(x))解：

解释I1为：个体为实数集合R，F(x)：x为自然数，G(x)：x为整数。在I1下，（1）为自然数都是整数，（2）为存在整数为自然数。他们都是真命题

解释I2为：个体域仍为实数集R，F(x)：x是无理数，G(x)：x能表示成分数，在I2下，（1）为无理数都能表示成分数，（2）为存在能表示成分数的无理数，他们都是假命题

4.给定公式AxF(x)xF(x)

（1）在解释I1中，个体域D1={a}，证明公式A在I1下的真值为1.（2）在解释I2中，个体域D2={a1,a2,,an}，n2,A在I2下的真值还一定是1吗？为什么？解：

（1）在I1下，xF(x)xF(x)F(a)F(a)F(a)F(a)1（2）在I2下

xF(x)xF(x)(F(a1)F(a2)F(an))(F(a1)F(a2)F(an))

为可满足式，设F(x)：x为奇数，aii,i1,2,n,n2，此时，蕴涵式前件为真，后件为假，故蕴含式为假，若令F(x)；x为整数，则蕴含式前后件均为真，所以（2）中公式在I2下为可满足式

5.给定解释I如下：（a）个体域D={3,4}；（b）f(x)为f(3)4,f(4)3;

（c）F(x,y)为F(3,3)F(4,4)0,F(3,4)F(4,3)1.试求下列公式在I下的真值。

(1)xyF(x,y)(2)xyF(x,y)(3)xyF(x,y)F(f(x),f(y)))

解：

（1）

xyF(x,y)x(F(x,3)F(x,4))(F(3,3)F(3,4))(F(4,3)F(4,4))111（2）

x(F(x,3)F(x,4))(F(3,3)F(3,4))(F(4,3)F(4,4)0（3）

x((F(x,3)F(f(x),f(3)))(F(x,4)F(f(x),f(4))))(((F(3,3)F(f(3),f(3)))(F(3,4)F(f(3),f(4))))(((F(4,3)F(f(4),f(3)))(F(4,4)F(f(4),f(4))))1

6.甲使用量词辖域收缩与扩张等值式进行如下演算

x(F(x)G(x,y))xF(x)G(x,y)

乙说甲错了，乙说的对吗？为什么？

解：乙说的对，甲错了，全称量词的指导变元x，辖域为(F(x)G(x,y))，其中F(x)与G(x,y)都是x的约束变元，因而不能讲量词的辖域变小

7.请指出下面等值运算的两处错误

xy(F(x)(G(y)H(x,y))xy(F(x)(G(y)H(x,y))xy((F(x)G(y))H(x,y))

解：

演算的第一步，应用量词辖域收缩与扩张算值式时丢掉了否定连接词，演算的第二步，在原错的基础上又用错了等值式

(F(x)G(y)H(x,y))和(F(x)G(y)H(x,y))不等值

8.在一阶逻辑中将下列命题符号化，要求用两种不同的等值形式（1）没有小于负数的正数

（2）相等的两个角未必都是对顶角解：

（1）x(F(x)G(x))x(G(x)F(x))

其中F(x)：x小于负数，G(x)：x是正数

（2）xy(F(x)F(y)H(x,y)L(x,y)xy(F(x)F(y)H(x,y)L(x,y))其中F(x)：x是角，H(x,y)：x=y，L(x,y)：x和y是对顶角

9.设个体域D为实数集合，命题“有的实数既是有理数又是无理数”，这显然是个假命题。可是某人却说这是真命题，其理由如下

设F(x)：x是有理数，G(x）：x是无理数。xF(x),xG(x)都是真命题，于是，xF(x)xG(x)x(F(x)G(x))由于xF(x)xG(x)是真命题，故x(F(x)G(x))也是真命题，即有的实数是有理数，也是无理数这个人的结论对吗？为什么？解：存在量词对无分配律

10.在求前束范式时有人说x(F(x)G(x,y))已是前束范式，理由是量词已在公式的前面，他说的对吗？为什么？

解：在前束范式中，否定联结词不能在量词前面出现 11.有人说无法求公式

x(F(x)G(x))xG(x,y)的前束范式，因为公式中的两个量词的指导变元相同。他的理由对吗？为什么？换名规则可以使两个指导变元不相同 12.求下列各式的前束范式：(1)xF(x)yG(x,y)(2)x(F(x,y)yG(x,y,z))(3)xF(x,y)xG(x,y)

(4)x1(F(x1)G(x1,x2))(x2H(x2)x3L(x2,x3))(5)x1F(x1,x2)(F(x1)x2G(x1,x2))解：

（1）xy(F(x)G(z,y))（2）xt(F(x,t)G(x,t,z))

（3）x1x2x3x4((F(x1,y)G(x2,y))(G(x3,y)F(x4,y)))（4）y1y2y3((F(y1)G(y1,x2))(H(y2)L(x2,y3)))（5）y1y2(F(y1,x2)(F(x1)G(x1,y2)))

13.将下列命题符号化，要求符号化的公式权威前束范式：（1）有点火车比有的汽车跑的快（2）有的火车比所有的汽车跑的快

（3）说有的火车比所有汽车跑得快是不对的（4）说有的飞机比有的汽车慢也是不对的解：

（1）xy(F(x)G(y)H(x,y))其中F(x)：x是汽车 G(y):y是火车 H(x,y)：x比y跑得快（2）xy(F(x)(G(y)H(x,y)))其中F(x)：x是火车 G(y):y是汽车 H(x,y)：x比y跑得快

（3)xy(F(x)G(y)H(x,y))其中F(x)：x是火车 G(y):y是汽车H(x,y)：x比y跑得快

（4）xy(F(x)G(y)H(x,y))其中F(x)：x是飞机 G(y):y是汽车 H(x,y)：x比y跑得慢

14.在自然推理系统F中，指出下面各证明序列中的错误：（1）①F(x)xG(x)前提引入

②F(c)G(c)①EI规则（2）①xF(x)yG(y)前提引入

②F(a)F(b)①EI规则（3）①F(y)G(y)前提引入

②x(F(x)G(x))①EG规则（4）①F(a)F(b)前提引入

②x(F(x)G(x))①EG规则（5）①F(c)G(c)前提引入

②x(F(x)G(x))①UG规则

解：（1）对F(x)xG(x)不能使用EI规则，它不是前束范式，首先化成前束范式F(x)xG(x)x(F(y)G(x))，因为量词辖域(F(y)G(x)中，除了x还有自由出现的y所以不能用EI规则

（2）对xF(x)yG(y)也应该先化成前束范式才能消去量词，其前束范式为xy(F(x)G(y))，要消去量词，既要用UI规则，又要用EI规则（3）这里A(y)=F(y)G(y)满足要求

（4）这里，使F(a)为真的a不一定使G(a)为真，同样的，使G(b)为真的b不一定使F(b)为真

（5）这里，c为个体常项，不能对F(c)G(c)引入全称量词 15.在自然推理系统F中，构造下面推理的证明：（1）前提：xF(x)y((F(y)G(y))R(y)),xF(x)

结论：xR(x)

（2）前提：x(F(x)(G(a)R(x))),xF(x)

结论：x(F(x)R(x))（3）前提：x(F(x)G(x)),xG(x)

结论：xF(x)

（4）前提：x(F(x)G(x)),x(G(x)R(x)),xR(x)

结论：xF(x)

（1）证明：1 xF(x)

前提引入 xF(x)y((F(y)G(y))R(y))

前提引入

y((F(y)G(y))R(y)

2假言推理

F(c)EI(F(c)G(c))R(c)

UI F(c)G(c)

附加

R(c)6假言推理

xR(x)

7EG

（2）证明：1 xF(x)

前提引入

x(H(x)),xF(x)x(F(a)G(a))),G(a)I(y)H(a)x(F(x)(G(a)R(x)))

x(G(a)H(a)I(a))前提引入 F(c)EI F(c)(G(a)R(c))

UI G(a)R(c)4假言推理

R(c)

5化简

F(c)R(c)6合取

x(F(x)R(x))

7EG

（3）证明：1 xF(x)

前提引入xF(x)

1置换F(c)

2UI

x(F(x)G(x))

前提引入F(c)G(c)

4UI

6F(c)5析取三段论xF(x)

6EG(4)证明：1 x(F(x)G(x))

前提引入

F(y)G(y)UI x(G(x)R(X))

前提引入

G(y)R(y)

UI xR(x)

前提引入

R(y)

5UI G(y)

6析取三段论

8F(y)

27析取三段论

xF(x)

UG 16.找一个解释I，在I下，使得xF(x)xG(x)为真，而使得x(F(x)G(x))为假，从而说明xF(x)xG(x)x(F(x)G(x))。解：取个体域为自然数集合N，F(x):x为奇数，G(x):x 为偶数。显然在以上解释下xF(x)xG(x)为真而x(F(x)G(x))为假。

17.给定推理如下：

前提：x(F(x)G(x)),x(H(x)G(x))

结论：x(H(x)F(x))。

有些人给出的证明如下：

证明：

①xH(x)附加前提引入

②H(y)

③x(H(x)G(x))

④H(y)G(y)

⑤G(y)

⑥x(F(x)G(x))

⑦F(y)G(y)

⑧F(y)

⑨xF(x)

解：根据16题可知两公式并不等价。

①UI 前提引入 ③UI ②⑤假言推理前提引入 ⑥UI ⑤⑦拒取式 ⑧UG 并且说，由附加前提证明法可知，推理正确，请指出以上证明的错误。18.给出上题（17）推理的正确证明（注意，不能使用附加前提证明法）。

证明：1 x(F(x)G(x))

前提引入

x(H(x)G(x))

前提引入

F(y)G(y)UI H(y)G(y)

2UI G(y)F(y)

3置换H(y)F(y)5假言三段论x(H(x)F(x))UG

19.在自然推理系统F中，构造下列推理的证明：

前提：xF(x)xG(x)

结论：x(F(x)G(x))

证明：1xF(x)xG(x)

前提引入 yF(y)xG(x)

换名规则

yx(F(x)G(x))化简

x(F(x)G(x))EI

20.在自然推理系统F中，构造下列推理的证明（可以使用附加前提证明法）：（1）前提：x(F(x)G(x))

结论：xF(x)xG(x)（2）前提：x(F(x)G(x))

结论：xF(x)xG(x)

证明：（1）.1xF(x)

附加前提引入

F(y)UI x(F(x)G(x))

前提引入

F(y)G(y)

3UI G(y)3假言推理

xG(x)

（2）1 xF(x)

附加前提引入xF(x)

置换原则F(c)

2EI

x(F(x)G(x))

前提引入

F(c)G(c)

G(c)

5析取三段论xG(x)

EG 21.在自然推理系统中，构造下面推理的证明：

没有白色的乌鸦，北京鸭都是白色的。因此，北京鸭都不是乌鸦。

设F(x):x是乌鸦，G(x)：x是北京鸭，H(x):x是白色的。前提 x(F(x)H(x)),x(G(x)H(x))结论 x(G(x)F(x))

证明：1 x(F(x)H(x))

前提引入 2 x(F(x)H(x))

置换原则 3 x(F(x)H(x))

置换原则 4 x(H(x)F(x))

H(y)F(y)

4UI 6 x(G(x)H(x))

前提引入 7 G(y)H(y)

5UI 8 G(y)F(y)

7假言三段论 9 x(G(x)F(x))

8UG 22.在自然推理系统F中，构造下面推理的证明：

(1)偶数都能被2整除。6是偶数。所以6能被2整除。

(2)凡大学生都是勤奋的。王晓山不勤奋，所以王晓山不是大学生。

（1）设F(x):x为偶数，G(x)：x能被2整除前提 x(F(x)G(x)),F(6)结论 G(6)证明：1 x(F(x)G(x))

前提引入

F(6)G(6)

1UI F(6)

前提引入 G(6)

3假言推理

(2)设F(x):x是大学生，G(x)：x是勤奋的，a 王晓山前提 x(F(x)G(x)),G(a)，结论 F(a)

证明：1 x(F(x)G(x))

前提引入

F(a)G(a)

1UI G(a)

前提引入

F(a)3 据取式

23.在自然推理系统F中，证明下面推理：

（1）每个有理数都是实数。有的有理数是整数。因此，有的实数是整数9（2）有理数，无理数都是实数。虚数不是实数。因此，虚数既不是有理数也不是无理数。

（1）设F(x):x是有理数，G(x)：x实数，H(x):x是整数

前提 x(F(x)G(x))，x(F(x)H(x))

结论 x(G(x)H(x))

(2)设F(x):x是有理数，G(x)：x是无理数，H(x):x是实数，I(x):x是虚数前提 x((F(x)G(x))H(x)),x(I(x)H(x))结论 x(I(x)(F(x)G(x)))

证明：1 x(I(x)H(x))

前提引入

I(y)H(y)

UI x((F(x)G(x))H(x)), 前提引入

4(F(y)G(y))H(y)UI H(y)(F(y)G(y))

置换 I(y)(F(y)G(y))

5假言三段论

x(I(x)(F(x)G(x))

UG 24.在自然推理系统F中，构造下面推理的证明：

每个喜欢不行的人都不喜欢骑自行车。每个人或者喜欢骑自行车或者喜欢乘汽车。有的人不喜欢乘汽车，所以有的人不喜欢步行。（个体域为人类集合）

设F(x):x喜欢步行，G(x)：x喜欢骑自行车，H(x):x喜欢乘汽车前提 x(F(x)G(x)，x(G(x)H(x)),xH(x)结论 xF(x)

证明：1 xH(x)

前提引入

H(c)

UI x(G(x)H(x))

前提引入

G(c)H(c)UI G(c)

4析取三段论

x(F(x)G(x))

前提引入

F(c)G(c)

F(c)

57拒取式

xF(x)

8UG 25.在自然推理系统F中，构造下列推理的证明（个体域为人类集合）：

每个科学工作者都是刻苦钻研的，每个刻苦钻研而又聪明的人在他的事业中都将获得成功。王大海是科学工作者，并且是聪明的，所以王大海在他的事业中将获得成功。

设F(x):x是科学工作者，G(x)：x是刻苦钻研的，H(x):x是聪明的，I(x):x在事业中获得成功

前提 x(F(x)G(x))，x(G(x)H(x)I(x))，a:王大海，F(a),H(a)结论 I(a)证明：1 F(a)

前提引入

x(F(x)G(x))

前提引入

F(a)G(a)

2UI G(a)3假言推论

H(a)

前提引入 x(G(x)H(x)I(x))

前提引入

G(a)H(a)I(a)

6UI G(a)H(a)5合取

离散数学习题及答案第6篇

一、（10分）某项工作需要派A、B、C和D 4个人中的2个人去完成，按下面3个条件，有几种派法？如何派？

(1)若A去，则C和D中要去1个人；

(2)B和C不能都去；

(3)若C去，则D留下。

解设A：A去工作；B：B去工作；C：C去工作；D：D去工作。则根据题意应有：ACD，(B∧C)，CD必须同时成立。因此

(ACD)∧(B∧C)∧(CD)

(A∨(C∧ D)∨(C∧D))∧(B∨C)∧(C∨D)

(A∨(C∧ D)∨(C∧D))∧((B∧C)∨(B∧D)∨C∨(C∧D))

(A∧B∧C)∨(A∧B∧D)∨(A∧C)∨(A∧C∧D)

∨(C∧ D∧B∧C)∨(C∧ D∧B∧D)∨(C∧ D∧C)∨(C∧ D∧C∧D)∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧D∧C∧D)

F∨F∨(A∧C)∨F∨F∨(C∧ D∧B)∨F∨F∨(C∧D∧B)∨F∨(C∧D)∨F (A∧C)∨(B∧C∧ D)∨(C∧D∧B)∨(C∧D)

(A∧C)∨(B∧C∧ D)∨(C∧D)

T

故有三种派法：B∧D，A∧C，A∧D。

二、（15分）在谓词逻辑中构造下面推理的证明：某学术会议的每个成员都是专家并且是工人，有些成员是青年人，所以，有些成员是青年专家。

解：论域：所有人的集合。S(x)：x是专家；W(x)：x是工人；Y(x)：x是青年人；则推理化形式为：

x(S(x)∧W(x))，xY(x)x(S(x)∧Y(x))

下面给出证明：

(1)xY(x)P

(2)Y(c)T(1)，ES

(3)x(S(x)∧W(x))P

(4)S(c)∧W(c)T(3)，US

(5)S(c)T(4)，I

(6)S(c)∧Y(c)T(2)(5)，I

(7)x(S(x)∧Y(x))T(6)，EG

三、（10分）设A、B和C是三个集合，则AB(BA)。

证明：ABx(x∈A→x∈B)∧x(x∈B∧xA)x(xA∨x∈B)∧x(x∈B∧xA)

x(x∈A∧xB)∧x(xB∨x∈A)x(x∈A∧xB)∨x(x∈A∨xB)

(x(x∈A∧xB)∧x(x∈A∨xB))(x(x∈A∧xB)∧x(x∈B→x∈A))

(BA)。

四、（15分）设A＝{1，2，3，4，5}，R是A上的二元关系，且R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。

解r(R)＝R∪IA＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>}

s(R)＝R∪R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，2>，<4，2>，<4，3>} R＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}

R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>}

R＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}＝R

t(R)＝Ri＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，1>，<5，4>，<5，i14232－

15>}。

五、（10分）R是非空集合A上的二元关系，若R是对称的，则r(R)和t(R)是对称的。

证明对任意的x、y∈A，若xr(R)y，则由r(R)＝R∪IA得，xRy或xIAy。因R与IA对称，所以有yRx或yIAx，于是yr(R)x。所以r(R)是对称的。

下证对任意正整数n，R对称。

因R对称，则有xRyz(xRz∧zRy)z(zRx∧yRz)yRx，所以R对称。若Rn对称，则xRn1yz(xRnz∧zRy)z(zRnx∧yRz)yRn1x，所以Rn1对称。因此，对任意正整数n，Rn对称。对任意的x、y∈A，若xt(R)y，则存在m使得xRy，于是有yRx，即有yt(R)x。因此，t(R)是对称的。

六、（10分）若f：A→B是双射，则f：B→A是双射。

证明因为f：A→B是双射，则f是B到A的函数。下证f是双射。

对任意x∈A，必存在y∈B使f(x)＝y，从而f(y)＝x，所以f是满射。

对任意的y1、y2∈B，若f(y1)＝f(y2)＝x，则f(x)＝y1，f(x)＝y2。因为f：A→B是函数，则y1＝y2。所以f是单射。

综上可得，f：B→A是双射。

七、（10分）设是一个半群，如果S是有限集，则必存在a∈S，使得a*a＝a。

证明因为是一个半群，对任意的b∈S，由*的封闭性可知，b＝b*b∈S，b＝b*b∈S，…，bn∈S，…。

因为S是有限集，所以必存在j＞i，使得bi＝bj。令p＝j－i，则bj＝bp*bj。所以对q≥i，有bq＝bp*bq。

因为p≥1，所以总可找到k≥1，使得kp≥i。对于bkp∈S，有bkp＝bp*bkp＝bp*(bp*bkp)＝…＝232－1－1－1－1－1－1－1－1－1mm222nbkp*bkp。

令a＝bkp，则a∈S且a*a＝a。

八、（20分）（1）若G是连通的平面图，且G的每个面的次数至少为l(l≥3)，则G的边数m与结点数n有如下关系：

m≤

rl(n－2)。l2l证明设G有r个面，则2m＝

2)。d(f)≥lr。由欧拉公式得，n－m＋r＝2。于是，m≤l2(n－ii

1（2）设平面图G＝是自对偶图，则| E|＝2(|V|－1)。

证明设G＝是连通平面图G＝的对偶图，则G G，于是|F|＝|V*|＝|V|，将其代入欧拉公式|V|－|E|＋|F|＝2得，|E|＝2(|V|－1)。**

离散数学考试试题（B卷及答案）

一、（10分）证明(P∨Q)∧(PR)∧(QS)S∨R

证明因为S∨RRS，所以，即要证(P∨Q)∧(PR)∧(QS)RS。

(1)R附加前提

(2)PRP

(3)PT(1)(2)，I

(4)P∨QP

(5)QT(3)(4)，I

(6)QSP

(7)ST(5)(6)，I

(8)RSCP

(9)S∨RT(8)，E

二、（15分）根据推理理论证明：每个考生或者勤奋或者聪明，所有勤奋的人都将有所作为，但并非所有考生都将有所作为，所以，一定有些考生是聪明的。

设P(e)：e是考生，Q(e)：e将有所作为，A(e)：e是勤奋的，B(e)：e是聪明的，个体域：人的集合，则命题可符号化为：x(P(x)(A(x)∨B(x)))，x(A(x)Q(x))，x(P(x)Q(x))x(P(x)∧B(x))。

(1)x(P(x)Q(x))P

(2)x(P(x)∨Q(x))T(1)，E

(3)x(P(x)∧Q(x))T(2)，E

(4)P(a)∧Q(a)T(3)，ES

(5)P(a)T(4)，I

(6)Q(a)T(4)，I

(7)x(P(x)(A(x)∨B(x))P

(8)P(a)(A(a)∨B(a))T(7)，US

(9)A(a)∨B(a)T(8)(5)，I

(10)x(A(x)Q(x))P

(11)A(a)Q(a)T(10)，US

(12)A(a)T(11)(6)，I

(13)B(a)T(12)(9)，I

(14)P(a)∧B(a)T(5)(13)，I

(15)x(P(x)∧B(x))T(14)，EG

三、（10分）某班有25名学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。而6个会打网球的人都会打另外一种球，求不会打这三种球的人数。

解设A、B、C分别表示会打排球、网球和篮球的学生集合。则：

|A|＝12，|B|＝6，|C|＝14，|A∩C|＝6，|B∩C|＝5，|A∩B∩C|＝2，|(A∪C)∩B|＝6。

因为|(A∪C)∩B|＝(A∩B)∪(B∩C)|＝|(A∩B)|＋|(B∩C)|－|A∩B∩C|＝|(A∩B)|＋5－2＝6，所以|(A∩

B)|＝3。于是|A∪B∪C|＝12＋6＋14－6－5－3＋2＝20，|ABC|＝25－20＝5。故，不会打这三种球的共5人。

四、（10分）设A1、A2和A3是全集U的子集，则形如Ai(Ai为Ai或Ai)的集合称为由A1、A2和

i1

3A3产生的小项。试证由A1、A2和A3所产生的所有非空小项的集合构成全集U的一个划分。

证明小项共8个，设有r个非空小项s1、s2、…、sr(r≤8)。

对任意的a∈U，则a∈Ai或a∈Ai，两者必有一个成立，取Ai为包含元素a的Ai或Ai，则a∈Ai，i13即有a∈si，于是Usi。又显然有siU，所以U＝si。

i1i1i1i1rrrr

任取两个非空小项sp和sq，若sp≠sq，则必存在某个Ai和Ai分别出现在sp和sq中，于是sp∩sq＝。综上可知，{s1，s2，…，sr}是U的一个划分。

五、（15分）设R是A上的二元关系，则：R是传递的R*RR。

证明(5)若R是传递的，则∈R*Rz(xRz∧zSy)xRc∧cSy，由R是传递的得xRy，即有∈R，所以R*RR。

反之，若R*RR，则对任意的x、y、z∈A，如果xRz且zRy，则∈R*R，于是有∈R，即有xRy，所以R是传递的。

六、（15分）若G为连通平面图，则n－m＋r＝2，其中，n、m、r分别为G的结点数、边数和面数。证明对G的边数m作归纳法。

当m＝0时，由于G是连通图，所以G为平凡图，此时n＝1，r＝1，结论自然成立。

假设对边数小于m的连通平面图结论成立。下面考虑连通平面图G的边数为m的情况。

设e是G的一条边，从G中删去e后得到的图记为G，并设其结点数、边数和面数分别为n、m和r。对e分为下列情况来讨论：

若e为割边，则G有两个连通分支G1和G2。Gi的结点数、边数和面数分别为ni、mi和ri。显然n1＋n2＝n＝n，m1＋m2＝m＝m－1，r1＋r2＝r＋1＝r＋1。由归纳假设有n1－m1＋r1＝2，n2－m2＋r2＝2，从而(n1＋n2)－(m1＋m2)＋(r1＋r2)＝4，n－(m－1)＋(r＋1)＝4，即n－m＋r＝2。

若e不为割边，则n＝n，m＝m－1，r＝r－1，由归纳假设有n－m＋r＝2，从而n－(m－1)＋r－1＝2，即n－m＋r＝2。

由数学归纳法知，结论成立。

七、（10分）设函数g：A→B，f：B→C，则：

(1)fg是A到C的函数；

(2)对任意的x∈A，有fg(x)＝f(g(x))。

证明(1)对任意的x∈A，因为g：A→B是函数，则存在y∈B使∈g。对于y∈B，因f：B→C是函数，则存在z∈C使∈f。根据复合关系的定义，由∈g和∈f得∈g*f，即∈fg。所以Dfg＝A。

对任意的x∈A，若存在y1、y2∈C，使得、∈fg＝g*f，则存在t1使得∈g且∈f，存在t2使得∈g且∈f。因为g：A→B是函数，则t1＝t2。又因f：B→C是函数，则y1＝y2。所以A中的每个元素对应C中惟一的元素。

综上可知，fg是A到C的函数。

(2)对任意的x∈A，由g：A→B是函数，有∈g且g(x)∈B，又由f：B→C是函数，得∈f，于是∈g*f＝fg。又因fg是A到C的函数，则可写为fg(x)＝f(g(x))。

八、（15分）设是的子群，定义R＝{|a、b∈G且a1*b∈H}，则R是G中的－

一个等价关系，且[a]R＝aH。

证明对于任意a∈G，必有a1∈G使得a1*a＝e∈H，所以∈R。－－

若∈R，则a1*b∈H。因为H是G的子群，故(a1*b)1＝b1*a∈H。所以∈R。－－－－

若∈R，∈R，则a1*b∈H，b1*c∈H。因为H是G的子群，所以(a1*b)*(b1*c)＝a－－－－

－1*c∈H，故∈R。

综上可得，R是G中的一个等价关系。

对于任意的b∈[a]R，有∈R，a1*b∈H，则存在h∈H使得a1*b＝h，b＝a*h，于是b∈aH，－－

[a]RaH。对任意的b∈aH，存在h∈H使得b＝a*h，a1*b＝h∈H，∈R，故aH[a]R。所以，[a]R－

离散数学复习题第7篇

• 设命题p，r的真值为1，命题q，s的真值为0，则（p→q）(﹁r→s)的真值

为。

• 只要4不是素数，3就是素数，用谓语表达式符号化为。

• D=｛｝，则幂集ρ(D)=

• A={a,{b}}，B=｛｝，则A×B=

• 若集合A，B的元素个数分别为|A|=m,|B|=n,则A到B有种不同二元关系。• 设A=｛1,2,3,4｝，B=｛4,5，6,7｝，R=｛<1,4>，<1,6><2,4>，<3,5>，<3,6>｝是由A

到B的二元关系，则domR=，ranR=

• I A是集合A上的恒等关系，A上的关系R具有性当且仅当IAR。• 二元关系R是等价关系，当且仅当的R是。

9.设K4是有4个点的无向完全图，则K4有条边。

10.无向图G是欧拉图当且仅当。

11.在任何无向图这，所有顶点的度数之和等于边数的倍。

12.设K5是有5个点的无向完全图，则K5有条边。

13.无向图G是欧拉图当且仅当。

计算题

• 求公式（PQ）→（QR）的主析取范式

• 集合A=｛a,b,c｝,R={,,,}是集合A上的二元关系，求R的自反

闭包r(R),对称闭包s(R)和传递闭包t(R)(用矩阵运算)，并画出各闭包的关系图。• 设图G

• 写出G的邻接矩阵

• 求各结点的初度，入度

• 求V3到V2长度是3的路的数目

• 设集合A=｛1,2，3,4,6,8，12｝，R是A上的整除关系，• 画出偏序图的哈斯图；

证明题

• 在自然推理系统p中构造下面推理的证明

前提：﹁r，﹁pr，（q）→p

结论：q→﹁

• 在自然系统p中构造下面推理的证明

前提：pq,p→r,q→s

离散数学简介及应用第8篇

离散数学是现代数学的一个重要分支,是计算机类专业的重要课程。它以研究离散量的结构及相互间的关系为主要目标,研究对象一般是有限个或可数个元素,因此离散数学可以充分描述计算机学科离散性的特点。它是传统的逻辑学、集合论(包括函数)、数论基础、算法设计、组合分析、离散概率、关系理论、图论与树、抽象代数、布尔代数,计算模型(语言与自动机)等汇集起来的一门综合学科。该课程主要介绍离散数学的各个分支的基本概念、基本理论和基本方法。这些概念、理论及方法大量地应用于数字电路、编译原理、数据结构、操作系统、数据库系统、算法的分析与设计、人工智能、计算机网络等专业课程中;同时,该课程提供的训练有益于学生概括抽象能力、逻辑思维能力、归纳构造能力的提高,有利于学生严谨、完整、规范的科学态度的培养。

2.离散数学在其他学科的应用

2.1数理逻辑在人工智能中的应用

人工智能是计算机学科一个非常重要的方向。离散数学在人工智能中的应用,主要是数理逻辑部分在人工智能中的应用,包括命题逻辑和谓词逻辑。命题逻辑就是研究以命题为单位进行前提与结论之间的推理, 而谓词逻辑就是研究句子内在的联系。人工智能共有两个流派:连接主义流派和符号主义流派。在符号主义流派里,他们认为现实世界的各种事物可以用符号的形式表示出来, 其中最主要的就是人类的自然语言可以用符号进行表示。语言的符号化就是数理逻辑研究的基本内容, 计算机智能化的前提就是将人类的语言符号化成机器可以识别的符号,这样计算机才能进行推理,才能具有智能。由此可见,数理逻辑中重要的思想、方法及内容贯穿人工智能的整个学科。

2.2图论在数据结构中的应用

离散数学在数据结构中的应用,主要是图论部分在数据结构中的应用,其中树在图论中占着重要的地位。树是一种非线性数据结构, 在现实生活中可以用树来表示某一家族的家谱或某公司的组织结构, 也可以用它来表示计算机中文件的组织结构,树中二叉树在计算机科学中有着重要的应用。二叉树中三种遍历方法:前序遍历法、中序遍历法和后序遍历法,均与离散数学中的图论有密不可分的关系。

2.3离散数学在生物信息学中的应用

生物信息学是现代计算机科学一个崭新的分支, 是计算机科学与生物学相结合的产物。目前,美国有一个国家实验室Sandia国家实验室 , 主要进行组合编码理论和密码学的研究 ,该机构在美国和国际学术界有很高的地位。另外,由于DNA是离散数学中的序列结构,美国科学院院士,近代离散数学的奠基人Rota教授预言,生物学中的组合问题将成为离散数学的一个前沿领域。而且IBM公司将成立一个生物信息学研究中心。在1994年, 美国计算机科学家阿德勒曼公布了DNA计算机的理论, 并成功地运用DNA计算机解决了一个有向哈密尔顿路径问题,这一成果迅速在国际产生了巨大反响,同时引起了国内学者的关注。DNA计算机的基本思想是:以DNA碱基序列作为信息编码的载体,利用现代分子生物学技术,在试管内控制酶作用下的DNA序列反应,作为实现运算的过程;这样,以反应前DNA序列作为输入的数据, 反应后的DNA序列作为运算的结果,DNA计算机几乎能够解决所有的NP完全问题。

2.4离散数学在门电路设计中的应用

在数字电路中,离散数学的应用主要体现在数理逻辑部分的使用。在数字电路中, 广于使用的逻辑代数即为布尔代数。逻辑代数中的逻辑运算与、或、非、异或与离散数学中的合取,析取、否定、异或(排斥或)相对应。数字电路的学习重点在于掌握电路设计技术,在设计门电路时,要求设计者根据给出的具体逻辑问题,求出实现这一逻辑功能的逻辑电路。

总之,离散数学无处不在,它的主要应用就是在各种复杂关系中找出最优的方案。离散数学完全可以看成是一门量化的关系学,一门量化了的运筹学,一门量化了的管理学。现在我国每一所大学的计算机专业都开设离散数学课程, 正是由于离散数学在计算机科学中的重要应用, 因此可以说没有离散数学就没有计算机理论,也就没有计算机科学。所以应努力学习离散数学,推动离散数学的研究,使它在计算机中有着更广泛的应用。

摘要：离散数学是现代数学的一个重要分支,在各学科领域,特别在计算机科学与技术领域有着广泛的应用,同时是计算机专业的许多专业课程,如程序设计语言、数据结构、算法设计与分析等课程必不可少的先行课程。通过离散数学的学习,不但可以掌握处理离散结构的描述工具和方法,为后续课程的学习创造条件,而且可以提高抽象思维和严格的逻辑推理能力,为将来参与创新性的研究和开发工作打下坚实的基础。