1、数理逻辑又称符号逻辑、理论逻辑。数理逻辑又称符号逻辑、理论逻辑。它既是数学的一个分支，也是逻辑学的它既是数学的一个分支，也是逻辑学的一个分支；是用数学的方法研究逻辑或一个分支；是用数学的方法研究逻辑或形式逻辑的学科。形式逻辑的学科。数理逻辑就是精确化、数学化的形式逻辑。数理逻辑就是精确化、数学化的形式逻辑。数理逻辑包括数理逻辑包括命题逻辑命题逻辑和和谓词逻辑谓词逻辑。它是现代计算机技术的基础。它是现代计算机技术的基础。它为机器证明、自动程序设计、它为机器证明、自动程序设计、计算机辅助设计等计算机应用计算机辅助设计等计算机应用提供必要的理论基础。提供必要的理论基础。第第9章章 命题逻辑命题逻辑例
2、例1 张三说李四在说谎张三说李四在说谎,李四说王五在说谎李四说王五在说谎, 王五说张三和李四都在说谎王五说张三和李四都在说谎. 问问:谁说的是真话谁说的是真话? 例例2 有一仓库被盗有一仓库被盗,经侦察确定甲经侦察确定甲,乙乙,丙丙,丁丁 四人中四人中 的两人作案的两人作案,且可靠的线索有且可靠的线索有: (1) 甲甲,乙两人中有且只有一个人去过仓库乙两人中有且只有一个人去过仓库; (2) 乙和丁不会同时去仓库乙和丁不会同时去仓库; (3) 丙若去仓库丙若去仓库,丁必定同去丁必定同去; (4) 丁若没去仓库丁若没去仓库,则甲也没去则甲也没去. 判断四人中哪两人作案判断四人中哪两人作案?解答解答
3、:(1)李四说真话李四说真话; (2)作案者为甲和丁作案者为甲和丁.9.1 命题和命题联结词命题和命题联结词 一、一、命题的概念命题的概念 二、二、命题联结词和真值表命题联结词和真值表 三、命题的符号化三、命题的符号化 四、四、命题公式命题公式 1.命题的定义命题的定义 能够确定或分辨其真假的陈述句能够确定或分辨其真假的陈述句, 且真与假必居其一。且真与假必居其一。 简言之简言之,命题是非真即假的陈述句命题是非真即假的陈述句。 2.命题的真值命题的真值 命题是真就说其真值为真命题是真就说其真值为真,用用“1”表示，表示， 命题是假就说其真值为假命题是假就说其真值为假,用用“0”表示。表示。 真
4、值为真的命题称为真命题真值为真的命题称为真命题, 真值为假的命题称假命题。真值为假的命题称假命题。一、命题的概念一、命题的概念 3.说明说明：判断命题应注意以下几点判断命题应注意以下几点 (1) 那些那些“自称谓自称谓”的陈述句可能产生自相矛盾的的陈述句可能产生自相矛盾的 结论结论(悖论悖论),故不在讨论之列故不在讨论之列. 例如：我现在说真话例如：我现在说真话. (2) “很难很难”,“相当年轻相当年轻”等这些概念等这些概念 没有清晰的界限没有清晰的界限,属于模糊概念属于模糊概念,故不在讨论之列故不在讨论之列. 例如：这个题目很难例如：这个题目很难. (3) 某些命题尚未确定其真值某些命题尚
5、未确定其真值. 例如：火星上存在有生命的物种例如：火星上存在有生命的物种. (4) 某些命题可能无法查明其真值某些命题可能无法查明其真值. 例如例如: 公元公元1014年元旦北京下过雨年元旦北京下过雨. (5) 命题真假会因时因地而异命题真假会因时因地而异. 例如例如: 现在是上午现在是上午. 例例1 判断下列句子是否是命题判断下列句子是否是命题 (1) 4是素数是素数. (2) 是无理数是无理数. (3) 月球上有水月球上有水. (4) 大于大于2吗吗 (5) 请不要吸烟！请不要吸烟！ (6) 这朵花真美丽啊！这朵花真美丽啊！ (7) x大于大于y. -是假命题是假命题-是真命题是真命题-是
6、真命题是真命题-不是命题不是命题-不是命题不是命题-不是命题不是命题-不是命题不是命题4.命题的表示命题的表示一般用大写的英文字母表示一个最简单命题。一般用大写的英文字母表示一个最简单命题。例如例如：P： 我是学生。我是学生。Q： 我明天要上学。我明天要上学。 1.原子命题原子命题 再细分不成为句子的命题称为再细分不成为句子的命题称为原子命题原子命题。 例如例如: “明天下雪明天下雪”和和“7是素数是素数” 都是原子命题。都是原子命题。 2.复合命题复合命题 原子命题常可通过一些原子命题常可通过一些命题联结词命题联结词 构成新命题构成新命题,这种命题称为这种命题称为复合命题复合命题。 例如例如
7、: “明天下雪或下雨明天下雪或下雨”； “明天下雨并且下雪明天下雨并且下雪”; “如果明天下雨如果明天下雨,我就不去游泳我就不去游泳”等，等， 都是复合命题。都是复合命题。 二、二、 命题的类型命题的类型 1.命题联结词命题联结词: 又称逻辑运算符号，又称逻辑运算符号， 是通常语言里的连接词的逻辑抽象。是通常语言里的连接词的逻辑抽象。 常用的命题联结词有五种常用的命题联结词有五种: 否定、合取、析取、蕴涵、等值否定、合取、析取、蕴涵、等值三、命题联结词三、命题联结词 注注: P为真当且仅当为真当且仅当P为假。为假。 P的真值表：的真值表：P PP P假假真真真真假假P P P P 1 0 0
8、1 设设P为命题为命题,那么那么“对对P的否定的否定”为另一命为另一命题。题。 表示为表示为P,叫做叫做P的的否定否定,读做读做“非非P”。2. 五种联结词五种联结词 例例2 设设P: 3是素数是素数; 则则P: 3不是素数。不是素数。 1) 否定否定 （ ） 设设Q: 这些都是男生这些都是男生; 则则Q:这些都不是男生。这些都不是男生。设设P,Q为命题为命题,那么那么“P并且并且Q”为一复合命题为一复合命题,表示为表示为PQ,叫做叫做P和和Q的的合取合取,读做读做“P且且Q”。注注: PQ为真当且仅当为真当且仅当P和和Q同为真。同为真。 PQ的的真值表：真值表：P Q P Q P PQQ0
9、00 00 10 11 01 01 11 10 00 00 01 1 例例3 设设P: 2是素数是素数, Q: 2是偶数是偶数; 则则PQ: 2是素数是素数,并且是偶数并且是偶数 2) 合取（合取（ ）3） 析取（析取（ ） 设设P,Q为命题为命题,那么那么“P或者或者Q”为一复合命题为一复合命题, 表示为表示为PQ,叫做叫做P和和Q的的析取析取, 读做读做“P或或Q”。 注注: PQ为真当且仅当为真当且仅当P和和Q至少一个为真。至少一个为真。 PQ的的真值表：真值表：P Q P Q P PQQ0 00 00 10 11 01 01 11 10 01 11 11 1 例例4 设设P: 张三爱唱
10、歌张三爱唱歌, Q: 张三爱听张三爱听 音乐音乐; 则则PQ: 张三爱唱歌或爱听音乐。张三爱唱歌或爱听音乐。思考思考: 张明下午在寝室或在图书馆。张明下午在寝室或在图书馆。 “或或”:可兼或和排斥或（不可兼或）。可兼或和排斥或（不可兼或）。 (PQ)(PQ)表示排斥或表示排斥或, 表示表示P和和Q不能同时发生。不能同时发生。 4) 蕴含（条件）（蕴含（条件）（ ） 设设P,Q为命题为命题,则则“如果如果P就就Q”为一复合命题为一复合命题, 表示为表示为PQ, 读做读做“若若P则则Q”。 这里这里, P叫做叫做前提前提,假设假设或或前件前件; Q叫做叫做结论或后件结论或后件。 注注: PQ为假当
11、且仅当为假当且仅当P为真而为真而Q为假。为假。 PQ的的真值表：真值表：P Q P Q P PQ Q0 00 00 10 11 01 01 11 11 11 10 01 1PQ的逻辑关系的逻辑关系: Q是是P的必要条件的必要条件, P是是Q的充分条件。的充分条件。若若P,则则Q； 如果如果P,那么那么Q； 因为因为P,所以所以Q。 例例:如果如果(因为因为)我有课我有课,那么那么(所以所以)我去教室。我去教室。 Q每当每当P； P仅当仅当Q。 例例:每当有课我去教室。我去教室仅当我有课。每当有课我去教室。我去教室仅当我有课。只要只要P,就就Q； 只有只有P才才Q 。 例例: 只要只要(只有只有
12、)我有课我有课,我就我就(才才)去教室。去教室。除非除非Q才才P； 除非除非Q,否则非否则非P。 例例:除非我有课除非我有课,我才我才(否则我不否则我不)去教室。去教室。说明：说明：注注1 在数理逻辑中在数理逻辑中,“如果如果P,那么那么Q”中的中的 前件前件P与后件与后件Q可以无任何内在联系。可以无任何内在联系。 例如：例如： “若若6是偶数，则明天下雨是偶数，则明天下雨”。注注2 在数理逻辑中在数理逻辑中,作为一种规定作为一种规定, 当当P为假时为假时,无论无论Q是真是假是真是假,PQ均为真。均为真。例例5 张三对李四说张三对李四说: “我去书店一定帮你买那本书我去书店一定帮你买那本书”。
13、 设设P:张三去书店张三去书店; Q:张三买那本书张三买那本书; 则可以将这句话表示为命题则可以将这句话表示为命题:PQ. 5) 等值（双条件）（等值（双条件）（ ） 设设P,Q为命题为命题,则则“P当且仅当当且仅当Q”为复合命题为复合命题,表示为表示为PQ,读做读做“P当且仅当当且仅当Q”。 PQ也可读做也可读做“P是是Q的充要条件的充要条件”。 注注: PQ为真当且仅当为真当且仅当P和和Q同为真或同为假。同为真或同为假。 或当且仅当或当且仅当PQ和和QP都为真都为真,PQ的真值表的真值表: P Q P Q P PQ Q0 00 00 10 11 01 01 11 11 10 00 01 1
14、 例例6: 设设P: 我去游泳我去游泳, Q: 天下雨天下雨; 则则PQ: 我去游泳当且仅当天不下雨。我去游泳当且仅当天不下雨。3.命题的符号化命题的符号化 符号化应注意以下几点符号化应注意以下几点: (1)确定语句是否为命题确定语句是否为命题,不是就不必翻译。不是就不必翻译。 (2)确定语句中的连接词是否能对应于并且确定语句中的连接词是否能对应于并且 对应于哪一个命题联结词对应于哪一个命题联结词; (3)正确表示原子命题和选择命题联结词正确表示原子命题和选择命题联结词; (5)原子命题一般表示成肯定。原子命题一般表示成肯定。 (4)要按逻辑关系翻译而不能凭字面翻译。要按逻辑关系翻译而不能凭字
15、面翻译。例例7 将下列命题符号化将下列命题符号化: (1) 他有理论知识但无实践经验。他有理论知识但无实践经验。 (2) 小张是计算机学院的学生，小张是计算机学院的学生， 他住在他住在8号楼号楼202室或室或203室。室。 (3) 又大又红的苹果我才会买。又大又红的苹果我才会买。 (4) 如果小王和小张都不去如果小王和小张都不去,则小李去。则小李去。 (5) 如果小王和小张不都去如果小王和小张不都去,则小李去。则小李去。 PQ(PQ)R(PQ)R(PQ)RP(QR)(QR)9.2 命题公式命题公式 1.命题变元命题变元: 如果如果P代表真值未指定的任意命题代表真值未指定的任意命题, 就称就称P
16、为为命题变元命题变元 2. 命题常元命题常元: 如果如果P代表真值已指定的命题代表真值已指定的命题, 就称就称P为为命题常元命题常元.(1和和0称为命题常元称为命题常元) 3. 原子公式原子公式:单个命题变元和命题常元单个命题变元和命题常元.一、命题变元一、命题变元(常元）常元） 定义定义 递归定义递归定义命题公式命题公式: (1) 0和和1是命题公式是命题公式; (2)命题变元是命题公式命题变元是命题公式; (3)如果如果A是命题公式是命题公式,则则A是命题公式是命题公式; (4)如果如果A和和B是命题公式是命题公式, 则则AB,AB, AB,AB是命题公式是命题公式; (5)只有有限次利用
17、上述只有有限次利用上述(1)(2)(3)(4) 而产生的符号串才是命题公式。而产生的符号串才是命题公式。二、命题公式二、命题公式 例例1 下面的符号串不是公式下面的符号串不是公式 PQP, RP, PP, (PQR)QR). 下面的符号串是公式下面的符号串是公式 (PQ)(PR), (P(QR)(QR). 定义定义 设设P1,P2,Pn是出现在命题公式是出现在命题公式 F中的全部命题变元中的全部命题变元, 给给P1,P2,Pn各指定一个真值各指定一个真值(真或假真或假), 称为对称为对F的一个的一个真值指派真值指派(赋值或解释赋值或解释)。 思考思考:含有含有n个命题变元的命题公式个命题变元的
18、命题公式F 有多少种真值指派有多少种真值指派? 三、公式的真值指派（赋值）三、公式的真值指派（赋值）四、公式的真值表四、公式的真值表用表格的形式来反映公式在所有不同的用表格的形式来反映公式在所有不同的真值指派下与其命题变元之间的真值关系，真值指派下与其命题变元之间的真值关系，这样的表格称为公式的这样的表格称为公式的真值表真值表。 定义定义 设设A为任一命题公式为任一命题公式: (1) 若公式若公式A在它的各种赋值下取值均为真在它的各种赋值下取值均为真, 则称公式则称公式A 是是重言式重言式或或永真式永真式; (2) 若公式若公式A在它的各种赋值下取值均为假在它的各种赋值下取值均为假, 则称公式
19、是则称公式是矛盾式矛盾式或或永假式永假式; (3) 若至少有一组真值指派使公式若至少有一组真值指派使公式 A的值为真，的值为真， 则称公式则称公式A是是可满足式可满足式。五、公式的类型五、公式的类型9.3 命题公式的等值关系和蕴含关系命题公式的等值关系和蕴含关系 1.定义定义 设设A和和B是两个命题公式是两个命题公式, 若公式若公式AB为重言式为重言式, 则称公式则称公式A和和B是等值的公式是等值的公式,记为记为AB。 注注: (1) 当且仅当在所有真值指派下，当且仅当在所有真值指派下， 公式公式A和和B的真值完全相同时的真值完全相同时, 公式公式A和和B才是两个等值的公式。才是两个等值的公式
20、。 (2) AB是表示一个公式，是表示一个公式， 而而AB是表示两公式是表示两公式A和和B的关系是等值。的关系是等值。一、一、 命题公式的等值关系命题公式的等值关系 1）自反性：）自反性： AA。 2）对称性：）对称性： 若若 AB 则则 BA。 3) 传递性：传递性： 若若AB,BC,则则AC。 2. 等值关系的性质等值关系的性质等值关系是一个等价关系。等值关系是一个等价关系。 3.证明逻辑恒等式证明逻辑恒等式AB的方法的方法: (1) 利用真值表利用真值表: 证明公式证明公式AB为重言式。为重言式。 例例1 证明：德证明：德.摩根定律摩根定律(PQ) PQ证明证明: 公式公式(PQ) )
21、(PQ )真值表：真值表：P QP QPQPQ(PQ)(PQ)P PQ Q( (PQ) )(PQ) )( (PPQ Q) )0 00 00 10 11 01 01 11 10 01 11 11 11 10 00 00 01 10 00 00 01 11 11 11 1 从真值表可得：从真值表可得： (PQ) PQ。 1)代入规则代入规则: 重言式中某命题变元出现的每一处重言式中某命题变元出现的每一处 均代以同一命题公式后所得命题公式均代以同一命题公式后所得命题公式 (代入实例代入实例)仍为重言式。仍为重言式。 如：如： 在在P(PQ)P中以中以(RP)代代P得得 (RP)(RP)Q)(RP)
22、在在PQQP中以中以C代代P,同时以同时以(AB)代代Q得得 C(AB)(AB)C (2) 等值演算：等值演算： a) 常用的等值式常用的等值式 b) 两个规则两个规则 2) 2) 定义定义 若若C是公式是公式A中的一部分且中的一部分且C为公式为公式, 则称则称C为为A的的子公式子公式。 例例: PQ和和PR是公式是公式PQPR 的子公式。的子公式。 3) 替换规则替换规则: 若若C是是A的子公式的子公式,且且CD。 如果将公式如果将公式A中的子公式中的子公式C， 置换成公式置换成公式D之后之后,得到公式得到公式B, 则则AB。 1.定义定义 设设A和和B是两个公式是两个公式, 若公式若公式A
23、B是重言式是重言式,即即AB1, 则称公式则称公式A蕴含公式蕴含公式B,记作记作AB。 2.蕴含关系的性质蕴含关系的性质 二、命题公式的蕴含关系二、命题公式的蕴含关系a) 自反性：自反性： AA.b) 反对称性：若反对称性：若AB,BA,则则AB.c) 传递性：传递性： 若若AB,BC,则则AC.蕴含关系是一个偏序关系。蕴含关系是一个偏序关系。 (2) 演绎推理：演绎推理： a）证明）证明A为真时为真时B为真为真. b) 证明证明B为假时为假时A为假。为假。 3.证明永真蕴涵式证明永真蕴涵式AB的方法的方法:(1) 利用真值表利用真值表: 证明公式证明公式AB为重言式。为重言式。 例例1 证明
24、证明 (PQ)Q P。 证明证明:设设 (PQ)Q为真为真, 则则 PQ和和Q同为真同为真; 因此因此Q为假为假;从而从而P为假为假; 所以所以P为真。为真。 例例2 证明证明(PQ)(QR) PR。 证明证明:设设 PR为假为假, 则则P为真而为真而R为假为假; 对对Q分两种情况讨论分两种情况讨论: (a) 若若Q为真为真,则因则因R为假为假,故故QR为假为假; (b) 若若Q为假为假,则因则因P为真为真,故故PQ为假为假; 则则(PQ)(QR)为假。为假。9.4 范式范式 一、一、质合取式与质析取式质合取式与质析取式 二、二、析取范式与合取范式析取范式与合取范式 三、三、最最小项与最大项小
25、项与最大项 四、四、主析取范式与主合取范式主析取范式与主合取范式 定义定义1 一个由命题变元或命题变元的否定一个由命题变元或命题变元的否定 所组成的所组成的合取式合取式称为称为质合取式质合取式。 定义定义2 一个由命题变元或命题变元的否定一个由命题变元或命题变元的否定 所组成的所组成的析取式析取式称为称为质析取式质析取式。 如：设如：设P和和Q是两个命题变元是两个命题变元, 则则P, PQ,PQ, PQ都是质合取式都是质合取式, 而而 Q,PQ, PQ, PQ都是质析取式。都是质析取式。 一、质合（析）取式一、质合（析）取式1.质合（析）取式的定义质合（析）取式的定义 (1) 质合取式为矛盾式
26、质合取式为矛盾式的充分必要条件是的充分必要条件是, 它同时包含某个命题变元它同时包含某个命题变元P及其否定及其否定P。 (2) 质析取式为重言式质析取式为重言式的充分必要条件是的充分必要条件是, 它同时包含某个命题变元它同时包含某个命题变元P及其否定及其否定P。2.定理定理 定义定义3 一个由一个由质合取式质合取式的的析取析取所组成的公式所组成的公式, 称为称为析取范式析取范式, 即该公式具有形式即该公式具有形式: A1A2 An(n1) 其中其中A1,A2,An都是质合取式。都是质合取式。 定义定义4一个由一个由质析取式质析取式的的合取合取所组成的公式所组成的公式, 称为称为合取范式合取范式
27、, 即该公式具有形式即该公式具有形式: A1A2 An(n1) 其中其中A1,A2,An都是质析取式。都是质析取式。 如：如： P(PQ)(QR) 为析取范式。为析取范式。 (PQR)(QR) Q 为合取范式。为合取范式。二、二、 析（合）取范式析（合）取范式1. 析（合）取范式的定义析（合）取范式的定义 3.定理定理:对于任何命题公式对于任何命题公式A都存在都存在 与其等值的析取范式和合取范式。与其等值的析取范式和合取范式。 4.求求与与A逻辑等价的析取范式和合取范式的方法逻辑等价的析取范式和合取范式的方法: (1) 用蕴涵表达式和等值表达式消去用蕴涵表达式和等值表达式消去 公式公式A中的中
28、的和和 联结词联结词; (2) 用双重否定律和德用双重否定律和德 摩根律将摩根律将A中的中的都消去都消去 或移到命题变元之前或移到命题变元之前; (3) 用结合律和分配律将公式化成析取范式用结合律和分配律将公式化成析取范式 或合取范式。或合取范式。 例例1 求公式：求公式：(PQ)P的析取范式的析取范式 与合取范式。与合取范式。 解解:公式公式 (PQ)P(PQ)P (析取范式析取范式) (PP)(QP) (合取范式合取范式) P(PQ) (合取范式合取范式) n*ii=1Pn*ii= 1P*iP三、三、 最小（大）项最小（大）项 定义定义5 思考思考:含含n个变元的最小项和最大项的个数？个变
29、元的最小项和最大项的个数？设有个设有个n命题变元命题变元P1,P2,Pn, 形如形如P1,P2,Pn所产生的所产生的最大项最大项。的命题公式称为由命题变元的命题公式称为由命题变元而形如而形如的命题公式称由命题变元的命题公式称由命题变元P1,P2,Pn所产生的所产生的最小项最小项。其中每个其中每个 或为或为Pi, 或为或为Pi ，即即Pi、Pi 必出现一个，且只能出现一个。必出现一个，且只能出现一个。最小项最小项最大项最大项公式公式成成真真赋值赋值编编号号公式公式成成假假赋值赋值编编号号PPQ QP QP Q P PQ Q P Q P Q0000010110101111m00m01m10m11
30、P Q P Q P PQ QP QP QPPQ Q0000010110101111M00M01M10M11 含含2个命题变元个命题变元P,Q的最小项和最大项的最小项和最大项最小项最小项最大项最大项公式公式成成真真赋值赋值编号编号公式公式成成假假赋值赋值编号编号PPQQR RPPQ RQ RP QP QR RP Q RP Q R P PQQR R P PQ RQ R P Q P QR R P Q R P Q R000000001001010010011011100100101101110110111111m000m001m010m011m100m101m110m111 P Q R P Q R P
31、 Q P QR R P PQ RQ R P PQQR RP Q RP Q RP QP QR RPPQ RQ RPPQQR R000000001001010010011011100100101101110110111111M000M001M010M011M100M101M110M111 含含3个命题变元个命题变元P,Q,R的最小项和最大项的最小项和最大项 1.定义定义 由不同的最小项所组成的析取式由不同的最小项所组成的析取式, 称为称为主析取范式主析取范式。 由不同的最大项所组成由不同的最大项所组成 的合取式的合取式, 称为称为主合取范式主合取范式。 四、四、 主析（合）取范式主析（合）取范式任
32、何非重言式都有唯一的主合取范式。任何非重言式都有唯一的主合取范式。 重言式重言式无主合取范式，定义为无主合取范式，定义为“1”。2. 定理定理 3. 定理定理 任何非矛盾式都有唯一的主析取范式。任何非矛盾式都有唯一的主析取范式。 矛盾式矛盾式无主析取范式，定义为无主析取范式，定义为“0”。 矛盾式矛盾式主合取范式必是所有最大项的合取。主合取范式必是所有最大项的合取。 重言式重言式主析取范式必是所有最小项的析取。主析取范式必是所有最小项的析取。 a. 利利用用真值表法求主析真值表法求主析(合合)取范式取范式: (1) 求主析取范式考虑真值表中对应求主析取范式考虑真值表中对应1的行的行 所有最小项
33、的析取。所有最小项的析取。 (2) 求主合取范式考虑真值表中对应求主合取范式考虑真值表中对应0的行的行 所有最大项的合取。所有最大项的合取。 4. 求命题公式主析求命题公式主析(合合)取范式的方法取范式的方法 例例2 用真值表求公式用真值表求公式(PQ)Q的主析的主析(合合)取范式。取范式。 P QP QPQPQ(PQ)Q(PQ)Q0 00 00 10 11 01 01 11 11 11 10 01 10 01 10 01 1考虑真值表为真的行考虑真值表为真的行,得公式的主析取范式：得公式的主析取范式：(PQ)(PQ)考虑真值表为假的行考虑真值表为假的行,得公式的主合取范式：得公式的主合取范式
34、： (PQ) (PQ) 。b. 利用等值演算求主析利用等值演算求主析(合合)取范式步骤取范式步骤:(1) 把给定命题公式化成析把给定命题公式化成析(合合)取范式取范式;(2) 删除析删除析(合合)取范式中所有为永假取范式中所有为永假(真真)的的 质合取式质合取式(质析取式质析取式);(3) 用等幂律将重复出现的变元化为一次出现用等幂律将重复出现的变元化为一次出现;(4) 补进析补进析(合合)取范式中未出现的所有变元取范式中未出现的所有变元;(5) 用等幂律消去重复出现的最小用等幂律消去重复出现的最小(大大)项。项。 例例3 求公式：求公式：(PQ)Q的主析取范式与主合取范式。的主析取范式与主合
35、取范式。 解解: (PQ)Q (PQ)Q (P Q) (Q (P P) (P Q) (P Q) (P Q) (P Q) (P Q) (主合取范式主合取范式) 主析取范式主析取范式: (P Q) (P Q) 9.5 命题演算的推理理论命题演算的推理理论 一、推理规则一、推理规则 二、证明方法二、证明方法 1.定义定义 设设A和和B是两个命题公式是两个命题公式,如果如果AB, 即如果命题公式即如果命题公式AB为重言式为重言式, 则称则称B是前提是前提A的的结论结论或从或从A推出结论推出结论B。 一般地一般地,假设假设H1,H2,Hn和和C是一些命题是一些命题, 如果如果: H1H2Hn C 则称从
36、前提则称从前提H1,H2,Hn推出结论推出结论C, 有时候也记为有时候也记为H1,H2,Hn C， 并且称并且称H1,H2,Hn 为为C的的前提集合前提集合。 一、一、 有效推理的概念有效推理的概念 P QP Q P PQ Q P(PP(PQ)Q)Q QQ(PQ(PQ)Q)P P0 00 00 10 11 01 01 11 11 1 1 1 0 0 1 10 00 00 01 10 01 10 01 10 0 1 1 0 0 1 10 00 01 11 1例例1判断结论判断结论C能否可以从前提能否可以从前提H1和和H2推出推出 (1)H1: PQ, H2:P, C:Q (2)H1: PQ, H
37、2:Q, C:P解解:写出前提的合取式和结论的真值表写出前提的合取式和结论的真值表, 看是否出现前提合取式为真看是否出现前提合取式为真,而结论为假的情形。而结论为假的情形。 由真值表可得：由真值表可得：(1)可以，可以，(2)不行不行 例例2 判断下列推理是否正确判断下列推理是否正确: 若下午气温超过若下午气温超过30,则小王必去游泳则小王必去游泳; 若他去游泳若他去游泳,他就不去看电影了他就不去看电影了. 所以若小王没去看电影所以若小王没去看电影,下午气温必超过下午气温必超过30。 解解:设设P:下午气温超过下午气温超过30; Q:小王去游泳小王去游泳; R:小王去看电影小王去看电影. 则前
38、提则前提:PQ,QR; 结论结论:RP; 推理的形式结构推理的形式结构:(PQ)(QR)(RP) (PQ)(QR)(RP) (PQ)(QR)(RP) (PQ)(QR)(RP) PR 非永真非永真, 因此推理不正确。因此推理不正确。 1.定义：定义： 形式证明是一个描述推理过称的命题序列。形式证明是一个描述推理过称的命题序列。 其中每个命题或是已知的命题，其中每个命题或是已知的命题， 或是有某些前提所推得的结论。或是有某些前提所推得的结论。 序列中最后一个命题就是所要求的结论。序列中最后一个命题就是所要求的结论。 二、二、 形式证明的概念形式证明的概念 2. 推理规则：推理规则： (1) 前提引
39、入规则前提引入规则: 在证明的任何步骤上都可以引用前提。在证明的任何步骤上都可以引用前提。 (2) 结论引用规则结论引用规则: 在证明的任何步骤上所得到的结论，在证明的任何步骤上所得到的结论， 都可以在其后的证明中引用。都可以在其后的证明中引用。 (3) 置换规则置换规则: 在证明的任何步骤上在证明的任何步骤上,命题公式的子公式命题公式的子公式 都可以用与之等值的其他命题公式置换。都可以用与之等值的其他命题公式置换。 (4) 代入规则代入规则: 在证明的任何步骤上在证明的任何步骤上, 重言式中的任一命题变元重言式中的任一命题变元 都可以用一命题公式代入都可以用一命题公式代入,得到的仍是重言式。
40、得到的仍是重言式。 3.证明的有效性：证明的有效性： 定义定义 如果证明过程中的每一步所得到的结论如果证明过程中的每一步所得到的结论 都是根据推理规则得到的都是根据推理规则得到的, 则这样的证明称为是则这样的证明称为是有效的有效的。 通过有效的证明而得到的结论通过有效的证明而得到的结论, 称为是称为是有效的有效的 结论结论。 4.证明方法证明方法: 直接证明法和间接证明法。直接证明法和间接证明法。 直接证明法有两种方法：直接证明法有两种方法： PT规则和规则和CP规则规则 例例3 证明：证明： PQ,QR,PS, S R(PQ)。 证明证明: 编号编号 公式公式 依据依据 (1) (2) (3
41、) (4) (5) (6) (7) (8) PS S P PQ Q QR RR(PQ) P P T(1)(2) P T(3)(4) P T(5)(6) T(4)(7)a) PT规则规则例例4 证明证明下列推理的正确性：下列推理的正确性： 若这里有球赛若这里有球赛,则通行是困难的则通行是困难的; 若他们按时到达若他们按时到达,则通行是不困难的则通行是不困难的; 他们按时到达了他们按时到达了, 所以这里没有球赛。所以这里没有球赛。解：设解：设 P:这里有球赛这里有球赛; Q:通行是困难的通行是困难的; R:他们按时到达他们按时到达 则要证明则要证明:PQ,RQ,R P。 编号编号 公式公式依据依据
42、 (1) (2) (3) (4) (5) R RQ Q PQ P P PT(1)(2)PT(3)(4)例例5 利用有效推理方法破解下列案子：利用有效推理方法破解下列案子： 一个侦探在调查了一珠宝商店的钻石项链一个侦探在调查了一珠宝商店的钻石项链盗窃案后，得到如下的事实线索：盗窃案后，得到如下的事实线索： 1）营业员）营业员A或或B偷了钻石项链；偷了钻石项链； 2）若）若A作案，则作案不在营业时间；作案，则作案不在营业时间； 3）若）若B提供的证词正确，则货柜没有上锁；提供的证词正确，则货柜没有上锁； 4）若）若B提供的证词不正确，提供的证词不正确， 则作案发生在营业时间；则作案发生在营业时间；
43、 5）货柜上锁了。）货柜上锁了。 试问谁偷了钻石项链？试问谁偷了钻石项链？ 并用有效推理的方法证明。并用有效推理的方法证明。 如果能够从如果能够从Q和前提集合和前提集合A中推导出中推导出R 来来, 则就能够从则就能够从A中推导出中推导出QR来。来。 b) 蕴含证明规则蕴含证明规则: (CP规则规则) 一般用在所要证明的结论为一般用在所要证明的结论为QR形式形式 （即结论为蕴含式）。（即结论为蕴含式）。例例6 证明证明: RS是前提是前提CD,CR,DS的有效结论的有效结论 证明证明: 编号编号 公式公式依据依据 (1) (2) (3) (4) (5) (6) (7) (8) (9) R CR
44、C CD D DS S RSRS附加前提附加前提PT(1)(2)PT(3)(4)PT(5)(6)T(1)(7)T(8)例例7 证明下列语句构成正确的推理：证明下列语句构成正确的推理：如果春暖花开，燕子就会飞回北方；如果春暖花开，燕子就会飞回北方；如果燕子飞回北方，则冰雪融化。如果燕子飞回北方，则冰雪融化。所以，如果冰雪没有融化，则没有春暖花开。所以，如果冰雪没有融化，则没有春暖花开。 5.定义定义 如果对公式如果对公式H1,H2,Hn中的命题变元中的命题变元 进行任何一组真值指派进行任何一组真值指派, 在公式在公式H1,H2,Hn中至少有一个为假中至少有一个为假, 即它们的合取式即它们的合取式
45、H1H2Hn是矛盾式是矛盾式, 则称公式则称公式H1,H2,Hn是是不相容的不相容的。 否则称其为否则称其为相容的相容的。 6. 间接证明法间接证明法: 为了证明结论为了证明结论C可以从前提可以从前提H1,H2,Hn推出推出, 把把C添加到这组前提中去添加到这组前提中去。 如果有某个公式如果有某个公式R使使H1H2HnC R R, 则这组新的前提是不相容的。则这组新的前提是不相容的。 于是当于是当H1H2Hn为真时为真时, C 必为假。必为假。 也就是当也就是当H1H2Hn为真时为真时, C必为真。必为真。 例例9 证明：证明： PQ，Q R ，R P P 证明证明: 编号编号 公式公式 依据依据 (1) (2) (3) (4) (5) (6) (7) (8) (9) （ P） P PQ Q Q R R RP R RR 假设假设 T(1) P T(2)(3) P T(4)(5) P T(2)(7) T(6)(8)
