离散数学引论.doc

离散数学引论

《离散数学》是现代数学的一个重要分支，是计算机科学基础理论的核心课程，其内容一直随着计算机科学的发展而不断地扩充与更新。它所研究的对象是离散数据结构及相互关系。由于数字电子计算机是一个离散结构，它只能处理离散的或离散化了的数量关系，因此，无论计算机科学本身，还是与计算机科学及其应用密切相关的现代科学研究领域，都面临着对离散结构建立相应的数学模型、将已用连续数量关系建立起来的数学模型离散化问题。在计算机科学中由于普遍采用了离散数学中的基本概念、基本思想和方法，从而使得离散数学成了不可少的理论工具。
离散数学的主要内容为：集合论、数理逻辑、近世代数、图论和组合数学等。离散数学不仅为数据结构、操作系统、编译原理、算法分析、人工智能、形式语言与自动机提供了重要的数学理论基础，而且通过对它的学习可以使我们熟悉和习惯抽象的符号表示和演算形式，培养和训练我们掌握使用数学语言或符号系统处理问题的基本方法，提高我们的抽象思维和逻辑推理的能力。
参考书目：
《离散数学》，耿素云等著，清华大学出版社；
《离散数学》，陈莉等著，高等教育出版社；
《离散数学》，孙吉贵等著，高等教育出版社；
《离散数学及其应用》，傅彦等著，电子工业出版社；

