离散数学试卷及答案

离散数学试卷及答案（精选7篇）

离散数学试卷及答案 篇1

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

一、（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－

＝aH。

离散数学试卷及答案 篇2

一、离散数学在计算机学科中的应用

1、在数据结构上的应用

在计算机科学中,需要依据数据机构知识解决相应的问题,在问题中处理的数据,需要从具体问题中建立一个抽象的数学模型,并且对这个模型进行计算和设计,之后编出相应的程序,并且实施有效的整合和测试,以此对相应的问题进行解答。在这个过程中研究的主要内容是指数据的逻辑结构、基本操作方式以及物理存储结构等。在这个过程中的逻辑推理和计算方式主要是依据离散数学的知识和思维方式。在离散数学中的集合论、关系以及图论等都可以很好的反应出数据结构的知识。

2、在数据库中的应用

计算机数据库在很多领域上都有很好的应用,关系数据库逐渐的成为发展的主流,离散数学中笛卜尔积是纯数学理论,主要是亚久关系数据库的主要方向,拥有至关重要的影响力,不但对理论和方案有着一定的影响力,也起到一定的促进作用,有助于数据库技术更快、更好的发展。

3、在编译原理中的应用

计算机中的编译是一个相对比较复杂的程序,经典的编译包括词语、语法、代码优化、中间代码、错误代码以及各类信息表等程序。离散数学中的计算模型主要是针对三个方面的计算模型实施研究,其中包括有限状态、文法以及图灵机。主要是指语法与文法、有限状态机、图灵机依据应用罗塑形术。一般来说,简单的逻辑推理,也包含基本的生产技术。推理机主要是在对知识库中知识点进行推理的情况,主要是依据问题研究和分析确保计算机的整体运行。

4、在人工智能中的应用

在人工智能中的研究和实际应用中的过程中,逻辑推理是工作的重点之一。其中主要是依据逻辑推理数学,实现对人工智能的应用。数学推理中的离散数学以及布尔代数章节中的知识点,主要是用作初期研究人工智能的理论和技术。在丽萨数学图例以及布尔代数章节中,主要就是指在人工智能的基础上实施管理,从而获取良好的护理基础知识,以此研究和分析非正式的工作,其中包括医疗诊断、信息搜索等,证明相应的问题。由此可见,在对人工智能进行研究的过程中,需要推理机的应用和知识库中的知识点,并对其专家思维进行划分,有效的解决相应的问题。

5、在计算机体系结构中的应用

在计算机学科体系中,命令系统的设计和改变都有着一定的影响力,优化原有的命令系统有助于提升整体计算机的效率。命令系统的方式有很多种,其中有一种是优化命令的格式,主要是指依据最短的位数展示命令实施的做法和信息。保证程序中的命令平均数是最短的。由此可见,可以应用哈弗曼压缩概念进行实施,从而获取优化的命令。

二、离散数学在计算机学科中的重要性

离散数学是一种数学用具,在计算机专业和技术发展的过程中占据着不可忽视的影响力。教师在实际教学中,可以根据离散数学中的自动理论来研究形式语言,依据谓词演算内容对程序的正确性实施研究和分析,也称之为利用袋鼠结构对编码理论进行研究和分析等。离散数学在实际计算机教学中占据中重要的位置,依据离散数学教学的方式可以用作计算机教学的研究方案和方向,以此不断的完善计算机专业教学。现阶段,计算机学科在实际教学中,若是对离散数学知识有所了解的话,就会提升研究计算机技术的效率。由此可见,离散数学在计算机学科中有着不可取代的作用。

三、结束语

综上所述,离散数学理论和技术在计算机很多方面都有应用,从科学计算到信息资源的处理,从计算机管理结构到应用技术,从计算机软件到计算机硬件,从人工智能到分布式的体系,这些都有离散数学的理论和技术。离散数学知识已经成为计算机专业学习中主要的课程之一。要想成为一名专业的计算机学生,就必须具备这项课程知识,这样才能更加深入的了解计算机更多的知识和技能。

摘要：离散数学知识是计算机技术和应用过程中重要的组成部分,更是有效的基础教学和应用。离散教学的一章节知识都在计算机中应用,由此可见,离散数学教学在计算机专业教学中有着至关重要的作用和影响力,这样就需要学习计算机专业的学生在学习的过程中学习离散数学知识,从而为今后的计算机知识学习奠定有效的基础。

关键词：离散数学,计算机学科,应用,重要性

参考文献

[1]黄震.《离散数学》课程在计算机学科中的作用及其应用[J].赤峰学院学报:自然科学版,2011,05.

[2]贺玉珍,张海江.浅析《离散数学》在计算机学科中的应用[J].现代计算机:专业版,2010,03.

离散数学试卷及答案 篇3

在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。

1．下列句子不是命题的是（D）．．A．中华人民共和国的首都是北京 C．雪是黑色的

B．张三是学生 D．太好了！

2．下列式子不是谓词合式公式的是（B）．．A．（x）P(x)→R(y)B．(x)┐P（x）(x)(P(x)→Q(x))C．(x)(y)(P(x)∧Q(y))→(x)R(x)D．(x)(P(x,y)→Q(x,z))∨(z)R(x,z)3．下列式子为重言式的是（）A．(┐P∧R)→Q C．P∨(P∧Q)

