优范式的基本思想是把一个公式的合(析)取范式进一步标准化,从而使每一个表达式都有一个唯一的标准形式,不同的表达式有不同的标准形式.特别使互为等值的命题形式具有相同的标准形式,不等值的命题形式的标准形式不同.由于我们讨论的范式有两种,因此对应地优范式也有两种:优合取范式和优析取范式.在合(析)取范式的基础上,求优合(析)取范式的方法,类似于中学里多项式函数的合并同类项.
定义3.5 我们把满足以下条件的合(析)取范式称为优合(析)取范式:
(1)如果某一命题变项在范式里出现,那么它要在每一简单析(合)取里出现;
(2)没有常真(假)的简单析(合)取;
(3)在简单析(合)取里,没有相同的支命题;
(4)对于命题变项及其否定按下列顺序排列
[p,⇁p,q,⇁q,r,⇁r,s,⇁s,p1,⇁p1,…];
在范式里,命题变项和简单析(合)取都照上面的顺序按字母顺序排列;
(5)没有相同的简单析(合)取.
例3.3 (1)根据定义3.5,我们可以断定:真值形式
(p∨q∨r)∧(p∨q∨⇁r)∧(p∨⇁q∨r)
是一个优合取范式;
(2)根据定义3.5,我们可以断定:真值形式
(p∧q∧r)∨(p∧q∧⇁r)∨(p∧⇁q∧r)
是一个优析取范式;
(3)根据定义3.5,我们可以断定:下面的真值形式
(p∨⇁q)∧q,(p∨q∨⇁q)∧(p∨⇁r),
(p∨⇁q∨⇁q)∧(⇁p∨q),(⇁p∨q)∧(q∨⇁p),
都不是优合取范式.
(4)根据定义3.5,我们可以断定:下面的真值形式
(p∧⇁q)∨q,(p∧q∧⇁q)∨(p∧⇁r),
(p∧⇁q∧⇁q)∨(⇁p∧q),(⇁p∧q)∨(q∧⇁p),
都不是优析取范式.
根据优范式的定义,从一个给定的范式出发,求其优范式的步骤如下:
第一步:展开.
把不包含某一命题变项的简单合取或简单析取,置换为含有这一命题变项的一些简单合取或简单析取.展开的规则是:
在简单合取α中引入命题变项π(即π的取值为p,q,r等),将α换以α∧(π∨⇁π);在简单析取α中引入命题变项π,将α换以α∨(π∧⇁π).
第二步:消去.
从第一步所得的合取范式或析取范式中消去重言的简单析取或不可满足的简单合取,消去简单析取或简单合取中重复的支命题,消去重复的简单析取或简单合取.消去规则是:
①α∨α换以α,α∧α换以α;
②α∨(β∧⇁β)换以α,α∨(β∧⇁β∧γ)换以α;
③α∧(β∨⇁β)换以α,α∧(β∨⇁β∨γ)换以α.(www.daowen.com)
第三步:排列.
按顺序排列各简单析取或简单合取中的命题变项及其否定,并按照特定的字母顺序排列各简单析取或简单合取.在按照特定的字母顺序排列时,可使用交换律和结合律.
例3.4 在例3.2中,p↔p∧q的析取范式和合取范式分别为:
(p∧p∧q)∨(⇁p∧⇁p)∨(⇁p∧⇁q),
和求它的优析取范式如下:
(⇁p∨p)∧(⇁p∨q)∧(p∨⇁p∨⇁q).
(1)在简单合取p∧p∧q和⇁p∧⇁p中,消去重复的支命题,得
(p∧q)∨(⇁p)∨(⇁p∧⇁q).
(2)展开,得
(p∧q)∨(⇁p∧(q∨⇁q))∨(⇁p∧⇁q),
(p∧q)∨((⇁p∧q)∨(⇁p∧⇁q))∨(⇁p∧⇁q).
(3)消去重复的简单合取⇁p∧⇁q,得
(p∧q)∨(⇁p∧q)∨(⇁p∧⇁q).
此式为原式的优析取范式.
求它的优合取范式如下:
消去重言的简单析取,得:
⇁p∨q.
此式为原式的优合取范式.
例3.5 求p∧(p→q)→r的优合取范式.
解 消去→,得:⇁(p∧(⇁p∨q))∨r.
内移⇁,得:⇁p∨⇁(⇁p∨q)∨r.
内移⇁,得:⇁p∨(⇁⇁p∧⇁q)∨r.
消去⇁⇁,得:⇁p∨(p∧⇁q)∨r.
展开,得:((⇁p∨p)∧(⇁p∨⇁q))∨r.
分配,得:(⇁p∨p∨r)∧(⇁p∨⇁q∨r).
消去重言式得:⇁p∨⇁q∨r,此式为原式的优合取范式.
优范式的特征在于它具有唯一性.两个含有相同命题变项的等值式,它们的优合取范式或优析取范式是完全相同的.特别地,对于有n个命题变项的公式,它应有2n个不同的真值组合.每一组合都对应一个简单析取或简单合取.前面,用写真法写出的公式就是优析取范式.如果一个优析取范式中有2n个简单合取,那么它是一个重言式;否则,如果优析取范式中有0个简单合取支(即优析取范式不存在),那么它是一个不可满足式.用写假法写出的公式经过适当排列后,是优合取范式.如果优合取范式中有2n个简单析取支,那么它是一个不可满足式;否则,如果优合取范式中有0个简单析取支(即优合取范式不存在),那么它是一个重言式.
对于优范式,我们有下面的结论:
定理3.2(优范式的存在唯一定理) 每一个真值形式都存在唯一的一个优析取范式和唯一的一个优合取范式.
同定理3.1一样,我们略去定理3.2的证明,有兴趣的读者可参阅文献[19].
免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。