第一章 数理逻辑
数理逻辑又称符号逻辑，是逻辑学的一个重要分支。逻辑学是研究人的思维形式的科学。数理逻辑是用数学方法研究推理、利用符号体系研究推理过程中前提和结论之间的关系。
1.1 命题符号化及联结词
1.1.1命题
命题是一个非真即假的陈述句。因此不能判断真假的陈述句、疑问句、祈使句和感叹句都不是命题。
（1） 一个命题的真或假称为命题的真值。真用T或1表示，假用F或0表示；
（2）原子命题(简单命题)：最简单的命题，通常用大写字母p,q,r表示；几个简单命题用联结词连接起来得到的命题叫复合命题。
（3）一个陈述句有真值与是否知道它的真假是两回事。
［例1.1.1］判断下列语句是不是命题？若是，给出命题的真值：
(1)2是素数。　 (2)雪是黑色的
(3)给我一块钱吧！　　　　　　(4)2007年元旦下雨
(5)x>y。
数理逻辑的特点是并不关心具体某个命题的真假，而是将逻辑推理变成类似数学演算的形式化了的过程，它关心的是命题之间的关联性。因此需要进行命题符号化：
原子(简单)命题就是简单陈述句，用大写字母(或带下标)表示；
命题常元：T(1)或F(0)，或者表示一个确定的命题；
命题变元：以T(1)或F(0)为值的变元；
指派(解释)：用一个具体命题代替一个命题变元。
而不是简单命题的复合命题需要使用称为命题联结词的运算符来进行符号化。命题联结词的作用是为了将原子命题组合成复合命题。常用的有五种：
(1) 否定联结词
P(否定式)：非P
： 不，非，没有
规定P是T当且仅当P是F。
（2） 合取联结词
PQ(合取式) ：P 并且Q，P合取Q
： 并且，且，既…又…，不仅…而且…
规定PQ是T当且仅当P和Q都是T。
（3） 析取联结词
PQ(析取式)：P或者Q，P析取Q
： 或，或者说，不是…就是，要么…要么
规定PQ是T当且仅当P，Q中至少一个是T(或者PQ是F当且仅当P，Q都是F)。
（4） 蕴含联结词→
P→Q(条件式、命题)：如果P则Q
P称为条件式的前件(前提)，Q称为条件式的后件(结论)
→：如果(若)…就(则)，只要…就，若…才能
规定P→Q是F当且仅当P是T，Q是F。
（5） 等价(双条件)联结词
PQ (双条件式、命题) ：P当且仅当Q
规定PQ是T当且仅当P，Q或者都是T，或者都是F。
命题符号化的目的在于用五个联结词将日常语言中的命题转化为数理逻辑中的形式命题，其关键在于使用适当的联结词。对自然语言中语句之间的逻辑关系以及命题联结词的含义要有正确的理解：
（1） 确定语句是否是一个命题；
（2） 找出句中连词，用适当的命题联结词表示。
［例1.1.2］试将下列命题符号化：
（1） 若你不看电影，则我也不看电影。
（2） 小王一边吃饭，一边看书。
1.2 命题公式及分类
1.2.1命题公式
一个命题越复杂，符号化该命题所需的命题变元和联结词就越来越多。如何安排这么多的东西使之有意义呢？
定义1.2.1 一个(合式)公式是由下列方式递归定义的：
（1） 命题常元或命题变元是一个公式；
（2） 若A是一个公式，则(A)也是一个公式；
（3） 若A、B是公式，则(AB)、(AB)、(A→B)和(AB)均为公式；
（4） 只有经过有限次地应用(1)、(2)、(3)所得的结果才是公式。
注：1、公式一般无真值，只有对其所有的变元进行解释后，它才有真值；
2、公式无限多；
3、在一个复杂的公式中，常常有许多括号，为了简便起见，规定下列运算顺序：，，，→，。从而外层括号可以省略；在不会引起混淆的情形中，可以省略公式中的一些括号。
定义1.2.1 命题常项或命题变项称为0层公式；A是n+1层公式如果：
（1）A=B, B是n层公式;
(2)A=CB (或CB、C→B、CB),n为C,B的层数的最大者；
［例1.2.3］指出下列公式的层
(P→QR)(PR)，PR，(P∧R)，(P→QR)(PR)。
1.2.2 命题公式的解释
对于一个命题公式，数理逻辑的目的在于利用这些形式化的表达式来研究命题之间的逻辑关系。这种逻辑关系是用真假来表示的；而命题公式一般而言只是一个符号串，不表示具体的命题，无确定真值，只有对其所有的变元指派以确定的真值后，它才有真值。
定义1.2.4 设公式A(P1, P2, …, Pn)含有n个命题变元P1, P2, …, Pn，对P1, P2, …, Pn进行赋值，即让每一个Pi(i=1,2,…,n)分别取T(1)或F(0)，这称为对A的一个解释或指派I。
一般地，含n个命题变元的公式共有2n种不同的解释。在公式A(P1, P2, …, Pn)的任一个解释I下，每个命题变元有确定的真值，从而公式A(P1, P2, …, Pn)有确定的真值。一个公式在其所有可能的解释下所取的真值，可列出一个真值表。
定义1.2.5　设A 是一个公式，则A的真值表由两部分组成：左边部分是A的所有命题变元以及所有的解释；右边部分是A及A相应于对应解释的真值。
[例1.2.4] 构造五个常用命题联结词的真值表。
[例1.2.5] 构造下列公式的真值表：
(1) (PQ)(PQ)；　　　(2) PP ； (3) PQ。
1.2.3公式分类与永真式
定义1.2.6　设A 是一个公式，
(1)　若A在任何解释下都为T，则称为永真式(重言式)；
(2)　若A在任何解释下都为F，则称A为永假式(矛盾式)；
(3)　若至少存在一个解释使A为T，则称A为可满足式。
注: 1、永真式必为可满足式，反之则不然；永真式的否定是永假式，反之亦然；
2、决定一个公式是否是一个永真式、永假式或可满足式有两种方法：真值表法(适用于变元少而简单的公式)和等值演算法等；
3、永真式的合取、析取、蕴含和等值式都是永真式。
[例1.2.6]判断下列几个公式的类型： PP，PP，PQ。

[例1.2.7]用真值表决定公式(PQ)P的类型。

1.3 等值演算

