离散数学及应用.ppt

《离散数学及应用.ppt》由会员分享，可在线阅读，更多相关《离散数学及应用.ppt（1148页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离散数学离散数学(DiscreteMathematics)计算机科学与技术学院计算机科学与技术学院（SchoolofComputerScience&Technology)魏雪丽魏雪丽12/13/20221引引言言一一.离散数学与计算机离散数学与计算机计计算算机机开开辟辟了了脑脑力力劳劳动动机机械械化化和和自自动动化化的的新新纪元。纪元。计计算算机机的的诞诞生生，人人们们就就要要为为它它进进一一步步发发展创建新的理论，就要寻找合适的数学工具。展创建新的理论，就要寻找合适的数学工具。例：为了描述新开拓的应用领域中的各例：为了描述新开拓的应用领域中的各种数据的结构，就需要适宜的数学工具。种数据的结构

2、，就需要适宜的数学工具。12/13/2022计算机科学与技术学院引引言（续）言（续）故故计计算算机机各各分分支支领领域域中中的的理理论论问问题题，交交错地使用着现代数学的各种不同的论题。错地使用着现代数学的各种不同的论题。因因为为计计算算机机系系统统从从本本质质上上说说是是一一种种离离散散性性的的结结构构，它它的的许许多多性性质质可可以以在在有有限限数数学学系系统统的的框框架架中中来来理理解解，从从中中选选出出一一些些必必要要而而且且是基本的主干论题称为离散数学。是基本的主干论题称为离散数学。因因此此，离离散散数数学学是是随随着着计计算算机机科科学学的的发发展展而而逐逐步步建建立立的的，它它形

3、形成成于于七七十十年年代代初初期期，是一门新兴的工具性学科。是一门新兴的工具性学科。12/13/2022计算机科学与技术学院引引言（续）言（续）离离散散数数学学是是现现代代数数学学的的一一个个重重要要分分支支，是是计计算算机机科科学学与与技技术术的的理理论论基基础础，是是计计算算机机科学与技术专业的核心、骨干课程。科学与技术专业的核心、骨干课程。它它以以研研究究离离散散量量的的结结构构和和相相互互间间的的关关系系为为主主要要目目标标，其其研研究究对对象象一一般般是是有有限限个个或或可可数数个个元元素素，因因此此它它充充分分描描述述了了计计算算机机科科学学离离散性散性的特点。的特点。12/13/

4、2022计算机科学与技术学院引引言（续）言（续）二、二、该课程的主要内容：该课程的主要内容：离散数学课程的主要内容可以分为四个部分：离散数学课程的主要内容可以分为四个部分：数理逻辑，数理逻辑，包括命题逻辑和谓词逻辑。包括命题逻辑和谓词逻辑。(教材的第一、二章教材的第一、二章)集合论，集合论，包括集合、关系和函数。包括集合、关系和函数。（教材的第三、四章）（教材的第三、四章）代数系统，代数系统，包括代数系统的一般概念，几类典型的代数系包括代数系统的一般概念，几类典型的代数系统和格。统和格。（教材的第五、六章）（教材的第五、六章）图论，图论，包括图的基本概念，几种特殊的图。包括图的基本概念，几种特

5、殊的图。(教材的第七章教材的第七章)12/13/2022计算机科学与技术学院引引言（续）言（续）三、三、学习该课程的目的学习该课程的目的：1.为为学学习习计计算算机机后后继继课课程程，如如数数据据结结构构、编编译译理理论论、操操作作系系统统、数数据据库库原原理理、形形式式语语言言及及自自动动机机、软软件件工工程程与与方方法法学学、计计算算机机网网络络和和人人工工智智能能、高高级级程程序序设设计计语语言言等等，提提供供必必要要的的数数学学基基础础；为为阅阅读读计计算算机机文文章章作作充充分分的数学准备。的数学准备。12/13/2022计算机科学与技术学院引引言（续）言（续）数理逻辑：数理逻辑：人

6、工智能，数据库，形式语言及自动机，人工智能，数据库，形式语言及自动机，高级程序设计语言。高级程序设计语言。集合论：集合论：信息结构与检索，数据结构。信息结构与检索，数据结构。图论：图论：可计算性理论，计算机网络可计算性理论，计算机网络,数据结构。数据结构。代数结构：代数结构：开关理论，逻辑设计和程序理论，语法开关理论，逻辑设计和程序理论，语法分析。分析。2.通过学习离散数学，可以培养和提高自己的抽象思通过学习离散数学，可以培养和提高自己的抽象思维和逻辑推理能力，维和逻辑推理能力，获得解决实际问题能力，获得解决实际问题能力，为以为以后的软、硬件学习和研究开发工作，打下坚实的数后的软、硬件学习和研

