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

第一篇：2013年年报告-离散数学-福州大学

离散数学及其应用教育部重点实验室工作总结报告（2014年1月28日）

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

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

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

二、本年度实验室在研科研项目国家973计划课题1项，国家自然科学基金13项，其中重点项目1项，面上项目4项，青年项目8项。教育部重点项目1项，高等学校博士学科点专项科研基金1项。新增国家自然科学基金4项，均为青年项目，分别是： 1.图的完美匹配计数及其相关问题的研究（11301085），林峰根。2.变密度粘性流体动力学中非线性瑞利-泰勒不稳定性的数学理论研究（11301083），江飞。3.保持全局形状和视觉舒适度的2D和3D媒体适应方法（61300102），牛玉贞。

4.不相交QoS路径与斯坦纳网络的近似算法研究（61300025），郭龙坤。

实验室成员于元隆博士获福建省“闽江学者奖励计划”项目资助，郭文忠博士获福建省自然科学基金杰青项目资助。

实验室成员陈国龙教授和郭文忠博士主持的“内网安全监控平台研制及其产业化”获福建省科技进步二等奖，该项研究针对日益严重的内网安全问题，深入分析内网所面临的各种安全威胁，从身份认证、网络接入控制、数据保护、移动存储设备监控以及网络访问监控等关键问题入手开展内网安全关键技术的创新开发，具体如下：(1)研发了基于USB 安全锁、手掌静脉识别、用户名与密码的统一身份认证平台，采用多因子身份认证方式，解决内网用户身份的合法性和真实性验证问题。(2)研发了一种高安全性的内网安全综合管理的网络接入控制方案，通过内网安全综合管理系统、统一身份认证平台、802.1x 交换机和Radius 服务器之间的联动实现对网络接入终端的身份验证和接入安全控制。(3)研发了一种基于微过滤器模型及内嵌加密标识的数据动态加解密技术的数据保护技术。(4)研发了基于新一代WFP 模型的网络数据包监控和过滤引擎，设计了一种融合防病毒和入侵检测功能的多功能综合网关。

实验室成员朱文兴教授主持的“连续全局优化和非线性整数规划的算法研究”获福建省自然科学奖三等奖。

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

四、年度科研成果

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

（1）VLSI中的图论与优化算法研究工作

1、设计并实现了超大规模集成电路混合单元布局问题的一个新的布局流程，主要思想是用版图规划算法指导电路单元的布局。该布局流程包含4个步骤：1）在多级框架下，利用递归划分技术对电路单元聚类；2）对每层的模块用版图规划算法布局；3）用局部移动技术确定宏单元的精确位置；4）当宏单元的位置确定后，用标准单元布局算法确定标准单元的具体位置。与当前最好的混合单元布局器相比，对IBM mixed-size benchmark circuits和modern mixed-size(MMS)placement benchmarks，我们的布局器在合理的计算时间内能得到最好的平均半周长线长。经过分析发现，我们的布局器的划分和模块形成阶段（即聚类阶段）占用了总的计算时间的2/5，所以划分和模块形成阶段是我们的布局器的主要瓶颈，需要进一步研究。

2、由于图划分问题在布局问题中有直接的应用，我们研究赋权图的最大二等分问题，该问题是NP困难问题。我们构造了该问题的一个memetic算法，其中包括一个快速的局部搜索过程，一个的交叉算子和种群修改策略。这些策略能在全局搜索和局部搜索之间取得平衡。利用文献中的大量有800-10000个顶点的标准测试实例对我们所构造的算法进行测试，我们的算法能取得所测试例子的比当前最好结果更好的解。与著名的circut算法相比，我们的算法在割值方面的提高幅度在0.02% 到4.15%之间。从而实验表明了我们的memetic算法可以在可接受的计算时间内获得高质量的解。

