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

《离散数学课件第一章命题逻辑.ppt》由会员分享，可在线阅读，更多相关《离散数学课件第一章命题逻辑.ppt（175页珍藏版）》请在三一办公上搜索。

1、刘师少Tel：86613623（h）E-授课:51学时 学分 3 教学目标:知识、能力、素质,Discrete Mathematics,什么是数理逻辑,数理逻辑：以数学的方法研究思维规律和推理过程的科学。它首先引进一套符号体系，规定一些规则，导出一些定律，然后借助于这些符号、规则、定律，将逻辑推理的过程在形式上变得像代数演算一样，因此数理逻辑又称符号逻辑。,微积分力学、机械工程 人类体力劳动自动化,数理逻辑人工智能、知识工程 脑力劳动自动化,数理逻辑,命题逻辑（数理逻辑的基础，以命题为研究对象，研究基于命题的符号逻辑体系及推理规律，也称命题演算）。主要内容：、命题与联结词、命题公式、真值表、重

2、言式、命题联结词的扩充、范式、命题演算的推理规则和证明方法 谓词逻辑（对命题逻辑的深入研究）。,第一章 命题逻辑,这章是以“命题”为中心主要讨论：命题的表示、命题的演算命题演算中的公式，及其应用命题逻辑推理,1.1.1 命题的概念 命题：能够判断真假的陈述句。命题的真值：命题的判断结果。真值只取两个值：真（1）、假（0）。真命题：真值为真的命题。假命题：真值为假的命题。判断命题的两个步骤：)1、是否为陈述句；2、是否有确定的、唯一的真值。,1.1 命题符号化及联结词,命题的特征：陈述句 真假必居其一，且只居其一。,例1.1 下列句子中那些是命题？(1)是无理数.(2)2+5 8.(3)x+5

3、3.(4)你有铅笔吗？(5)这只兔子跑得真快呀！(6)请不要讲话！(7)我正在说谎话.,真命题,假命题,真值不确定,疑问句,感叹句,祈使句,悖论,(3)(7)都不是命题,第一章 命题逻辑,祈使句，感叹句，疑问句均不是命题。再如 把门关上！你到哪里去？语句既为真，同时又包含假的不是命题，这样的句子称为“悖论”。如 他正在说谎。（在命题逻辑中不讨论这类问题）,例1.2 判定下面这些句子哪些是命题。(8)2是个素数。(9)雪是黑色的。(10)2015年人类将到达火星。(11)如果 a b且 b c，则 a c。(12)x+y 5(13)请打开书！(14)您去吗？(8)(9)(10)(11)是命题,第

4、一章 命题逻辑,一个命题的真或假称为命题的真值，由于命题只有真假两个值，所以命题逻辑也称二值逻辑。以T(True)（或1）表示命题的真值为真，F(False)（或0）表示命题的真值为假,1.1.2 命题的真值,练习 判断下列句子是否为命题。1.100是自然数。2.太阳从西方升起。3.北京是中国的首都4.杭州是中国最大的城市5.关门!6.你去哪里?7.这道题太难8.凡石头均可炼成金。9.x+3910.皇马中国之行没有提升国家队的水平。,第一章 命题逻辑,模糊逻辑,1.1.3 命题及其真值的抽象化 在本书中，用小写英文字母p,q,r,p1,p2,p3等表示命题,用“1”、“0”分别表示真值的真、假

5、。例1.2：p：罗纳尔多是球星。q：5是负数。p3：明天天气晴。皆为符号化的命题，其真值依次为1、0、1或0。若令 p：是有理数，则 p 的真值为 0 q：2+5=7，则 q 的真值为 1,分类 根据其真值分类：真命题。假命题。根据其复杂程度分类：简单命题或原子命题。复合命题。,1.1.4 命题的分类,简单/原子命题：由不能再分解为更简单的陈述句的陈述句构成。如上例中的命题。复合命题：由简单命题与联结词按一定规则复合而成的命题 例1.3(1)若三角形等腰，则两底角相等(2)若行列式两行成比例，则行列式值为0,1.1.4 命题的分类,例1.3 由简单命题能构造更加复杂的命题 期中考试，张三没有考

