L1命题逻辑1 离散数学.ppt

命题逻辑,一,LuChaojun,SJTU,2,2,主要内容,命题与命题联结词命题公式等值演算命题公式的范式联结词的功能完全集永真蕴涵式命题逻辑推理,LuChaojun,SJTU,3,3,什么是命题?,命题(proposition):可判断真假而且非真即假的陈述句的内容.是陈述句的内容,而非陈述句本身.命令句、疑问句或感叹句等的内容不构成命题.可判定真假:是否符合事实.不可:不真不假，又真又假.命题的真值(truthvalue):命题的真假结果.即真(TRUE)和假(FALSE).常记作T和F,或者1和0.二值逻辑,LuChaojun,SJTU,4,4,例:命题,(1)“雪是白的.”是命题,真值为1.(2)“雪是黑的.”是命题,真值为0.(3)“好大的雪啊!”不是命题(4)“大于2的偶数可表示成两个素数之和.”(Goldbach猜想)是命题,目前不知其真假.(5)“1+10l110.”此数学式相当于命题“1加101等于110”.在十进制中真值为0,在二进制中真值为1.并非说同一命题有两个真值!在不同数制中是不同的命题.,LuChaojun,SJTU,5,5,命题的符号化表示,为便于进行命题演算,将自然语言符号化.用符号表示命题:命题常量:有确定真值的具体命题.符号化:如用a表示“雪是白的”.命题变量:用符号来表示任意命题.命题变量的真值是不确定的.对其指派了具体命题之后,才具有确定的真值.我们采用的表示法采用小写字母(可带下标)作为命题符号:a,b,c,命题符号如果不加说明一般是命题变量,LuChaojun,SJTU,6,6,简单命题和复合命题,从自然语言的简单句和复合句可形成简单命题与复合命题的概念.简单命题(或原子命题):简单语句不含“并且”“或者”“如果那么”之类的联结词.例如“雪是白的.”命题逻辑中不作进一步分析.但谓词逻辑不同.复合命题:复合语句可分析为:简单命题经联结词联结而成.联结词:并且,或者,非,如果那么,例如“张三是教师并且雪是白的.”,LuChaojun,SJTU,7,7,命题联结词,命题联结词(propositionalconnective):将命题联结起来构成新命题.常用命题联结词:,将命题视为运算对象,命题联结词视为运算符,则构成运算表达式.比较:初等代数中运算对象是a,b,c等,运算符有等,LuChaojun,SJTU,8,8,否定词“”,否定(negation):命题a加上否定词就形成一个新命题a,表达的是对a的否定.读作:非a的严格定义可利用真值关系给出:a为真iffa为假.这种真值关系常常用真值表(truthtable)来表示.,LuChaojun,SJTU,9,9,的真值表,真值表描述了a的真值如何依赖于a的真值.当命题变量不多时,真值表是研究真值关系的重要工具.,LuChaojun,SJTU,10,10,的例子,1.令a:“张三去看球赛了.”则a:“张三没有去看球赛.”2.令b:“今天是星期三.”则b:“今天不是星期三.”,LuChaojun,SJTU,11,11,合取词“”,合取(conjunction):联结两个命题a和b构成一个新命题ab,表达“a并且b”.读作:a且b,a与b,a、b的合取.的严格定义可用真值关系给出:ab为真iffa和b都为真,LuChaojun,SJTU,12,12,的真值表,的真值表描述了ab的真值如何依赖于a和b的真值.,LuChaojun,SJTU,13,13,的例子,1.令a:“雪是白的.”b:“煤是黑的.”则ab:“雪是白的并且煤是黑的.”2.令a:“雪是白的.”b:“教室里有人.”则ab:“雪是白的并且教室里有人.”,LuChaojun,SJTU,14,14,与日常用语的差异,日常用语里的“和”“与”“并且”一般表示有联系的事物;而只关心命题间的真值关系,并不考虑两命题是否有意义上的联系.例如“雪是白的并且教室里有人.”日常用语中的某些意义用表达不出来例如“苹果电脑质量很好,但是很贵.”可符号化为用表达,但没有转折语气.“张和李是同学”中的“和”不是联结词.,LuChaojun,SJTU,15,15,析取词“”,析取(disjunction):联结两个命题a和b构成新命题ab,表达“a或者b”.读作:a或b,a、b的析取.的严格定义可用真值关系给出:ab为假iffa和b都为假,LuChaojun,SJTU,16,16,的真值表,的真值表描述了ab的真值如何依赖于a和b的真值.,LuChaojun,SJTU,17,的例子,1.令a:“雪是白的.”b:“雪是黑的.”则ab:“雪是白的或者雪是黑的.”2.令a:“2小于3.”b:“雪是黑的.”则ab:“2小于3或者雪是黑的.”由于“2小于3”真,所以ab必真,尽管“雪是黑的”为假.,17,LuChaojun,SJTU,18,与日常用语的差异,日常用语中的“或”还可能具有“排他”涵义例如“你去或者我去”有二选一的意思可定义这种“排他的或(exclusiveor)”,称为异或.而是“包容的或(inclusiveor)”.,18,LuChaojun,SJTU,19,蕴涵词“”,蕴涵(implication):将两个命题a和b联结起来,构成一个新的命题ab,表达“如果a成立那么b成立”.读作:a蕴涵ba称前件(antecedent),b称后件(consequent).的严格定义可用真值关系给出:ab为假iffa真而b假,19,LuChaojun,SJTU,20,20,的真值表,的真值表描述了ab的真值如何依赖于a和b的真值.,LuChaojun,SJTU,21,与推理,的最重要用途是进行命题间的推理.如果已知ab为真,那么只要a为真,必能推知b为真.绝不可能a真而b假.此即传统逻辑所称modusponens推理规则.肯定前件式,或称分离规则ab若a则baabb,21,LuChaojun,SJTU,22,与日常用语的差异,称为实质蕴涵(materialimplication),与日常用语“如果那么”有不同.因果联系?日常用语的“如果a那么b”表明a和b有因果联系.而只反映a和b的真值关系,与因果无关.a为假时,不论b的真假,ab都为真.“如果雪是黑的,那么1=2.”是个真命题!若对此不满,可给出不同的蕴涵定义.,22,LuChaojun,SJTU,23,的例子,1.令a:“224.”a1:“225.”b:“雪是白的.”b1:“雪是黑的.”则ab为真a1b为真a1b1为真ab1为假2.令a:“陆老师讲课.”b:“他来听课.”则“只有陆老师讲课他才来听课”应译为ba.,23,LuChaojun,SJTU,24,双条件词“”,双条件/等价(biconditional/equivalence):将两个命题a和b联结起来,构成一个新的命题ab,表达“等价于”“当且仅当”等.读作:a等价b,a当且仅当b的严格定义可用真值关系给出:ab为真iffa和b真值相同,24,LuChaojun,SJTU,25,25,的真值表,的真值表描述了ab的真值如何依赖于a和b的真值.验证:ab和(ab)(ba)真值表相同,LuChaojun,SJTU,26,与日常用语的差异,和蕴含一样,并不意味着有因果联系.例如“225太阳从西边出来”是真的.,26,LuChaojun,SJTU,27,的例子,令a:“ABC是等腰三角形.”b:“ABC中有两个角相等.”则ab表达了“ABC是等腰三角形当且仅当ABC中有两个角相等”.就此例而言:ab为真.若把“等腰”换成“直角”,则ab为假.,27,LuChaojun,SJTU,28,关于联结词,是最常用的.也有用不同符号的:,+,还可定义其他联结词如异或但既不常用,又都可由上述五个联结词表示出来.(稍后讨论)联结词,对应着数字电路的门电路,可见命题逻辑(布尔逻辑)是数字电路分析和设计的理论基础和工具.,28,LuChaojun,SJTU,29,关于自然语句的符号化,将自然语句翻译成符号化的命题(1)根据自然语句的含义,确定若干简单命题,并用命题符号a,b,c,表示之;(2)根据自然语句的含义,确定简单命题之间的关系,并用命题联结词将它们联结起来.可能需要仔细考察自然语句的含义,才能抽取出隐含的简单命题和联结词.,29,LuChaojun,SJTU,30,例子,(1)张三不是学生.令a:张三是学生.则(1):a.令a:张三不是学生.如何?(2)张三既聪明又用功.令a:张三聪明.b:张三用功.则(2):ab.令a:张三既聪明又用功.如何?思考:张三虽然聪明但不用功.(3)张三一感冒就发烧.令a:张三感冒.b:张三发烧.则(3):ab.,30,LuChaojun,SJTU,31,例子(续),(4)张三和李四是学生.令a:张三是学生.b:李四是学生.则(4):ab.思考:张三和李四是表兄弟.也用?(5)张三或李四当班长.令a:张三当班长.b:李四当班长.则(5):ab?不可兼或!(5)应表示为:(ab)(ab).思考:张三和李四至少一人是学生.ab合适.思考:张三或李四都可当班长.也用?,31,LuChaojun,SJTU,32,32,主要内容,命题与命题联结词命题公式等值演算命题公式的范式联结词的功能完全集永真蕴涵式命题逻辑推理,LuChaojun,SJTU,33,命题公式,问题:通过联结词构成复杂命题时,如何才是有意义的命题?例如:abc的意义明确吗?定义(命题公式):(1)命题常量和命题变量是命题公式.(2)如果A、B是命题公式,则(A),(AB),(AB),(AB)和(AB)也是命题公式.(3)所有命题公式都通过(1)(2)得到.,33,关于命题公式定义,符号表:这里隐含规定使用大小写字母(可带下标),联结词,圆括号.这种定义方式是形式系统常用的合式定义,所定义的公式称为合式公式(wff).(1)(2)是归纳定义的奠基和归纳步骤,(3)并不是多余的一句话.(Why?)为简化括号的使用,可规定联结词的优先级(由高到低):同级:自左到右次序最外层括号常省略,LuChaojun,SJTU,34,LuChaojun,SJTU,35,判断符号串是否wff,根据合式定义,层层归约,直到原子命题即可判断.例(ab)(a(ab)(ab)(bc)(ac)(ab)b(ab),35,LuChaojun,SJTU,36,命题变量的真值,命题公式的真值由其成员命题的真值决定.公式中有命题变量时如何确定真值?对公式中所有命题变量进行真值赋值(指派),则公式的真值即可确定.不同赋值导致公式的不同真值.真值赋值:设U是全体命题变量的集合.一个真值赋值t是从U到0,1的一个函数.,36,LuChaojun,SJTU,37,命题公式的真值,命题公式A在真值赋值t下的真值t(A):(1)A是命题常量a,则t(A)a的真值.(2)A是命题变量x,则t(A)t(x).(3)t(A)1ifft(A)0.(4)t(AB)1ifft(A)t(B)1.(5)t(AB)0ifft(A)t(B)0.(6)t(AB)0ifft(A)1且t(B)0.(7)t(AB)1ifft(A)t(B),37,t()的性质,定理(1)t(1)1,t(0)0.(2)t(A)t(A).(3)t(AB)t(A)t(B).(4)t(AB)t(A)t(B).(5)t(AB)t(A)t(B).(6)t(AB)t(A)t(B).,LuChaojun,SJTU,38,例:计算公式的真值,1.求A(xy)(x)(yz)在t(x)0,t(y)1,t(z)0时的真值.解:t(xy)1t(x)1t(yz)0t(x)(yz)0t(A)t(10)02.设t(xy)0,求t(y(xy)x).解:由t(xy)0,知t(y(xy)0.则t(y(xy)x)1.,LuChaojun,SJTU,39,LuChaojun,SJTU,40,命题公式分类,若命题公式A在任一赋值下值都为1,则称A为永真式(或重言式,tautology).例:a(a).重言式由,联结所得公式仍是重言式.重言式反映了逻辑规律.若A在任一赋值下值都为0,则称A为永假式(或矛盾式contradiction).例:a(a)若A在某个赋值下值为1,则称A是可满足式.例:ab,40,LuChaojun,SJTU,41,三类公式间关系,以下关系是显然的(1)A永真iffA永假.(2)A可满足iffA非永真.(3)A非可满足iffA永假.(4)A非永假iffA可满足.,41,永真,可满足,永假,真