7、究开发工作，打下坚实的数学基础。学基础。12/13/2022计算机科学与技术学院引引言言（续）（续）四、四、教学要求教学要求：通通过过该该课课程程的的学学习习，学学生生应应当当了了解解并并掌掌握握计计算算机机科科学学中中普普遍遍采采用用的的离离散散数数学学中中的的一一些些基基本本概概念念、基本思想、基本方法。基本思想、基本方法。五、五、自学要求自学要求：由于课时少，内容多且抽象，故要求课前预习，由于课时少，内容多且抽象，故要求课前预习，课后复习；认真完成习题，通过做课后习题，来加课后复习；认真完成习题，通过做课后习题，来加深对该课程中的一些基本概念的理解，逐步提高自深对该课程中的一些基本概念的

8、理解，逐步提高自己的抽象思维和逻辑推理能力。己的抽象思维和逻辑推理能力。作业每星期一交，作为平时成绩作业每星期一交，作为平时成绩。12/13/2022计算机科学与技术学院引引言言（续）（续）六、六、参考教材参考教材：1.离散数学及其应用魏雪丽等编著离散数学及其应用魏雪丽等编著机械工业出版社机械工业出版社2.离散数学离散数学左孝凌等著左孝凌等著上海科技文献出版社上海科技文献出版社3.离散数学离散数学理论理论分析分析题解题解左孝凌等著左孝凌等著上海科技文献出版社上海科技文献出版社4.DiscreteMathematicsandItsApplications（英英文文版）版）(美美)KennethH

9、.Rosen著著机械工业出版社机械工业出版社12/13/2022计算机科学与技术学院引引言言（续）（续）七、七、考核方式：考核方式：期末考试成绩占期末考试成绩占70%,平时成绩占平时成绩占30%.12/13/2022计算机科学与技术学院第一部分第一部分数理逻辑数理逻辑（MathematicalLogic)MathematicalLogic)v逻逻辑辑：是是研研究究推推理理的的科科学学。公公元元前前四四世世纪纪由由希希腊腊的的哲哲学学家家亚亚里里斯斯多多德德首首创创。作作为为一一门门独独立立科科学学，十十七七世世纪纪，德德国国的的莱莱布布尼尼兹兹(Leibniz)给给逻逻辑辑学学引引进进了了符符

10、号号,又称为数理逻辑又称为数理逻辑(或符号逻辑或符号逻辑)。逻辑逻辑可分为：可分为：1.形式逻辑（通过数学方法）形式逻辑（通过数学方法）数理逻辑数理逻辑2.辩证逻辑辩证逻辑指引进一套符号体系的方法。指引进一套符号体系的方法。辩证逻辑辩证逻辑是研究反映客观世界辩证发展过程的人类是研究反映客观世界辩证发展过程的人类思维的形态的。思维的形态的。12/13/2022计算机科学与技术学院第一部分第一部分数理逻辑数理逻辑（MathematicalLogic)MathematicalLogic)v形形式式逻逻辑辑是是研研究究思思维维的的形形式式结结构构和和规规律律的的科科学学，它它撇撇开开具具体体的的、个个

11、别别的的思思维维内内容容，从从形形式式结结构构方方面面研研究概念、判断和推理及其正确联系的规律。究概念、判断和推理及其正确联系的规律。v数数理理逻逻辑辑是是用用数数学学方方法法研研究究推推理理的的形形式式结结构构和和推推理理的的规规律律的的数数学学学学科科。它它的的创创始始人人Leibniz，为为了了实实现现把把推推理理变变为为演演算算的的想想法法，把把数数学学引引入入了了形形式式逻逻辑辑。其其后后，又又经经多多人人努努力力，逐逐渐渐使使得得数数理理逻逻辑辑成成为为一一门门专门的学科。专门的学科。v上上个个世世纪纪30年年代代以以后后，数数理理逻逻辑辑进进入入一一个个崭崭新新的的发发展展阶阶段

12、段，逻逻辑辑学学不不仅仅与与数数学学结结合合，还还与与计计算算机机科科学学等密切关联。等密切关联。12/13/2022计算机科学与技术学院第一部分第一部分数理逻辑数理逻辑（MathematicalLogic)MathematicalLogic)v1931年年Godel不不完完全全性性定定理理的的提提出出，以以及及递递归归函函数数可可计计算算性性的的引引入入，促促使使了了1936年年Turing机机的的产产生生，十十年年后后，第第一一台台电电子子计计算算机问世机问世。v从从广广义义上上讲讲，数数理理逻逻辑辑包包括括四四论论、两两演演算算即即集集合合论论、模模型型论论、递递归归论论、证证明明论论和

