(20120829)第一章命题逻辑的基本概念.ppt

,漳州师范学院计算机科学与工程系,第一章命题逻辑的基本概念,2020年6月11日1时40分,第一章命题逻辑的基本概念,命题与联结词命题公式及其赋值知识点：命题及表示、联结词、命题公式与赋值、真值表教学要求：深刻理解和掌握命题逻辑中的基本概念教学重点：命题逻辑中的基本概念学时:2,2020年6月11日1时40分,1.1命题与与联结词,命题：能判断真假而不是可真可假的陈述句命题的真值：作为命题的陈述句所表达的判断结果真值只取两个值：真或假真值为真的命题称为真命题，真命题表达的判断正确真值为假的命题称为假命题，假命题表达的判断错误任何命题的真值都是唯一的判断给定句子是否为命题，应该分两步首先判定它是否为陈述句其次判断它是否有唯一的真值,2020年6月11日1时40分,1.1命题与与联结词,例1:判断下列句子是否为命题4是素数是无理数x大于y火星上有水2100年元旦是晴天,假命题,真命题,不是命题-根据x,y的不同取值情况它可真可假,无唯一的真值,是命题-火星上有没有水是确定的客观事实，虽然目前无法判断，但结果肯定只有一种,是命题-目前无法确定但将来可以判断真假，结果肯定只有一种,2020年6月11日1时40分,1.1命题与与联结词,大于3吗？请不要吸烟！这朵花真美丽啊！我正在说假话所有的整数都大于0有的整数大于0,不是命题-疑问句,祈使句,感叹句都不是命题,不是命题悖论(自相矛盾的陈述句),假命题,真命题,2020年6月11日1时40分,1.1命题与与联结词,数理逻辑研究方法的主要特征是将论述或推理中的各种要素都符号化，即构造形式语言来代替自然语言命题真值的符号化:1或T表示真,0或F表示假1或T,0或F称为命题常元命题的符号化：用字母p,q,r,pi,qi,ri,表示命题,2020年6月11日1时40分,1.1命题与与联结词,注意一个代表命题的变量称为命题变元命题变元是用来表示任意命题的,它的真值是未确定的当命题变元用一个具体的命题”代入”时,它才有确定的真值用一个具体的命题“代入”一个命题变元p,称为对命题变元p进行指派,也称赋值或解释例如：用”雪是黑的”代入p后,这时p有确定的值0用”雪是白的”代入p后,这时p有确定的值1,2020年6月11日1时40分,1.1命题与与联结词,原子命题:不能分解为更简单命题的命题复合命题:由原子命题通过联词复合而成的命题例如:小王会唱歌和跳舞;小王会唱歌但不会跳舞为了避免歧义,对联结词进行严格定义,并且加以符号化常用的联词设p和q为两个命题定义1.1否定联结词:复合命题”非p”称为p的否定式,记为p,2020年6月11日1时40分,1.1命题与与联结词,定义1.2合取联结词:复合命题”p并且q”称为p与q的合取式,记作pq定义1.3析取联结词:复合命题”p或者q”称为p与q的析取式,记作pq,2020年6月11日1时40分,1.1命题与与联结词,定义1.4蕴涵联结词:复合命题”如果p则q”称为p与q的蕴涵式,记作pq定义1.5等价联结词:复合命题”p当且仅当q”称为p与q的等价式,记作pq,前件,后件,规定：当前件为假命题时，不论后件是真是假，该蕴涵式都为真命题,蕴涵式的前件和后件可以没有内在联系例如：如果中国的首都是北京则雪是白的显然这是一个真命题,2020年6月11日1时40分,1.1命题与与联结词,基本复合命题的真值表,pq与(pq)(qp)的真值表是相同的,2020年6月11日1时40分,1.1命题与与联结词,逻辑联词也称为逻辑运算符运算的优先级依次为:(,),高,低,例如pqpqrqp相当于(p)q)p)(q(r)q)p,2020年6月11日1时40分,1.1命题与与联结词,例2试用符号形式表示下列命题:明天不下雨p如果明天不下雨,那么我去看电影pq当且仅当明天不下雨,我才去看电影pq如果明天不下雨而且我有时间,那么我去看电影(pr)q如果明天下雨或我没有时间,那么我就不去看电影(pr)q除非明天下雨,否则我就去看电影pq只有明天下雨我才会去看电影qp除非明天下雨我才会去看电影qp,p:明天下雨q:明天我去看电影r:明天我有时间,2020年6月11日1时40分,1.1命题与与联结词,例3试用符号形式表示下列命题并求真值:设p:2是有理数,q:2是无理数,r:3是有理数,s:3是无理数,t:2大于02是有理数是不对的2是有理数或者是无理数2是有理数或者大于0只有2是有理数,3才是有理数只要2是有理数,3就是无理数,p,真值为0,(pq)(pq),pq真值为1,pt,真值为1,rp,真值为1,ps,真值为0,2020年6月11日1时40分,1.1命题与与联结词,排拆或和相容或自然语言中的”或”具有二义性,它有时具有相容性,有时具有排斥性排斥或(pq)(pq),只有当一个为真、另一个为假时才为真相容或pq,两个命题可以同时为真对于具体的命题p和q,如果p,q不可能同时为真时就不用区分,2020年6月11日1时40分,1.2命题公式及其赋值,命题公式:由命题常元、命题变元、逻辑联词和括号按下述法则联结起来的符号串定义1.6(1)单个命题变项和命题常项是合式公式,并称为原子命题公式(2若A是合式公式,则A合式公式(3)若A,B是合式公式，则AB,AB,AB,AB是合式公式(4)只有有限次应用,得到的符号串才是合式公式,2020年6月11日1时40分,1.2命题公式及其赋值,如:(pq)(qr)(pq)rp(qr)等都是合式公式pqr,（p(rq)等不是合式公式注意：上述命题合式公式的定义方式称为归纳定义方式命题公式可以看作是关于命题变项的取值为0或1的函数,A=f(p,q,r),p,q,r0,1,A0,1,2020年6月11日1时40分,1.2命题公式及其赋值,定义1.7(1)若公式A是单个的命题变项，则称A为0层合式。(2)称A是n+1(n0)层公式是指下面情况之一：(a)A=B，B是n层公式(b)A=BC,其中B,C分别为i层和j层公式,且n=max(i,j)(c)A=BC，其中B，C的层次及n同(b)(d)A=BC，其中B，C的层次及n同(b)(e)A=BC，其中B，C的层次及n同(b)(3)若公式A的层次为k，则称A是k层公式易知，(pq)r，(pq)(rs)p)分别为3层和4层公式,公式的“层次”可以描述其构造的复杂性。,2020年6月11日1时40分,1.2命题公式及其赋值,定义1.8设p1,p2,pn是出现在公式A中的全部命题变项,给p1,p2,pn各指定一个真值,称为对A的一个赋值或解释。若指定的一组值使A为1,则称这组值为A的成真赋值若指定的一组值使A为0,则称这组值为A的成假赋值,2020年6月11日1时40分,1.2命题公式及其赋值,定义1.9将命题公式A在所有赋值下取值情况列成表称作命题公式A的真值表,构造真值表的具体步骤如下：(1)找出公式中所含的全体命题变项p1,p2,pn(若无下角标就按字典顺序排列)，列出2n个赋值。赋值从000开始然后按二进制加法依次写出各赋值，直到111为止(2)按从低到高的顺序写出公式的各个层次(3)对应各个赋值计算出各层次的真值，直到最后计算出公式的真值,2020年6月11日1时40分,1.2命题公式及其赋值,例4求p(pq),pp,pp,pqrr的真值表,2020年6月11日1时40分,1.2命题公式及其赋值,定义1.10设A为任一命题公式若A在它的各种赋值下取值均为真,则称A是重言式或永真式若A在它的各种赋值下取值均为假,则称A是矛盾式或永假式若A不是矛盾式,则称A是可满足式真值表可用来判断公式的类型:(1)若真值表最后一列全为1，则公式为重言式(2)若真值表最后一列全为0，则公式为矛盾式(3)若真值表最后一列中至少有一个1，则公式为可满足式,可满足A至少存在一个成真赋值重言式一定是可满足式,若公式A是可满足式且它至少存在一个成假赋值，则称A为非重言