报告-离散数学-福州大学

报告-离散数学-福州大学（共10篇）

报告-离散数学-福州大学 篇1

离散数学及其应用教育部重点实验室工作总结报告

（2011年3月18日）

实验室名称： 离散数学及其应用教育部重点实验室 主管部门： 福建省教育厅 依托单位： 福州大学

实验室概况: 在迅速发展的计算机科学技术及信息技术等领域，离散数学是重要的基础学科和支撑学科，它的发展和应用是影响一个国家科学技术发展水平的重要因素。以福州大学“离散数学与理论计算机科学研究中心”为依托的离散数学及其应用教育部重点实验室于2007年7月获教育部批准立项建设。目前，实验室共有固定研究人员27人，其中教授16人，副教授4人。实验室由马志明院士担任学术委员会主任，范更华教授担任实验室主任。实验室位于福州大学铜盘校区。2007年11月完成了实验室装修一期工程；2009年3月完成了二期装修工程，达到 “环境优美、设备一流”。按国际研究所标准建设基础设施，为每位研究人员及来访学者提供40平米宽敞办公室及一流科研设备。为每位研究生提供一个工作位及台式电脑。已建成无线网覆盖实验室3000平米的科研、办公场所。重视网络建设，保证网络高速畅通。订购相关专业的国外数据库及原版图书，已基本建成一流的专业图书资料室。

一、实验室现有三个研究方向：图论与组合数学、大规模集成电路设计中的数学方法、优化理论与算法。

二、在本，实验室主任范更华教授获全国优秀科技工作者。实验室在研科研项目国家973计划课题1项，国家自然科学基金7项，其中重点项目1项，面上项目6项，新增国家973计划课题1项，为

1.大规模集成电路物理设计中关键应用数学理论和方法（2011CB808003），范更华 新增国家自然科学基金3项，其中面上项目2项，青年项目1项，分别是：

1.超大规模集成电路多目标划分的算法研究（61070020），朱文兴，国家基金面上项目。

2.近景摄影测量中的自动图像分割技术（11071270），王美清，国家基金面上项目。

3.几类图染色问题的研究（11001055），侯建锋，国家基金青年项目。

实验室在2010年8月顺利完成了国家重点基础研究发展计划（973计划）课题“大规模集成电路设计中的图论与代数方法（2006CB805904）”。课题实施期间，课题组共发表研究论文133篇，其中被SCI收录104篇；由于出色完成了该课题，我们将继续承担新一轮的973课题：大规模集成电路物理设计中关键应用数学理论和方法（2011年1月至2015年12月）。

三、实验室不仅是高水平科学研究中心，也是高层次人才培养基地。实验室以应用数学、计算机应用技术省级重点学科，国家集成电路人才培养基地，离散数学“211工程”建设重点学科，应用数学博士点以及两个一级学科硕士点（数学、计算机科学与技术）为支撑，形成具有一定规模的离散数学高层次人才培养体系。实验室将充分利用自身的条件，围绕主攻方向，提升开放层次，促进学术交流与合作，使实验室整体研究水平达到国内领先水平，某些研究方向达到国际先进水平，为国家及福建地方建设做出突出贡献。本培养博士研究生2名，硕士研究生21名。

四、科研成果

实验室在各个研究问题方面开展了深入地研究工作，在课题研究中取得了一些很好的研究结果。本课题组研究成员在国内外重要专业刊物上发表SCI收录论文27篇，EI收录论文6篇，具体研究成果如下：

（1）图论与组合研究工作 关于连通图支撑树的计数问题，给出了连通图支撑树个数的紧的上界，并且考虑的连通度为k的图的支撑树的个数，同时给出了连通图支撑树的个数和图色数之间的关系，其结果发表在《Applied Mathematics Letters》上。

一个图的Laplacian谱半径是指该图Laplacian矩阵的最大特征值，对于图n个顶点，最大度为△，直径为D的非正则图，Shi给出了该图的Laplacian谱半径的上界，我们改进了该上界，并且证明了该上界给出了在某些情况是紧的，同时，给出了不含三角形图的Laplacian谱半径的上界。对于连通二部图，给出了Laplacian谱半径紧的上界和下界，从而改进了Shi的结果。