3、研究了超大规模集成电路划分问题的动态凸化算法。利用辅助函数，把集成电路划分问题等价变换为有约束非线性整数规划问题，并构造了动态凸化算法这一全局搜索算法。我们修改了集成电路划分的FM算法，使适合我们的整数规划问题。理论分析和实际计算表明，我们的算法可以成功跳出离散局部极小解。在ACM/SIGDA和ISPD98的测试实例集上的测试表明，我们的局部搜索算法得到的结果比FM算法优58%以上。为解决大规模集成电路划分问题，我们把所构造的算法集成到多级划分框架MLPart中，在同一测试实例集上的测试表明，算法所得到的结果比MLPart优3-7%。

4、划分与超大规模集成电路紧密相关，我们研究了图的max-k-cut问题，把该问题转化为非线性整数规划问题。改进了集成电路划分的FM算法，构造了该问题的一个局部搜索算法。为跳出局部极大解，我们构造了一个辅助函数，理论分析和实验表明，对该函数的局部搜索，可以找到更好的局部极大解。对k=2的情况，用大量的标准实例计算实验表明，算法不仅可以求到当今其它基于局部搜索的算法不能找到的解，而且效率较优。对k≧2的情况，算法也是稳定的，且可以与国际上最新的算法比较。

5、研究了从超大规模集成电路全局布局中提取的非线性规划问题，其目标函数是对半周长线长的基于L1范数的近似，是两个凸函数的和，约束是密度函数约束，是一系列Lipschitz连续非凸函数构成的不等式。该问题对交替方向法来说是新问题，我们构造了基于临近点的交替方向法，在适当条件下证明了算法收敛于问题的KKT点。在实现的时候，我们对临近点参数采用自适应策略。把所构造的算法嵌入到NTUplacer中，用IBM的标准测试实例测试，对18个例子所获得的半周长线长均比NTUplacer3的短，其中例子IBM01的要短3.21%，IBM08的要短6.97%。与其他的最新的布局工具相比，我们的算法在18个例子中多数占优势。该算法的优点是计算效果好，但是算法的计算时间太长，需要在以后的研究中加以克服。

6、研究了超大规模集成电路标准单元布局问题的ell-1模优化模型。我们把半周长线长目标函数用ell-1模近似，把单元重叠函数用非光滑函数近似，然后用非光滑共轭次梯度法求解所得到的非光滑优化模型，进而构造了一个标准单元布局的多级框架。该框架包含聚类阶段和解聚类阶段。在聚类阶段中，我们改进了best-choice电路聚 类算法，以实现电路的全局视图。在解聚类阶段中，用我们所构造的非光滑优化技术对全局布局问题逐级求解，其中对目标线长和密度约束需要做仔细的平衡。我们用IBM standard cell benchmark circuits 和 Peko suites的测试例子测试所构造的布局工具，初步实验表明该工具能在合理的时间内获得高质量的布局效果，而且在时间和解的质量上与当前主流的布局工具相比，有很大的优越性。

7、总体布线是超大规模集成电路物理设计中极为重要的一个环节。针对此问题，我们在研究中引入了非曼哈顿结构，继而在非曼哈顿结构的基础上开展了总体布线中布线树的相关构造工作，包括：1）超大规模集成电路中绕障X结构Steiner树问题已经被证明是一个NP完全问题，而且对于超大规模集成电路中的非曼哈顿结构布线问题有着非常重要的意义。本课题提出了一种有效的绕障X结构Steiner树算法。研究成果发表在国际会议《IEEE ICNC2013》。本课题在绕障X结构Steiner树的基础上进一步考虑多层结构，基于粒子群优化方法提出了多层绕障X结构Steiner最小树算法；2）超大规模集成电路中性能驱动非曼顿结构Steiner树是VLSI布线中非常重要的布线树模型。本课题设计一个基于多目标离散粒子群优化算法的性能驱动Steiner树构造算法。

（2）图论与组合研究工作

课题组开展了关于超图的张量谱理论的研究工作，并对于图与超图的划分问题相关的谱与张量谱方法等问题进行了系统研究，取得了多项有意义的结果。

