| 
  中国学术期刊网络出版总库
  关闭
带中介的鸽巢公式  
   推荐 CAJ下载 PDF下载
【英文篇名】 Pigeon-Hole Formulas with Medium
【下载频次】 ★★
【作者】 刘长云; 许道云;
【英文作者】 LIU Chang-yun; XU Dao-yun(Department of Computer Science; Guizhou University; Guiyang 550025; China );
【作者单位】 贵州大学计算机科学系; 贵州大学计算机科学系 贵州贵阳; 贵州贵阳;
【文献出处】 贵州大学学报(自然科学版) , Journal of Guizhou University(Natural Science), 编辑部邮箱 2004年 04期  
期刊荣誉：ASPT来源刊  CJFD收录刊
【中文关键词】 鸽巢公式; 消解难例; 二分图;
【英文关键词】 pigeon-hole formula; hard example for resolution; bipartite graph;
【摘要】 鸽巢公式的一个真值指派可以用一个边带标记的完全二分图表示。在完全二分图中插入一个新的中介结点集,可以将鸽巢公式推广到带中介的情形,从而形成一类新的消解难例公式。文中提供了一种新的消解难例的构造方法。
【英文摘要】 A truth assignment of Pigeon-hole formula can be associated to a complete bipartite graph with a edge-label function.By inserting a new set of medium vertices in a complete bipartite graph,we extend Pigeon-hole formula to general pigeon-hole formula.So,we get a class of hard example for resolution.A new method constructing hard example is presented in this paper.
【基金】 贵州省省长基金资助课题
【更新日期】 2005-08-19
【分类号】 O157
【正文快照】 1　引言组合数学中的鸽巢原理(pigeonholeprinciple)指:n只鸽子进入n-1个巢,则有一个巢中至少有两只鸽子。我们用命题xp,h表示第p号鸽子进入第h号巢,其中1≤p≤n,且1≤h≤n-1。则可以用如下命题公式表示鸽巢原理:PHPnn-1=∧(1≤p≤n)(∨(1≤h≤n-1)xp,h)→∨(1≤h≤n-1)∨(1≤i

xxx
【读者推荐文章】中国期刊全文数据库 中国优秀硕士学位论文全文数据库
【相似文献】
中国期刊全文数据库
中国优秀硕士学位论文全文数据库
中国博士学位论文全文数据库
中国重要会议论文全文数据库
中国重要报纸全文数据库
中国学术期刊网络出版总库
点击下列相关研究机构和相关文献作者，可以直接查到这些机构和作者被《中国知识资源总库》收录的其它文献，使您全面了解该机构和该作者的研究动态和历史。
【文献分类导航】从导航的最底层可以看到与本文研究领域相同的文献，从上层导航可以浏览更多相关领域的文献。

数理科学和化学
　 数学
　　 代数、数论、组合理论
　　　 组合数学（组合学）
  
 
  CNKI系列数据库编辑出版及版权所有：中国学术期刊(光盘版)电子杂志社
中国知网技术服务及网站系统软件版权所有：清华同方知网(北京)技术有限公司
其它数据库版权所有：各数据库编辑出版单位（见各库版权信息）
京ICP证040431号    互联网出版许可证 新出网证（京）字008号