数理逻辑.ppt

《数理逻辑.ppt》由会员分享，可在线阅读，更多相关《数理逻辑.ppt（79页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、离散数学,马汝辉上海交通大学 计算机科学与工程系电信群楼3-229 Tel: 34207874,2,2,什么是离散数学?,离散数学(discrete mathematics)是研究离散对象的数学分支.离散:由分离的元素组成.如自然数集.相对应的是连续对象. 如实数集.微积分就是研究连续函数的数学分支.内容包括:集合,关系,函数数理逻辑图论抽象代数组合数学数论, ,3,离散数学,研究对象：离散个体及其结构离散数学是：现代数学的一个重要分支计算机科学与技术的理论基础是计算机应用必不可少的工具，所以又称为计算机数学离散数学应用举例,在数字电路中的应用,交通信号灯控制有红、黄、绿三灯，由3个开关分别控

2、制每次仅一种颜色灯亮红灯及绿灯不会连续出现，即二者之间必须有黄灯可加上延时：如红灯20秒，黄灯10秒，绿灯13秒更复杂的情形：十字路口多信号灯、信号灯闪断等,本质上是数理逻辑,理发师悖论,在某个城市中有一位理发师，他的广告词是这样写的： “本人的理发技艺十分高超，誉满全城。我将为本城所有不给自己刮脸的人刮脸，我也只给这些人刮脸。我对各位表示热诚欢迎！” 来找他刮脸的人络绎不绝，自然都是那些不给自己刮脸的人。可是，有一天，这位理发师从镜子里看见自己的胡子长了，他本能地抓起了剃刀，你们看他能不能给他自己刮脸呢？如果他不给自己刮脸，他就属于“不给自己刮脸的人”，他就要给自己刮脸，而如果他给自己刮脸呢

3、？他又属于“给自己刮脸的人”，他就不该给自己刮脸。,本质上是集合论,一笔画及社交网络,一笔画：给定一个由顶点和边所组成的图。能否无重复的遍历该图的边？社交网络：在社交网络环境中，依据后台数据库，自动得到一个成员之间彼此直接/间接认识的最大群体,本质上是图论,7,离散数学,事实上，从计算机产生到其发展每一步都离不开数学1936年，英国数学家图灵(A.M.Turing)发表了著名论文 “理想计算机”，从而给出了计算机的理论模型1946年在著名数学家冯诺依曼(J.Von Neumann)的领导下，制造了世界上第一台现代意义的通用计算机EDVAC (Electronic Discrete Variab

4、le Automatic Computer) 为什么离散数学对计算机科学来说如此重要？数字电子计算机是一个离散结构，它只能处理离散的或离散化了的数量关系无论计算机科学本身，还是与计算机科学及其应用密切相关的现代科学研究领域，都面临着如何对离散结构建立相应的数学模型；又如何将已用连续数量关系建立起来的数学模型离散化，从而可由计算机加以处理,8,离散数学与计算机科学的关系,数理逻辑：人工智能、程序正确性证明、程序验证等集合论：关系数据库模型等图论：数据结构、数据库模型、网络模型等代数结构：软件规范、形式语义、编译系统、 编码理论、密码学、数据仓库等组合数学：算法分析与设计、编码理论、容错等,9,离

5、散数学课程说明,研究对象-离散个体及其结构研究思想-以集合和映射为工具、体现公理化和结构的思想研究内容-包含不同的数学分支，模块化结构数理逻辑：推理、形式化方法集合论：离散结构的表示、描述工具图论：离散结构的关系模型代数结构：离散结构的代数模型组合数学：离散结构的存在性、计数、枚举、优化、设计离散概率（概率统计课程）,10,课程内容,数理逻辑图论教材及下载地址数理逻辑与集合论（第二版）：石纯一，清华大学出版社图论与代数结构：戴一奇，清华大学出版社链接: http:/202.120.38.22:8080/wiki/index.php/Course2016助教 TA李阳德，硕士，软件大楼5406,

6、11,参考书籍,离散数学：董晓蕾，曹珍富，机械工业出版社数理逻辑：莫绍揆，科学文献出版社数理逻辑教程：莫绍揆，华中工学院出版社集论与逻辑：沈恩绍，科学出版社A Mathematical Introduction to Logic, 2nd. Ed, H.Enderton, Academic Press Logic for Applications, 2nd ed., A. Nerode, Springer离散数学（第4版），Richard Johnsonbaugh，电子工业出版社,12,学习目标,理解、掌握命题逻辑的基本概念及命题逻辑的等值和推理演算理解、掌握谓词逻辑的基本概念及谓词逻辑的等值

