离散数学 薛广涛 计算机科学与工程系 上海交通大学

联系方式 薛广涛： xue-gt@cs.sjtu.edu.cn ftp.cs.sjtu.edu.cn/xue-gt（课程讲义） 52543318*205 电院楼群3-518

教材和辅导书 教材： 数理逻辑与集合论（第二版）：石纯一，清华大学出版社。 图论与代数结构：戴一奇，清华大学出版社。 辅导书： 图论与代数结构：戴一奇，清华大学出版社。 　 辅导书： 离散数学（第4版），Richard Johnsonbaugh，电子工业出版社 离散数学题解：屈婉玲，清华大学出版社。 离散数学辅导与练习：左孝凌，上海科学技术文献出版社。

课程说明书 讲授内容： 数理逻辑 集合论 图论 成绩构成＝期末考试(第17周)＋平时成绩 平时成绩=作业＋出勤考核： 每周一交作业

离散数学课程说明 研究对象----离散个体及其结构 研究思想----以集合和映射为工具、体现公理化和结构的思想 研究内容----包含不同的数学分支，模块化结构 数理逻辑：形式化、推理方法 集合论：离散结构的表示、描述工具 图论：离散结构的关系模型 代数结构：离散结构的代数模型 组合数学：离散结构的存在性、计数、枚举、优化、设计 离散概率（概率统计课程）

离散数学主要内容的知识结构

离散数学与计算机科学的关系 数理逻辑：人工智能、程序正确性证明、 程序验证等 集合论： 关系数据库模型 数理逻辑：人工智能、程序正确性证明、 　　　　　程序验证等 集合论：　关系数据库模型 图论：　　数据结构、数据库模型、 　　　　　网络模型等 代数结构：软件规范、形式语义、编译系统、 　　　　　编码理论、密码学、数据仓库 组合数学：算法分析与设计、编码理论、容错

第一部分 数理逻辑 逻辑：是对人类推理过程的研究。 数理逻辑：是用数学的方法对人类推理过程作研究。 数学研究方法：使用符号

第一章 命题逻辑的基本概念 命题逻辑(Logic) 主要内容 研究命题的推理演算； 命题逻辑的应用： 命题的基本概念； 命题联结词； 第一章 命题逻辑的基本概念 命题逻辑(Logic) 研究命题的推理演算； 命题逻辑的应用： 数学上定理的推导 在计算机科学上，验证程序的正确性 主要内容 命题的基本概念； 命题联结词； 命题合式公式、重言式； 自然语句的形式化．

1.1 命题（proposition） 命题是一个非真即假(不可兼)的陈述句 真假命题： 命题是一个陈述句，命令句、疑问句和感叹句都不是命题； 命题只有两个取值：真或假。这个陈述句所表达的内容可决定是真还是假，而且不是真的就是假的，不能不真又不假，也不能又真又假。 真假命题： 凡与事实相符的陈述句为真语句，而与事实不符的陈述句为假语句．这就是说，一个命题具有两种可能的取值(又称真值)，为真或为假，并且只能取其一． 通常用大写字母“T”表示真值为真，用“F”表示真值为假．因为只有两种取值，所以这样的命题逻辑称为二值逻辑．

命题举例 (1)“雪是白的” ； (2)“雪是黑的”  ； (3)“好大的雪啊”  ，不是陈述句，不是命题； (4)“一个偶数可表示成两个素数之和”  ． 只不过当今尚不知其是真命题还是假命题． (5)“1+10l＝110”．  这是一个数学表达式，相当于一个陈述句，可以叙述为“1加101等于110"，这个句子所表达的内容在十进制范围中真值为假，而在二进制范围中真值为真．可见，这个命题的真值与所讨论问题的范围有关．