B．P∨Q∧R→┐R D．(┐P∨Q)(P→Q)4．在指定的解释下，下列公式为真的是（）A．(x)(P(x)∨Q(x)),P(x):x=1,Q(x):x=2,论域:{1,2} B．(x)(P(x)∧Q(x)),P(x):x=1,Q(x):x=2,论域: {1,2} C．(x)(P(x)→Q(x)),P(x):x>2,Q(x):x=0,论域:{3,4} D．(x)(P(x)→Q(x)),P(x):x>2,Q(x):x=0,论域:{3,4} 5．对于公式(x)(y)(P(x)∧Q(y))→(x)R(x,y)，下列说法正确的是（）A．y是自由变元 C．(x)的辖域是R(x, y)

B．y是约束变元

D．(x)的辖域是(y)(P(x)∧Q(y))→(x)R(x,y)6．设论域为{1,2}，与公式(x)A(x)等价的是（）A．A(1)∨A(2)C．A(1)∧A(2)

B．A(1)→A(2)D．A(2)→A(1)7．设Z+是正整数集，R是实数集，f:Z+→R, f(n)=log2n ,则f（）A．仅是入射 C．是双射

B．仅是满射 D．不是函数

8．下列关系矩阵所对应的关系具有反对称性的是（）101A．011

100001C．001

100100B．011

101101D．010

1009．设R1和R2是集合A上的相容关系，下列关于复合关系R1R2的说法正确的是（）A．一定是等价关系

B．一定是相容关系

全国2010年7月自学考试离散数学试题

C．一定不是相容关系

10．下列运算不满足交换律的是（）．．．A．a*b=a+2b C．a*b=|a-b|

D．可能是也可能不是相容关系

B．a*b=min(a,b)D．a*b=2ab

11．设A是偶数集合，下列说法正确的是（）A．是群 C．是群

B．是群

D．, ,都不是群

12．设*是集合A上的二元运算，下列说法正确的是（）A．在A中有关于运算*的左幺元一定有右幺元 B．在A中有关于运算*的左右幺元一定有幺元 C．在A中有关于运算*的左右幺元，它们不一定相同 D．在A中有关于运算*的幺元不一定有左右幺元 13．题13图的最大出度是（）A．0 C．2 14．下列图是欧拉图的是（）

B．1 D．3

15．一棵树的3个4度点，4个2度点，其它的都是1度，那么这棵树的边数是（）A．13 C．15

B．14 D．16

二、填空题（本大题共10小题，每小题2分，共20分）请在每小题的空格中填上正确答案。错填、不填均无分。

16．请写出表示德摩根律的两个命题公式等价定理___________，___________。

17．n个命题变元的___________称为小项，其中每个变元与它的否定不能同时出现，但两者必须___________。18．前提引入规则：在证明的任何步骤上都可以___________，简称___________规则。

19．自由变元代入规则是指对某___________出现的个体变元可用个体常元或用与原子公式中所有个体变元不同的个体变元去代入，且___________。

