命题逻辑公式的范式
析取范式与合取范式
析取范式是一个或多个简单合取式的析取
• 简单合取式是一个或多个文字的合取
文字(literal)是命题变量或命题变量的否定
合取范式是一个或多个简单析取式的合取
• 简单析取式是一个或多个文字的析取
析取范式举例
单个文字既是简单合取式也是析取范式:p, ¬q, ⋯
单个简单合取式是析取范式:p ∧ q, q ∧ ¬r, ⋯
多个简单合取式的析取范式:p ∨ q ∧ ¬r , p ∨ q,
合取范式举例
单个文字既是简单析取式也是合取范式:p, ¬q, ⋯
单个简单析取式是合取范式:p ∨ q, q ∨ ¬r, ⋯
多个简单合取式的析取范式:p ∧ q ∨ ¬r , p ∧ q,
求与公式逻辑等值的析取范式
• 先通过蕴涵等值式和双蕴涵等值式转换为不含→和 ↔的公式
• 然后使用德摩尔根律将所有否定运算符移到命题变量的前面
• 最后使用分配律将合取运算符放到括号里的文字之间,而析取运算符放到括号外的合取式之间
主析取范式与主合取范式
什么是主合取范式(principal conjunctive normal form)?
含n个命题变量的主合取范式是零个或多个极大项(max-term)的合取
- 含n个命题变量的极大项是n个文字的析取
- 每个文字对应不同的命题变量
- 每个文字是这个命题变量本身或者是它的否定
-
分情况证明:p ∨ q, p → r, q → r ⟹ r
-
构造性二难推理:p ∨ q, p → r, q → s ⟹ r ∨ s
-
破坏性二难推理:¬r ∨ ¬s, p → r, q → s ⟹ ¬p ∨ ¬q