离散数学及应用讲课稿课件

离散数学及应用离散数学及应用引言（续）

故计算机各分支领域中的理论问题，交错地使用着现代数学的各种不同的论题。因为计算机系统从本质上说是一种离散性的结构，它的许多性质可以在有限数学系统的框架中来理解，从中选出一些必要而且是基本的主干论题称为离散数学。因此，离散数学是随着计算机科学的发展而逐步建立的，它形成于七十年代初期，是一门新兴的工具性学科。引言（续）引言（续）离散数学是现代数学的一个重要分支，是计算机科学与技术的理论基础，是计算机科学与技术专业的核心、骨干课程。它以研究离散量的结构和相互间的关系为主要目标，其研究对象一般是有限个或可数个元素，因此它充分描述了计算机科学离散性的特点。引言（续）引言（续）二、该课程的主要内容：离散数学课程的主要内容可以分为四个部分：数理逻辑，包括命题逻辑和谓词逻辑。(教材的第一、二章)

集合论，包括集合、关系和函数。（教材的第三、四章）代数系统，包括代数系统的一般概念，几类典型的代数系统和格。（教材的第五、六章）图论，包括图的基本概念，几种特殊的图。(教材的第七章)引言（续）二、该课程的主要内容：引言（续）三、学习该课程的目的：

1.为学习计算机后继课程，如数据结构、编译理论、操作系统、数据库原理、形式语言及自动机、软件工程与方法学、计算机网络和人工智能、高级程序设计语言等，提供必要的数学基础；为阅读计算机文章作充分的数学准备。引言（续）三、学习该课程的目的：引言（续）数理逻辑：人工智能，数据库，形式语言及自动机，高级程序设计语言。集合论：信息结构与检索，数据结构。

图论：可计算性理论，计算机网络,数据结构。代数结构：开关理论，逻辑设计和程序理论，语法分析。

2.通过学习离散数学，可以培养和提高自己的抽象思维和逻辑推理能力，获得解决实际问题能力，为以后的软、硬件学习和研究开发工作，打下坚实的数学基础。引言（续）数理逻辑：人工智能，数据库，形式语言及自动机，引言（续）四、教学要求：

通过该课程的学习，学生应当了解并掌握计算机科学中普遍采用的离散数学中的一些基本概念、基本思想、基本方法。五、自学要求：

由于课时少，内容多且抽象，故要求课前预习，课后复习；认真完成习题，通过做课后习题，来加深对该课程中的一些基本概念的理解，逐步提高自己的抽象思维和逻辑推理能力。作业每星期一交，作为平时成绩。引言（续）四、教学要求：引言（续）六、参考教材：1.《离散数学及其应用》魏雪丽等编著机械工业出版社2.《离散数学》左孝凌等著上海科技文献出版社3.《离散数学—理论·分析·题解》左孝凌等著上海科技文献出版社4.《DiscreteMathematicsandItsApplications》（英文版）(美)KennethH.Rosen著机械工业出版社引言（续）六、参考教材：引言（续）七、考核方式：期末考试成绩占70%,平时成绩占30%.引言（续）七、考核方式：第一部分数理逻辑（MathematicalLogic)逻辑：是研究推理的科学。公元前四世纪由希腊的哲学家亚里斯多德首创。作为一门独立科学，十七世纪，德国的莱布尼兹(Leibniz)给逻辑学引进了符号,又称为数理逻辑(或符号逻辑)。逻辑可分为：1.形式逻辑（通过数学方法）数理逻辑

2.辩证逻辑指引进一套符号体系的方法。

辩证逻辑是研究反映客观世界辩证发展过程的人类思维的形态的。第一部分数理逻辑（MathematicalLogic)第一部分数理逻辑（MathematicalLogic)形式逻辑是研究思维的形式结构和规律的科学，它撇开具体的、个别的思维内容，从形式结构方面研究概念、判断和推理及其正确联系的规律。数理逻辑是用数学方法研究推理的形式结构和推理的规律的数学学科。它的创始人Leibniz，为了实现把推理变为演算的想法，把数学引入了形式逻辑。其后，又经多人努力，逐渐使得数理逻辑成为一门专门的学科。上个世纪30年代以后，数理逻辑进入一个崭新的发展阶段，逻辑学不仅与数学结合，还与计算机科学等密切关联。第一部分数理逻辑（MathematicalLogic)第一部分数理逻辑（MathematicalLogic)1931年Godel不完全性定理的提出，以及递归函数可计算性的引入，促使了1936年Turing机的产生，十年后，第一台电子计算机问世。从广义上讲，数理逻辑包括四论、两演算——即集合论、模型论、递归论、证明论和命题演算、谓词演算，但现在提到数理逻辑，一般是指命题演算和谓词演算。本书课程只研究这两个演算。第一部分数理逻辑（MathematicalLogic)第一部分数理逻辑（MathematicalLogic)数理逻辑与计算机学、控制论、人工智能的相互渗透推动了其自身的发展，模糊逻辑、概率逻辑、归纳逻辑、时态逻辑等都是目前比较热门的研究领域。第一部分数理逻辑（MathematicalLogic)第一章命题逻辑（PropositionalLogic）