命题变项 为了对命题作逻辑演算，采用数学手法将命题符号化(形式化)是十分重要的． 命题的表示：大写符号 P表示“雪是白的” Q表示“北京是中国的首都” 命题变项：P表示任一命题时，P就称为命题变项(变元)． 命题与命题变项含义是不同的： 命题指具体的陈述句，是有确定的真值； 命题变项的真值不定，只当将某个具体命题代入命题变项时，命题变项化为命题，方可确定其真值， 命题与命题变项像初等数学中常量与变量的关系一样．如5是一个常量，是一个确定的数字，而x是一个变量，赋给它一个什么值它就代表什么值，即x的值是不定的。

简单命题和复合命题 简单命题又称原子命题(Primitive proposition) 简单命题是不包含任何的与、或、非一类联结词的命题． 简单命题不可再分割，如“雪是白的”再分割就不是命题了． 命题“雪是白的而且l+l＝2”不是简单命题，它可以分割为“雪是白的”以及“1十1＝2”两个简单命题，联结词是“而且”． 在简单命题中，尽管常有主语和谓语，但我们不去加以分割，是将简单命题作为一个不可分的整体来看待，进而作命题演算．在谓词逻辑里，才对命题中的主谓结构进行深入分析．

复合命题(Compound proposition) 复合命题：把一个或几个简单命题用联结词(如与、或、非等)联结所构成的新的命题。 “张三学英语和李四学日语”就是一个复合命题； 由简单命题“张三学英语” “李四学日语”经联结词“和”联结而成。 复合命题的真值：依赖于构成该复合命题的各个简单命题的真值以及联结词。 上例中，当以上两个简单命题真值均为真时，该复合命题方为真． 命题逻辑所讨论的是多个命题联结而成的复合命题的规律性．

内容 / 形式 命题是一个可取真或可取假的陈述句。 数理逻辑不关心：这些具体的陈述句的真值究竟为什么或在什么环境下是真还是假。 数理逻辑关心的是：命题可以被赋予真或假这样的可能性，以及规定了真值后怎样与其他命题发生联系。

1.2 命题联结词及真值表 联结词可将命题联结起来构成复杂的命题。 1.2 命题联结词及真值表 联结词可将命题联结起来构成复杂的命题。 命题逻辑联结词的引入是十分重要的，其作用相当于初等数学里在实数集上定义的+、、、÷等运算符； 通过联结词便可定义新的命题，从而使命题逻辑的内容变得丰富起来； 我们要讨论的仅只是复合命题的真值，此值可由组成它的简单命题的真值所确定． 值得注意的是逻辑联结词与日常自然用语中的有关联结词的共同点和不同点．

常用的逻辑联结词 否定词（negation）“ ”是个一元联结词，亦称否定符号． 一个命题P加上否定词就形成了一个新的命题，记作 P，这个新命题是命题的否定，读作非P。 否定词 “ ”的真值规定如下： 若命题P的真值为真，那么 P的真值就为假；若P的真值为假，那么 P的真值就为真．  P与P间的真值关系，常常使用称作真值表的一种表格来表示.

P 的定义 P P T F 真值表 真值表表明了P的真值如何依赖于P的真值． 真值表描述了命题之间的真值关系，很直观. 真值表是命题逻辑里研究真值关系的重要工具． P P T F

例1 “昨天张三去看球赛了”．该命题以P表示； “昨天张三没有去看球赛”，该新命题便可用P表示． 若昨天张三去看球赛了，命题P是真的，那么新命题P必然是假的．反之，若命题P是假的，那么P就是真的．

例2 Q：今天是星期三．  Q：今天不是星期三．

合取词 合取词(Conjuction)是个二元命题联结词，亦称合取符号 将两个命题P，Q联结起来，构成一个新的命题P  Q，读作P  Q的合取，也可读作P与Q 这个新命题P  Q的真值与构成它的命题P，Q的真值间的关系，由合取词真值表来规定。

合取词真值表 P^Q可用来表示日常用语P与Q，或P并且Q． 只有当两个命题变项P＝T，Q=T时方有 P^Q ＝T，而P，Q只要有一为F，则P^Q =F． P^Q可用来表示日常用语P与Q，或P并且Q． P Q P^Q F T