13、和命命题题演演算算、谓谓词词演演算算，但但现现在在提提到到数数理理逻逻辑辑，一一般般是是指指命命题题演演算算和和谓谓词词演演算算。本本书书课课程程只只研究这两个演算。研究这两个演算。12/13/2022计算机科学与技术学院第一部分第一部分数理逻辑数理逻辑（MathematicalLogic)MathematicalLogic)v数数理理逻逻辑辑与与计计算算机机学学、控控制制论论、人人工工智智能能的的相相互互渗渗透透推推动动了了其其自自身身的的发发展展，模模糊糊逻逻辑辑、概概率率逻逻辑辑、归归纳纳逻逻辑辑、时时态态逻逻辑辑等等都都是是目目前前比较热门的研究领域。比较热门的研究领域。12/13/2

14、022计算机科学与技术学院第一章第一章命题逻辑命题逻辑（PropositionalLogic）n1.1命题命题及其及其表示方法表示方法(PropositionandItsExpression)n1.2逻辑联结词逻辑联结词(LogicalConnectives)n1.3命题公式与翻译命题公式与翻译(PropositionalFormula&ItsTranslation)n n1.4真值表与等价公式真值表与等价公式(TruthTablesandPrepositionalEquivalences)12/13/2022计算机科学与技术学院第一章第一章命题逻辑命题逻辑（PropositionalLogi

15、c）n n1.5重言式与重言式与蕴含蕴含式式(TautologyandImplication)n n1.6其它联结词其它联结词(OtherConnectives)n n1.7对偶与范式对偶与范式(Dual&NormalForm)n n1.8推理理论推理理论(InferenceTheory)12/13/2022计算机科学与技术学院第一章第一章命题逻辑命题逻辑（PropositionalLogic）n n1.1命题及其表示方法命题及其表示方法n1.1.1命题命题n1.1.2命题的表示方法命题的表示方法n1.1.3命题的分类命题的分类12/13/2022计算机科学与技术学院第一章第一章命题逻辑命题逻

16、辑（PropositionalLogic）1.11.1命题及其表示方法命题及其表示方法命题及其表示方法命题及其表示方法1.1.1命题命题（Proposition)数数 理理 逻逻 辑辑 研研 究究 的的 中中 心心 问问 题题 是是 推推 理理（inference),而而推推理理的的前前提提和和结结论论都都是是表表达达判判断断的的陈陈述述句句，因因而而表表达达判判断断的的陈陈述述句句构构成成了了推推理理的的基本单位基本单位。12/13/2022计算机科学与技术学院第一章第一章命题逻辑命题逻辑（PropositionalLogic）1.11.1命题及其表示方法命题及其表示方法命题及其表示方法命题

17、及其表示方法基本概念基本概念命题：能够判断真假的陈述句。命题：能够判断真假的陈述句。命命题题的的真真值值：命命题题的的判判断断结结果果。命命题题的的真真值值只只取取两两个个值值:真真（用用T(true)或或1表表示示）、假假（用用F(false)或或0表表示示）。真命题：判断为正确的命题，即真值为真的命题。真命题：判断为正确的命题，即真值为真的命题。假命题：判断为错误的命题，即真值为假的命题。假命题：判断为错误的命题，即真值为假的命题。12/13/2022计算机科学与技术学院因而又可以称因而又可以称命题是具有唯一真值的陈述句。命题是具有唯一真值的陈述句。判断命题的两个步骤判断命题的两个步骤：1

18、、是否为陈述句；、是否为陈述句；2、是否有确定的、唯一的真值。、是否有确定的、唯一的真值。例例：判断下列句子是否为命题。：判断下列句子是否为命题。(1).100是自然数。是自然数。T(2).太阳从西方升起。太阳从西方升起。F第一章第一章命题逻辑命题逻辑（PropositionalLogic）1.11.1命题及其表示方法命题及其表示方法命题及其表示方法命题及其表示方法12/13/2022计算机科学与技术学院第一章第一章命题逻辑命题逻辑（PropositionalLogic）1.11.1命题及其表示方法命题及其表示方法命题及其表示方法命题及其表示方法(3).3+3=8.F(4).Howdoyoud

