离散第9讲命题与逻辑联结词

,-,*,-,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第9讲 命题与逻辑联结词,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,专业基础课程,授课人：张桂芸,PowerPoint,Template_Sub,逻辑学是一门非常古老的学科，到现在已经有了两千多年的历史。古典逻辑学主要起源于古希腊学者亚里士多德的逻辑学说，他的,工具论,是古代一部最完备的逻辑学著作。,古典逻辑学的基本特点是用自然语言描述对逻辑的研究，而一旦超出这个范围，,引入数学的方法,来研究逻辑，就产生了远远优于古典逻辑学的,现代逻辑学,。,数理逻辑,也称,符号逻辑,，是现代逻辑学研究的主体部分，是一门,运用数学方法研究思维规律的学科,。将推理变成数学演算，是数理逻辑的指导思想，并且已经成为这门学科的主要特征,。,数理逻辑是用形式化,(,符号化,),方法来研究推理的科学。,孔子,是,孔仲尼,孔子,是,人,人,是,动物,PowerPoint,Template_Sub,侦探调查了罪案的四个证人。从证人的话侦探得出的结论是：,如果男管家说的是真话，那么厨师说的也是真话；,厨师和园丁说的不可能都是真话；,园丁和杂役不可能都在说谎,如果杂役说真话，那么厨师在说谎,侦探能判断这四个证人分别是在说谎还是在说真话吗？,推理的例子,-,5,-,第9讲 命题与逻辑联结词,PowerPoint,Template_Sub,1,命题与逻辑联结词,2,逻辑等价式和逻辑蕴涵式,3,范式,4,证明技术（补充）,第四章 逻辑代数（上）：命题演算,命题与逻辑联结词,离散数学,第,9,讲,Textbook Page 56 to 62,-,7,-,第9讲 命题与逻辑联结词,内容提要,命题的概念,断言与命题、命题真值表示,原子命题和复合命题、命题常元、命题变元,逻辑联结词,、,命题公式,公式的归纳定义,真值表,自然语句的形式化,-,8,-,第9讲 命题与逻辑联结词,命题,(proposition,或,statement),命题,(proposition),：,表示判断的陈述句。,或是真，或是假，但二者不能得兼（排中律）,真、假常被称为,命题的真值,用大写的英文字母,T,或“,1,”,表示命题真值是“,真的,”,F,或“,0,”,表示命题的真值是“,假的,”,-,9,-,第9讲 命题与逻辑联结词,命题举例,例,4.1,雪是白的。,2+2=5,。,2,是偶数且,3,也是偶数。,陈胜起义那天杭州下雨。,大于,2,的偶数均可以分解为两个质数的和。,火星上有生物。,好痛快啊,!,您去看电影吗？,X+Y0,。,我只给那些不给自己刮胡子的人刮胡子。,我正在说谎。,-,10,-,第9讲 命题与逻辑联结词,原子命题和复合命题,命题常元和变元,命题变元指一个,未确定真值,的任意命题，其值在,0,1,上变化,命题常元指一个,有确定真值,的固定命题,原子命题：,一个不能再分解成更简单语句的命题,原子命题是最简单的陈述句,原子命题通常记为,p,、,q,、,r,等小写字母，,f,表示恒假命题，,t,表示恒真命题,相对于原子命题的是,复合命题,，它是由原子命题通过逻辑联结词进行适当的组合而成的,复合命题的真值不仅依赖于这两个组成它的命题，而且还依赖于这个联结词的意义,-,11,-,第9讲 命题与逻辑联结词,举例,p,：明天下雪；,q,：明天下雨,利用联结词“不”、“或”、“且”等可分别构成新命题：,“非,p”,：,明天不下雪,“,p,或,q”,：,明天要么下雪，要么下雨,“,p,并且,q”,：,明天下雨雪,-,12,-,第9讲 命题与逻辑联结词,常用,5,个逻辑联结词,否定词,(negation),：,P,，“,P,不成立”、“并非,P”,否定词是一元运算。,否定的是整个命题，并不是否定命题中个别的词。,P,P,0,1,1,0,真值表,“,A,和,B,都大于,0,”,的否定：,“,A,和,B,都不大于,0,”,“,A,和,B,不都大于,0,”,“,A,和,B,至少有一个不大于,0,”,“,A,和,B,至少有一个小于等于,0,”,“,A,大于,0”,的否定：,“,A,不大于,0”,“A,小于等于,0”,-,13,-,第9讲 命题与逻辑联结词,常用,5,个逻辑联结词,合取词,(conjunction),：,pq,，“,p,并且,q”,、“,p,和,q,都成立”,合取词是二元运算,只有当,p,和,q,均为真时，,pq,才是真的，否则，,pq,是假的,是可交换的,p,q,p q,0,0,0,0,1,0,1,0,0,1,1,1,p:,今天是星,期三,；,q:,今天上离散数学课；,p q,：今天是星期三并且上离散数学课；,-,14,-,第9讲 命题与逻辑联结词,常用,5,个逻辑联结词,析取词,(disjunction),：,pq,，“,p,成立或者,q,成立”、“,p,或,q”,析取词是二元运算,只有当,p,和,q,的真值均为假时，,pq,才是假的，否则，,pq,总是真的,p,q,p q,0,0,0,0,1,1,1,0,1,1,1,1,p:,我,上,午上离散数学；,q:,我,上,午上,C,+,语言；,p,q,：我上午或者离散数学，或者上,C,+,语言；,p:,我,上,午一二节课上离散数学；,q:,我,上,午一二节课上,C+,语言；,p,q,：我,上,午一二节课要么上离散数,上,学，要么上,C,+,语言,(,不会都上,),；,同或,异或,-,15,-,第9讲 命题与逻辑联结词,常用,5,个逻辑联结词,蕴涵词,(implication),：,pq,，“如果,p,，那么,q”,、“,p,蕴涵,q”,、“,p,是,q,的充分条件”,从真值表可以看出，只有当前提为真，而结论是假时，,pq,才是假的,p,q,p q,0,0,1,0,1,1,1,0,0,1,1,1,逆命题：,qp,；,否命题：,pq,逆否命题：,qp,命题和逆否命题有相同的真值,“,如果今天是星期五，那么,2+3=6,”,：,前提为假，蕴涵命题为真；,前提和结论之间可以没有关系，称为实质蕴涵,p:,天晴；,q:,我爬山；,只要天晴，我就爬山：,p,q,只有天晴，我才爬山：,q,p,“,只要下雨，我们队就能赢,”,-,16,-,第9讲 命题与逻辑联结词,常用,5,个逻辑联结词,p,q,p q,0,0,1,0,1,1,1,0,0,1,1,1,p,q,p q,0,0,0,0,1,1,1,0,1,1,1,1,p,q,p q,0,0,0,0,1,0,1,0,0,1,1,1,P,P,0,1,1,0,-,17,-,第9讲 命题与逻辑联结词,常用,5,个逻辑联结词,双向蕴涵词,(two-way implication),：,p,q,，“,p,当且仅当,q”,、“如果,p,，那么,q,；反之亦然”,只有当,p,和,q,的真值相同时，,p,q,才取真的真值,p,q,与,(pq)(qp),有完全相同的真值。,p,q,p,q,0,0,1,0,1,0,1,0,0,1,1,1,“,只有你健康，你才会感到快乐；只有感觉快乐你才健康,”,-,18,-,第9讲 命题与逻辑联结词,命题公式,(proposition formula),命题公式：,是一个表达式，它是由命题常元、命题变元、联结词符号和圆括号所组成的一个字符串,归纳定义：,命题常元和命题变元是命题公式，也称为原子公式或原子,如果,A,，,B,是命题公式，那么（,A,）、（,AB,）、（,AB,）、（,AB,）、（,A,B,）也是命题公式,只有有限步引用条款（,1,）、（,2,）所组成的符号串是命题公式,参见教材,P60,例,4.8,中的正例与反例,-,19,-,第9讲 命题与逻辑联结词,简写约定,为了减少圆括号的使用，我们,约定,：,省掉最外面的括号,联结词的结合能力强弱为、（、）、,结合能力平等的联结词从左到右运算,(p)(q(r q),s,),p q(r q,s,),-,20,-,第9讲 命题与逻辑联结词,语句形式化举例,我和他既是兄弟又是同学,pq,，其中：,p,：我和他是兄弟，,q,：我和他是同学,我和他至少有一个要去外地,pq,，其中：,p,：我去外地，,q,：他去外地,狗急跳墙,pq,，其中：,p,：狗急了，,q,：狗跳墙,除非他来，否则我不同他和解,p,q,，,(pq)(pq),，其中：,p,：他来，,q,：我同他和解,-,21,-,第9讲 命题与逻辑联结词,语句形式化举例,如果我和他不都是傻子，那么我们俩都不会去自讨没趣,（,pq,）（,rs,），其中：,p,：我是傻子；,q,：他是傻子,r,：我会去自讨没趣；,s,：他会去自讨没趣,若天气不下雨或不起雾，则航行比赛将举行而且救生表演将进行,如果他没来见你，那么他或者是生病了，或者是不在本地,语句形式化步骤,要准确确定原子命题，并将其形式化,要选用恰当的联结词,要善于识别自然语言中的联结词（有时它们被省略）,否定词的位置要放准确,必要时可以进行改述，但要保证表达意思一致,(,逻辑等价,),需要的括号不能省略,要注意语句的形式化未必是唯一的,-,23,-,第9讲 命题与逻辑联结词,语句形式化举例,设,p,：,a,是偶数,q,：,a,是奇数,r,：,a,是质数,s,：,a=2,，如何理解下述命题公式,pq,pr s,p,（,r s,）,rs q,（,qs,）,r,r,（,q s,）,r,q s,-,24,-,第9讲 命题与逻辑联结词,指派,(assignment),设公式,A,含有,n,个命题变元,p,1,，,p,2,，,，,p,n,记为,A(p,1,p,n,),给定这,n,个变元任意一组确定的值,（每一变元都有取真或假两种可能），公式,A,得到一个确定的值（,1,或,0,），我们称这一组确定的值为公式,A,的一组,指派,常用,表示指派，若在某一指派,下,A,取真的真值，则称,弄真,A,，记为,(A)=1,反之称,弄假,A,，记为,(A)=0,-,25,-,第9讲 命题与逻辑联结词,复合命题公式的真值表,首先确定在公式中出现的,命题变元的个数。,写出公式,A,的,所有指派,，一个指派为一行，若有,n,个命题变元，则有,2,n,组指派，也就是说真值表有,2,n,+1,行。,确定公式中,联结词的个数,，写出单个联结词的真值，一般讲，一个联结词对应着一列。,例,4.9(p(qr),的真值表,(pq)r),p,的真值表,p,q,r,pq,r,(pq)r,(pq)r),p,0,0,0,0,1,1,0,0,0,1,0,0,0,1,0,1,0,0,1,1,0,0,1,1,0,0,0,1,1,0,0,0,1,1,1,1,0,1,0,0,0,0,1,1,0,1,1,1,1,1,1,1,1,0,1,1,-,26,-,第9讲 命题与逻辑联结词,指派举例,使公式,A:(pq)r),p,为真的指派,(A)=1,1.(,(pq)r,)=1,，,(p)=1,，,2.(,(pq)r,)=0,，,(p)=0,(,r,)=0,(,r,)=1,1.1.(,q,)=1,1.1.1.(,r,)=0,1.1.2.(,r,)=1,1.2.(,q,)=0,1.2.1.(,r,)=0,2.1.(,q,)=0,2.2.(q)=1,(1,1,0),(1,1,1),(1,0,0),(0,0,1),(0,1,1),-,27,-,第9讲 命题与逻辑联结词,推理的例子,侦探调查了罪案的四个证人。从证人的话侦探得出的结论是：,如果男管家说的是真话，那么厨师说的也是真话；,厨师和园丁说的不可能都是真话；,园丁和杂役不可能都在说谎,如果杂役说真话，那么厨师在说谎,p,、,q,、,r,、,s,：分别表示男管家、厨师、园丁、杂役说的是真话,1,、,pq,2,、,qr,3,、,rs,4,、,sq,哪些指派使这四个命题公式同时为真？,-,28,-,第9讲 命题与逻辑联结词,本讲小结,主要内容,命题的概念：,什么是命题、命题的真值,五个主要的,逻辑联结词,命题公式的概念、命题公式的,真值表