1.1

命题及其表示方法(PropositionandItsExpression)1.2逻辑联结词(LogicalConnectives)1.3命题公式与翻译(PropositionalFormula&ItsTranslation)1.4真值表与等价公式(TruthTablesandPrepositionalEquivalences)第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）1.5重言式与蕴含式(TautologyandImplication

)1.6其它联结词(OtherConnectives)1.7对偶与范式(Dual&NormalForm)1.8推理理论(InferenceTheory

)第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）1.1命题及其表示方法1.1.1

命题1.1.2命题的表示方法1.1.3命题的分类第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.1命题及其表示方法1.1.1命题（Proposition)

数理逻辑研究的中心问题是推理（inference),而推理的前提和结论都是表达判断的陈述句，因而表达判断的陈述句构成了推理的基本单位。第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.1命题及其表示方法基本概念命题：能够判断真假的陈述句。命题的真值：命题的判断结果。命题的真值只取两个值:真（用T(true)或1表示）、假（用F(false)或0表示）。真命题：判断为正确的命题，即真值为真的命题。假命题：判断为错误的命题，即真值为假的命题。第一章命题逻辑（PropositionalLogic）因而又可以称命题是具有唯一真值的陈述句。判断命题的两个步骤：1、是否为陈述句；2、是否有确定的、唯一的真值。

例：判断下列句子是否为命题。(1).100是自然数。T(2).太阳从西方升起。F第一章命题逻辑（PropositionalLogic）

1.1命题及其表示方法因而又可以称命题是具有唯一真值的陈述句。第一章命题逻辑（第一章命题逻辑（PropositionalLogic）

1.1命题及其表示方法(3).3+3=8.F(4).Howdoyoudo?疑问句，不是命题(5).明年的十月一日是晴天。是命题，其真值到明年十月一日方可知道。(6).x+3>9不是命题(7).我正在说谎。是悖论第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.1命题及其表示方法(8).1+101=110二进制中为真，十进制中为假。(9).如果太阳从西方升起，那么2是奇数。T(10).国足能杀入2006世界杯当且仅当2+2=4。F(11).今天天气多好啊！感叹句，不是命题(12).请你关上门！祁使句，不是命题，(13).别的星球上有生物。是命题，客观上能判断真假。第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.1命题及其表示方法说明：（1）只有具有确定真值的陈述句才是命题。一切没有判断内容的句子，无所谓是非的句子，如感叹句、祁使句、疑问句等都不是命题。（2）因为命题只有两种真值，所以“命题逻辑”又称“二值逻辑”。第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.1命题及其表示方法(3)“具有确定真值”是指客观上的具有，与我们是否知道它的真值是两回事。如上例中的（5）和（13）。1.1.2命题的表示方法在本书中，用大写英文字母A,B,…,P,Q或带下标的字母P1,P2,P3,

…,或数字(1),[2],…,等表示命题，称之为命题标识符。

第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.1命题及其表示方法例如：P：罗纳尔多是球星。Q：5是负数。P3：明天天气晴。(2)：太阳从西方升起。皆为符号化的命题，其真值依次为1、0、1或0、0。第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.1命题及其表示方法命题标识符又有命题常量、命题变元和原子变元之分。命题常量：表示确定命题的命题标识符。命题变元：命题标识符如仅是表示任意命题的位置标志，就称为命题变元。原子变元：当命题变元表示原子命题时，该变元称为原子变元。命题变元也用A,B,…,P,Q,P1,P2,P3,

…,表示。第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.1命题及其表示方法1.1.3命题的分类：简单/原子命题：不能分解为更简单的陈述语句的命题(如上例中的命题)。复合命题：由简单命题通过联结词联结而成的命题。联结词就是复合命题中的运算符。

第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.1命题及其表示方法注意：（1）一个符号(如P),它表示的是命题常量还是命题变元，一般由上下文来确定。（2）命题变元可以表示任意命题，它不能确定真值，故命题变元不是命题。这与“变数x不是数”是一样的道理。第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.1命题及其表示方法小结：本节主要介绍了命题、命题的真值、原子命题、复合命题、命题标识符、命题常量、命题变元和原子变元的概念。

