泉州师范《离散数学》期中复习

泉州师范《离散数学》期中复习（共5篇）

泉州师范《离散数学》期中复习 篇1

内容：第一章~第七章 题型：

一、选择题（20%，每题2分）二．填空题（20%，每题2分）

三、计算题（20%，每题5分）

四、证明题（20%，每题5分）

五、判断题（20%，每题2分）

第1章 数学语言与证明方法

1.1 常用的数学符号

1.计算常用的数学符号式子 1.2 集合及其表示法

1.用列举法和描述法表示集合

2.判断元素与集合的关系(属于和不属于)3.判断集合之间的包含与相等关系，空集(E)，全集()4.计算集合的幂集

5.求集合的运算：并、交、相对补、对称差、绝对补

6.用文氏图表示集合的运算 7.证明集合包含或相等

方法一： 根据定义, 通过逻辑等值演算证明

方法二： 利用已知集合等式或包含式, 通过集合演算证明

1.3 证明方法概述

1、用如下各式方法对命题进行证明。 直接证明法：AB为真

 间接证明法：“AB为真”  “ ¬B ¬A为真”  归谬法(反证法)： A¬B0为真

 穷举法： A1B, A2B,…, AkB 均为真

 构造证明法：在A为真的条件下, 构造出具有这种性质的客体B  空证明法：“A恒为假”  “AB为真” 平凡证明法：“B恒为真”  “AB为真”  数学归纳法： 第2章 命题逻辑

2.1 命题逻辑基本概念

1、判断句子是否为命题、将命题符号化、求命题的真值（0或1）。

命题的定义和联结词(¬, , , , )

2、判断命题公式的类型

赋值或解释.成真赋值,成假赋值；重言式(永真式)、矛盾式(永假式)、可满足式:。2.2 命题逻辑等值演算

1、用真值表判断两个命题公式是否等值

2、用等值演算证明两个命题公式是否等值

3、证明联结词集合是否为联结词完备集 2.3 范式

1、求命题公式的析取范式与合取范式

2、求命题公式的主析取范式与主合取范式（两种主范式的转换）

3、应用主析取范式分析和解决实际问题 2.4 命题逻辑推理理论

1、用直接法、附加前提、归谬法、归结证明法等推理规则证明推理有效 第3章 一阶逻辑

3.1 一阶逻辑基本概念

1、用谓词公式符号命题（正确使用量词）

2、求谓词公式的真值、判断谓词公式的类型 3.2 一阶逻辑等值演算

1、证明谓词公式的等值式

2、求谓词公式的前束范式 第4章 关系

4.1 关系的定义及其表示

1、计算有序对、笛卡儿积

2、计算给定关系的集合

3、用关系图和关系矩阵表示关系 4.2 关系的运算

1、计算关系的定义域、关系的值域

2、计算关系的逆关系、复合关系和幂关系

3、证明关系运算满足的式子 4.3 关系的性质

1、判断关系是否为自反、反自反、对称、反对称、传递的2、判断关系运算与性质的关系

3、计算关系自反闭包、对称闭包和传递闭包 4.4 等价关系与偏序关系

1、判断关系是否为等价关系

2、计算等价关系的等价类和商集

3、计算集合的划分

4、判断关系是否为偏序关系

5、画出偏序集的哈期图

6、求偏序集的最大元、最小元、极小元、极大元、上界、下界、上确界、下确界

7、求偏序集的拓扑排序 第5章 函数

1.判断关系是否为函数 2.求函数的像和完全原像

3.判断函数是否为满射、单射、双射 4.构建集合之间的双射函数 5.求复合函数

6.判断函数的满射、单射、双射的性质与函数复合运算之间的关系 7.判断函数的反函数是否存在，若存在求反函数 第6章 图

1.指出无向图的阶数、边数、各顶点的度数、最大度、最小度

2.指出有向图的阶数、边数、各顶点的出度和入度、最大出度、最大入度、最小出度最小入出度

3.根据握手定理顶点数、边数等

