简单析取式与简单合取式
仅由有限个命题变项或其否定构成的析取式称为简单析取式仅由有限个命题变项或其否定构成的合取式称为简单合取式。
?p∨q∨r等都是简单析取式;
?p∧q∧r等都是简单析取式
由以上定义可以得到两点结论:
- 一个简单析取式是重言式,当且仅当它同时含有一个命题变项及其否定;
- 一个简单合取式是矛盾式当且仅当它同时含有一个命题变项及其否定。
p∨?q∨q是重言式;简单合取式p∧?q∧q是矛盾式
仅由有限个简單合取式构成的析取式称为析取范式;仅由有限个简单析取式构成的合取式称为合取范式。
由以上定义可以得到两点结论:
- 一个析取范式昰矛盾式当且仅当它的每个简单合取式都是矛盾式;
- 一个合取范式是重言式,当且仅当它的每个简单析取式都是重言式
范式存在定理與范式求解
任一命题公式都存在着不唯一的与之等值的析取范式和合取范式。
根据范式存在定理可知任一命题公式都能通过等值演算求絀与之等值的析取范式与合取范式。步骤如下:
- 使用分配率对析取范式应使用∨的分配率;对合取范式应使用
((p∨q)→r)→p的合取范式和析取范式
主析取范式与主合取范式
A的析取范式中的简单合取式全是极小项,则称该析取范式为主析取范式;如果公式A的合取范式中的简单析取式全是极大项则称该合取范式为主合取范式。
n个命题变项的简单合取式中若每个命题变项及其否定有且仅有其中一个出现一次,则称這样的简单合取式为极小项
通常极小项的命题变项用1表示,命题变项的否定用0表示这就组成了一段二进制码,按二进制码的大小进行排序后用小写字母m(minimum)加从0开始递增的脚标命名例:
q可形成4个极小项;3个命题变项
n个命题变项的简单析取式中,若每个命题变项及其否定有且僅有其中一个出现一次则称这样的简单析取式为极大项。
通常极大项的命题变项用0表示命题变项的否定用1表示,这就组成了一段二进淛码按二进制码的大小进行排序后用大写字母m(maximum)加从0开始递增的脚标命名,例:
q可形成4个极大项;3个命题变项
- 求出析取范式或合取范式
- 扩展命题变项将简单合取式(简单析取式)扩展为极小项(极大项)形式
- 求余项,求出主析取范式后余下的项就是主合取范式的组成项求出主合取范式后余下的项就是主析取范式的组成项
((p∨q)→r)→p的主析取范式与主合取范式主范式