重点理解和掌握命题、命题变元、简单（原子）命题、复合命题四个概念。作业：P21,2第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.2逻辑联结词(LogicalConnectives)1.2.1否定联结词(Negation)┐1.2.2合取联结词(Conjunction)∧1.2.3析取联结词(Disjunction)∨1.2.4条件联结词(蕴涵联结词Conditional)→1.2.5双条件联结(等值联结词Biconditional)

第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.2逻辑联结词(LogicalConnectives)

在命题逻辑中,主要研究的是复合命题,而复合命题是由原子命题与逻辑联结词组合而成,联结词组是复合命题的重要组成部分.第一章命题逻辑（PropositionalLogic）1.2.1否定联结词┐定义1.2.1

设P为一命题，P的否定是一个新的复合命题,称为P的否定式，记作“┐P”读作“非P”.符号“┐”

称为否定联结词。┐P为真当且仅当P为假.说明：“┐”属于一元(unary)运算符.第一章命题逻辑（PropositionalLogic）

1.2逻辑联结词(LogicalConnectives)1.2.1否定联结词┐第一章命题逻辑（Proposi第一章命题逻辑（PropositionalLogic）

1.2逻辑联结词(LogicalConnectives)“┐”的定义也可用下表来说明.联结词“┐”的定义真值表

P

┐P0110第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.2逻辑联结词(LogicalConnectives)例1.P:天津是一个城市.Q:3是偶数.于是:┐P:天津不是一个城市.

┐Q:3不是偶数.例2.P:苏州处处清洁.Q:这些都是男同学.┐P:苏州不处处清洁(注意,不是处处不清洁).┐Q:这些不都是男同学.第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.2逻辑联结词(LogicalConnectives)1.2.2合取联结词(Conjunction∧

)定义1.2.2设P,Q为二命题，复合命题“P并且Q”（或“P与Q”）称为P与Q的合取式，记作P∧Q，符号“∧”

称为合取联结词.P∧Q为真当且仅当P和Q同时为真.

第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.2逻辑联结词(LogicalConnectives)

联结词“∧”的定义真值表PQ

P

Q

000010100111第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.2逻辑联结词(LogicalConnectives)说明：“∧”

属于二元(binary)运算符.合取运算特点：只有参与运算的二命题全为真时，运算结果才为真，否则为假。自然语言中的表示“并且”意思的联结词，如“既…又…”、“不但…而且…”、“虽然…但是…”、“一面…一面…”、“…和…”、“…与…”等都可以符号化为∧。第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.2逻辑联结词(LogicalConnectives)例3.将下列命题符号化.(1)李平既聪明又用功.(2)李平虽然聪明,但不用功.(3)李平不但聪明,而且用功.(4)李平不是不聪明,而是不用功.解:设P:李平聪明.Q:李平用功.则(1)P∧Q(2)P∧┐Q(3)P∧Q(4)┐(┐P)∧┐Q第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.2逻辑联结词(LogicalConnectives)注意：不要见到“与”或“和”就使用联结词∧！例如:(1)李敏和李华是姐妹。(2)李敏和张华是朋友。

第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.2逻辑联结词(LogicalConnectives)例4.试生成下列命题的合取.(1)P:我们在6-503.Q:今天是星期二.

(2)S：李平在吃饭.R：张明在吃饭.解:(1)P∧Q:我们在6-503且今天是星期二.(2)S∧R:李平与张明在吃饭.

第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.2逻辑联结词(LogicalConnectives)

第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.2逻辑联结词(LogicalConnectives)1.2.3析取联结词(Disjunction)∨定义1.2.3设P,Q为二命题，复合命题“P或Q”称为P与Q的析取式，记作P∨Q，符号∨称为析取联结词.P∨Q为真当且仅当P与Q中至少有一个为真.

第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.2逻辑联结词(LogicalConnectives)

联结词“∨”的定义真值表PQP

Q 000011101111第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.2逻辑联结词(LogicalConnectives)说明：“∨”

属于二元(binary)运算符.析取运算特点：只有参与运算的二命题全为假时，运算结果才为假，否则为真。由析取联结词的定义可以看出，“∨”与汉语中的联结词“或”意义相近，但又不完全相同。在现代汉语中，联结词的“或”实际上有“可兼或”和“排斥或”之分。第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.2逻辑联结词(LogicalConnectives)考察下面命题：（1）小王爱打球或爱跑步。（可兼或）

设P：小王爱打球。Q：小王爱跑步。则上述命题可符号化为：P∨Q（2）林芳学过英语或法语。

（可兼或）设P：林芳学过英语。Q：林芳学过法语。则上述命题可符号化为：P∨Q第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.2逻辑联结词(LogicalConnectives)（3）派小王或小李中的一人去开会。（排斥或）设P：派小王去开会。Q：派小李去开会。则上述命题可符号化为：(P∧┐Q)∨(┐P∧Q)（4）人固有一死，或重于泰山或轻于鸿毛.