4.指出图的平行边、环、弧立点、悬挂顶点和悬挂边 5.判断给定的度数列能否构成无向图

6.判断图是否为简单图、完全图、正则图、圈图、轮图、方体图 7.求给定图的补图、生成子图、导出子图 8.判断两个图是否同构 6.2 图的连通性

1.求图中给定顶点通路、回路的距离

2.计算无向图的连通度、点割集、割点、边割集、割边 3.判断有向图的类型：强连通图、单向连通图、弱连通图 6.3 图的矩阵表示

1.计算无向图的关联矩阵 2.计算有向无环图的关联矩阵 3.计算有向图的邻接矩阵 4.计算有向图的可达矩阵

5.计算图的给定长度的通路数、回路数 6.4 几种特殊的图

1、判断无向图是否为二部图、欧拉图、哈密顿图 第7章 树及其应用 7.1 无向树

1.判断一个无向图是否为树

2.计算无向树的树叶、树枝、顶点数、顶点度数之间的关系 3.给定无向树的度数列，画出非同构的无向树 4.求生成树对应的基本回路系统和基本割集系统 5.求最小生成树 7.2 根树及其应用

1.判断一个有向图是否为根树

2.求根树的树根、树叶、内点、树高 3.求最优树

4.判断一个符号串集合是否为前缀码 5.求最佳前缀码

离散数学复习题1 篇2

1、给出的真值表

2、证明为永真式 谓词量词和推理

1、使用量词和谓词表达不存在这一事实

2、证明前提“在这个班上的某个学生没有读过书”和班上的每个学生都通过了第一门考试蕴含结论“通过考试的某个人没有读过书” 集合、函数、数列与求和

1、全集为，求集合A=的位串？它的补集的位串是什么？写出集合A=的所有子集，写出集合

2、从集合到集合能定义多少个函数？下面给出的函数其定义为：该函数是双射吗？是满射吗？该函数是否存在逆函数？如果存在请给出其逆函数。计数

1、计算机系统的美国用户有一个6～8个字符构成的密码，其中每个字符是一个大写字母或数字，且每个密码必须至少包含一个数字，问总共有多少个合适的密码？

2、在30天的一个月里，某棒球队一天至少打一场比赛，但最多打45场。证明一定有连续的若干天内这个球队恰好打了14场比赛

3、证明n个元素的集合中允许重复的r组合数等于

4、按照字典顺序生成整数1，2，3的所有排列（不允许重复），在362541后面按照字典顺序的下一个最大排列是什么？找出在1000100111后面的下一个最大的二进制串。关系

1、求下面给出关系R的自反闭包、对称闭包和传递闭包的0-1关系矩阵，其中

2、S是所有比特串的集合，关系定义为当s=t或者s和t的长度至少是3，且前3个比特相同时具有关系，例如0101，0011100101，但01010，0101101110。证明是S上的等价关系，由产生的S的等价类是那些集合？

3、偏序集（{2,4,5,10,12,20,25},|）的那些元素是极大的，那些元素是极小的？ 图与树

1、在下图所示的图中，从a 到d的长度为4的通路有几条？该图是否是Euler图，是否是Hamilton图，该图的度序列是什么？该图是否可平面，如果是请给出平面画图，该图的点色数和边色数等于多少？给出该图的一个生成树，2、求下面赋权图从a到z的最短距离是多少？最短路径是什么？（画图给出标号过程）

3、用哈夫曼编码方法来编码下列符号，这些符号具有下列频率：A:0.08，B:0.10，C:0.12，D:0.15，E:0.20，F:0.35,该编码方法编码一个字符的平均位数是多少？

泉州师范《离散数学》期中复习 篇3

《 离散数学I 》课程试卷（A卷）

一．单选题(本题总分20分，每小题2分)

1．以下语句是命题的是()。

A．你喜欢唱歌吗？

2．A={a,b}，B={c,d}，A和B的笛卡尔积A×B是()。

A． {, }B．{}

C．{, , , }

3．设A={a,{a}}，下列命题错误的是()。

A．{a}P(A)B．{a}P(A)