6、及格。期中考试，张三和李四都及格了。期中考试，张三和李四中有人考90分。如果张三能考90分，那么李四也能考90分。张三能考90分当且仅当李四也能考90分。,联结词和复合命题,上述诸如“没有”、“如果那么”等词称为联结词。由联结词和命题连接而成的更加复杂命题称为复合命题；相对地，不能分解为更简单命题的命题成为简单命题。（命题的分类）复合命题的真假完全由构成它的简单命题的真假所决定。注：简单命题和复合命题的划分是相对的。,在命题逻辑的符号化过程中，通常的要求是每一个引进的表示命题的符号都表示一个原子命题。例如：将下列命题符号化(1)杭州不是中国的首都。(2)张三虽然学习努力但成绩并不优秀。解(1)

7、令P：杭州是中国的首都。则命题“杭州不是中国的首都”符号化为：P(2)令P：张三学习努力。Q：张三成绩优秀。则命题“张三虽然学习努力但成绩并不优秀。”符号化为：PQ。,由此我们进一步明确指出：原子命题是用肯定语气表达的具有真假意义的简单陈述句。上述例题中。直接令P表示“杭州不是中国的首都”。来做符号化，是不符合要求的。在上述第2个命题中，如果简单地用一个符号P表示“张三虽然学习努力但成绩并不优秀”做符号化就更不符合符号化的要求了。,复合命题的构成：是用“联结词”将原子命题联结起来构成的。归纳自然语言中的联结词，定义了六个逻辑联结词，分别是：(1)否定“”(2)合取“”(3)析取“”(4)异或“

8、”(5)蕴涵“”(6)等价“”,1.1.5 联结词,否定联结词“”,表示：“不成立”，“不”。用于：对一个命题P的否定，写成P，并读成“非P”。P的真值：与P真值相反。例1.4 P：2是素数。P：2不是素数。,P P,1 0,0 1,定义1.1 设p为命题，复合命题“非p”（或“p 的否定”）称为p的否定式，记作 p，符号 称为否定联结词,#include void main()int z,p;printf(验证逻辑连接词否定);printf(t);printf(z=!p);while(p!=0,否定连接词的程序实现,定义1.2 设p,q为二命题，复合命题“p并且q”（或“p与q”）称为p与q

9、的合取式，记 作p q，符号称为合取联结词。运算规则：属于双目运算符,合取联结词,表示：“并且”、“不但而且.”、“既又.”“尽管还”例如 P：小王能唱歌。Q：小王能跳舞。PQ：小王能歌善舞。PQ 读成P合取Q。PQ的真值为真，当且仅当P和Q的真值均为真。,合取运算特点：只有参与运算的二命题全为真时，运算结果才为真，否则为假。自然语言中的表示“并且”意思的联结词，如“既又”、“不但而且”、“虽然但是”、“一面一面”等都可以符号化为注意：不要见到“与”或“和”就使用联结词！例1.4 下列命题符号化(1)北京不仅是中国的首都而且是一个故都 p：北京是中国的首都。q：北京是一个故都。pq：北京是中国