例3 P：教室里有10名女同学； Q：教室里有15名男同学； 命题P  Q : “教室里有10名女同学与15名男同学”。

例4 A：今天下雨了． B：教室里有100张桌子。 命题A^B是 ：“今天下雨了并且教室里有100张桌子”．

合取词与日常自然用语中的联结词 逻辑联结词是自然用语中联结词的抽象，与合取词并不等同，这是需注意的． 日常自然用语里的联结词“和”、“与”、“并且”，一般是表示两种同类有关事物的并列关系．而在逻辑语言中仅考虑命题与命题之间的形式关系并不顾及日常自然用语中是否有此说法．这样，“”同“与”、“并且”又不能等同视之． 日常自然用语中说，“这台机器质量很好，但是很贵”，这句话的含义是说同一台机器质量很好而且很贵．若用P表示“这台机器质量很好”，用Q表示“这台机器很贵”，那么这句话的逻辑表示就是P  Q ，尽管这句话里出现的联结词是“但是”．总之，合取词有“与”、“并且”的含义，

析取词∨ 析取词(disjuction)“∨”是个二元命题联结词。 将两个命题P、Q联结起来,构成一个新的命题P∨Q, 读作P、Q的析取, 也读作P或Q。 这个新命题的真值与构成它的命题P、Q的真值间的关系,

析取词真值表 当P、Q有一取值为T时, P∨Q便为T。 仅当P、Q均取F值时, P∨Q方为F。 这就是析取词的定义, P∨Q可用来表示自然用语P或Q。 P Q P Q F T

例 例5: P: 今天刮风。 Q: 今天下雨。 命题“今天刮风或者下雨”便可由P∨Q来描述了。 例6: A: 2小于3。 B: 雪是黑的。 A∨B就是命题“2小于3或者雪是黑的”。由于2小于3是真的, 所以A∨B必取值为真, 尽管“雪是黑的”这命题取假。

蕴涵词 蕴涵词(implication)“”也是个二元命题联结词。 将两个命题P、Q联结起来, 构成一个新的命题PQ, 读作如果P则Q, 或读作P蕴涵Q, 如果P那么Q, 其中P称前件(前项、条件), Q称后件(后项、结论)。 规定只有当P为T而Q为F时, PQ = F。而P = F、Q任意, 或P = T、Q = T时PQ均取值为T。

蕴涵词 举例 P：天下雨了； Q：地上是湿的； PQ 如果天下雨，那么地是湿的， T 如果天下雨，那么地不是湿的， F

真值表 PQ = T下, 若P = T必有Q = T, 而不会出现Q = F, 这表明PQ体现了P是Q成立的充分条件。 PQ = T下, 若P = F可有Q = T, 这表明PQ体现了P不必是Q成立的必要条件。 P Q P  Q F T

因果关系 引入的目的是希望用来描述命题间的推理, 表示因果关系。 使用PQ能描述推理。 PQ为真时, 只要P为真必有Q真, 而不能出现P真而Q假就够了。 P为假时, Q取真取假, 并不违背P为真时Q必真。从而仍可规定P为假时, PQ取真。 当P = F时对PQ真值的不同定义方式将给推理的讨论带来不同的表示形式, 也是允许的。

PQ = P∨Q P Q P  Q F T 在P、Q的所有取值下, PQ同P∨Q都有相同的真值: PQ = P∨Q