C．{{a}}P(A)D．{{a}}P(A)

4．设A={1, 2, 3, 4}，下列()不是A的划分。

A．{{1}, {2}, {3}, {4}}

5．下列式子()不正确。

A．{}

6．假设论域是整数集合，下列自然语言的符号化表示中，()的值是假的。

A．xyG(x,y)，其中G(x,y)表示xy=x

B．yxH(x,y)，其中H(x,y)表示xy=x

C．yxF(x,y)，其中F(x,y)表示x+y=10

D．xyM(x,y)，其中M(x,y)表示x+y=10

7．以下联结词的集合()不是完备集。

B．{}{{}}C．{}D．{}{{}}B．{{1, 2}, {3}, {4}}D．{, {1, 2, 3}, {4}} C．{{1, 2}, {3, 4}}D．{, }B．x+y=20 C．给我一杯水吧！D．若7+818，则三角形有4条边。

A．{, , , , }B．{, , }

8．下面哪个谓词公式是前束范式()。

A．x(A(x)B(x))

9．以下式子错误的是()。C．{, }D．{, }B．xA(x) xB(x)D．xx(A(x) B(x))C．xx(A(x) B(x))

A．xA(x)xA(x)B．x(A(x)B(x)) xA(x)x B(x)

C．x(A(x)B(x)) xA(x)x B(x)D．x(A(x)B(x)) xA(x)x B(x)

10．以下命题公式是重言式的是()。

A．q(pq)

二．填空题(本题总分30分，每空2分)

1．实数集上的函数f(x)=2x2+1，g(x)=-3x+10，g-1(x)=()，fºg(x)=()。

2．谓词公式x(P(x) yR(y)) Q(x)中量词x的辖域是()。

3．若A={a,b}，则A×P(A)=()。

4．设p：我生病，q：我去学校，则句子“只有在生病时，我才不去学校”符号化为公式

()。

5．集合A={a,b,c,d}，A上的一个划分π={{a, b},{c, d}}，与π对应的A之上的等价关系是()。

6．设S={1,2,3,4}，A上的关系R＝{<1,2>，<2,1>，<2,3>，<3,4>}，则RR=()。

7．集合A上的等价关系的三个性质是()。

8．公式x((A(x)B(y，x))z C(y，z))D(x)中，自由变元是()，约束变元是()。

9．A={1,2,3,4}，B={3,4,5}，全集E={0,1,2,3,4,5,6,7}，A(AB)=()，(B-A)=()。

10． A={a,b,c,d}，A之上的关系R={, , , }，t(R)=（）。

11．A={a,b,c,d}, 以下哈斯图所对应的偏序关系R=()。

2B．((pq)qD．((pq)q)p C．((pq)q)p

c

三．计算/简答题(本题总分20分，每小题10分)

1．(10分)用等值演算法求公式(pq)r的主合取范式和主析取范式。

2．(10分)求公式的前束范式：(x1F(x1, x2)x2G(x2))x2H(x1, x2)

四．证明题(本题总分30分，每小题10分)

1．(10分)在自然推理系统N中构造下面推理的证明(个体域为人的集合)。

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

2．(10分)若R和S都是非空集A上的等价关系，则RS是A上的等价关系。

3．(10分)对任意集合A,B，证明：若AA = BB，则A=B。

泉州师范《离散数学》期中复习 篇4

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();

期中考试数学复习计划 篇5

复习范围：第22章二次根式、第23章旋转、第24章圆;复习时间：

复习阶段采取的措施：

1. 精心备课上课，针对班级学生出现的错题及所涉及到的重点问题认真挑选试题。

2. 对于复习阶段作业的布置，少而精，有针对性，并且很抓订正及改错。

3. 抓好课堂学生的管理，切实作到每个学生都集中精神，提高课堂45分钟的质量。

4. 发挥备课组教师的集体力量，在试题的选择上作到面面俱到，重点难点突出，不重不漏。

由于复习时间较短，基本上每一章复习一节课，也可根据自己班的具体情况做调整。