20．设A=,B={2,4}，则((A)=___________，A×B___________。

21．设A={1,2,3,4}, A上的二元关系R={<1,2>,<2,4>,<3,3>},S={<1,3>,<2,4>,<4,2>}，则R2S=___________，(R-1)2=___________。

22．设代数系统是环，则是___________，是___________。

23．在中，元素2的阶为___________，它生成的子群为___________，其中7为模7乘法。24．设是一个___________，如果A中任意两个元素都有___________，则称为格。25．若一条___________中，所有的___________均不相同，称为迹。

全国2010年7月自学考试离散数学试题

三、计算题（本大题共6小题，每小题5分，共30分）

26．给定论域D={1,2}，f(1)=2, f(2)=1, S(1)=F, S(2)=T, G(1,2)=T, G(2,1)=T,在该赋值下，求式子x(S(f(x))∧G(x, f(x)))的真值。

27．请通过等值演算法求┐(P∧Q)→(P∨Q)的主析取范式。

28．设A={1,2,3,4}，给定A上二元关系R={<1,1>,<1,2>,<2,4>,<4,2>}，求R的传递闭包。29．对题29图所示格，找出它的所有的4元子格。

30．用矩阵的方法求题30图中结点ui，u5之间长度为2的路径的数目。

31．求题31图的最小生成树。

四、证明题（本大题共3小题，第32小题8分，第33、34小题各6分，共20分）32．用推理方法证明(A∨B)→(C∧D),(D∨F)→E├A→E。

33．证明：设是一个群，则对于任意a,b∈G，必存在惟一的x∈G使得a·x=b。34．设图G有n个结点，n+1条边，证明：G中至少有一个结点度数≥3。

五、应用题（本大题共2小题，第35小题9分，第36小题6分，共15分）

35．符合化下列命题，并构造推理证明：三角函数都是周期函数，有些三角函数是连续函数，所以有些周期函数是连续函数。

36．两个等价关系的并集不一定是等价关系，试举例说明。

全国2010年7月自学考试离散数学试题

全国2010年7月自学考试离散数学试题

全国2010年7月自学考试离散数学试题

全国2010年7月自学考试离散数学试题

离散数学试题答案[范文] 篇4

一、单项选择题(每小题2分，共10分)1.命题公式(PQ)Q为()

(A)矛盾式(B)可满足式(C)重言式(D)合取范式

2.设C(x): x是国家级运动员，G(x): x是健壮的，则命题“没有一个国家级运动员不是健壮的”可符号化为()

(A)x(C(x)G(x))(B)x(C(x)G(x))

(C)x(C(x)G(x))(D)x(C(x)G(x))

3.设集合A={{1,2,3}, {4,5}, {6,7,8}}，则下式为真的是()

(A)1A(B){1,2, 3}A

(C){{4,5}}A(D)A

4.设A＝{1,2},B={a,b,c},C={c,d}, 则A×(BC)=()

(A){<1,c>,<2,c>}(B){,<2,c>}(C){,}(D){<1,c>,}

5.如第5题图所示各图，其中存在哈密顿回路的图是()

二、填空题(每小题3分，共15分)

6.设集合A={,{a}}，则A的幂集P(A7.设集合A={1,2,3,4 }, B={6,8,12}, A到B的关系R＝{x,yy2x,xA,yB},那么R1＝

8.图G如第8题图所示，那么图G的割点是－abfced第8题图

9.连通有向图D含有欧拉回路的充分必要条件是.10.设X＝{a,b,c}，R是X上的二元关系，其关系矩阵为

101，那么R的关系图为MR＝100100

三、化简解答题(每小题8分，共24分)11.简化表达式(((A(BC))A)(B(BA)))(CA).12.设代数系统(R*, )，其中R*是非0实数集，二元运算为：a,bR, ab=ab.试问是否满足交换律、结合律，并求单位元以及可逆元素的逆元.13.化简布尔表达式aab(cab).四．计算题(每小题8分，共32分)

14.求命题公式(PQ)(PQ)的真值表.15.试求谓词公式x(P(x)xQ(x,y)yR(x,y))A(x,y)中，x,x,y的辖域，试

问R(x,y)和A(x,y)中x,y是自由变元，还是约束变元？16.设R1是A1＝{1,2}到A2＝(a,b,c)的二元关系，R2是A2到A3＝{,}的二元关系，R1= {<1,a>,<1,b>,<2,c>}, R2={,}试用关系矩阵求R1R2的集合表达式.v

217图G如第17题图

求图G的最小生成树.v4v

3第17题图

五、证明题(第18题10分，第19题9分)18.证明(PQ)((QR)R)(PS))S19.设G为9个结点的无向图，每个结点的度数不是5就是6，试证明G中至少有5个度数为6的结点，或者至少有6个度数为5的结点.《计算机数学基础》离散数学试题

之五解答

一、单项选择题(每小题2分，共15分)1.B2.D3.C4.A5.C

二、填空题(每小题3分，共15分)6.{,{},{{a}},{,{a}}}

7.{<6,3>,<8,4> }8.a, f9.D中每个结点的入度＝出度.10.见第10题答案图.三、化简解答题(每小题8分，共24分)(((A(BC))A)(B(BA)))(CA)

c第10题答案图

(A(B(~BA)))(CA)（2分）

(A(AB))(CA)AC~A)

（4分）

（6分）（8分）

12.a,b,cR*, ab=ab=ba=ba，可交换；(2分)(ab)c=abc=abc=a(bc)=a(bc)=a(bc)，可结合.(4分)易见，单位元为1.(6分)

对aR*, aa1=aa1=1=a1a＝a1a，故a的逆元：a1

－

－

－

－

(8分)a

13.aab(cab)

＝aabcaab(2分)

＝aab(5分)＝(aa)(ab)ab(8分)

四、计算题(每小题8分，共32分)

表中最后一列的数中，每对1个数得2分.15.x的辖域：(P(x)xQ(x,y)yR(x,y))(2分)x的辖域：Q(x,y)(4分)y的辖域：R(x,y)(6分)R(x,y)中的x,y是约束变量，A(x,y)中的x,y是自由变量.(8分)

110

16.MR1,(2分)

001

01

(4分)MR20100

01

11001(6分)MR1R201

0010000



R1R2{1,}(8分)

v217图G的最小生成树，如第17题答案图.首先选对边(v 1, v 2)得2分，再每选对一条边得分.v4v

3第17题答案图

五、证明题(第18题10分，第19题9分，共19分)18.①QRP（2分）②RP(4分)

③Q①，②析取三段论

④PQP(7分)

⑤P③，④拒取式⑥PSP

⑦S⑤，⑥析取三段论(10分)

19.由第5章定理1(握手定理)的推论，G中度数为5的结点个数只能是0,2,4,6,8五种情况；(3分)此时，相应的结点度数为6的结点个数分别为9，7，5，3，1个，(6分)

离散数学课后习题答案第四章 篇5

4．判断下列集合对所给的二元运算是否封闭：（1）整数集合Z和普通的减法运算。

封闭,不满足交换律和结合律，无零元和单位元（2）非零整数集合普通的除法运算。不封闭

（R）和矩阵加法及乘法运算，其中n2。（3）全体nn实矩阵集合封闭 均满足交换律，结合律，乘法对加法满足分配律； 加法单位元是零矩阵，无零元；

乘法单位元是单位矩阵，零元是零矩阵；

