第九章命题逻辑

1、数理逻辑又称符号逻辑、理论逻辑。 它既是数学的一个分支，也是逻辑学的 一个分支；是用数学的方法研究逻辑或 形式逻辑的学科。 数理逻辑就是精确化、数学化的形式逻辑。 数理逻辑包括命题逻辑和谓词逻辑。 它是现代计算机技术的基础。,它为机器证明、自动程序设计、 计算机辅助设计等计算机应用 提供必要的理论基础。,第9章 命题逻辑,例1 张三说李四在说谎,李四说王五在说谎, 王五说张三和李四都在说谎. 问:谁说的是真话? 例2 有一仓库被盗,经侦察确定甲,乙,丙,丁 四人中 的两人作案,且可靠的线索有: (1) 甲,乙两人中有且只有一个人去过仓库; (2) 乙和丁不会同时去仓库; (3) 丙若去仓库,丁

2、必定同去; (4) 丁若没去仓库,则甲也没去. 判断四人中哪两人作案? 解答:(1)李四说真话; (2)作案者为甲和丁.,9.1 命题和命题联结词,一、命题的概念 二、命题联结词和真值表 三、命题的符号化 四、命题公式,1.命题的定义 能够确定或分辨其真假的陈述句, 且真与假必居其一。 简言之,命题是非真即假的陈述句。 2.命题的真值 命题是真就说其真值为真,用“1”表示， 命题是假就说其真值为假,用“0”表示。 真值为真的命题称为真命题, 真值为假的命题称假命题。,一、命题的概念,3.说明：判断命题应注意以下几点 (1) 那些“自称谓”的陈述句可能产生自相矛盾的 结论(悖论),故不在讨论之列

3、. 例如：我现在说真话. (2) “很难”,“相当年轻”等这些概念 没有清晰的界限,属于模糊概念,故不在讨论之列. 例如：这个题目很难. (3) 某些命题尚未确定其真值. 例如：火星上存在有生命的物种. (4) 某些命题可能无法查明其真值. 例如: 公元1014年元旦北京下过雨. (5) 命题真假会因时因地而异. 例如: 现在是上午.,例1 判断下列句子是否是命题 (1) 4是素数. (2) 是无理数. (3) 月球上有水. (4) 大于2吗 (5) 请不要吸烟！ (6) 这朵花真美丽啊！ (7) x大于y.,-是假命题,-是真命题,-是真命题,-不是命题,-不是命题,-不是命题,-不是命题,

4、4.命题的表示,一般用大写的英文字母表示一个最简单命题。,例如：,P： 我是学生。,Q： 我明天要上学。,1.原子命题 再细分不成为句子的命题称为原子命题。 例如: “明天下雪”和“7是素数” 都是原子命题。 2.复合命题 原子命题常可通过一些命题联结词 构成新命题,这种命题称为复合命题。 例如: “明天下雪或下雨”； “明天下雨并且下雪”; “如果明天下雨,我就不去游泳”等， 都是复合命题。,二、 命题的类型,1.命题联结词: 又称逻辑运算符号， 是通常语言里的连接词的逻辑抽象。 常用的命题联结词有五种: 否定、合取、析取、蕴涵、等值,三、命题联结词,注: P为真当且仅当P为假。 P的真值表

5、：,设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的真值表：,例3 设P: 2是素数, Q: 2是偶数; 则PQ: 2是素数,并且是偶数,2) 合取（ ）,3） 析取（ ） 设P,Q为命题,那么“P或者Q”为一复合命题, 表示为PQ,叫做P和Q的析取, 读做“P或Q”。 注: PQ为真当且

6、仅当P和Q至少一个为真。 PQ的真值表：,例4 设P: 张三爱唱歌, Q: 张三爱听 音乐; 则PQ: 张三爱唱歌或爱听音乐。,思考: 张明下午在寝室或在图书馆。 “或”:可兼或和排斥或（不可兼或）。 (PQ)(PQ)表示排斥或, 表示P和Q不能同时发生。,4) 蕴含（条件）（ ） 设P,Q为命题,则“如果P就Q”为一复合命题, 表示为PQ, 读做“若P则Q”。 这里, P叫做前提,假设或前件; Q叫做结论或后件。 注: PQ为假当且仅当P为真而Q为假。 PQ的真值表：,PQ的逻辑关系: Q是P的必要条件, P是Q的充分条件。 若P,则Q； 如果P,那么Q； 因为P,所以Q。 例:如果(因为)

