为什么命题逻辑有效性是可判定的，而谓词逻辑有效性是不可判定的？
因为命题逻辑由有限个合式公式及原子命题构成，且原子命题的取值只有真、假两种，简单的判定方法是真值表穷举，其复杂度为指数级：2^N，N为原子命题数量。快速的方法是先转成合取范式（输入是由否定、而且、或者、蕴含四种连接词构成的语法正确的命题逻辑公式，经过对公式结构归纳作蕴含释放、否定原子、分配律变换三步处理，同时运用DAG优化：共享终止即叶子结点、删除冗余的测试结点、删除重复的有相同子图结构的内部结点，输出等价最小的合取范式），再检测合取范式的有效性（检查所有子句，若每个子句包含至少一个原子及其否定形式，则有效，否则因为存在一种真值指派使其为假而导致整个合取范式无效），其复杂度为多项式级：N*logN+N，N为公式长度。谓词逻辑基于命题逻辑扩展，添加了变元、函数、量词“所有”与“存在”，如果量词没有约束变元范围即定义域无限，那么函数值域也是无限的，另外可能引入的自由变元不受限制，这导致了解空间是无限的，所以不存在通用算法去判定任意谓词逻辑公式是否有效，具体证明可以用pcp归约，即构造一组特定的谓词逻辑公式，它是有效的当且仅当pcp实例有解，又已知pcp是不可判定的，故该特定谓词逻辑有效性是不可判定的，由于任意包括特定，所以谓词逻辑有效性是不可判定的
posted on 2023-09-09 08:05
春秋十二月 阅读(58)
评论(0) 编辑 收藏 引用 所属分类:
Compute Theory