(排斥或）（5）ab=0,即a=0或b=0.

（可兼或）由此可见,“P∨Q”表示的是“可兼或”.第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.2逻辑联结词(LogicalConnectives)注意：当P和Q客观上不能同时发生时，“P或Q”可以符号化为“P∨Q”。例如：小王现在在宿舍或在图书馆。设P：小王现在在宿舍。Q：小王现在在图书馆。则上述命题可符号化为：P∨Q。第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.2逻辑联结词(LogicalConnectives)第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.2逻辑联结词(LogicalConnectives)1.2.4.条件联结词(蕴涵联结词Conditional)→定义1.2.4设P,Q为二命题，复合命题“如果P则Q(若P则Q)”称为P与Q的条件命题,记作P

Q.P

Q为假当且仅当P为真且Q为假.称符号“”为条件联结词。并称P为前件，Q为后件.

第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.2逻辑联结词(LogicalConnectives)

联结词“

”的定义真值表PQP→

Q001011100111第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.2逻辑联结词(LogicalConnectives)注：（1）P

Q表示的基本逻辑关系是,Q是P的必要条件或P是Q的充分条件.

因此复合命题“只要P就Q”、“因为P，所以Q”、“P仅当Q”、“只有Q才P”等都可以符号化为

P

Q的形式。（2）

“”

属于二元(binary)运算.第一章命题逻辑（PropositionalLogic）第一章命题逻辑（ProPositionalLogic）

1.2逻辑联结词(LogicalConnectives)例5.将下列命题符号化。（1）天不下雨，则草木枯黄。

P：天下雨。Q：草木枯黄。则原命题可表示为：┐P→Q。（2）如果小明学日语，小华学英语，则小芳学德语。P：小明学日语.Q：小华学英语.R：小芳学德语.则原命题可表示为：(P∧Q)→R第一章命题逻辑（ProPositionalLogic）第一章命题逻辑（PropositionalLogic）

1.2逻辑联结词(LogicalConnectives)（3）只要不下雨，我就骑自行车上班。P：天下雨。Q：我骑自行车上班。则原命题可表示为：┐P→Q。（4）只有不下雨，我才骑自行车上班。P：天下雨。Q：我骑自行车上班。则原命题可表示为：

Q

→┐P。第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.2逻辑联结词(LogicalConnectives)

（5）如果2+2=4,则太阳从东方升起。(P→Q,T)PQ

如果2+2=4,则太阳从西方升起。(P→R,F)R

如果2+2≠4,则太阳从东方升起。(┐P→Q,T)

如果2+2≠4,则太阳从西方升起。(┐P→R,T)第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.2逻辑联结词(LogicalConnectives)

注意:

(1)与自然语言的不同：前件与后件可以没有任何内在联系！(2)在数学中，“若P则Q”往往表示前件P为真，则后件Q为真的推理关系.但数理逻辑中，当前件P为假时，P→Q的真值为真。第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.2逻辑联结词(LogicalConnectives)1.2.5双条件联结(等值联结词Biconditional)

定义1.2.5设P,Q为二命题，复合命题“P当且仅当Q”称为P与Q的双条件命题，记作PiffQ或P

Q，符号

称为双条件（等值）联结词。P

Q为真当且仅当P，Q真值相同。

第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.2逻辑联结词(LogicalConnectives)联结词“

”的定义真值表PQP

Q001010100111第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.2逻辑联结词(LogicalConnectives)注：（1）P仅当Q可译为P→QP当Q可译为Q→PP当且仅当Q译为P

Q

（2）“”属于二元(binary)运算符。

(3)双条件命题P

Q所表达的逻辑关系是,P与Q互为充分必要条件,相当于(P

Q)∧(Q

P).只要P与Q的真值同为1或同为0,P

Q的真值就为1,否则P

Q的真值为0.双条件联结词连接的两个命题之间可以没有因果关系。第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.2逻辑联结词(LogicalConnectives)例6.分析下列命题的真值.(1)2+2=4当且仅当3是奇数.(P

Q)P：2+2=4.Q：3是奇数.

(2)2+2=4当且仅当3不是奇数.(P

┐Q)(3)2+2≠4当且仅当3是奇数.(┐P

Q)(4)2+2≠4当且仅当3不是奇数.(┐P

┐Q)第一章命题逻辑（PropositionalLogic）第一章命题逻辑（ProPositionalLogic）

1.2逻辑联结词(LogicalConnectives)约定:1.运算次序优先级：┐，

，

，→，.

2.相同的运算符按从左至右次序计算，否则要加上括号。3.最外层圆括号可省去。

小结:本节介绍了五种联结词(┐，

，

，→，),重点是理解和掌握五种联结词的内涵及它们与自然语言中相应联结词的不同之处.第一章命题逻辑（ProPositionalLogic）第一章命题逻辑（PropositionalLogic）

1.2逻辑联结词(LogicalConnectives)作业:1.P522.预习1.3,1.4思考题:1.何谓合式公式?2.复合命题符号化的基本步骤是什么?3.何谓真值表?4.两个命题公式等价的涵义是什么?5.两个等价的命题公式其真值表有何关系?第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.3命题公式与翻译1.3命题公式与翻译1.3.1命题公式1.3.2复合命题的符号化(翻译)第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.3命题公式与翻译(PropositionalFormula&ItsTranslation)1.3.1命题合式公式(Well-formedformula)(wff)定义1.3.1:单个命题变元和命题常量称为原子公式。命题合式公式是由命题变元、命题常量、联结词和圆括号按一定的逻辑关系联结起来的符号串。我们以如下递归的形式来定义合式公式：第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.3命题公式与翻译定义1.3.2：(1)原子公式是合式公式(wff)。（2）若A是合式公式，则(┐A)也是合式公式。（3）若A，B是合式公式，则(A∧B)，(A∨B)，(A

B)，(A

B)也是合式公式。（4）当且仅当有限次地应用(1)~(3)所得到的包含原子公式、联结词和括号的符号串是合式公式。第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.3命题公式与翻译注:

(1)合式公式也称为命题公式，并简称为公式。(2)命题公式一般不是命题,仅当公式中的命题变元用确定的命题代入时,才得到一个命题.其真值依赖于代换变元的那些命题的真值.第一章命题逻辑（PropositionalLogic）第一章命题逻辑（ProPositionalLogic）1.3命题公式与翻译例1：指出(P→(P

Q))是否是命题公式(wff)，如果是，则具体说明。解：①P是wff由(1)②Q是wff由(1)③P

Q是wff由(2)①②④(P→(P

Q))由(2)①③第一章命题逻辑（ProPositionalLogic）第一章命题逻辑（ProPositionalLogic）1.3命题公式与翻译例2:(P

Q),(R∧S)∨┐Q,P，(┐P)等均为合式公式，而PQ∨S,(P

W)∧Q)等不是合式公式。第一章命题逻辑（ProPositionalLogic）第一章命题逻辑（PropositionalLogic）

