如何将命题公式转换为合取范式(CNF)? [英] How to convert a propositional formula to conjunctive normal form (CNF)?

问题描述

如何将这个方程式转换为CNF?

How can I convert this equation to CNF?

¬((p ∨ ¬Q) ⊃ R) ⊃ (P ∧ R))

推荐答案

要将命题公式转换为合取范式，执行以下两个步骤:

To convert a propositional formula to conjunctive normal form, perform the following two steps:

1. 将否定式推入公式，重复应用迪摩根定律，直到所有否定式仅适用于原子.您可以以否定范式获得一个公式.

1. Push negations into the formula, repeatedly applying De Morgan's Law, until all negations only apply to atoms. You obtain a formula in negation normal form.

• ¬(p∨q)到(¬p)∧(¬q)

¬(p∧q)到(¬p)∨(¬q)

重复应用分配律，其中连接词上出现析取.一旦这不可能了，该公式就会出现在CNF中.

Repeatedly apply the distributive law where a disjunction occurs over a conjunction. Once this is not possible anymore, the formula is in CNF.

• p∨(q∧r)到(p∨q)∧(p∨r)

要获得析取范式的公式，只需在步骤2中将∧的分布应用于∨即可.

To obtain a formula in disjunctive normal form, simply apply the distribution of ∧ over ∨ in step 2.

问题中使用的子集符号(⊂)只是逻辑含义/含义的替代表示法，通常表示为箭头(⇒).

The subset symbol (⊂) used in the question is just an alternative notation for the logical implication/entailment, which is usually written as an arrow (⇒).

这篇关于如何将命题公式转换为合取范式(CNF)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！