10、的首都并且是一个故都。牛启飞和林妹妹是好朋友 P:牛启飞和林妹妹是好朋友,例1.5 将下列命题符号化.(3)王晓既用功又聪明.(4)王晓不仅聪明，而且用功.(5)王晓虽然聪明，但不用功.(6 张辉与王丽都是三好生.(7)张辉与王丽是同学.解 令 p：王晓用功，q：王晓聪明，则(3)pq(4)pq(5)pq.令 r:张辉是三好学生，s:王丽是三好学生(6)rs.(7)令 t:张辉与王丽是同学，t 是简单命题.,#include void main()int z,p,q;printf(验证逻辑连接词合取);printf(t);printf(z=pq);while(p!=0,合取连接词的程序实现,定

11、义1.3 设p,q为二命题，复合命题“p或q”称为 p与q的析取式，记作p q，符号称 为析取联结词。运算规则：属于双目运算符,析取联结词“”,例1.6 期中考试张三和李四中有人考90分 P:期中考试张三考了90分 Q:期中考试李四考了90分,例1.7.第一节课上数学或者上英语,P：第一节上数学。Q：第一节上英语。该复合命题 可写成 P Q，读 成P异或Q。PQ的真值为 F，当且仅当P与Q的真值 相同,0 0 0,0 1 1,1 0 1,1 1 0,上例中的或者是不可兼取的或，也称之为异或、排斥或。即“”.,P Q,例1.8 将下列命题符号化(1)2或4是素数.(2)2或3是素数.(3)4或6

12、是素数.(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)(

13、vw),能符号化为 vw,为什么?,析取运算特点：只有参与运算的二命题全为假时，运算结果才为假，否则为真。这里的析取运算只能表示自然语言中的“相容或”的意思，特别要注意自然语言里的“排斥或”。再举例说明：（1）小王爱打球或爱跑步。设p：小王爱打球。q：小王爱跑步。则上述命题可符号化为：p q（2）火车8：00或9：00到站。设p：火车8：00到站。q：火车9：00到站。则上述命题就不可简单符号化为：p q 而应描述为(p q)(pq)或 p q,（3）今天晚上我在家看电视或去剧场看戏。这个命题中的“或”是排斥或，表示二者只居其一，不能同时成立。令 p:今天晚上我在家看电视 q:今天晚上我去剧场

14、看戏 上述命题不能表示为pq，因为按“”的定义。P,q都为真时，pq也为真，而上题当p，q都为真时，命题为假，这是由于一个人不可能既在家，又在剧场里,所以不能用pq表示,要用排斥或()表示上述命题可表示为：(p q)(pq)或 p q,#include void main()int z,p,q;printf(验证逻辑连接词析取);printf(t);printf(z=p q);while(p!=0,析取连接词的程序实现,定义1.4 设p,q为二命题,复合命题“如果p,则 q”称为p与q的蕴涵式，记作p q，并称p为蕴涵式的前件，q为蕴涵式的 后件，符号称为蕴涵联结词。与自然语言的不同：前件与后

15、件可以没有任何内在联系！运算规则：属于双目运算符,蕴涵(条件)“”,例1.9 如果张三能考90分，那么李四也考90分 P：“张三考90分”Q：“李四考90分”,例1.10 将下列命题符号化(1)如果你今年离散数学考100分，那么就 奖励你100元。P：你今年离散数学考100分。Q：奖励你100元。,(2)如果22=5，则雪是黑的 令 p：22=5，q：雪是黑的，于是命题符号化为 p q 这是和人们日常生活中语言不一致的地方(3)如果我得到这部小说，那么我今夜就读完它 令 p1：我得到这部小说 q1：我今夜就读完它 于是命题符号化为 p1 q1,#include void main()int z

16、,p,q;printf(验证逻辑连接词蕴涵);printf(t);printf(z=pq);while(p!=0,蕴涵连接词的程序实现,定义1.5 设p,q为二命题，复合命题“p当且仅当 q”称为p与q的等价式，记作p q，符号称为等价联结词。说明:(1)pq 的逻辑关系:p与q互为充分必要条件(2)pq为真当且仅当p与q同真或同假 运算规则：属于双目运算符,等价(双条件）联结词“”,例1.11 将下列命题符号化(1)张三能考90分当且仅当李四也能考90分 P：张三考90分 Q：李四考90分 命题符号化为 PQ,(2)2是素数当且仅当三角形有3条边；(3)雪是黑的当且仅当太阳从东方升起.解:(

17、2)令 p：2是素数，q：三角形有3条边，则原命题符号化为pq.(3)令 p1：雪是黑，q1：太阳从东方升起，则原命题符号化为p1 q1，这是假命题 以上例子充分说明:等价运算p q 表示的逻辑关系是：p与q互为充分必要条件。相当于(p q)(q p).,例1.12 求下列复合命题的真值(1)2+2 4 当且仅当 3+3 6.(2)2+2 4 当且仅当 3 是偶数.(3)2+2 4 当且仅当 太阳从东方升起.(4)2+2 4 当且仅当 美国位于非洲.(5)函数 f(x)在x0 可导的充要条件是它在 x0 连续.它们的真值分别为 1，0，1，0，0.,例1.13 将下列命题符号化(1)如果你走路

18、时看书，那么你一定会成为近视眼。解 令p：你走路；q：你看书；r：你是近视眼。于是，上述语句可表示为（pq）r。(2)设p，q，r的意义如下：p：苹果是甜的；q：苹果是红的；r：我买苹果。试用日常语言复述下述复合命题：(a)(pq)r(b)(pq)r 解：(a)如果苹果甜且红，那么我买。(b)我没买苹果，因为苹果不甜也不红。,#include void main()int z,p,q;printf(验证逻辑连接词双条件);printf(t);printf(z=pq);while(p!=0,双条件 连接词的程序实现,以上联结词组成的复合命题的真假值一定要根据它们的定义去理解，而不能据日常语言的含

19、义去理解。不能“对号入座”，如见到“或”就表示为”有些词也可表示为这五个联结词，如“但是”也可表示为“”。在今后我们主要关心的是命题间的真假值的关系，而不讨论命题的内容。,以上5种最基本、最常用、最重要的联结词可以组成一个集合，成为一个联结词集，其运算的优先级为：，对于同一级者，先出现者先运算。,例1.13 将下列命题符号化铁和氧化合，但铁和氮不化合。如果我下班早，就去商店看看，除非我很累。李四是信息技术学院的学生，他住在1312室或1313室。,铁和氧化合，但铁和氮不化合。P：“铁和氧化合”Q：“铁和氮化合”则用符号表示:P(Q)如果我下班早，就去商店看看，除非我很累。P：“我很累”Q：“我

20、下班早”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)

21、已知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

22、),17)如果小张与小王都不去，则小李去。P：小张去。Q：小王去。R：小李去,该命题可写成：(PQ)R该命题可写成：(P Q)R,1.2 命题公式及其分类基本概念简单命题/命题常项/命题常元：真值唯一确定的陈述句。命题变项/命题变元：真值可以变化的陈述句。命题常项与命题变项都可以用p,q,r等表示，具体情况由上下文确定。合式公式/命题公式：将命题变项用联结词和圆括号按一定的逻辑关系联结起来的符号串。当使用联结词集，时，合式公式定义如下：,第一章 命题逻辑,定义1.6（1）单个命题变项是合式公式，并称为原子 命题公式。（2）若A是合式公式，则(A)也是合式公式。（3）若A，B是合式公式，则(AB

23、)，(AB)(A B)，(A B)也是合式公式。（4）只有有限次地应用(1)(3)形成的符号串 才是合式公式。合式公式也称为命题公式或命题形式，并简称为公式。,第一章 命题逻辑,可以看出所谓的合式公式可以解释为合法的命题公式之意，也称之为命题公式，有时也简称公式。下面的式子不是合式公式：PR，(PQ)R pq t,(p w)q)下面的式子才是合式公式：(PQ)，(PR)，(PQ)R)(p q),(r t)e,p，(p),约定：为方便，最外层括号可以不写，前面的合式 公式可以写成：PQ，PR，(PQ)R上述归纳定义方式中的符号A,B不同于具体公式里面的p,q,r等符号，可以用来表示任意的合式公式