在图染色领域，考虑了图的列表染色问题，给出了考虑图列表染色的新的思路，并且用该思路证明了某些形式的完全k部图是(2, 2)-total weight choosable，并证明了除了一条边外的所有完全二部图都是(1, 2)-total weight choosable。研究了稀疏图和平面图的列表全染色问题，证明了如果平面图的最大度不超过8，则其列表全色数不超过11；如果平面图最大度至少是8，且不含5-圈，则其列表全色数等于最大度加一；如果图的最大度是4，并且最大平均度不超过3，则其列表全色数是5，该项成果发表在《Information Processing Letters》上。考虑了有向图博弈染色，给出了有向图博弈色数以及弱的博弈色数的定义，证明每个定向平面图的博弈色数不超过9，每个定向外平面图的博弈色数不超过4，同时研究了有向图强博弈染色，证明了每个定向平面图的强博弈色数不超过16。考虑的外平面图的无圈边染色问题，完全确定了外平面图无圈边色数的上界，其结果发表在《Journal of Graph Theory》上。在化学图论方面，一个图的能量是指该图所有特征值绝对值的和，一个图的能量小于图的顶点数，称该图是hypoenergetic，我们研究了图的能量，构造了顶点数为4n+2的树T，使得T是hypoenergetic，从而验证了Gutman等人在2008年提出的猜想，该文发表在《Applied Mathematics Letters》上。同时考虑的图的能量和Estrada指标之间的关系，给出了图Estrada指标紧的上界。（2）VLSI中的图论与优化算法研究工作

为了开展大规模集成电路设计领域的研究工作，实验室于2010年建立了一个150m2的大规模集成电路设计EDA实验室，拥有16个研究工作位，装备国产熊猫EDA系统软件16台套，对所有实验室研究成员和研究生开放使用。

布局是大规模集成电路电路设计重要环节，决定了超大规模集成电路芯片的性能，尺寸，产量和可靠性，我们给出了基于粒子群优化算法新的智能决策，利用该决策可以超大规模集成电路较快的获得一个可行的电路物理布局。同时在遗传算法的变异和交叉的原则中引入了粒子群优化算法，可以使得该算法脱离局部最优和实现更好的多样性。实验通过采用MCNC和GSRC基准测试表明，该算法是有效的。同时该算法可以避免局部最小，并有很好的收敛性。实验结果表明所提出的方法可以大大帮助集成电路设计中的布局决策，其结果发表在《Soft Comput.》上。

从计算的角度来看，超大规模集成电路布局规划是一个NP-困难问题。我们给出了非分层和模块VLSI布图规划问题的一个混合演化算法（HGA），该算法使用一个有效的遗传搜索方法来探索搜索空间和一种有效的局部搜索方法，利用信息在搜索区域。MCNC基准的实验结果表明该算法是有效的。同时，借助于进化算法和模拟退火算法的概念，给出了另外一种混合演化算法，实验表明该算法也是有效的。

（3）优化理论与算法

我们提出了一个高效求解三维装箱问题（Three Dimensional Container Loading Problem 3D-CLP）的混合模拟退火算法；研究了极大可满足性问题的局部搜索算法，提出了用单纯形法产生“初始概率”(每个变量取1的概率)，用“初始概率”对局部搜索算法中变量的初始随机指派进行适当的约束；研究了箱约束非线性整数规划问题，提出了该问题的离散动态凸化算法，同时还证明了算法的收敛性；对非线性约束连续全局优化问题，我们构造一个结合罚函数的辅助函数，构造了解非线性约束连续全局优化的一个动态凸化算法，该算法避免了传统罚函数法中罚参数选取困难的问题。

五、学术交流

为推动福建省数学教育和研究活动开展，在范更华教授的大力倡导下，协同福建省数学会，于2010年10月16日至17日召开福建省首届数学大会，1100多名来自全省各地高校和中学的数学教师参会。为了使基层农村学校数学教师有机会参加会议，在省政府、省教育厅等部门的大力支持下，会议为300名工作在乡镇学校的教师提供了交通、住宿等经费支持。会议期间，“院士与中学教师互动座谈会”和“专家讲座”等专项活动交流和讨论热烈，这种面对面的交流让来自中小学的数学教师受益匪浅、耳目一新，为广大基层学校特别是农村学校教师提供了良好的学习机会，有效地调动了全省中学教师参与数学研究的积极性，对提升福建省数学教育水平起到了积极的推动作用。