例7: P: n > 3 (n为整数) Q: n2 > 9 命题PQ表示“如果n > 3那么n2 > 9”, 分析PQ的真值。 P = Q = T。这时如n = 4 > 3, 有n2 = 16 > 9, 这符合事实 PQ = T, 正是我们所期望的可以PQ表示P、Q间的因果关系, 这时规定P T是自然的。 P = T, Q = F。如n > 3而 n2 < 9这是不会成立的, 也可用PQ表示P、Q间的因果关系是不成立的, 自然规定PQ = F。 P = F而Q = F或T。如 n = 2 < 3 有 n2 = 4 < 9 n = -4 < 3 有 n2 = 16 > 9 由于前提条件n > 3不成立，而n2 > 9 成立与否并不重要，都不违反对自然用语“如果n > 3那么n2 > 9”成立的肯定。于是 P = F时可规定P Q = T。

如果……那么…… 蕴涵词与自然用语“如果…那么…”有一致的一面，可表示因果关系。然而P、Q是无关的命题时，逻辑上允许讨论PQ。并且P = F则PQ = T，这在自然用语中是不大使用的。 对P = F时PQ的值另作规定也是可以的, 同样不违反自然语句“如果……那么……”可以用PQ来描述。总之，对PQ的这种说明是可接受的, 但也不是说仅只有这样的解释才是合理的。

例8: P: 2 + 2 = 5 Q: 雪是黑的 PQ就是命题“如果2 + 2 = 5, 那么雪是黑的” 从蕴涵词的定义看，由2 + 2 = 5是不成立的或说P取F值, 不管Q取真取假都有PQ = T。

双条件词 双条件词(Biconditional)“”也是个二元命题联结词。 P Q PQ F T

(PQ)∧(QP) = PQ 只有当两个命题P、Q的真值相同或说P = Q时, PQ的真值方为T。而当P、Q的真值不同时, PQ = F。 若建立(PQ)∧(QP)的真值表, 就可发现(PQ)∧(QP)和PQ有相同的真值, 于是 (PQ)∧(QP) = PQ

例9 P: ABC是等腰三角形 Q: ABC中有两个角相等 命题PQ就是“ABC是等腰三角形当且仅当ABC中有两个角相等”。显然就这个例子而言PQ = T。

总结 定义的五个联结词是数理逻辑中最基本最常用的逻辑运算。 一元二元联结词还有多个，此外还有三元以至更多元的联结词，因其极少使用，况且又都可由这五个基本联结词表示出来，所以无需一一定义了。 联结词是由命题定义新命题的基本方法。 命题逻辑的许多问题都可化成是计算复合命题的真假值问题，真值表方法是极为有力的工具，是应十分重视和经常使用的。

总结 由联结词构成新命题的真值表中，对仅由两个变元P、Q构成的新命题A而言, 每个变元有T、F两种取值, 从而P、Q共有四种可能的取值, 对应于真值表中的四行, 每一行下命题A都有确定的真值。 对P、Q的每组真值组合(如P = T, Q = F)或说真值指派, 都称作命题A的一个解释。 一般地说, 当命题A依赖于命题P1, …, Pn到A的真值表就有2n行, 每一行对应着P1, …, Pn的每组真值都称作命题A的一个解释。A有2n个解释, 命题的解释用符号I表示。

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

不同的符号 五个联结词在不同的书中会采用不同的符号。如P可以以～P表示, P∧Q以P·Q表示, P∨Q以P + Q表示, PQ以PQ表示, PQ以PQ表示。阅读时应注意不同的表示方式。

1.3 合式公式 命题公式是命题逻辑讨论的对象 由命题变项使用联结词可构成任意多的复合命题，如P∧Q, P∧Q∨R, PQ等。问题是它们是否都有意义呢？ 只有一个联结词的命题P, P∧Q, PQ当然是有意义的。 由两个联结词构成的命题P∧Q∨R至少意义不明确, 是先作P∧Q再对R做∨, 还是先作Q∨R再对P作∧呢? 括号解决 由命题变项、命题联结词和圆括号便组成了命题逻辑的全部符号。进一步的问题是建立一个一般的原则以便生成所有的合法的命题公式，并能识别什么样的符号串是合法的（有意义的）？

