1、5/19/2022-1计算机科学与技术学院计算机科学与技术学院（ School of Computer Science & Technology)魏雪丽魏雪丽5/19/2022- 引引 言言一一. 离散数学与计算机离散数学与计算机计算机开辟了脑力劳动机械化和自动化的新计算机开辟了脑力劳动机械化和自动化的新纪元。纪元。 计算机的诞生，人们就要为它进一步发计算机的诞生，人们就要为它进一步发展创建新的理论，就要寻找合适的数学工具。展创建新的理论，就要寻找合适的数学工具。 例：为了描述新开拓的应用领域中的各例：为了描述新开拓的应用领域中的各种数据的结构，就需要适宜的数学工具。种数据的结构，就需要适宜的
2、数学工具。5/19/2022-引引 言（续）言（续） 故计算机各分支领域中的理论问题，交故计算机各分支领域中的理论问题，交错地使用着现代数学的各种不同的论题。错地使用着现代数学的各种不同的论题。 因为计算机因为计算机系统从本质上说是一种离散系统从本质上说是一种离散性的结构性的结构 ，它的许多性质可以在有限数学系，它的许多性质可以在有限数学系统的框架中来理解，从中选出一些必要而且统的框架中来理解，从中选出一些必要而且是基本的主干论题称为离散数学。是基本的主干论题称为离散数学。 因此，离散数学是随着因此，离散数学是随着计算机科学计算机科学的发的发展而逐步建立的，它形成于七十年代初期，展而逐步建立的
3、，它形成于七十年代初期，是一门新兴的工具性学科。是一门新兴的工具性学科。5/19/2022-引引 言（续）言（续） 离散数学是现代数学的一个重要分支，离散数学是现代数学的一个重要分支，是是计算机科学计算机科学与技术与技术的理论基础，是计算机的理论基础，是计算机科学与技术专业的核心、骨干课程。科学与技术专业的核心、骨干课程。 它它以研究以研究离散量离散量的结构和相互间的关系的结构和相互间的关系为主要目标，其研究对象一般是为主要目标，其研究对象一般是有限个有限个或或可可数个数个元素，因此它充分描述了元素，因此它充分描述了计算机科学计算机科学离离散性散性的特点。的特点。5/19/2022-引引 言（
4、续）言（续） 二、二、该课程的主要内容：该课程的主要内容：离散数学课程的主要内容可以分为四个部分：离散数学课程的主要内容可以分为四个部分：数理逻辑，数理逻辑，包括命题逻辑和谓词逻辑。包括命题逻辑和谓词逻辑。(教材的第一、二章教材的第一、二章) 集合论，集合论，包括集合、关系和函数。包括集合、关系和函数。（教材的第三、四章）（教材的第三、四章）代数系统，代数系统，包括代数系统的一般概念，几类典型的代数系包括代数系统的一般概念，几类典型的代数系 统和格。统和格。（教材的第五、六章）（教材的第五、六章）图论，图论，包括图的基本概念，几种特殊的图。包括图的基本概念，几种特殊的图。 (教材的第七章教材的
5、第七章)5/19/2022-引引 言（续）言（续） 三、三、学习该课程的目的学习该课程的目的： 1. 为学习计算机后继课程，如数据结构、为学习计算机后继课程，如数据结构、编译理论、操作系统、数据库原理、编译理论、操作系统、数据库原理、形式语形式语言及自动机、言及自动机、软件工程与方法学、计算机网软件工程与方法学、计算机网络和人工智能、络和人工智能、高级程序设计语言高级程序设计语言等，提供等，提供必要的数学基础；为阅读计算机文章作充分必要的数学基础；为阅读计算机文章作充分的数学准备。的数学准备。5/19/2022-引引 言（续）言（续） 数理逻辑：数理逻辑：人工智能，数据库，形式语言及自动机，人
6、工智能，数据库，形式语言及自动机， 高级程序设计语言。高级程序设计语言。集合论：集合论： 信息结构与检索，数据结构。信息结构与检索，数据结构。 图论：图论： 可计算性理论，计算机网络可计算性理论，计算机网络,数据结构。数据结构。代数结构：代数结构：开关理论，逻辑设计和程序理论，语法开关理论，逻辑设计和程序理论，语法 分析。分析。 2. 通过学习离散数学，可以培养和提高自己的抽象思通过学习离散数学，可以培养和提高自己的抽象思维和逻辑推理能力，维和逻辑推理能力，获得解决实际问题能力，获得解决实际问题能力，为以为以后的软、硬件学习和研究开发工作，打下坚实的数后的软、硬件学习和研究开发工作，打下坚实的
7、数学基础。学基础。5/19/2022-（续）（续）四、四、教学要求教学要求： 通过该课程的学习，学生应当了解并掌握计算通过该课程的学习，学生应当了解并掌握计算机科学中普遍采用的离散数学中的一些基本概念、机科学中普遍采用的离散数学中的一些基本概念、基本思想、基本方法。基本思想、基本方法。五、五、自学要求自学要求： 由于课时少，内容多且抽象，故要求课前预习，由于课时少，内容多且抽象，故要求课前预习，课后复习；认真完成习题，通过做课后习题，来加课后复习；认真完成习题，通过做课后习题，来加深对该课程中的一些基本概念的理解，逐步提高自深对该课程中的一些基本概念的理解，逐步提高自己的抽象思维和逻辑推理能力
8、。己的抽象思维和逻辑推理能力。 作业每星期一交，作为平时成绩作业每星期一交，作为平时成绩。5/19/2022-（续）（续）六、六、参考教材参考教材：1.离散数学及其应用离散数学及其应用魏雪丽等编著魏雪丽等编著 机械工业出版社机械工业出版社2 .离散数学离散数学 左孝凌等著左孝凌等著 上海科技文献出版社上海科技文献出版社3. 离散数学离散数学 理论理论分析分析题解题解 左孝凌等著左孝凌等著 上海科技文献出版社上海科技文献出版社4. Discrete Mathematics and Its Applications （英文（英文版）版） (美美)Kenneth H.Rosen 著著 机械工业出版社
9、机械工业出版社5/19/2022-（续）（续）七、七、考核方式：考核方式：期末考试成绩占期末考试成绩占70%, 平时成绩占平时成绩占30%.5/19/2022-v逻辑：是研究推理的科学。公元前四世纪逻辑：是研究推理的科学。公元前四世纪由希腊的由希腊的哲学家亚里斯多德首创。作为一门独立科学，十七哲学家亚里斯多德首创。作为一门独立科学，十七世纪，德国的莱布尼兹世纪，德国的莱布尼兹(Leibniz)给逻辑学引进了符给逻辑学引进了符号号, 又称为数理逻辑又称为数理逻辑(或符号逻辑或符号逻辑)。 逻辑逻辑可分为：可分为：1. 形式逻辑（通过数学方法）形式逻辑（通过数学方法） 数理逻辑数理逻辑 2. 辩证
10、逻辑辩证逻辑 指引进一套符号体系的方法。指引进一套符号体系的方法。 辩证逻辑辩证逻辑是研究反映客观世界辩证发展过程的人类是研究反映客观世界辩证发展过程的人类思维的形态的。思维的形态的。5/19/2022-v形式逻辑形式逻辑是研究思维的形式结构和规律的科学，它是研究思维的形式结构和规律的科学，它撇开具体的、个别的思维内容，从形式结构方面研撇开具体的、个别的思维内容，从形式结构方面研究概念、判断和推理及其正确联系的规律。究概念、判断和推理及其正确联系的规律。v数理逻辑数理逻辑是用数学方法研究推理的形式结构和推理是用数学方法研究推理的形式结构和推理的规律的数学学科。它的创始人的规律的数学学科。它的创
11、始人Leibniz，为了实，为了实现把推理变为演算的想法，把数学引入了形式逻辑。现把推理变为演算的想法，把数学引入了形式逻辑。其后，又经多人努力，逐渐使得数理逻辑成为一门其后，又经多人努力，逐渐使得数理逻辑成为一门专门的学科。专门的学科。v上个世纪上个世纪30年代以后，数理逻辑进入一个崭新的发年代以后，数理逻辑进入一个崭新的发展阶段，逻辑学不仅与数学结合，还与计算机科学展阶段，逻辑学不仅与数学结合，还与计算机科学等密切关联。等密切关联。5/19/2022-v1931年年Godel不完全性定理的提出，以及递不完全性定理的提出，以及递归函数可计算性的引入，促使了归函数可计算性的引入，促使了1936
12、年年Turing机的产生，十年后，第一台电子计算机的产生，十年后，第一台电子计算机问世机问世。v从广义上讲，数理逻辑包括四论、两演算从广义上讲，数理逻辑包括四论、两演算即集合论、模型论、递归论、证明论和命即集合论、模型论、递归论、证明论和命题演算、谓词演算，但现在提到数理逻辑，题演算、谓词演算，但现在提到数理逻辑，一般是指一般是指命题演算命题演算和和谓词演算谓词演算。本书课程只。本书课程只研究这两个演算。研究这两个演算。5/19/2022-v数理逻辑与计算机学、控制论、人工智能的数理逻辑与计算机学、控制论、人工智能的相互渗透推动了其自身的发展，模糊逻辑、相互渗透推动了其自身的发展，模糊逻辑、概
13、率逻辑、归纳逻辑、时态逻辑等都是目前概率逻辑、归纳逻辑、时态逻辑等都是目前比较热门的研究领域。比较热门的研究领域。5/19/2022- n1.1 命题命题表示方法表示方法(Proposition and Its Expression)n1.2 逻辑联结词逻辑联结词(Logical Connectives)n1.3 命题公式与翻译命题公式与翻译(ormula & Its Translation)Truth Tables and Prepositional Equivalences5/19/2022-蕴含蕴含Tautology and Implication Inference Theory 5/
14、19/2022-n1.1.1 命题命题n1.1.2 命题的表示方法命题的表示方法n1.1.3 命题的分类命题的分类5/19/2022- 1.1.1 命题命题（Proposition) 数 理 逻 辑 研 究 的 中 心 问 题 是数 理 逻 辑 研 究 的 中 心 问 题 是 推 理推 理（inference),而推理的而推理的前提前提和和结论结论都是表达判断都是表达判断的陈述句，因而表达判断的陈述句构成了推理的的陈述句，因而表达判断的陈述句构成了推理的基本单位基本单位。5/19/2022- 基本概念基本概念 命题：能够判断真假的陈述句。命题：能够判断真假的陈述句。 命题的真值：命题的判断结果
15、。命题的真值只取两命题的真值：命题的判断结果。命题的真值只取两个值个值:真（真（用用T(true)或或1表示表示）、假（）、假（用用F(false)或或0表表示示） 。 真命题：判断为正确的命题，即真值为真的命题。真命题：判断为正确的命题，即真值为真的命题。 假命题：判断为错误的命题，即真值为假的命题。假命题：判断为错误的命题，即真值为假的命题。5/19/2022-因而又可以称命题是具有唯一真值的陈述句。因而又可以称命题是具有唯一真值的陈述句。判断命题的两个步骤判断命题的两个步骤： 1、是否为陈述句；、是否为陈述句； 2、是否有确定的、唯一的真值。、是否有确定的、唯一的真值。 例例：判断下列句
16、子是否为命题。：判断下列句子是否为命题。 (1). 100是自然数。是自然数。 T (2). 太阳从西方升起。太阳从西方升起。 F 5/19/2022-(3). 3+3=8 . F(4). How do you do ? 疑问句，疑问句，不是命题不是命题(5). 明年的十月一日是晴天。明年的十月一日是晴天。是命题，其真值是命题，其真值到到明年十月一日方可知道。明年十月一日方可知道。(6). x+39 不是命题不是命题(7). 我正在说谎。我正在说谎。是悖论是悖论5/19/2022- (8). 1+101=110 二进制中为真，十进制中为假。二进制中为真，十进制中为假。(9). 如果太阳从西方升
17、起，那么如果太阳从西方升起，那么2是奇数是奇数。T(10). 国足能杀入国足能杀入2006世界杯当且仅当世界杯当且仅当2+2=4。F(11). 今天天气多好啊！今天天气多好啊！ 感叹句，感叹句，不是命题不是命题(12). 请你关上门！请你关上门！ 祁使句，不祁使句，不是命题，是命题， (13). 别的星球上有生物。别的星球上有生物。 是命题，客观上能判是命题，客观上能判断真假。断真假。5/19/2022- 说明：说明：（1）只有具有确定真值的陈述句才是命题。）只有具有确定真值的陈述句才是命题。 一切没有判断内容的句子，无所谓一切没有判断内容的句子，无所谓 是非的句子，如是非的句子，如感叹句、祁
18、使句、感叹句、祁使句、 疑问疑问 句等都不是命题。句等都不是命题。（2） 因为因为命题只有两种真值，所以命题只有两种真值，所以“命题命题 逻逻 辑辑”又称又称 “二值逻辑二值逻辑”。5/19/2022- (3) “具有确定真值具有确定真值”是指客观上的具有，与我们是指客观上的具有，与我们 是否知道它的真值是两回事。如上例中是否知道它的真值是两回事。如上例中 的（的（5）和（）和（13）。）。1.1.2 命题的表示方法命题的表示方法 在本书中，用大写英文字母在本书中，用大写英文字母A,B,P,Q或带下标或带下标的字母的字母P1,P2,P3 , ,或数字或数字(1),2, ,等表示命题，等表示命题
19、，称之为命题标识符。称之为命题标识符。 5/19/2022- 例如：例如： P：罗纳尔多是球星。：罗纳尔多是球星。 Q：5是负数。是负数。 P3：明天天气晴。明天天气晴。 (2)：太阳从西方升起。：太阳从西方升起。 皆为符号化的命题，其真值依次为皆为符号化的命题，其真值依次为1、0、1或或0、0。5/19/2022- 命题标识符又有命题常量、命题变元和原子变元命题标识符又有命题常量、命题变元和原子变元之分。之分。命题常量命题常量：表示确定命题的命题标识符。：表示确定命题的命题标识符。命题变元命题变元：命题标识符如仅是表示任意命题的位置标：命题标识符如仅是表示任意命题的位置标 志，就称为命题变元
20、。志，就称为命题变元。原子变元原子变元：当命题变元表示原子命题时，该变元称为：当命题变元表示原子命题时，该变元称为 原子变元。原子变元。命题变元也用命题变元也用A,B,P,Q,P1,P2,P3 , , 表示。表示。5/19/2022- 1.1.3 命题的分类：命题的分类：简单简单/原子命题：原子命题：不能分解为更简单的陈述语不能分解为更简单的陈述语句的命题句的命题(如上例中的命题如上例中的命题)。复合命题：复合命题：由简单命题通过由简单命题通过联结词联结词联结而成联结而成的命题。的命题。联结词就是复合命题中的运算符。联结词就是复合命题中的运算符。 5/19/2022-注意注意：（1）一个符号）
21、一个符号(如如P), 它表示的是命题常量还是它表示的是命题常量还是命题变元，一般由上下文来确定。命题变元，一般由上下文来确定。（2）命题变元可以表示任意命题，它不能确定）命题变元可以表示任意命题，它不能确定真值，故命题变元不是命题。这与真值，故命题变元不是命题。这与“变数变数x不不是数是数”是一样的道理。是一样的道理。5/19/2022-小结：小结：本节主要介绍了命题、命题的真值、本节主要介绍了命题、命题的真值、原子命题、复合命题、命题标识符、命题常量、原子命题、复合命题、命题标识符、命题常量、命题变元和原子变元的概念。命题变元和原子变元的概念。 重点理解和掌握命题、命题变元、简单（原子）重点
22、理解和掌握命题、命题变元、简单（原子）命题、复合命题四个概念。命题、复合命题四个概念。 作业：作业：P2 1,25/19/2022- 1.2 逻辑联结词逻辑联结词(Logical Connectives) 1.2.1 否定联结词否定联结词(Negation) 1.2.2 合取联结词合取联结词(Conjunction)1.2.3 析取联结词析取联结词(Disjunction)1.2.4 条件联结词条件联结词(蕴涵联结词蕴涵联结词Conditional)1.2.5 双条件联结双条件联结(等值联结词等值联结词Biconditional) 5/19/2022- 1.2逻辑联结词逻辑联结词(Logica
23、l Connectives) 在命题逻辑中在命题逻辑中, ,主要研究的是主要研究的是复合命复合命题题, ,而而复合命题复合命题是由原子命题与逻辑联是由原子命题与逻辑联结词组合而成结词组合而成, ,联结词组是复合命题的联结词组是复合命题的重要组成部分重要组成部分. .5/19/2022-1.2.1 否定联结词否定联结词 定义定义1.2.1 设设P为一命题，为一命题， P的否定是一个新的的否定是一个新的复合命题复合命题, 称为称为P的否定式，记作的否定式，记作 “P”读作读作“非非P”. 符号符号“ ” 称为否定联结词。称为否定联结词。 P为真当且为真当且仅当仅当P为假为假.说明说明： “”属于一
24、元属于一元(unary)运算符运算符. 1.2逻辑联结词逻辑联结词(Logical Connectives)5/19/2022- 1.2逻辑联结词逻辑联结词(Logical Connectives)n“”的定义也可用下表来说明的定义也可用下表来说明. 联结词联结词“”的定义真值表的定义真值表 P P01105/19/2022- 1.2逻辑联结词逻辑联结词(Logical Connectives)例例1. P: 天津是一个城市天津是一个城市. Q: 3是偶数是偶数.于是于是: P: 天津不是一个城市天津不是一个城市. Q: 3不是偶数不是偶数.例例2. P:苏州处处清洁苏州处处清洁. Q:这些都
25、是男同学这些都是男同学. P:苏州不处处清洁苏州不处处清洁 (注意注意,不是处处不清洁不是处处不清洁). Q:这些不都是男同学这些不都是男同学.5/19/2022- 1.2逻辑联结词逻辑联结词(Logical Connectives)1.2.2 合取联结词合取联结词(Conjunction )定义定义1.2.2 设设P,Q为二命题，复合命题为二命题，复合命题“P并且并且Q”（或（或“P与与Q”）称为）称为P与与Q的合取式，记作的合取式，记作PQ，符号，符号“” 称为合取联结词称为合取联结词. PQ为真为真当且仅当当且仅当P P和和Q Q同时为真同时为真. . 5/19/2022- 1.2逻辑联
26、结词逻辑联结词(Logical Connectives) 联结词联结词“”的定义真值表的定义真值表PQ P Q 0 00 00 00 01 10 01 10 00 01 11 11 15/19/2022- 1.2逻辑联结词逻辑联结词(Logical Connectives)说明：说明：“” 属于二元属于二元(binary)运算符运算符.合取运算特点合取运算特点：只有参与运算的二命题全为真：只有参与运算的二命题全为真时，运算结果才为真，否则为假。时，运算结果才为真，否则为假。自然语言中的表示自然语言中的表示“并且并且”意思的联结词，如意思的联结词，如“既既又又”、“不但不但而且而且”、“虽然虽然
27、但是但是”、“一一面面一面一面”、 “和和”、 “与与”等都可以等都可以 符号化为符号化为 。5/19/2022- 1.2逻辑联结词逻辑联结词(Logical Connectives)n例例3. 将下列命题符号化将下列命题符号化. (1) 李平既聪明又用功李平既聪明又用功. (2) 李平虽然聪明李平虽然聪明, 但不用功但不用功. (3) 李平不但聪明李平不但聪明,而且用功而且用功. (4) 李平不是不聪明李平不是不聪明,而是不用功而是不用功.解解: 设设 P:李平聪明李平聪明. Q:李平用功李平用功.则则 (1) PQ (2) PQ (3) PQ (4) (P)Q 5/19/2022- 1.2
28、逻辑联结词逻辑联结词(Logical Connectives)注意注意：不要见到不要见到“与与”或或“和和”就使用联结词就使用联结词 ！例如例如: (1)李敏和李华是姐妹。李敏和李华是姐妹。 (2)李敏和张华是朋友。李敏和张华是朋友。 5/19/2022- 1.2逻辑联结词逻辑联结词(Logical Connectives) 例例4. 试生成下列命题的合取试生成下列命题的合取. (1) P: 我们在我们在6-503. Q: 今天是星期二今天是星期二. (2) S：李平在吃饭：李平在吃饭. R：张明在吃饭：张明在吃饭. 解解: (1) PQ :我们在我们在6-503且今天是星期二且今天是星期二.
29、 (2) SR:李平与张明在吃饭李平与张明在吃饭. 5/19/2022- 1.2逻辑联结词逻辑联结词(Logical Connectives) 同之处的不和与语言中与日常.):(, , )2(1).(.(,) 1 (李华和李敏是姐妹如去翻译不能一概用和与不同意义上使用联结词自然语言中有时在各种如上例的命题原子命题生成一个新的甚至互为否定的独立无关的逻辑学中允许两个相互5/19/2022- 1.2逻辑联结词逻辑联结词(Logical Connectives)1.2.3 析取联结词析取联结词(Disjunction)定义定义1.2.3 设设P,Q为二命题，复合命题为二命题，复合命题“P或或Q” 称
30、为称为P与与Q的析取式，记作的析取式，记作PQ ，符号，符号称为称为析取联结词析取联结词. PQ为真当且仅当为真当且仅当 P与与Q中至少有中至少有一个为真一个为真. 5/19/2022- 1.2逻辑联结词逻辑联结词(Logical Connectives) 联结词联结词“”的定义真值表的定义真值表PQ P Q 0 00 00 00 01 11 11 10 01 11 11 11 15/19/2022- 1.2逻辑联结词逻辑联结词(Logical Connectives)说明：说明：“” 属于二元属于二元(binary)运算符运算符.析取运算特点析取运算特点：只有参与运算的二命题全为假：只有参与
31、运算的二命题全为假时，运算结果才为假，否则为真。时，运算结果才为假，否则为真。 由析取联结词的定义可以看出，由析取联结词的定义可以看出， “”与汉与汉语中的联结词语中的联结词“或或”意义相近，但又不完全相同。意义相近，但又不完全相同。在现代汉语中，联结词的在现代汉语中，联结词的“或或”实际上有实际上有“”和和“”之分。之分。5/19/2022- 1.2逻辑联结词逻辑联结词(Logical Connectives)考察下面命题：考察下面命题：（1）小王爱打球或爱跑步。）小王爱打球或爱跑步。（ 设设P：小王爱打球。：小王爱打球。 Q：小王爱跑步。：小王爱跑步。 则上述命题可符号化为：则上述命题可符
32、号化为：P Q（2）林芳学过英语或法语。）林芳学过英语或法语。 （设设P：林芳学过英语林芳学过英语。 Q：林芳学过法语林芳学过法语。 则上述命题可符号化为：则上述命题可符号化为： P Q5/19/2022- 1.2逻辑联结词逻辑联结词(Logical Connectives)（3）派小王或小李中的一人去开会。）派小王或小李中的一人去开会。（） 设设P：派小王去开会。派小王去开会。Q：派小李去开会。派小李去开会。 则上述命题可符号化为：则上述命题可符号化为：(PQ) (PQ)（4）人固有一死，或重于泰山或轻于鸿毛）人固有一死，或重于泰山或轻于鸿毛. (） （5）ab=0, 即即a=0 或或 b=
33、0. （ 由此可见由此可见, “P Q”表示的是表示的是“5/19/2022- 1.2逻辑联结词逻辑联结词(Logical Connectives)注意：注意：当当P和和Q客观上不能同时发生时，客观上不能同时发生时，“P或或Q”可以符号化为可以符号化为“P Q”。例如：小王现在在宿舍或在图书馆。设例如：小王现在在宿舍或在图书馆。设 P：小王现在在宿舍。：小王现在在宿舍。Q：小王现在在图书馆。：小王现在在图书馆。则上述命题可符号化为：则上述命题可符号化为：PQ。5/19/2022- 1.2逻辑联结词逻辑联结词(Logical Connectives)同之处的不或语言中与日常(1) .(2),(:
34、63)P逻辑学中允许联结两个毫无关系的命题自然语言中有时在各种不同意义上使用联结词 或 不能一概用去翻译 如例5/19/2022- 1.2逻辑联结词逻辑联结词(Logical Connectives)1.2.4. 条件联结词条件联结词(蕴涵联结词蕴涵联结词Conditional)定义定义1.2.4 设设P,Q为二命题，复合命题为二命题，复合命题“如果如果P则则Q(若若P则则Q)” 称为称为P与与Q的条件命题的条件命题,记作记作P Q. PQ为假当且仅当为假当且仅当P为真且为真且Q为假为假.称符称符号号“”为条件联结词。并称为条件联结词。并称P为前件，为前件，Q为后为后件件. 5/19/2022
35、- 1.2逻辑联结词逻辑联结词(Logical Connectives) 联结词联结词“”的定义真值表的定义真值表PQP Q0 00 01 10 01 11 11 10 00 01 11 11 15/19/2022- 1.2逻辑联结词逻辑联结词(Logical Connectives) 注：注：（1）PQ表示的基本逻辑关系是表示的基本逻辑关系是,Q是是P的必要的必要条件或条件或P是是Q的充分条件的充分条件. 因此复合命题因此复合命题“只只要要P就就Q”、“因为因为P，所以，所以Q”、“P仅当仅当Q”、“只有只有Q才才P”等都可以符号化为等都可以符号化为 PQ 的形式。的形式。（2） “” 属于
36、二元属于二元(binary)运算运算.5/19/2022- 1.2逻辑联结词逻辑联结词(Logical Connectives)例例5. 将下列命题符号化。将下列命题符号化。 （1 1）天不下雨，则草木枯黄。）天不下雨，则草木枯黄。 P：天下雨。：天下雨。 Q：草木枯黄。：草木枯黄。则原命题可表示为：则原命题可表示为： PQ。 （2）如果小明学日语，小华学英语，则小芳）如果小明学日语，小华学英语，则小芳学德语。学德语。 P：小明学日语：小明学日语. Q：小华学英语：小华学英语. R：小芳学德语：小芳学德语.则原命题可表示为：则原命题可表示为：(PQ)R5/19/2022- 1.2逻辑联结词逻辑
37、联结词(Logical Connectives) （3）只要不下雨，我就骑自行车上班。）只要不下雨，我就骑自行车上班。 P：天下雨。：天下雨。Q：我骑自行车上班。：我骑自行车上班。 则原命题可表示为：则原命题可表示为： PQ。 （4）只有不下雨，我才骑自行车上班。）只有不下雨，我才骑自行车上班。 P：天下雨。：天下雨。Q：我骑自行车上班。：我骑自行车上班。 则原命题可表示为：则原命题可表示为： Q P 。5/19/2022- 1.2逻辑联结词逻辑联结词(Logical Connectives) （5）如果如果 2+2=4, 则则太阳从东方升起太阳从东方升起。 (PQ, T) P Q 如果如果
38、2+2=4, 则则太阳从西方升起太阳从西方升起。 (PR, F) R 如果如果 2+24, 则太阳从东方升起。则太阳从东方升起。 (PQ , T) 如果如果 2+2 4, 则太阳从西方升起。则太阳从西方升起。 (PR, T)5/19/2022- 1.2逻辑联结词逻辑联结词(Logical Connectives) 注意注意: (1)与自然语言的不同：与自然语言的不同：前件与后件可以没有任前件与后件可以没有任何内在联系！何内在联系！ (2) 在数学中，在数学中，“若若P则则Q”往往表示前件往往表示前件P为真，为真，则后件则后件Q为真的推理关系为真的推理关系. 但数理逻辑中，当前但数理逻辑中，当前
39、件件P为假时，为假时， PQ的真值为真。的真值为真。5/19/2022- 1.2逻辑联结词逻辑联结词(Logical Connectives)1.2.5 双条件联结双条件联结(等值联结词等值联结词Biconditional) 定义定义1.2.5 设设P,Q为二命题，复合命题为二命题，复合命题“P当且仅当且仅当当Q” 称为称为P与与Q的双条件命题，记作的双条件命题，记作P iff Q或或 PQ，符号，符号称为双条件（等值）联结词。称为双条件（等值）联结词。 PQ为真当且仅当为真当且仅当P，Q真值相同。真值相同。 5/19/2022- 1.2逻辑联结词逻辑联结词(Logical Connectiv
40、es) 联结词联结词“”的定义真值表的定义真值表PQP Q0 00 01 10 01 10 01 10 00 01 11 11 15/19/2022- 1.2逻辑联结词逻辑联结词(Logical Connectives)注：注：（1）P仅当仅当Q 可译为可译为PQ P当当Q 可译为可译为QP P当且仅当当且仅当Q 译为译为PQ （2）“”属于二元属于二元(binary)运算符。运算符。 (3) 双条件命题双条件命题PQ所表达的逻辑关系是所表达的逻辑关系是, P与与Q互为充分必要条件互为充分必要条件,相当于相当于(PQ)(QP). 只要只要P与与Q的真值同为的真值同为1或同为或同为0, PQ的真
41、值就的真值就为为1, 否则否则PQ的真值为的真值为0. 双条件联结词连接的双条件联结词连接的两个命题之间可以没有因果关系。两个命题之间可以没有因果关系。5/19/2022- 1.2逻辑联结词逻辑联结词(Logical Connectives)例例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)5/
42、19/2022- 1.2逻辑联结词逻辑联结词(Logical Connectives)约约 定定:1. 运算次序优先级：运算次序优先级：， ， ，. 2. 相同的运算符按从左至右次序计算，否相同的运算符按从左至右次序计算，否则要加上括号。则要加上括号。 3.最外层圆括号可省去。最外层圆括号可省去。 小结小结: 本节介绍了五种联结词本节介绍了五种联结词(， ， ，),重点是理解和掌握重点是理解和掌握五种联结词的内涵及它五种联结词的内涵及它们与自然语言中相应联结词的不同之处们与自然语言中相应联结词的不同之处.5/19/2022- 1.2逻辑联结词逻辑联结词(Logical Connectives)
43、作业作业: 1. P5 2 2. 预习预习 1.3, 1.4思考题思考题: 1. 何谓合式公式何谓合式公式? 2. 复合命题符号化的基本步骤是什么复合命题符号化的基本步骤是什么? 3.何谓真值表何谓真值表? 4. 两个命题公式等价的涵义是什么两个命题公式等价的涵义是什么? 5.两个等价的命题公式其真值表有何关系两个等价的命题公式其真值表有何关系?5/19/2022- 1.3命题公式与翻译命题公式与翻译1.3 命题公式与翻译命题公式与翻译1.3.1 命题公式命题公式1.3.2 复合命题的符号化复合命题的符号化(翻译翻译)5/19/2022-1.3命题公式与翻译命题公式与翻译(ormula & I
44、ts Translation)1.3.1 命题合式公式命题合式公式(Well-formed formula)(wff)定义定义1.3.1: :单个命题变元和命题常量称为单个命题变元和命题常量称为原子公原子公式式。命题合式公式命题合式公式是由命题变元、是由命题变元、命题常量、命题常量、联结词联结词和圆括号按一定的逻辑关系联结起来的符号串。和圆括号按一定的逻辑关系联结起来的符号串。我们以如下递归的形式来定义合式公式：我们以如下递归的形式来定义合式公式：5/19/2022- 1.3命题公式与翻译命题公式与翻译定义定义1.3.2：(1)(1)原子公式是原子公式是合式合式公式公式( (wff)。 （2）
45、若）若A是合式公式，则是合式公式，则(A)也是合式公式。也是合式公式。 （3）若）若A，B是合式公式，则是合式公式，则(AB)，(AB)，(AB)，(AB)也是合式公式。也是合式公式。 （4）当且仅当当且仅当有限次地应用有限次地应用(1)(3)所得到的包含所得到的包含原子公式、原子公式、联结词和括号的符号串是合式公式。联结词和括号的符号串是合式公式。5/19/2022- 1.3命题公式与翻译命题公式与翻译注注: (1)合式公式也称为合式公式也称为命题公式命题公式，并简称为，并简称为公式。公式。 (2)命题公式命题公式一般一般不是不是命题命题,仅当仅当公式中的公式中的命题变命题变元元用用确定的命
46、题确定的命题代入时代入时,才得到一个命题才得到一个命题.其真值其真值依赖于代换变元的那些命题的真值依赖于代换变元的那些命题的真值.5/19/2022-1.3命题公式与翻译命题公式与翻译例例1：指出：指出(P(P Q)是否是命题公式是否是命题公式(wff)，如果是，则具体说明。如果是，则具体说明。解：解： P是是wff 由由(1) Q是是wff 由由(1) P Q是是wff 由由(2) (P(P Q) 由由(2) 5/19/2022-1.3命题公式与翻译命题公式与翻译例例2: (P Q) , (R S) Q , P，(P)等均等均为合式公式，而为合式公式，而PQ S , (P W) Q)等不等不
47、是合式公式。是合式公式。5/19/2022- 1.3命题公式与翻译命题公式与翻译n1.3.2 复合命题的符号化复合命题的符号化(翻译翻译)n有了命题演算的合式公式的概念有了命题演算的合式公式的概念,我们可以把我们可以把自然语言中的有些语句自然语言中的有些语句(复合命题复合命题),翻译成数翻译成数理逻辑中的符号形式理逻辑中的符号形式.基本步骤如下基本步骤如下:n(1) 分析出各简单命题分析出各简单命题,将它们符号化将它们符号化;n(2) 使用合适的联结词使用合适的联结词,把简单命题逐个的联把简单命题逐个的联结起来结起来,组成复合命题的符号化表示组成复合命题的符号化表示.5/19/2022- 1.
48、3命题公式与翻译命题公式与翻译n例例3：1) 我今天进城，除非下雨。我今天进城，除非下雨。n2) 仅当你走我将留下。仅当你走我将留下。n3) 假如上午不下雨，我去看电影，否则就在家里假如上午不下雨，我去看电影，否则就在家里n 读书或看报。读书或看报。n4)除非你努力，否则你将失败。除非你努力，否则你将失败。n5)一个人起初说：一个人起初说：“占据空间的、有质量的而且不占据空间的、有质量的而且不断变化的叫做物质断变化的叫做物质”；后来他改说，；后来他改说，“占据空间的占据空间的有质量的叫做物质，而物质是不断变化的。有质量的叫做物质，而物质是不断变化的。”问他问他前后主张的差异在什么地方，试以命题
49、形式进行分前后主张的差异在什么地方，试以命题形式进行分析析。5/19/2022- 1.3命题公式与翻译命题公式与翻译n例例4：P6 例例1.3.3 ，例，例1.3.4(5) ，例，例1.3.5n小结小结：本节介了命题公式的概念及复合命题的：本节介了命题公式的概念及复合命题的符号化符号化.重点是理解命题公式的递归定义重点是理解命题公式的递归定义,掌握掌握复合命题的符号化方法复合命题的符号化方法.n作业作业: P7: 25/19/2022- 1.4.1 真值表真值表(Truth Table)1.4.2 等价公式等价公式()1.4.1 真值表真值表 前面在定义联结词时前面在定义联结词时,曾经使用过真
50、值表曾经使用过真值表,下面下面给出真值表的定义给出真值表的定义.5/19/2022- 定义定义1.4.1 (对公式的赋值或解释对公式的赋值或解释)设设P1 , P2 ,Pn是出现在公式是出现在公式A中的全部的命题变元中的全部的命题变元, 给给P1 , P2 ,Pn各指定一个真值，称为对各指定一个真值，称为对A的一个的一个赋值赋值或或解释解释。若指定的一组值使。若指定的一组值使A的真值为真的真值为真(假假), 称这组值为称这组值为A的的成真成真(假假)赋值赋值.5/19/2022- 例如例如:对公式对公式(PQ)R，赋值，赋值011(即令即令P=0，Q=1， R=1) 为为(PQ)R的成真赋值的