24、,定义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=B C,其中B,C的层次及n同(b);(e)A=B C,其中B,C的层次及n同(b);（3）若公式A的层次为k，则称A是k层公式。,第一章 命题逻辑,例:公式 p 0层 p 1层 pq 2层(pq)r 3层(pq)r)(rs)4层,第一章 命题逻辑,定义1.8公式赋值 设p1，p2，pn是出现在公式A中的全部的命题变

25、项，给p1，p2，pn各指定一个真值，称为对A的一个赋值或解释。比如：对公式(p q)r一组赋值为011(意即令p=0,q=1,r=1)可得真值为1，另一组赋值为010可得真值为0；还有000，001，111 考虑：含有n个命题变项的公式共有多少个不同的赋值？,第一章 命题逻辑,2n个赋值.,若指定的一组值使A的真值为1，则称这组值为A的成真赋值。(使公式为真的赋值)如对公式(p q)r赋值011，还有?若指定的一组值使A的真值为0，则称这组值为A的成假赋值。(使公式为假的赋值)如对公式(p q)r赋值010，还有?,第一章 命题逻辑,真值表 将命题公式A在所有赋值下取值情况列成表称做A的真值

26、表。对公式A构造真值表的具体步骤为：（1）找出公式中所有的全体命题变项 p1，p2，pn，列出2n个赋值。（2）按从低到高的顺序写出公式的各个层次（3）对应各个赋值计算出各层次的真值，直 到最后计算出公式的真值。,第一章 命题逻辑,例1.14(1)求命题公式(p q)r的 真值表,第一章 命题逻辑,(2)求命题公式(pq)(q p)的真值表,第一章 命题逻辑,(3)求命题公式(p q)q 的真值表。,第一章 命题逻辑,(4)求(qp)qp 的真值表,(5)求(pq)q 的真值表,(6)求(pq)r 的真值表,定义1.9 设A为任一命题公式，（1）若A在其各种赋值下的取值均为真，则称A是重言式或