1.3.1 等值演算
定义1.3.1 设A，B是两个公式，若AB是永真式，即在所有的解释下A和B的真值对应相同，则称A与B 是等值的，记作AB，并称AB为逻辑恒等式。
注1、可用真值表法证明两个公式是否等价；
[例1.3.1]证明　ＰＱ (ＰＱ)(ＱＰ)。
2、等值公式不必含有同样多变元；
3、等值关系是等价关系：自反性(AA)，对称性(若AB，则BA)和传递性(若AB，BC，则AC)；
4、若AB，则AB。
1.3.2 基本等值式
下面是常用的基本逻辑等值式，是公式推理法的基础。
（１） 双否律：ＡＡ；
（２） 交换律：ＡＢＢＡ，ＡＢＢＡ；
（３） 结合律：(ＡＢ)ＣＡ(ＢＣ)，
(ＡＢ)ＣＡ(ＢＣ)；
（４） 分配律：(ＡＢ)Ｃ (ＡＣ)(ＢＣ)，
(ＡＢ) Ｃ (ＡＣ)(ＢＣ)；
（５） De Morgan律：(AB)AB，
(AB)AB；
（６） 等幂律:AAA，AAA；
（７） 同一律:A0A，A1A；
（８） 零一律:A00，A11；
（９） 吸收律:A(AB)A，A(AB)A；
(10)矛盾律与排中律: AA1，AA0；
(11)蕴含等值式:A→BAB， A→BB→A；
(12)等价等值式:AB( A→B)(B→A)
(AB)(BA)(AB)(AB)；
定理1.3.1(置换原理)　设是含命题公式A的公式 是用公式B代替中的A之后所得到的公式，若AB，则。
例如： 所以
[例1.3.2]证明：P→(q→r) (pq)→r。
[例1.3.3]证明：P(pq) (Pq)

1.4对偶与范式
1.4.1 对偶式
定义1.4.1 设A是仅含，和这三种命题联结词的公式，在A中将和互换、1和0(若有的话)所得到的公式称为A的对偶式，记为A＊。
［例1.4.1］　求(P→Q)→R的对偶式。
(P→Q)→R的对偶式是

定理1.4.1 设A(P1, P2, …, Pn)是仅含，和这三种命题联结词的公式，则
A(P1, P2, …, Pn) A＊(P1, P2, …, Pn)。
定理1.3.4(对偶原理)　设A和B都是仅含，和这三种命题联结词的公式，若A B，则A＊B＊。
1.4.2 范式
1.4.2.1 范式
范式使千变万化的公式有了一个统一的表示方式，从而为实现公式的机器判断提供了基础。范式也在电子线路技术、自动机理论和人工智能方面有重要的应用。
（1）简单析（合）取式
定义1.4.2 有限个命题变项或者其否定构成的析取式叫简单析取式：有限个命题变项或者其否定构成的合取式叫简单合取式。
P， P，PP，PQR是简单析取式。
P， P，PP，PQR是简单合取式。
显然：一个简单析取式是永真式它同时含有某命题变元与它的否定。
一个简单合取式是矛盾式它同时含有某命题变元与它的否定。
（2）析（合）范式
定义1.4.3 有限个简单合取式的析取式叫析取范式；有限个简单析取式的合取式叫和取范式。
注（1）若B是合取范式，A是合式公式。若AB，则称B是A的合取范式。
（2）若B是析取范式，A是合式公式。若AB，则称B是A的析取范式。
结论：任意一个命题公式总存在于志等值得合取范式和析取范式。
下面是求一个公式范式的方法：
（1）首先将公式中的蕴涵式和等价式转化为只含，，；
（2）利用De Morgan 律和双否律将括号外的转化到括号内；
（3）利用交换、分配以及结合律按相应范式的要求安排，。
［例1.4.2］ 求 (P→(Q→R))(PQ)的合取范式。

1.4.2.2主范式
从例1.4.2中可以看出，一个公式的合取范式或析取范式是不唯一的，这就给用形式化的方法(特别是用计算机作为工具)来判断两公式是否等价带来了困难。为此我们在下面引入主合取范式与主合取范式。
l 极小项与极大项
定义1.4.4 设公式A是关于的简单合取式,如果
(1) 每个变元与其否定不同时出现，但二者之一必须恰好出现一次,
(2) 出现在第i个位置上 ,
则称A未极小项,用m表示.
注(1) 共有2n个不同的n元极小项；
(2) 极小项的下标编号有唯一的真赋值；
(3)极小项的下标编号方法：
①给出成真赋值,
②把成真赋值视为二进制数,
③把二进制数化为十进制数即得