1.著名的Erdős–Sós猜想是说如果图G的平均度大于k-1，则G存在k条边的任意树，对于该猜想的成果较少，研究方法较单一，我们对该猜想进行了深入研究，利用新的思路证明了如果图G的平均度大于k-1，则G存在k条边的任意蜘蛛，其中k≥(n+5)/2，其结果为研究Erdős–Sós猜想提供了新的思路。

2.图的无符号Laplace矩阵的研究是图谱理论研究的重点问题，我们将图的无符号Laplace矩阵推广到无符号，从而研究一致超图谱的性质，给出了超图的无符号Laplace张量谱理论的一些基本性质，特别是，偶一致超图无符号Laplace张量的最小和最大的 Z-特征值的研究，并研究了与这两个Z-特征值有关的超图的边割和边连通性。

3.给出了偶一致超图无符号Laplace张量的H-特征值，并证明了H-特征值的一些基本性质，对取到最小和最大无符号Laplace张量的H-特征值的偶一致超图进行了刻画，同时，研究了H-特征值与一致超图的割，最小度，最大度的关系。同时，利用最小和最大无符号Laplace张量的H-特征值给出了一致超图边割和边连通度的上下界。

4.研究了平面图的无圈边染色问题，给出了平面图无圈边色数的上界，该上界改进了《SIAM J.Discrete Math.》上的结果。同时考虑了围长为5的平面图的无圈边染色，给出了这类图无圈边色数的紧的上界，同时证明了，如果该类图的最大度至少是4，则其无圈边色数等于最大度，该结果改进了原有一系列结果。

五、学术交流

2013年5月，实验室和福州大学数学与计算机学院，主办了“图与超图谱理论国际研讨会议”，本次国际学术会议是首次在国内召开的有关图与超图谱理论的专题研讨会，会议主席为香港理工大学祁力群教授和厦门大学张福基教授，执行主席为福州大学常安教授。共有来自美国、荷兰、澳大利亚、南非、中国香港地区和国内北京大学、清华大学、上海交通大学高校的60多位学者和博、硕士研究生参加了此次研讨会议，其中包括北京大学张恭庆院士、美国威斯康辛大学Richard Brualdi教授（University of Wisconsin-Madison）、宾夕法尼亚州立大学Winnie Li教授（Pennsylvania State University）、荷兰Tilburg 大学Willem Haemers教授（Tilburg University）、同济大学邵嘉裕教授等多位国内外知名学者。福州大学副校长、离散数学及其应用教育部重点实验室主任范更华教授在会议开幕式上代表福州大学致辞欢迎并介绍了福州大学概况。

在为期4天的研讨会期间，共有31位与会国内外学者做了图与超图谱理论研究领域最新研究成果的学术报告，包括20个40分钟会 6 议邀请报告：11个20分钟会议报告。这些报告内容涉及图的谱理论、张量谱理论、超图的张量表示及其谱理论，以及与图与超图谱理论相关的应用问题研究等。另外，会议在5月30日下午专门安排了半天的3个专题报告，由香港理工大学祁力群教授等系统介绍了关于张量特征值理论和超图张量特征值问题的基础知识和研究进展情况。本次会议为图与超图谱理论研究领域的国内外专家学者开展学术交流和合作研究提供了一次难得机会，与会者一致认为这是一次高水平的学术研讨会，会议报告和讲座体现和代表了国内外相关研究的先进水平和本领域国内外研究现状和趋势，将对于国内相关研究领域的科学研究和发展起到积极的促进作用，并有助于开拓与会研究生的视野和研究水平的提高，促进青年研究人才的培养。本次会议得到了教育部高校数学中心资助！

2013年12月，实验室主办了“2013 International Conference on Cloud Computing and Big Data(CloudCom-Asia)”国际学术研讨会，共有100多位学者和博、硕士研究生参加了此次研讨会议。2013年3月，实验室联合国家自然科学基金委，召开了数学天元基金“问题驱动的应用数学研究”研讨会，5月，在实验室召开了973计划项目“信息及相关领域重大需求的应用数学研究”交流会。在本年度，共有10余位国内外知名学者到校访问，并作报告和进行合作研究，其中包含美国伊利诺伊大学教授Douglas West，美国乔治亚理工大学教授郁星星，美国乔治亚州立大学教授陈冠涛，山东大学教授吴建良等。

