第九章命题逻辑

数理逻辑又称符号逻辑、理论逻辑。它既是数学的一个分支，也是逻辑学的一个分支；是用数学的方法研究逻辑或形式逻辑的学科。数理逻辑就是精确化、数学化的形式逻辑。数理逻辑包括命题逻辑和谓词逻辑。它是现代计算机技术的基础。它为机器证明、自动程序设计、计算机辅助设计等计算机应用提供必要的理论基础。第9章命题逻辑例1张三说李四在说谎,李四说王五在说谎,王五说张三和李四都在说谎.问:谁说的是真话?例2有一仓库被盗,经侦察确定甲,乙,丙,丁四人中的两人作案,且可靠的线索有:(1)甲,乙两人中有且只有一个人去过仓库;(2)乙和丁不会同时去仓库;(3)丙若去仓库,丁必定同去;(4)丁若没去仓库,则甲也没去.判断四人中哪两人作案?解答:(1)李四说真话;(2)作案者为甲和丁.9.1命题和命题联结词一、命题的概念二、命题联结词和真值表三、命题的符号化四、命题公式1.命题的定义能够确定或分辨其真假的陈述句,且真与假必居其一。简言之,命题是非真即假的陈述句。2.命题的真值命题是真就说其真值为真,用“1”表示，命题是假就说其真值为假,用“0”表示。真值为真的命题称为真命题,真值为假的命题称假命题。一、命题的概念3.说明：判断命题应注意以下几点(1)那些“自称谓”的陈述句可能产生自相矛盾的结论(悖论),故不在讨论之列.例如：我现在说真话.(2)“很难”,“相当年轻”等这些概念没有清晰的界限,属于模糊概念,故不在讨论之列.例如：这个题目很难.(3)某些命题尚未确定其真值.例如：火星上存在有生命的物种.(4)某些命题可能无法查明其真值.例如:公元1014年元旦北京下过雨.(5)命题真假会因时因地而异.例如:现在是上午.例1判断下列句子是否是命题(1)4是素数.(2)π是无理数.(3)月球上有水.(4)π大于2吗(5)请不要吸烟！(6)这朵花真美丽啊！(7)x大于y.-------------是假命题---------是真命题---------是真命题---------不是命题--------不是命题----不是命题-------------不是命题4.命题的表示一般用大写的英文字母表示一个最简单命题。例如：P：我是学生。Q：我明天要上学。1.原子命题再细分不成为句子的命题称为原子命题。例如:“明天下雪”和“7是素数”都是原子命题。2.复合命题原子命题常可通过一些命题联结词构成新命题,这种命题称为复合命题。例如:“明天下雪或下雨”；“明天下雨并且下雪”;“如果明天下雨,我就不去游泳”等，都是复合命题。二、命题的类型1.命题联结词:又称逻辑运算符号，是通常语言里的连接词的逻辑抽象。常用的命题联结词有五种:否定、合取、析取、蕴涵、等值三、命题联结词注:¬P为真当且仅当P为假。¬P的真值表：P¬P假真真假P¬P1001设P为命题,那么“对P的否定”为另一命题。表示为¬P,叫做P的否定,读做“非P”。2.五种联结词例2设P:3是素数;则¬P:3不是素数。1)否定（¬）设Q:这些都是男生;则¬Q:这些都不是男生。设P,Q为命题,那么“P并且Q”为一复合命题,表示为P∧Q,叫做P和Q的合取,读做“P且Q”。注:P∧Q为真当且仅当P和Q同为真。P∧Q的真值表：PQP∧Q000110110001例3设P:2是素数,Q:2是偶数;则P∧Q:2是素数,并且是偶数2)合取（∧）3）析取（∨）设P,Q为命题,那么“P或者Q”为一复合命题,表示为P∨Q,叫做P和Q的析取,读做“P或Q”。注:P∨Q为真当且仅当P和Q至少一个为真。P∨Q的真值表：PQP∨Q000110110111例4设P:张三爱唱歌,Q:张三爱听音乐;则P∨Q:张三爱唱歌或爱听音乐。思考:张明下午在寝室或在图书馆。“或”:可兼或和排斥或（不可兼或）。(P∧¬Q)∨(¬P∧Q)表示排斥或,表示P和Q不能同时发生。4)蕴含（条件）（→）设P,Q为命题,则“如果P就Q”为一复合命题,表示为P→Q,读做“若P则Q”。这里,P叫做前提,假设或前件;Q叫做结论或后件。注:P→Q为假当且仅当P为真而Q为假。P→Q的真值表：PQPQ000110111101P→Q的逻辑关系:Q是P的必要条件,P是Q的充分条件。若P,则Q；如果P,那么Q；因为P,所以Q。例:如果(因为)我有课,那么(所以)我去教室。Q每当P；P仅当Q。例:每当有课我去教室。我去教室仅当我有课。只要P,就Q；只有P才Q。例:只要(只有)我有课,我就(才)去教室。除非Q才P；除非Q,否则非P。例:除非我有课,我才(否则我不)去教室。说明：注1在数理逻辑中,“如果P,那么Q”中的前件P与后件Q可以无任何内在联系。例如：“若6是偶数，则明天下雨”。注2在数理逻辑中,作为一种规定,当P为假时,无论Q是真是假,P→Q均为真。例5张三对李四说:“我去书店一定帮你买那本书”。设P:张三去书店;Q:张三买那本书;则可以将这句话表示为命题:P→Q.5)等值（双条件）（）设P,Q为命题,则“P当且仅当Q”为复合命题,表示为PQ,读做“P当且仅当Q”。PQ也可读做“P是Q的充要条件”。注:PQ为真当且仅当P和Q同为真或同为假。或当且仅当P→Q和Q→P都为真,PQ的真值表:PQPQ000110111001例6:设P:我去游泳,Q:天下雨;则P¬Q:我去游泳当且仅当天不下雨。3.命题的符号化符号化应注意以下几点:(1)确定语句是否为命题,不是就不必翻译。(2)确定语句中的连接词是否能对应于并且对应于哪一个命题联结词;(3)正确表示原子命题和选择命题联结词;(5)原子命题一般表示成肯定。(4)要按逻辑关系翻译而不能凭字面翻译。例7将下列命题符号化:(1)他有理论知识但无实践经验。(2)小张是计算机学院的学生，他住在8号楼202室或203室。(3)又大又红的苹果我才会买。(4)如果小王和小张都不去,则小李去。(5)如果小王和小张不都去,则小李去。P∧¬Q(P∧Q)→R(¬P∧¬Q)→R¬(P∧Q)→RP∧((Q∧¬R)∨(¬Q∧R))9.2命题公式1.命题变元:如果P代表真值未指定的任意命题,就称P为命题变元2.命题常元:如果P代表真值已指定的命题,就称P为命题常元.(1和0称为命题常元)3.原子公式:单个命题变元和命题常元.一、命题变元(常元）定义递归定义命题公式:(1)0和1是命题公式;(2)命题变元是命题公式;(3)如果A是命题公式,则¬A是命题公式;(4)如果A和B是命题公式,则A∧B,A∨B,A→B,AB是命题公式;(5)只有有限次利用上述(1)(2)(3)(4)而产生的符号串才是命题公式。二、命题公式例1下面的符号串不是公式P→QP,∨R→P,P→P∨,(P∧Q∨R))Q∧R).下面的符号串是公式(P∨Q)→(¬P∧R),(P∧(Q∨R))(Q∧R).定义设P1,P2,…,Pn是出现在命题公式F中的全部命题变元,给P1,P2,…,Pn各指定一个真值(真或假),称为对F的一个真值指派(赋值或解释)。思考:含有n个命题变元的命题公式F有多少种真值指派?三、公式的真值指派（赋值）四、公式的真值表用表格的形式来反映公式在所有不同的真值指派下与其命题变元之间的真值关系，这样的表格称为公式的真值表。定义设A为任一命题公式:(1)若公式A在它的各种赋值下取值均为真,则称公式A是重言式或永真式;(2)若公式A在它的各种赋值下取值均为假,则称公式是矛盾式或永假式;(3)若至少有一组真值指派使公式A的值为真，则称公式A是可满足式。五、公式的类型9.3命题公式的等值关系和蕴含关系1.定义设A和B是两个命题公式,若公式AB为重言式,则称公式A和B是等值的公式,记为AB。注:(1)当且仅当在所有真值指派下，公式A和B的真值完全相同时,公式A和B才是两个等值的公式。(2)AB是表示一个公式，而AB是表示两公式A和B的关系是等值。一、命题公式的等值关系1）自反性：AA。2）对称性：若AB则BA。3)传递性：若AB,BC,则AC。2.等值关系的性质等值关系是一个等价关系。3.证明逻辑恒等式AB的方法:(1)利用真值表:证明公式AB为重言式。例1证明：德.摩根定律¬(P∨Q)¬P∧¬Q证明:公式(¬(P∨Q))(¬P∧¬Q)真值表：PQP∨Q¬(P∨Q)¬P∧¬Q(¬(P∨Q))(¬P∧¬Q)000110110111100010001111从真值表可得：¬(P∨Q)¬P∧¬Q。1)代入规则:重言式中某命题变元出现的每一处均代以同一命题公式后所得命题公式(代入实例)仍为重言式。如：在P∨(P∧Q)P中以(R→P)代P得(R→P)∨((R→P)∧Q)(R→P)在P∨QQ∨P中以¬C代P,同时以(¬A∧B)代Q得¬C∨(¬A∧B)(¬A∧B)∨¬C(2)等值演算：a)常用的等值式b)两个规则2)定义若C是公式A中的一部分且C为公式,则称C为A的子公式。例:P∨Q和P∧R是公式P∨Q→P∧R的子公式。3)替换规则:若C是A的子公式,且CD。如果将公式A中的子公式C，置换成公式D之后,得到公式B,则AB。1.定义设A和B是两个公式,若公式A→B是重言式,即A→B1,则称公式A蕴含公式B,记作AB。2.蕴含关系的性质二、命题公式的蕴含关系a)自反性：AA.b)反对称性：若AB,BA,则AB.c)传递性：若AB,BC,则AC.蕴含关系是一个偏序关系。(2)演绎推理：a）证明A为真时B为真.b)证明B为假时A为假。3.证明永真蕴涵式AB的方法:(1)利用真值表:证明公式A→B为重言式。例1证明(P→Q)∧¬Q¬P。证明:设(P→Q)∧¬Q为真,则P→Q和¬Q同为真;因此Q为假;从而P为假;所以¬P为真。例2证明(P→Q)∧(Q→R)P→R。证明:设P→R为假,则P为真而R为假;对Q分两种情况讨论:(a)若Q为真,则因R为假,故Q→R为假;(b)若Q为假,则因P为真,故P→Q为假;则(P→Q)∧(Q→R)为假。9.4范式一、质合取式与质析取式二、析取范式与合取范式三、最小项与最大项四、主析取范式与主合取范式定义1一个由命题变元或命题变元的否定所组成的合取式称为质合取式。定义2一个由命题变元或命题变元的否定所组成的析取式称为质析取式。如：设P和Q是两个命题变元,则P,P∧Q,¬P∧Q,¬P∧¬Q都是质合取式,而Q,P∨Q,¬P∨Q,¬P∨¬Q都是质析取式。一、质合（析）取式1.质合（析）取式的定义(1)质合取式为矛盾式的充分必要条件是,它同时包含某个命题变元P及其否定¬P。(2)质析取式为重言式的充分必要条件是,它同时包含某个命题变元P及其否定¬P。2.定理定义3一个由质合取式的析取所组成的公式,称为析取范式,即该公式具有形式:A1∨A2∨…∨An(n≥1)其中A1,A2,…,An都是质合取式。定义4一个由质析取式的合取所组成的公式,称为合取范式,即该公式具有形式:A1∧A2∧…∧An(n≥1)其中A1,A2,…,An都是质析取式。如：¬P∨(P∧Q)∨(Q∧R)为析取范式。(¬P∨Q∨R)∧(¬Q∨¬R)∧Q为合取范式。二、析（合）取范式1.析（合）取范式的定义3.定理:对于任何命题公式A都存在与其等值的析取范式和合取范式。4.求与A逻辑等价的析取范式和合取范式的方法:(1)用蕴涵表达式和等值表达式消去公式A中的→和联结词;(2)用双重否定律和德摩根律将A中的¬都消去或移到命题变元之前;(3)用结合律和分配律将公式化成析取范式或合取范式。例1求公式：(P→Q)→P的析取范式与合取范式。解:公式¬(¬P∨Q)∨P(P∧¬Q)∨P(析取范式)(P∨P)∧(¬Q∨P)(合取范式)P∧(P∨¬Q)(合取范式)n*ii=1Pn*ii=1P*iP三、最小（大）项定义5思考:含n个变元的最小项和最大项的个数？设有个n命题变元P1,P2,…,Pn,形如P1,P2,…,Pn所产生的最大项。的命题公式称为由命题变元而形如的命题公式称由命题变元P1,P2,…,Pn所产生的最小项。其中每个或为Pi,或为¬Pi，即Pi、¬Pi必出现一个，且只