注：相应地定义极大项，极大项编号方法类似于极小项,只需把“成真”改成“成假”
l 主范式
定义1.4.6 如果析取范式中的每个简单合取式都是极小项，则称它为主析取范式；如果合取范式中的每个简单析取式都是极大项，则称它为主和取范式。
任意命题公式都存在与其等值的主析（合）取范式；且在不计极大项出现的顺序情形下是唯一的。
l 求主析（合）取范式的方法:
　（1）先将公式化为析取范式;
（２）对每一个简单析取式若其中既有某个变元又有它的否定，则去掉该它，若某个变元(或其否定)在式中同时出现二次或二次以上，则用等幂律化简;若其中既无某个变元又无它的否定，则用同一律、排中律和矛盾律使变元或它的否定出现在该和中(扩充)。
［例1.4.３］ (PQ) → (PR)和(P→Q)→R的主析取范式及主合取范式。
1.4.３主范式的应用：
(1)主范式与真值表相互确定
　　主析取范式成真赋值真值表成假赋值主合取范式
极小项成真赋值 极大项成假赋值
［例1.4.４］ 用真值表法求 (PQ)(PR)的主析取范式。
(2)主析取范式与主合取范式相互确定
可以利用主析取范式求主合取范式或反之：
(1)两个主范式中,极小项与极大项共有2n项;
(2) 两个主范式中的下标集互为补集.
［例1.4.５］ 求 (PQ)(PR)
(3)公式的分类：
若n元公式A的主析取范式含2n个极小项，则A为永真式 ;
若n元公式A的主合取范式含2n个极大项，则A为矛盾式;
若n元公式A的主合取范式所含极大项不到2n个，则A为可满足式;
规定: 永真式的主合取范式为1, 矛盾式的主析取范式为0
［例1.4.６］ 判断下列公式是何种公式: (P→Q)Q。
(4)判断公式等值
若两个公式有相同的主范式，则这两个公式等价。
［例1.4.７］ 求证 (P→Q)(P→R) (P→（QR）)；
1.5 命题逻辑的推理理论
1.5.1推理的基本概念和推理形式
定义1.5.1推理就是从一组已知的命题出发，按照一组推理规则推出新的命题的过程。已知命题称为推理的前提，推出的命题称为推理的结论。
推理的格式├
定义1.5.1 设和是公式，若，是永真式，则称是前提的有效结论。记位
推理形式是一个有限公式序列，它的最后一个是结论，其余的公式或者是一个给定的前提，或者是由若干个在它前面出现的公式的有效结论。
判断有效结论的常用方法：
真值表法,等值演算法,主范式法等
［例1.5.1］ 求证

1.5.２推理规则
P规则(前提引入): 在推导过程中，前提可视需要引入使用。
T规则(结论引入): 在推导过程中，利用推理定律可引入前面已导出的结论的有效结论。
置换规则：前面讲过的基本逻辑等价式和基本永真蕴含式都可以适当地变成可用的推理定律。
常用的有：
(1)附加规则AAB；
(2)化简规则ABA；
(3)假言推理A，ABB；
(4)拒取式B，ABA；
(5)析取三段论B，ABA；
(6)假言三段论A→B，B→CA→C；
(7)等价三段论AB，BCAC；
(8)构造性二难 A→B，C→D，AC BD。
(9)合取引入A，B AB；
［例1.5.2］
(1) 前提：
结论：
(2) 前提：
结论：
1.5.3两种推理方法
附加前提证明法: 若结论是形为R→C的公式，则与等价。
［例1.5.3］
前提：
结论：
反证法(归谬法)：
［例1.5.4］
前提：
结论：

11