1.3命题公式与翻译1.3.2复合命题的符号化(翻译)有了命题演算的合式公式的概念,我们可以把自然语言中的有些语句(复合命题),翻译成数理逻辑中的符号形式.基本步骤如下:(1)分析出各简单命题,将它们符号化;(2)使用合适的联结词,把简单命题逐个的联结起来,组成复合命题的符号化表示.第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.3命题公式与翻译例3：1)我今天进城，除非下雨。2)仅当你走我将留下。3)假如上午不下雨，我去看电影，否则就在家里读书或看报。4)除非你努力，否则你将失败。5)一个人起初说：“占据空间的、有质量的而且不断变化的叫做物质”；后来他改说，“占据空间的有质量的叫做物质，而物质是不断变化的。”问他前后主张的差异在什么地方，试以命题形式进行分析。第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.3命题公式与翻译例4：P6例1.3.3，例1.3.4(5)，例1.3.5小结：本节介了命题公式的概念及复合命题的符号化.重点是理解命题公式的递归定义,掌握复合命题的符号化方法.作业:P7:2第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.4真值表与等价公式1.4.1真值表(TruthTable)1.4.2等价公式(ProPositionalEquivalences)1.4.1真值表前面在定义联结词时,曾经使用过真值表,下面给出真值表的定义.第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.4真值表与等价公式定义1.4.1(对公式的赋值或解释)设P1,P2,…,Pn是出现在公式A中的全部的命题变元,给P1,P2,…,Pn各指定一个真值，称为对A的一个赋值或解释。若指定的一组值使A的真值为真(假),称这组值为A的成真(假)赋值.第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.4真值表与等价公式例如:对公式(P

Q)∧R，赋值011(即令P=0，Q=1，R=1)为(P

Q)∧R的成真赋值;另一组赋值010为(P

Q)∧R的成假赋值；还有000，001，111……第一章命题逻辑（PropositionalLogic）第一章命题逻辑（ProPositionalLogic）

1.4真值表与等价公式考虑：含有n个命题变元的公式共有多少组不同的赋值？定义1.4.2(真值表)在命题公式A中,对于命题变元的每一组赋值和由它们所确定的命题公式A的真值列成表，称做命题公式A的真值表。第一章命题逻辑（ProPositionalLogic）第一章命题逻辑（PropositionalLogic）