第二篇：2012年报告-离散数学-福州大学

离散数学及其应用教育部重点实验室工作总结报告（2013年2月20日）

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

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

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

二、本实验室在研科研项目国家973计划课题1项，国家自然科学基金7项，其中重点项目1项，面上项目2项，青年项目4项。教育部重点项目1项，高等学校博士学科点专项科研基金1项。新增国家自然科学基金7项，其中面上项目3项，分别是：

1.超大规模集成电路布局的ell-1模优化模型及其算法研究（61170308），朱文兴。2.有色噪声下基于噪声约束最小均方估计的语音增强算法（61179037），夏又生。

3.非曼哈顿结构下带粒子群优化的VLSI总体布线算法研究（11141005），陈国龙。青年项目4项，分别为：

1.基于视觉注意力机制的机器人认知视觉感知系统（61105102），于元隆

2.无线传感器网络中任务调度的并行联盟生成与博弈分配策略（61103175），郭文忠

3.图的拉普拉斯谱及相关拓扑指标（11101087），刘剑萍 4.不含某些子式的拟阵结构（11201076），陈容

实验室成员刘剑萍主持的“图谱理论及其相关问题”获福建省自然科学二等奖。

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

四、科研成果

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

（1）VLSI中的图论与优化算法研究工作

在大规模集成电路设计理论研究方面，课题组在开展拟定研究工 作的同时, 进一步加强与集成电路设计研发机构的合作，先后派出课题组成员和博士研究生共计9人次到北京华大九天软件有限公司，了解我国目前唯一的集成电路设计工具“九天”EDA的研发进展，并针对该项研发所提出的多项实际研究问题，从理论和实际两个方面都提出了解决方案。

1）北京华大九天软件有限公司正在着力开发的自动化对称布线软件中，由于当前国内外对对称布线的系统研究非常少, 在实际布线过程中存在线网需要对称布线的问题。该问题目前都是采用手工布线,只能解决布线层和已布线网数比较少的情况, 还经常出现找不到问题的解的情况。课题组研究了该问题，证明了H-V模型下对称布线问题等价于在有效连通图中找所有引脚对应点的一棵斯坦纳树问题，并提出一个解决对称布线问题的算法。该算法适合无网格且水平和垂直布线层交替出现的模型，经过修改还得到在一层中既可以水平布线又可以垂直布线的模型下的对称布线问题的方法。这项研究为自动化对称布线软件的开发提供了一个方法和理论保障。

2）研究了超大规模集成电路标准单元的布局问题。布局是超大规模集成电路物理设计的关键步骤，影响了芯片的可布线性、性能和功耗。我们研发了一个标准单元布局器，其中包含了全局布局和详细布局两个阶段。在全局布局阶段，我们用非线性规划方法和最优聚类技术对电路聚类，在解聚类阶段用迭代改进技术确定每个单元的位置，同时缩短线长。在详细布局阶段，我们构造一个快速合法化算法把全局布局的解合法化，并用单元序消除策略改进合法化后的解。用IBM standard cell benchmark circuits和Peko standard cell benchmark suite2对所构造的布局工具做测试，实验表明该布局工具可以在合理的时间内得到高质量的布局结果。

3）研究了与集成电路设计相关的若干理论问题。在与电路划分问题密切相关的图划分问题研究中，研究了最小平衡划分问题，在一般图类上给出了一个紧的上界，将这一结果应用于平面图类上，得到了平面图最小平衡划分很好的上界。