7、和推理演算理解、掌握图的基本概念及代数表示理解、掌握道路与回路、欧拉道路与回路及哈密顿道路与回路理解、掌握树的基本概念、Huffman树及最短树应用逻辑推理、形式化方法、离散结构的关系模型（如树等）来解决实际问题,成绩评定,平时成绩（30%）期末考试成绩（70%）,13,第一部分 数理逻辑,逻辑学研究人的思维形式和规律的科学数理逻辑用数学方法研究推理，是研究推理中前提和结论之间的形式关系的科学所谓推理就是由一个或几个判断推出一个新判断的思维形式这里所说的数学方法就是建立一套表意符号体系，对具体事物进行抽象的形式研究的方法. 因此, 数理逻辑又称符号逻辑,什么是逻辑,直观的说，逻辑是研究说话的道

8、理的学科，从而增强人的“说话”（推理过程）与思考的能力“说话”：日常对话、数学证明、科学定律、各种预测例子：判断下面两个说法是否有道理,所有的人都会死； 所有的人都会死；苏格拉底是人。 苏格拉底会死。所以，苏格拉底会死。 所以，苏格拉底是人。,会死的,人,苏,会死的,人,苏,数理逻辑前史时期古典形式逻辑时期,代表人物：亚里士多德,数理逻辑初创时期逻辑代数时期,代表人物：莱布尼茨,数理逻辑的奠定时期,代表人物：康托尔、希尔伯特、罗素,数理逻辑发展初期,代表人物：哥德尔,数理逻辑现代发展时期,这一时期从20世纪40年代开始。主要内容是各种非经典逻辑和四论模型论、集合论、递归论和证明论的突飞猛进的发

9、展,数理逻辑的发展历程,16,第一章 命题逻辑的基本概念,命题逻辑(Logic)研究命题的推理演算命题逻辑的应用数学上定理的推导在计算机科学上，验证程序的正确性主要内容命题的基本概念命题联结词命题合式公式、重言式自然语句的形式化,18,1.1 命题（Proposition）,命题是一个非真即假(不可兼)的陈述句命题是一个陈述句，命令句、疑问句和感叹句都不是命题命题只有两个取值：真或假。这个陈述句所表达的内容可决定是真还是假，而且不是真的就是假的，不能不真又不假，也不能又真又假真假命题凡与事实相符的陈述句为真语句，而与事实不符的陈述句为假语句这就是说，一个命题具有两种可能的取值(又称真值)，为真

10、或为假，并且只能取其一通常用大写字母“T”(1)表示真值为真，用“F”(0)表示真值为假因为只有两种取值，所以这样的命题逻辑称为二值逻辑,19,命题举例,(1) “雪是白的”。 (2) “雪是黑的”。 (3) “好大的雪啊” ！ 不是陈述句，不是命题(4) “一个偶数可表示成两个素数之和”。 只不过当今尚不知其是真命题还是假命题(5) “1+101110”。 这是一个数学表达式，相当于一个陈述句，可以叙述为“1加101等于110”，这个句子所表达的内容在十进制范围中真值为假，而在二进制范围中真值为真。可见，这个命题的真值与所讨论问题的范围有关。(6) “xy” ,20,命题变项,为了对命题作逻

11、辑演算，采用数学手法将命题符号化(形式化)是十分重要的命题的表示：大写符号P表示“雪是白的”Q表示“北京是中国的首都”命题变项：P表示任一命题时，P就称为命题变项(变元)命题与命题变项含义是不同的：命题指具体的陈述句，是有确定的真值命题变项的真值不定，只当将某个具体命题代入命题变项时，命题变项化为命题，方可确定其真值命题与命题变项像初等数学中常量与变量的关系一样如5是一个常量，是一个确定的数字，而x是一个变量，赋给它一个什么值它就代表什么值，即x的值是不定的,21,简单命题和复合命题,简单命题又称原子命题(Primitive proposition)简单命题是不包含任何的与、或、非一类联结词的