27、永真式。（2）若A在其各种赋值下的取值均为假，则称A是矛盾式或永假式。（3）若A不是矛盾式，则称A为可满足式。,命题公式的类型,重言式特性重言式的否定是矛盾，矛盾的否定是重言式。两个重言式的合取、析取、蕴含、等价均为重言式。若两个公式的等价是重言式，则此两公式对任何指派必同真假,真值表的作用：（1）表示出公式的成真或成假赋值。（2）判断公式类型：(a)若真值表最后一列全为1，则为重言式；(b)若真值表最后一列全为0，则为矛盾式；(c)若真值表最后一列至少有一个1，则为 可满足式；,第一章 命题逻辑,有很多公式具有相同的真值表。如：,第一章 命题逻辑,还有 p q、p q等,1.3 等值演算定义

28、1.10 设A,B是两个命题公式，若A，B构成 的等价式A B为重言式，则称A与B 是等值的,记作AB.即AB的充要 条件是A B为重言式判断两个公式等值的方法1：真值表法。,第一章 命题逻辑,由真值表可知，两个公式为等值式。,例1.15 判断公式 p(qr)与(p q)r 是否等值,例1.16 证明 PQ(PQ)(QP),两者的真值表相等，故PQ(PQ)(QP)不难验证：P P PP P(PP)Q Q P P QQ,注意：“”，“”的区别和联系：,区别：（1）“”是命题联结词，AB是一个命题公式，该公式取值可以是真，可以是假。（2）“”不是命题联结词，而是公式的等价关系符，AB不代表命题，而

29、表示的是命题A、B有完全相同的真值。联系：AB当且仅当AB是永真式。,等价公式的性质,自反性：即对任意公式A，有AA；对称性：即对任意公式A和B，若AB，则BA；传递性：即对任意公式A和B，C，若AB，BC,则AC。,等值 演算：由已知的等值式推演出另外一些 等值式的过程。等值演算中使用的一条重要规则：置换规则定理1.1 设(A)是含公式A的命题公式,(B)是用公式B置换了(A)中所有的A后 得到的命题公式，若B A，则(A)(B)。,第一章 命题逻辑,等值演算与置换规则,等值演算:由已知的等值式推演出新的等值式的过程置换规则：若AB,则(B)(A)等值演算的基础：(1)等值关系的性质：自反、