4）构造了图的max-cut问题和max-k-cut问题的动态凸化算法，计算实验表明了算法的性能是这两个问题当前性能最好的算法之一。利用B*-tree表示法，构造了矩形装箱问题的启发式装箱策略，构造了改进该策略的一个局部搜索算法。实验表明算法可以有效地求解矩形装箱。研究了带一个连续变量的0-1背包问题，构造了快速分支定界算法；构造了非凸混合非线性整数规划问题的动态凸化算法。实验验证了算法的有效性。（2）图论与组合研究工作

课题组开展了关于图的平衡划分，图与超图的谱理论拟阵分解，Ramsey理论，图染色的研究工作，取得了多项有意义的结果。

1）在离散数学中，一个常见的现象是对连通度较低的结构很适合用数学归纳法但却没有很多有用的性质，而那些连通度较高的结构虽然有很多好的性质却不能用数学归纳法。因此，如何找到一个二者的最佳结合点便成为了一个大家关注的问题。1连通拟阵很显然可以分解成2连通拟阵。Cunningham和Edmonds证明了通过运算“2-sum”任意2连通拟阵可以像树一样地分解成一系列的3连通拟阵。在这篇论文中，我们证明了任何元素个数大于等于9的3连通可表示拟阵，通过运算“reducing”可以像树一样地分解成一系列的序列4连通拟阵和三类特殊的拟阵。序列4连通是一个介于3连通和4连通之间的连通度，它弥补了对4连通拟阵不能用数学归纳法的缺憾，也具备了3连通拟阵不具备的好的性质。该论文发表在组合顶级杂志“J.Combin.Theory Ser.B”上，审稿人称该文“of high quality”, “of interesting and will be useful to other researchers.Moreover, the methods used are good”。

2）图的线性荫度是指将图分解成线性森林的最小数目，在1984年，Akiyama提出了注明的线性荫度猜想，在2008年,Wu等人证明了平面图满足线性荫度猜想，我们对平面图上的线性染色进行了考虑，猜测如果平面图的最大度至少是6，则其线性荫度可以完全确定，并且证明了如果平面图的最大度至少是8，其线性荫度可以完全确定，从而猜想只剩下最大度等于6或者7的情形，同时，我们给出了该类图的一个线性染色，其时间复杂性是O(nlogn)。

3）图的无圈边染色问题是著名数学家Alon提出的，在2001年，Alon等人利用概率方法给出了无圈边色数的上界。在其证明过程中，因为小圈会以很大的概率出现两种颜色，因此其上界较难改进，我们利用类似的思路考虑的围长较大的图的无圈染色问题，从而改进其上界，同时，我们利用组合方法考虑的不含三角形的系列平行图的无圈染色问题，确定了该类图的无圈边色数。在2001年，Alon等人给出了无圈边染色猜想，我们验证了不含短圈的平面图上的情形。4）Remasy理论的研究是一直是图论研究的热门问题，我们研究了非对角Remasy，证明了存在一个正整数C，使得下面成立：如果N

五、学术交流

2012年11月2日--6日，由中国系统工程学会模糊数学与模糊系统专业委员会（国际模糊系统协会中国分会）主办，由福州大学承办的第十六届全国模糊数学与模糊系统学术会议在福州大学学术交流中心--怡山大厦隆重举行。

本次会议由中国模糊数学与模糊系统专业委员会名誉主任委员、中国科学院院士刘应明教授担任大会主席，由专业委员会主任委员、四川大学罗懋康教授担任程序委员会主任，由实验室主任范更华教授担任组织委员会主任，由专业委员会秘书长、四川大学张德学教授和福州大学校长助理、科技处处长陈国龙教授担任组织委员会副主任。参加大会的代表有来自全国高等院校、研究院所等60多个单位的专家学者和研究生200多人。本次会议得到了全国模糊数学和模糊系统领域的专家和学者的大力支持，共收到学术论文110余篇，经专家评审，其中42篇论文发表在专业委员会杂志《模糊系统与数学》2012年第4期和第5期上，18篇论文发表在杂志《数学的实践与认识》2012年第19期上。在本次会议期间，代表们进行了广泛的学术交流。9位专家分别作了精彩的大会报告，24位代表在分组会上进行了学术交流，内容涉及模糊数学的理论研究及应用等领域。本次学术会议学 术氛围浓厚，交流广泛，达到了国内模糊数学界相互交流最新研究成果的目的。