合式公式(简记为Wff)的定义： 1. 简单命题是合式公式。 2. 如果A是合式公式, 那么A也是合式公式。 3. 如果A、B是合式公式, 那么(A∧B), (A∨B), (AB)和(AB)是合式公式。 4. 当且仅当经过有限次地使用1.2.3所组成的符号串才是合式公式。 这个定义给出了建立合式公式的一般原则，也给出了识别一个符号串是否是合式公式的原则。 这是递归（归纳）的定义。在定义中使用了所要定义的概念，如在2和3中都出现了所要定义的合式公式字样，其次是定义中规定了初始情形，如1中指明了已知的简单命题是合式公式。条件4说明了哪些不是合式公式，而1、2和3说明不了这一点。

判断一个公式是否为合式公式 若判断一个公式是否为合式公式，必然要层层解脱回归到简单命题方可判定。 (P∧Q) (P(P∧Q)) (((PQ)∧(QR))(PR))是合式公式。 P∨Q∨, ((PQ)( ∧Q)), (PQ都不是合式公式。

约定 为了减少圆括号的数量，可以引入一些约 (P(Q∨R))可写成P(Q∨R)或PQ∨R。 (P(PR))可写成P(PR)。 规定联结词优先级的办法，可按， ∧， ∨，，的排列次序安排优先的级别 多个同一联结词按从左到右的优先次序。这样，在书写合式公式时，可以省去部分或全部圆括号。通常采用省略一部分又保留一部分括号的办法，这样选择就给公式的阅读带来方便。如 (P(Q∨R))可写成P(Q∨R)或PQ∨R。 (P(PR))可写成P(PR)。 命题演算中只讨论合式公式, 将合式公式就称作公式。

1.4 重言式 /可满足式/矛盾式 如果一个公式，对于任一解释I其值都为真，就称为重言式（永真式）。如P∨P是一个重言式。 1.4 重言式 /可满足式/矛盾式 如果一个公式，对于任一解释I其值都为真，就称为重言式（永真式）。如P∨P是一个重言式。 由∨、∧、和联结的重言式仍是重言式。 一个公式，如在某个解释I0下值为真, 则称它是可满足的。如P∨Q，当取I0 = (T, F)，即P = T, Q = F时便有P∨Q = T, 所以是可满足的。 重言式当然是可满足的。 矛盾式（永假式或不可满足式）：如果一个公式，对于任一解释I值都是假的，便称是矛盾式。如P∧P就是矛盾式。

三类公式间关系 1. 公式A永真， 当且仅当Ａ永假。 2. 公式A可满足, 当且仅当A非永真。 3. 不是可满足的公式必永假。 4. 不是永假的公式必可满足。

1.4.2 代入规则 A是一个公式, 对A使用代入规则得公式B, 若A是重言式, 则B也是重言式。 1.4.2 代入规则 A是一个公式, 对A使用代入规则得公式B, 若A是重言式, 则B也是重言式。 为保证重言式经代入规则仍得到保持, 要求: 公式中被代换的只能是命题变元(原子命题), 而不能是复合命题。 2. 对公式中某命题变项施以代入，必须对该公式中出现的所有同一命题变项代换以同一公式。

A = P∨P, P以 Q代之得 规则1举例 如可用(R∧S)来代换某公式中的P, 而不能反过来将公式中的(R∧S)以P代之。 这一要求可以以代数的例子来说明，如对 (a + b)2 = a2 + 2ab + b2 可以a = cd代入，仍会保持等式成立。而若将a + b以cd代入，结果左端得(cd)2，而右端无法代入cd，不能保持等式成立了。 规则2举例 A = P∨P, P以 Q代之得 B = Q∨Q 仍是重言式。 若将P以Q代替得B = P∨Q不是重言式了

使用代入规则证明重言式 例1: 判断(R∨S) ∨(R∨S)为重言式。 因 P∨P为重言式, P以(R∨S)代入即得。 例2： 判断((R∨S)∧((R∨S)(P∨Q)))(P∨Q)为重言式. 不难验证(A∧(AB))B是重言式, A 以R∨S代入，B 以P∨Q代入即得。

1.5 命题形式化 一些推理问题的描述，常是以自然语句来表示的，需首先把自然语句形式化成逻辑语言，即以符号表示的逻辑公式，然后根据逻辑演算规律进行推理演算。 先要引入一些命题符号P、Q、…用来表示自然语句中所出现的简单命题，进而依自然语句通过联结词将这些命题符号联结起来，以形成表示自然语句的合式公式。

1.5.1 简单自然语句的形式化 命题1. 北京不是村庄。 令P表示“北京是村庄”，于是命题1可表示为P。 命题2. 李明既聪明又用功。 1.5.1 简单自然语句的形式化 命题1. 北京不是村庄。 令P表示“北京是村庄”，于是命题1可表示为P。 命题2. 李明既聪明又用功。 令P表示“李明聪明”，Q表示“李明用功”，于是命题2可表示为P∧Q。 命题3. √2是有理数的话, 2√2也是有理数。 令P表示“√2是有理数”，Q表示“2√2是有理数”，于是命题3可表示为PQ。

1.5.2 较复杂自然语句的形式化 需注意的是逻辑联结词是从自然语句中提炼抽象出来的，它仅保留了逻辑内容，而把自然语句所表达的主观因素、心理因素以及文艺修辞方面的因素全部撇开了，从而命题联结词只表达了自然语句的一种客观性质。 又由于自然语句本身并不严谨，常有二义性，自然会出现同一自然语句的不等价的逻辑描述，其根由在于人们对同一自然语句的不同理解。

例1: 张三与李四是表兄弟。 这是普通的自然用语，它是一个命题，令以R表示, 若形式地规定: P: 张三是表兄弟。 Q: 李四是表兄弟。 那么 R = P∧Q。 显然，这样的形式化是错误的。原因很简单。“张三是表兄弟”，“李四是表兄弟”都不是命题。实际上“张三与李四是表兄弟”才是一个命题，而且是一个简单命题。这例子说明自然语句中的“与”不一定都能用合取词来表达。

例2：张三或李四都能做这件事。 这句话中的“或”不一定就用析取词来表示，应允许有的人把这命题的内容理解为：张三能做这件事而且李四也能做这件事，这样，这句话便可以P∧Q的形式表示了。

例3: 给了三个命题 A: 今晚8点我在家里看电视。 B: 今晚8点我在体育场看球赛。 C: 今晚8点我在家里看电视或在体育场看球赛。 问题是C与A∨B是否表达的是同一命题呢?

否。因为C同A、B的真值关系为 A B C A∨B F T

异或(不可兼或) 这表的前三行很容易理解，而第四行是说今晚我在家看电视，又去体育场看球赛。显然对同一个人来说这是不可能的，从而这时C的真值为F。这就说明了C与A∨B逻辑上是并不相等的。即C中出现的“或”不能以“∨”来表示。 C同A, B的逻辑关系, 常称为异或(不可兼或), 以 表示, 有 C = A B 不难验证 C = (A∧B) ∨(A∧B)

例4: 今天我上班, 除非今天我病了 以P表示今天我病了, Q表示今天我上班,

例5: 仅当明天不下雨，并且明天不刮风，我才去学校。 以P表示明天下雨, Q表示明天刮风,R表示我去学校。 仅当…并且…,才…。 可描述成R (P ∧ Q) 或描述成 (P ∨ Q)  R

作业 P12 3(2) 4(3,5) 5(6,7,8)

作业 使用命题，将下列句子形式化： 如果这个材料无趣，习题也不难，那么这门课程就不让人喜欢 这个材料有趣，意味着这些系统很难，并且反之亦然。 或者这个材料有趣，或者这些习题很难，并且两者恰具其一。 假如上午不下雨，我去看电影，否则就在家里读书或看报。 我今天进城，除非下雨 仅当你走，我将留下。