30、对称、传递(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代表任意的命题公式牢记这些等值式是继续学习的基础,等值演

31、算的用途一：证明等值式。例1.14 验证 p(qr)(p q)r 右(p q)r 蕴涵等值式 p q r 德摩根律 p(q r)结合律 p(q r)蕴涵等值式 p(q r)蕴涵等值式 注:A B AB,第一章 命题逻辑,例1.15 证明:p(qr)(pq)r 用等值演算不能直接证明两个公式不等值,证明两个公式不等值的基本思想是找到一个赋值使一个成真,另一个成假.方法一 真值表法（自己证）方法二 观察赋值法.容易看出000,010等是左 边的成真赋值，是右边的成假赋值.方法三 用等值演算先化简两个公式，再观 察(用公式A B AB 和(AB)AB),例1.16 用等值演算法判断下列公式的类型(1

32、)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为矛盾式当且仅当A0 A为重言式当且仅当A1说明：演算步骤不惟一,应尽量使演算短些,例1.17：判

33、断公式(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)(

34、r2s3)0(r1q2)(r2s3)0,(r1q2)(r1q2)1(r2s3)(r2s3)1(p2s4)(p2s4)11(r1q2)(r2s3)(r1q2)(r2s3)11 1p2q2r1r2s3 s4由上式可知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=(p

35、q)。p q pq 0 0 1 0 1 1 1 0 1 1 1 0,定义1.13 设p，q是两个命题，复合命题“p或q的否定”称为p与q的或非式，记作pq，称作或非联结词。pq为真当且仅当p，q同时为假。由定义可知：pq=(pq),第一章 命题逻辑,p q pq 0 0 1 0 1 0 1 0 0 1 1 0,第一章 命题逻辑,定义1.14 一个n(n1)维卡氏积0,1n到0,1的函数称 为一个n元真值函数。设F是一个n元真值 函数，则可记为F：0,1n 0,1 n个命题变项，共有2n个可能的赋值，对于每个赋值真值函数的函数值非 0 即 1，于是n个命题变元共可以形成22 个不同的真值函数。见

36、教材P13 表1.6,n,命题公式与真值函数,对于任何一个含n个命题变项的命题公式A，都存在惟一的一个n元真值函数F为A的真值表.等值的公式对应的真值函数相同.下表给出所有2元真值函数对应的真值表,每一个含2个命题变项的公式的真值表都可以在下表中找到.例如：pq,pq,(pq)(pq)q)等都对应表中的F14(2),2元真值函数对应的真值表,其实，每个真值函数可对应无穷多个命题公式，它们彼此都是等值的，有很多公式具有相同的真值表。如：,第一章 命题逻辑,还有 p q、p q等,第一章 命题逻辑,定义1.15 在一个联结词的集合中，如果一个联结词可由集合中的其他联结词定义，则称此联结词为冗余的联

37、结词，否则称为独立的联结词。前面给出的5个联结词组成的联结词集为，由于 p q p q p q(p q)(q p)(p q)(q p)所以，都是冗余的，又，中，由于 p q(pq)(p q)所以可看成是冗余的，但在,中无冗余的联结词,第一章 命题逻辑,定义1.16 若任一真值函数都可以用仅含某一联结词的命题公式表示，则称该联结词集为全功能集。若一个联结词集的全功能集中不含冗余的的联结词，则称它为极小全功能集例1.17 若已知，是全功能集，证明，也是 全功能集证明 由于，是全功能集，因而任一真值函数均可由仅含，中的联结词的命题公式表示，而对于任意的命题形式A，B，有 A B AB因而任一真值函数

38、均可由含，中的联结词的命题公式表示，所以它是全功能集。,在仅含联结词,的命题公式A中，将换成，换成,若A中含0或1，就将0换成1，1换成0，所得命题公式称为A的对偶式，记作A*。从定义不难看出，(A*)*=A如:公式 P(Q F)的对偶公式为P(Q F)定理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为两命题公式，若A B，则A*B*其中A*，B*分别为A，B的对偶式。该定理称为对偶原理 由对

39、偶原理可知，若A为重言式，则A*必为矛盾式，反之亦然 给定一个命题公式，判断它是重言式、矛盾式、还是可满足式，这类问题称为判定问题。,第一章 命题逻辑,1.5.1 范式 命题公式是千变万化的，这给研究命题演算带来困难，这里我们研究如何由一个命题公式化归为一个标准形式的问题，这样命题演算的研究问题就归结为对标准形式的研究问题，这种标准形式就叫范式。简单说范式就是命题公式形式的规范形式。这里约定在范式中 只含有联结词、和,析取范式与合取范式1)合取式与析取式 合取式：是用“”联结命题变元或变元的否定构成的式子。如 P、P、PQ、PQR 析取式：是用“”联结命题变元或变元的否定构成的式子。如 P、P

