可满足性问题的充分必要条件 |
| |
引用本文: | 郭成.可满足性问题的充分必要条件[J].中国西部科技,2007(9). |
| |
作者姓名: | 郭成 |
| |
作者单位: | 淮海工学院数理科学系,江苏连云港222005 |
| |
摘 要: | 可满足性问题是计算机和人工智能领域内的一个重要的问题,是第一个被证明是NPC的问题。本文主要把子句集进行分类,给出翻转定义、简单集定义,翻转同构定义,并且证明翻转同构不改变子句集的可满足性。论文证明了可满足子句集的三个充要条件。并且这些充要条件可以用于判断可满足问题的完全搜索和不完全搜索算法。
|
关 键 词: | 子句集 赋值 模 简单集 翻转 翻转同构 |
本文献已被 维普 等数据库收录! |
|