19、o?疑问句，疑问句，不是命题不是命题(5).明明年年的的十十月月一一日日是是晴晴天天。是是命命题题，其其真真值值到到明年十月一日方可知道。明年十月一日方可知道。(6).x+39不是命题不是命题(7).我正在说谎。我正在说谎。是悖论是悖论12/13/2022计算机科学与技术学院第一章第一章命题逻辑命题逻辑（PropositionalLogic）1.11.1命题及其表示方法命题及其表示方法命题及其表示方法命题及其表示方法(8).1+101=110二进制中为真，十进制中为假。二进制中为真，十进制中为假。(9).如果太阳从西方升起，那么如果太阳从西方升起，那么2是奇数是奇数。T(10).国足能杀入国足

20、能杀入2006世界杯当且仅当世界杯当且仅当2+2=4。F(11).今天天气多好啊！今天天气多好啊！感叹句，感叹句，不是命题不是命题(12).请你关上门！请你关上门！祁使句，不祁使句，不是命题，是命题，(13).别别的的星星球球上上有有生生物物。是是命命题题，客客观观上上能能判判断真假。断真假。12/13/2022计算机科学与技术学院第一章第一章命题逻辑命题逻辑（PropositionalLogic）1.11.1命题及其表示方法命题及其表示方法命题及其表示方法命题及其表示方法说明：说明：（1）只有具有确定真值的陈述句才是命题。）只有具有确定真值的陈述句才是命题。一切没有判断内容的句子，无所谓一切

21、没有判断内容的句子，无所谓是非的句子，如是非的句子，如感叹句、祁使句、感叹句、祁使句、疑问疑问句等都不是命题。句等都不是命题。（2）因为因为命题只有两种真值，所以命题只有两种真值，所以“命题命题逻逻辑辑”又称又称“二值逻辑二值逻辑”。12/13/2022计算机科学与技术学院第一章第一章命题逻辑命题逻辑（PropositionalLogic）1.11.1命题及其表示方法命题及其表示方法命题及其表示方法命题及其表示方法(3)“具有确定真值具有确定真值”是指客观上的具有，与我们是指客观上的具有，与我们是否知道它的真值是两回事。如上例中是否知道它的真值是两回事。如上例中的（的（5）和（）和（13）。）

22、。1.1.2命题的表示方法命题的表示方法在在本本书书中中，用用大大写写英英文文字字母母A,B,P,Q或或带带下下标标的的字字母母P1,P2,P3,或或数数字字(1),2,等等表表示示命命题题，称之为命题标识符。称之为命题标识符。12/13/2022计算机科学与技术学院第一章第一章命题逻辑命题逻辑（PropositionalLogic）1.11.1命题及其表示方法命题及其表示方法命题及其表示方法命题及其表示方法例如：例如：P：罗纳尔多是球星。：罗纳尔多是球星。Q：5是负数。是负数。P3：明天天气晴。明天天气晴。(2)：太阳从西方升起。：太阳从西方升起。皆皆为为符符号号化化的的命命题题，其其真真值

23、值依依次次为为1、0、1或或0、0。12/13/2022计算机科学与技术学院第一章第一章命题逻辑命题逻辑（PropositionalLogic）1.11.1命题及其表示方法命题及其表示方法命题及其表示方法命题及其表示方法命题标识符又有命题常量、命题变元和原子变元命题标识符又有命题常量、命题变元和原子变元之分。之分。命题常量命题常量：表示确定命题的命题标识符。：表示确定命题的命题标识符。命题变元命题变元：命题标识符如仅是表示任意命题的位置标：命题标识符如仅是表示任意命题的位置标志，就称为命题变元。志，就称为命题变元。原子变元原子变元：当命题变元表示原子命题时，该变元称为：当命题变元表示原子命题时

24、，该变元称为原子变元。原子变元。命题变元也用命题变元也用A,B,P,Q,P1,P2,P3,表示。表示。12/13/2022计算机科学与技术学院第一章第一章命题逻辑命题逻辑（PropositionalLogic）1.11.1命题及其表示方法命题及其表示方法命题及其表示方法命题及其表示方法1.1.3命题的分类：命题的分类：简单简单/原子命题：原子命题：不能分解为更简单的陈述语不能分解为更简单的陈述语句的命题句的命题(如上例中的命题如上例中的命题)。复合命题：复合命题：由简单命题通过由简单命题通过联结词联结词联结而成联结而成的命题。的命题。联结词就是复合命题中的运算符。联结词就是复合命题中的运算符。

25、12/13/2022计算机科学与技术学院第一章第一章命题逻辑命题逻辑（PropositionalLogicPropositionalLogic）1.11.1命题及其表示方法命题及其表示方法命题及其表示方法命题及其表示方法注意注意：（1）一一个个符符号号(如如P),它它表表示示的的是是命命题题常常量量还还是是命题变元，一般由上下文来确定。命题变元，一般由上下文来确定。（2）命命题题变变元元可可以以表表示示任任意意命命题题，它它不不能能确确定定真真值值，故故命命题题变变元元不不是是命命题题。这这与与“变变数数x不不是数是数”是一样的道理。是一样的道理。12/13/2022计算机科学与技术学院第一章