1.4真值表与等价公式对公式A构造真值表的具体步骤为：（1）找出公式中所有命题变元P1,P2,…,Pn,列出全部的2n组赋值。（2）按从小到大的顺序列出对命题变元P1,P2,…,Pn,的全部2n组赋值。（3）对应各组赋值计算出公式A的真值，并将其列在对应赋值的后面。第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.4真值表与等价公式例1.

给出┐(P

Q)

(┐P

┐Q)的真值表：PQP

Q┐(P

Q)┐P

┐Q┐(P

Q)

(┐P

┐Q)00011011第一章命题逻辑（PropositionalLogic）第一章命题逻辑（ProPositionalLogic）

1.4真值表与等价公式例1.给出┐(P

Q)

(┐P

┐Q)的真值表：PQP

Q┐(P

Q)┐P

┐Q┐(P

Q)

(┐P

┐Q)000111010111100111111001第一章命题逻辑（ProPositionalLogic）第一章命题逻辑（ProPositionalLogic）

1.4真值表与等价公式例2：构造公式(P

Q)∧R的真值表。PQRP

Q(P

Q)∧R000001010011100101110111第一章命题逻辑（ProPositionalLogic）第一章命题逻辑（PropositionalLogic）

1.4真值表与等价公式例2：构造公式(P

Q)∧R的真值表。PQRP

Q(P

Q)∧R0001000111010100111110000101001101011111第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.4真值表与等价公式练习1：构造公式(P

Q)

(┐Q

┐P)真值表。PQ┐P┐QP

Q┐Q

┐P(P

Q)

(┐Q

┐P)00011011第一章命题逻辑（PropositionalLogic）第一章命题逻辑（ProPositionalLogic）

1.4真值表与等价公式练习1：构造公式(P

Q)

(┐Q

┐P)真值表。PQ┐P┐QP

Q┐Q

┐P(P

Q)

(┐Q

┐P)0011111011011110010011100111第一章命题逻辑（ProPositionalLogic）第一章命题逻辑（PropositionalLogic）

1.4真值表与等价公式PQ(P

Q)┐(P

Q)┐(P

Q)∧Q00011011练习2：构造公式┐(P

Q)∧Q真值表。第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.4真值表与等价公式PQ(P

Q)┐(P

Q)┐(P

Q)∧Q00100011001001011100练习2：构造公式┐(P

Q)∧Q真值表。第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.4真值表与等价公式1.4.2等价公式给定n个命题变元,按合式公式的形成规则可以形成无数多个命题公式,但这些无穷尽的命题公式中，有些具有相同的真值表。考虑：由n个命题变元能生成???种真值(表)不同的命题公式？第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.4真值表与等价公式定义1.4.3:给定两个命题公式A和B，设P1,P2,…,Pn为出现于A和B中的所有原子变元,若给P1,P2,…,Pn任一组真值指派,A和B的真值都相同,则称A和B是等价的或逻辑相等.记作A

B。第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.4真值表与等价公式注:(1)“

”不是逻辑联结词.(2)命题公式之间的逻辑相等关系具有：自反性：A

A；对称性：若A

B，则B

A；传递性：若A

B且B

C，则A

C。第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.4真值表与等价公式证明公式等价的方法：1.真值表法2.等值演算法1.真值表法

例1.┐(P

Q)

(┐P

┐Q)见真值表例题1.第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.4真值表与等价公式例2.证明:P

Q

(P→Q)

(Q→P)PQP

QQ→PP→Q(P→Q)

(Q→P)00011011第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.4真值表与等价公式例2.证明:P

Q

(P→Q)

(Q→P)PQP

QQ→PP→Q(P→Q)

(Q→P)001111010010100100111111第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.4真值表与等价公式例3：判断公式P(QR)、(P∧Q)R是否等价。PQRP∧QQ

RP(Q

R)(P∧Q)

R0000100101010000110110001101011101011111第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.4真值表与等价公式PQRP∧QQ

RP(Q

R)(P∧Q)

R00001110010111010001101101111000111101011111010001111111例3：判断公式P(QR)、(P∧Q)R是否等价。第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.4真值表与等价公式

由真值表可知，两个公式为等价式。2.等值演算法(EquivalentCalculation)

等值演算中使用的一条重要规则：置换规则定义1.4.4(子公式)：如果X是wffA的一部分,且X本身也是wff，则称X是A的子公式。例如,P

(PQ)为Q(P

(PQ))的子公式。第一章命题逻辑（PropositionalLogic）第一章命题逻辑（ProPositionalLogic）

1.4真值表与等价公式定理1.4.1(置换定理AxiomofrePlacement)设X是wffA的子wff，若X

Y，则若将A中的X用Y来置换，所得公式B与A等价，即A

B。证：因为对变元的任一指派,X与Y真值相同，所以Y取代X后，公式B与公式A对变元的任一指派真值也相同,所以A