2012年12月7日至11日，实验室主办“2012年离散数学国际研讨会”，40多位国内外离散数学专家应邀参加了会议，在本次会议期间，代表们进行了广泛的学术交流。20位专家分别作了精彩的学术报告，内容涉及离散数学的理论研究及应用等领域。本次学术会议学术氛围浓厚，交流广泛，达到了国内离散数学界相互交流最新研究成果的目的。

2012年12月14日至16日，实验室主办了“International Workshop on Image Processing and Inverse Problems”国际学术会议，共有70多位国内外学者参会。

在本，共有10余位国内外知名学者到校访问，并作报告和进行合作研究，其中包含美国乔治亚理工大学教授郁星星，复旦大学教授朱洪，南开大学教授向开南等。

第三篇：2011年报告-离散数学-福州大学

离散数学及其应用教育部重点实验室工作总结报告（2012年2月10日）

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

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

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

二、在本，实验室在研科研项目国家973计划课题1项，国家自然科学基金8项，其中重点项目1项，面上项目6项，青年项目1项。国家科技部产学研项目1项，教育部高校博士点专项科研基金联合资助课题1项，新增国家自然科学基金3项，均为青年项目，分别是：

1.矩阵定性分析中Ray非异及复符号非异矩阵的特征刻画（11101088），刘月。2.图的Ramsey理论中的随机方法（11101086），林启忠。3.Volterra 方程与高维分数阶扩散方程的理论与数值研究（11201077），李娴娟。

新增教育部重点项目1项：动态拓扑下WSN任务调度中多目标优化问题的算法研究，郭文忠。

实验室成员侯建锋博士获福建省自然科学基金杰青项目资助。

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

四、科研成果

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

（1）VLSI中的图论与优化算法研究工作

1）在大规模集成电路设计理论研究方面，课题组在开展拟定研究工作的同时, 进一步加强与集成电路设计研发和研究机构的合作，先后派出课题组成员和博士研究生共计9人次到北京华大电子了解我国目前唯一的集成电路设计工具“九天”EDA的研发进展，并针对该项研发所提出的多项实际研究问题，从理论和实际两个方面都提出了解决方案。在北京华大九天公司正在着力开发的自动化对称布线软件研发中，由于当前国内外对对称布线的系统研究非常少, 在实际布线过程中如果存在线网需要对称布线都是采用手工布线, 而且手工布线也只能解决布线层和已布线 网比较少的情况, 还经常出现找不到问题的解的情况。课题组得到了H-V模型下对称布线问题等价于在有效连通图中找所有引脚对应的点的一棵斯坦纳树并提出一个解决对称布线算法。本方法适合无网格且水平和垂直布线层交替出现的模型。此方法经过修改还得到一层既可以水平布线又可以垂直布线的模型下关于对称布线问题的方法。这项研究为自动化对称布线软件的开发提供了一个方法和理论保障；布线在超大规模集成电路布局面积中是一个关键性问题。Szymanski证明找一个通道布线的最小宽度是NP-困难的。课题组研究证明了通道对应的图CCG的一个最少平行团覆盖等价于一个垂直限制无圈且不添加新的空列和狗腿到网格上的二层曼哈顿模型通道布线的一个最优解。根据这个结论我们还给出了一个解决二层曼哈顿模型通道布线的一个启发式算法。为华大九天公司开发的自动化布线软件中自动化通道布线软件的开发提供了一个可行的解决方案；我们使用图论的方法对David Szeszler的2层具有Manhattan模型的通道布线的算法进行改进，并给了一个新的算法，这个算法比以前的算法所用层数更少，该项研究可用在华大九天公司正在开发的布线工具通道宽度的估计。

2）研究并设计出器件匹配问题的一种自动匹配方法（MatchingLiu算法），该算法已用C程序实现。通过华大九天公司的评估，认为该算法快速、有效，可以帮助弥补公司新一代IC设计平台Aether的自动匹配工具的空白。