12、命题简单命题不可再分割，如“雪是白的”再分割就不是命题了命题“雪是白的而且1+12”不是简单命题，它可以分割为“雪是白的”以及“1+12”两个简单命题，联结词是“而且”在简单命题中，尽管常有主语和谓语，但我们不去加以分割，是将简单命题作为一个不可分的整体来看待，进而作命题演算在谓词逻辑里，才对命题中的主谓结构进行深入分析,22,复合命题(Compound proposition),复合命题：把一个或几个简单命题用联结词(如与、或、非等)联结所构成的新的命题“张三学英语和李四学日语”就是一个复合命题由简单命题“张三学英语” “李四学日语”经联结词“和”联结而成复合命题的真值：依赖于构成该复合命题

13、的各个简单命题的真值以及联结词上例中，当以上两个简单命题真值均为真时，该复合命题方为真命题逻辑所讨论的是多个命题联结而成的复合命题的规律性,23,内容 / 形式,命题是一个可取真或可取假的陈述句数理逻辑不关心内容 这些具体的陈述句的真值究竟为什么或在什么环境下是真还是假数理逻辑只关心形式 命题可以被赋予真或假这样的可能性，以及规定了真值后怎样与其他命题发生联系,24,1.2 命题联结词及真值表,联结词可将命题联结起来构成复杂的命题命题逻辑联结词的引入是十分重要的，其作用相当于初等数学里在实数集上定义的+、等运算符通过联结词便可定义新的命题，从而使命题逻辑的内容变得丰富起来我们要讨论的仅只是复合

14、命题的真值，此值可由组成它的简单命题的真值所确定值得注意的是逻辑联结词与日常自然用语中的有关联结词的共同点和不同点,25,常用的逻辑联结词(五个),否定词（negation）“ ”是个一元联结词，亦称否定符号一个命题P加上否定词就形成了一个新的命题，记作 P，这个新命题是命题的否定，读作非P。 否定词 “ ”的真值规定如下：若命题P的真值为真，那么 P的真值就为假；若P的真值为假，那么 P的真值就为真 P与P间的真值关系，常常使用称作真值表的一种表格来表示.,26,P的定义,真值表,真值表表明了P的真值如何依赖于P的真值真值表描述了命题之间的真值关系，很直观真值表是命题逻辑里研究真值关系的重要

15、工具,27,例1,“昨天张三去看球赛了”该命题以P表示；“昨天张三没有去看球赛”，该新命题便可用P表示 若昨天张三去看球赛了，命题P是真的，那么新命题P必然是假的反之，若命题P是假的，那么P就是真的,28,例2,Q：今天是星期三Q：今天不是星期三Q不能理解为“今天是星期四”，因为“今天是星期三”的否定，并不一定必是星期四，还可能是星期五、星期六Q：这些都是男同学。Q：这些不都是男同学。 (翻译成“这些都不是男同学”是错的。),29,合取词,合取词(Conjunction)是个二元命题联结词，亦称合取符号将两个命题P, Q联结起来，构成一个新的命题P Q，读作P , Q的合取，也可读作P与Q这个

16、新命题P Q的真值与构成它的命题P, Q的真值间的关系，由合取词真值表来规定。,30,合取词真值表,只有当两个命题变项PT，Q=T时方有 PQ T。而P，Q只要有一为F，则PQ =F。PQ可用来表示日常用语P与Q，或P并且Q。,31,例3,P：教室里有10名女同学；Q：教室里有15名男同学；命题P Q : “教室里有10名女同学与15名男同学”。,32,例4,A：今天下雨了B：教室里有100张桌子。命题A B是 ：“今天下雨了并且教室里有100张桌子”,33,合取词与日常自然用语中的联结词,逻辑联结词是自然用语中联结词的抽象，但两者并不等同，这是需注意的日常自然用语里的联结词“和”、“与”、“

17、并且”，一般是表示两种同类有关事物的并列关系。而在逻辑语言中仅考虑命题与命题之间的形式关系并不顾及日常自然用语中是否有此说法。 这样，“”同“与”、“并且”又不能等同视之。日常自然用语中说，“这台机器质量很好，但是很贵”，这句话的含义是说同一台机器质量很好而且很贵。 若用P表示“这台机器质量很好”，用Q表示“这台机器很贵”，那么这句话的逻辑表示就是P Q ，尽管这句话里出现的联结词是“但是”。总之，合取词有“与”、“并且”的含义。,34,析取词,析取词(disjunction)“”是个二元命题联结词将两个命题P, Q联结起来，构成一个新的命题PQ，读作P, Q的析取，也读作P或Q这个新命题的真