7、我有课,那么(所以)我去教室。 Q每当P； P仅当Q。 例:每当有课我去教室。我去教室仅当我有课。 只要P,就Q； 只有P才Q 。 例: 只要(只有)我有课,我就(才)去教室。 除非Q才P； 除非Q,否则非P。 例:除非我有课,我才(否则我不)去教室。,说明：,注1 在数理逻辑中,“如果P,那么Q”中的 前件P与后件Q可以无任何内在联系。 例如： “若6是偶数，则明天下雨”。 注2 在数理逻辑中,作为一种规定, 当P为假时,无论Q是真是假,PQ均为真。 例5 张三对李四说: “我去书店一定帮你买那本书”。 设P:张三去书店; Q:张三买那本书; 则可以将这句话表示为命题:PQ.,5) 等值（双

8、条件）（ ） 设P,Q为命题,则“P当且仅当Q”为复合命题,表示为PQ,读做“P当且仅当Q”。 PQ也可读做“P是Q的充要条件”。 注: PQ为真当且仅当P和Q同为真或同为假。 或当且仅当PQ和QP都为真,PQ的真值表:,例6: 设P: 我去游泳, Q: 天下雨; 则PQ: 我去游泳当且仅当天不下雨。,3.命题的符号化 符号化应注意以下几点: (1)确定语句是否为命题,不是就不必翻译。 (2)确定语句中的连接词是否能对应于并且 对应于哪一个命题联结词; (3)正确表示原子命题和选择命题联结词; (5)原子命题一般表示成肯定。 (4)要按逻辑关系翻译而不能凭字面翻译。,例7 将下列命题符号化:

9、(1) 他有理论知识但无实践经验。 (2) 小张是计算机学院的学生， 他住在8号楼202室或203室。 (3) 又大又红的苹果我才会买。 (4) 如果小王和小张都不去,则小李去。 (5) 如果小王和小张不都去,则小李去。,PQ,(PQ)R,(PQ)R,(PQ)R,P(QR)(QR),9.2 命题公式,1.命题变元: 如果P代表真值未指定的任意命题, 就称P为命题变元 2. 命题常元: 如果P代表真值已指定的命题, 就称P为命题常元.(1和0称为命题常元) 3. 原子公式:单个命题变元和命题常元.,一、命题变元(常元）,定义 递归定义命题公式: (1) 0和1是命题公式; (2)命题变元是命题公

10、式; (3)如果A是命题公式,则A是命题公式; (4)如果A和B是命题公式, 则AB,AB, AB,AB是命题公式; (5)只有有限次利用上述(1)(2)(3)(4) 而产生的符号串才是命题公式。,二、命题公式,例1 下面的符号串不是公式 PQP, RP, PP, (PQR)QR). 下面的符号串是公式 (PQ)(PR), (P(QR)(QR).,定义 设P1,P2,Pn是出现在命题公式 F中的全部命题变元, 给P1,P2,Pn各指定一个真值(真或假), 称为对F的一个真值指派(赋值或解释)。 思考:含有n个命题变元的命题公式F 有多少种真值指派?,三、公式的真值指派（赋值）,四、公式的真值表

11、,用表格的形式来反映公式在所有不同的 真值指派下与其命题变元之间的真值关系， 这样的表格称为公式的真值表。,定义 设A为任一命题公式: (1) 若公式A在它的各种赋值下取值均为真, 则称公式A 是重言式或永真式; (2) 若公式A在它的各种赋值下取值均为假, 则称公式是矛盾式或永假式; (3) 若至少有一组真值指派使公式 A的值为真， 则称公式A是可满足式。,五、公式的类型,9.3 命题公式的等值关系和蕴含关系,1.定义 设A和B是两个命题公式, 若公式AB为重言式, 则称公式A和B是等值的公式,记为AB。 注: (1) 当且仅当在所有真值指派下， 公式A和B的真值完全相同时, 公式A和B才是

12、两个等值的公式。 (2) AB是表示一个公式， 而AB是表示两公式A和B的关系是等值。,一、 命题公式的等值关系,1）自反性： AA。 2）对称性： 若 AB 则 BA。 3) 传递性： 若AB,BC,则AC。,2. 等值关系的性质,等值关系是一个等价关系。,3.证明逻辑恒等式AB的方法: (1) 利用真值表: 证明公式AB为重言式。,例1 证明：德.摩根定律(PQ) PQ,证明:,公式(PQ) ) (PQ )真值表：,从真值表可得：,(PQ) PQ。,1)代入规则: 重言式中某命题变元出现的每一处 均代以同一命题公式后所得命题公式 (代入实例)仍为重言式。 如： 在P(PQ)P中以(RP)代