B。第一章命题逻辑（ProPositionalLogic）第一章命题逻辑（PropositionalLogic）

1.4真值表与等价公式注:满足定理1.4.1的条件的置换称为等价置换(或等价代换).定义1.4.5(等值演算)：根据已知的等价公式,推演出另外一些等价公式的过程称为等值演算.第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.4真值表与等价公式常用的等价式：

1.双重否定律：

┐┐P

P2.结合律：(P

Q)RP

(QR)(P

Q)RP

(QR)(P

Q)RP

(QR)3.交换律:P

Q

Q

PP

Q

Q

PP

Q

Q

P4.分配律:P

(QR)

(P

Q)(PR)P

(QR)

(P

Q)(PR)第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.4真值表与等价公式常用的等价式：

5.幂等律:P

P

PP

P

P6.吸收律:P

(P

Q)

PP

(P

Q)

P7.德.摩根律:┐(P

Q)

┐P

┐Q┐(P

Q)

┐P

┐Q8.同一律:PFPP

T

P9.零律:PTTPFF第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.4真值表与等价公式常用的等价式：

10.否定律：P

┐PTP

┐PF11.

蕴涵等值式:P

Q

┐P

Q12.等价等值式:P

Q

(P→Q)

(Q→P)13.假言易位:P

Q

┐Q

┐P14.等价否定等值式:P

Q

┐P

┐Q15.归谬论:(P

Q)(P

┐Q)

┐P

第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.4真值表与等价公式其中P,Q,R等代表任意命题公式.这样上面的每一个公式都是一个模式,它可以代表无数多个同类型的命题公式.例如,P

┐P

T中,用(PQ)置换P,则得(PQ)┐(PQ)T,用┐P置换P,则得(┐P)┐(┐P)T。第一章命题逻辑（PropositionalLogic）第一章命题逻辑（ProPositionalLogic）

1.4真值表与等价公式例1：证明Q→(P

(P

Q))

Q→P证:Q→(P

(P

Q))

Q→P~~~~~~~~P(吸收律)例2：证明P

┐Q

Q

P

Q证：(P

┐Q)

Q

(P

Q)(┐Q

Q)(P

Q)

T

P

Q第一章命题逻辑（ProPositionalLogic）第一章命题逻辑（PropositionalLogic）

1.4真值表与等价公式例3：证明(P→Q)→(Q

R)

P

Q

R证：(P→Q)→(Q

R)

(┐P

Q)→(Q

R)

┐(┐P

Q)

(Q

R)(P

┐Q)

(Q

R)

(P

Q

R)

(┐Q

Q

R)

P

Q

R

第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.4真值表与等价公式例4：验证P(QR)(P∧Q)R证:右┐(P∧Q)∨R

┐P∨┐Q∨R

┐P∨(┐Q∨R)

┐P∨(QR))

P(QR)练：1.((P

Q)∧(PR))P(Q∧R)2.(P∧┐Q)∨(┐P∧Q)(P∨Q)∧┐(P∧Q)第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.4真值表与等价公式等值演算在计算机硬件设计中,在开关理论和电子元器件中都占有重要地位.小结:

本节介绍了真值表、公式等价、等值演算和等价置换等概念，给出了常用的重要等价公式（26个）。重点掌握用真值表法验证公式的等价性和等值演算法推演两个公式等价。第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.4真值表与等价公式作业：Pg.13:1(2),(4)；2(2),(4)；4；6（3）预习:1.5,1.6思考题：Pg.13:5第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.5重言式与蕴含式(TautologyandImplication)1.5.1命题公式的分类1.5.2重言式(Tautology)与矛盾式

(contradictory)的性质1.5.3蕴含式(

ImPlication)第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.5重言式与蕴含式(TautologyandImplication)1.5.1命题公式的分类

复合命题第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.5重言式与蕴含式(TautologyandImplication)定义1.5.1设A为任一命题公式，(1)若A在其各种赋值下的取值均为真，则称A是重言式或永真式,记为T或1。(2)若A在其各种赋值下的取值均为假，则称A是矛盾式或永假式,记为F或0。(3)若A不是矛盾式则称A为可满足式(satisfiable)。注:由定义可知,重言式一定是可满足式,反之不真.第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.5重言式与蕴含式(TautologyandImplication)

判别命题公式的类型有两种方法:真值表法和等值演算法.等值演算法是将所给命题公式通过等值演算化为最简单的形式,然后再进行判别.例1.判别下列命题公式的类型.(1).Q∨┓((┓P∨Q)∧P)(重言式)(2).(P∨┓P)

