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

刘师少刘师少Tel：86613623（h）E-授课:51学时学分3教学目标:知识、能力、素质Discrete Mathematics什么是数理逻辑l数理逻辑：以数学的方法研究思维规律和推理过程的科学。l它首先引进一套符号体系，规定一些规则，导出一些定律，然后借助于这些符号、规则、定律，将逻辑推理的过程在形式上变得像代数演算一样，因此数理逻辑又称符号逻辑。微积分微积分力学、机械工程力学、机械工程 人类体力劳动自动化人类体力劳动自动化数理逻辑数理逻辑人工智能、知识工程人工智能、知识工程 脑力劳动自动化脑力劳动自动化数理逻辑数理逻辑l命题逻辑命题逻辑（数理逻辑的基础，以命题为研究（数理逻辑的基础，以命题为研究对象，研究基于命题的符号逻辑体系及推理对象，研究基于命题的符号逻辑体系及推理规律，也称命题演算）。规律，也称命题演算）。主要内容：主要内容：、命题与联结词、命题与联结词、命题公式、真值表、命题公式、真值表 、重言式、重言式、命题联结词的扩充、命题联结词的扩充、范式、范式、命题演算的推理规则和证明方法、命题演算的推理规则和证明方法 l谓词逻辑谓词逻辑（对命题逻辑的深入研究）。（对命题逻辑的深入研究）。第一章 命题逻辑这章是以“命题”为中心主要讨论：命题的表示、命题的演算命题演算中的公式，及其应用命题逻辑推理1.1.1命题的概念命题的概念命题：能够判断真假的陈述句。命题：能够判断真假的陈述句。命命题题的的真真值值：命命题题的的判判断断结结果果。真真值值只只取取两个值：两个值：真（真（1）、假（）、假（0）。）。真命题：真值为真的命题。真命题：真值为真的命题。假命题：真值为假的命题。假命题：真值为假的命题。判断命题的两个步骤：判断命题的两个步骤：)1、是否为陈述句；、是否为陈述句；2、是否有确定的、唯一的真值、是否有确定的、唯一的真值。1.1命题符号化及联结词命题符号化及联结词命题的特征：命题的特征：陈述句陈述句真假必居其一，且只居其真假必居其一，且只居其一。一。例例1.11.1 下列句子中那些是命题？下列句子中那些是命题？(1)是无理数是无理数.(2)2+58.(3)x+53.(4)你有铅笔吗？你有铅笔吗？(5)这只兔子跑得真快呀！这只兔子跑得真快呀！(6)请不要讲话！请不要讲话！(7)我正在说谎话我正在说谎话.真命题真命题假命题假命题真值不确定真值不确定疑问句疑问句感叹句感叹句祈使句祈使句悖论悖论(3)(7)都不是命题都不是命题第一章 命题逻辑祈使句，感叹句，疑问句均不是命题。再如 把门关上！你到哪里去？语句既为真，同时又包含假的不是命题，这样的句子称为“悖论悖论”。如 他正在说谎。（在命题逻辑中不讨论这类问题）例例1.2 1.2 判定下面这些句子哪些是命题。判定下面这些句子哪些是命题。(8)2(8)2是个素数。是个素数。(9)(9)雪是黑色的。雪是黑色的。(10)2015(10)2015年人类将到达火星。年人类将到达火星。(11)(11)如果如果 a ba b且且 b cb c，则，则 a ca c。(12)x+y 5 (12)x+y 910.皇马中国之行没有提升国家队的水平。皇马中国之行没有提升国家队的水平。第一章 命题逻辑模糊逻辑模糊逻辑1.1.3 1.1.3 命题及其真值的抽象化命题及其真值的抽象化 在本书中，用小写英文字母在本书中，用小写英文字母p,q,r,pp,q,r,p1 1,p,p2 2,p,p3 3等表示命题等表示命题,用用“1”“1”、“0”“0”分别表示真值的真、假。分别表示真值的真、假。例例1.21.2：p p：罗纳尔多是球星。罗纳尔多是球星。q q：5 5是负数。是负数。p p3 3：明天天气晴。明天天气晴。皆为符号化的命题，其真值依次为皆为符号化的命题，其真值依次为1 1、0 0、1 1或或0 0。若令若令 p p：是有理数，则是有理数，则 p p 的真值为的真值为 0 0 q q：2+5=72+5=7，则则 q q 的真值为的真值为 1 1 分类分类 根据其真值分类：根据其真值分类：真命题。真命题。假命题。假命题。根据其复杂程度分类：根据其复杂程度分类：简单命题或原子命题。简单命题或原子命题。复合命题。复合命题。1.1.4 1.1.4 命题的分类命题的分类简简单单/原原子子命命题题：由由不不能能再再分分解解为为更更简简单单的的陈陈述句的陈述句构成。述句的陈述句构成。如上例中的命题。如上例中的命题。复复合合命命题题：由由简简单单命命题题与与联联结结词词按按一一定定规规则则复复合而成的命题合而成的命题例例1.3(1)若三角形等腰，则两底角相等(2)若行列式两行成比例，则行列式值为01.1.4 1.1.4 命题的分类命题的分类例例1.1.3 3 由简单命题能构造更加复杂的命题由简单命题能构造更加复杂的命题 期中考试，张三没有考及格。期中考试，张三没有考及格。期中考试，张三和李四都及格了。期中考试，张三和李四都及格了。期中考试，张三和李四中有人考期中考试，张三和李四中有人考9090分。分。如果张三能考如果张三能考9090分，那么李四也能考分，那么李四也能考9090分。分。张三能考张三能考9090分当且仅当李四也能考分当且仅当李四也能考9090分。分。联结词和复合命题上述诸如上述诸如“没有没有”、“如果如果那么那么”等词等词称为联结词。称为联结词。由联结词和命题连接而成的更加复杂命题称由联结词和命题连接而成的更加复杂命题称为复合命题；相对地，不能分解为更简单命为复合命题；相对地，不能分解为更简单命题的命题成为简单命题。（命题的分类）题的命题成为简单命题。（命题的分类）复合命题的真假完全由构成它的简单命题的复合命题的真假完全由构成它的简单命题的真假所决定。真假所决定。注：简单命题和复合命题的划分是相对的。注：简单命题和复合命题的划分是相对的。在命题逻辑的符号化过程中，通常的要求是每一在命题逻辑的符号化过程中，通常的要求是每一个引进的表示命题的符号都表示一个原子命题。个引进的表示命题的符号都表示一个原子命题。例如：将下列命题符号化例如：将下列命题符号化(1)杭州不是中国的首都。杭州不是中国的首都。(2)张三虽然学习努力但成绩并不优秀。张三虽然学习努力但成绩并不优秀。解解(1)令令P：杭州是中国的首都。杭州是中国的首都。则命题则命题“杭州不是中国的首都杭州不是中国的首都”符号化为：符号化为：P(2)令令P：张三学习努力。张三学习努力。Q：张三成绩优秀。张三成绩优秀。则命题则命题“张三虽然学习努力但成绩并不优秀。张三虽然学习努力但成绩并不优秀。”符号化为：符号化为：PQ。由此我们进一步明确指出：由此我们进一步明确指出：原原子子命命题题是是用用肯肯定定语语气气表表达达的的具具有有真真假假意意义义的的简简单单陈陈述述句句。上上述述例例题题中中。直直接接令令P表表示示“杭杭州州不不是是中中国国的的首首都都”。来来做做符符号号化化，是是不符合要求的。不符合要求的。在在上上述述第第2个个命命题题中中，如如果果简简单单地地用用一一个个符符号号P表表示示“张张三三虽虽然然学学习习努努力力但但成成绩绩并并不不优优秀秀”做符号化就更不符合符号化的要求了。做符号化就更不符合符号化的要求了。复合命题的构成：是用复合命题的构成：是用“联结词联结词”将原子命题联结将原子命题联结起来构成的。起来构成的。归纳自然语言中的联结词，定义了六个逻辑联结词，归纳自然语言中的联结词，定义了六个逻辑联结词，分别是：分别是：(1)(1)否定否定“”(2)(2)合取合取“”(3)(3)析取析取“”(4)(4)异或异或“”(5)(5)蕴涵蕴涵“”(6)(6)等价等价“”1.1.5 1.1.5 联结词联结词否定联结词否定联结词“”l表示：表示：“不成立不成立”，“不不”。l用于：对一个命题用于：对一个命题P P的否定，写成的否定，写成 P P，并并读读成成“非非P P”。l P P的真值：与的真值：与P P真值相反。真值相反。l例例1.4 P1.4 P：2 2是素数。是素数。P P：2 2不是素数。不是素数。PP1001定义定义1.1 1.1 设设p p为命题为命题，复合命题复合命题“非非p”p”（或或“p p 的否定的否定”）称为）称为p p的否定式，的否定式，记作记作 p p，符号符号 称为否定联结词称为否定联结词#includevoidmain()intz,p;printf(验证逻辑连接词否定);printf(t);printf(z=!p);while(p!=0&p!=1)printf(pleaseinput(0or1):P=);scanf(%d,&p);if(p=0)z=1;elsez=0;printf(z=%dn,z);否定连接词否定连接词 的程序实现的程序实现定义定义1.2设设p,q为二命题，复合命题为二命题，复合命题“p并且并且q”（或或“p与与q”）称为称为p与与q的合取式，记的合取式，记作作pq，符号符号称为合取联结词。称为合取联结词。运算规则：属于双目运算符运算规则：属于双目运算符PqPq000010100111合取联结词合取联结词 表示：表示：“并且并且”、“不但不但而且而且.”.”、“既既又又 .”“.”“尽管尽管还还”例如例如 P P：小王能唱歌。：小王能唱歌。Q Q：小王能跳舞。：小王能跳舞。PQ PQ：小王能歌善舞。：小王能歌善舞。PQ PQ 读成读成P P合取合取Q Q。PQ PQ的真值为的真值为真真，当且仅当，当且仅当P P和和Q Q的真值均的真值均为为真真。合取运算特点合取运算特点：只有参与运算的二命题全为真时，运：只有参与运算的二命题全为真时，运算结果才为真，否则为假。自然语言中的表示算结果才为真，否则为假。自然语言中的表示“并且并且”意思的联结词，如意思的联结词，如“既既又又”、“不但不但而且而且”、“虽虽然然但但是是”、“一一面面一一面面”等等都都可可以以符符号号化化为为注意：不要见到注意：不要见到“与与”或或“和和”就使用联结词就使用联结词 ！例例1.41.4 下列命题符号化下列命题符号化(1)(1)北京不仅是中国的首都而且是一个故都北京不仅是中国的首都而且是一个故都 p p：北京是中国的首都。北京是中国的首都。q q：北京是一个故都。北京是一个故都。pqpq：北京是中国的首都并且是一个故都。北京是中国的首都并且是一个故都。(2)(2)牛启飞和林妹妹是好朋友牛启飞和林妹妹是好朋友(3)(3)P:P:牛启飞和林妹妹是好朋友牛启飞和林妹妹是好朋友例例1.1.5 5 将下列命题符号化将下列命题符号化.(3)(3)王晓既用功又聪明王晓既用功又聪明.(4)(4)王晓不仅聪明，而且用功王晓不仅聪明，而且用功.(5)(5)王晓虽然聪明，但不用功王晓虽然聪明，但不用功.(6 (6 张辉与王丽都是三好生张辉与王丽都是三好生.(7)(7)张辉与王丽是同学张辉与王丽是同学.解解 令令 p p：王晓用功，：王晓用功，q q：王晓聪明，则：王晓聪明，则 (3)(3)p pq q (4)(4)p pq q (5)(5)p p q q.令令 r r:张辉是三好学生，张辉是三好学生，s s:王丽是三好学生王丽是三好学生 (6)(6)r rs s.(7)(7)令令 t t:张辉与王丽是同学，张辉与王丽是同学，t t 是简单命题是简单命题 .#includevoidmain()intz,p,q;printf(验证逻辑连接词合取);printf(t);printf(z=pq);while(p!=0&p!=1)|(q!=0&q!=1)printf(pleaseinput(0or1):P=);scanf(%d,&p);printf(pleaseinput(0or1):q=);scanf(%d,&q);if(p=1)&(q=1)z=1;elsez=0;printf(z=%dn,z);合取合取连接词的程序实现连接词的程序实现定义定义1.3设设p,q为二命题，复合命题为二命题，复合命题“p或或q”称为称为p与与q的析取式，记作的析取式，记作pq，符号符号称称为析取联结词。为析取联结词。运算规则：属于双目运算符运算规则：属于双目运算符PqPq000011101111析取联结词析取联结词“”例例1.6 1.6 期中考试张三和李四中有人考期中考试张三和李四中有人考9090分分 P:P:期中考试张三考了期中考试张三考了9090分分 Q:Q:期中考试李四考了期中考试李四考了9090分分PQPQ000011101111例例1.7.1.7.第一节课上数学或者上英语第一节课上数学或者上英语P P：第一节上数学第一节上数学。Q Q：第一节上英语。第一节上英语。该该复合命题复合命题 可写成可写成 P QP Q，读读 成成P P异或异或Q Q。PQ PQ的真值为的真值为 F F，当且仅当当且仅当P P与与Q Q的真值的真值 相同相同000011101110上例中的或者是不可兼取的或，也称之为异或、排斥上例中的或者是不可兼取的或，也称之为异或、排斥或。即或。即“”“”.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.8 将下列命题符号化将下列命题符号化 (1)2(1)2或或4 4是素数是素数.(2)2(2)2或或3 3是素数是素数.(3)4(3)4或或6 6是素数是素数.(4)(4)小元元只能拿一个苹果或一个梨小元元只能拿一个苹果或一个梨.(5)(5)王晓红生于王晓红生于19751975年或年或19761976年年.而而 (4),(5)(4),(5)为排斥或为排斥或.令令 t:t:小元元拿一个苹果，小元元拿一个苹果，u:u:小元元拿一个梨，小元元拿一个梨，则则 (4)(4)符号化为符号化为(t(t u)(u)(tu).tu).或或 令令v:v:王晓红生于王晓红生于19751975年年,w:,w:王晓红生于王晓红生于19761976年年,则则 (5)(5)符号化为符号化为 (v(v w)(w)(vw),vw),能符号化为能符号化为 vw,vw,为什么为什么?析取运算特点析取运算特点：只有参与运算的二命题全为假时，运：只有参与运算的二命题全为假时，运算结果才为假，否则为真。算结果才为假，否则为真。这这里里的的析析取取运运算算只只能能表表示示自自然然语语言言中中的的“相相相相容容容容或或或或”的的意意思思，特特别别要要注注意意自自然然语语言言里里的的“排排排排斥斥斥斥或或或或”。再再举举例例说说明：明：（1）小王爱打球或爱跑步。）小王爱打球或爱跑步。设设p：小王爱打球。小王爱打球。q：小王爱跑步。小王爱跑步。则上述命题可符号化为：则上述命题可符号化为：pq（2）火车火车8：00或或9：00到站。到站。设设p：火车火车8：00到站。到站。q：火车火车9：00到站。到站。则上述命题就不可简单符号化为：则上述命题就不可简单符号化为：pq而应描述为而应描述为(p q)(pq)或或pq（3）今天晚上我在家看电视或去剧场看戏。）今天晚上我在家看电视或去剧场看戏。这这个个命命题题中中的的“或或”是是排排斥斥或或，表表示示二二者者只只居其一，不能同时成立。居其一，不能同时成立。令令p:今今天天晚晚上上我我在在家家看看电电视视q:今今天天晚晚上上我我去去剧剧场场看戏看戏上上述述命命题题不不能能表表示示为为pq，因因为为按按“”的的定定义义。P,q都都为为真真时时，pq也也为为真真，而而上上题题当当p，q都都为为真真时时，命命题题为为假假，这这是是由由于于一一个个人人不不可可能能既既在在家家，又又在在剧剧场场里里,所所以以不不能能用用pq表表示示,要要用用排斥或排斥或()表示表示上述命题可表示为：上述命题可表示为：(p q)(pq)或或pq#includevoidmain()intz,p,q;printf(验证逻辑连接词析取);printf(t);printf(z=pq);while(p!=0&p!=1)|(q!=0&q!=1)printf(pleaseinput(0or1):P=);scanf(%d,&p);printf(pleaseinput(0or1):q=);scanf(%d,&q);if(p=1)|(q=1)z=1;elsez=0;printf(z=%dn,z);析取析取连接词的程序实现连接词的程序实现定义定义1.4设设p,q为二命题为二命题,复合命题复合命题“如果如果p,则则q”称为称为p与与q的蕴涵式，记作的蕴涵式，记作pq，并称并称p为蕴涵式的前件，为蕴涵式的前件，q为蕴涵式的为蕴涵式的后件，符号后件，符号称为蕴涵联结词。称为蕴涵联结词。与自然语言的不同：与自然语言的不同：前件与后件可以没有任何内在联系！前件与后件可以没有任何内在联系！运算规则：属于双目运算符运算规则：属于双目运算符PqPq001011100111蕴涵蕴涵(条件条件)“”例例1.9 1.9 如果张三能考如果张三能考9090分，那么李四也考分，那么李四也考9090分分 P P：“张三考张三考9090分分”Q Q：“李四考李四考9090分分”PQPQ001011100111例例1.10 1.10 将下列命题符号化将下列命题符号化 (1)(1)如果你今年离散数学考如果你今年离散数学考100100分，那么就分，那么就 奖励你奖励你100100元。元。P P：你今年离散数学考：你今年离散数学考100100分。分。Q Q：奖励你：奖励你100100元。元。PQPQ00101110011 1(2)如果如果2 2=5，则雪是黑的，则雪是黑的令令p：2 2=5，q：雪是黑的，雪是黑的，于是命题符号化为于是命题符号化为pq这是和人们日常生活中语言不一致的地方这是和人们日常生活中语言不一致的地方(3)如果我得到这部小说，那么我今夜就读完它如果我得到这部小说，那么我今夜就读完它令令p1：我得到这部小说我得到这部小说q1：我今夜就读完它我今夜就读完它于是命题符号化为于是命题符号化为p1q1#includevoidmain()intz,p,q;printf(验证逻辑连接词蕴涵);printf(t);printf(z=pq);while(p!=0&p!=1)|(q!=0&q!=1)printf(npleaseinput(0or1):P=);scanf(%d,&p);printf(npleaseinput(0or1):q=);scanf(%d,&q);if(p=1)&(q=0)z=0;elsez=1;printf(z=%dn,z);蕴涵蕴涵连接词的程序实现连接词的程序实现定义定义1.5设设p,q为二命题，复合命题为二命题，复合命题“p当且仅当当且仅当q”称为称为p与与q的等价式，记作的等价式，记作pq，符号符号称为等价联结词。称为等价联结词。说明说明:(1)pq的逻辑关系的逻辑关系:p与与q互为充分必要条件互为充分必要条件(2)pq为真当且仅当为真当且仅当p与与q同真或同假同真或同假运算规则：属于双目运算符运算规则：属于双目运算符PqPq001010100111等价等价(双条件）联结词双条件）联结词“”例1.11 将下列命题符号化将下列命题符号化 (1)张三能考90分当且仅当李四也能考90分 P：张三考90分 Q：李四考90分 命题符号化为命题符号化为 PQPQPQ001010100111(2)2是素数当且仅当三角形有是素数当且仅当三角形有3条边；条边；(3)3)雪是黑的当且仅当太阳从东方升起雪是黑的当且仅当太阳从东方升起.解解:(2)令令p：2是素数，是素数，q：三角形有三角形有3条边，条边，则原命题符号化为则原命题符号化为pq q.(3)令令p1：雪是黑，雪是黑，q1：太阳从东方升起，太阳从东方升起，则原命题符号化为则原命题符号化为p1 q1 ，这是假命题这是假命题以上例子充分说明以上例子充分说明:等价运算等价运算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：你是近视眼。你是近视眼。于是，上述语句可表示为（于是，上述语句可表示为（p q）r。(2)设设p，q，r的意义如下：的意义如下：p：苹果是甜的；苹果是甜的；q：苹果是红的；苹果是红的；r：我买苹果。我买苹果。试用日常语言复述下述复合命题：试用日常语言复述下述复合命题：(a)(p q)r(b)(pq)r解：解：(a)如果苹果甜且红，那么我买。如果苹果甜且红，那么我买。(b)我没买苹果，因为苹果不甜也不红。我没买苹果，因为苹果不甜也不红。#includevoidmain()intz,p,q;printf(验证逻辑连接词双条件);printf(t);printf(z=pq);while(p!=0&p!=1)|(q!=0&q!=1)printf(npleaseinput(0or1):P=);scanf(%d,&p);printf(npleaseinput(0or1):q=);scanf(%d,&q);if(p=q)z=1;elsez=0;printf(z=%dn,z);双条件双条件 连接词的程序实现连接词的程序实现以上联结词组成的复合命题的真假值一定要根据它们的定义去理解，而不能据日常语言的含义去理解。不能“对号入座”，如见到“或”就表示为”有些词也可表示为这五个联结词，如“但是”也可表示为“”。u在今后我们主要关心的是命题间的真假值的关系，而不讨论命题的内容。以上以上5种最基本、最常用、最重要的联结词可以组成种最基本、最常用、最重要的联结词可以组成一个集合一个集合，成为一个联结词集，成为一个联结词集，其运算的优先级为：其运算的优先级为：，对于同一，对于同一级者，先出现者先运算。级者，先出现者先运算。例例1.13将下列命题符号化将下列命题符号化铁和氧化合，但铁和氮不化合。铁和氧化合，但铁和氮不化合。如果我下班早，就去商店看看，除如果我下班早，就去商店看看，除非我很累。非我很累。李四是信息技术学院的学生，他住李四是信息技术学院的学生，他住在在1312室或室或1313室。室。铁和氧化合，但铁和氮不化合。铁和氧化合，但铁和氮不化合。P P：“铁和氧化合铁和氧化合”Q Q：“铁和氮化合铁和氮化合”则用符号表示则用符号表示:P P(Q)Q)如果我下班早，就去商店看看，除非我很累。如果我下班早，就去商店看看，除非我很累。P P：“我很累我很累”Q Q：“我下班早我下班早”R R：“我去商店看看我去商店看看”则用符号表示则用符号表示为：为：(P)P)Q)Q)R)R)李四是信息技术学院的学生，他住在李四是信息技术学院的学生，他住在13121312室或室或13131313室。室。P P：“李四是信息技术学院的学生。李四是信息技术学院的学生。”Q Q：“李四住李四住13121312室。室。”R R：“李四住李四住13131313室。室。”则用符号表示则用符号表示:P P(Q Q(R R)(Q)Q)R R)小结命题及其符号命题及其符号P P、Q Q、R R。构成复合命题的联结词构成复合命题的联结词、，以，以及由联结词构成的复合命题及其真假值。及由联结词构成的复合命题及其真假值。注意：注意：有了命题和命题联结词，为了进一步的研有了命题和命题联结词，为了进一步的研究，今后，将只注重命题的真假值，而并不注意究，今后，将只注重命题的真假值，而并不注意其内容含义，对命题联结词，只承认它由真值表其内容含义，对命题联结词，只承认它由真值表定义，而不理会它的实际含义，这样，就可以在定义，而不理会它的实际含义，这样，就可以在命题与命题联结词的基础上建立起一个形式系统。命题与命题联结词的基础上建立起一个形式系统。练习：填空练习：填空1)1)已知已知P PQ Q为为T T，则，则P P为为()()，Q Q为为()()。2)2)已知已知P PQ Q为为F F，则，则P P为为()()，Q Q为为()()。3)3)已知已知P P为为F F，则，则P PQ Q为为()()。4)4)已知已知P P为为T T，则，则P PQ Q为为()()。5)5)已知已知P PQ Q为为T T，且，且P P为为F F，则，则Q Q为为()()。6)6)已知已知P PQ Q为为F F，则，则P P为为()()，Q Q为为()()。7)7)已知已知P P为为F F，则，则P PQ Q为为()()。8)8)已知已知Q Q为为T T，则，则P PQ Q为为()()。9)9)已知已知 P PQ Q为为F F，则则P P为为()()，Q Q为为()()。10)10)已知已知P P为为T T，P PQ Q为为T T，则，则Q Q为为()()。11)11)已知已知 Q Q为为T,PT,PQ Q为为T T，则，则P P为为()()。12)12)已知已知P PQ Q为为T T，P P为为T,T,则则Q Q为为().().13)13)已知已知P PQ Q为为F F，P P为为T,T,则则Q Q为为().().14)P14)PP P 的真值为的真值为().().15)P15)PP P 的真值的真值为为()()。16)16)说离散数学无用且枯燥无味是不对的。说离散数学无用且枯燥无味是不对的。P P：离散数学是有用的。：离散数学是有用的。Q Q：离散数学是有味的。：离散数学是有味的。该命题可写成：该命题可写成：(P P Q)Q)17)17)如果小张与小王都不去，则小李去。如果小张与小王都不去，则小李去。P P：小张去。：小张去。Q Q：小王去。：小王去。R R：小李去：小李去该命题可写成：该命题可写成：(P P Q)Q)R R该命题可写成：该命题可写成：(P(PQ)Q)R R1.2命题公式及其分类命题公式及其分类基本概念基本概念简简单单命命题题/命命题题常常项项/命命题题常常元元：真真值值唯唯一一确确定定的的陈陈述句。述句。命题变项命题变项/命题变元：真值可以变化的陈述句。命题变元：真值可以变化的陈述句。命命题题常常项项与与命命题题变变项项都都可可以以用用p,q,r等等表表示示，具体情况由上下文确定。具体情况由上下文确定。合合式式公公式式/命命题题公公式式：将将命命题题变变项项用用联联结结词词和和圆圆括括号按一定的逻辑关系联结起来的符号串。号按一定的逻辑关系联结起来的符号串。当当使使用用联联结结词词集集，时时，合合式式公公式定义如下：式定义如下：第一章 命题逻辑定义定义1.6（1）单个命题变项是合式公式，并称为原子）单个命题变项是合式公式，并称为原子命题公式。命题公式。（2）若）若A是合式公式，则是合式公式，则(A)也是合式公式。也是合式公式。（3）若）若A，B是合式公式，则是合式公式，则(AB)，(AB)(AB)，(AB)也是合式公式。也是合式公式。（4）只有有限次地应用）只有有限次地应用(1)(3)形成的符号串形成的符号串才是合式公式。才是合式公式。合合式式公公式式也也称称为为命命题题公公式式或或命命题题形形式式，并并简简称称为公式。为公式。第一章 命题逻辑可以看出所谓的合式公式可以解释为合法可以看出所谓的合式公式可以解释为合法的命题公式之意，也称之为命题公式，的命题公式之意，也称之为命题公式，有时也简称公式。有时也简称公式。下面的式子不是合式公式：下面的式子不是合式公式：P PR R，(PQ)R(PQ)Rpqt,(pw)q)下面的式子才是合式公式：下面的式子才是合式公式：(P(PQ)Q)，(P PR)R)，(PQ)R)(PQ)R)(pq),(rt)e,p，(p)约定约定：为方便，最外层括号可以不写，前面的合式：为方便，最外层括号可以不写，前面的合式 公式可以写成：公式可以写成：P PQQ，P PR R，(PQ)R(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层公式。层公式。第一章 命题逻辑例例:公式公式 p 0层层 p1层层 pq2层层(pq)r3层层 (p q)r)(r s)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的的真值表真值表p pq qr rp pq q(p p q)r q)r0 00 0 0 0 1 10 0 0 0 0 0 1 11 1 1 1 0 0 1 1 0 0 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 00 0 1 1 0 0 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 1 1 1 1 1 1 1 1 第一章 命题逻辑(2)求命题公式求命题公式(pq)(qp)的真值表的真值表pqpqpqqp(pq)(qp)0011111011011110010011100111第一章 命题逻辑(3)求命题公式求命题公式(pq)q的真值表。的真值表。pq(pq)(pq)(pq)q00100011001001011100第一章 命题逻辑 (4)求求(qp)qp的的真值表真值表 p q qp(qp)q(qp)qp00011011101100011111(5)求求(p q)q 的的真值表真值表 p q p p q(p q)(p q)q000110111100110100100000(6)求求(p q)r 的的真值表真值表 p q r p q r(p q)r000001010011100101110111001111111010101011101010定义定义1.9设设A为任一命题公式，为任一命题公式，（1）若若A在在其其各各种种赋赋值值下下的的取取值值均均为为真真，则则称称A是是重言式重言式或或永真式永真式。（2）若若A在在其其各各种种赋赋值值下下的的取取值值均均为为假假，则则称称A是是矛盾式矛盾式或或永假式永假式。（3）若）若A不是矛盾式，则称不是矛盾式，则称A为为可满足式可满足式。命题公式的类型重言式特性重言式特性重言式的否定是矛盾，矛盾的否定是重言式。重言式的否定是矛盾，矛盾的否定是重言式。两个重言式的合取、析取、蕴含、等价均为重两个重言式的合取、析取、蕴含、等价均为重言式。言式。若两个公式的等价是重言式，则此两公式对任若两个公式的等价是重言式，则此两公式对任何指派必同真假何指派必同真假真值表的作用：真值表的作用：（1）表示出公式的成真或成假赋值。表示出公式的成真或成假赋值。（2）判断公式类型：判断公式类型：(a)若真值表最后一列全为若真值表最后一列全为1，则为，则为重言式重言式；(b)若真值表最后一列全为若真值表最后一列全为0，则为，则为矛盾式矛盾式；(c)若真值表最后一列至少有一个若真值表最后一列至少有一个1，则为，则为可满足式可满足式；第一章 命题逻辑有很多公式具有相同的真值表。如：有很多公式具有相同的真值表。如：pqpq(pq)0011011110001111第一章 命题逻辑还有还有 pq、p q等等1.3等值演算等值演算定义定义1.10设设A,B是两个命题公式，若是两个命题公式，若A，B构成构成的等价式的等价式AB为重言式，则称为重言式，则称A与与B是等值的是等值的,记作记作AB.即即AB的充要的充要条件是条件是AB为重言式为重言式判断两个公式等值的方法判断两个公式等值的方法1：真值表法。：真值表法。第一章 命题逻辑pqrpqqrp(qr)(pq)r00001110010111010001101101111000111101011111010001111111由真值表可知，两个公式为等值式。由真值表可知，两个公式为等值式。例例1.15判断公式判断公式p(qr)与与(pq)r是否等值是否等值例1.16 证明证明 P PQ Q (PQ)PQ)(QP)(QP)P Q(PQ)(PQ)(QP)(PQ)(QP)001111010100100010111111两者的真值表相等，故两者的真值表相等，故PQ(PQ)(QP)不难验证：不难验证：P PPPP(P P)QQP PQ Q注意：注意：“”，“”的区别和联系：的区别和联系：区别：（1 1）“”是命题联结词，是命题联结词，A AB B是一个命题是一个命题公式，该公式取值可以是真，可以是假。公式，该公式取值可以是真，可以是假。（2 2）“”不是命题联结词，而是公式的等不是命题联结词，而是公式的等价关系符，价关系符，A AB B不代表命题，而表示的是命题不代表命题，而表示的是命题A A、B B有完全相同的真值。有完全相同的真值。联系：A AB B当且仅当当且仅当A AB B是永真式。是永真式。等价公式的性质等价公式的性质 自反性：即对任意公式自反