26、第一章命题逻辑命题逻辑（PropositionalLogicPropositionalLogic）1.11.1命题及其表示方法命题及其表示方法命题及其表示方法命题及其表示方法小结：小结：本节主要介绍了命题、命题的真值、本节主要介绍了命题、命题的真值、原子命题、复合命题、命题标识符、命题常量、原子命题、复合命题、命题标识符、命题常量、命题变元和原子变元的概念。命题变元和原子变元的概念。重点理解和掌握命题、命题变元、简单（原子）重点理解和掌握命题、命题变元、简单（原子）命题、复合命题四个概念。命题、复合命题四个概念。作业：作业：P21,212/13/2022计算机科学与技术学院第一章第一章命题逻辑

27、命题逻辑（PropositionalLogic）1.2逻辑联结词逻辑联结词(LogicalConnectives)1.2.1否定联结词否定联结词(Negation)1.2.2合取联结词合取联结词(Conjunction)1.2.3析取联结词析取联结词(Disjunction)1.2.4条件联结词条件联结词(蕴涵联结词蕴涵联结词Conditional)1.2.5双条件联结双条件联结(等值联结词等值联结词Biconditional)12/13/2022计算机科学与技术学院第一章第一章命题逻辑命题逻辑（PropositionalLogic）1.2逻辑联结词逻辑联结词(LogicalConnectiv

28、es)在在命命题题逻逻辑辑中中,主主要要研研究究的的是是复复合合命命题题,而而复复合合命命题题是是由由原原子子命命题题与与逻逻辑辑联联结结词词组组合合而而成成,联联结结词词组组是是复复合合命命题题的的重要组成部分重要组成部分.12/13/2022计算机科学与技术学院1.2.1否定否定联结词联结词定义定义1.2.1设设P为一命题，为一命题，P的否定是一个新的的否定是一个新的复合命题复合命题,称为称为P的否定式，记作的否定式，记作“P”读作读作“非非P”.符号符号“”称为否定联结词。称为否定联结词。P为真当且为真当且仅当仅当P为假为假.说明说明：“”属于一元属于一元(unary)运算符运算符.第一

29、章第一章命题逻辑命题逻辑（PropositionalLogic）1.2逻辑联结词逻辑联结词(LogicalConnectives)12/13/2022计算机科学与技术学院第一章第一章命题逻辑命题逻辑（PropositionalLogic）1.2逻辑联结词逻辑联结词(LogicalConnectives)n“”的定义也可用下表来说明的定义也可用下表来说明.联结词联结词“”的定义真值表的定义真值表PP011012/13/2022计算机科学与技术学院第一章第一章命题逻辑命题逻辑（PropositionalLogic）1.2逻辑联结词逻辑联结词(LogicalConnectives)例例1.P:天津是

30、一个城市天津是一个城市.Q:3是偶数是偶数.于是于是:P:天津不是一个城市天津不是一个城市.Q:3不是偶数不是偶数.例例2.P:苏州处处清洁苏州处处清洁.Q:这些都是男同学这些都是男同学.P:苏州不处处清洁苏州不处处清洁(注意注意,不是处处不清洁不是处处不清洁).Q:这些不都是男同学这些不都是男同学.12/13/2022计算机科学与技术学院第一章第一章命题逻辑命题逻辑（PropositionalLogic）1.2逻辑联结词逻辑联结词(LogicalConnectives)1.2.2合取联结词合取联结词(Conjunction)定义定义1.2.2设设P,Q为二命题，复合命题为二命题，复合命题“P

31、并且并且Q”（或（或“P与与Q”）称为）称为P与与Q的合取式，记作的合取式，记作PQ，符号，符号“”称为合取联结词称为合取联结词.PQ为真为真当且仅当当且仅当P P和和Q Q同时为真同时为真.12/13/2022计算机科学与技术学院第一章第一章命题逻辑命题逻辑（PropositionalLogic）1.2逻辑联结词逻辑联结词(LogicalConnectives)联结词联结词“”的定义真值表的定义真值表PQP Q0 00 00 00 01 10 01 10 00 01 11 11 112/13/2022计算机科学与技术学院第一章第一章命题逻辑命题逻辑（PropositionalLogic）1.