（4）全体nn实可逆矩阵集合关于矩阵加法及乘法运算，其中n2。不封闭（5）正实数集合和运算，其中运算定义为：

不封闭

因为 1111111R（6）n关于普通的加法和乘法运算。

封闭，均满足交换律，结合律，乘法对加法满足分配律 加法单位元是0，无零元；

乘法无单位元（n1），零元是0；n1单位元是1（7）A = {a1,a2,,an} n运算定义如下：

封闭 不满足交换律，满足结合律，（8）S = 关于普通的加法和乘法运算。

封闭

均满足交换律，结合律，乘法对加法满足分配律（9）S = {0,1},S是关于普通的加法和乘法运算。

加法不封闭，乘法封闭；乘法满足交换律，结合律（10）S = ,S关于普通的加法和乘法运算。

加法不封闭，乘法封闭，乘法满足交换律，结合律

5．对于上题中封闭的二元运算判断是否适合交换律，结合律，分配律。

见上题

7．设 * 为Z上的二元运算x,yZ，X * Y = min(x，y),即x和y之中较小的数.(1)求4 * 6，7 * 3。

4,(2)* 在Z上是否适合交换律，结合律，和幂等律？ 满足交换律，结合律，和幂等律

(3)求*运算的单位元，零元及Z中所有可逆元素的逆元。单位元无，零元1, 所有元素无逆元

8．SQQ Q为有理数集，*为S上的二元运算，,S有

< a，b >* = （1）*运算在S上是否可交换，可结合？是否为幂等的？ 不可交换：*= < a，b >* 可结合：(*)*=*= *(*)=*=(*)*=*(*)不是幂等的

（2）*运算是否有单位元，零元？ 如果有请指出，并求S中所有可逆元素的逆元。

设是单位元，S，*= *= 则==，解的=<1,0>，即为单位。

设是零元，S，*= *= 则==，无解。即无零元。

S，设是它的逆元*= *=<1,0> ==<1,0> a=1/x,b=-y/x 所以当x0时，x,y11y, xx

10．令S={a，b}，S上有四个运算：*，分别有表10.8确定。

(a)

(b)

(c)

(d)

(1)这4个运算中哪些运算满足交换律，结合律，幂等律？(a)交换律，结合律，幂等律都满足，零元为a,没有单位元；(b)满足交换律和结合律，不满足幂等律，单位元为a,没有零元

a1a,b1b(c)满足交换律,不满足幂等律,不满足结合律

a(bb)aab, a(bb)(ab)b

没有单位元, 没有零元

(d)不满足交换律，满足结合律和幂等律

没有单位元, 没有零元

(2)求每个运算的单位元，零元以及每一个可逆元素的逆元。见上

(ab)baba

16．设V=〈 N，+，〉，其中+，分别代表普通加法与乘法，对下面给定的每个集合确定它是否构成V的子代数，为什么？

（1）S1=（2）S2= 是

不是 加法不封闭

（3）S3 = {-1，0，1} 不是，加法不封闭

第十一章部分课后习题参考答案

8.设S={0，1，2，3}，为模4乘法，即

y=(xy)mod 4 “x,y∈S, x问〈S，〉是否构成群？为什么？

y=(xy)mod 4S,是S上的代数运算。解：(1)x,y∈S, x(2)x,y,z∈S,设xy=4k+r 0r3

(xy)z =((xy)mod 4)

z=r

