搜索

离散数学 第一章 命题逻辑 1-7 对偶与范式

gecimao 发表于 2019-07-12 17:14 | 查看: | 回复:

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

  (2) 利用德摩根定律将否定符号直接移到各个命题变元之前.

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

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

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

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

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

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

  此要证ab,即要证a与b在相应指派下具有相同真值。首先对a为t的某一指派,其对应的小项为mi,则因为mi为t,而m1,m2

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

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

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

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

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

  大项有如下性质:(1)每一个大项当其真值指派与编码相同时,其线种真值指派情况下均为t。(2)任意两个不同大项的析取式永线)全体大项的合取式永为假。 记为:2n-1ii mi=m0m

  (2)除去合取范式中所有永线)将合取式中重复出现的析取项和相同的变元合并。(4) 对析取项补入没有出现的命题变元,即添加(p p)式,然后,应用分配律展开公式。

本文链接:http://baumseelen.com/duiouchanshengqi/649.html
随机为您推荐歌词

联系我们 | 关于我们 | 网友投稿 | 版权声明 | 广告服务 | 站点统计 | 网站地图

版权声明:本站资源均来自互联网,如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

Copyright @ 2012-2013 织梦猫 版权所有  Powered by Dedecms 5.7
渝ICP备10013703号  

回顶部