18、值与构成它的命题P, Q的真值间的关系，由析取词真值表来规定,35,析取词真值表,当P、Q有一取值为T时, PQ便为T。仅当P、Q均取F值时, PQ方为F。这就是析取词的定义, PQ可用来表示自然用语P或Q。,36,例,例5P: 今天刮风 Q: 今天下雨命题“今天刮风或者下雨”便可由PQ来描述了例6A: 2小于3B: 雪是黑的AB就是命题“2小于3或者雪是黑的” 由于2小于3是真的，所以AB必取值为真，尽管“雪是黑的”这命题取假,37,蕴涵词,蕴涵词(implication)“”是个二元命题联结词将两个命题P, Q联结起来, 构成一个新的命题PQ，读作如果P则Q，或读作P蕴涵Q如果P那么Q，其

19、中P称前件(前项、条件)，Q称后件(后项、结论)规定只有当P为T而Q为F时，PQ = F 而P = F，Q任意，或P = T，Q = T时PQ均取值为T。,蕴涵词 例7,P：天下雨了；Q：地上是湿的；PQ如果天下雨，那么地是湿的， T如果天下雨，那么地不是湿的， F如果天没有下雨，那么地是湿的 T如果天没有下雨，那么地不是湿的 T,39,蕴涵词真值表,PQ = T下, 若P = T必有Q = T, 而不会出现Q = F, 这表明PQ体现了P是Q成立的充分条件。PQ = T下, 若P = F 时可有Q = T, 这表明PQ体现了P不必是Q成立的必要条件。,P: 下雨；Q: 地湿,40,因果关系,

20、引入的目的是希望用来描述命题间的推理，表示因果关系使用PQ能描述推理PQ为真时，只要P为真必有Q真，而不能出现P真而Q假就够了P为假时，Q取真取假，并不违背P为真时Q必真。从而仍可规定P为假时，PQ取真当P = F时对PQ真值的不同定义方式将给推理的讨论带来不同的表示形式，也是允许的,41,PQ = PQ,在P、Q的所有取值下, PQ同PQ都有相同的真值: PQ = PQ (真值相同的等值命题以等号联结)这也说明可由、来表示, 从逻辑上看“如果P则Q”同“非P或Q”是等同的两个命题实际上，, 构成一个联结词的完备集，可表达任何联结词,42,例8,P（命题变元）: n 3 (n为整数) Q（命题

21、变元）: n2 9 命题（命题公式）PQ表示“如果n 3那么n2 9”, 分析PQ的真值P = Q = T。这时如n = 4 3，有n2 = 16 9，这符合事实 PQ = T，正是我们所期望的可以PQ表示P、Q间的因果关系，这时规定P Q是自然的P = T, Q = F。如n 3而 n2 9 由于前提条件n 3不成立，而n2 9成立与否并不重要，都不违反对自然用语“如果n 3那么n2 9”成立的肯定。于是 P = F时可规定P Q = T,43,如果那么,蕴涵词与自然用语“如果那么”有一致的一面，可表示因果关系 然而P、Q是无关的命题时，逻辑上允许讨论PQ。并且P = F则PQ = T，这在

22、自然用语中是不大使用的。对P = F时PQ的值另作规定也是可以的, 同样不违反自然语句“如果那么”可以用PQ来描述。总之，对PQ的这种说明是可接受的, 但也不是说仅只有这样的解释才是合理的,44,例9,P: 2 + 2 = 5Q: 雪是黑的PQ就是命题“如果2 + 2 = 5, 那么雪是黑的”从蕴涵词的定义看，由2 + 2 = 5是不成立的或说P取F值, 不管Q取真取假都有PQ = T,45,蕴涵词,蕴含式PQ可以用多种方式陈述: 给定命题PQ, 我们把QP, PQ, QP分别叫做命题PQ的逆命题, 否命题和逆否命题,46,双条件词,双条件词(Biconditional)“”是个二元命题联结词

