离散数学的命题逻辑

数理逻辑:命题逻辑2逻辑逻辑不仅对理解数学推理十分重要，而且在计算机科学中有许多应用。这些逻辑规则用于计算机电路设计、计算机程序构造、程序正确性证明等许多方面！3Copyright2007@byXuDezhi3逻辑学逻辑学=研究正确推理的科学推理：由一个或几个命题推出另外一个命题的思维形式。逻辑学的作用1、有助于准确、严密地表达和交流思想。2、有助于培养、提高认知能力，获得间接知识。3、有助于识别、驳斥谬误和诡辩，进行批判性思维。数理逻辑：用数学方法研究推理的一门学科一套符号体系+一组推理规则4Copyright2007@byXuDezhi4逻辑学逻辑学关注的是陈述（命题）之间的关系。例如:我的表是数字的.所有数字设备都依靠电池运行.因此，我的表依靠电池运行注意：逻辑学并不关心前面两个陈述（命题）的真假。但是，如果它们是真的，则推论也一定是真的。5命题：凡是具有确定真假意义的陈述句均称为命题。命题的值:若为“真”，用Ｔ或１表示；若为“假”，用Ｆ或０表示。由于一个命题的值只可能取“真”或“假”两种值，因此，命题逻辑也称为“二值逻辑”。延伸阅读:模糊逻辑基本概念:命题与命题的值6下面三类陈述句是命题：1.现实可判断真假的陈述句。2.目前还不知道真假，但它们本身是具有真假意义的。3.其真假与讨论问题范围（论域）有关的陈述句（如：所有的人都爱跑步）。下面的不是命题：感叹句，疑问句，祈使句,非命题陈述句：悖论语句(如:我正在说谎)。7例：1)地球绕着月亮转。2)1+1=3。3)禁止烟火！4)地球有一天会爆炸。5)明天会下雨吗？6)x5.7)如果明天天气晴朗，我就到湘江边散步。8)如果太阳从西边升起,我就可以长生不老。9)火星上有水。8简单命题(原子命题）——它不能再分解成更简单的命题。在命题逻辑中，简单命题被看作是一个整体，不再分析其内部的逻辑形式。常用大写字母：P，Q，R，…..表示简单命题。例如：P:4是质数，Q：所有人都爱学习简单命题与复合命题9复合命题（命题的组合）复合（杂）命题——命题可以通过逻辑联接词构成新的命题，即复合命题。复合命题的子命题也可以是复合命题。例如：如果明天天气晴朗，我就到湘江边散步。如果太阳从西边升起,我就可以长生不老。10命题可以通过一些逻辑联结词构成新的命题（复合命题）1.否定词:定义：设Ｐ是命题，复合命题“Ｐ”是Ｐ的否定，规定Ｐ为真当且仅当Ｐ为假。例：Ｐ：长沙的秋天景色很美。Ｐ：Q:上海处处都清洁。Q：五种常用的命题（逻辑）联接词11定义：设Ｐ，Ｑ是命题，复合命题“Ｐ并且Ｑ”称为Ｐ和Ｑ的合取,写成Ｐ∧Ｑ。Ｐ∧Ｑ为真当且仅当Ｐ与Ｑ同时为真。真值表如下：ＰＱＰ∧Ｑ００００１０１００１１１2.合取词“∧”12定义：设Ｐ，Ｑ是命题，复合命题“Ｐ或者Ｑ”称为Ｐ和Ｑ的析取,记为Ｐ∨Ｑ。Ｐ∨Ｑ为真当且仅当Ｐ与Ｑ至少有一个为真。真值表如下：ＰＱＰ∨Ｑ００００１１１０１１１１3.析取词“∨”13定义：设Ｐ，Ｑ是命题，复合命题“如果Ｐ，则Ｑ”称为Ｐ蕴涵Ｑ,记为:ＰＱ。称Ｐ为条件，Ｑ为结论。规定ＰＱ为假当且仅当Ｐ为真而Ｑ为假。ＰＱＰＱ００１０１１１００１１１4.蕴涵词“”P→Q“如果P,则Q”“P是Q的充分条件”“Q是P的必要条件”“Q每当P”14在日常生活中,蕴含式中条件与结论是有逻辑联系的，即有因果关系，称为即形式蕴含.在数理逻辑中,蕴含式中条件和结论不一定有因果关系，即实质蕴含。例：如果太阳从西方升起，我就可以长生不老。逆命题ofp→q:q→p逆反命题ofp→q:¬q→¬p形式蕴含与实质蕴含15定义：设Ｐ，Ｑ是命题，复合命题“Ｐ当且仅当Ｑ”称为Ｐ等值Ｑ。记为：ＰＱＰＱ为真当且仅当Ｐ与Ｑ同时为真或同时为假。ＰＱＰＱ００１０１０１００１１１5.等值(双条件)联接词“”16例：非本仓库工作人员，一律不得入内。令P：某人是仓库工作人员；Q：某人可以进入仓库。则上述命题可表示为：PQ17命题的符号化使用上面介绍的逻辑联结词,可将一些自然语句翻译成逻辑式.即命题符号化.（1）从语句中分析出各原子(简单)命题，将它们符号化(用字母表示)（2）使用合适的命题联结词，把原子命题逐个联结起来，组成复合命题的符号化表示。18例：用符号形式表示下列命题。（1）如果明天早上下雨或下雪，那么我不去学校（2）如果明天早上不下雨且不下雪，那么我去学校。（3）如果明天早上不是雨夹雪，那么我去学校。（4）只有当明天早上不下雨且不下雪时，我才去学校。令P：明天早上下雨；Q：明天早上下雪；R：我去学校。（1）（P∨Q）→¬R；（2）（¬P∧¬Q）→R；（3）¬(P∧Q）→R（4）R→(¬P∧¬Q）19例:不是鱼死，就是网破设Ｐ：鱼死，Ｑ：网破则为：(P∧¬Q)∨(¬P∧Q)注意:命题符号化时,由于自然语言丰富多彩且有时还具有二义性，只有在具体的语言环境中，每个联接词才有确切的含义，因此具体问题要具体分析;复合命题的真值只取决于构成它的各原子命题的(真）值，而与这些原子命题的具体内容无关。20上面定义的五个联结词，他们各自可以表示自然语言中的一些常用语句。要表达更复杂的语句，还可能会用到多个联结词，形成更复杂的复合命题。21基本定义：命题变元与命题公式2．命题变元：一个没有指定具体内容的命题符号：即命题的真假没有指定。如果没对一个命题变元赋以内容时，它的值不能确定，一旦用一个具体的命题代入，它的真值就确定了。1.命题常元：一个表示确定命题的大写字母：即命题的值已确定。22命题公式命题公式（或简称公式）是由命题常元（T和F）、命题变元以及命题联结词按一定的规则产生的符号串。定义（命题公式的递归定义。）（1）单个命题符号是公式；（2）如果A是命题公式，则¬A是命题公式；（3）如果A和B是命题公式，则（A∨B），（A∧B）,(A→B）,(AB）也是命题公式；有限次地利用上述（1）—（3）而产生的符号串是命题公式。23例1判断下列符号串是否为命题公式。（1）(P→(Q∧PR）)；（2）((P∨Q)→(¬(Q∧R)))为了省掉一些括号,作如下约定：1.五种连接词的运算优先级的次序由高到低如下：，，，，2.多个同类联接词按从左到右的优先次序运算。3.公式（A）的括号可省略4.整个公式的最外层括号可省略24例：以下符号串是命题公式，可按定义生成。（（P）（（PQ）R）Q））按约定可省掉一些（）简化写成：P（PQ）RQ25命题公式的真假值是不确定的。当命题公式中所有的命题变元都代以命题时，命题公式就变为命题。即所有公式中的命题变元用指定的命题（真值）代入（或指派），就得到一个公式的值。262.公式的解释(指派)设G是命题公式，A1，A2，……An是出现在G中的所有命题变元，指定A1,A2,……An的一组真值（a1,a2,……an)ai｛T,F｝,i=1,……n,则这组真值称为公式G的一个解释。例如公式:(P∧¬Q)的解释为:(T,T)(T,F),(F,T),(F,F)或表示为:(1,1),(1,0),(0,1),(0,0)由定义知，含n(n1)个命题变元的命题公式共有2n个不同的解释。可以采用真值表的方法，将一个命题公式的所有解释与公式的真值对应起来，形成该命题公式的真值表。27ＰＱＰＱ００１０１１１００１１１例：公式：ＰＱ在解释(0，0)，(0，1）和（1，1）下为真，在其他解释下为假。公式的真值表28(P→Q)∧R的真值表PQR(P→Q)∧R0000111100110011010101010101000129判断p(qr)和（pq)(pr)是否等值的真值表30逻辑运算和位运算计算机用位（bit)表示信息。位是一个具有两个可能值的符号，即0和1。计算机的位运算对应于逻辑联结词。只要在位运算符∧(AND），∨（OR）和⊕（XOR）的真值表中用1代替T，用0代替F即可。信息一般用位串(即0和1构成的序列)表示。对位串的运算即可用来处理信息。xyxORyxANDyxXORy0011010101110001011031命题逻辑的应用逻辑在数学、计算机科学一其他许多学科有着重要的应用。例如，数学，自然科学以及自然语言中的语句通常不太准确，甚至有歧义，为了使其精确表达，可以将它们翻译成逻辑语言。32命题逻辑应用实例1.系统规范说明:在描述硬件系统和软件系统时，系统和软件工程师根据自然语言描述的需求，生成精确而无二义性的规范说明，这些规范说明可作为系统开发的规范说明。例1:使用逻辑联结词表示规范说明:“当文件系统已满时，不能够发送自动应答”。令p表示：能够发送自动应答，令q表示:文件系统满了。则该规范说明可以表示成:q→¬p33命题逻辑的应用例2:确定下列系统规范说明是否是一致的。“诊断消息存储在缓冲区中或者被重传.”“诊断消息没有存储在缓冲区中。””如果诊断消息存储在缓冲区中，那么它被重传。”（备注:三个规范说明都能同时为真则表示是一致的)。34布尔搜索逻辑联结词广泛用于大量信息搜索中。例如网页索引。由于搜索采用命题逻辑技术，所以称为布尔搜索。例:网页搜索。大部份Web搜索引擎支持布尔搜索技术，以有助于寻找有关特定主题的网页。基本都支持AND，OR及NOT等。(但用户不需要写出来)。35逻辑电路命题逻辑可应用于计算机硬件的设计。36思考题：利用命题逻辑解决问题问题：三人估计比赛结果，甲说“A第一，B第二”，乙说“C第二，D第四“，丙说”A第二，D第四“，结果三人的估计都对了一半，试确定A，B，C，D的名次。解：设P:A第一;Q:B第二;R:C第二S:D第四;H:A第二;则P┐Q,R┐S和H┐S的值都为1;而P∧H,Q∧R和Q∧H的值都为0;因此可得出:P和R及H的值为0,Q和S的值为1.由此得出:B第二,D第四,A第三,C第一371.2重言式定义：设G是一个命题公式。重言式：G在它的所有解释下均为真，则称G是永真的，或称G为重言式；矛盾式：若G在它的所有解释下均为假，则称G是永假的，或称G为矛盾式；可满足式：若G至少存在一个指派，使其值为真，则称G为可满足的，如果至少存在一个指派，使其值为假，则称此公式为非永真。38重言式（永真式）我们只研究重言式，因为：重言式的否定是矛盾式，矛盾式的否定是重言式。故只需研究其一。重言式的合取、析取、蕴含、等值等都是重言式，由简单的重言式可推出复杂的重言式。重言式中有许多非常有用的恒等式和永真蕴含式。39例如：P∨P：重言式P∧P：矛盾式(PQ)∧R：偶然式（可满足式）40定义：对于公式A和B，如果在任何相同的解释下，其相应的值都相同，则称A与B逻辑等值（价），记为：AB。读作“A等价于B”。或者说如果AB是重言式,则称AB.注意:符号“”是关系符，不是逻辑联结词。AB当且仅当AB是重言式。恒等式41基本的逻辑恒等式（P8-P9）1.双重否定律：PP2.等幂律：PP∨P，PP∧P3.交换律：P∨QQ∨P，P∧QQ∧P4.结合律：(P∨Q)∨RP∨(Q∨R)(P∧Q)∧RP∧(Q∧R)5.分配律：P∧(Q∨R)(P∧Q)∨(P∧R)P∨(Q∧R)(P∨Q)∧(P∨R)6.DeMorgan律：（P∨Q）P∧Q（P∧Q）P∨Q7.吸收律：P∧（P∨Q）PP∨（P∧Q）P8.零律：P∨11P∧009.同一律：P∨0PP∧1P10.补余律：P∨P1P∧P0补充：PQP∨QPQ┐Q┐PPQ(PQ)∧(QP)(P∧Q)∨(┐P∧┐Q)(P(QR)P∧QR43思考1思考:对联结词是否还可以归约,即五种联结词是否都是必要的?如果能归约,能归约到什么程度?44恒等式的判别：真值表方法和命题演算方法例1用真值表方法证明E10：(PQ)PQPQ00011110(PQ)1000PQ10001111(PQ)PQ45例2用真值表方法证明