32、2逻辑联结词逻辑联结词(LogicalConnectives)说明：说明：“”属于二元属于二元(binary)运算符运算符.合取运算特点合取运算特点：只有参与运算的二命题全为真：只有参与运算的二命题全为真时，运算结果才为真，否则为假。时，运算结果才为真，否则为假。自然语言中的表示自然语言中的表示“并且并且”意思的联结词，如意思的联结词，如“既既又又”、“不但不但而且而且”、“虽然虽然但是但是”、“一一面面一面一面”、“和和”、“与与”等都可以等都可以符号化为符号化为。12/13/2022计算机科学与技术学院第一章第一章命题逻辑命题逻辑（PropositionalLogic）1.2逻辑联结词逻辑

33、联结词(LogicalConnectives)n例例3.将下列命题符号化将下列命题符号化.(1)李平既聪明又用功李平既聪明又用功.(2)李平虽然聪明李平虽然聪明,但不用功但不用功.(3)李平不但聪明李平不但聪明,而且用功而且用功.(4)李平不是不聪明李平不是不聪明,而是不用功而是不用功.解解:设设P:李平聪明李平聪明.Q:李平用功李平用功.则则(1)PQ(2)PQ(3)PQ(4)(P)Q12/13/2022计算机科学与技术学院第一章第一章命题逻辑命题逻辑（PropositionalLogic）1.2逻辑联结词逻辑联结词(LogicalConnectives)注意注意：不要见到不要见到“与与”或

34、或“和和”就使用联结词就使用联结词！例如例如:(1)李敏和李华是姐妹。李敏和李华是姐妹。(2)李敏和张华是朋友。李敏和张华是朋友。12/13/2022计算机科学与技术学院第一章第一章命题逻辑命题逻辑（PropositionalLogic）1.2逻辑联结词逻辑联结词(LogicalConnectives)例例4.试生成下列命题的合取试生成下列命题的合取.(1)P:我们在我们在6-503.Q:今天是星期二今天是星期二.(2)S：李平在吃饭：李平在吃饭.R：张明在吃饭：张明在吃饭.解解:(1)PQ:我们在我们在6-503且今天是星期二且今天是星期二.(2)SR:李平与张明在吃饭李平与张明在吃饭.12

35、/13/2022计算机科学与技术学院第一章第一章命题逻辑命题逻辑（PropositionalLogicPropositionalLogic）1.2逻辑联结词逻辑联结词(LogicalConnectives)12/13/2022计算机科学与技术学院第一章第一章命题逻辑命题逻辑（PropositionalLogic）1.2逻辑联结词逻辑联结词(LogicalConnectives)1.2.3析取联结词析取联结词(Disjunction)定义定义1.2.3设设P,Q为二命题，复合命题为二命题，复合命题“P或或Q”称为称为P与与Q的析取式，记作的析取式，记作PQ，符号，符号称为称为析取联结词析取联结词

36、.PQ为真当且仅当为真当且仅当P与与Q中至少有中至少有一个为真一个为真.12/13/2022计算机科学与技术学院第一章第一章命题逻辑命题逻辑（PropositionalLogic）1.2逻辑联结词逻辑联结词(LogicalConnectives)联结词联结词“”的定义真值表的定义真值表PQP Q0 00 00 00 01 11 11 10 01 11 11 11 112/13/2022计算机科学与技术学院第一章第一章命题逻辑命题逻辑（PropositionalLogic）1.2逻辑联结词逻辑联结词(LogicalConnectives)说明：说明：“”属于二元属于二元(binary)运算符运算

37、符.析取运算特点析取运算特点：只有参与运算的二命题全为假：只有参与运算的二命题全为假时，运算结果才为假，否则为真。时，运算结果才为假，否则为真。由析取联结词的定义可以看出，由析取联结词的定义可以看出，“”与汉与汉语中的联结词语中的联结词“或或”意义相近，但又不完全相同。意义相近，但又不完全相同。在现代汉语中，联结词的在现代汉语中，联结词的“或或”实际上有实际上有“可兼或可兼或”和和“排斥或排斥或”之分。之分。12/13/2022计算机科学与技术学院第一章第一章命题逻辑命题逻辑（PropositionalLogic）1.2逻辑联结词逻辑联结词(LogicalConnectives)考察下面命题：

38、考察下面命题：（1）小王爱打球或爱跑步。）小王爱打球或爱跑步。（可兼或）可兼或）设设P：小王爱打球。：小王爱打球。Q：小王爱跑步。：小王爱跑步。则上述命题可符号化为：则上述命题可符号化为：PQ（2）林芳学过英语或法语。）林芳学过英语或法语。（可兼或）可兼或）设设P：林芳学过英语林芳学过英语。Q：林芳学过法语林芳学过法语。则上述命题可符号化为：则上述命题可符号化为：PQ12/13/2022计算机科学与技术学院第一章第一章命题逻辑命题逻辑（PropositionalLogic）1.2逻辑联结词逻辑联结词(LogicalConnectives)（3）派小王或小李中的一人去开会。）派小王或小李中的一人

