合取范式 任何

系统 1784 0

在布尔逻辑中,一个公式是合取范式(CNF)的,如果它是子句的合取。作为规范形式,它在自动定理证明中有用。它类似于在电路理论中的规范和之积形式。 所有的文字的合取和所有的文字的析取是 CNF 的,因为可以被分别看作一个文字的子句的合取和一个单一子句的合取。和析取范式(DNF)中一样,在 CNF 公式中可以包含的命题连结词是与、或和非。非算子只能用做文字的一部分,这意味着它只能领先于命题变量。 例如,下列所有公式都是 CNF:

 

而下列不是:

 

上述三个公式分别等价于合取范式的下列三个公式:

 

所有命题公式都可以转换成 CNF 的等价公式。这种变换基于了关于逻辑等价的规则: 双重否定律、德·摩根定律和分配律。 因为所有逻辑公式都可以转换成合取范式的等价公式,证明经常基于所有公式都是 CNF 的假定。但是在某些情况下,这种到 CNF 的转换可能导致公式的指数性爆涨。例如,把下述非-CNF 公式转换成 CNF 生成有 2n 个子句的公式:

合取范式 任何


更多文章、技术交流、商务合作、联系博主

微信扫码或搜索:z360901061

微信扫一扫加我为好友

QQ号联系: 360901061

您的支持是博主写作最大的动力,如果您喜欢我的文章,感觉我的文章对您有帮助,请用微信扫描下面二维码支持博主2元、5元、10元、20元等您想捐的金额吧,狠狠点击下面给点支持吧,站长非常感激您!手机微信长按不能支付解决办法:请将微信支付二维码保存到相册,切换到微信,然后点击微信右上角扫一扫功能,选择支付二维码完成支付。

【本文对您有帮助就好】

您的支持是博主写作最大的动力,如果您喜欢我的文章,感觉我的文章对您有帮助,请用微信扫描上面二维码支持博主2元、5元、10元、自定义金额等您想捐的金额吧,站长会非常 感谢您的哦!!!

发表我的评论
最新评论 总共0条评论