离散数学课件第一章命题逻辑

刘师少Tel：86613623（h）E-mail：lss授课:51学时学分3教学目标:知识、能力、素质,DiscreteMathematics,什么是数理逻辑,数理逻辑：以数学的方法研究思维规律和推理过程的科学。它首先引进一套符号体系，规定一些规则，导出一些定律，然后借助于这些符号、规则、定律，将逻辑推理的过程在形式上变得像代数演算一样，因此数理逻辑又称符号逻辑。,微积分力学、机械工程人类体力劳动自动化,数理逻辑人工智能、知识工程脑力劳动自动化,数理逻辑,命题逻辑（数理逻辑的基础，以命题为研究对象，研究基于命题的符号逻辑体系及推理规律，也称命题演算）。主要内容：、命题与联结词、命题公式、真值表、重言式、命题联结词的扩充、范式、命题演算的推理规则和证明方法谓词逻辑（对命题逻辑的深入研究）。,第一章命题逻辑,这章是以“命题”为中心主要讨论：命题的表示、命题的演算命题演算中的公式，及其应用命题逻辑推理,1.1.1命题的概念命题：能够判断真假的陈述句。命题的真值：命题的判断结果。真值只取两个值：真（1）、假（0）。真命题：真值为真的命题。假命题：真值为假的命题。判断命题的两个步骤：)1、是否为陈述句；2、是否有确定的、唯一的真值。,1.1命题符号化及联结词,命题的特征：陈述句真假必居其一，且只居其一。,例1.1下列句子中那些是命题？(1)是无理数.(2)2+58.(3)x+53.(4)你有铅笔吗？(5)这只兔子跑得真快呀！(6)请不要讲话！(7)我正在说谎话.,真命题,假命题,真值不确定,疑问句,感叹句,祈使句,悖论,(3)(7)都不是命题,第一章命题逻辑,祈使句，感叹句，疑问句均不是命题。再如把门关上！你到哪里去？语句既为真，同时又包含假的不是命题，这样的句子称为“悖论”。如他正在说谎。（在命题逻辑中不讨论这类问题）,例1.2判定下面这些句子哪些是命题。(8)2是个素数。(9)雪是黑色的。(10)2015年人类将到达火星。(11)如果ab且bc，则ac。(12)x+y910.皇马中国之行没有提升国家队的水平。,第一章命题逻辑,模糊逻辑,1.1.3命题及其真值的抽象化在本书中，用小写英文字母p,q,r,p1,p2,p3等表示命题,用“1”、“0”分别表示真值的真、假。例1.2：p：罗纳尔多是球星。q：5是负数。p3：明天天气晴。皆为符号化的命题，其真值依次为1、0、1或0。若令p：是有理数，则p的真值为0q：2+5=7，则q的真值为1,分类根据其真值分类：真命题。假命题。根据其复杂程度分类：简单命题或原子命题。复合命题。,1.1.4命题的分类,简单/原子命题：由不能再分解为更简单的陈述句的陈述句构成。如上例中的命题。复合命题：由简单命题与联结词按一定规则复合而成的命题例1.3(1)若三角形等腰，则两底角相等(2)若行列式两行成比例，则行列式值为0,1.1.4命题的分类,例1.3由简单命题能构造更加复杂的命题期中考试，张三没有考及格。期中考试，张三和李四都及格了。期中考试，张三和李四中有人考90分。如果张三能考90分，那么李四也能考90分。张三能考90分当且仅当李四也能考90分。,联结词和复合命题,上述诸如“没有”、“如果那么”等词称为联结词。由联结词和命题连接而成的更加复杂命题称为复合命题；相对地，不能分解为更简单命题的命题成为简单命题。（命题的分类）复合命题的真假完全由构成它的简单命题的真假所决定。注：简单命题和复合命题的划分是相对的。,在命题逻辑的符号化过程中，通常的要求是每一个引进的表示命题的符号都表示一个原子命题。例如：将下列命题符号化(1)杭州不是中国的首都。(2)张三虽然学习努力但成绩并不优秀。解(1)令P：杭州是中国的首都。则命题“杭州不是中国的首都”符号化为：P(2)令P：张三学习努力。Q：张三成绩优秀。则命题“张三虽然学习努力但成绩并不优秀。”符号化为：PQ。,由此我们进一步明确指出：原子命题是用肯定语气表达的具有真假意义的简单陈述句。上述例题中。直接令P表示“杭州不是中国的首都”。来做符号化，是不符合要求的。在上述第2个命题中，如果简单地用一个符号P表示“张三虽然学习努力但成绩并不优秀”做符号化就更不符合符号化的要求了。,复合命题的构成：是用“联结词”将原子命题联结起来构成的。归纳自然语言中的联结词，定义了六个逻辑联结词，分别是：(1)否定“”(2)合取“”(3)析取“”(4)异或“”(5)蕴涵“”(6)等价“”,1.1.5联结词,否定联结词“”,表示：“不成立”，“不”。用于：对一个命题P的否定，写成P，并读成“非P”。P的真值：与P真值相反。例1.4P：2是素数。P：2不是素数。,PP,10,01,定义1.1设p为命题，复合命题“非p”（或“p的否定”）称为p的否定式，记作p，符号称为否定联结词,#includevoidmain()intz,p;printf(验证逻辑连接词否定);printf(t);printf(z=!p);while(p!=0,否定连接词的程序实现,定义1.2设p,q为二命题，复合命题“p并且q”（或“p与q”）称为p与q的合取式，记作pq，符号称为合取联结词。运算规则：属于双目运算符,合取联结词,表示：“并且”、“不但而且.”、“既又.”“尽管还”例如P：小王能唱歌。Q：小王能跳舞。PQ：小王能歌善舞。PQ读成P合取Q。PQ的真值为真，当且仅当P和Q的真值均为真。,合取运算特点：只有参与运算的二命题全为真时，运算结果才为真，否则为假。自然语言中的表示“并且”意思的联结词，如“既又”、“不但而且”、“虽然但是”、“一面一面”等都可以符号化为注意：不要见到“与”或“和”就使用联结词！例1.4下列命题符号化(1)北京不仅是中国的首都而且是一个故都p：北京是中国的首都。q：北京是一个故都。pq：北京是中国的首都并且是一个故都。牛启飞和林妹妹是好朋友P:牛启飞和林妹妹是好朋友,例1.5将下列命题符号化.(3)王晓既用功又聪明.(4)王晓不仅聪明，而且用功.(5)王晓虽然聪明，但不用功.(6张辉与王丽都是三好生.(7)张辉与王丽是同学.解令p：王晓用功，q：王晓聪明，则(3)pq(4)pq(5)pq.令r:张辉是三好学生，s:王丽是三好学生(6)rs.(7)令t:张辉与王丽是同学，t是简单命题.,#includevoidmain()intz,p,q;printf(验证逻辑连接词合取);printf(t);printf(z=pq);while(p!=0,合取连接词的程序实现,定义1.3设p,q为二命题，复合命题“p或q”称为p与q的析取式，记作pq，符号称为析取联结词。运算规则：属于双目运算符,析取联结词“”,例1.6期中考试张三和李四中有人考90分P:期中考试张三考了90分Q:期中考试李四考了90分,例1.7.第一节课上数学或者上英语,P：第一节上数学。Q：第一节上英语。该复合命题可写成PQ，读成P异或Q。PQ的真值为F，当且仅当P与Q的真值相同,000,011,101,110,上例中的或者是不可兼取的或，也称之为异或、排斥或。即“”.,PQ,例1.8将下列命题符号化(1)2或4是素数.(2)2或3是素数.(3)4或6是素数.(4)小元元只能拿一个苹果或一个梨.(5)王晓红生于1975年或1976年.解令p:2是素数,q:3是素数,r:4是素数,s:6是素数则(1),(2),(3)均为相容或.分别符号化为:pr,pq,rs,它们的真值分别为1,1,0.,例1.8将下列命题符号化(1)2或4是素数.(2)2或3是素数.(3)4或6是素数.(4)小元元只能拿一个苹果或一个梨.(5)王晓红生于1975年或1976年.而(4),(5)为排斥或.令t:小元元拿一个苹果，u:小元元拿一个梨，则(4)符号化为(tu)(tu).或令v:王晓红生于1975年,w:王晓红生于1976年,则(5)符号化为(vw)(vw),能符号化为vw,为什么?,析取运算特点：只有参与运算的二命题全为假时，运算结果才为假，否则为真。这里的析取运算只能表示自然语言中的“相容或”的意思，特别要注意自然语言里的“排斥或”。再举例说明：（1）小王爱打球或爱跑步。设p：小王爱打球。q：小王爱跑步。则上述命题可符号化为：pq（2）火车8：00或9：00到站。设p：火车8：00到站。q：火车9：00到站。则上述命题就不可简单符号化为：pq而应描述为(pq)(pq)或pq,（3）今天晚上我在家看电视或去剧场看戏。这个命题中的“或”是排斥或，表示二者只居其一，不能同时成立。令p:今天晚上我在家看电视q:今天晚上我去剧场看戏上述命题不能表示为pq，因为按“”的定义。P,q都为真时，pq也为真，而上题当p，q都为真时，命题为假，这是由于一个人不可能既在家，又在剧场里,所以不能用pq表示,要用排斥或()表示上述命题可表示为：(pq)(pq)或pq,#includevoidmain()intz,p,q;printf(验证逻辑连接词析取);printf(t);printf(z=pq);while(p!=0,析取连接词的程序实现,定义1.4设p,q为二命题,复合命题“如果p,则q”称为p与q的蕴涵式，记作pq，并称p为蕴涵式的前件，q为蕴涵式的后件，符号称为蕴涵联结词。与自然语言的不同：前件与后件可以没有任何内在联系！运算规则：属于双目运算符,蕴涵(条件)“”,例1.9如果张三能考90分，那么李四也考90分P：“张三考90分”Q：“李四考90分”,例1.10将下列命题符号化(1)如果你今年离散数学考100分，那么就奖励你100元。P：你今年离散数学考100分。Q：奖励你100元。,(2)如果22=5，则雪是黑的令p：22=5，q：雪是黑的，于是命题符号化为pq这是和人们日常生活中语言不一致的地方(3)如果我得到这部小说，那么我今夜就读完它令p1：我得到这部小说q1：我今夜就读完它于是命题符号化为p1q1,#includevoidmain()intz,p,q;printf(验证逻辑连接词蕴涵);printf(t);printf(z=pq);while(p!=0,蕴涵连接词的程序实现,定义1.5设p,q为二命题，复合命题“p当且仅当q”称为p与q的等价式，记作pq，符号称为等价联结词。说明:(1)pq的逻辑关系:p与q互为充分必要条件(2)pq为真当且仅当p与q同真或同假运算规则：属于双目运算符,等价(双条件）联结词“”,例1.11将下列命题符号化(1)张三能考90分当且仅当李四也能考90分P：张三考90分Q：李四考90分命题符号化为PQ,(2)2是素数当且仅当三角形有3条边；(3)雪是黑的当且仅当太阳从东方升起.解:(2)令p：2是素数，q：三角形有3条边，则原命题符号化为pq.(3)令p1：雪是黑，q1：太阳从东方升起，则原命题符号化为p1q1，这是假命题以上例子充分说明:等价运算pq表示的逻辑关系是：p与q互为充分必要条件。相当于(pq)(qp).,例1.12求下列复合命题的真值(1)2+24当且仅当3+36.(2)2+24当且仅当3是偶数.(3)2+24当且仅当太阳从东方升起.(4)2+24当且仅当美国位于非洲.(5)函数f(x)在x0可导的充要条件是它在x0连续.它们的真值分别为1，0，1，0，0.,例1.13将下列命题符号化(1)如果你走路时看书，那么你一定会成为近视眼。解令p：你走路；q：你看书；r：你是近视眼。于是，上述语句可表示为（pq）r。(2)设p，q，r的意义如下：p：苹果是甜的；q：苹果是红的；r：我买苹果。试用日常语言复述下述复合命题：(a)(pq)r(b)(pq)r解：(a)如果苹果甜且红，那么我买。(b)我没买苹果，因为苹果不甜也不红。,#includevoidmain()intz,p,q;printf(验证逻辑连接词双条件);printf(t);printf(z=pq);while(p!=0,双条件连接词的程序实现,以上联结词组成的复合命题的真假值一定要根据它们的定义去理解，而不能据日常语言的含义去理解。不能“对号入座”，如见到“或”就表示为”有些词也可表示为这五个联结词，如“但是”也可表示为“”。在今后我们主要关心的是命题间的真假值的关系，而不讨论命题的内容。,以上5种最基本、最常用、最重要的联结词可以组成一个集合，成为一个联结词集，其运算的优先级为：，对于同一级者，先出现者先运算。,例1.13将下列命题符号化铁和氧化合，但铁和氮不化合。如果我下班早，就去商店看看，除非我很累。李四是信息技术学院的学生，他住在1312室或1313室。,铁和氧化合，但铁和氮不化合。P：“铁和氧化合”Q：“铁和氮化合”则用符号表示:P(Q)如果我下班早，就去商店看看，除非我很累。P：“我很累”Q：“我下班早”R：“我去商店看看”则用符号表示为：(P)Q)R),李四是信息技术学院的学生，他住在1312室或1313室。P：“李四是信息技术学院的学生。”Q：“李四住1312室。”R：“李四住1313室。”则用符号表示:P(Q(R)(Q)R),小结,命题及其符号P、Q、R。构成复合命题的联结词、，以及由联结词构成的复合命题及其真假值。注意：有了命题和命题联结词，为了进一步的研究，今后，将只注重命题的真假值，而并不注意其内容含义，对命题联结词，只承认它由真值表定义，而不理会它的实际含义，这样，就可以在命题与命题联结词的基础上建立起一个形式系统。,练习：填空1)已知PQ为T，则P为()，Q为()。2)已知PQ为F，则P为()，Q为()。3)已知P为F，则PQ为()。4)已知P为T，则PQ为()。5)已知PQ为T，且P为F，则Q为()。6)已知PQ为F，则P为()，Q为()。7)已知P为F，则PQ为()。8)已知Q为T，则PQ为()。9)已知PQ为F，则P为()，Q为()。,10)已知P为T，PQ为T，则Q为()。11)已知Q为T,PQ为T，则P为()。12)已知PQ为T，P为T,则Q为().13)已知PQ为F，P为T,则Q为().14)PP的真值为().15)PP的真值为()。,16)说离散数学无用且枯燥无味是不对的。P：离散数学是有用的。Q：离散数学是有味的。,该命题可写成：(PQ),17)如果小张与小王都不去，则小李去。P：小张去。Q：小王去。R：小李去,该命题可写成：(PQ)R该命题可写成：(PQ)R,1.2命题公式及其分类基本概念简单命题/命题常项/命题常元：真值唯一确定的陈述句。命题变项/命题变元：真值可以变化的陈述句。命题常项与命题变项都可以用p,q,r等表示，具体情况由上下文确定。合式公式/命题公式：将命题变项用联结词和圆括号按一定的逻辑关系联结起来的符号串。当使用联结词集，时，合式公式定义如下：,第一章命题逻辑,定义1.6（1）单个命题变项是合式公式，并称为原子命题公式。（2）若A是合式公式，则(A)也是合式公式。（3）若A，B是合式公式，则(AB)，(AB)(AB)，(AB)也是合式公式。（4）只有有限次地应用(1)(3)形成的符号串才是合式公式。合式公式也称为命题公式或命题形式，并简称为公式。,第一章命题逻辑,可以看出所谓的合式公式可以解释为合法的命题公式之意，也称之为命题公式，有时也简称公式。下面的式子不是合式公式：PR，(PQ)Rpqt,(pw)q)下面的式子才是合式公式：(PQ)，(PR)，(PQ)R)(pq),(rt)e,p，(p),约定：为方便，最外层括号可以不写，前面的合式公式可以写成：PQ，PR，(PQ)R上述归纳定义方式中的符号A,B不同于具体公式里面的p,q,r等符号，可以用来表示任意的合式公式,定义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层公式。,第一章命题逻辑,例:公式p0层p1层pq2层(pq)r3层(pq)r)(rs)4层,第一章命题逻辑,定义1.8公式赋值设p1，p2，pn是出现在公式A中的全部的命题变项，给p1，p2，pn各指定一个真值，称为对A的一个赋值或解释。比如：对公式(pq)r一组赋值为011(意即令p=0,q=1,r=1)可得真值为1，另一组赋值为010可得真值为0；还有000，001，111考虑：含有n个命题变项的公式共有多少个不同的赋值？,第一章命题逻辑,2n个赋值.,若指定的一组值使A的真值为1，则称这组值为A的成真赋值。(使公式为真的赋值)如对公式(pq)r赋值011，还有?若指定的一组值使A的真值为0，则称这组值为A的成假赋值。(使公式为假的赋值)如对公式(pq)r赋值010，还有?,第一章命题逻辑,真值表将命题公式A在所有赋值下取值情况列成表称做A的真值表。对公式A构造真值表的具体步骤为：（1）找出公式中所有的全体命题变项p1，p2，pn，列出2n个赋值。（2）按从低到高的顺序写出公式的各个层次（3）对应各个赋值计算出各层次的真值，直到最后计算出公式的真值。,第一章命题逻辑,例1.14(1)求命题公式(pq)r的真值表,第一章命题逻辑,(2)求命题公式(pq)(qp)的真值表,第一章命题逻辑,(3)求命题公式(pq)q的真值表。,第一章命题逻辑,(4)求(qp)qp的真值表,(5)求(pq)q的真值表,(6)求(pq)r的真值表,定义1.9设A为任一命题公式，（1）若A在其各种赋值下的取值均为真，则称A是重言式或永真式。（2）若A在其各种赋值下的取值均为假，则称A是矛盾式或永假式。（3）若A不是矛盾式，则称A为可满足式。,命题公式的类型,重言式特性重言式的否定是矛盾，矛盾的否定是重言式。两个重言式的合取、析取、蕴含、等价均为重言式。若两个公式的等价是重言式，则此两公式对任何指派必同真假,真值表的作用：（1）表示出公式的成真或成假赋值。（2）判断公式类型：(a)若真值表最后一列全为1，则为重言式；(b)若真值表最后一列全为0，则为矛盾式；(c)若真值表最后一列至少有一个1，则为可满足式；,第一章命题逻辑,有很多公式具有相同的真值表。如：,第一章命题逻辑,还有pq、pq等,1.3等值演算定义1.10设A,B是两个命题公式，若A，B构成的等价式AB为重言式，则称A与B是等值的,记作AB.即AB的充要条件是AB为重言式判断两个公式等值的方法1：真值表法。,第一章命题逻辑,由真值表可知，两个公式为等值式。,例1.15判断公式p(qr)与(pq)r是否等值,例1.16证明PQ(PQ)(QP),两者的真值表相等，故PQ(PQ)(QP)不难验证：PPPPP(PP)QQPPQQ,注意：“”，“”的区别和联系：,区别：（1）“”是命题联结词，AB是一个命题公式，该公式取值可以是真，可以是假。（2）“”不是命题联结词，而是公式的等价关系符，AB不代表命题，而表示的是命题A、B有完全相同的真值。联系：AB当且仅当AB是永真式。,等价公式的性质,自反性：即对任意公式A，有AA；对称性：即对任意公式A和B，若AB，则BA；传递性：即对任意公式A和B，C，若AB，BC,则AC。,等值演算：由已知的等值式推演出另外一些等值式的过程。等值演算中使用的一条重要规则：置换规则定理1.1设(A)是含公式A的命题公式,(B)是用公式B置换了(A)中所有的A后得到的命题公式，若BA，则(A)(B)。,第一章命题逻辑,等值演算与置换规则,等值演算:由已知的等值式推演出新的等值式的过程置换规则：若AB,则(B)(A)等值演算的基础：(1)等值关系的性质：自反、对称、传递(2)基本的等值式(3)置换规则,基本等值式,双重否定律:AA等幂律：AAA,AAA交换律:ABBA,ABBA结合律:(AB)CA(BC)(AB)CA(BC)分配律:A(BC)(AB)(AC)A(BC)(AB)(AC),基本等值式(续),德摩根律:(AB)AB(AB)AB吸收律:A(AB)A,A(AB)A零律:A11,A00同一律:A0A,A1A排中律:AA1矛盾律:AA0,基本等值式(续),蕴涵等值式:ABAB等价等值式:AB(AB)(BA)假言易位:ABBA等价否定等值式:ABAB归谬论:(AB)(AB)A注意:A,B,C代表任意的命题公式牢记这些等值式是继续学习的基础,等值演算的用途一：证明等值式。例1.14验证p(qr)(pq)r右(pq)r蕴涵等值式pqr德摩根律p(qr)结合律p(qr)蕴涵等值式p(qr)蕴涵等值式注:ABAB,第一章命题逻辑,例1.15证明:p(qr)(pq)r用等值演算不能直接证明两个公式不等值,证明两个公式不等值的基本思想是找到一个赋值使一个成真,另一个成假.方法一真值表法（自己证）方法二观察赋值法.容易看出000,010等是左边的成真赋值，是右边的成假赋值.方法三用等值演算先化简两个公式，再观察(用公式ABAB和(AB)AB),例1.16用等值演算法判断下列公式的类型(1)q(pq)解q(pq)q(pq)（蕴涵等值式）q(pq)（德摩根律）p(qq)（交换律，结合律）p0（矛盾律）0（零律）由最后一步可知，该式为矛盾式.,(2)(pq)(qp)解(pq)(qp)(pq)(qp)（蕴涵等值式）(pq)(pq)（交换律）1由最后一步可知，该式为重言式.问：最后一步为什么等值于1？,(3)求证(PQ)(PQ)P证明(PQ)(PQ)(PQ)(PQ)(公式E20)(PQ)(PQ)(摩根定律)(PQ)(PQ)(对合律)P(QQ)(分配律)PT(互补律)P(同一律),总结：A为矛盾式当且仅当A0A为重言式当且仅当A1说明：演算步骤不惟一,应尽量使演算短些,例1.17：判断公式(pq)r的类型解：列出真值表如下，可知其是可满足式的,等值演算的用途三：文字断案问题。例：参见教材p11例1.11解：设pi,qi,ri,si分别表示A第i名,B第i名,C第i名,D第i名,由题意可知下列命题成立。(r1q2)(r1q2)1(r2s3)(r2s3)1(p2s4)(p2s4)11(r1q2)(r1q2)(r2s3)(r2s3)(r1q2)(r2s3)(r1q2)(r2s3)(r1q2)(r2s3)(r1q2)(r2s3),第一章命题逻辑,这里用到分配率公式(AB)(CD)=(AC)(BC)(AD)(BD),由于C不能既第一又第二,又B和C不能都第二,故(r1q2)(r2s3)0(r1q2)(r2s3)0,(r1q2)(r1q2)1(r2s3)(r2s3)1(p2s4)(p2s4)11(r1q2)(r2s3)(r1q2)(r2s3)111p2q2r1r2s3s4由上式可知r1,p2,s3是真命题，即C第一，A第二，D第三，B只能第四了。,例：参见教材p11例1.11解：设pi,qi,ri,si分别表示A第i名,B第i名,C第i名,D第i名,由题意可知下列命题成立。,第一章命题逻辑,定义1.12设p，q是两个命题，复合命题“p与q的否定”称为p与q的与非式，记作pq。“”称作与非联结词。pq为真当且仅当p，q不同时为真。由定义可知：pq=(pq)。pqpq001011101110,定义1.13设p，q是两个命题，复合命题“p或q的否定”称为p与q的或非式，记作pq，称作或非联结词。pq为真当且仅当p，q同时为假。由定义可知：pq=(pq),第一章命题逻辑,pqpq001010100110,第一章命题逻辑,定义1.14一个n(n1)维卡氏积0,1n到0,1的函数称为一个n元真值函数。设F是一个n元真值函数，则可记为F：0,1n0,1n个命题变项，共有2n个可能的赋值，对于每个赋值真值函数的函数值非0即1，于是n个命题变元共可以形成22个不同的真值函数。见教材P13表1.6,n,命题公式与真值函数,对于任何一个含n个命题变项的命题公式A，都存在惟一的一个n元真值函数F为A的真值表.等值的公式对应的真值函数相同.下表给出所有2元真值函数对应的真值表,每一个含2个命题变项的公式的真值表都可以在下表中找到.例如：pq,pq,(pq)(pq)q)等都对应表中的F14(2),2元真值函数对应的真值表,其实，每个真值函数可对应无穷多个命题公式，它们彼此都是等值的，有很多公式具有相同的真值表。如：,第一章命题逻辑,还有pq、pq等,第一章命题逻辑,定义1.15在一个联结词的集合中，如果一个联结词可由集合中的其他联结词定义，则称此联结词为冗余的联结词，否则称为独立的联结词。前面给出的5个联结词组成的联结词集为，由于pqpqpq(pq)(qp)(pq)(qp)所以，都是冗余的，又，中，由于pq(pq)(pq)所以可看成是冗余的，但在,中无冗余的联结词,第一章命题逻辑,定义1.16若任一真值函数都可以用仅含某一联结词的命题公式表示，则称该联结词集为全功能集。若一个联结词集的全功能集中不含冗余的的联结词，则称它为极小全功能集例1.17若已知，是全功能集，证明，也是全功能集证明由于，是全功能集，因而任一真值函数均可由仅含，中的联结词的命题公式表示，而对于任意的命题形式A，B，有ABAB因而任一真值函数均可由含，中的联结词的命题公式表示，所以它是全功能集。,定义1.1.7在仅含联结词,的命题公式A中，将换成，换成,若A中含0或1，就将0换成1，1换成0，所得命题公式称为A的对偶式，记作A*。从定义不难看出，(A*)*=A如:公式P(QF)的对偶公式为P(QF)定理1.2设A和A*互为对偶式，设p1,pn是出现在A和A*中的全部的命题变项，若将A和A*写成n元函数形式，则A(P1,P2,Pn)A*(P1,P2,Pn);A(P1,P2,Pn)A*(P1,P2,Pn).,1.5对偶与范式,定理1.3设A、B为两命题公式，若AB，则A*B*其中A*，B*分别为A，B的对偶式。该定理称为对偶原理由对偶原理可知，若A为重言式，则A*必为矛盾式，反之亦然给定一个命题公式，判断它是重言式、矛盾式、还是可满足式，这类问题称为判定问题。,第一章命题逻辑,1.5.1范式命题公式是千变万化的，这给研究命题演算带来困难，这里我们研究如何由一个命题公式化归为一个标准形式的问题，这样命题演算的研究问题就归结为对标准形式的研究问题，这种标准形式就叫范式。简单说范式就是命题公式形式的规范形式。这里约定在范式中只含有联结词、和,1.5.1.1析取范式与合取范式1)合取式与析取式合取式：是用“”联结命题变元或变元的否定构成的式子。如P、P、PQ、PQR析取式：是用“”联结命题变元或变元的否定构成的式子。如P、P、PQ、PQR注:PPPPPPP是合(析)取式.,析取范式它是这样一种标准形式，在此式内不出现联结词及，否定符号只出现在命题变元前。它是一个析取式，式中的每个析取项是个合取式，每个合取式中只包含命题变元或命题变元的否定。例如p(pq)(qr)此式即具有析取范式之形式注意:一个公式的析取范式并不唯一，如p(rq),可以写成(pp)(rq),合取范式它是这样一种标准形式，在此式内不出现联结词及，否定符号只出现在命题变元前。它是一个合取式，式中的每个合取项是个析取式，每个析取式中只包含命题变元或命题变元的否定。例如p(pq)(qr)此式即具有合取范式之形式注意:一个公式的合取范式并不唯一，如p(rq)可以写成(pp)(rq),定义1.9析取范式：由有限个简单合取式构成的析取式。如：pq,(pq)(pqr)合取范式：由有限个简单析取式构成的合取式。如：pq,（pq）（pqr）范式：析取范式与合取范式统称为范式。,第一章命题逻辑,设Ai(i=1,2,3,n)为简单合取式，则A=A1A2An就是析取范式，而B=A1A2An就是合取范式。析取范式和合取范式有下列性质：（1）一个析取范式是矛盾式它的每个简单合取式都是矛盾式。（2）一个合取范式是重言式它的每个简单析取式都是重言式。,第一章命题逻辑,定理1.4(范式存在定理)任一个命题公式都存在着与之等值的析取范式与合取范式。求范式的具体步骤：（1）消去对,来说冗余的联结词，即，。利用下列等值式：AB(AB)AB(AB)(AB),第一章命题逻辑,（2）否定词的消去或内移。利用下列等值式：AB(AB)(AB)AB(AB)AB（3）利用分配律：C(AB)（CA）（CB）C(AB)（CA）（CB）,第一章命题逻辑,例1.18求下列公式的析取范式与合取范式(1)A=(pq)r解(pq)r(pq)r（消去）pqr（结合律）这既是A的析取范式（由3个简单合取式组成的析取式），又是A的合取范式（由一个简单析取式组成的合取式）,(2)B=(pq)r解(pq)r(pq)r（消去第一个）(pq)r（消去第二个）(pq)r（否定号内移德摩根律）这一步已为析取范式（两个简单合取式构成）继续：(pq)r(pr)(qr)（对分配律）这一步得到合取范式（由两个简单析取式构成）,定义1.20在含有n个命题变项的简单合取式(简单析取式)中，若每个命题变项均以文字的形式在其中出现且仅出现一次，而且第i（1in）个文字出现在左起第i位上，称这样的简单合取式（简单析取式）为极小项（极大项）.,第一章命题逻辑,说明：n个命题变项产生2n个极小项和2n个极大项2n个极小项（极大项）均互不等值用mi表示第i个极小项，其中i是该极小项成真赋值的十进制表示.用Mi表示第i个极大项，其中i是该极大项成假赋值的十进制表示,mi(Mi)称为极小项(极大项)的名称.mi与Mi的关系:miMi,Mimi,第一章命题逻辑,由p,q两个命题变项形成的极小项与极大项,由p,q,r三个命题变项形成的极小项与极大项,主析取范式:由极小项构成的析取范式主合取范式:由极大项构成的合取范式例如，n=3,命题变项为p,q,r时，(pqr)(pqr)m1m3是主析取范式(pqr)(pqr)M1M5是主合取范式A的主析取范式:与A等值的主析取范式A的主合取范式:与A等值的主合取范式.,定理1.5任何命题公式都存在着与之等值的主析取范式和主合取范式,并且是惟一的.用等值演算法求公式的主范式的步骤：(1)先求析取范式（合取范式）(2)将不是极小项（极大项）的简单合取式（简单析取式）化成与之等值的若干个极小项的析取（极大项的合取），需要利用同一律（零律）、排中律（矛盾律）、分配律、幂等律等.(3)极小项（极大项）用名称mi（Mi）表示，并按角标从小到大顺序排序.,主析取范式:析取范式A1A2.An,其中每个Ai(i=1,2.n)都是小项。主析取范式的写法方法：列真值表列出给定公式的真值表。找出真值表中每个“1”对应的小项。用“”联结上述小项，即可。,例1.17求PQ和PQ的主析取范式PQPQPQ0011011010001111PQm0m1m3(PQ)(PQ)(PQ)PQm0m3(PQ)(PQ),主析取范式:由极小项构成的析取范式主合取范式:由极大项构成的合取范式,主合取范式合取范式A1A2.An,其中每个Ai(i=1,2.n)都是大项主合取范式的写法方法：列真值表列出给定公式的真值表。找出真值表中每个“0”对应的大项。用“”联结上述大项，即可。,例1.18求PQ和PQ的主合取范式PQPQPQ0011011010001111PQM2PQPQM1M2(PQ)(PQ),例1.18求(pq)(pr)的主析取范式。解法1：Pqrppqpr(pq)(pr)00010100011010010111101111111000100101011111001001110111,第一章命题逻辑,所以：(pq)(pr)m2m3m5m7(2,3,5,7),例1.19求(pq)(pr)的主合取范式。解法1：Pqrppqpr(pq)(pr)00010100011010010111101111111000100101011111001001110111,第一章命题逻辑,所以:(pq)(pr)M0M1M4M6(0,1,4,6),解法2：(pq)(pr)(pq)(pr)(合取范式)(pq)(rr)(pr)(qq)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(主合取范式)M0M1M4M6(0,1,4,6),第一章命题逻辑,例1.20判断命题公式(pq)(pr)的类型解法1：Pqrpqpr(pq)(pr)000101001101010101011101100000101011110101111111,第一章命题逻辑,该公式m0m1m2m3m5m6m7为可满足式,提示:用真值表判断命题公式的类型是最常用的方法,第一章命题逻辑,主析取范式的用途（主合取范式类似讨论）：1、求公式的成真/成假赋值：若公式A中含有n个命题变项，且A的主析取范式含s个极小项，则A有s个成真赋值，有2n-s个成假赋值。,第一章命题逻辑,2、判断公式的类型：设公式A中含有n个命题变项，则：（1）A为重言式A的主析取范式含全部2n个极小项。（2）A为矛盾式A的主析取范式不含任何极小项，记A的主析取范式为0。（3）A为可满足式A的主析取范式至少含一个极小项。,第一章命题逻辑,3、判断两个命题是否等值：设公式A、B中共含有n个命题变项，按n个命题变项求出A、B的主析取范式A、B。若A=B，则AB，否则A、B不等值。例1.21判断下列命题公式是否等值(1)(pq)(pr)与p(qr)(2)p(qr)与p(qr),第一章命题逻辑,第一章命题逻辑,pqrqrpqpr(pq)(pr)p(qr)0000111100101111010011110111111110000000101001001100100011111111,命题公式(pq)(pr)与p(qr)等值,第一章命题逻辑,pqrqrqrp(qr)p(qr)00001110010111010001001111111000101101010111000011111111,命题公式p(qr)与p(qr)不等值,(补充)范式的应用范式在逻辑设计方面有广泛的应用。例1.加法器的设计，有两个n位二进制数a,b相加和为s(s=a+b)，a,b分别写成：a=anan-1aiai-1.a2a1,+b=bnbn-1bibi-1.b2b1s=cnsnsn-1sisi-1s2s1其中si是第i位ai、bi及ci-1(ci-1是第i-1位向第i位的进位)的和，显然si是aibi及ci-1的函数,写成si(ai,bi,ci-1),它与ai,bi,ci-1的关系如下表：,aibici-1si(ai,bi,ci-1)00000011010101101001101011001111,在电路逻辑设计中用如下逻辑部件：非门与门或门,根据前边的表,列出si(ai,bi,ci-1)的主析取范式：si(ai,bi,ci-1)=(aibici-1)(aibici-1)(aibici-1)(aibici-1)(在指派001、010、100、111时Si为1)下面设计出Si(ai,bi,ci-1)的线路图。,si(ai,bi,ci-1)=(aibici-1)(aibici-1)(aibici-1)(aibici-1),重申：AB当且仅当A、B含有相同的真值表或A、B有相同的主析（合）取范式。,第一章命题逻辑,1.6推理理论,问题的引入-推理举例:(1)若函数f(x)在点x0处可导,则f(x)在该点处连续.(2)若ACBD，则AB且CD.推理:从前提出发推出结论的思维过程上面(1)是正确的推理，而(2)是错误的推理.证明:描述推理正确的过程.,推理就是根据一个或几个已知的判断得出一个新的判断的思维过程。称这些已知的判断为前提。得到的新的判断为前提的有效结论。实际上，推理的过程就是证明永真蕴含式的过程，即令A1，A2，An是已知的命题公式(前提)，若有A1A2.AnB则称B是A1，A2，An的有效结论，简称结论。,定义1.22若(A1A2Ak)B为重言式，则称A1，A2，Ak，推结论B的结论正确，B是A1，A2，Ak，的逻辑结论或有效结论，称(A1A2Ak)B为由前提A1，A2，Ak推结论B的推理的形式结构。同用“AB”表示“AB”是重言式,类似用“AB”表示“AB”是重言式，由前提A1，A2，Ak，推B的推理正确也记(A1A2Ak)B,对于任一组赋值，前提和结论的取值有以下四种情况：A1，A2，Ak为0，B为0。A1，A2，Ak为0，B为1。A1，A2，Ak为1，B为0。A1，A2，Ak为1，B为1。,判断推理是否正确的方法,真值表法等值演算法判断推理是否正确主析取范式法构造证明法证明推理正确说明：当命题变项比较少时，用前3个方法比较方便,此时采用形式结构“A1A2AkB”.而在构造证明时，采用“前提:A1,A2,Ak,结论:B”.,推理的另一种形式：命题公式A1，A2，Ak推B的推理正确当且仅当(A1A2Ak)B为重言式。于是推理的一般形式可转化为：(A1A2Ak)B推理正确转化为：A1A2AkB,第一章命题逻辑,于是，以后推理的形式就写作：前提：p,pq结论：q推理的形式结构：(p(pq)q即只需证明蕴涵式(p(pq)q为重言式。,第一章命题逻辑,例1.22利用真值表法论证(1)(PQ)PQ（？）(2)(PQ)(QR)PR（？）解：真值表如下：因使PQ，P同时为T的只有第一、二行，相应的Q：第一行为F，但第二行为T，所以Q不是PQ，P的有效结论,(2)(PQ)(QR)PR（？）真值表如下：所以(PQ)(QR)PR推理正确,例1.23：判断下列推理是否正确。1.今天杨尚树或去网吧或去教室。他没去教室，所以他去网吧了。设p：杨尚树去网吧。q：杨尚树去教室。则，前提：pq,q结论：p推理的形式结构：(pq)q)p,第一章命题逻辑,解法1：真值表法,该命题公式为重言式，说明推理正确，所以杨尚树去网吧,第一章命题逻辑,解法2：等值演算法：(pq)q)p(pq)(qq)p(pq)p(pq)ppqp1所以，推理正确，即（(pq)q)p,第一章命题逻辑,解：设各命题变元为P：材料不可靠。Q：计算有错误。则Q是前提PQ，P的有效结论，即P(PQ)Q列出真值表,例1.23_1:一份统计表格的错误或者是由于材料不可靠,或者是由于计算有错误,这份统计表格的错误不是由于材料不可靠,所以这份统计表格是由于计算有错误,解：设各命题变元为P：统计表格的错误是由于材料不可靠。Q：统计表格的错误是由于计算有错误。P(PQ)Q列出真值表从表中看到使PQ，P同时为T的只有第二行，这时Q的真值亦为T，所以Q，故Q是前提PQ，P的有效结论。即：P(PQ)Q,P(PQ)Q1111,例1.24：判断下列推理是否正确。2、若a能被4整除，则天