39、去开会。（排斥或排斥或）设设P：派小王去开会。派小王去开会。Q：派小李去开会。派小李去开会。则上述命题可符号化为：则上述命题可符号化为：(PQ)(PQ)（4）人固有一死，或重于泰山或轻于鸿毛）人固有一死，或重于泰山或轻于鸿毛.(排斥或排斥或排斥或排斥或）（5）ab=0,即即a=0或或b=0.（可兼或）可兼或）由此可见由此可见,“PQ”表示的是表示的是“可兼或可兼或”.12/13/2022计算机科学与技术学院第一章第一章命题逻辑命题逻辑（PropositionalLogic）1.2逻辑联结词逻辑联结词(LogicalConnectives)注意：注意：当当P和和Q客观上不能同时发生时，客观上不能

40、同时发生时，“P或或Q”可以符号化为可以符号化为“PQ”。例如：小王现在在宿舍或在图书馆。设例如：小王现在在宿舍或在图书馆。设P：小王现在在宿舍。：小王现在在宿舍。Q：小王现在在图书馆。：小王现在在图书馆。则上述命题可符号化为：则上述命题可符号化为：PQ。12/13/2022计算机科学与技术学院第一章第一章命题逻辑命题逻辑（PropositionalLogic）1.2逻辑联结词逻辑联结词(LogicalConnectives)12/13/2022计算机科学与技术学院第一章第一章命题逻辑命题逻辑（PropositionalLogic）1.2逻辑联结词逻辑联结词(LogicalConnective

41、s)1.2.4.条件联结词条件联结词(蕴涵联结词蕴涵联结词Conditional)定义定义1.2.4设设P,Q为二命题，复合命题为二命题，复合命题“如果如果P则则Q(若若P则则Q)”称为称为P与与Q的条件命题的条件命题,记作记作PQ.PQ为假当且仅当为假当且仅当P为真且为真且Q为假为假.称符称符号号“”为条件联结词。并称为条件联结词。并称P为前件，为前件，Q为后为后件件.12/13/2022计算机科学与技术学院第一章第一章命题逻辑命题逻辑（PropositionalLogic）1.2逻辑联结词逻辑联结词(LogicalConnectives)联结词联结词“”的定义真值表的定义真值表PQPQ0

42、00 01 10 01 11 11 10 00 01 11 11 112/13/2022计算机科学与技术学院第一章第一章命题逻辑命题逻辑（PropositionalLogic）1.2逻辑联结词逻辑联结词(LogicalConnectives)注：注：（1）PQ表表示示的的基基本本逻逻辑辑关关系系是是,Q是是P的的必必要要条条件件或或P是是Q的的充充分分条条件件.因因此此复复合合命命题题“只只要要P就就Q”、“因因为为P，所所以以Q”、“P仅仅当当Q”、“只有只有Q才才P”等都可以符号化为等都可以符号化为PQ的形式。的形式。（2）“”属于二元属于二元(binary)运算运算.12/13/2022

43、计算机科学与技术学院第一章第一章命题逻辑命题逻辑（ProPositionalLogicProPositionalLogic）1.2逻辑联结词逻辑联结词(LogicalConnectives)例例5.将下列命题符号化。将下列命题符号化。（1 1）天不下雨，则草木枯黄。）天不下雨，则草木枯黄。P：天下雨。：天下雨。Q：草木枯黄。：草木枯黄。则原命题可表示为：则原命题可表示为：PQ。（2）如果小明学日语，小华学英语，则小芳）如果小明学日语，小华学英语，则小芳学德语。学德语。P：小明学日语：小明学日语.Q：小华学英语：小华学英语.R：小芳学德语：小芳学德语.则原命题可表示为：则原命题可表示为：(PQ)

44、R12/13/2022计算机科学与技术学院第一章第一章命题逻辑命题逻辑（PropositionalLogic）1.2逻辑联结词逻辑联结词(LogicalConnectives)（3）只要不下雨，我就骑自行车上班。）只要不下雨，我就骑自行车上班。P：天下雨。：天下雨。Q：我骑自行车上班。：我骑自行车上班。则原命题可表示为：则原命题可表示为：PQ。（4）只有不下雨，我才骑自行车上班。）只有不下雨，我才骑自行车上班。P：天下雨。：天下雨。Q：我骑自行车上班。：我骑自行车上班。则原命题可表示为：则原命题可表示为：QP。12/13/2022计算机科学与技术学院第一章第一章命题逻辑命题逻辑（Proposi

45、tionalLogic）1.2逻辑联结词逻辑联结词(LogicalConnectives)（5）如果如果2+2=4,则则太阳从东方升起太阳从东方升起。(PQ,T)PQ如果如果2+2=4,则则太阳从西方升起太阳从西方升起。(PR,F)R如果如果2+24,则太阳从东方升起。则太阳从东方升起。(PQ,T)如果如果2+24,则太阳从西方升起。则太阳从西方升起。(PR,T)12/13/2022计算机科学与技术学院第一章第一章命题逻辑命题逻辑（PropositionalLogic）1.2逻辑联结词逻辑联结词(LogicalConnectives)注意注意:(1)与与自自然然语语言言的的不不同同：前前件件与

46、与后后件件可可以以没没有有任任何内在联系！何内在联系！(2)在数学中，在数学中，“若若P则则Q”往往表示前件往往表示前件P为真，为真，则后件则后件Q为真的推理关系为真的推理关系.但数理逻辑中，当前但数理逻辑中，当前件件P为假时，为假时，PQ的真值为真。的真值为真。12/13/2022计算机科学与技术学院第一章第一章命题逻辑命题逻辑（PropositionalLogic）1.2逻辑联结词逻辑联结词(LogicalConnectives)1.2.5双条件联结双条件联结(等值联结词等值联结词Biconditional)定义定义1.2.5设设P,Q为二命题，复合命题为二命题，复合命题“P当且仅当且仅当

47、当Q”称为称为P与与Q的双条件命题，记作的双条件命题，记作PiffQ或或PQ，符号，符号称为双条件（等值）联结词。称为双条件（等值）联结词。PQ为真当且仅当为真当且仅当P，Q真值相同。真值相同。12/13/2022计算机科学与技术学院第一章第一章命题逻辑命题逻辑（PropositionalLogic）1.2逻辑联结词逻辑联结词(LogicalConnectives)联结词联结词“”的定义真值表的定义真值表PQPQ0 00 01 10 01 10 01 10 00 01 11 11 112/13/2022计算机科学与技术学院第一章第一章命题逻辑命题逻辑（PropositionalLogic）1.

48、2逻辑联结词逻辑联结词(LogicalConnectives)注：注：（1）P仅当仅当Q可译为可译为PQP当当Q可译为可译为QPP当且仅当当且仅当Q译为译为PQ（2）“”属于二元属于二元(binary)运算符。运算符。(3)双条件命题双条件命题PQ所表达的逻辑关系是所表达的逻辑关系是,P与与Q互为充分必要条件互为充分必要条件,相当于相当于(PQ)(QP).只只要要P与与Q的真值同为的真值同为1或同为或同为0,PQ的真值就为的真值就为1,否则否则PQ的真值为的真值为0.双条件联结词连接的两双条件联结词连接的两个命题之间可以没有因果关系。个命题之间可以没有因果关系。12/13/2022计算机科学与

49、技术学院第一章第一章命题逻辑命题逻辑（PropositionalLogic）1.2逻辑联结词逻辑联结词(LogicalConnectives)例例6.分析下列命题的真值分析下列命题的真值.(1)2+2=4当且仅当当且仅当3是奇数是奇数.(PQ)P：2+2=4.Q：3是奇数是奇数.(2)2+2=4当且仅当当且仅当3不是奇数不是奇数.(PQ)(3)2+24当且仅当当且仅当3是奇数是奇数.(PQ)(4)2+24当且仅当当且仅当3不是奇数不是奇数.(PQ)12/13/2022计算机科学与技术学院第一章第一章命题逻辑命题逻辑（ProPositionalLogicProPositionalLogic）1.

50、2逻辑联结词逻辑联结词(LogicalConnectives)约约定定:1.运算次序优先级：运算次序优先级：，.2.相同的运算符按从左至右次序计算，否相同的运算符按从左至右次序计算，否则要加上括号。则要加上括号。3.最外层圆括号可省去。最外层圆括号可省去。小结小结:本节介绍了五种联结词本节介绍了五种联结词(，),重点是理解和掌握重点是理解和掌握五种联结词的内涵及它五种联结词的内涵及它们与自然语言中相应联结词的不同之处们与自然语言中相应联结词的不同之处.12/13/2022计算机科学与技术学院第一章第一章命题逻辑命题逻辑（PropositionalLogic）1.2逻辑联结词逻辑联结词(Logi