07命题逻辑.ppt

第一章 命题逻辑第七讲第七讲 定义定义 对于给定的命题公式，如果有一个等价公式对于给定的命题公式，如果有一个等价公式仅由仅由小项的析取小项的析取所组成，则该等价式称为原式的所组成，则该等价式称为原式的主析主析取范式。取范式。内容回顾内容回顾小项小项 定义 n个命题变元的合取式，称为布尔合个命题变元的合取式，称为布尔合取或小项，其中每个变元与它的否定不能同时取或小项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。存在，但两者必须出现且仅出现一次。每个小项可用每个小项可用n位二进制编码表示。以位二进制编码表示。以变元变元自身出现自身出现的用的用1 表示，以其表示，以其否定否定出现的用出现的用0表示：表示：小项的性质如下：小项的性质如下：（1）每一个小项当其真值指派与）每一个小项当其真值指派与编码编码相同时，其真值为相同时，其真值为1，其余的，其余的2n1种均为种均为0;（2）任意两个不同小项的合取式永假：）任意两个不同小项的合取式永假：（3）全体小项的析取式永为真，记为：）全体小项的析取式永为真，记为：主析取范式的求法主析取范式的求法真值表法真值表法等值演算法等值演算法趣味推理题趣味推理题A、B、C三人去餐馆吃饭，他们每人要的不是火腿三人去餐馆吃饭，他们每人要的不是火腿就是猪排。就是猪排。（1）如果如果A要的是火腿，那么要的是火腿，那么B要的就是猪排。要的就是猪排。（2）A或或C要的是火腿，但是不会两人都要火腿。要的是火腿，但是不会两人都要火腿。（3）B和和C不会两人都要猪排。不会两人都要猪排。谁昨天要的是火腿，今天要的是猪排？谁昨天要的是火腿，今天要的是猪排？只有只有B才能昨天要火腿，今天要猪排。才能昨天要火腿，今天要猪排。154 主合取范式主合取范式定义定义1-n个命题变元的析取式，称为布尔析取或个命题变元的析取式，称为布尔析取或极大项极大项，其中每个变元与它的否定不能同时存在，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。，但两者必须出现且仅出现一次。例如，例如，2 2个命题变元个命题变元p和和q的大项为：的大项为：3 3个命题变元个命题变元P、Q、R的大项为：的大项为：n个命题变元共有个命题变元共有2n个大项，每个大项可表示为个大项，每个大项可表示为n位二进制编码，以位二进制编码，以变元自身变元自身出现的用出现的用0表示，以变元的表示，以变元的否否定定出现的用出现的用1 1表示；且对应十进制编码。这一点与表示；且对应十进制编码。这一点与极小项极小项的表示的表示刚好相反刚好相反。若若n=2，则有，则有若若n=3，则有，则有:大项的性质如下：大项的性质如下：(1)每一个大项当其真值指派与编码相同时，其真值为每一个大项当其真值指派与编码相同时，其真值为0，其余的其余的2n1种赋值均为种赋值均为1;(2)任意两个不同大项的任意两个不同大项的析取析取式永真：式永真：(3)全体全体大项的合取式必为假，记为：大项的合取式必为假，记为：mi与与Mi的关系：的关系：mi Mi,Mi mi 极小项与极大项极小项与极大项由由p,q两个命题变项形成的极小项与极大项两个命题变项形成的极小项与极大项 公式公式 成真赋值成真赋值名称名称 公式公式 成假赋值成假赋值名称名称 p q p q p q p q0 0 0 1 1 0 1 1 m0m1m2m3 p q p q p q p q 0 0 0 1 1 0 1 1 M0M1M2M3 极小项极小项 极大项极大项 由由p,q,r三个命题变项形成的极小项与极大项三个命题变项形成的极小项与极大项 极小项极小项 极大项极大项 公式公式 成真成真赋值赋值名称名称 公式公式 成假成假赋值赋值名称名称 p q r p q r p q r p q rp q rp q rp q rp q r0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1m0m1m2m3m4m5m6m7p q r p q r p q r p q r p q r p q r p q r p q r 0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1M0M1M2M3M4M5M6M7 定义定义1-对于给定的命题公式，如果有一个等价公式仅由对于给定的命题公式，如果有一个等价公式仅由极大极大项的合取项的合取所组成，则该等价式称为原式的主合取范式。所组成，则该等价式称为原式的主合取范式。定理定理1-（主合取范式存在惟一定理）任何命题公式的主合（主合取范式存在惟一定理）任何命题公式的主合取范式一定存在，并且惟一。取范式一定存在，并且惟一。由真值表方法可由真值表方法可知知：一个公式的真值为：一个公式的真值为0的真值指派所的真值指派所对应的大项的合取，即为此公式的主合取范式。对应的大项的合取，即为此公式的主合取范式。例例1-用真值表方法求用真值表方法求 的主合取范式的主合取范式解解:公式的真值表如下公式的真值表如下P Q R PQ R(pQ)R0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 1 1 1 1 0 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0所以公式所以公式 的主合取范式为的主合取范式为:用用等值演算等值演算方法构成主合取范式的主要步骤如下：方法构成主合取范式的主要步骤如下：（1）将原命题公式化归为）将原命题公式化归为合取范式合取范式；（2）除去合取范式中所有）除去合取范式中所有永真永真的合取项；的合取项；（3）合并相同的析取项和相同的变元；）合并相同的析取项和相同的变元；（4）对合取项补入没有出现的命题变元，即添加如）对合取项补入没有出现的命题变元，即添加如(pp)的式子，再按分配律进行演算；的式子，再按分配律进行演算；（5）将大项按下标由小到大的顺序排列。）将大项按下标由小到大的顺序排列。(pq)r (p r)(q r)（合取范式）（合取范式）p r p(qq)r (p q r)(pq r)M0 M2 q r (pp)q r (p q r)(p q r)M0 M4 ,代入代入 并排序，得并排序，得 (pq)r M0 M2 M4 （主合取范式（主合取范式）例例1 求公式求公式 A=(pq)r的主合取范式的主合取范式例例2 用等值演算方法求用等值演算方法求 的主合取范式。的主合取范式。解：解：合取范式合取范式【说明说明】(1)(1)主析取范式的析取项为小项，用小主析取范式的析取项为小项，用小m加下标表示。加下标表示。如如m010，其中其中0表示对应的命题变元的表示对应的命题变元的否定否定出现在合出现在合取项中取项中,1,1表示对应的命题变元出现在合取项中。表示对应的命题变元出现在合取项中。(2)(2)主合取范式的合取项为大项主合取范式的合取项为大项,用大用大M加下标表示加下标表示,如如M010,其中其中0表示对应的命题变元出现在析取项中表示对应的命题变元出现在析取项中,1,1表示对应命题变元的否定出现在析取项中。表示对应命题变元的否定出现在析取项中。(3)(3)在在真值表真值表中中,一个公式的主析取范式由其一个公式的主析取范式由其真值为真值为1 1的的真值指派所在对应的小项的析取组成。真值指派所在对应的小项的析取组成。(4)(4)在在真值表真值表中中,一个公式的一个公式的主合取范式由其主合取范式由其真值为真值为0 0的的真值指派所对应的真值指派所对应的大项大项的合取所组成。的合取所组成。主范式的应用主范式的应用1.1.求公式的成真成假赋求公式的成真成假赋值值 设公式设公式A含含n个命题变项个命题变项,A的主析取范式有的主析取范式有s个极小项个极小项,则则A有有s个成真赋值个成真赋值,它们是极小项下标的二进制表示它们是极小项下标的二进制表示,其其余余2n-s个赋值都是成假赋值个赋值都是成假赋值 例如例如 (pq)r m1 m3 m5 m6 m7成真赋值为成真赋值为 001,011,101,110,111，成假赋值为成假赋值为 000,010,100.类似地，由主合取范式也立即求出成假赋值和成真赋值类似地，由主合取范式也立即求出成假赋值和成真赋值.设设A含含n个命题变项个命题变项.2.判断公式的类型判断公式的类型 A为重言式为重言式 A的主析取范式含全部的主析取范式含全部2n个极小项个极小项 A的主合取范式的主合取范式不含不含任何极大项任何极大项,记记为为1.A为矛盾式为矛盾式 A的主合析取范式含全部的主合析取范式含全部2n个极大项个极大项 A的主析取范式不含任何极小项的主析取范式不含任何极小项,记记为为0.A为非重言式的可满足式为非重言式的可满足式 A的主析取范式中至少含一个、但的主析取范式中至少含一个、但不是全部不是全部极小项极小项 A的主合取范式中至少含一个、但不的主合取范式中至少含一个、但不是全部极大项是全部极大项.主范式的应用例例3 用主析取范式判断用主析取范式判断公式的类型公式的类型:(1)A (pq)q (2)B p(p q)(3)C(p q)r解：解：(1)A (p q)q (pq)q 0 矛盾式矛盾式(2)B p(p q)1 m0 m1 m2 m3 重言式重言式(3)C (p q)r (pq)r (pq r)(pqr)(pq r)(p q r)(pq r)(p q r)m0 m1 m3 m5 m7 非重言式的可满足式非重言式的可满足式主范式的应用主范式的应用3.判断两个公式是否等值判断两个公式是否等值例例4 用主析取范式判以下每一组公式是否等值用主析取范式判以下每一组公式是否等值 p(qr)与与(p q)r p(qr)与与(pq)r解解 p(qr)=m0 m1 m2 m3 m4 m5 m7 (p q)r=m0 m1 m2 m3 m4 m5 m7 (pq)r=m1 m3 m4 m5 m7显见，显见，中的两公式等值，而中的两公式等值，而的不等值的不等值.主范式的应用主范式的应用由主由主析取范式析取范式确定主确定主合取范式合取范式例例5 设设A有有3个命题变项个命题变项,且已知且已知A=m1 m3 m7,求求A的主合取范式的主合取范式.解解 A的成真赋值是的成真赋值是1,3,7的二进制表示的二进制表示,成假赋成假赋值是在主析取范式中没有出现的极小项的下角标值是在主析取范式中没有出现的极小项的下角标0,2,4,5,6的二进制表示。的二进制表示。它们恰好是它们恰好是A的主合取范式的极大项的下角标的主合取范式的极大项的下角标,故故 A M0 M2 M4 M5 M61.6 蕴含公式蕴含公式 如果双条件命题如果双条件命题AB为重言式，则为重言式，则AB。而条件命题而条件命题AB 是不对称的，如果是不对称的，如果AB为真，为真，B不一定能推出不一定能推出A。那么那么A和和B究竟存在什么关系呢？究竟存在什么关系呢？161 蕴含公式蕴含公式定义定义1-26 设设A，B是命题公式是命题公式,若若AB是重言式是重言式,则则称称AB是是蕴含重言式蕴含重言式，记为，记为AB，读作读作“A永真永真蕴蕴含含B”，简称，简称A蕴含蕴含B。即即 AB iff AB 1注意注意:与与 是意义不同的符号。是意义不同的符号。证明：证明：所以所以P(pQ)Q下面介绍几种证明下面介绍几种证明A永真蕴含永真蕴含B的方法。的方法。方法一：用真值表法或方法一：用真值表法或等价变换等价变换(推导推导)法证明法证明AB 1。例例1-24 证明证明 。P Q PQ P(PQ)(P(PQ)Q0 00 11 01 1110100011111方法二：通过分析的方法来证明一个条件命题是方法二：通过分析的方法来证明一个条件命题是蕴含式蕴含式。由于原命题等价于其逆反命题，即。由于原命题等价于其逆反命题，即 ABBA ，所以用分析法证明，所以用分析法证明AB，有如有如下两种方法下两种方法:(1)假设前件假设前件A为为真真时时,推出推出后件后件B也为真也为真,则则AB;(2)假设后件假设后件B为为假假时时,推出推出前件前件A也为假也为假,则则AB。例例1-25证法证法1：证法证法2：例例1-26 如果我认真学习，我的如果我认真学习，我的“离散数学离散数学”不会不及格，不会不及格，如果我不热衷于玩电子游戏，我将认真学习，如果我不热衷于玩电子游戏，我将认真学习，但我的但我的“离散数学离散数学”不及格。不及格。结论：我热衷于玩电子游戏。结论：我热衷于玩电子游戏。证明：证明：设设P：我认真学习。：我认真学习。Q：我的：我的“离散数学离散数学”及格。及格。R：我热衷于玩电子游戏。：我热衷于玩电子游戏。常见的蕴含重言式析取三段论假言推论拒取式假言三段论二难推论化简式一附加式化简式二例例1-27 分析证明分析证明 。证明：假设后件证明：假设后件 为为0，则，则P为为1，R 为为 0。(a)若若Q为为1，则，则 为为0，所以，所以 为为0；(b)若若Q为为0，则，则 为为0，所以，所以 为为0。故此：故此：成立。成立。162 蕴含公式的性质蕴含公式的性质（1）设）设A、B是命题公式，若是命题公式，若ABB 且且A为重言式，则为重言式，则B必是重言式。必是重言式。证明证明:因为因为ABB，所以，所以 AB 为为1，又因为，又因为A为为1，所以，所以B为为1，即，即B为重言式。为重言式。（2）蕴含关系是传递的，即）蕴含关系是传递的，即ABB 且且BCC，则则ACC。1.8 推理理论推理理论 逻辑学的主要任务是提出一套推理规则，按照公认的推逻辑学的主要任务是提出一套推理规则，按照公认的推理规则从前提集合中推导出一个结论来，这个推理过程称理规则从前提集合中推导出一个结论来，这个推理过程称为演绎或形式证明。为演绎或形式证明。在一般的论证中，主要是根据实践经验。如果确认前提在一般的论证中，主要是根据实践经验。如果确认前提为真，并遵守恰当的推理规则，则可期望所得的结论也是为真，并遵守恰当的推理规则，则可期望所得的结论也是真的。倘若认定前提是真的，从前提推导出结论的论证是真的。倘若认定前提是真的，从前提推导出结论的论证是遵守逻辑推理规则，且公认此结论是真实的，则这个论证遵守逻辑推理规则，且公认此结论是真实的，则这个论证称为合法论证。一般论证中必须特别注意论证的合法性。称为合法论证。一般论证中必须特别注意论证的合法性。所谓合法是指前提和结论都符合客观实际情况，大家公所谓合法是指前提和结论都符合客观实际情况，大家公认是真实的。即合情、合理、合法，令人信服。认是真实的。即合情、合理、合法，令人信服。在数理逻辑中情况稍有不同，它把注意力集在数理逻辑中情况稍有不同，它把注意力集中在推理规则的研究上，如果依据这些推理规则，中在推理规则的研究上，如果依据这些推理规则，从前提推导出来的任何结论都称为有效结论，这从前提推导出来的任何结论都称为有效结论，这种论证称为有效论证。在确认论证有效性时，前种论证称为有效论证。在确认论证有效性时，前提与结论的真实性不起任何作用，也就是说，在提与结论的真实性不起任何作用，也就是说，在数理逻辑中，只关心论证的有效性，而不大关心数理逻辑中，只关心论证的有效性，而不大关心论证的合法性。论证的合法性。前提前提：如果马会飞或羊吃草，则母鸡就会是飞如果马会飞或羊吃草，则母鸡就会是飞 鸟；如果母鸡是飞鸟，那么烤熟的鸭子还鸟；如果母鸡是飞鸟，那么烤熟的鸭子还 会跑；烤熟的鸭子不会跑。会跑；烤熟的鸭子不会跑。结论结论：羊不吃草。羊不吃草。蕴含式的定义是：给定两个命题公式蕴含式的定义是：给定两个命题公式A和和B，当且仅当，当且仅当AB 是一个重言式，则称是一个重言式，则称A蕴含蕴含B，记为，记为 AB，又称，又称B是是A的有的有效结论或效结论或B由由A逻辑推出。这个定义可以推广到有逻辑推出。这个定义可以推广到有n个前提的个前提的情况。情况。定义定义1-27 设设 是命题公式，当且仅当是命题公式，当且仅当 则称则称C是前提集合是前提集合 的有效结论。的有效结论。判别有效结论的过程就是论证的过程，论证方法千变万化，判别有效结论的过程就是论证的过程，论证方法千变万化，但基本方法是真值表法、直接证法和间接证法。但基本方法是真值表法、直接证法和间接证法。（一）真值表法（一）真值表法 设设 是出现的前提集合是出现的前提集合 和和C中的所有命题分量，假定对中的所有命题分量，假定对 作全部作全部的真值指派就能确定的真值指派就能确定 和和C的真值，的真值，那么通过真值表就可以确定结论那么通过真值表就可以确定结论C是否是前提集合的有效是否是前提集合的有效论证，这个方法称为真值表法。论证，这个方法称为真值表法。利用真值表判别一个有效论证的方法：利用真值表判别一个有效论证的方法：方法一：方法一：在真值表上，若前提在真值表上，若前提 H1,H2,H3,Hn 均为真的所有行，均为真的所有行，结论结论C也为真，则论证有效。也为真，则论证有效。方法二：方法二：在真值表上，若结论在真值表上，若结论C为假的每一行，其前提为假的每一行，其前提 H1,H2,H3,Hn 中至少有一个为假，则论证有效。中至少有一个为假，则论证有效。例例1-28 如果我认真学习，我的如果我认真学习，我的“离散数学离散数学”不会不及格，不会不及格，如果我不热衷于玩电子游戏，我将认真学习，如果我不热衷于玩电子游戏，我将认真学习，但我的但我的“离散数学离散数学”不及格。不及格。结论：我热衷于玩电子游戏。结论：我热衷于玩电子游戏。P:我认真学习，我认真学习，Q:我的我的“离散数学离散数学”及格，及格，R:我热衷于玩电子游戏。我热衷于玩电子游戏。符号化为：符号化为：其真值表如下：其真值表如下：解：解：判断法一：真值表中，只有第判断法一：真值表中，只有第2行的前提都为行的前提都为1，其结论也，其结论也为为1，所以论证有效。，所以论证有效。判断法二：真值表中，第判断法二：真值表中，第1、3、5、7行为行为0，每行的前提，每行的前提至少有一个为至少有一个为0，所以论证有效。，所以论证有效。P Q RRpQRpQ R0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 1 0 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 0 1 1 1 1 1 1 1 0 0 1 1 0 0 0 1 0 1 0 1 0 1 pqpqpq00111011101000111100（二）构造证明法（二）构造证明法 (1)(1)推理规则推理规则 常用的推理规则有：常用的推理规则有：P规则：规则：在推导的任意一步都可以引入一个前提。在推导的任意一步都可以引入一个前提。T规则：规则：如果公式如果公式S等价于或被重言蕴含在一个或多个前提或中间等价于或被重言蕴含在一个或多个前提或中间结果命题中，则推导中可以引入结果命题中，则推导中可以引入S。CP规则：规则：如果能从如果能从R及一组前提推导出及一组前提推导出C，则可从这组前提推导出，则可从这组前提推导出RC。设前提前提 若若 则 (2)(2)推理定律推理定律 在推导过程除推理规则外在推导过程除推理规则外,还需要推理定律还需要推理定律,这些推理定这些推理定律就是前面所讲的常用的蕴含式（用律就是前面所讲的常用的蕴含式（用I I表示）和命题定律表示）和命题定律（用（用E E表示）。现在将蕴含式和命题定律再次显示如下。表示）。现在将蕴含式和命题定律再次显示如下。化简1附加化简2化简2假言推论拒取式假言三段论二难推论联结词归化联结词归化（3）推理方法）推理方法 直接证明法直接证明法 利用推理规则和已知的等价式和蕴含式，从前提集合利用推理规则和已知的等价式和蕴含式，从前提集合中直接推导出有效结论。中直接推导出有效结论。例例1-29 证明证明 证明：证明：PT(1)E11 联结词归化联结词归化 PT(2)(3)I13 假言三段论假言三段论T(4)E14 PT(5)(6)I13 假言三段论假言三段论T(7)E11 联结词归化联结词归化