23、,47,(PQ)(QP) = PQ,只有当两个命题P、Q的真值相同或说P = Q时，PQ的真值方为T。而当P、Q的真值不同时， PQ = F若建立(PQ)(QP)的真值表，就可发现(PQ)(QP)和PQ有相同的真值，于是 (PQ)(QP) = PQ,48,例10,P: ABC是等腰三角形Q: ABC中有两个角相等命题PQ就是“ABC是等腰三角形当且仅当ABC中有两个角相等”。显然就这个例子而言PQ = T,49,总结,定义的五个联结词是数理逻辑中最基本最常用的逻辑运算一元二元联结词还有多个，此外还有三元以至更多元的联结词，因其极少使用，况且又都可由这五个基本联结词表示出来，所以无需一一定义了联

24、结词是由命题定义新命题的基本方法命题逻辑的许多问题都可化成是计算复合命题的真假值问题，真值表方法是极为有力的工具，是应十分重视和经常使用的,50,总结,由联结词构成新命题的真值表中，对仅由两个变元P、Q构成的新命题A而言，每个变元有T、F两种取值，从而P、Q共有四种可能的取值，对应于真值表中的四行,，每一行下命题A都有确定的真值对P、Q的每组真值组合(如P = T, Q = F)或说真值指派，都称作命题A的一个解释一般地说，当命题A依赖于命题P1, Pn，从P1, Pn 到A的真值表就有2n行, 每一行对应着P1, , Pn的一组真值，称作命题A的一个解释，A有2n个解释，命题的解释用符号I表

25、示,51,总结,由于数理逻辑是采用数学的、符号化的方法来研究命题间最一般的真值规律的，而不涉及判断一个命题本身如何取真取假，抛开命题的具体含义，而是抽象形式地讨论逻辑关系，这就导致了数理逻辑中所讨论的命题与自然用语的差异联结词、同构成计算机的与门、或门和非门电路是相对应的。从而命题逻辑是计算机硬件电路的表示、分析和设计的重要工具。也正是数理逻辑应用于实际特别是应用于计算机学科推动了数理逻辑的发展。,52,不同的符号,五个联结词在不同的书中会采用不同的符号P以P表示PQ以PQ表示PQ以P + Q表示 PQ以PQ表示 PQ以PQ表示,53,1.3 合式公式(Well Formed Formula)

