单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,Lu Chaojun,SJTU,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,Lu Chaojun,SJTU,*,命题逻辑的基本概念,命题逻辑的基本概念,Lu Chaojun,SJTU,2,2,主要内容,命题,命题联结词,合式公式,重言式,Lu Chaojun,SJTU 22主要内容命题,Lu Chaojun,SJTU,3,3,什么是命题?,命题,(,proposition,):,是一个,非真即假,的,陈述句,.,是陈述句,而非命令句、疑问句或感叹句等,.,表达的内容可判断真假,而且非真即假,.,真假的判定,:,与事实是否相符,.,不能不真又不假，也不能又真又假,.,真值,(,truth value,):,命题具有两种可能的取值,即真,(true),和假,(false).,常写做,T,和,F.,称为二值逻辑,.,Lu Chaojun,SJTU 33什么是命题?命题(pr,Lu Chaojun,SJTU,4,4,例子:命题,(1),雪是白的,.,是命题,真值为,T.,(2),雪是黑的,.,是命题,真值为,F.,(3),好大的雪啊,!,不是命题,(4),偶数可表示成两个素数之和,.(Goldbach,猜想,),是命题,目前不知其真假,.,(5)1+10l,110.,相当于陈述句,“1,加,101,等于,110”.,在十进制范围中真值为,F,在二进制范围中真值为,T.,并不意味着同一命题有两个真值,!,在不同数制中是不同的命题,.,Lu Chaojun,SJTU 44例子:命题(1)雪是白,Lu Chaojun,SJTU,5,5,命题的符号化表示,为了对命题进行逻辑演算,利用数学手段将命题符号化,(,形式化,).,用字母表示命题,命题常项,:,例如用,P,表示,“,雪是白的,”.,命题变项,:,例如用,P,表示任意命题,.,命题,vs.,命题变项,命题指具体的陈述句,有确定的真值,命题变项不特指某个命题,真值不确定,将某个命题代入命题变项时,命题变项方可确定真值,.,但在命题逻辑演算中,两者处理原则是一样的,可不做区分,.,Lu Chaojun,SJTU 55命题的符号化表示为了对,Lu Chaojun,SJTU,6,6,简单命题和复合命题,简单命题,:,简单句,不包含任何,“,并且,”,“,或者,”,之类的联结词,.,例如,:,雪是白的,.,又叫,原子命题,:,不可分割,.,如果按主语谓语分析,则是谓词逻辑的做法,.,复合命题,:,成分命题,经联结词,联结而成,.,例如,:,张三是教师并且雪是白的,.,又叫分子命题,:,可以分割,.,联结词例子,:,并且,或者,非,如果,那么,Lu Chaojun,SJTU 66简单命题和复合命题简单,Lu Chaojun,SJTU,7,7,复合命题的真值,复合命题的真值是,成分命题的真值的函数,.,当成分命题被赋予任一真值组合时,联结词完全决定了复合命题的真值,.,例如,:“,张三学英语且李四学日语,”,由简单命题,“,张三学英语,”,“,李四学日语,”,经联结词,“,且,”,联结而成,.,当这两个简单命题真值均为,T,时,该复合命题真值才为,T.,Lu Chaojun,SJTU 77复合命题的真值复合命题,Lu Chaojun,SJTU,8,8,命题内容vs.形式,形式逻辑并不关心命题内容为真为假的条件和环境等,只关心命题有真假的可能性,以及复合命题的真假规律性,.,风马牛不相及的内容也可以组成复合命题,.,例如,:,张三学英语或者熊猫是珍稀动物,.,Lu Chaojun,SJTU 88命题内容vs.形式形式,Lu Chaojun,SJTU,9,9,命题联结词,命题联结词,(,propositional connective,):,将命题联结起来构成新命题,.,将命题视为运算对象,命题联结词视为运算符,从而构成运算表达式,.,比较,:,初等代数中运算对象是,a,b,c,等,运算符有,等,常用命题联结词,:,Lu Chaojun,SJTU 99命题联结词命题联结词(,Lu Chaojun,SJTU,10,10,否定词,“,”,否定,(,negation,),:,命题,P,加上否定词就形成一个新命题,P,表达的是对,P,的否定,.,读作,:,非,P,的定义可用真值关系精确给出,:,P,为真,iff,P,为假,.,这种真值关系常常用,真值表,(,truth table,),来表示,.,Lu Chaojun,SJTU 1010否定词“”否定(,Lu Chaojun,SJTU,11,11,的真值表,真值表描述了,P,的真值如何依赖于,P,的真值,.,当命题变项不多时,真值表是研究真值关系的重要工具,.,P,P,T,F,F,T,Lu Chaojun,SJTU 1111的真值表真值表描,Lu Chaojun,SJTU,12,12,的,例子,1.,令,P,:,张三去看球赛了,.,则,P,:,张三没有去看球赛,.,2.,令,Q,:,今天是星期三,.,则,Q,:,今天不是星期三,.,Lu Chaojun,SJTU 1212的例子1.令P:,Lu Chaojun,SJTU,13,13,合取词,“,”,合取,(,conjunction,),:,联结,两个命题,P,和,Q,构成一个新命题,P,Q,表达,“,P,并且,Q,”.,读作,:,P,与,Q,P,、,Q,的合取,.,的定义可用真值关系精确给出,:,P,Q,为真,iff,P,和,Q,都为真,Lu Chaojun,SJTU 1313合取词“”合取(,Lu Chaojun,SJTU,14,14,的,真值表,的,真值表描述了,P,Q,的真值如何依赖于,P,和,Q,的真值,.,P,Q,P,Q,F,F,F,F,T,F,T,F,F,T,T,T,Lu Chaojun,SJTU 1414的真值表的真值,Lu Chaojun,SJTU,15,15,的,例子,1.,令,P,:,教室里有,10,名女同学,.,Q,:,教室里有,15,名男同学,.,则,P,Q,:,教室里有,10,名女同学并且有,15,名男同学,.,2.,令,A,:,今天下雨了,.,B,:,教室里有,100,张桌子,.,则,A,B,:,今天下雨了并且教室里有,100,张桌子,.,Lu Chaojun,SJTU 1515的例子1.令P:,Lu Chaojun,SJTU,16,16,与日常用语的差异,日常用语里的,“,和,”,、,“,与,”,、,“,并且,”,一般表示同类事物的并列,;,而形式逻辑中的,只关心,命题与命题之间的真值关系,并不考虑两命题是否有意义上的联系,.,例如,:“,张三,18,岁并且今天天气晴朗”,日常用语中的某些意义用,表达不出来,例如,:,“,这台机器质量很好,但是很贵,”,用,表达时并无,“,转折,”,的语气,.,Lu Chaojun,SJTU 1616与日常用语的差异,Lu Chaojun,SJTU,17,17,析取词,“,”,析取,(,disjunction,),:,联结两个命题,P,、,Q,构成新命题,P,Q,表达,“,P,或者,Q,”.,读作,:,P,或,Q,P,、,Q,的析取,.,的定义可用真值关系精确给出,:,P,Q,为假,iff,P,和,Q,都为假,Lu Chaojun,SJTU 1717析取词“”析取(,Lu Chaojun,SJTU,18,18,的,真值表,的,真值表描述了,P,Q,的真值如何依赖于,P,和,Q,的真值,.,P,Q,P,Q,F,F,F,F,T,T,T,F,T,T,T,T,Lu Chaojun,SJTU 1818的真值表的真值,Lu Chaojun,SJTU,19,的,例子,1.,令,P,:,今天刮风,Q,:,今天下雨,则,P,Q,:,今天刮风或者下雨,.,2.,令,A,:2,小于,3,B,:,雪是黑的,则,A,B,:2,小于,3,或者雪是黑的,由于,2,小于,3,是真的,所以,A,B,必为真,尽管,“,雪是黑的,”,为假,.,19,Lu Chaojun,SJTU 19的例子1.令P:今天,Lu Chaojun,SJTU,20,与日常用语的差异,日常用语中的,“,或,”,往往具有,“,不可兼,”,的涵义,即二选一,.,例如,:,你去或者我去,.,也可定义,“,不可兼或,”,也叫,“,异或,”.,20,Lu Chaojun,SJTU 20与日常用语的差异日常,Lu Chaojun,SJTU,21,蕴涵词,“,”,蕴涵,(,implication,),:,将两个命题,P,、,Q,联结起来,构成一个新的命题,P,Q,表达,“,如果,P,成立那么,Q,成立,”.,读作,:,P,蕴涵,Q,P,称,前件,(,antecedent,),Q,称,后件,(,consequent,).,的定义可用真值关系精确给出,:,P,Q,为假,iff,P,真而,Q,假,21,Lu Chaojun,SJTU 21蕴涵词“”蕴涵(im,Lu Chaojun,SJTU,22,22,的,真值表,的,真值表描述了,P,Q,的真值如何依赖于,P,和,Q,的真值,.,P,Q,P,Q,F,F,T,F,T,T,T,F,F,T,T,T,Lu Chaojun,SJTU 2222的真值表的真值,Lu Chaojun,SJTU,23,与推理,的最重要用途是,进行命题间的推理,.,如果已知,P,Q,为真,那么只要,P,为真,必能推知,Q,为真,.,绝不可能,P,真而,Q,假,.,此即传统逻辑所称,modus ponens,推理规则,.,肯定前件式,或称分离规则,P,Q,若,P,则,Q,P,P,Q,Q,23,Lu Chaojun,SJTU 23与推理 的最重要用,Lu Chaojun,SJTU,24,与日常用语的差异,称为,实质蕴涵,(,material implication,),与日常用语,“,如果,那么,”,有不同,.,因果联系,?,日常用语的,“,如果,P,那么,Q,”,仅用于,P,和,Q,有内容上的因果联系,.,只反映,P,和,Q,的真值间的关系,:,不能,P,真而,Q,假,与命题内容无关,.,P,为假时,不论,Q,的真假,P,Q,都为真,.,存在不同的蕴涵定义,.,24,Lu Chaojun,SJTU 24与日常用语的差异称,Lu Chaojun,SJTU,25,的,例子,令,P,:22,4;,P,:22,5.,Q,:,雪是白的,;,Q,:,雪是黑的,.,则,P,Q,为真,P,Q,为真,P,Q,为真,P,Q,为假,25,Lu Chaojun,SJTU 25的例子 令P:22,Lu Chaojun,SJTU,26,双条件词,“,”,双条件,/,等价,(,biconditional,/,equivalence,),:,将两个命题,P,、,Q,联结起来,构成一个新的命题,P,Q,表达,“,等价于,”“,当且仅当,”,等,.,读作,:,P,等价,Q,P,当且仅当,Q,的定义可用真值关系精确给,/,出,:,P,Q,为真,iff,P,和,Q,真值相同,26,Lu Chaojun,SJTU 26双条件词“”双条件/,Lu Chaojun,SJTU,27,27,的,真值表,的,真值表描述了,P,Q,的真值如何依赖于,P,和,Q,的真值,.,验证,:,P,Q,和,(,P,Q,),(,Q,P,),真值表相同,P,Q,P,Q,F,F,T,F,T,F,T,F,F,T,T,T,Lu Chaojun,SJTU 2727的真值表的真值,Lu Chaojun,SJTU,28,的,例子,令,P,:ABC,是等腰三角形,.,Q,:ABC,中有两个角相等,.,则,P,Q,表达了,“ABC,是等腰三角形当且仅当,ABC,中有两个角相等,”.,就此例而言,:,P,Q,为真,.,若把,“,等腰,”,换成,“,直角,”,则,P,Q,为假,.,28,Lu Chaojun,SJTU 28的例子令P:AB,Lu Chaojun,S