(Q∧┓Q)∧R(矛盾式)(3).(P

Q)∧┓P.(可满足式)第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.5重言式与蕴含式(TautologyandImplication)1.5.2重言式(Tautology)与矛盾式(contradictory)的性质定理1.5.1:任何两个重言式的合取或析取,仍然是一重言式.（由幂等律立得）证明:设A和B为两个重言式,则不论A和B的分量指派任何真值,总有A为T,B为T,故A∧B

T，A∨B

T。第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.5重言式与蕴含式(TautologyandImplication)定理1.5.2:一个重言式(矛盾式),对同一分量都用任何合式公式置换,其结果仍为一重言式(矛盾式).证明：由于重言式(矛盾式)的真值与对变元的赋值无关，故对同一变元以任何合式公式置换后，重言式(矛盾式)的真值仍永为T（F）。第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.5重言式与蕴含式(TautologyandImplication)定理1.5.3：A,B是两个命题公式，A

B的充要条件是A

B为重言式。

证明:若A

B为重言式，则A

B永为T，即A，B的真值表相同，所以A

B。

反之，若A

B，则A，B真值表相同，所以A

B永为T，所以A

B为重言式。第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.5重言式与蕴含式(TautologyandImplication)它们之间具有如下关系:

P

Q

┓Q

┓P

Q

P

┓P

┓Q原命题逆换式反换式逆反式P

QQ

P┓P

┓Q┓Q

┓P1.5.3蕴含式（ImPlication）定义1.5.2：当且仅当P

Q是一个重言式时，我们称“P蕴含Q”，并记作P

Q.第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.5重言式与蕴含式(TautologyandImplication)因此,要证明P

Q有三种方法:1)真值表法:即列出P

Q的真值表,观察其是否永为真。2)等值演算法：通过证明P

Q1来证P

Q3)分析法：直接分析法:假定前件P是真，推出后件Q是真。间接分析法:假定后件是假，推出前件是假,即证

┓Q

┓P

。第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.5重言式与蕴含式(TautologyandImplication)例:证明┐Q

(P→Q)

┐P1)法1：真值表（略）2)法2：┐Q

(P→Q)→┐P

┐(┐Q

(P→Q))∨(┐P)

Q∨┐(┐P∨Q)∨(┐P)

(┐P∨Q)∨┐(┐P∨Q)1即┐Q

(P→Q)

┐P第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.5重言式与蕴含式(TautologyandImplication)3)直接分析法：若┐Q(P→Q)为真，则┐Q，P→Q为真，所以Q为假，P为假，所以┐P为真。

间接分析法：若┐P为假，则P为真，再分二种情况：①若Q为真，则┐Q为假,从而┐Q(P→Q)为假.

②若Q为假，则P→Q为假，则┐Q(P→Q)为假.根据①②，所以┐Q(P→Q)

┐P第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.5重言式与蕴含式(TautologyandImplication)下面常用的14个蕴含式,都可以用上述方法加以推证.1.P

Q

P2.

P

Q

Q3.P

P∨Q4.┐P

P→Q5.Q

P→Q6.┐(P→Q)

P7.┐(P→Q)

┐Q8.P

(P→Q)

Q9.┐Q

(P→Q)

┐P10.┐P

(P∨Q)

Q11.

(P→Q)

(Q→R)

P→R12.

(P∨Q)

(P→R)

(Q→R)

R13.(P→Q)

(R→S)

(P

R)→(Q

S)14.(P

Q)

(Q

R)

(P

R)第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.5重言式与蕴含式(TautologyandImplication)等价式与蕴含式的关系:定理1.5.4:

设P,Q为任意两个命题公式,P

Q的充要条件为P

Q且Q

P.证：若P

Q，则P

Q为永真式因为P

Q

（P→Q）

（Q→P）所以P→Q，Q→P为永真式,从而P

Q，Q

P.反之，若P

Q，Q

P，则P→Q，Q→P为永真式,所以（P→Q）

（Q→P）为永真式，从而P

Q为永真式，即P

Q.第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.5重言式与蕴含式(TautologyandImplication)蕴含的性质:设A，B，C为任意wff,1)若A

B，且A为永真式，则B必为永真式.2)若A

B，B

C，则A

C.3)若A

B，A

C，则A

B

C.4)若A

B且C

B，则A

C

B.证：1)因为A→B，A永为T,所以B必永为T.2)由I11（A→B)(B→C）

A→C,所以若A

B，B

C，则（A→B)(B→C）永为T,从而A→C永为T,故A

C.第一章命题逻辑（PropositionalLogic）第一章命题逻辑（PropositionalLogic）

1.5重言式与蕴含式(TautologyandImplication)3)（A→B）

（A→C）

（┐A

B）

（┐A

C）

┐A

（B

C）

A→B

C4)(A→B)(C→B)

(┐A

B)(┐C

B)

(┐A

┐C)

B

┐(A

C)

B

A

C→B