主析取范式的求法

《主析取范式的求法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章命题逻辑第七讲定义对于给定的命题公式，如果有一个等价公式仅由小项的析取所组成，则该等价式称为原式的主析取范式。内容回顾小项定义n个命题变元的合取式，称为布尔合取或小项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。每个小项可用n位二进制编码表示。以变元自身出现的用1表示，以其否定出现的用0表示：小项的性质如下：（1）每一个小项当其真值指派与编码相同时，其真值为1，其余的2n－1种均为0;（2）任意两个不同小项的合取式永假：（3）全体小项的析取式永为真，记为：主析取范式的求法

2、真值表法等值演算法趣味推理题A、B、C三人去餐馆吃饭，他们每人要的不是火腿就是猪排。（1）如果A要的是火腿，那么B要的就是猪排。（2）A或C要的是火腿，但是不会两人都要火腿。（3）B和C不会两人都要猪排。谁昨天要的是火腿，今天要的是猪排？只有B才能昨天要火腿，今天要猪排。1．5．4主合取范式定义1-n个命题变元的析取式，称为布尔析取或极大项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。例如，2个命题变元p和Q的大项为：3个命题变元p、Q、R的大项为：n个命题变元共有2n

3、个大项，每个大项可表示为n位二进制编码，以变元自身出现的用0表示，以变元的否定出现的用1表示；且对应十进制编码。这一点与小项的表示刚好相反。若n=2，则有若n=3，则有:大项的性质如下：(1)每一个大项当其真值指派与编码相同时，其真值为0，其余的2n－1种赋值均为1;(2)任意两个不同大项的析取式永真：(3)全体大项的合取式必为假，记为：定义1-对于给定的命题公式，如果有一个等价公式仅由极大项的合取所组成，则该等价式称为原式的主合取范式。定理1-（主合取范式存在惟一定理）　任何命题公式的主合取范式

4、一定存在，并且惟一。由真值表方法可知：一个公式的真值为0的真值指派所对应的大项的合取，即为此公式的主合取范式。例1-用真值表方法求的主合取范式解:公式的真值表如下PQRP→Q¬R(p→Q)→¬R000001010011100101110111111100111010101010101110所以公式的主合取范式为:用等值演算方法构成主合取范式的主要步骤如下：（1）将原命题公式化归为合取范式；（2）除去合取范式中所有永真的合取项；（3）合并相同的析取项和相同的变元；（4）对合取项补入没有出现的命题变元

5、，即添加如(p∧┐p)的式子，再按分配律进行演算；（5）将大项按下标由小到大的顺序排列。例1-用等值演算方法求的主合取范式。解：【说明】(1)主析取范式的析取项为小项，用小m加下标表示。如m010，其中0表示对应的命题变元的否定出现在析取项中,1表示对应的命题变元出现在析取项中。(2)主合取范式的合取项为大项,用大M加下标表示,如M010,其中0表示对应的命题变元出现在合取项中,1表示对应命题变元的否定出现在合取项中。(3)在真值表中,一个公式的主析取范式由其真值为1的真值指派所在对应的小项的析取

6、组成。(4)在真值表中,一个公式的主合取范式由其真值为0的真值指派所对应的大项的合取所组成。极小项与极大项由p,q两个命题变项形成的极小项与极大项公式成真赋值名称公式成假赋值名称pqpqpqpq00011011m0m1m2m3pqpqpqpq00011011M0M1M2M3极小项极大项由p,q,r三个命题变项形成的极小项与极大项极小项极大项公式成真赋值名称公式成假赋值名称pqrpqrpqrpqrpqrpqrpqrp

7、qr000001010011100101110111m0m1m2m3m4m5m6m7pqrpqrpqrpqrpqrpqrpqrpqr000001010011100101110111M0M1M2M3M4M5M6M71.6蕴含公式如果双条件命题A↔B为重言式，则A⇔B。而条件命题A→B是不对称的，如果A→B为真，B不一定能推出A。那么A和B究竟存在什么关系呢？1．6．1蕴含公式定义1-26设A，B是命题公式,若A→B是重言式,则称A→B是蕴含

8、重言式，记为A⇒B，读作“A永真蕴含B”。简称A蕴含B即A⇒BiffA→B⇔1注意:→与⇒是意义不同的符号。证明：所以P∧(p→Q)⇒Q下面介绍几种证明A永真蕴含B的方法。方法一：用真值表法或等价变换(推导)法证明A→B⇔1。例1-24证明。PQP→QP∧(P→Q)(P∧(P→Q))→Q00011011110100011111方法二：通过分析的方法来证明一个条件命题是蕴含式。由于原命题等于其逆反命题，即A→B⇔┐B→┐A，所以用分析法证明A⇒B，有如下两种方法:(1)假设前件A为真