40、、PQ、PQR注:PPP PPP P是合(析)取式.,析取范式 它是这样一种标准形式，在此式内不出现联结词及，否定符号只出现在命题变元前。它是一个析取式，式中的每个析取项是个合取式，每个合取式中只包含命题变元或命题变元的否定。例如 p(pq)(qr)此式即具有析取范式之形式注意:一个公式的析取范式并不唯一，如p(rq),可以写成(pp)(rq),合取范式 它是这样一种标准形式，在此式内不出现联结词及，否定符号只出现在命题变元前。它是一个合取式，式中的每个合取项是个析取式，每个析取式中只包含命题变元或命题变元的否定。例如 p(pq)(q r)此式即具有合取范式之形式注意:一个公式的合取范式并不唯

41、一，如 p(r q)可以写成(p p)(r q),定义1.9析取范式：由有限个简单合取式构成的析取式。如：p q,(p q)(p q r)合取范式：由有限个简单析取式构成的合取式。如：p q,（p q）（p qr）范式：析取范式与合取范式统称为范式。,第一章 命题逻辑,设Ai(i=1,2,3,n)为简单合取式，则A=A1 A2 An 就是析取范式，而B=A1 A2 An 就是合取范式。析取范式和合取范式有下列性质：（1）一个析取范式是矛盾式它的每个简单合取式 都是矛盾式。（2）一个合取范式是重言式它的每个简单析取式 都是重言式。,第一章 命题逻辑,定理1.4(范式存在定理)任一个命题公式都存在

42、着与之等值的析取范式与合取范式。求范式的具体步骤：（1）消去对,来说冗余的联结词，即，。利用下列等值式：A B(A B)A B(A B)(A B),第一章 命题逻辑,（2）否定词的消去或内移。利用下列等值式：A B(A B)(A B)A B(A B)A B（3）利用分配律：C(AB)（CA）（C B）C(AB)（CA）（C B）,第一章 命题逻辑,例1.18 求下列公式的析取范式与合取范式(1)A=(pq)r解(pq)r(pq)r（消去）pqr（结合律）这既是A的析取范式（由3个简单合取式组成的析取式），又是A的合取范式（由一个简单析取式组成的合取式）,(2)B=(pq)r解(pq)r(pq)

43、r（消去第一个）(pq)r（消去第二个）(pq)r（否定号内移德摩根律）这一步已为析取范式（两个简单合取式构成）继续：(pq)r(pr)(qr)（对分配律）这一步得到合取范式（由两个简单析取式构成）,定义1.20 在含有n个命题变项的简单合取式(简单析取式)中，若每个命题变项均以文字的形式在其中出现且仅出现一次，而且第i（1in）个文字出现在左起第i位上，称这样的简单合取式（简单析取式）为 极小项（极大项）.,第一章 命题逻辑,说明：n个命题变项产生2n个极小项和2n个极大项 2n个极小项（极大项）均互不等值 用mi表示第i个极小项，其中i是该极小项成真赋值的十进制表示.用Mi表示第i个极大项

44、，其中i是该极大项成假赋值的十进制表示,mi(Mi)称为极小项(极大项)的名称.mi与Mi的关系:mi Mi,Mi mi,第一章 命题逻辑,由p,q两个命题变项形成的极小项与极大项,由p,q,r三个命题变项形成的极小项与极大项,主析取范式:由极小项构成的析取范式主合取范式:由极大项构成的合取范式例如，n=3,命题变项为p,q,r时，(pqr)(pqr)m1 m3 是主析取范式(pqr)(pqr)M1 M5 是主合取范式 A 的主析取范式:与A 等值的主析取范式 A 的主合取范式:与A 等值的主合取范式.,定理 1.5 任何命题公式都存在着与之等值的主析取范式和主合取范式,并且是惟一的.用等值演