z=(rz)mod 4 =(4kz+rz)mod 4=((4k+r)z)mod 4 =(xyz)mod 4 同理x(yz)=(xyz)mod 4 y)z = x1)=(1(y

z)，结合律成立。所以，(x(3)x∈S,(xx)=x,，所以1是单位元。

(4)111,313, 0和2没有逆元 所以，〈S，9.设Z为整数集合，在Z上定义二元运算。如下： ” x,y∈Z,xoy= x+y-2 问Z关于o运算能否构成群？为什么？ 〉不构成群 解：(1)x,y∈Z, xoy= x+y-2Z,o是Z上的代数运算。(2)x,y,z∈Z,(xoy)oz =(x+y-2)oz=(x+y-2)+z-2=x+y+z-4 同理(xoy)oz= xo(yoz)，结合律成立。

(3)设e是单位元，x∈Z, xoe= eox=x,即x+e-2= e+x-2=x, e=2(4)x∈Z , 设x的逆元是y, xoy= yox=e, 即x+y-2=y+x-2=2, 所以，x1y4x 所以〈Z，o〉构成群

101011.设G=01,01,101001,01，证明G关于矩阵乘法构成一个群． 解：(1)x,y∈G, 易知xy∈G,乘法是Z上的代数运算。

(2)矩阵乘法满足结合律

10(3)设01是单位元，(4)每个矩阵的逆元都是自己。所以G关于矩阵乘法构成一个群．

14.设G为群，且存在a∈G,使得 G={ak∣k∈Z} 证明：G是交换群。

证明:x,y∈G，设xak,yal，则

xyakalaklalkalakyx 所以，G是交换群

17.设G为群，证明e为G中唯一的幂等元。

22证明:设e0G也是幂等元，则e0e0，即e0e0e，由消去律知e0e

18.设G为群，a,b,c∈G,证明

∣abc∣=∣bca∣=∣cab∣ 证明：先证设(abc)ke(bca)ke 设(abc)ke,则(abc)(abc)(abc)(abc)e，即

a(bc)(abc)(abc)a(bc)aa1e 左边同乘a1，右边同乘a得

(bca)(bca)(bca)(bca)(bac)ka1eae

反过来，设(bac)ke,则(abc)ke.由元素阶的定义知，∣abc∣=∣bca∣，同理∣bca∣=∣cab∣

19.证明：偶数阶群G必含2阶元。

证明：设群G不含2阶元，aG，当ae时，a是一阶元，当ae时，a至少是3阶元,因为群G时有限阶的，所以a是有限阶的，设a是k阶的,则a1也是k阶的，所以高于3阶的元成对出现的，G不含2阶元，G含唯一的1阶元e,这与群G是偶数阶的矛盾。所以，偶数阶群G必含2阶元

20.设G为非Abel群，证明G中存在非单位元a和b,a≠b,且ab=ba.证明：先证明G含至少含3阶元。

若G只含1阶元,则G={e},G为Abel群矛盾；

若G除了1阶元e外,其余元a均为2阶元，则a2e，a1a

a,bG,a1a,b1b,(ab)1ab,所以aba1b1(ba)1ba，与G为Abel群矛盾；

所以，G含至少含一个3阶元，设为a，则aa2，且a2aaa2。令ba2的证。

21.设G是Mn(R)上的加法群，n≥2，判断下述子集是否构成子群。（1）全体对称矩阵 是子群（2）全体对角矩阵 是子群

（3）全体行列式大于等于0的矩阵.不是子群（4）全体上（下）三角矩阵。是子群

22.设G为群，a是G中给定元素，a的正规化子N（a）表示G中与a可交换的元素构成的集合，即 N（a）={x∣x∈G∧xa=ax} 证明N（a）构成G的子群。证明：ea=ae,eN(a)

x,yN(a),则axxa,ayya

a(xy)(ax)y(xa)yx(ay)x(ya)(xy)a,所以xyN(a)

由axxa，得x1axx1x1xax1,x1aeeax1，即x1aax1，所以x1N(a)所以N（a）构成G的子群

31.设1是群G1到G2的同态，2是G2到G3的同态，证明12是G1到G3的同态。证明：有已知1是G1到G2的函数，2是G2到G3的函数，则1·2是G1到G3的函数。

a,bG1,(12)(ab)2(1(ab))2(1(a)1(b))

(2(1(a)))(2(1(b)))(12)(a)(12)(b)所以:1·2是G1到G3的同态。

33.证明循环群一定是阿贝尔群，说明阿贝尔群是否一定为循环群，并证明你的结论。

证明：设G是循环群,令G=,x,yG,令xak,yal,那么

xyakalaklalkalakyx,G是阿贝尔群

克莱因四元群,G{e,a,b,c}

eeabceabcaaecb bbceaccbae是交换群,但不是循环群,因为e是一阶元，a,b,c是二阶元。36.设,是5元置换，且

123451234521453，34512

(1)计算,,1,1,1；(2)将,1,1表成不交的轮换之积。

(3)将（2）中的置换表示成对换之积，并说明哪些为奇置换，哪些为偶置换。

1234512345112345解：(1) 4532143125 45123

11234512345121534 54132 )1(14253(2)(1425)(25))1(143(3)(14)(12)(15)奇置换，1(14)(12)(15)(13)偶置换

离散数学入门教学初探 篇6

离散数学作为计算机科学中基础理论的核心课程, 确实有一定的难度。计算机科学在其研究过程中需要借助于离散数学这个工具, 离散数学对于计算机的发展和计算机的研究具有重要的作用。而离散数学是一门教与学都较困难的现代数学分支, 它是研究离散对象之间关系的科学。该课程的特点是内容多、概念多、抽象化。学生对知识与知识之间的联系, 如何将知识正确应用于解决实际问题, 经常把握不好, 仍然需要教师给予指导。我们应该使学生在掌握知识的同时提高分析问题和解决问题的能力, 实现学习成果的转化。

思维方式

离散数学成为一门数学学科的时间并不长, 但它已经成了计算机科学系统理论中不可缺少的核心课程和先行课程。它不仅在知识上为计算机专业基础课 (编译原理、数字电路等课程) 做准备, 同时在思维方式———抽象性思维方面为学生打开了一道新的门。教师除了要教给学生数学工具外, 更重要的是培养学生的思维能力和创造能力。该课程就是要培养学生的分析问题、解决问题的能力以及抽象思维能力。这就要求教师在讲课时条理非常清晰, 并且告诉学生你的思维方式、分析问题的过程。

课后习题

每当讲解完概念、定理和方法后, 应及时找一些课外习题讲解, 并让学生练习, 达到巩固知识的效果。因为一个好的示例不仅可以打开思想, 而且对理解一种数学方法, 理解理论的含意, 能起到促进的效果。需要注意的是必须找课本以外的练习题。因为大学生具有自学能力, 若仅仅是讲解课本上的例题, 学生认为没有新意, 他们看书就完全可以了, 这样不能吸引学生的注意力。用课外的习题就不一样, 因为书本上没有, 学生就会仔细认真地去听, 这样才有好的教学效果。要精选习题, 多选与计算机科学直接相关的习题 (例如编码、程序设计、数据结构等) , 多选巩固概念、理解概念的习题, 多选应用型的习题、证明题, 尽可能少讲, 以加强学生逻辑分析的能力。

强调应用

数学知识与数学素养对于工科学生的应用能力和进一步的开拓创新能力有很大的影响, 有些时候甚至有决定性的影响。这一点, 人们在理论上较容易接受, 在实践上却未必认同。对于应用型的工科学生, 他们一般更注意一种技能的获得。而对数学, 对在无形中增长他们的判断能力和抽象思维能力, 增长他们透过感性表象洞察隐蔽本质的能力, 增长他们的条理性和逻辑性的数学, 却难于产生热情。而愈无兴趣就愈觉枯燥, 愈觉困难。这种负反馈在不少学生中存在。对于更为抽象的离散数学, 这个问题会更加突出。

作者在教学过程中遇到过这样的情景, 学生说学习离散数学这样的理论课程没有用处, 所以没有兴趣, 不想好好学。这是现在高职学生对于理论课程的一种普遍看法。其实我们都知道理论很重要, 特别是数学知识很重要, 但是学生没有这样的意识, 为什么?这与许多教师在讲课时没有及时将所讲内容与现实应用联系起来, 以至于让学生产生错误的认识是分不开的。所以要求教师在讲课时一定要清楚地让学生意识到自己所学的知识是非常有用的, 教师应该将知识和实际联系起来 (我校正在实施的“六位一体”课程能力目标教学改革) 。针对计算机专业的学生这一特定的对象, 应着重阐明概念与定理所涵盖的现实对象或现实模型, 应尽量多介绍离散数学在计算机领域的应用。使学生感受到数学在其他学科中的巨大应用, 并学会一些应用数学的方法。例如“一笔画”的问题。这是每一个学生都比较感兴趣的话题, 我们从小就接触过这样的问题, 有些图形可以一笔画成, 有些则不可以, 为什么?从这个角度入手容易引起学生的好奇心, 接着再讲解欧拉图的内容就能收到很好的教学效果。

改变学生对离散数学的消极心态, 调动学生的积极性, 使他们感到离散数学的有用和有趣, 自觉主动地去学习, 这是学生不仅获得知识而且增长能力的前提。是完成教学要求的基本保证, 也是教学改革的重要内容。

第一印象会长久鲜明地留在学生的头脑中, 开始的教学不宜大量讲述抽象的概念和逻辑推演, 而要对离散数学的历史、现状、应用作较生动的讲解。在各章节的开始, 最好有主题介绍。对离散数学中的一些富于历史趣味的故事或富于启发性的问题应加以介绍。比如哥尼斯堡七桥问题, 邮递员问题, 一笔画问题, 周游世界游戏问题等。有关的介绍不必全面和深入, 而是应侧重讲解它们的意境, 侧重讲解它们的趣味性和启发性, 这些介绍宜分散到相关章节去做。接下去, 应向学生提出一些富于思考性的问题, 这些问题或与他们的专业有关, 或与他们已有的知识有关, 或出于他们的意外, 或饶有趣味。这些问题使他们看来似能解决而又不能解决, 这样就能启动学生思维的积极性。

改进教学法

不同内容的讲授, 方法可以不同。有些概念可以从多个角度进行讲解。例如子图和生成子图的概念。子图和生成子图的定义如下:

1.图G=与G′=间如果有V′≦V及E′≦E, 则称G′是G的子图。

2.如果G′是G的子图, 并且V=V′ (即子图G′包含G的所有节点) , 则称该子图G′为G的生成子图。

分析上述定义后, 也可理解为:

在图G中删去一些边或顶点后所得的图称为图G的子图。

在图G中删去一些边后所得的图称为图G的生成子图。

传统的教学思想过分重视演绎法, 演绎法虽然有利于学习已有的知识, 但它注重繁琐的理论证明和局部的解题技巧, 学生只能得到一些基本理论, 而不能指导学生去发现, 去创新。因此, 在教学改革中, 要让学生通过对各种现象的观察、分析, 在演绎的基础上进行示例、类比、归纳, 去发现问题、研究问题、解决问题。

近二十年来, 由于计算机专业的兴起, “离散数学”这门课也随之开设。应当承认, 该课程较为抽象, 学与教两方面均存在一定的难度, 正因为这个难度, 使其成为一门培养素质与创造能力的好课程, 通过有效的知识传授可以达到培养素质的目的。

掌握知识框架

要想让学生从总体上把该课的结构、各部分内容之间的关系搞清楚, 就要在每一章结束后, 对本章的内容进行总结整理, 让学生的脑海中有一个知识框架, 帮助学生有一个清楚的知识体系。

多媒体课件的使用使用CAI, 习题库的建立对计算机专业教学而言, 更应早日提上日程。尽管离散数学CAI的编制有较大难度, 但可由浅入深, 由简到繁, 逐步编制和使用。根据教材知识体系, 把内容划分成集合论、数理逻辑、图论三个单元, 编制各单元的辅导教学知识结构体系的文字教案或电子教案。

使用多样形式的教学方法讲清知识体系的内涵和外延, 设计符合学生学习特点的多媒体教材, 尽量将抽象的知识形象化, 达到帮助学生理解和掌握知识的目的。

讲清楚内容对于有难度的内容, 书本上书写不充分的内容或者学生看不懂的内容, 在讲课过程中, 一定要仔细地分析讲解, 使复杂的问题简单化、抽象的问题形象化, 从而达到较好的教学效果。

讲课速度教师一定要做好课前的教学设计, 精心安排每次课的教学内容, 争取整个教学过程都达到最佳效果。主讲课虽然以教师讲为主, 但也要避免传统的“填鸭式”的满堂灌教学方式, 要注意调动学生的学习积极性, 充分发挥学生的主体作用。对主讲课的教学, 教师要认真把握好速度、进度, 切实注重教学效果, 质量是根本, 学生在理解的基础上掌握是目的。讲课时速度适中, 难的内容多讲、慢讲, 不能只求速度而不管学生的接受能力;简单的内容快讲、少讲, 也可以让学生自学。特别应强调说明的是, 自学能力强是素质高的一个表现, 因为毕业后学生为了适应工作的需要, 要吸收许多新的知识, 这个时候主要靠自学。在教学中, 有意识地指导学生自学某些章节是有益的。精心组织教学。需要教师更加充分备课, 更加精心组织每次教学。让学生自学的某些章节, 不是放任不管, 而是需要精心策划。劳力且劳心, 付出的应该更多。培养学生的素质, 需要高素质的教师, 需要教师努力提高自身的素质。要使学生具有创造性, 教师在教学中就应有创造性。这些都需要对所教的课程反复钻研体会。

参考文献

[1]涂建斌, 周小强.离散数学课程教学改革初探[J].数学理论与应用, 2006, (4) .

[2]姜楠, 信琦, 等.离散数学辅助教学网站设计[J].大连民族学院学报, 2004, 5 (4) .

离散数学试卷及答案 篇7

11*2设n>1是奇数，证明n整除(1+++)(n-1)!2n-1证明：

11++)(n-1)!=[(11)(11)(11)](n1)!2n-11n12n2

nnn)(n1)!n1n1n12(n2)

