第1章 命题逻辑_20.ppt

1.5范式1.5.1析取范式与合取范式定义1.5.1由一些命题变元或其否定构成的析取式称为基本和，也叫简单析取式。约定单个变元或其否定是基本和。,例如，pq、pq、pq、q、p、q都是基本和。,定义1.5.2由一些命题变元或其否定构成的合取式称为基本积，也叫简单合取式。约定单个变元或其否定是基本积。例如，pq、pq、pq、p、q、p都是基本积。,定义1.5.3由基本和的合取构成的公式叫做合取范式。约定单个基本和是合取范式。,定义1.5.4由基本积的析取构成的公式叫做析取范式。约定单个基本积是析取范式。,1)基本和和基本积既是析取范式，又是合取范式。,2)析取范式和合取范式都仅含联结词,。,利用双重否定律消去否定联结词“”或利用德摩根律将否定联结词“”移到各命题变元前(内移)。,利用分配律，结合律将公式归约为合取范式和析取范式。,任何命题公式都可以化成与其等价的析取范式或合取范式。求析取范式和合取范式的步骤如下：,消去联结词“”和“”,【例1.21】求命题公式(pq)p的合取范式和析取范式。,解：求合取范式(pq)p,(pq)p)(p(pq)(消去),(pq)p)(p(pq)(消去),(pq)p)(p(pq)(内移),(pp)(qp)(ppq)(分配律),1(qp)(1q)(排中律),1(qp)1(零律),(qp)(同一律，合取范式),合取范式,求析取范式(pq)p,(pq)p)(pq)p)(消去),(pq)p)(pq)p)(内移),p(pqp)(吸收律),p(ppq)(交换律),p(pq)(幂等律，析取范式),由此例可以看出，命题公式的析取范式也不惟一。,析取范式,析取范式,AB(AB)(AB),1.5.2主析取范式由于析取范式和合取范式不惟一，所以使用起来很不方便。为此，引入主析取范式和主合取范式的概念。当命题变元的顺序约定以后，主析取范式和主合取范式是惟一的。,析取范式和合取范式的基本成分是基本积和基本和，而主析取范式和主合取范式的基本成分是极小项和极大项，它们分别是特殊的基本积和基本和。,p，q的极小项为：pq，pq，pq，pq,定义1.5.5在基本积中，每个变元及其否定不同时存在，但两者之一必须出现且仅出现一次，这样的基本积叫做布尔合取也叫小项或极小项。,表1.12是两个变元p和q的极小项的真值表。极小项有下列的性质：,两个命题变元的极小项共4(=22)个,三个命题变元的极小项共8(=23)个,。一般地说，n个命题变元共有2n个极小项。,表1.13,每个极小项只有一个成真赋值，且各极小项的成真赋值互不相同。极小项和它的成真赋值构成了一一对应的关系。可用成真赋值为极小项进行编码，并把编码作为m的下标来表示该极小项，叫做该极小项的名称。,两个命题变元的极小项、成真赋值和名称如表1.13所示。,三个命题变元的极小项，成真赋值和名称如表1.14所示。,从表1.13和表1.14中可以看出，极小项与其成真赋值的对应关系为：变元对应1，而变元的否定对应0。,任意两个不同的极小项的合取式为永假式。例如：m001m100(pqr)(pqr)pqrpqr0,定义1.5.6对于给定的命题公式，如果有一个它的等价公式，仅由极小项的析取组成，称该公式为原公式的主析取范式。,m0m11,任何命题公式都存在着与之等价的主析取范式。一个命题公式的主析取范式可以由以下两种方法求得：等价演算法：即用基本等价公式推出。,全体极小项的析取式为永真式。记为：,用等价演算法求主析取范式的步骤如下：,例1.22用等价演算法求(pq)(pr)(qr)的主析取范式。解：(pq)(pr)(qr),(pq(rr)(pr(qq)(qr(pp),(pqr)(pqr)(pqr)(pqr)(pqr)(pqr),(pqr)(pqr)(pqr)(pqr),m111m110m011m001,m7m6m3m11，3，6，7,在基本积中补入没有出现的命题变元，即添加(xx)，再用分配律展开，最后合并相同的极小项。,化归为析取范式。,除去析取范式中所有永假的基本积。,在基本积中，将重复出现的合取项和相同变元合并。,真值表法：即用真值表求主析取范式。用真值表求主析取范式的步骤如下：构造命题公式的真值表。找出公式的成真赋值对应的极小项。这些极小项的析取就是此公式的主析取范式。,【例1.24】用真值表法，求(pq)r的主析取范式。解：表1.15是(pq)r的真值表，公式的成真赋值对应的极小项为：pqr(成真赋值为001)pqr(成真赋值为011)pqr(成真赋值为100)pqr(成真赋值为101)pqr(成真赋值为111)(pq)r的主析取范式为：,(pqr)(pqr)(pqr)(pqr)(pqr)m001m011m100m101m111m1m3m4m5m71，3，4，5，7,因而主析取范式含2n(n为公式中命题变元的个数)个极小项。,矛盾式无成真赋值，,可满足式的主析取范式中极小项的个数一定小于等于2n。,因而其主析取范式不含任何极小项，将矛盾式的主析取范式记为0。,重言式无成假赋值，,矛盾式、重言式、可满足式主析取范式的性质,1.5.3主合取范式定义1.5.7在基本和中，每个变元及其否定不同时存在，但两者之一必须出现且仅出现一次，这样的基本和叫作布尔析取，也叫大项或极大项。,两个变元p，q构成的极大项为：pq，pq，pq，pq三个命题变元p，q，r构成的极大项为：pqr，pqr，pqr，pqr，pqr，pqr，pqr，pqr,两个命题变元的极大项共4(=22)个,三个命题变元的极大项共8(=23)个,。一般地说，n个变元共有2n个极大项。,例如，两个变元p，q的极大项pq，它的成假赋值是11，表示为M11，把11理解为2进制数，它的10进制表示为3，所以M11又表示为M3。,两个命题变元的极大项，成假赋值及名称见表1.16，三个命题变元的极大项，成假赋值及名称见表1.17。,极大项有下列三个性质：每个极大项只有一个成假赋值，极大项不同，成假赋值也不同。极大项和它的成假赋值构成了一一对应的关系。故可用成假赋值为该极大项进行编码，并把编码作为M的下标来表示该极大项，叫做极大项的名称。,从表1.16和表1.17中可以看出，极大项与成假赋值的对应关系为：变元对应0，而变元的否定对应1。,全体极大项的合取式为永假式。记为：,永真式,任意两个不同的极大项的析取式为,定义1.5.8对于给定的命题公式，如果有一个它的等价公式，仅由极大项的合取组成，则该等价式称为原公式的主合取范式。,等价演算法：即用基本等价公式推出。其演算步骤如下：化归为合取范式。除去所有永真的基本和。在基本和中合并重复出现的析取项和相同的变元。在基本和中补入没有出现的命题变元。即增加(xx)，然后，应用分配律展开公式，最后合并相同的极大项。,任何命题公式都存在着与之等价的主合取范式。主合取范式也可以由以下两种方法求得。,【例1.25】用等价演算法求(pq)r的主合取范式。解：(pq)r,(pq)r(pq)r(pr)(qr),(pr(qq)(qr(pp),(prq)(prq)(pqr)(pqr),(pqr)(pqr)(pqr),M000M010M110M0M2M60，2，6,真值表法：用真值表求主合取范式。用真值表求主合取范式的步骤如下：构造命题公式的真值表。找出公式的成假赋值对应的极大项。这些极大项的合取就是此公式的主合取范式。,【例1.26】用真值表法求(pq)r的主合取范式。,解：(pq)r的真值表是表1.15。公式的成假赋值对应的大项为：pqr(成假赋值为000)pqr(成假赋值为010),pqr(成假赋值为110)主合取范式为：(pqr)(pqr)(pqr)M000M010M110M0M2M60，2，6,矛盾式无成真赋值，因而矛盾式的主合取范式含2n(n为公式中命题变元的个数)个极大项。而重言式无成假赋值，因而主合取范式不含任何极大项。将重言式的主合取范式记为1。至于可满足式，它的主合取范式中极