3）研究了超大规模集成电路标准单元的布局问题。布局是超大规模集成电路物理设计的关键步骤，影响了芯片的可布线性、性能和功耗。我们研发了一个标准单元布局器，其中包含了多层全局布局和详细布局两个阶段。在全局布局阶段，我们用非线性规划方法和最优聚类技术对电路聚类，在解聚类阶段用迭代改进技术定每个单元的位置，同时缩短线长。在详细布局阶段，我们构造一个快速合法化算法把全局布局的解合法化，并用单元序消除策略改进合法化后的解。用IBM standard cell benchmark circuits和 Peko standard cell benchmark suite2对所构造的布局工具做测试，实验表明该布局工具可以在合理的时间内得到高质量的布局结果。

4）研究了超大规模集成电路标准单元的布图规划问题。布图规划是超大规模集成电路物理设计的第一阶段，是NP难问题。我们构造了不可二分布图规划问题的混合模拟退火算法，该算法先用一个贪心策略生成初始的B*-tree，通过B*-tree搜索解空间，并用一个新的经验性策略平衡全局搜索和局部搜索。用MCNC benchmarks的实例对算法作测试，实验表面算法能快速找到最优解或近优解。

5）电路划分是VLSI 物理设计自动化中的一个关键阶段，也影响了后续的电路设计，电路划分问题是NP 困难的组合优化问题。我们把该问题转化为带约束的非线性整数规划问题，同时构造了该问题的动态凸化算法。算法用改进的Fiduccia-Mattheyses(FM)算法作为非线性整数规划问题的局部搜索算法。理论分析和实验表面，通过增加一个参数的值，算法能跳出局部极小解找到更好的的解。我们用ACM/SIGDA and ISPD98 benchmarks的测试实例对算法作测试，结果表明我们的算法产生的解的质量大大优于原始的FM算法。进一步，我们把所构造的算法集成到多层划分工具MLPart中，实验表明，所得到的解的质量比MLpart提高了3-7%。此外，我们把FM 算法结合到分散搜索算法框架中，提出一种电路划分的分散搜索算法。算法利用FM 算法进行局部搜索，利用分散搜索的策略进行全局搜索。为满足分散搜索方法对初始解的质量和多样性的要求，提出采用GRASP 和聚类相结合的方法来产生初始解。实验结果表明，该算法可以求解较大规模的电路划分实例，且与基于多级框架的划分算法hMetis 相比，划分的质量有了明显的提高。

6）研究了从集成电路中提取的max-k-cut问题，构造了该问题的一个动态凸化算法；研究了带一个连续变量的0-1背包问题，构造了快速分支定界算法；构造了非凸混合非线性整数规划问题的动 态凸化算法。实验验证了算法的有效性。（2）图论与组合研究工作

在图全染色方面，证明了图的全色数等于d+1的几个充分条件，其中d表示图的最大度，其结果推广了发表在《Discrete Applied Mathematics》上的堵丁柱教授的结果。

在图无圈边染色方面，考虑了不含短圈的平面图的无圈边染色，给出了无圈边色数等于图的最大度的两个充分条件，并且给出了不含三角形或者不含四圈的平面图的无圈边色数的上界，其上界大大改进了已有结果。

在图的谱理论研究中，主要开展了关于图的代数连通度、与图与超图的划分问题相关的谱方法等问题的研究工作。得到了图的最大割新的有关无符号Laplace谱的较好上下界、具有完美匹配图的代数连通度序等多项结果。

五、学术交流

本来校访问并作合作研究的国内外著名学者10余人次，其中包括中科院院士、北京大学教授田刚，香港浸会大学教授朱力行，澳大利亚Newcastle大学林宇清等。

第四篇：离散数学及其应用教育部重点试验室工作总结报告-福州大学

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

（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等。

第五篇：离散数学

离散数学课件作业

第一部分 集合论

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

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号。