8.1命题与逻辑连接词详解课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第八章 命题逻辑基础,我们在日常生活中经常会遇到推,理.日常生活中使用的语言常称为,自然语言或元语言，而自然语言,含义丰富，有时甚至含糊多义。,例如我们说三句带“是”的语句：,孔子是孔仲尼；,孔子是人；,人是动物。,这三句中 “是”的符号含义分别为,“=”、“”、“,”。,因此用自然语言进行的推理非常,灵活，结论不定。,数理逻辑（mathematical logic）,是用数学的方法来研究推理的一,门学科，它采用一套符号来简洁,地表达命题及其间的关系。,因此它表示的含义单一、明确，,在给定前提下会有确切的结论。,计算机科学中有两个常用的公式：,程序,=,算法,+,数据；,算法,=,逻辑,+,控制。,著名计算机软件设计大师戴克斯,特拉（）曾经这样,说：“我现在年纪大了，搞了这,么多年软件,错误不知犯了多少，,现在觉悟了。我想，假如我早年,在数理逻辑上好好下点功夫的话,我就不会犯这么多的错误。不少,东西逻辑学家早就说了，可我不,知道。要是我能年轻20岁的话，,就要回去学逻辑。”,我国著名数理逻辑学家甚至说得,更加直截了当：“事实上，程序设,计或者就是数理逻辑，或者是用,计算机语言书写的数理逻辑，或,者是数理逻辑在计算机上的应用”.,可以说计算机的本质结构就是逻,辑结构。,数理逻辑是计算机程序设计、硬,件逻辑设计以及人工智能等学科,的重要理论基础。有趋势表明：,微积分在人类体力劳动自动化的,过程中扮演了重要角色，数理逻,辑在人类脑力劳动自动化的过程,中将起越来越大的作用。,数理逻辑的两个最基本逻辑-,命题逻辑和谓词逻辑的基础。,8.1 命题与逻辑连接词,8.1.1 命题,命题逻辑以命题作为研究对象，,那么什么叫命题呢？,今天北京是阴天。,我们班是三好班集体。,1/5是自然数。,公鸡能下蛋。,象这些表示判断的语句都是命题.,命题（propositions）是表示判断,的陈述句。,尽管这些判断有些是符合事实的,有些是不符合事实的。,符合事实的判断其命题真值为真,记为“T”或“1”,；,不符合事实的判断其命题真值为,假，,记为“F”或“0”,。,因此一个命题的真值一定为“真、,假”其中的一个（也有其他的逻辑,不这样定义，如第,10,章的多值逻,辑和模糊逻辑）。,例 判断下列语句哪些是命题；,对于是命题的其真值是什么？,（,1,）台湾是中国的一部分。,（,2,）多伦多是加拿大的首都。,（,3,）,2,是偶数并且也是素数。,（,4,）天津解放的那天有,100,个,婴儿出生。,（,5,）大于,2,的偶数均可分解为两,个质数的和（哥德巴赫猜想）。,（,6,）第,29,届奥林匹克运动会开幕,时北京天晴。,（,7,）好过瘾啊！,（,8,）你去上机吗？,（,9,）请随手关门！,（10）我希望有一台笔记本电脑。,（,11,）我只给那些不给自己刮胡,子的人刮胡子。,解：,（1），（2），（3）,都是命题，,（1）,（3）,真值为真,（2）,真值为假。,（4）,（5），（6）,也是命题，,（7）是感叹句,（8）是疑问句,（9），（10）,都是祈使句,它们都不表示一个判断，,因此都不是命题。,（11）,是著名的理发师悖论，,悖论是自相矛盾的，即无论真假,都会导致矛盾，,（11）,将导出“我”既不能给自己,刮胡子，又不能不给自己刮胡子,的矛盾结论。故它不是命题。,例 判断下列语句哪些是命题；,(1),a,b,(2),x,y,(3) 我正在说假话。,(4) 本命题是假的。,是命题,不是命题,不是命题,不是命题,原子命题,(,atoms,),或简单命题,命题表示的都是一个基本的判断,由一个主语和一个谓语构成。,复合命题,compositive,propositions,由两个或更多个原子命题和连词,组成的命题,逻辑连接词（,logical connectives,）,或命题连接词,连接原子命题的连接词,原子命题非常简单,它只有真或假,而复合命题的真值不仅要依赖于,组成它的原子命题的真值，而且,更要依赖于连接原子命题的逻辑,联接词。因此逻辑联接词是逻辑,重要而基本的内容。,一般用大写英文字母或带下标的,大写字母如,P,，,Q,，,A,，,B,，,P,1,P,2,，,来表示命题，并且若,P,表示一个确切的命题，则称其为,命题常元,propositional constants,若,P,表示任意一个命题，则称其为,命题变元,propositional variables,。,对一个命题变元指定它一个命题,或一个真值，我们叫做赋值或真值,指派(,assignments,)，而更多的我们,是给命题变元一个真值指派，,因为在逻辑演算和推理中我们更,关心它的真值。,例 将下列命题写成原子命题与连,接词的复合,(1) 6是偶数是不对的。,(2) 6是偶数且是3的倍数。,(3) 6是偶数或是3的倍数。,(4) 如果6是偶数，则3是奇数。,(5) 6是偶数当且仅当3是奇数。,解:本例中的,5,个语句都是复合命题,都是由原子命题通过自然语言中的,连接词复合而成的。若将涉及到的,原子命题符号化如下，,P,: 6是偶数,q,: 6是3的倍数,r,: 3是奇数,则,5,个复合命题表示为,(1) 非,p,(2),P,且,q,(3),p,或,q,(4) 如果,p,，则,r,(5),p,当且仅当,r,上述出现的非、且、或、如果,则,当且仅当等都是自然语言中常用的,连接词，但自然语言中的连接词,可能有二义性。为排除二义性, 在,数理逻辑中必须给出连接词的严格,定义，并用特定符号表示。,8.1.2 逻辑连接词,例 下列语句都是复合命题，,其中带下划线的词为逻辑连接词,（1）3,不,是奇数（并非3是奇数）,（2）今晚我去书店,或者,去打球。,（3）他去了教室，,也,去了实验室,（用“也”表示逻辑联结词“并且”）,（4）你作硬件，我作软件。,（用逗号表示逻辑联结词“并且”）,（5）,如果,有辆车,那么,我去接你。,（6）偶数,a,是质数,当且仅当,a,=2.,五个逻辑联接词,否定词(negation)“并非”（not），,用符号,表示。,设,P,表示一命题，,那么,P,表示命题,P,的否定。,P,真时，,P,假，,P,假时，,P,真。,P,读作 “非,P,”,其真值状况,P,P,0,1,1,0,设,P,表示“,3,是奇数”，,则“,3,不,是奇数”表示为,P,，,P,的真值为真，,P,的真值为假。,设,P,表示“整数都是自然数”，,则,P,表示“并非整数都是自然数”,或“整数不都是自然数”，,而不是“整数都不是自然数”。,因为,P,的真值为假，,P,的真值应为真。,合取词(conjunction)“并且”（and）,用符号,表示。,设,P,，,Q,表示两命题，,那么,P,Q,表示合取,P,和,Q,所得的,命题，当,P,和,Q,同时为真时,P,Q,真，,否则,P,Q,为假。,P,Q,读作 “,P,且,Q,”。,其真值状况,P,Q,P,Q,0,0,1,1,0,1,0,1,0,0,0,1,设,P,：他去了教室，,Q,：他去了实验室，,则该命题可表示为,P,Q,。,他去了教室，,也,去了实验室,你作硬件，我作软件。,设,A,：你作硬件，,B,：我作软件，,则该命题可表示为,A,B,析取词(disjunction)“或”（or）,用符号,表示,设,P,，,Q,表示两命题，,那么,P,Q,表示,P,和,Q,的析取，,当,P,和,Q,有一为真时，,P,Q,为真，,只有当,P,和,Q,均假时,P,Q,为假。,P,Q,读作 “,P,或,Q,”。,其真值状况,P,Q,P,Q,0,0,1,1,0,1,0,1,0,1,1,1,今晚我去书店,或者,去打球。,设,P,：今晚我去书店，,Q,：今晚我去打球，,则该命题可表示为,P,Q,。,条件词(condition,如果，那么”,（,if,then,）,用符号,表示。,设,P,，,Q,表示两命题，,则,P,Q,表示命题“如果,P,那么,Q,”，,并且,P,称为前件，,Q,称为后件。,当,P,真而,Q,假时，命题,P,Q,为假,否则均认为,P,Q,为真。,P,Q,常读作“若,P,则,Q,”。,其真值状况,P,Q,P,Q,0,0,1,1,0,1,0,1,1,1,0,1,如果,有辆车,那么,我去接你。,设,P,：我有辆车，,Q,：我去接你，,则该命题可表示为,P,Q,。,注意：,P,Q,中允许前件,P,为假，,且此时无论后件,Q,是真还是假，,P,Q,的真值都为真。,许多程序设计语言中用,if,then,结构，与逻辑中使用的不同。,在程序设计中往往是,if p then S,，,其中,p,是命题，而,S,是一段程序。,当程序运行到这条语句时，,如果,p,为真，就执行,S,，,但若,P,为假，则,S,不执行。,“如果,2+2=5,，那么雪是黑的”,“如果我是美国总统，,我就不那样对待萨达姆”,都是真值为“真”的命题。,双条件词(bicondition)“当且仅当”,（,if and only if,）,用符号,表示之。,设,P,，,Q,为两命题，,则,P,Q,表示命题“,P,当且仅当,Q,”，,且当,P,与,Q,同真值时,P,Q,为真，,否则为假。,P,Q,读作“,P,双条件,Q,”,或“,P,当且仅当,Q,”。,其真值状况,P,Q,P,Q,0,0,1,1,0,1,0,1,1,0,0,1,偶数,a,是质数,当且仅当,a,=2.,设,P,：偶数,a,是质数，,Q,：,a,=2，,则该命题可表示为,P,Q,。,这五个联接词可看成是逻辑运算，,其中,是一元运算,，,，,，,是二元运算,。,上述五个联结词来源于日常使用,的相应词汇,但并不完全一致，在,使用时要注意：,以上联结词组成的复合命题的真,假值一定要根据它们的定义去理,解, 而不能据日常语言的含义去理,解。,不能“对号入座”，如见到“或”就,表示为“”。,在今后我们主要关心的是命题间,的真假值的关系, 而不讨论命题的,内容.,8.1.3 命题公式与真值表,当,P,Q,R,为命题常元即分别表示,某个确切的命题时,(,P,Q,),R,可表示一个更复杂的命题，而且,可根据,P,Q,R,的真值来确定这个,复杂命题的真值；而当,P,，,Q,，,R,为命题变元时，由于,P,，,Q,，,R,的,真值不确定因而（,P,Q,）,R,真值不确定因而（,P,Q,）,R,的真值也就无法确定，这个符号串,也就不能再是命题，我们称它为,命题公式，而且随着我们赋值给,P,，,Q,，,R,即对它们进行真值指派,这个符号串就会对应有一个真值，,而这个所谓命题公式的真值往往,要随它所含命题变元的真值变化,而变化。,定义,一个命题公式按如下规则生成：,（1）命,题常元和命题变元是命题,公式，也称为原子公式或原子。,（2）如果,A,，,B,是命题公式，,那么,A,(,A,B,),(,A,B,),(,A,B,),(,A,B,)也是命题公式。,（3）只有有限步使用规则(1),(2),所组成的符号串是命题公式。,一个命题公式就是一个合法的,符号串:(,P,R,),(,(,P,(,Q,R,),(,Q,P,)都是命题公式，,但(,PQ,),P,R,很明显都不合法，,因而都不是命题公式。,约定：,（1）公式最外层括号一律可省略,（2）联结词运算优先级依次为：,，(，)，,例:,P,Q,(,R,Q,S,) 所表示的,是公式(,P,)(,Q,(,R,Q,),S,),定义,B,称为公式,A,的子公式,如果,B,是公式,A,的一部分，,且,B,也为一公式。,真值表（truth table）,一个命题公式的真值往往要随它,所含命题变元的真值变化而变化，,把所有变化情况对应的汇总一张,表，即为该公式的真值表。,例 构造公式,P,Q,的真值表。,解：该公式的真值表为：,P,Q,P,P,Q,0,0,1,1,0,1,0,1,1,1,0,0,1,1,0,1,说明：,（1）若公式中含有两个命题变元,则真值组合共有4组；若公式中含,有三个命题变元，则真值组合共,有8组；即若公式中含有,n,个命题,变元，则真值组合共有2,n,组,且为,所有,n,位二进制数。,（2）为简化计算，可以逐步算出,各子公式的真值，最后求出所求,公式的真值。,例 求公式,（,P,Q,）,P,Q,的真值表。,解：该公式的真值表为：,P,Q,P,Q,(,P,Q,),P,Q,P,Q,(,P,Q,),P,Q,0,0,1,1,0,1,0,1,0,1,1,1,1,0,0,0,1,1,0,0,1,0,1,0,1,0,0,0,1,1,1,1,例求公式,(,p,(,Q,R,)的真值表,解：该公式的真值表为：,例求,p,(,q,r,), (,p,q,),r,的真值表,解：,8.1.4 语句的形式化,把命题和联接词都符号化了，,也就是说现在能够用符号即命题,公式来表示一个命题的语句了，,下面研究语句形式化问题。,语句形式化的步骤是：, 将所给语句所包含的原子命题,找出，并将它们用符号表示；, 选用恰当逻辑联接词，,将所给语句形式化；,式，使其能形式化，但一定要保, 必要时可将原语句改变描述方,持与原意等价。,例 将下列语句形式化：,（1）海洋聪明但不用功。,解：,设,A,：海洋聪明，,B,：海洋用功，,则原命题形式化为：,A,B,。,（2）我和你之间至少有一个要去,海南岛。,解：,设,P,:我去海南岛,Q,：你去海南岛,则原命题形式化为：,P,Q,。,（3）狗急跳墙。,解：,设,P,1,：狗急了，,P,2,：狗跳墙,则原命题形式化为：,P,1,P,2,。,（4）只有你购买的电脑不超过一,年，你的保修单才有效。,解：,设,A,：你购买的电脑超过了一年，,B,：你的保修单有效。,则原命题形式化为：,B,A,例 将下列语句符号化：,(1)仅当计算机无病毒,它才正常工作.,解：,设,P,：计算机有病毒，,Q,：计算机能正常工作，,则原命题符号化为：,Q,P,。,（2）除非我有特殊原因，,否则我不会放弃学习。,解：,设,P,：我有特殊原因，,Q,：我放弃学习，,则原命题符号化为：,P,Q,。,（3）如果他没来见你，,那么他或者是生病了，,或者是不在本地。,解：,设,P,：他来见你，,Q,：他生病，,R,：他在本地,则原命题符号化为:,P,(,Q,R,),（4）如果袁翼和王津都是聪明人,那么他们俩不会都去。,解：,设,P,：袁翼聪明，,Q,：王津聪明，,R,：袁翼会去，,S,：王津会去,则原命题符号化为：,(,P,Q,),(,R,S,)。,（5）风雨无阻，我去上学。,解：,设,A,：天刮风，,B,：天下雨，,C,：我去上学。,则原命题符号化为：,(,A,B,C,),(,A,B,C,),(,A,B,C,),(,A,B,C,),(6) 除非你已满16周岁，否则只要,你身高不足4英尺就不能乘公园滑,行铁道。,解：,设,A,：你已满16周岁,B,：你身高不足4英尺,C,：你能乘公园滑行铁道,则原命题符号化为：,(,A,B,C,),或(,C,A,B,),注意:一个语句形式化未必唯一。,