2010年5月，实验室协同中国运筹学会，召开中国运筹学会第八届三次常务理事会。

在本，共有10余位国内外知名学者到校访问，并作报告和进行合作研究，其中包含千人计划入选者，浙江师范大学教授朱绪鼎，香港浸会大学数学系主任朱力行，加拿大Simon Fraser大学教授Pavol Hell等。

报告-离散数学-福州大学 篇2

2007年招收硕士学位研究生入学考试试题

报考专业：计算机各专业考试科目：离散数学（复试）

1.设A,B为非空集合,ρ(A)=ρ(B),求证A=B

2.S＝{|存在z 使得xRz且zRy}

求证若R为等价关系，则S为等价关系

3.从以下题目中任选一道，多选按最低分计算

(1)设为群,R为G上等价关系且对任意x,y,z∈G,若(x*z)R(y*z), 则xRy 设H={h|h∈G且hRe},求证为的子群

(2)没做，4.设T为非平凡无向树,T中度数最大的节点有两个,且度数K>=2,求证T叶子节点的数量>=2K-2

5.一个推理理论的题目.前提：1.所有学生都得参加考试；

2.通过考试的学生都很高兴；

3.所有学习努力的学生都可以通过考试；

4.有些学生学习努力；

报告-离散数学-福州大学 篇3

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

《离散数学》期末复习 篇4

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

一、选择题（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.求最佳前缀码

离散数学复习要点 篇5

题型：选择题、填空题、计算和证明题

(不用担心，考题不难，都是平时上课讲过的内容)

命题逻辑：

命题的判定和符号化（即命题的翻译）.会画命题公式的真值表.理解成真赋值，小项.含n个变元的不等价的命题公式有多少类.求公式的主合取范式和主析取范式.熟悉命题的等价公式(命题定律)和蕴涵公式(推理定律).谓词逻辑:

命题的符号化，即带量词的谓词公式的翻译，包括一元谓词和二元谓词的翻译.谓词公式中量词的作用域.会求谓词公式的前束范式.谓词逻辑中推理的证明(P,T规则 + EI,EG,UI,UG规则).集合与关系:

子集概念，会求幂集，会求幂集中元素个数.会求两个集合的笛卡尔积.关系的性质：（反）自反性，（反）对称性，传递性。弄清定义，会判断。会求复合关系、逆关系.会求自反/对称/传递闭包.会证明等价关系.等价关系与划分的相互转化.图论：

离散数学课程总结 篇6