26、,命题公式是命题逻辑讨论的对象由命题变项使用联结词可构成任意多的复合命题，如PQ, PQR, PQ等。问题是它们是否都有意义呢？只有一个联结词的命题P，PQ，PQ当然是有意义的由两个联结词构成的命题PQR至少意义不明确，是先作PQ再对R做，还是先作QR再对P作呢? 括号解决 由命题变项、命题联结词和圆括号便组成了命题逻辑的全部符号进一步的问题是建立一个一般的原则以便生成所有的合法的命题公式，并能识别什么样的符号串是合法的（有意义的）？,54,合式公式(简记为Wff)的定义,简单命题(包括简单命题常量与命题变项)是合式公式如果A是合式公式，那么A也是合式公式如果A、B是合式公式，那么(AB)，(

27、AB)， (AB)和(AB)是合式公式当且仅当经过有限次地使用1, 2, 3所组成的符号串才是合式公式这个定义给出了建立合式公式的一般原则，也给出了识别一个符号串是否是合式公式的原则这是递归(归纳)的定义。在定义中使用了所要定义的概念，如在2和3中都出现了所要定义的合式公式字样，其次是定义中规定了初始情形，如1中指明了已知的简单命题是合式公式。条件4说明了哪些不是合式公式，而1、2和3说明不了这一点,55,判断一个公式是否为合式公式,若判断一个公式是否为合式公式，必然要层层解脱回归到简单命题方可判定合式公式(PQ), (P(PQ), (PQ)(QR)(PR)非合式公式 PQ, (PQ)( Q)

28、, (PQ,56,约定,为了减少圆括号的数量，可以引入一些约定规定联结词优先级的办法，可按， ， ，的排列次序安排优先的级别多个同一联结词按从左到右的优先次序。这样，在书写合式公式时，可以省去部分或全部圆括号。通常采用省略一部分又保留一部分括号的办法，这样选择就给公式的阅读带来方便。如 (P(QR)可写成P(QR)或PQR(P(PR)可写成P(PR)命题演算中只讨论合式公式，将合式公式就称作公式,57,1.4 重言式 /可满足式/矛盾式,如果一个公式，对于任一解释I其值都为真，就称为重言式（永真式）。如PP是一个重言式由、和联结的重言式仍是重言式。一个公式，如在某个解释I0下值为真, 则称它是

29、可满足的。如PQ，当取I0 = (T, F)，即P = T, Q = F时便有PQ = T, 所以是可满足的重言式当然是可满足的矛盾式（永假式或不可满足式）：如果一个公式，对于任一解释I值都是假的，便称是矛盾式。如PP就是矛盾式,58,三类公式间关系,1. 公式A永真， 当且仅当A永假2. 公式A可满足, 当且仅当A非永真3. 不是可满足的公式必永假4. 不是永假的公式必可满足,59,1.4.2 代入规则,A是一个公式，对A使用代入规则得公式B，若A是重言式，则B也是重言式为保证重言式经代入规则仍得到保持，要求公式中被代换的只能是命题变元(原子命题), 而不能是复合命题对公式中某命题变元施以代

30、入，必须对该公式中出现的所有同一命题变元代换以同一公式。,60,规则1举例 如可用(RS)来代换某公式中的P，而不能反过来将公式中的(RS)以P代之 这一要求可以以代数的例子来说明，如对(a + b)2 = a2 + 2ab + b2 可以a = cd代入，仍会保持等式成立。而若将a + b以cd代入，结果左端得(cd)2，而右端无法代入cd，不能保持等式成立了规则2举例A = (RS)(RS)，用S只代换第二个R，则有： B = (RS)(S S) = RS 不是重言式,例11,61,使用代入规则证明重言式,例12. 判断(RS) (RS)为重言式。因PP为重言式, P以(RS)代入即得例1

31、3. 判断(RS)(RS)(PQ)(PQ)为重言式。不难验证(A(AB)B是重言式，A 以RS代入，B 以PQ代入即得,62,1.5 命题形式化,一些推理问题的描述，常是以自然语句来表示的，需首先把自然语句形式化成逻辑语言，即以符号表示的逻辑公式，然后根据逻辑演算规律进行推理演算先要引入一些命题符号P, Q, 用来表示自然语句中所出现的简单命题，进而依自然语句通过联结词将这些命题符号联结起来，以形成表示自然语句的合式公式,63,1.5.1 简单自然语句的形式化,命题1. 北京不是村庄。令P表示“北京是村庄”，于是命题1可表示为P。命题2. 李明既聪明又用功。令P表示“李明聪明”，Q表示“李明用

32、功”，于是命题2可表示为PQ。命题3. squr(2)是有理数的话, 2squr(2)也是有理数。令P表示“squr(2)是有理数”，Q表示“2squr(2)是有理数”，于是命题3可表示为PQ。,64,1.5.2 较复杂自然语句的形式化,需注意的是逻辑联结词是从自然语句中提炼抽象出来的，它仅保留了逻辑内容，而把自然语句所表达的主观因素、心理因素以及文艺修辞方面的因素全部撇开了，从而命题联结词只表达了自然语句的一种客观性质又由于自然语句本身并不严谨，常有二义性，自然会出现同一自然语句的不等价的逻辑描述，其根由在于人们对同一自然语句的不同理解例如: 爱因斯坦是我的崇拜者自然语句联结词与逻辑联结词无

33、固定关系,65,张三与李四是表兄弟。 这是普通的自然用语，它是一个命题，令以R表示。若形式地规定: P: 张三是表兄弟。Q: 李四是表兄弟。 那么R = PQ显然，这样的形式化是错误的。原因是“张三是表兄弟”，“李四是表兄弟”都不是命题。实际上“张三与李四是表兄弟”才是一个命题，而且是一个简单命题。这例子说明自然语句中的“与”不一定都能用合取词来表达,例12 (“与”未必为合取词),66,张三或李四都能做这件事。这句话中的“或”不一定就用析取词来表示，应允许有的人把这命题的内容理解为： 张三能做这件事而且李四也能做这件事 这样，这句话便可以PQ的形式表示了,例13 (“或”未必为析取词),67

34、,例14 (“或”未必为析取词),A: 今晚我在家里看电视。B: 今晚我去体育场看球赛。C: 今晚我在家里看电视或去体育场看球赛。问题是C与AB是否表达的是同一命题呢?,68,否。因为C同A、B的真值关系为,例14,69,异或(不可兼或),这表的前三行很容易理解，而第四行是说今晚我在家看电视，又去体育场看球赛。显然对同一个人来说这是不可能的，从而这时C的真值为F。这就说明了C与AB逻辑上是并不相等的。即C中出现的“或”不能以“”来表示C同A, B的逻辑关系，常称为异或(不可兼或), 以 表示, 有不难验证 C = (AB) (AB),70,例15,今天我上班, 除非今天我病了以P表示今天我病了

35、，Q表示今天我上班 可以理解为：除非今天我病了，否则今天我来上班进一步： 如果今天我不生病，那么我来上班可描述成PQ,71,中缀表达式,一般地，合式公式中使用的是联结词的中缀表示，同时，引入括号以便区分运算次序 计算机识别、处理这种公式的方法：反复自左向右，自右向左的扫描例如：公式(P (Q R) (S T)真值的计算过程：1). 开始从左向右扫描，至发现第一个右半括号为止，便返回至最近的左半括号，计算(Q R)的真值； 2). 随后又向右扫描，至发现第二个右半括号，便返回至第二个左半括号，计算(P (Q R)的真值； 3). 以此类推，直至计算结束。多次重复扫描，效率低下,72,波兰表达式,

36、使用联结词构成公式有三种方式：中缀式如P Q ，前缀式如PQ ，后缀式PQ 前缀式用于逻辑学是由波兰数理逻辑学家J. Lukasiewicz提出的，也称为波兰表达式 将中缀式化成波兰式，可由内层括号逐步向外层脱开（或是按运算优先级顺序逐步写成前缀式）以波兰式表示的公式，由计算机识别、处理时可通过自右向左扫描一次完成，避免了重复扫描类似地，可将中缀式化成后缀式（也称为逆波兰式）,73,例16,把P (Q R) S)写成波兰式和逆波兰式：波兰式(内层括号逐步向外层脱开)： PQRS逆波兰式(内层括号逐步向外层脱开)： PQRS,74,例17,把P Q R S写成波兰式和逆波兰式：波兰式(按运算优先

37、级顺序逐步写成前缀式)： PQRS逆波兰式(按运算优先级顺序逐步写成后缀式)： PQRS,75,作业,P12 1(2,4,6,8) 4(2,4,6) 5(2,4,6,8) 6(2),76,悖论,“我正在说谎”。 他是在说谎还是在说真话呢? 如果他讲真话, 那么他所说的是真, 也就是他在说谎。我们得出结论如果他讲真话, 那么他是在说谎 另一方面, 如果他是说谎, 那么他所说的是假, 也就是他在讲真话。我们得出结论如果他说谎, 那么他是讲真话。 从以上分析, 我们得出他必须既非说谎也不是讲真话。这样, 陈述句“我正在说谎”事实上不能指定它的真假, 所以不是命题，而是“悖论”。,77,悖论,悖论是自

38、相矛盾的命题。即如果承认这个命题成立，就可推出它的否定命题成立；反之，如果承认这个命题的否定命题成立，又可推出这个命题成立 A paradox is a statement or group of statements that leads to a contradiction or a situation which defies intuition 例如比较有名的理发师(罗素)悖论：某乡村有一位理发师，一天他宣布：只给不自己刮胡子的人刮胡子。这里就产生了问题：理发师给不给自己刮胡子？如果他给自己刮胡子，他就是自己刮胡子的人，按照他的原则，他不能给自己刮胡子；如果他不给自己刮胡子，他就是不自

39、己刮胡子的人，按照他的原则，他就应该给自己刮胡子。这就产生了矛盾,78,蕴涵词形式化,设 P:天冷，Q:小王穿羽绒服，将下列命题符号化 (1) 只要天冷，小王就穿羽绒服. PQ(2) 因为天冷，所以小王穿羽绒服. PQ(3) 若小王不穿羽绒服，则天不冷. QP (PQ)(4) 除非小王穿羽绒服，否则天不冷. QP (PQ)(5) 如果天不冷，则小王不穿羽绒服. PQ (QP) (6) 只有天冷，小王才穿羽绒服. QP(7) 除非天冷，小王才穿羽绒服. QP(8) 小王穿羽绒服仅当天冷的时候. QP,自然语言形式化的两个例子,假如今天不下雨，我去看电影，否则就在家里读书看报对下面两者进行形式化，并比较它们的不同占据空间、有质量、且不断变化的叫做物质占据空间且有质量的叫做物质，而物质是不断变化的,