manbetx官方网站一个公式的主合取范式

当前位置:manbetx官网登录 > manbetx官方网站 > manbetx官方网站一个公式的主合取范式
作者: manbetx官网登录|来源: http://www.peoplegynews.com|栏目:manbetx官方网站

文章关键词:manbetx官网登录,对偶原理离散数学

  从上节可看到命题公式的最小联结词组为{┓, ∨}或{┓, ∧},但实际上为了使用方便,命题公式常常同时包含{┓, ∨,∧}.我们从表1-4.8可以看到命题定律除对9外都是成对出现的,其不同的只是∨和∧互换.我们把这样的公式称作具有对偶规律.

  定义1-7.1 在给定的命题公式中,将联结词∨换成∧,将∧换成∨,若有特殊变元f和t亦相互取代,所得公式a*称为a的对偶.

  解 因为p↑qû┓(p∧q),故p↑q的对偶式为┓(p∨q),即p↓q。同理p↓q的对偶式是p↑q。

  定理1-7.1 设a和a*是对偶式,p1,p2,……,pn是出现在a和a*中的原子变元,则

  ┓a*(┓p1,┓p2,……,┓pn)ûa(┓p1,┓p2,……,┓pn)

  证明由于a*(s,w,r)是┓s∧(┓w∨r),则a*(┓s,┓w,┓r)是s∧(w∨┓r)。但 a(s,w,r)是┓s∨(┓w∧r),故┓a(s,w,r)是┓(┓s∨(┓w∧r)ûs∧(w∨┓r)。

  定理1-7.2 设 p1,p2,……,pn是出现在公式a和b中的所有原子变元,如果aûb,则a*ûb*。

  a(┓p1,┓p2,……,┓pn)«b(┓p1,┓p2,……,┓pn)也是一个重言式。即

  例题4如果a(p,q,r)是p↑(q∧┓(r↓p)),求它的对偶式a*(p,q,r)。并求它与a及a*等价,但又包含联结词“∧”“∨”及“┓”的公式。

  从真值表和对偶律等可以简化或推证一些命题公式。同一命题公式可以有各种相互等价的表达形式,为了把命题公式规范化,下面讨论命题公式的范式问题。

  定义1-7.2 一个命题公式称为合取范式,当且仅当它具有型式:a1∧a2∧……∧an,(n=1)

  定义1-7.3 一个命题公式称为析取范式,当且仅当它具有型式:a1∨a2∨……∨an,(n=1)

  故┓(p∨q)«(p∧q)û(┓(p∨q)∧(p∧q))∨((p∨q)∧┓(p∧q))

  û(┓p∧┓q∧p∧q)∨(p∨┓p)∧(q∨┓p)∨ (p∧┓q)∨(q∧┓q)

  一个命题公式的合取范式或析取范式并不是唯一的。例如p∨( q∧r)是一个析取范式,但它亦可以写成

  为了使任意一个命题公式,化成唯一的等价命题的标准形式,下面介绍主范式的有关概念。

  定义1-7.4n个命题变元的合取式,称作布尔合取或小项,其中每个变元与它的否定不能同时存在,但两者必须出现且仅出现一次。

  例如,两个命题变元p和q,其小项为:p∧q,p∧┓q,┓p∧q,┓p∧┓q。

  三个命题变元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∧┓q∧┓r。

  从这个真值表中可以看到,没有两个小项是等价的,且每个小项都只对应p和q的一组真值指派,使得该小项的真值为t。

  出一种编码,使n个变元的小项可以很快地写出来。现按三个变元为例说明如下。

  2n-1ûti=0定义1-7.5 对于给定的命题公式,如果有一个等价公式,它仅由小项的析取所组成,则该等价式称作原式的主析取范式。一个公式的主析取范式可用构成真值表的方法予以写出。定理1-7.3 在真值表中,一个公式的真值为t的指派所对应的小项的析取,即为此公式的主析取范式。证明设给定公式为a,其真值为t的指派所对应的小项为m1’,m2’,…… m

  首先对a为t的某一指派,其对应的小项为mi’,则因为mi’为t,而m1‘,m2’,…… mi-1‘,mi+1

  ‘……,mk‘均为f,故b为t。其次,对a为f的某一指派,其对应的小项不包含在b中,即m1‘,m2’,…… mk‘均为f,故b为f。因此aû

  b。例题6 给定p→q,p∨q和┓(p∧q),求这些公式的主析取范式。解三公式的线所示。故p→qû(┓p∧\┓q)∨(┓p∧q)∨(p∧q)

  û(┓p∧q)∨(p∧┓q)∨(p∧q)┓(p∧q)û(┓p∧┓q)∨(┓p∧q)∨(p∧┓q)

  ( p∧q∧(r∧┓r))∨(┓p∧r∧(q∨┓q))∨(q∧r∧(p∨┓p))û( p∧q∧r)∨(p∧q∧┓r)∨(┓p∧q∧r)∨(┓p∧q∧r)

  由上述各例我们看到,一个命题公式的主析取范式,可由两种方法构成。一是由公式的真值表得出,另一是由基本等价公式推出。其推演步骤可归纳为:(1)化归为析取范式。

  (2)除去析取范式中所有永假的析取项。(3)将析取式中重复出现的合取项和相同的变元合并。

  (4)对合取项补入没有出项的命题变元,即添加(p∨┓p)式,然后,应用分配律展开公式。

  对于一个命题公式的主析取范式,如将其命题变元的个数及出现次序固定后,则此公式的主析取范式便是唯一的,因此,给定任两个公式,由主析取范式可以方便地看出两个公式是否等价。manbetx官方网站与主析取范式类似的是主合取范式。

  个明天变元的析取式,称作布尔析取或大项,其中每个变元与他的否定不能同时出现,但两者必须出现且仅出现一次。例如:

  m111=┓ p∨┓q∨┓r大项有如下性质:(1)每一个大项当其真值指派与编码相同时,其线种真值指派情况下均为t。(2)任意两个不同大项的析取式永真。mi∨m

  1∧…∧m2n-1fi=0定义1-7.7 对于给定的命题公式a,如果有一个等价公式a’,它仅由大项的合取所组成,则称a’为a的主合取范式(majorconjunctivenormalform)。一个公式主合取范式可以构成真值表的方法写出。

  定理1-7.4在真值表中,一个公式的真值为f的指派所对应的大项的合取,即为次公式的主合取范式。

  证法与定理1-7.3相同。例题10 利用真值表技术求(p∧q)∨(┓p∧r)的主合取范式与主析取范式。

  (┓p∨q∨┓r)∧(┓p∨q∨r)∧(p∨┓q∨r)∧(p∨q∨r)主析取范式为:

  一个公式的主合取范式,亦可用基本等价式推出,其推演步骤为:(1)化归为合取范式。

  (q∨┓p)∨(r∧┓r))∧(p∨r∨(q∧┓q))∧(q∨r∨(p∧┓p))

  û(q∨┓p∨r)∧(q∨ ┓p∨┓r)∧(p∨r∨q)∧(p∨r∨┓q)∧(q∨r∨p)∧(q∨r∨┓p)

  (┓p∨q∨r)∧(┓p∨q∨r)∧(p∨┓q∨r)∧(p∨q∨r)为了使主析取范式和主合去范式表达简洁,我们今后用∑i,j,k,既表示mi∨mj∨m

  k;用ii表示大项的合取,iii,j,k表示mi∧mj∧mk,由这样的约定,例题10可以表达为:(p∧q)∨(┓p∧r)=m001∨m

  100∧m101=ii0,2,4,5可以证明,如果命题公式p的主析取范式为:

网友评论

我的2016年度评论盘点
还没有评论,快来抢沙发吧!