主析取范式的求法课件

第一章命题逻辑第七讲定义对于给定的命题公式，如果有一个等价公式仅由小项的析取所组成，则该等价式称为原式的主析取范式。内容回顾小项定义n个命题变元的合取式，称为布尔合取或小项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。

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

由真值表方法可知：一个公式的真值为0的真值指派所对应的大项的合取，即为此公式的主合取范式。例1-用真值表方法求的主合取范式解:公式的真值表如下PQRP→Q

¬R(p→Q)→¬R000001010011100101110111111100111010101010101110所以公式的主合取范式为:用等值演算方法构成主合取范式的主要步骤如下：（1）将原命题公式化归为合取范式；（2）除去合取范式中所有永真的合取项；（3）合并相同的析取项和相同的变元；（4）对合取项补入没有出现的命题变元，即添加如(p∧┐p)的式子，再按分配律进行演算；（5）将大项按下标由小到大的顺序排列。例1-用等值演算方法求的主合取范式。解：极小项与极大项由p,q两个命题变项形成的极小项与极大项

公式

成真赋值名称

公式

成假赋值名称

p

qp

qp

qp

q00011011m0m1m2m3

p

q

p

q

p

q

p

q

00011011

M0M1M2M3

极小项

极大项

由p,q,r三个命题变项形成的极小项与极大项

极小项

极大项

公式

成真赋值名称

公式

成假赋值名称

pq

rpq

rpq

rpq

rpq

rpq

rpq

rpq

r000001010011100101110111m0m1m2m3m4m5m6m7p

q

r

p

q

r

p

q

r

p

q

r

p

q

r

p

q

r

p

q

r

p

q

r

000001010011100101110111M0M1M2M3M4M5M6M7

证明：所以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为真时,推出后件B也为真,则A⇒B;

(2)假设后件B为假时,推出前件A也为假,则A⇒B

。例1-26如果我认真学习，我的“离散数学”不会不及格，如果我不热衷于玩电子游戏，我将认真学习，但我的“离散数学”不及格。结论：我热衷于玩电子游戏。证明：设P：我认真学习。Q：我的“离散数学”及格。R：我热衷于玩电子游戏。常见的蕴含重言式析取三段论假言推论拒取式假言三段论二难推论化简式一附加式化简式二例1-27分析证明。证明：假设后件为0，则P为1，R为0。(a)若Q为1，则为0，所以为0；(b)若Q为0，则为0，所以为0。故此：成立。1.8推理理论逻辑学的主要任务是提出一套推理规则，按照公认的推理规则从前提集合中推导出一个结论来，这个推理过程称为演绎或形式证明。在一般的论证中，主要是根据实践经验。如果确认前提为真，并遵守恰当的推理规则，则可期望所得的结论也是真的。倘若认定前提是真的，从前提推导出结论的论证是遵守逻辑推理规则，且公认此结论是真实的，则这个论证称为合法论证。一般论证中必须特别注意论证的合法性。所谓合法是指前提和结论都符合客观实际情况，大家公认是真实的。即合情、合理、合法，令人信服。

在数理逻辑中情况稍有不同，它把注意力集中在推理规则的研究上，如果依据这些推理规则，从前提推导出来的任何结论都称为有效结论，这种论证称为有效论证。在确认论证有效性时，前提与结论的真实性不起任何作用，也就是说，在数理逻辑中，只关心论证的有效性，而不大关心论证的合法性。

前提：如果马会飞或羊吃草，则母鸡就会是飞鸟；如果母鸡是飞鸟，那么烤熟的鸭子还会跑；烤熟的鸭子不会跑。结论：羊不吃草。

利用真值表判别一个有效论证的方法：方法一：在真值表上，若前提H1,H2,H3,…Hn均为真的所有行，结论C也为真，则论证有效。方法二：在真值表上，若结论C为假的每一行，其前提

H1,H2,H3,…Hn中至少有一个为假，则论证有效。例1-28如果我认真学习，我的“离散数学”不会不及格，如果我不热衷于玩电子游戏，我将认真学习，但我的“离散数学”不及格。结论：我热衷于玩电子游戏。P:我认真学习，Q:我的“离散数学”及格，R:我热衷于玩电子游戏。符号化为：其真值表如下：解：判断法一：真值表中，只有第2行的前提都为1，其结论也为1，所以论证有效。判断法二：真值表中，第1、3、5、7行为0，每行的前提至少有一个为0，所以论证有效。PQR¬Rp→Q¬R→p¬QR000001010011100101110111101010101

111

0011

0

1

0111111

1

0011

00

0

1

01

01

01pqp→q﹁p﹁q00111011101000111100（二）构造证明法

(1)推理规则常用的推理规则有：P规则：在推导的任意一步都可以引入一个前提。T规则：如果公式S等价于或被重言蕴含在一个或多个前提或中间结果命题中，则推导中可以引入S。CP规则：如果能从R及一组前提推导出C，则可从这组前提推导出R→C。设前提若则

(2)推理定律

在推导过程除推理规则外,还需要推理定律,这些推理定律就是前面所讲的常用的蕴含式（用I表示）和命题定律（用E表示）。现在将蕴含式和命题定律再次显示如下。化简1