45、算法求公式的主范式的步骤：(1)先求析取范式（合取范式）(2)将不是极小项（极大项）的简单合取式（简单析取式）化成与之等值的若干个极小 项的析取（极大项的合取），需要利用同一 律（零律）、排中律（矛盾律）、分配律、幂等律等.(3)极小项（极大项）用名称mi（Mi）表示，并按角标从小到大顺序排序.,主析取范式:析取范式 A1A2.An,其中每个Ai(i=1,2.n)都是小项。主析取范式的写法 方法：列真值表 列出给定公式的真值表。找出真值表中每个“1”对应的小项。用“”联结上述小项，即可。,例1.17 求 PQ和PQ的主析取范式 P Q PQ PQ 0 0 1 1 0 1 1 0 1 0 0 0

46、 1 1 1 1 PQ m0m1m3(PQ)(PQ)(PQ)PQm0m3(PQ)(PQ),主析取范式:由极小项构成的析取范式主合取范式:由极大项构成的合取范式,主合取范式 合取范式 A1A2.An,其中每个Ai(i=1,2.n)都是大项主合取范式的写法 方法：列真值表 列出给定公式的真值表。找出真值表中每个“0”对应的大项。用“”联结上述大项，即可。,例1.18 求 PQ和PQ的主合取范式 P Q PQ PQ 0 0 1 1 0 1 1 0 1 0 0 0 1 1 1 1 PQ M2 PQ PQ M1M2(PQ)(PQ),例1.18 求(p q)(p r)的主析取范式。解法1：P q r p

47、p q p r(p q)(p r)0 0 0 1 0 1 0 0 0 1 1 0 1 0 0 1 0 1 1 1 1 0 1 1 1 1 1 1 1 0 0 0 1 0 0 1 0 1 0 1 1 1 1 1 0 0 1 0 0 1 1 1 0 1 1 1,第一章 命题逻辑,所以：(pq)(pr)m2m3m5m7(2,3,5,7),例1.19 求(p q)(p r)的主合取范式。解法1：P q r p p q p r(p q)(p r)0 0 0 1 0 1 0 0 0 1 1 0 1 0 0 1 0 1 1 1 1 0 1 1 1 1 1 1 1 0 0 0 1 0 0 1 0 1 0 1

48、1 1 1 1 0 0 1 0 0 1 1 1 0 1 1 1,第一章 命题逻辑,所以:(pq)(pr)M0M1M4 M6(0,1,4,6),解法2：(p q)(p r)(pq)(p r)(合取范式)(p q)(r r)(p r)(q q)(p q r)(p q r)(pq r)(pq r)(p q r)(p q r)(pq r)(pq r)(主合取范式)M0M1M4 M6(0,1,4,6),第一章 命题逻辑,例1.20 判断命题公式(p q)(p r)的类型解法1：P q r p q p r(p q)(pr)0 0 0 1 0 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 1

49、1 0 1 1 0 0 0 0 0 1 0 1 0 1 1 1 1 0 1 0 1 1 1 1 1 1 1,第一章 命题逻辑,该公式m0m1m2m3m5m6m7 为可满足式,提示:用真值表判断命题公式的类型是最常用的 方法,第一章 命题逻辑,主析取范式的用途（主合取范式类似讨论）：1、求公式的成真/成假赋值：若公式A中含有n个命题变项，且A的主析取范式含s 个极小项，则A有s个成真赋值，有2n-s个成假赋值。,第一章 命题逻辑,2、判断公式的类型：设公式A中含有n个命题变项，则：（1）A为重言式 A的主析取范式含全部2n 个极小项。（2）A为矛盾式 A的主析取范式不含任 何极小项，记A的主析取

50、范式为0。（3）A为可满足式 A的主析取范式至少 含一个极小项。,第一章 命题逻辑,3、判断两个命题是否等值：设公式A、B中共含有n个命题变项，按n个命题变项求出A、B的主析取范式A、B。若A=B，则A B，否则A、B不等值。例1.21 判断下列命题公式是否等值(1)(p q)(p r)与 p(q r)(2)p(q r)与 p(q r),第一章 命题逻辑,第一章 命题逻辑,p q r qr p q p r(pq)(p r)p(qr)0 0 0 0 1 1 1 1 0 0 1 0 1 1 1 1 0 1 0 0 1 1 1 1 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1