第二章 命题逻辑.ppt

离散数学,2.1命题符号化及联结词,2.2真值表与逻辑等价,2.3永真蕴含式,2.4推理理论,第二章命题逻辑,离散数学,研究人的思维形式和规律的科学称为逻辑学。由于研究的对象和方法各有侧重而又分为:形式逻辑、辩证逻辑、数理逻辑数理逻辑数学家希尔伯脱:“它把数学上的形式的方法，应用到逻辑领域的结果。”数理逻辑是一门用数学方法来研究推理规律的科学。所谓数学方法主要是指引进一套符号体系的方法，所以数理逻辑也称做符号逻辑。,离散数学,近年来，数理逻辑与计算机科学的关系日益密切，数理逻辑的大量方法已运用于计算机软件的理论研究中，可以这样说,数理逻辑在计算机科学的应用前景是极其广阔的。,离散数学,2.1命题符号化及联结词,任何基于命题分析的逻辑称为命题逻辑。命题是非真即假的陈述句。首先判断它是否为陈述句其次判断它是否有唯一的真值,离散数学,真值只有两个：真或假记作:True和False符号：T和F1和0,离散数学,【例1】下述各句是否为命题：（1）4是偶数。（2）煤是白色的。（3）几何原本的作者是欧几里德。（4）2190年人类将移居火星。（5）地球外也有生命存在。,（1）、（3）是真命题，（2）是假命题,（4）（5）结果目前谁也不知道，但其真值是客观存在的，因而是命题,离散数学,【例2】下列语句是否为命题：（1）你好吗？（2）好棒啊！（3）请勿吸烟。（4）x3。（5）我正在说谎。,（1）（2）（3）不是陈述句,是陈述句，但它的真假取决于变量x的取值，（4）不是命题,悖论，因而也不是命题。,离散数学,几个有趣的悖论,说谎者悖论：“我正在说谎。”他到底说没说谎？江湖传言悖论：没有人能避开西门吹雪的那一剑；陆小凤的灵犀指可以夹住任何兵器的来袭。这两个人交手的话，胜负如何？相对悖论：世上没有绝对的真理。这是绝对的吗？苏格拉底悖论：我现在唯一知道的事，就是我一无所知。知道还是不知道？,离散数学,性质悖论：一切都是可能的，不可能也是如此。可能还是不可能？麦堆悖论：一粒麦子构不成麦堆，两粒也不行，三粒也不行所以无论多少麦粒都不能构成麦堆。肯定错了，但是错在哪里了？语言悖论：这句话包含七个字。对还是错？说明：以上不都是命题逻辑中讲的悖论，同学们可以课余自行考虑。,离散数学,命题是非真即假的陈述句。一个陈述句在客观上能判断真假，而不受人的知识范围的限制。一个陈述句暂时不能确定真值，但到了一定时候就可以确定，与一个陈述句的真值不能唯一确定是不同的。只有说法“真值为真”或“真值为假”没有假值一说。,离散数学,(1)中华人民共和国首都是北京。(2)2是偶数。(3)雪是黑色的。(4)我是工程师。(5)外太空有生命(6)明天开会吗？(7)多美妙啊！(8)请进来。(9)我正在说假话,离散数学,以上所讨论的命题均是一些简单陈述句。在语言学中称为简单句，其结构均具有“主语+谓语”的形式，在数理逻辑中，我们将这种由简单句构成的命题称为简单命题，或称为原子命题，用p、q、r等符号表示（必要时亦可用其它小写的英文字母表示）。如：p：4是偶数。q：煤是白的。r：几何原本的作者是欧几里德。,离散数学,根据命题的构成形式，可以将命题分为：原子命题:不能再细分的命题称为原子命题。复合命题：由原子命题和命题联结词构成。“明天下雪”“4是素数”都是原子命题“明天下雨或明天下雪”是复合命题,离散数学,【例3】下列命题不是简单命题：（1）4是偶数且是2的倍数。（2）北京不是个小城市。（3）小王或小李考试得第一。（4）如果你努力，则你能成功。（5）三角形是等边三角形，当且仅当三内角相等。,离散数学,命题常量：表示具体命题的命题标识符例如,P:今天天气晴好。则P是命题常量命题变元：未指定具体命题，可以代表任意命题的命题标识符。集合T,F是命题变元的值域。指派：命题变元用一个特定命题取代，从而成为一个命题，这个过程称为对命题变元进行指派。,离散数学,用P表示任意的命题，则是命题变元，没有确定的真值；当用具体的命题，如“雪是黑色的”代入后，P就表示命题：雪是黑色的，这时有确定真值：F。,离散数学,联结词是复合命题的重要组成部分，又称为逻辑运算符。常用的有五种：否定合取析取排斥析取条件双条件,离散数学,由命题和联结词构成的命题称为复合命题。构成复合命题的可以是原子命题，也可以是另一个复合命题。一个复合命题的真值不仅与构成复合命题的命题的真值有关，而且也与所用联结词有关。,离散数学,设p为任一命题，复合命题“非p”（p的否定）称为p的否定式，记作：为否定联结词。为真，当且仅当p为假。,的真值亦可由表6.1.1所示的称为“真值表”的表格确定。由表6.1.1可知：命题p为真，当且仅当为假。,离散数学,表6.1.1,【例】(1)p：4是偶数。其真值为1。：4不是偶数。其真值为0。(2)q：这些都是男生。：这些不都是男生。,离散数学,否定联结词使用的原则：将真命题变成假命题，将假命题变成真命题。但这并不是简单的随意加个不字就能完成的。例如上例中的（2），q的否定式就不能写成“这些都不是学生”。事实上严格来讲，“不是”不一定否定“是”。不过，一般地，自然语言中的“不”、“无”、“没有”、“并非”等词均可符号化为,离散数学,设p、q是任意两个命题，复合命题“p且q”（p与q）称为p与q的合取式，记作：pq。“”是合取联结词。pq为真，当且仅当p、q都为真。,表6.1.2,离散数学,例如P:张静是个女人。Q:张静是个老师。上述命题的合取为：PQ：张静是个女人并且是个教师。PQ：张静是个女教师。显然只有当“张静是个女人”与“张静是个教师”都是真时，“张静是个女教师”才是真的。,离散数学,【例】(1)p：4是偶数。q：3是素数。则pq：4是偶数且3是素数。真值为1。(2)r：煤是白的。则pr：4是偶数且煤是白的。真值为0。,离散数学,注意：联结词合取的概念与自然语言中的“与”“并且”，意义相似，但并不完全相同。P:我们去香山看红叶。Q:教室里有两块黑板。PQ:我们去香山看红叶与教室里有两块黑板。在自然语言中，上述命题是没有意义的，因为P与Q没有什么联系，但作为数理逻辑中的命题P和Q的合取PQ来说，它仍可作为一个新的命题,离散数学,设p、q是任意两个命题，复合命题“p或q”称为p、q的析取式，记作：pq。“”称为析取联结词。pq为假，当且仅当p、q同为假。,表6.1.3,离散数学,【例】(1)p：小王喜欢唱歌。q：小王喜欢跳舞。则pq：小王喜欢唱歌或喜欢跳舞。(2)p：明天刮风。q：明天下雨。则pq：明天或者刮风或者下雨。“”的逻辑关系是明确的。即p、q二命题中至少有一个为真则析取式为真。因而，自然语言中常用的联结词诸如：“或者或者”、“可能可能”等，都可以符号化为“”。,离散数学,（1）P：我吃香蕉。Q：我吃橘子。R：我吃香蕉或橘子。这里的“或”是“兼并或”，可以同时为真。因此可以符号化为PQ（2）P：今晚我在家复习功课。Q：今晚我去图书馆查阅资料。R：今晚我在家复习功课或去图书馆查阅资料。这里的或是“排斥或”，可以符号化为,离散数学,日常语言中的“或”是具有二义性的，用“或”联结的命题有时是具有相容性的，我们称之为可兼或。而有时用“或”联结的命题又具有排斥性，称为不可兼或（异或），如：（1）小李明天出差去上海或去广州。（2）刘昕这次考试可能是全班第一也可能是全班第二。,离散数学,设P、Q是命题，P和Q的排斥析取也是个命题,记作。当且仅当P和Q的真值不相同时，为T，在其他情况下,的真值都是F。,离散数学,例1请指出下列命题中的“或”是析取还是排斥析取。（1）我吃面包或蛋糕。（2）今晚我去看演出或在家里看电视现场转播。（3）他是一百米冠军或跳高冠军。（4）今晚九点，中央电视台一台播放电视剧或足球比赛。（5）派小王或小赵出差去上海。（6）派小王或小赵中的一个出差去上海。其中1、3、5中的“或”为析取，2、4、6中的“或”为排斥析取。,离散数学,设p、q是任意两个命题，复合命题“如果p，则q”称为p与q的蕴含涵式，记作：pq。P称为蕴含式的前件，q称为蕴含式的后件，称为蕴含联结词。pq为假，当且仅当p为真、q为假。,离散数学,表6.1.5,离散数学,（1）P：天不下雨Q：我去看电影PQ：如果天不下雨，那么我去看电影。（2）P：我生病。Q：我不到学校去。PQ：如果我生病，那么我不到学校去。条件命题PQ用自然语句可读作“如果P则Q”,离散数学,【例】(1)p：天下雨了。q：路面湿了。pq：如果天下雨，则路面湿。(2)r：三七二十一。pr：如果天下雨，则三七二十一。,离散数学,pq的逻辑关系是：p是q的充分条件，q是p的必要条件。q是p的必要条件还有许多不同的叙述方式，均可符号化成pq的形式。如：“p仅当q（仅当q，则p）”、“只有q才p”、“只要p就q”、“除非q，否则非p（非p，除非q）”,离散数学,在数理逻辑中，联结词所联结的命题可以毫无关系。,逻辑中，作为一种“善意推断”的规定，前件p为假时，无论后件q是真是假，蕴含式pq的真值均为1。这与日常语言中的，特别是数学上常用的“真蕴含真”不太一样。事实上并不矛盾。,“如果张三能及格，那太阳从西边升起”它所要明确的是“张三能及格”是假命题。,离散数学,只要天不下雨，我就骑自行车上班只有天不下雨，我才骑自行车上班解：设P：天下雨，Q：我骑车上班(1)(2),离散数学,设p、q是任意两个命题，复合命题“p当且当q”称为p与q的等价式，记作：pq。“”称为等价联结词。pq为真，当且仅当p、q真值相同。,表6.1.6,离散数学,例如，(1)P：G是无向树。Q：G是无回路的连通无向图。PQ：G是无向树，当且仅当G是无回路的连通无向图。(2)P：G是无向欧拉图。Q：G是各结点的度数为偶数的无向连通图。PQ：G是无向欧拉图，当且仅当G是各结点度数为偶数的无向连通图。,离散数学,例设P表示命题“天下雪”。Q表示命题“我去看电影”。R表示命题“我有时间”。试以符号形式表示下列命题：(1)天不下雪。(2)如果天不下雪。那么我去看电影。(3)我去看电影，仅当我有时间。(4)如果天不下雪且我有时间，那么我去看电影。,P(2)PQ(3)QR(4)(PR)Q,离散数学,例3请将下列命题符号化(1)如果天不下雪，那么我去看电影；否则我不去看电影。(2)如果天不下雪，那么我去看电影；否则我在家里复习功课。解令P表示命题“天下雪”。Q表示命题“我去看电影”。R表示命题“我在家里复习功课”。用符号表示命题(1)：PQ用符号表示命题(2)：(PQ)(PQ),离散数学,【例】将下列自然语言形式化:（1）如果天不下雨并且不刮风，我就去书店。（2）小王边走边唱。（3）除非a能被2整除，否则a不能被4整除。（4）此时，小纲要么在学习，要么在玩游戏。（5）如果天不下雨，我们去打篮球，除非班上有会。,解：（1）设p：今天天下雨，q：今天天刮风，r：我去书店。则原命题符号化为：,解(2)设p：小王走路，q：小王唱歌。则原命题符号为：pq,解：(3)设p：a能被2整除，q：a能被4整除。则原命题符号化为：,解(4)设p：小刚在学习，q：小刚在玩游戏。则原命题符号化为：,解(5)设p：今天天下雨，q：我们去打篮球，r：今天班上有会。则原命题符号化为：,离散数学,补充：联结词的优先顺序,最优先；与同级别；与同级别；若有括号，则括号优先，同级别按从左到右顺序演算,离散数学,6.2真值表与逻辑等价,1单个的命题变元（或常元）是合式公式。2如果A是一个合式公式，则（A）也是合式公式。3如果A、B均是合式公式，则（AB）、（AB）、（AB）、（AB）也都是合式公式。4只有有限次地应用1、2、3组成的字符串才是合式公式。,离散数学,定义6.2.1在命题公式中，对于各分量指派所有可能的真值从而确定命题公式的各种真值，把它会列成表，就是命题公式的真值表。,离散数学,将公式A在所有赋值情况下的取值列成表，称为A的真值表。构造真值表的步骤如下：,课本例题,离散数学,【例】求下列命题公式的真值表：,(2)公式的真值表如表6.2.2所示。(3)公式(pq)r的真值表如表6.2.3所示。,解(1)公式的真值表如表6.2.1所示。,离散数学,表6.2.1,离散数学,表6.2.2,离散数学,表6.2.3,离散数学,由定义可知，任何不是矛盾式的公式是可满足式。,离散数学,【例】构造下列公式的真值表,解：上述公式的真值表如表6.3.1,表6.3.1,离散数学,由例题可见，的真值表是完全相同的。事实上，给定n个命题变元，按照公式的生成规则，我们可以得到无穷多个命题公式，但这无穷多个命题公式的真值表却只有有限个。,离散数学,在真值表中，两个命题公式A和B,在分量的不同指派下，其真值总是相同的，则称这两个命题公式A和B是逻辑等价的记作,离散数学,利用真值表进行证明牢记本题结论,例题见板书,离散数学,【例】证明等价等值式：AB(AB)(BA)。解作如表6.3.2所示的真值表。,表6.3.2,因此，AB(AB)(BA)。,离散数学,小结,命题是客观上能判明真假的陈述句，当命题为真时，称命题的真值为“真”，否则，说命题的真值为“假”。析取联结词指的是“兼并或”，而汉语中的或，既可以是“兼并或”，也可以是“排斥或”复合命题,表示的逻辑关系是Q是P的必要条件，P是Q的充分条件在数学中,”如P，则Q”,往往要求前件为真，后件为真的推理关系在数理逻辑中规定，当前件为假，不论后件为真为假，均为真。,离散数学,将公式A在所有赋值情况下的取值列成表，称为A的真值表。构造真值表的步骤如下：,课本例题,离散数学,在真值表中，两个命题公式A和B,在分量的不同指派下，其真值总是相同的，则称这两个命题公式A和B是逻辑等价的记作,离散数学,(1)双重否定律对合律(2)幂等律(3)交换律(4)结合律(5)分配律,利用真值表我们可以证明许多等值式：,离散数学,(7)吸收律(8)零律(9)同一律(10)否定律,(6)德摩根律,离散数学,逻辑等价相关定理,定理2.1设P、Q、R命题公式是命题公式，如果则定义2.12设P、Q是命题公式，且P是Q的一部分，则称P为Q的子式。定理2.2设命题公式,如果P是命题公式R的子式，在R中出现P的地方用Q代换后（不一定每一处）得到命题公式S,则,离散数学,离散数学,2.3永真蕴含式,符号不是联结词，它表示公式间的“永真蕴含”关系，也可以看成是推导关系。即可以理解成由P可推导Q,（即由P为真可推出Q为真）,离散数学,例如：,由此可知,离散数学,证明证明：,离散数学,证明证明：,课本采用真值表证明法,离散数学,简化规则,分析,离散数学,添加规则,离散数学,假言推理,拒取式、反证法,离散数学,析取三段论,离散数学,假言三段论,离散数学,二难推论,离散数学,2.3.2永真蕴含式的性质,性质1：如果，则,性质2：如果，则,离散数学,性质3：如果，,则,性质4：如果，且,则,离散数学,设P、Q、R是命题公式，如果则即永真蕴含是可传递的。证明由于PQ和QR，所以PQ和QR都是永真式，显然(PQ)(QR)也是永真式。由例3的证明结果可知，(PQ)(QR)(PR)，所以当(PQ)(QR)为永真式时，PR必为永真式。证毕。,离散数学,例题见板书,离散数学,2.4推理理论,推理是“前提结论”的思维过程。在命题逻辑中，前提是已知的命题公式，结论是从前提出发应用推理规则推出的命题公式。在传统数学中定理的证明均是由前提（已知条件，全是真命题）推出结论（亦全是真命题），这样的结论称为合法结论。,离散数学,定义2.14设和Q是命题公式，且有由永真蕴含的定义可知，的真值为T时，必然有Q的真值为T。常称为前提，Q为由这些前提推出的有效结论。,离散数学,在推理中常把写作：,离散数学,解：令P：我的论文通过答辩Q：我获得博士学位R：我很高兴由题意可知，前提R(PQ)(QR)结论：P即要证明：R(PQ)(QR)P由常用永真蕴含式可知R(PQ)(QR)R(PR)R(PR)P所以得到R(PQ)(QR)P,“如果我的论文通过答辩，那么我能获得博士学位；如果我获得博士学位，那么我很高兴；但我不高兴，所以我的论文没有通过答辩。”试指出前提和有效结论并证明之。,例,离散数学,例2分析下列事实：“如果小琨来了，那么我们就能下围棋；如果小静来了，那么我们也能下围棋；总之，不论小琨或小静来了，我们都能下围棋。”试指出前提和有效结论。解令P：小琨来了。Q：小静来了。R：我们能下围棋。由题意可知，前提：(PR)(QR)(PQ)，有效结论：R。既要证明(PR)(QR)(PQ)R由常用永真蕴含式(11)即得证明。,离散数学,证明是逐步进行的，每一步往往只对前提中的某一部分进行比较“处理”，而其他部分只是重复的抄一遍。为了使证明过程简单明了，下面介绍几种证明方法。,离散数学,直接证明法遵循以下两条规则：P规则前提在推导过程中的任何时候都可以引入使用。T规则在推导中，如果有一个或多个公式、永真蕴含着公式S，则S可引入推导中。,1.直接证明法,离散数学,例4证明(PQ)(PR)(QS)RS。证明(1)PQ利用p规则，引入前提(2)PQ由(1)，利用T规则(3)QS利用P规则，引入前提(4)PS由(2)、(3)，利用T规则(5)PR利用P规则，引入前提(6)RP由(5)，利用T规则(7)RS由(4)，(6)，利用T规则(8)RS由(7)，利用T规则为了简化书写，以后将“利用P规则，引入前提”简写做“P”；将“利用T规则”，简写作“T”。,离散数学,例5证明PQ，QR，R，(PS)S，(逗号“，”和“”的含义相同)。证明(1)PQP(2)QRP(3)QRT(2)(4)PRT(1),(3)(5)RP(6)PT(4),(5)(7)(PS)P(8)PST(7)(9)PST(8)(10)ST(6),(9),离散数学,例6证明(AB)(CD)，(DF)EAE证明(1)(AB)(CD)P(2)(AB)(CD)T(1)(3)(AB)C)(AB)D)T(2)(4)(AB)DT(3)(5)(AB)DT(4)(6)(AD)(BD)T(5)(7)ADT(6)(8)ADT(7),离散数学,(9)(DF)EP(10)(DF)ET(9)(11)(DF)ET(10)(12)(DE)(FE)T(11)(13)DET(12)(14)DET(13)(15)AET(8),(14),离散数学,2.间接证明法设有一组前提P1、P2、Pn，要推出结论Q，既证明即证明即证明即证明(,离散数学,利用摩根律，即证明由此可见，要证明，可将结论Q的否定Q加入到前提中去，然后再证明是永假式即可。,离散数学,间接证明法的另一种情况是利用CP规则。如果要证即证即证即证即证即证,离散数学,数理逻辑有所不同，它着重研究的是推理的过程，这种过程称为演绎或形式证明。在过程中使用的推理规则必须是公认的且要明确列出，而对于作为前提和结论的命题并不一定要求它们全是真命题，这样的结论称为有效结论。,离散数学,蕴含式（A1A2An）B为推理的形式结构，A1，A2，An为推理的前提，B为推理的结论。若（A1A2An）B是重言式则称由前提A1，A2，An推出结论B的推理正确B是A1，A2，An的有效结论或逻辑结论。记作：,（A1A2An）B（A1,A2,AnB),否则称推理不正确，或B不是前提A1，An的有效结论。,离散数学,【例6.6.1】验证下面推理是否正确：一个数是复数，仅当它是实数或是虚数，一个数既不是实数也不是虚数，因此它不是复数。证明设p：它是复数，q：它是实数，r：它是虚数。推理的形式结构为：（p（qr）（qr）p（1）真值表法(真值表如表1.6.1所示)。因为只有第一行前提、结论均为真，所以推理正确。,离散数学,表6.6.1,离散数学,（2）等值演算法：,（蕴涵等值式）（德摩根律）（分配律、排中律）（同一律）（蕴涵等值式）（德摩根律）（交换律、排中律）（零律）,离散数学,推理规则：前提引入规则在证明的任何步骤上，都可以引入前提。结论引入规则在证明的任何步骤上，所得到的结论均可