一个多项式的标准形为:
f(x)=an x n+an-1 x n-1+…+a1 x+a0.
这里ai(i=0,1,…,n)是实数,并且an≠0.这样一来,求f(x)=0根的问题,就只需要考虑x的各项次幂的系数.
另外,前面我们还曾把自然数按是否能被3整除进行分类.于是,
其中:m~n当且仅当m-n≡mod(3),m,n∈N.这里0,1和2分别是余数为0,1和2数类的代表元,而且是最小的,即最简单的.这样一来,要讨论形如3n这类数所具有的性质,只需讨论0所具有的性质即可.要讨论3n这类数与3n+1这类数之间的差异,只需讨论0和1之间的差异即可.
这一节要讨论的范式,就是要在每一类真值函项中,选出一个真值形式作代表元,使得作为代表元的真值形式能显示出这一类真值函项所具有的特征.为了便于比较不同类真值形式的差异,还要求:每一类真值函项的代表元具有统一的形式.因此,范式就是一种形式上比较规范的或比较标准的真值形式.
下面我们将要介绍两种范式:合取范式和析取范式.其实,范式是一种在形式上有一定规律的公式,因而它具有一些形式方面的特征.凭借这种特征,我们就能确定一个真值形式是否重言式.范式的作用还有很多,我们将在本节稍后再详细讨论.
1.合取范式和析取范式
定义3.1 由命题变项或命题变项的否定用析取词联结而成的析取式称为简单析取.
如:⇁p∨q,q∨r,p∨⇁q∨r,p∨⇁q∨r∨⇁r,它们都是简单析取.
定义3.2 由命题变项或命题变项的否定用合取词联结而成的合取式称为简单合取.
如:p∧q∧r,p∧⇁q∧⇁r,p∧⇁p∧q∧r,它们都是简单合取.
下面是两个显然的事实.
事实1:一个简单析取是重言式当且仅当有一个命题变项,它和它的否定都在该简单析取中出现.
事实2:一个简单合取是不可满足的当且仅当有一个命题变项,它和它的否定都在该简单合取中出现.
由此可以断定:p∨⇁q∨r∨⇁r是一个重言式,而⇁p∨q,q∨r和p∨⇁q∨r都不是重言式,p∧⇁p∧q∧r是一个不可满足式.p∧q∧r和p∧⇁q∧⇁r是可满足式.
定义3.3 由简单析取经合取词联结而成的真值形式称为合取范式.
一般地,合取范式α具有以下标准形式:
α1∧α2∧…∧αn,
其中αi(1≤i≤n)都是简单析取.
如:(p∨⇁q)∧(⇁p∨q)∧(q∨r)
和 (p∨q∨r)∧(p∨⇁q∨r)∧(p∨⇁q∨⇁r)
都是合取范式.特别地,p∨⇁q也是合取范式.它是在合取范式α的标准形中,n=1的情况.
容易看出:一个合取范式是重言式,当且仅当,它的每一个简单析取αi(1≤i≤n)均是重言式,即每个简单析取αi中都有某个命题变项及其否定在其中出现.如:
(p∨⇁p∨q)∧(p∨q∨⇁q)∧(p∨r∨⇁r)
是一个重言式.
定义3.4 由简单合取经析取词联结而成的真值形式称为析取范式.
一般地,析取范式α具有如下形式:
α1∨α2∨…∨αn,
其中αi(1≤i≤n)都是简单合取.
如:(p∧⇁q)∨(⇁p∧q)∨(q∧r)
和 (p∧q∧r)∨(p∧⇁q∧r)∨(p∧⇁q∧⇁r)
都是析取范式.特别地,p∧⇁q也是析取范式.它是在析取范式α的标准形中,n=1的情况.
容易看出:一个析取范式是不可满足式,当且仅当,它的每一简单合取αi(1≤i≤n)均是不可满足式,即每个简单合取αi中有某个命题变项及其否定在其中出现.如:
(p∧⇁p∧q)∨(p∧q∧⇁q)∨(p∧r∧⇁r)
是一个不可满足式.
从定义3.3和定义3.4可知,在合取范式和析取范式中均不包含蕴涵词“→”和等值词“↔”,否定词“⇁”只涉及命题变项本身.
2.范式的存在问题
是否每一个真值形式都有与之等值的合取范式和析取范式呢?我们有下面的结论.(www.daowen.com)
定理3.1 (范式存在定理) 每一真值形式都有一个与之等值的合取范式和析取范式.即:对每个真值形式α,都存在合取范式β和析取范式γ,使得α↔β并且α↔γ.(因此称β为α的合取范式,γ为α的析取范式)
本书略去这个定理的证明(有兴趣的读者可参阅文献[19]),只通过几个具体的例子说明如何从一个给定的公式α,去求它的合取范式和析取范式.
3.求范式的步骤
第一步,消去→和↔.
①根据2.2.5节中重言等值式(1),用⇁α∨β置换α→β,消去→;
②根据2.2.5节中重言等值式(4),用(⇁α∨β)∧(α∨⇁β)置换α↔β,消去↔求合取范式;或根据2.2.5节中重言等值式(5),用(α∧β)∨(⇁α∧⇁β)置换α↔β,消去↔求析取范式.
第二步,内移或消去⇁.
①根据2.2.5节中重言等值式(14),用α置换⇁⇁α,消去⇁⇁;
②根据2.2.5节中重言等值式(12),用⇁α∧⇁β置换⇁(α∨β);或根据2.2.5节中重言等值式(13),用⇁α∨⇁β置换⇁(α∧β),使⇁不断深入,直至置于命题变项之前.
第三步,根据2.2.5节中重言等值式(8)和(9)(即析取和合取的结合律),互换析取和合取的各项顺序,还可以略去结合的括号.
第四步,根据2.2.5节中重言等值式(11)(即析取对合取的分配律),用(α∨β)∧(α∨γ)置换α∨(β∧γ)求合取范式;根据2.2.5节中重言等值式(10)(即合取对析取的分配律),用(α∧β)∨(α∧γ)置换α∧(β∨γ)求析取范式.
例3.1 求(p→(q→r))→(p∧q→r)的合取范式和析取范式.
解 (1)消去→,得
⇁(⇁p∨(⇁q∨r))∨(⇁(p∧q)∨r).
(2)将⇁内移,得
(⇁⇁p∧⇁(⇁q∨r))∨(⇁p∨⇁q∨r),
(⇁⇁p∧⇁⇁q∧⇁r)∨(⇁p∨⇁q∨r),
消去⇁⇁,得
(p∧q∧⇁r)∨(⇁p∨⇁q∨r).
即(p∧q∧⇁r)∨⇁p∨⇁q∨r为所求析取范式.
用∨对∧的分配律,得
(p∨⇁p∨⇁q∨r)∧(q∨⇁p∨⇁q∨r)∧(⇁r∨⇁p∨⇁q∨r)
该式即为所求的合取范式.
例3.2 求p↔p∧q的合取范式和析取范式.
解 消去↔,得
(⇁p∨(p∧q))∧(p∨⇁(p∧q)).
内移⇁,得
对(*),用∨对∧的分配律,得
((⇁p∨p)∧(⇁p∨q))∧(p∨⇁p∨⇁q),
即:(⇁p∨p)∧(⇁p∨q)∧(p∨⇁p∨⇁q)为所求的合取范式.
又在原式中,消去↔,得
(p∧p∧q)∨(⇁p∧⇁(p∧q)).
内移⇁,得
(p∧p∧q)∨(⇁p∧(⇁p∨⇁q)).
用∧对∨的分配律,得
(p∧p∧q)∨((⇁p∧⇁p)∨(⇁p∧⇁q)),
即(p∧p∧q)∨(⇁p∧⇁p)∨(⇁p∧⇁q)为所求的析取范式.
另外,容易证明:⇁p∨q与p↔p∧q重言等值,所以,⇁p∨q也是原式的一个合取范式.这样一来,用前面的步骤,求一个公式的范式,其结果不是唯一的.为了使结果具有唯一性,下面将介绍优范式.
免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。