离散数学是现代数学的`一个重要分支，是计算机科学专业的专业主干课之一，课程结合计算科学的特点研究离散对象和相互关系，对提高学生的抽象思维与逻辑推理能力有很重要的作用。它以研究离散量的结构和相互关系为主要目标，在计算机科学的数据结构、操作系统等有广泛的应用。它是许多数学科目的统称。它的内容包括了数理逻辑、集合论、抽象代数、图论、排列组合、形式语言及自动机等。该门课概念较多、论性较强，定理比较多，学习起来难免有点枯燥乏味。同时也因为概念比较多所以课程连接比较混乱，概念不清，张冠李戴等问题屡屡出现。

第一章主要是介绍命题逻辑的基本概念。其中包括命题与联结词；命题公式及其赋值。这张可以说是基础中的基础，为后面打下基础。通过各种联结词将命题连接起来构成推理，从而可以判断其真假。

第二章主要是介绍命题逻辑等值演算。其中包括等值式；析取范式与合取范式；联结词的完备集；可满足性问题与消解集。学习完了第一章的命题逻辑之后，就开始在此基础上扩充知识点。在这章中重点有运用等值演算法或者真值表法去求解析取范式和合取范式（或者主析取范式和主合取范式）以及等值式。26个等值式中我们要特别需要记住的有分配律，德摩根律，蕴涵等值式，等价等值式，这些等值式贯穿于后面几章的知识。其后就是求主析取范式和主合取范式了

第三章主要是介绍命题逻辑的推理理论。其中包括推理的形式结构和自然推理系统P。这张将又会介绍更多的等值式。当然，学以致用在本章得以诠释，同时这也是考试的一个重点。

第四章的知识点逐渐深入，由浅及深，主要是介绍一阶逻辑基本概念。也就是一阶逻辑命题符号化，一阶逻辑公式及其解释。

第五章与第四章息息相关，主要是介绍一阶逻辑等值演算与推理。包括一阶逻辑等值式与置换规则，前束范式，推理理论。运用等值式及各种规则求一阶逻辑的翻译或者符号化。

第六章主要是介绍集合代数。包括有集合的基本概念，集合的运算，集合恒等式。这章主要是围绕集合而展开学习的，内容简单易懂。

第七章主要是介绍二元关系。其中包括有序对与笛卡尔积，二元关系，关系的运算，关系的性质，关系的闭包，等价关系与划分，偏序关系。这章内容比较重要，特别是后面的五种关系及闭包。了解了有序对知识点后，在此基础上继续学习五种关系：自反性，反自反性，对称性，反对称性，传递性，并且熟悉他们的证明过程。关系的闭包，等价关系，偏序关系是考试的另一个重点，需重点掌握。

第八章主要是介绍函数。包括函数的定义和性质的掌握以及复合函数，反函数。

第九章和第十章主要是介绍代数系统及群与环。可以这样总结：二元运算及其性质---?代数系统---?半群---?独异点---?群。与此同时，我们也要掌握群，半群的相关证明。

第十四章和第十五章主要是介绍图的基本概念以及欧拉图，哈密顿图。在第十四章中，我们初步学习图的相关知识，同时还有图的矩阵表示和运算。这也是一重点。至于欧拉图及哈密顿图，我们要学习如何判断是否为欧拉图及哈密顿图，要求不是很多，了解就好。

二、对课程的意见和建议：

可以适当的多添加几节离散数学课，老师也可以在课堂上适当的添加一些在其他计算机学科中应用的知识点。对离散数学中的一些富有历史趣味的有关离散的历史故事也可以提一提，增加课堂气氛，减少课堂的乏味。

三、对老师德意见和建议：

学习离散数学总结范文 篇7

姓名：

学号：1

班级：计算机

离散数学，对绝大多数学生来说应该都会是一门十分困难的课程，当然也包括我在内。通过这一学期的学习，我对这门课程有一些初步的了解，现在的心情和当初也很不相同。

在还没有接触的时候，看见课本就想退缩，心想：这是什么课程啊，这叫数学吗，这些符号都是之前没有见过的呢！但是既然都说是挑战就没有退缩的道理。虽然不能说是抱着“视死如归”的精神，至少能说是忐忑不安。在听老师讲课的时候有些定义性的东西总会混淆，我自认为是个越挫越勇的人，并没有因此退缩。超乎想象的是，老师讲课好仔细，好详细，因为前面的知识是为后面做铺垫，所以在后面老师经常强调。

而且老师每两次课都会布置作业，这让我们在完成作业的时候对上过的内容进行了加深，有利于我们更好的学习离散数学。而且每次作业老师都很认真批改，错误的地方都会给你圈出来，以便于我们自己更好的完成订正。错误的地方，经过老师认真仔细的讲解，更让我们对知识点及解题技巧有了一定的认知。当一题题目本来不会做错了但是经过老师讲解听讲到会做这题题目的时候，这种成就感还是相当不错的呢。难得有这么认真又负责的老师，让我本来对数学没什么兴趣的人居然也会渐渐地对数学产生了兴趣。有了这些认知，我觉得这门课的难点在于课程比较枯燥，好多理论的知识需要我们去理解。

前三章主要是认识逻辑语言符号，了解了数理逻辑的特点，并做一些简单的逻辑推理和运算。这些知识都是以前所学的进一步转换，只要将数学的函数符号逻辑化就行。也就是说，那些符号知识形式上的不同，实质上是一样的。不同的是，之前的数学只需要运用结论证明其他的案例等。但是逻辑数学不仅要知其然还要知其所以然，运用结论正结论。即使如此，我还是觉得这几章学着很轻松，只要熟练掌握公式定理就会觉得离散数学并不像之前想象的那么困难。

第四章讲的是关系。这一章，进一步认识、运用数理逻辑语言，熟练强化练习，深入理解。这一章的难度相较于前几章要繁琐些，有很多的符号转换，运算，运算过程很复杂。对于计算能力不强的我来说，这一章或许是最吃力的，即使知道原理也需要通过大量的练习强化巩固，而这其中用到的还有线性代数里面的矩阵。

第五章学的是函数，定义和高中所学一样，只不过是把它转换运用于数理逻辑，并用逻辑符号进行运算。虽说如此，但是这其中仍然有更深层次的概念和逻辑公式，如果单纯的用原有的思维是很难想透彻的。

第六章“图”和第七章“树及其应用”可以归为“图论”。在刚接触到“图”这一章的时候我是抱着好奇之心去学习的，因为这章都是关于“图”，想了解一下和几何图形的差别，所以觉得善长几何的我应该能够把它学好。但是不可否认，随着知识的深入，这一章一定会比前面的更难理解，更难学。因此，上课的时候听得格外认真，课后还找了一些相关书籍阅览。在看过这些书籍以后，我才真正了解到它并不是枯燥乏味的，它的用途非常广泛，并且应用于我们整个日常生活中。比如：怎样布线才能使每一部电话互相连通，并且花费最小？从首府到每州州府的最短路线是什么？n项任务怎样才能最有效地由n个人完成？管道网络中从源点到集汇点的单位时间最大流是多少？一个计算机芯片需要多少层才能使得同一层的路线互不相交？怎样安排一个体育联盟季度赛的日程表使其在最少的周数内完成？一位流动推销员要以怎样的顺序到达每一个城市才能使得旅行时间最短？我们能用4种颜色来为每张地图的各个区域着色并使得相邻的区域具有不同的颜色吗？这些问题以及其他一些实际问题都涉及“图论”。

这里所说的图并不是几何学中的图形，而是客观世界中某些具体事物间联系的一个数学抽象，用顶点代表事物，用边表示各式物间的二元关系，如果所讨论的事物之间有某种二元关系，我们就把相应的顶点练成一条边。这种由顶点及连接这些顶点的边所组成的图就是图论中所研究的图。由于它关系着客观世界的事物，所以对于解决实际问题是相当有效的。哥尼斯堡桥问题（七桥问题），这个著名的数学难题，在经过如此漫长的时间最终还是瑞士数学家欧拉利用图论解决了它，并得出没有一种方法使得从这块陆地中的任意一块开始，通过每一座桥恰好一次再回到原点。

树是指没有回路的连通图。它是连通图中最简单的一类图，许多问题对一般连通图未能解决或者没有简单的方法，而对于树，则已圆满解决，且方法较为简单。而且在许多不同领域中有着广泛的应用。例如家谱图就是其中之一。如果将每个人用一个顶点来表示，并且在父子之间连一条边，便得到一个树状图。

图论中最著名的应该就是图的染色问题。这个问题的研究来源于著名的四色问题。四色问题是图论中也许是全部数学中最出名、最难得一个问题之一。所谓四色猜想就是在平面上任何一张地图，总可以用至多四种颜色给每一个国家染色，使得任何相邻国家的颜色是不同的。四色问题粗看起来似乎与我们所讨论的图没有什么联系。其实也是可以转化为图论中的问题来讨论。首先从地图出发来构作一个图，让每一个顶点代表地图的一个区域，如果两个区域有一段公共边界线，就在相应的顶点之间连上一条边。由于地图中每一块区域对应图的一个顶点，两个相邻顶点对应两个相邻的区域。所以对地图染色使相邻的区域染以不同的颜色相当于对图的每个顶点染以相应的一种颜色，使得相邻的顶点有不同的颜色。总之，图论是数学科学的一个分支，而四色问题是典型的图论课题。

通过对图论的初步理解和认识，我深深地认识到，图论的概念虽然有其直观、通俗的方面，但是这许多日常生活用语被引入图论后就都有了其严格、确切的含义。我们既要学会通过术语的通俗含义更快、更好地理解图论概念，又要注意保持术语起码的严格。

离散数学单元测试试题1 篇8

离散数学单元测试试题一

(适用于2014级计算机科学与技术、软件工程、网络工程专业本科学生)

一、选择题(共10题，每题3分，共30分)1.下列语句中为命题的是（D)。A.这朵花是谁的？ B.这朵花真美丽啊！C.这朵花是你的吗？ D.这朵花是他的。

2.若p：他聪明；q：他用功；则“他虽聪明，但不用功”，可符号化为(B)。A.p∨q

B.p∧┐q

C.p→┐q

D.p∨┐q 3.命题公式p∨q→q的公式类型为（D)。A.矛盾式 B.非重言可满足式 C.重言式

D.条件式

4.若F(x)：x是有理数，G(x)：x能被2整除，则“有的有理数能被2整除”，可符号化为（A)。

A.x(F(x)∧G(x))

B.F(x)∧G(x)

C.xF(x)

D.xG(x)5.设F(x)表示x是火车，G(x)表示y是汽车，H(x，y)表示x比y快，命题“某些汽车比所有火车慢”的符号化公式是（B)。

A.y(G(y)→x(F(x)∧H(x,y)))B.y(G(y)∧x(F(x)→H(x,y)))C.xy(G(y)→(F(x)∧H(x,y)))D.y(G(y)→(x)(F(x)→H(x,y)))6．设集合A={1,2,3},A上的关系R={<1,2>,<1,3>,<3,3>},则R具有(D)。A.自反性 B.传递性 C.对称性 D.以上答案都不对

######7.谓词公式x(P(x)∨yR(y))→Q(x)中的 x是(C)。A.自由变元 B.约束变元

C.既是自由变元又是约束变元 D.既不是自由变元又不是约束变元

8.设X、Y是两个集合且|X|＝n，|Y|＝m，则从X到Y可产生(A)个二元关系。A.n  m B.mn

C.2n m D.nm 9.下列关于集合的表示中正确的为(C)。A.{a}{a,b,c} B.{a}{a,b,c}

C.{a,b,c} D.{a,b}{a,b,c} 10．设集合A={1,2,3,4,5},下列哪些是集合A的划分(D)。A.{{1,2},{3,5}}

B.{{1,2,3,4},5} C.{ ,{1,2},{3},{4,5}} D.{{1},{2},{3},{4},{5}}

二、填空题(共10空，每空3分，共30分)1.设p：2＋2＝5，q：明天是阴天，则命题“只要2＋2＝5，那么明天是阴天”可符号化为 p->q，其真值是 1。

2.设p:你陪伴我，q:你代我叫车子，r:我出去，则“如果你不陪伴我或不代我叫车子,我就不出去。”的符号化形式为 ¬p/¬q->r。

3.设p: 天下雨，q: 天刮风，r: 我去书店，则“如果天不下雨并且不刮风，我就去书店”的符号化形式为。

4.设S(x)∶x是大学生；K(x)∶x是运动员。则“有些运动员不是大学生”的符号化为。

5.设P(x)：x非常聪明；Q(x):x非常能干；a：小李；则“小李非常聪明且能干”的符号化形式为。

6.设F(x): x是人，G(x): x用右手写字，则“有的人并不用右手写字”的符号化形式为。

7.设S(x)：x是学生；L(x)：x喜欢英语。则“有些学生喜欢英语”的符号化为：。8.在公式x(P(z)→Q(x,z))∧zR(x,z)中，x的辖域是

，z的辖域是。

三、计算与证明(共2题，每题20分，共40分)1.用等值演算求下公式的主析取范式(p→q)∧r。

2.在命题逻辑自然推理系统中，构造下面推理的证明。前提： p∨q, q→r, p→s, ┐s，结论：r ∧

离散数学衔接试卷1解答 篇9

（课程代码 02324）

1、下列句子是命题的是[ D ]。

A、x + y > 3

B、这朵玫瑰花真美呀

C、请全体同学起立

D、我是一位大学生

2、下列式子为重言式的是[ B ]。

A、(┐P∧R)→QB、P∨（┐P）

C、P∨(P∧Q)D、(┐P∨Q)→(P→Q)

3、对于公式(x)(y)(P(x)∧Q(y))→(x)R(x，y)，下列说法正确的是[ C ]。

A、y是自由变元B、y是约束变元

C、(x)的辖域是R(x, y)D、(x)的辖域是(y)(P(x)∧Q(y))→(x)R(x,y)

4、设R是实数集，f:R→R, f(x)=x^2+2，则f 是[D ]。

A、单射B、满射

C、双射D、映射

5、下列运算不满足交换律的是[A ]。

A．a*b=a+2b B．a*b=min(a,b)

C．a*b=|a-b| D．a*b=2ab 101100011011

6、下列关系矩阵所对应的关系具有对称性的是[D ]。1100B、1001 1A、001010C、0 01D、

7、如右图所示的有向图的最大出度是010[C ]。100A、0 B、1

C、2 D、38、下列图是欧拉图的是[D ]。

9、下列正确的说法是[D]。

A、满足自反性、对称性的二元关系称为等价关系

B、满足自反性、传递性的二元关系称为等价关系

C、满足自反性、反对称性、传递性的二元关系称为等价关系

D、满足自反性、对称性、传递性的二元关系称为等价关系

10、一棵树的3个4度点，4个2度点，其它的都是1度，那么这棵树的边数是 [ B]。

A、13 B、14

C、15 D、16

二、填空题（本大题共10小题，每小题3分，共30分。请将正确答案填入括号内。填错或不填都不得分。）

1、P表示“王一学习努力”，Q表示“王一身体好”。则“王一学习努力身体又好”的符号表述为：

2、设命题变元P、Q、R的真值都是0，则命题公式(┐P∧R)→Q的真值为 1。

3、设论域为{1 , 2}，与公式(x)A(x)等价的是PQ。A1A2A3。

R6,6。

4、设H =｛f，m，s，d｝依次表示一个家庭里的父母子女四个人的集合，R是H上的长幼关系，则R =f,s,f,ds,m,d,m,。

5、设A=｛1，3，6｝，H上的关系R={（1，1），（1，3），（3，3）}，则R的自反闭包为r（R）=

6、全体整数的集合Z上定义关系R为模4同余关系，则Z关于R的分类Z/R = 10011007、设S为非空集合，T为S的幂集，代数系统中，对于∪的单位元是。，这个有向图为：

8、已知有向图的邻接矩阵为

0011。3度点，其它的都是叶子，则这棵树的叶子数为：

9、一棵树有2个4度点，3个 9。101010、周游树的前序行遍法的访问次序为：树根、左子树、右子树。

三、计算题（本大题共5小题，每小题8分，共40分。）

1、设集合，求集合的幂集。

解：。

2、设集合，是集合上的整除关系，画出

解： 01,2,3,0AAa,bPA,a,b,a,bAA1,2,4,8RA,R的哈斯图。

3、求下图的最小生成树。

解：

4、构造下列命题公式

pqp 的真值表。

1、今有a、b、c、d、e、f、g等7人，已知以下信息：a会说英语，b会说英语和汉语，c会说英语、意大利语和俄语，d会讲日语和汉语，e会讲德语和意大利语，f会讲法语、日语和俄语，g会讲法语和德语。用图来证明这7个人按照适当顺序围成一圈，相邻的两人可以交谈。

解：

经观察哈密顿回路是：。

2、证明整数集合上的“大于或者等于”关系是偏序关系。

证明：（1）任意给出一个整数，则。即“大于或者等于”关系满足自反性；

（2）如果有两个整数，使得，且，则。即“大于或者等于”关系满足反对称性；

（3）如果有三个整数，使得，且，则。即“大于或者等于”关系满足传递性。

离散数学证明方法有哪些 篇10

反证法反证法是证明那些“存在某一个例子或性质”，“不具有某一种的性质”，“仅存在”等的题目。它的方法是首先假设出所求命题的否命题，接着根据这个否命题和已知条件进行推演，直至推出与已知条件或定理相矛盾，则认为假设是不成立的，因此，命题得证。

构造法证明“存在某一个例子或性质”的题目，我们可以用反证法，假设不存在这样的例子和性质，然后推出矛盾，也可以直接构造出这么一个例子就可以了。这就是构造法，通常这样的题目在图论中多见。值得注意的是，有一些题目其实也是本类型的题目，只不过比较隐蔽罢了，像证明两个集合等势，实际上就是证明“两个集合中存在一个双射”，我们即可以假设不存在，用反证法，也可以直接构造出这个双射。