111](n1)!n1n1n1n2(1+=(=n[

4求方程963x+657y=(963,657)的所有整数解。

解：

（1）

由辗转相除法可得到方程的一个解：x0 =-15，y0=22

设(x,y)也是一个解，则963x+657y=(963,657)

于是963(x-x0)+657(y-y0)=0，从而107(x-x0)=-73(y-y0)，所以10773(y-y0)。又因为(107,73)=1,所以107(y-y0)

设(y-y0)=107k，则(x-x0)=-73k，从而x=x0-73k，y=y0+107k

容易验证，对于任意整数k，(x0+73k,y0+107k)满足原方程。

所以，原方程有无穷多个解：x=-15-73k

y=22+107k

其中k=…,-2,-1,0,1,2,…

（2）

963x+657y=(963,657) 963x-9=-657y

x,yZ，963x-9=-657y  xZ，963x≡9(mod 657)

5．设a、b、c、d是正整数，满足ab=cd。证明：a4+b4+c4+d4不是素数。证明：设11)(n-1)!∴n整除(1+++2n-1adp，其中p和q是互素的正整数 cbq

aq=cp  paq  pa（∵p和q互素）

于是，uN，使a=pu  c=qu

同理vN，使d=pv  b=qv

从而，a4+b4+c4+d4=(p4+q4)(u4+v4) a4+b4+c4+d4不是素数

7团体操表演过程中，要求队伍在变换成10行、15行、18行、24行时均能成长方形，问需要多少人？

解：

由题意，所求之数为10,15,18,24的倍数，[10,15,18,24]＝360，故需360k(k>0)人。

10证明：如果p,p+2,p+4都是素数，则p=3。

证明：用反证法，假设p≠3。

p,p+1,p+2是3个连续的整数，其中有且仅有一个为3的倍数。

p,p+2是素数，且p≠3  p+1是3的倍数

不妨设p+1=3k(kN)。

于是，p+4=3(k+1)必为合数，与条件矛盾。

所以，p=3

11计算2400 mod 319。

解：

φ(n)=319*(1-1／11)(1-1／29)=280

2400 mod 319=2280·2120mod 319=2120mod 319=(210)12mod 319)=(3*319+67)12 mod 319=(672)6 mod 319=((23)2)3 mod 319=(210)3 mod 319=111

14(2)解同余方程：56x≡88(mod 96)。

解：

（1）(a,m)=(56,96)=8，8|96，方程有解

（2）a=56/8=7，b=88/8=11，m=96/8=12

（3）由辗转相除法可求得p和q满足pa+qm=1，p=-5，q=3

特解x0=pb=-511

（4）解为x-511+t12(mod 96)，t=0,1,,7 即x≡5,17,29,41,53,65,77,89(mod 96)

16(1)解同余方程组：x3(mod5)x7(mod9)

解：

m1=5，m2=9，M=45，M1=9，M2=5

9x≡1(mod 5),5x≡1(mod 9),的特解：c1=-1,c2=2原方程组的解：x≡-1×3×9+2×7×5≡43(mod 45)

5x7(mod 12)16(2)解同余方程组7x1(mod 10)

解：

5x≡7(mod 12) 12(5x-7) 4(5x-7)且3(5x-7) 5x≡7(mod 4)且5x≡7(mod 3)∴同余方程5x≡7(mod 12)与同余方程组5x7(mod 4)同解

5x7(mod 3)

x3(mod 4)后者可规约为 x2(mod 3)

类似地，同余方程7x≡1(mod 10)可规约为同余方程组

x1(mod 2)x3(mod 5)

x2(mod 3)x2(mod 3)x3(mod 4)x3(mod 4)∴原同余方程组可规约为，它与同余方程组同解 x3(mod 5)x1(mod 2)

x3(mod 5)

x2(mod 3)x3(mod 4)求解同余方程组： x3(mod 5)

m1=3，m2=4，m3=5，M=60，M1=20，M2=15，M3=12

20x≡1(mod 3),15x≡1(mod 4),12x≡1(mod 5)的特解：c1=2,c2=3,c3=3

原同余方程组的解：x≡2×2×20+3×3×15+3×3×12≡80+135+108≡23(mod 60)

*17解同余方程组：

x≡3(mod 8)，x≡11(mod 20)，x≡1(mod 15)。

解：

x3(mod 8)x3(mod8)x11(mod 4)x1(mod 3)原同余方程组与同余方程组x11(mod 5)同解，后者可规约为x1(mod 5)x1(mod 5)x1(mod 3)

x3(mod8)x1(mod 3)： 求解同余方程组x1(mod 5)

m1=8，m2=3，m3=5，M=120，M1=15，M2=40，M3=24

15x≡1(mod 8),40x≡1(mod 3),24x≡1(mod 5)的特解：

c1=7,c2=1,c3=4

原同余方程组的解：x≡7×3×15+1×1×40+4×1×24≡351+40+96≡91(mod 120)

19．*设m1和m2是正整数，b1和b2是整数。证明一次同余方程组

x≡b1(mod m1)，x≡b2(mod m2)

有解的充分必要条件是(m1,m2)|(b1-b2)；并且，当此条件成立时，该同余方程组的解可表示为x≡c(mod [m1,m2])，其中0

证明：用反证法，假设p≠3。

（1）

有解  可设x为一个解  m1x-b1，m2x-b2  k1,k2Z，使x-b1=k1m1, x-b2=k2m2  b2-b1=k1m1-k2m2

(m1,m2)|m1,(m1,m2)|m 2 (m1,m2)| k1m1-k2m2=(b1-b2)

（2）

(m1,m2)|(b1-b2) k,s,tN，使(b1-b2)=k(m1,m2)=k(sm1+tm2)

容易验证，x=b1-ksm1是同余方程组的解  有解

（3）容易验证，解x，kZ，x+k[m1,m2]也是解  结论

补充：编写一程序实现Miller-Rabin素性测试算法。已知RSA密码体制的公钥(e,n)=(5,35)，（1）请按本小节例题所示的方式将明文信息“rsa”加密；

（2）请破解出私钥。

解：

（1）

明文信息由26个小写字母构成，数字化编码为字母的序号：a01，r18，s19，明文“rsa”181901

取段长为2，明文” 181901”分为3段：m1=18，m2=19，m3=01

用公钥(5,35)加密得到3个密文：

c1=m1e mod n =185 mod 35=23

c2=m2e mod n =195 mod 35=24

c3=m3e mod n =015 mod 35=01

组合得到密文串：232401

（2）

由公钥：KU=(e,n)=(5,35)得到n=35的两个素因数p=5,q=7，(n)=(p-1)(q-1)=24，e=5(5,24)=1，解同余方程5d≡1(mod 24)，得到唯一解d=5

私钥： KR=(d,n)=(5,35)

请编写一个高效的指数取模运算算法

/*

exp_mod.c

handle the Modexp calculation((a^p)%m)using Montgomery algorithm(O(logn))*/

#include

int expmod(int a, int p, int m){

int r;

int k;

if(p==0)return 1;

r=a%m;

k=1;

while(p>1){

if((p&1)!=0)

k=(k*r)%m;

r=(r*r)%m;

p>>=1;

}

return(r*k)%m;

}

void main()

{

int a,b,c,r;

scanf(“%d%d%d”,&a,&b,&c);

r=expmod(a,b,c);

printf(“(%d^%d)%%%d=%dn”,a,b,c,r);

//getch();

}

编写一程序实现Miller-Rabin素性测试算法

#include

#include

int powmod(int i,int d,int n)//模n的大数幂乘快速算法

{

int c = 1;//c为余数，保存每次模后的数

while(d == 0)

{

if(d % 2 == 0){d = d / 2;i =(i * i)% n;}//d是偶数，就先求i平方的模

else {d--;c =(c * i)% n;}//d是奇数，就与上一次的模相乘后在求模

}

return c;//d为0，只能通过d--，所以返回的必是c

}

void main()

{

int i = 2,d,n;

d = n1){printf(“是素数”);break;} //如果模为n-1也结束，因为只有当模为1时才能不断地把d折半

}

else {printf(“ 不是素数”);printf(“%d”,powmod(i,d,n));break;}//如果在d折半的过程中出现的powmod不是1或n-1的话就结束

}

if(d == 1)printf(“是素数”);//如果d一直都能折半到1，也为素数

//getch();