13、P得 (RP)(RP)Q)(RP) 在PQQP中以C代P,同时以(AB)代Q得 C(AB)(AB)C,(2) 等值演算：,a) 常用的等值式,b) 两个规则,2) 定义 若C是公式A中的一部分且C为公式, 则称C为A的子公式。 例: PQ和PR是公式PQPR 的子公式。 3) 替换规则: 若C是A的子公式,且CD。 如果将公式A中的子公式C， 置换成公式D之后,得到公式B, 则AB。,1.定义 设A和B是两个公式, 若公式AB是重言式,即AB1, 则称公式A蕴含公式B,记作AB。 2.蕴含关系的性质,二、命题公式的蕴含关系,自反性： AA. 反对称性：若AB,BA,则AB. 传递性： 若AB,

14、BC,则AC.,蕴含关系是一个偏序关系。,(2) 演绎推理： a）证明A为真时B为真. b) 证明B为假时A为假。,3.证明永真蕴涵式AB的方法:,(1) 利用真值表: 证明公式AB为重言式。,例1 证明 (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 范式,一、质合取式与质析取式 二、析取范式与合取范式 三、最小项

15、与最大项 四、主析取范式与主合取范式,定义1 一个由命题变元或命题变元的否定 所组成的合取式称为质合取式。 定义2 一个由命题变元或命题变元的否定 所组成的析取式称为质析取式。 如：设P和Q是两个命题变元, 则P, PQ,PQ, PQ都是质合取式, 而 Q,PQ, PQ, PQ都是质析取式。,一、质合（析）取式,1.质合（析）取式的定义,(1) 质合取式为矛盾式的充分必要条件是, 它同时包含某个命题变元P及其否定P。 (2) 质析取式为重言式的充分必要条件是, 它同时包含某个命题变元P及其否定P。,2.定理,定义3 一个由质合取式的析取所组成的公式, 称为析取范式, 即该公式具有形式: A1A

16、2 An(n1) 其中A1,A2,An都是质合取式。 定义4一个由质析取式的合取所组成的公式, 称为合取范式, 即该公式具有形式: A1A2 An(n1) 其中A1,A2,An都是质析取式。 如： P(PQ)(QR) 为析取范式。 (PQR)(QR) Q 为合取范式。,二、 析（合）取范式,1. 析（合）取范式的定义,3.定理:对于任何命题公式A都存在 与其等值的析取范式和合取范式。 4.求与A逻辑等价的析取范式和合取范式的方法: (1) 用蕴涵表达式和等值表达式消去 公式A中的和 联结词; (2) 用双重否定律和德摩根律将A中的都消去 或移到命题变元之前; (3) 用结合律和分配律将公式化成

17、析取范式 或合取范式。,例1 求公式：(PQ)P的析取范式 与合取范式。 解:公式 (PQ)P(PQ)P (析取范式) (PP)(QP) (合取范式) P(PQ) (合取范式),三、 最小（大）项,定义5,思考:含n个变元的最小项和最大项的个数？,设有个n命题变元P1,P2,Pn,形如,P1,P2,Pn所产生的最大项。,的命题公式称为由命题变元,而形如,的命题公式称由命题变元,P1,P2,Pn所产生的最小项。,其中每个,或为Pi, 或为Pi ，,即Pi、Pi 必出现一个，且只能出现一个。,含2个命题变元P,Q的最小项和最大项,含3个命题变元P,Q,R的最小项和最大项,1.定义 由不同的最小项所

18、组成的析取式, 称为主析取范式。 由不同的最大项所组成 的合取式, 称为主合取范式。,四、 主析（合）取范式,任何非重言式都有唯一的主合取范式。,重言式无主合取范式，定义为“1”。,2. 定理,3. 定理,任何非矛盾式都有唯一的主析取范式。,矛盾式无主析取范式，定义为“0”。,矛盾式主合取范式必是所有最大项的合取。,重言式主析取范式必是所有最小项的析取。,a. 利用真值表法求主析(合)取范式: (1) 求主析取范式考虑真值表中对应1的行 所有最小项的析取。 (2) 求主合取范式考虑真值表中对应0的行 所有最大项的合取。,4. 求命题公式主析(合)取范式的方法,例2 用真值表求公式(PQ)Q的主

19、析(合)取范式。,考虑真值表为真的行, 得公式的主析取范式：(PQ)(PQ) 考虑真值表为假的行, 得公式的主合取范式： (PQ) (PQ) 。,b. 利用等值演算求主析(合)取范式步骤: (1) 把给定命题公式化成析(合)取范式; (2) 删除析(合)取范式中所有为永假(真)的 质合取式(质析取式); (3) 用等幂律将重复出现的变元化为一次出现; (4) 补进析(合)取范式中未出现的所有变元; (5) 用等幂律消去重复出现的最小(大)项。,例3 求公式：(PQ)Q的主析取范式与主合取范式。 解: (PQ)Q (PQ)Q (P Q) (Q (P P) (P Q) (P Q) (P Q) (P

20、 Q) (P Q) (主合取范式) 主析取范式: (P Q) (P Q),9.5 命题演算的推理理论,一、推理规则 二、证明方法,1.定义 设A和B是两个命题公式,如果AB, 即如果命题公式AB为重言式, 则称B是前提A的结论或从A推出结论B。 一般地,假设H1,H2,Hn和C是一些命题, 如果: H1H2Hn C 则称从前提H1,H2,Hn推出结论C, 有时候也记为H1,H2,Hn C， 并且称H1,H2,Hn 为C的前提集合。,一、 有效推理的概念,例1判断结论C能否可以从前提H1和H2推出 (1)H1: PQ, H2:P, C:Q (2)H1: PQ, H2:Q, C:P,解:写出前提的

21、合取式和结论的真值表, 看是否出现前提合取式为真,而结论为假的情形。,由真值表可得：(1)可以，(2)不行,例2 判断下列推理是否正确: 若下午气温超过30,则小王必去游泳; 若他去游泳,他就不去看电影了. 所以若小王没去看电影,下午气温必超过30。 解:设P:下午气温超过30; Q:小王去游泳; R:小王去看电影. 则前提:PQ,QR; 结论:RP; 推理的形式结构:(PQ)(QR)(RP) (PQ)(QR)(RP) (PQ)(QR)(RP) (PQ)(QR)(RP) PR 非永真, 因此推理不正确。,1.定义： 形式证明是一个描述推理过称的命题序列。 其中每个命题或是已知的命题， 或是有某

22、些前提所推得的结论。 序列中最后一个命题就是所要求的结论。,二、 形式证明的概念,2. 推理规则： (1) 前提引入规则: 在证明的任何步骤上都可以引用前提。 (2) 结论引用规则: 在证明的任何步骤上所得到的结论， 都可以在其后的证明中引用。 (3) 置换规则: 在证明的任何步骤上,命题公式的子公式 都可以用与之等值的其他命题公式置换。 (4) 代入规则: 在证明的任何步骤上, 重言式中的任一命题变元 都可以用一命题公式代入,得到的仍是重言式。,3.证明的有效性： 定义 如果证明过程中的每一步所得到的结论 都是根据推理规则得到的, 则这样的证明称为是有效的。 通过有效的证明而得到的结论, 称为是有效的 结论。 4.证明方法: 直接证明法和间接证明法。 直接证明法有两种方法： PT规则和CP规则,例3 证明： PQ,QR,PS, S R(