离散数学学习笔记-个人总结

第1章主要介绍集合论的基本概念和结论，集合的运算及其性质，以及利用运算性质进行集合表达式的化简和集合恒等式的证明等内容．考试经常涉及到的题型有以下4个： 集合与集合之间的包含、元素与集合之间的属于关系 幂集的计算 集合之间的运算

利用集合运算性质证明集合恒等式

大家对于集合与集合、元素和集合之间的关系往往容易混淆，那让我们来仔细分析下二者的区别。 1.集合与集合之间存在一种包含关系，用?、?、?、?等符号表示

①对任意两个集合A和B，若B中的每个元素都是A中的元素，则称B为A的子集，用B?A（B为A的子集）或A?B（B被A包含）表示．若B不是A的子集，即B?A不成立时，则称A不包含B，记作BA． ②空集是任意一个集合的子集，集合A也是自己的子集．

③对任意两个集合A和B，若B?A且B≠A，则称B为A的真子集，用B?A或A?B表示． 2.元素与集合之间存在一种从属关系，用∈、等符号表示 当a是集合A中的元素，则称a属于A，记作a∈A； 若a不是集合A中的元素，则称a不属于A，记作aA． 那么在考试中是怎样考的呢？我们来看2道历年真题：

[例1]若集合A＝{a，{a}，{1，2}}，则下列表述正确的是(C )． （2008年9月试卷第1题） A．{a，{a}}∈A B．{2}?A C．{a}?A D．∈A [分析]

选项A，错了．

因为{a，{a}}是集合A＝{a，{a}，{1，2}}的子集，集合之间应该用包含关系?表示，即{a，{a}}?A． 选项B，错了．

因为2不是集合A＝{a，{a}，{1，2}}的元素，当然{2}也不是A的子集．正确的表示方法是{2}A． 选项C，正确．

因为a是集合A＝{a，{a}，{1，2}}的元素，所以取元素a组成一个集合{a}就是A的子集，用包含关系?表示是正确的．

注意：{a}也是集合A的元素，若属于关系∈也是正确的． 选项D，错了．

因为空集是任意一个集合的子集，所以也是A的子集，集合之间应该用包含关系?表示，即?A． [例2]若集合A={a，b}，B={a，b，{a，b}}，则（ ）． （2009年7月试卷第1题） A．A?B，且A∈B B．A∈B，但AB C．A?B，但AB D．AB，且AB [答案]A [分析]

选项A，正确．

因为集合A={a，b}既是取集合B={a，b，{a，b}}中元素a，b组成的一个集合，是B的一个真子集，用A?B表示是正确的；但它也是B的元素，所以用A∈B表示也是正确的． 选项B，错了．

选项中第一个式子A∈B是正确的，但第二个式子AB是错的．因为集合A={a，b}是取集合B={a，b，{a，b}}中元素a，b组成的一个集合，是B的一个真子集，应该用A?B表示，而不是用AB表示． 选项C，错了．

选项中第一个式子A?B是正确的，但第二个式子AB是错的．因为集合A={a，b}是集合B={a，b，{a，b}}中元素，应该用A∈B表示，而不是用AB表示． 选项D，错了．

因为集合A={a，b}是取集合B={a，b，{a，b}}中元素a，b组成的一个集合，是B的一个真子集，应该用A?B表示，而不是用AB表示．

又因为集合A={a，b}是集合B={a，b，{a，b}}中元素，应该用A∈B表示，而不是用AB表示．

幂集的计算比较简单，先来看什么是幂集呢？

由集合A的所有子集组成的集合，称为A的幂集，记作P(A)或2A ．若集合A是由n个元素所组成的集合，则A的幂集由2n元素组成．当n=3时，A的幂集由23=8个元素组成．

举个例子来说，大家就会觉得比较简单了．设集合A = {0, 1, 2 }，则A的全部子集由以下子集组成：

0元子集（即空集）：；

1元子集：{0}，{1}，{2}；

2元子集：{0, 1}，{0, 2}，{1, 2}； 3元子集（即集合A）：{0, 1, 2}．

因此，计算集合A的幂集时，首先要按照上述方法写出集合A的全部子集，然后检验写出的子集个数是否等于2n 个，其中n是集合A的元素个数 那么在考试中是怎样考的呢？我们来看2道历年真题：

[例1] 若集合A的元素个数为10，则其幂集的元素个数为( )． （2008年7月试卷第3题） A．1024 B．10

C．100 D．1 [答案]：A [分析]

由集合A的所有子集组成的集合，称为A的幂集，记作P(A)或2A.

若集合A是由n个元素所组成的集合，则A的幂集由2n元素组成．本题集合A有10个元素，因此A的幂集由210=1024个元素组成．

所以选项A是正确，其他选项都不对．

【易错点】

当n比较大时，有些同学可能不会计算2的n次幂，即把210计算错了．【提示】 若集合A有n个元集，则其幂集P(A )有2n个元素．

[例2] 设集合A＝{a，b}，那么集合A的幂集是_________ ． （2008年7月试卷第6题） [答案]：{，{a}，{b}，{a,b}} [分析]

按照幂集定义，集合A＝{a，b}的所有子集就是A 的幂集． A的全部子集由以下子集组成： 0元子集（即空集）：； 1元子集：{ a }，{ b }；

2元子集（即集合A）：{a，b}．

所以，集合A的幂集是：{，{a}，{b}，{a, b}}

集合之间的运算有并（∪）、交（∩）、差（-）、补（~）和对称差（）等五种运算，在做集合运算的题目时，一定要按照它们的定义进行计算。 (1) 集合A和B的并集 A∪B＝{ x | x∈A 或 x∈B } 特点：所有属于A或属于B的元素组成的集合．见图1 (2) 集合A和B的交集 A∩B＝{ x | x∈A 且 x∈B } 特点：既属于A又属于B的所有元素组成的集合．见图2 (3) 集合A和B的差集 A-B＝{ x | x∈A 且 xB } 特点：由属于A，而不属于B的所有元素组成的集合．见图3 (4) 集合A的补集 ~A = { x | x∈E 且 xA } 特点：由属于全集E但不属于集合A的元素组成的集合．见图4 补集总相对于一个全集而言，可以看作是全集E与集合A的差集． (5) 集合A与B的对称差 AB＝(A-B)∪(B-A) 或 AB＝(A∪B)-(A∩B) 特点：由分别属于集合A与B的元素但不属于它们公共元素组成的集合．见图5 (6) 把集合A，B合成集合A×B叫做笛卡儿积，规定 A×B＝{ | x∈A且y∈B}

注意：由于有序对中x, y的位置是确定的，因此A×B的记法也是确定的，不能写成B×A.．

笛卡儿积的运算一般不能交换.．

虽然笛卡儿积的内容是第2章2.1.1目的内容，是二元关系的预备知识，但我们认为把它作为集合的一种运算考虑更好些。

那么在考试中是怎样考的呢？我们来看2道历年真题：

[例1] 设A={{1},{2}, 1, 2}，B={1, 2, {1, 2}}，试计算 （2008年9月试卷第17题） （1）A-B； （2）A∩B； （3）A×B [分析]

（1）求集合A与B的差集A-B，就是求属于A而不属于B的所有元素组成的集合．即 A-B= {{1},{2}, 1, 2}-{1, 2, {1, 2}}= {{1},{2}}．

（2）求集合A与B的交集A∩B，就是求由集合A和B的公共元素组成的集合．即 A∩B ={{1},{2}, 1, 2}∩{1, 2, {1, 2}}={1, 2}．

（3）求集合A与B的笛卡儿积A×B，就是求一个元素是有序对的集合，而这些有序对的第一个元素取自集合A，第二个元素取自集合B．即

A×B={{1},{2}, 1, 2}×{1, 2, {1, 2}}={<{1}, 1>，<{1}, 2>，<{1}, {1, 2}>，<{2}, 1>，<{2}, 2>，<{2},{1,2}>，<1, 1>，<1, 2>，<1, {1, 2}>，<2, 1>，<2, 2>，<2, {1, 2}>}

【易错点】

我们对集合中有的元素用集合形式表示的情形容易混淆，既不把{1},{2}看作集合A的元素，不把{1, 2}看作集合B的元素，或者把{1}，{2}，{1, 2}看作是相同的。

【提示】

笛卡儿积A×B是由集合A的每一个元素与集合B的各个元素合成有序对（其中x∈A且y∈B）作为元素的集合．

所谓有序对就是指一个有顺序的数组，如，x, y 的位置是确定的，不能随意放置。

[例2] 设A={{a, b}, 1, 2}，B={ a, b, {1}, 1}，试计算 （2009年1月试卷第17题） （1）A-B； （2）A∪B； （3）（A∪B）-（A∩B） [分析]

（1）求集合A与B的差集A-B，就是求属于A而不属于B的所有元素组成的集合．即 A-B={{a, b}, 1, 2}-{ a, b, {1}, 1}={{a, b}, 2}．

（2）求集合A与B的并集A∪B，就是求由集合A和B的所有元素组成的集合．即 A∪B ={{a, b}, 1, 2}∪{ a, b, {1}, 1}={{a, b}, 1, 2,a, b, {1}}．

（3）因为 A∪B ={{a, b}, 1, 2,a, b, {1}} A∩B ={{a, b}, 1, 2}∩{ a, b, {1}, 1}={1}

所以（A∪B）-（A∩B）={{a, b}, 1, 2, a, b, {1}}-{1}={{a, b}, 2, a, b, {1}}．

如同实数运算有交换律、结合律和分配率等。集合的运算也有许多运算律。下面以恒等式的形式给出集合运算满足的主要运算律,其中

A,B,C为任意集合,E为全集。 这些恒等式是证明其它集合恒等式、化简集合表达式的主要依据,正确运用这些恒等式是做好集合证明或化简题的关键．因此,大家要通过练习逐步掌握这些集合运算性质.

A∪B=B∪A

1、交换律

A∩B=B∩A

(A∪B)∪C=A∪(B∪C)

2、结合律

(A∩B)∩C=A∩(B∩C) A∪(B∩C)=(A∪B)∩(A∪C)

3、分配律

A∩(B∪C)=(A∩B)∪(A∩C)

4、同一律 5、幂等律 6、零律

A∪=A A∩E=A A∪A=A A∩A=A A∪E=E

7、补余律 8、吸收率

A∩= A∪~A=E A∩~A = A∪(A∩B)=A A∩(A∪B)=A A-(B∪C)=(A-B)∩(A-C) A-(B∩C)=(A-B)∪(A-C) ～(B∪C)=~B∩~C ～(B∩C)=~B∪~C

~=E ~E= ~（~A）=A

9、摩根律

10、双补律

[例1] 试证明集合等式A∪(B∩C)=(A∪B)∩(A∪C)． （2008年9月试卷第19题、2009年10月试卷第8题）

[证明过程]

若对A∪(B∩C)中的任一元素x，即x∈A∪(B∩C), 则有x∈A或x∈B∩C，

即 x∈A或x∈B且x∈A或x∈C,

也即x∈A∪B且x∈A∪C，得x∈(A∪B)∩(A∪C)． 所以A∪(B∩C)?(A∪B)∩(A∪C)．①

反之，若对(A∪B)∩(A∪C)中的任一元素x，即x∈(A∪B)∩(A∪C), 则有x∈A∪B且x∈A∪C,

即x∈A或x∈B且x∈A或x∈C,

也即x∈A或x∈B∩C，得x∈A∪(B∩C)． 所以(A∪B)∩(A∪C)?A∪(B∩C)． ② 由①和②得 A∪(B∩C)=(A∪B)∩(A∪C)．

【提示】

集合恒等式的证明方法通常有二：

(1)要证明A=B，只需要证明A?B，又A?B； (2)通过运算律进行等式推导.

[例2] 设A，B是任意集合，试证明：若A×A=B×B，则A=B． （2010年1月试卷第18题） [证明过程]

设对A中的任一元素x，即x∈A，那么有序对是笛卡儿积A×A的元素，即∈A×A． 因为A×A=B×B，故有∈ B×B，则有x∈B． 所以A?B． ①

又设对B中的任一元素x，即x∈ B，那么有序对是B×B的元素，即∈ B×B． 因为A×A=B×B，故有∈A×A，则有x∈A． 所以B?A． ②

由①和②得 A=B．

第2章主要介绍关系的概念及运算、关系的性质与闭包运算、等价关系、相容关系和偏序关系三个重要关系、函数以及函数相关知识等内容．考试经常涉及到的题型有以下5个：

关系的概念理解以及关系的并、交、补、差以及复合和逆关系等运算

关系自反和反自反、对称和反对称等性质的概念理解与判定；自反、对称和传递闭包运算 等价关系

偏序关系和哈斯图

函数的概念和性质

所谓“关系”，就是指客体之间的相互联系，是一种普遍存在的现象．任何一个有序对集合，称为一个“二元关系”，简称“关系”，记作R．对于二元关系R， 若∈R，可记作aRb；

若R，则记作ab．

[例1] 如果R是非空集合A上的等价关系，a∈A，b∈A，则可推知R中至少包含 等元素． [答案] ， [分析]

由等价关系的概念，知道R具备了自反性、对称性和传递性．根据已知A上的元素a和b，根据自反的概念，知道R中必须包含和，由对称和传递概念，得知{，}也具备对称性和传递性，因此对应A上的关系R至少应该包含元素，

【易错点】

本题目中要求的是最小等价关系，同学们容易将答案写为{，，，}．

【提示】

先加入自反关系，然后再根据等价关系加入必要的对称和传递所需的元素．

[例2] 集合A={1，2，3，4，5，6，7，8}上的关系R={| x+y=10且x，y∈A}，则R的性质为（ ）． A．自反的 B．对称的

C．传递且对称的 D．反自反且传递的 [答案] B 分析]

首先，可以写出关系R的有限集合表示，即 {<2，8>，<8，2>，<3，7>，<7，3>，<4，6>，<6，4>，<5，5>}

容易看出，<1，1>R，因此R不是自反的．<5，5>∈R因此，R不是反自反的．

又因为<2，8>∈R，且<8，2>∈R，而<2，2>R，因此，R不具备传递性． 因此，答案选择B [例3] 若A={1，2}，R={| x∈A，y∈A，x+y=10}，则R的自反闭包为 答案] {<1，1>，<2，2>} [分析]

本题考核的是关系闭包的计算．计算关系闭包有集合法、矩阵法和关系图法．本题目可以直接使用集合法计算公式r(R)=R∪IA．

首先容易计算出R=Φ，IA={<1，1>，<2，2>}． r(R)=R∪IA= IA={<1，1>，<2，2>}

（1）函数的概念

设 f 是集合A到B的二元关系，若任意 a∈A，存在 b∈B，且∈ f ，Dom(f) = A，则 f 是一个函数（映射）．函数是一种特殊的关系．

注意：集合 A×B 的任何子集都是关系，但不一定是函数．函数要求对于定义域 A 中每一个元素a，B中有且仅有一个元素与 a 对应，而一般的关系没有这个限制． （2）单射、满射和双射的判断 单射：若 a1≠a2?f (a1)≠ f (a2)；

满射：f (A) = B，即对任意 y ∈B，存在 x ∈A，使得 y = f(x) ； 双射：单射且满射． （3）函数的复合

若 f：A→B，g：B→C，则 f·g：A→C，即 (g·f)(x)=g( f(x))．

复合成立的条件是：Ran(f)? Dom(g)．

[例1] 设A={a，b，c}，B={1，2}，作 f：A→B，则不同的函数个数为__________ [答案]：8 [分析]

本题目考核的是学生对函数概念的理解． 函数可以有下面映射规则：

（1）a,b,c全映射到2；

（2）a 映射到1，b 和 c映射到2； （3）b 映射到1，a 和 c映射到2； （4）c 映射到1，a 和 b映射到2； （5）a 映射到2，b 和 c映射到1； （6）b 映射到2，a 和 c映射到1； （7）c 映射到2，a 和 b映射到1； （8）a,b,c全映射到1；

因此，函数个数为8．另外，此类题目也可以作以下分析．A到B映射个数可以描述为： C30+C31+C32+C33=8 正确答案：8 【提示】

函数概念中，有两点尤其要注意．第一，是函数的单值性，即对于A中任何元素，必须有B中元素映射 f 唯一对应；第二，是函数的定义域，即A是函数 f 定义域

[例2] 判断说明：设N、R分别为自然数集与实数集，f：N→R，f (x)=x+6，则 f 是单射． [答案]：正确 [分析]

设x1，x2为自然数且x1≠ x2，则有 f(x1)= x1+6 ≠ x2+6= f(x2)，故 f 为单射．

【提示】

“单射”概念中，强调的是对于不同定义域中的值，通过函数映射得到的对应值不同，这种“一对一”是从前到后的一对一，并不要求从后到前一对一．

[例3] 设A={a，b}，B={1，2}，R1，R2，R3是A到B的二元关系，且R1={ , }，R2={,, }，R3={, }，则（ ）不是从A到B的函数． A．R1和R2 B．R2

C．R3 D．R1和R3 [答案]：B [分析]

函数的概念中，强调两点：第一，函数的单值性，即对于每一个定义域中的值，只能有一个对应函数值；第二，函数的定义域必须为集合A．本题中的R2不符合函数概念强调的第一点．

（1）偏序关系

设R是非空集合A上的二元关系，如果R是自反的、反对称的和传递的，则称R是A上的偏序关系或者简称序关系．偏序关系记作≤．∈≤，则称a小于等于b，记作a ≤ b． （2）哈斯图 作图规则：

i．去掉每个结点的自回路，用空心点表示集合的元素；

ii．对于集合任意元素a和b，若a≤b，则将a画在b的下方；

iii．对于集合任意元素a和b，若a

一个子集的极大(小)元可以有多个，而最大(小)元若有，只能惟一；且极元、最元只在该子集内；而上界与下界可在子集之外确定，最小上界是所有上界中最小者，最小上界再小也不会小于子集中的任一元素；可以与某一元素相等，最大下界也是同样．

[例1] 若偏序集 的哈斯图如所示，则集合A的最大元为a，最小元不存在． [答案] 错误

集合A的最大元不存在，a是极大元． 若a为最大元，则对于任意x∈A，必有 ∈R，但从图中可以得知， R，因此a不是最大元．同时，不存在x∈A，满足 ∈R，因此，a为极大元．

【易错点】

哈斯图不是简单的层次关系图，不要用层次关系判断最大元、最小元、极大元、极小元等． 【提示】

最小元应小于等于其它各元素；最大元应该大于等于其它各元素；极小元应该小于等于一些元素，而与剩下的元素没有关系；极大元应该大于等于一些元素，而与剩下的元素没有关系．最大元和最小元不一定存在，如果存在则必定唯一.

[例2] 设集合A={1，2，3，4，5}，偏序关系≤是A上的整除关系，则偏序集 上的元素5是集合A的（ ）. A．最大元 B．极大元

C．最小元 D．极小元 [答案] B

由于元素4和5没有整除关系，显然5不是最大元．

同理，5和2没有整除关系，5也不是最小元． 【提示】

整除关系是常考的一类偏序关系．两个元素是否具备整除关系可以不直接表达，所以题型描述简单，但是同学们需要将序关系的概念应用到此类题目中才能正确辨别．

第3章是图论的基础部分，主要介绍图论的基本概念与结论，包括图的基本概念、图的连通性与连通度、图的矩阵表示等.经常涉及到的题型有：

已知点集和边集画图，求结点的度数，画补图 握手定理计算题

强分图（连通）、单向分图（连通）、弱分图（连通）的判断 求点割集，割点，边割集，割边

无向简单图，已知点集和边集求邻接矩阵

我们将反映对象及其相互关系的图分为无向图和有向图，那我们就仔细了解一下它们，以及它们的区别、联系：

1. 无向图是一个有序的二元组，记作G＝ ，其中V≠称为顶点集，其元素称为顶点或结点；其中E称为边集，其元素称为无向边，简称为边.

2. 有向图是一个有序的二元组，记作G＝ ，其中V≠称为顶点集，其元素称为顶点或结点；其中E称为边集，其元素称为有向边，简称为边. 小提示：

① 用图形表示无向图和有向图时，用小圆圈表示顶点，用顶点之间的连线表示无向边，用有方向的连线表示有向边.

② 在无向图中，与结点相关联的边的条数，称为该结点的度数，记作deg(V)，用Δ(G)表示最大度，用δ(G)表示最小度.

③ 在有向图中，对于任何结点，出度就是以其为始点的边的条数，入度就是以其为终点的边的条数，出度与入度之和称为该结点的度数.

④ 如果图G与图H互为补图，则它们的顶点集相同，且它们的边集的并集等于其完全图的边集.

[例1]设图G＝，V＝{ v1，v2，v3，v4，v5}，E＝{ (v1, v2)，(v1, v3)，(v2, v3)，(v2, v4)，(v3, v4)，(v3, v5)，(v4, v5) }，试

（1）画出G的图形表示； （2）求出每个结点的度数； （3）画出图G的补图的图形． [解题过程] （1）关系图

先根据G的结点集画出图中的5个结点，这里的结点按逆时针排列，也可以按顺时针排列.再根据边集，在邻接的结点间将边画出.

（2）在图示中观察每个结点连接的边数，计算出各结点的度数. deg(v1)=2 deg(v2)=3 deg(v3)=4

deg(v4)=3 deg(v5)=2 （3）补图

补图的结点集与原图的结点集相等，补图的边集是那些由结点集确定的完全图中去掉原图中的边所留下的边组成

的.补图的边数＝完全图的边数－原图的边数.又因为5个结点的完全图的边数为条

条.所以10－7＝3

[例2] 设G是一个n阶无向简单图，n是大于等于2的奇数．证明G与中的奇数度顶点个数相等(补图)．

[证明过程]分析]

因为握手定理：结点度数之和等于边数的2倍，所以图G的结点度数总和一定是偶数. 又因为n是奇数，图G有奇数个结点，所以n阶完全图每个顶点度数为偶数. 因此，奇数＋奇数＝偶数，若G中顶点v的度数为奇数，则在补图中的奇数度顶点个数相等． 【提示】

补图与原图的结点集相等，补图与原图的边数之和等于其结点的完全图的边数.

是G的

中v的度数一定也是奇数，所以G与

那么在考试中是怎样考的呢？我们来看2道历年真题：

[例1] 设图G＝，vV，则下列结论成立的是 ( ) ． （2008年9月试卷第2题） A．

B．

C． D．

[答案]：Ｃ [分析]

选项A，不对.

因为没有连加符号∑，不能表示所有度数之和. 选项B，不对.

不但没有连加符号∑，而且边数

也没有乘以2.

选项C，正确. 有连加符∑，还有边数 选项D，不对.

乘以2.表示所有的度数之和等于边数的2倍.

没有将边数也没有乘以2.

【提示】 不论图中有奇数个结点或者偶数个结点，图的度数之和都是偶数.

【易错点】 同学们容易忘记将边数乘以2倍，容易忘记表示所有度数之和的连加符号. [例2] 设G是一个图，结点集合为V，边集合为E，则G的结点度数之和为_________ ． [答案]2（或“边数的两倍”）

[分析]

根据握手定理，在图中所有结点的度数之和等于边数的2倍.

【提示】

不论图中有奇数个结点或者偶数个结点，图的度数之和都是偶数

那么在考试中是怎样考的呢？我们来看2道历年真题：

[例1] 设有向图（a）、（b）、（c）与（d）如图一所示，则下列结论成立的是 ( )．

（2009年1月试卷第2题）

A．（a）是强连通的 B．（b）是强连通的

C．（c）是强连通的 D．（d）是强连通的 [答案] Ｄ [分析]

选项A，不对.

（a）图存在一点（左下角点）不可达其它点，所以不是强连通图.但图存在一点（左上角点）可达其它各点，所以是单向连通图，也是弱连通图. 选项B，不对.

b）图存在一点（右上角点）不可达其它点，所以不是强连通图.但图存在一点（右下角点）可达其它各点，所以是单向连通图，也是弱连通图. 选项C，不对.

（c）图存在两点（右上和左下角点）不可达其它点，所以不是强连通图.但图略去边的方向后，是连通图，所以是弱连通图.

选项D，正确.

（d）图中任何两结点互相可达，所以是强连通图，当然也是单向连通图和弱连通图. 易错点】

同学们要完全理解弱连通图、意向连通图、强连通图的概念，不能将它们混淆. 【提示】

强连通图一定是单向连通图和弱连通图；单向连通图一定是弱连通图.反之，不成立.

[例2] 判断下图是哪类连通图.

⑴ ⑵ （3）

[解题过程]

（1）存在V1点，可达其它各点V2 、V3、V4，所以是单向连通图.但图中V3点不可达其它点，所以不是强连通图.

（2）略去边的方向后，不是连通图，所以不是任何连通图. （3）存在V1点，可达其它各点V2、V3、V4. 存在V2点，可达其它各点V1 、V3 、V4. 存在V3点，可达其它各点V1 、V2 、V4. 存在V4点，可达其它各点V1、V2、V3.

因此，任何两结点都可达，所以是强连通图 【提示】

强连通图一定是单向连通图和弱连通图；单向连通图一定是弱连通图.反之，不成立.

那么在考试中是怎样考的呢？我们来看2道历年真题：

[例1] 如图一所示，以下说法正确的是 ( )． （2008年9月试卷第4题） A．e是割点 B．{a, e}是点割集 C．{b, e}是点割集 D．{d}是点割集

[答案] Ａ [分析]

选项A，正确.

去掉点e和其连接的边后，图就不连通了. 选项B，不对． 虽然去掉点ａ、点e和其连接的边后，图就不国通了.但是单单去掉点e和其连接的边后也可以不连通，所以不应该包括点a． 选项C，不对.

虽然去掉点b、点e和其连接的边后，图就不连通了.但是单单去掉点e和其连接的边后也可以不连通，所以不应该包括点b.

选项D，正确.

去掉点d和其连接的边后，图依然连通.

【提示】

点割集里只有一个结点时，这个结点才是割点.

【易错点】

同学们要准确地确定点割集里的结点，不能含多余的结点.

[例2] 如图一所示，以下说法正确的是( ）． （2010年7月试卷第4题） A．｛（a，e）｝是割边 B．｛(a, e)｝是边割集 C．{（a，e） ,（b，ｃ）}是边割集 D．｛(ｄ, e)｝是边割集 [解题过程] [分析]

选项A，不对.

去掉边（a，e）后，图依然连通.而且{（a，e）}是集合. 选项B，不对.去掉边（a，e）后，图依然连通. 选项C，不对.

去掉边（a，e），（b，c）后，图依然连通.

选项D，正确.

去掉边（d，e）后，图就不连通了. 【提示】

边割集里只有一条边时，这条边才是割边． 【易错点】

同学们要准确地确定边割集里的边，不能含有多余的边．

[例1]已知图G的邻接矩阵为

则则G有（ ）. （2008年7月试卷第5题）

A．5点，8边 B．6点，7边 C．6点，8边 D．5点，7边

[解题过程] 选项A，不对。

因为无向图的邻接矩阵的上三角矩阵数字之和为7，所以边数为7。 选项B，不对。

因为邻接矩阵是5×5方阵，所以图的结点数为5个。 选项C，不对。

因为邻接矩阵是5×5方阵，所以图的结点数为5个。

因为无向图的邻接矩阵的上三角矩阵数字之和为7，所以边数为7。 选项D，正确。

【提示】

n个结点的邻接矩阵为n×n矩阵，即n行n列矩阵.

【易错点】

有向图的邻接矩阵里所有的数字之和等于边数.而因为无向图忽略了方向，所以无向图的邻接矩阵的上三角矩阵数字之和或者下三角矩阵数字之和才是边数.不要混淆．

[例2]设G＝，V＝{ v1，v2，v3，v4}，E＝{ (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4) }，试写出其邻接矩阵. [解题过程]

图G有4个结点，则G的邻接矩阵为4×4矩阵，按结点的序号排序，根据结点间的邻接关系，确定邻接矩阵中的对应数值。边（v1，v3）对应的位置为1，边（v2，v3）对应的位置为1，边（v2，v4）对应的位置为1，边（v3，v4）对应的位置为1.又因为是无向图，所以边没有方向，因此在（v3，v1）（v3，v2），（v 4，v2），（v4，v3）的位置也是1.其余的位

置由于没有边，因此为0.

邻接矩阵： 【提示】

n个结点的邻接矩阵为n×n矩阵，即n行n列矩阵。无向图的邻接矩阵是对称矩阵.

第1章主要介绍集合论的基本概念和结论，集合的运算及其性质，以及利用运算性质进行集合表达式的化简和集合恒等式的证明等内容．考试经常涉及到的题型有以下4个：

欧拉通路、欧拉图的判别方法 汉密尔顿图的判断方法

平面图的判断方法

（1）定义的要点：图Ｇ满足无向，连通，经过每条边一次且仅一次，经过每个结点（注意：点可重复经过，边不能重复经过），这四点缺一不可．

如果同时满足这四点，当始点与终点不重合时，就是欧拉通路． 如果同时满足这四点，当始点与终点重合时，就是欧拉图． （2）欧拉图判定定理的要点：无向、连通图Ｇ是欧拉图的（充要条件是）Ｇ不含奇数度结点． 若无向、连通图Ｇ是欧拉图，那么Ｇ一定不含奇数度结点．

反之，若无向、连通图Ｇ不含奇数度结点，那么Ｇ一定是欧拉图． （3）欧拉通路判定定理的要点：无向、连通图Ｇ是欧拉通路的（充要条件是）Ｇ不含奇数度结点或只含2个奇数度结点．当Ｇ不含奇数度结点时，Ｇ是欧拉图 ．

若无向、连通图 是欧拉通路，那么 不含奇数度结点或只含2个奇数度结点．

反之，若无向、连通图Ｇ不含奇数度结点或只含2个奇数度结点，那么Ｇ一定是欧拉通路．当Ｇ不含奇数度结点时，Ｇ是欧拉图．

那么在考试中是怎样考的呢？我们来看5道历年真题：

[例1] 若集合A的元素个数为10，则其幂集的元素个数为( )．

A．ｍ为奇数 B．ｎ为偶数

C．ｎ为奇数 D．ｍ为偶数 [答案]：C [分析]

关键：无向完全图的总度数为，平均每个结点的度数为，如果中存在欧拉图，则每个结点的度数为偶数，于是ｎ为奇数．

知识点：根据欧拉图定义，每个结点的度数都是偶数，不含奇数度结点，完全图是连通图． [例2] 无向图Ｇ存在欧拉回路，当且仅当Ｇ连通且_________ [答案]：所有结点的度数全为偶数

[分析]

关键：欧拉图判定定理的要点：连通、不含奇数度结点． 知识点：欧拉图判定定理：无向连通图Ｇ是欧拉图的（充要条件是）Ｇ不含奇数度结点．

[例3]判断下列各题正误，并说明理由． （2008年9月试卷第15题） 如图1所示的图G存在一条欧拉回路.

均

[答案]：正确． [分析]

关键：欧拉图判定定理的要点：连通、不含奇数度结点． 知识点：欧拉图判定定理：无向连通图G是欧拉图的（充要条件是）G不含奇数度结点．

因为图Ｇ为连通的，且结点的度数分别为2,4,4,4,4，均为偶数，不含奇数度结点，所以Ｇ存在一条欧拉回路． [例4]判断下列各题正误，并说明理由． （2008年7月试卷第6题） 如图所示的图Ｇ存在一条欧拉回路．

[答案]：错误.因为图G为中包含度数为奇数的结点.

[分析]

关键：欧拉图判定定理的要点：连通、不含奇数度结点．

知识点：欧拉图判定定理：无向连通图是欧拉图的（充要条件是）G不含奇数度结点．． [例5]]判断下列各题正误，并说明理由．

如果图G是无向图，且其结点度数均为偶数，则图G是欧拉图 [答案]：错误.因为题中的图G缺少连通的条件.

[分析]

关键：根据欧拉图定义，缺少连通的条件．当图不连通时，图Ｇ不是欧拉图． 知识点：欧拉图的要点是：连通、无向图、不含奇数度结点．本题缺少连通条件．

【易错点】

容易漏掉欧拉图的部分要点．

（1）定义的要点：图Ｇ存在一条路，经过每个结点一次且仅一次． 在满足定义的条件下，若这条路是回路，则图Ｇ是汉密尔顿图．． 在满足定义的条件下，若这条路不是回路，则图Ｇ是汉密尔顿通路． （2）定理4.2.1：如果图中具有一条汉密尔顿回路（即汉密尔顿图），则对于Ｖ的每个非空子集

S，均有其中是的连通分支

也就是说，从图G中去掉若干个结点（至少一个结点），得到的连通分支数（即连通图数）不大于去掉的点数.。

[例1]若图

中有一条汉密尔顿回路，则对于的G每个非空子集S，在G中删除非空子集中的所有结点得到的

与W满足关系式__________．

连通分支数为W，则S中的结点数

[答案]：

[分析]

关键：记住定理4.2.1的条件和结论． 知识点：定理4.2.1：如果图

，其中

【易错点】

容易机械记忆定理，用

中具有一条汉密尔顿回路（即汉密尔顿图），则对于Ｖ的每个非空子集Ｓ，均有

是

的连通分支．

表示分支数．

．

【提示】

本题叙述与定理叙述不同，这里是用Ｗ表示

[例2] 若Ｇ是一个汉密尔顿图，则Ｇ一定是( )

A．平面图 B．对偶图

C．欧拉图 D．连通图 [答案]：D [分析]

（1）汉密尔顿图定义：Ｇ存在一条回路，经过每个点一次且仅一次．

（2）连通图定义：对任意两点【提示】

，存在路径，使得一点达到另一点

汉密尔顿图定义要点：G存在一条回路，经过每个点一次且仅一次

．

，则

．

（1）定义的要点：任意两条边，除结点外没有任何交点．

（2）欧拉定理：连通平面图G的结点数为v，边数为e，面数为，则

（3）定理4.3.3：设G是一个有v个结点e条边的连通、简单、平面图，若那么在考试中是怎样考的呢？我们来看2道历年真题：

[例1] 设连通平面图G的结点数为5，边数为6，则面数为______________． 关键：利用欧拉定理：连通平面图G的结点数为v，边数为e，面数为

解 应填

．

分别表示G的结点数，边数和面数，则v，e和

，则

满足的关系式______________． ．

，则

．

[例2] 设G是连通平面图，v，e，

关键：利用欧拉定理：连通平面图G的结点数为v，边数为e，面数为

解 应填 ．

[例3] 设G是具有n个结点m条边k个面的连通平面图，则m等于______________． （2010年1月试卷第9题） 关键：利用欧拉定理：连通平面图G的结点数为n，边数为m，面数为k，则解 应填

．

．

一、题型分析

树是图论中的重要部分之一，其在计算机科学与技术领域有着广泛的应用，二叉树更是程序设计中的一种基本的数据结构.

本章主要介绍树、生成树、二叉树、树根、最优树等概念及相关的结论与算法，包括求最小生成树的Kruskal算法、构造最优树的Huffman算法以及前缀码的求法. 经常涉及到的题型有： 1.树叶与结点间的计算 2.画最小生成树并求其权

3.构造最优树（Huffman算法）并求其权 4.求前缀码

因此，在本章学习过程中希望大家要清楚地知道一些概念：

树 连通无简单回路的无向图G. 树中次数为1的顶点称为树叶．次数大于1的顶点称为分支点或内部顶点． 森林 一个无向图称为森林，如果它的每个连通分图都是树． 树的判别 给定图T，则以下命题关于图T为树的定义等价． (1) T是无回路的连通图；

(2) 图T无回路且e＝v－1，其中e是边数，v是顶点数； (3) 图T连通且e＝v－1；

(4) 图T无回路，若增加一条新边，得到且仅得到一个回路； (5) 图T连通，但删去任一边后图便不连通（v≥0）； (6) 图T的每一对顶点之间有且仅有一条路（v≥0）．

生成树 给定一个无向图G，若G的一个生成子图T是树，则称T为G的生成树或支撑树．T的边称为树枝． 生成树的结论 任何连通图至少有一棵生成树．

权与带权图 n个结点的连通图G，每边指定一正数，称为权，每边带权的图称为带权图．G的生成树T中树枝的权之和称为T的权，记作W(T)．

有向树 如果一个有向图在不考虑边的方向时是一棵树，那么该有向图就是有向树．

根树与树根 一棵有向树T，若恰有一个顶点的入度为0，其余顶点的入度都为1，则称T为根树；入度为0的顶点称为树根；出度为0的顶点称为树叶；入度为1出度不为0的顶点称为内点；根与内点统称为分支点；从树根到T的任一顶点v的通路（顶点不同的路）的长度称为v顶点的层数；层数最大的顶点的层数称为树高．

[例1] 设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去 条边后使之变成树．

【答案】4 【分析】

运用教材中的 定理5.1.1，可以作出正确选择．因为定理5.1.1中给出的图G为树的等价定义之一是图G连通且e＝v-1（e是边数，v是顶点数）．若图G变为树，则边数e＝6-1＝5。由于题中结点的总度数为18，根据定理3.1.1，总度数应为边数2倍，可知此图中有边数9条。所以应该删去9-5＝4条边才能使图G 是树。

【易错点】

大家对集合中有的元素用集合形式表示的情形容易混淆，但这种类型考题中经常出现，大家一定要习惯．本题主要是检查大家对属于关系∈和包含关系?是否理解，能否正确运用。

【提示】

首先检查各选项给出的关系符号∈和?左边的式子是集合A的元素还是子集，然后判断选项中使用的关系符号是否正确，确定选项。

[例2] 已知一棵无向树T中有8个结点，4度，3度，2度的分支点各一个，T的树叶数为 ． [答案] 5 [分析]

设无向树T的树叶数为x，因为树叶是度数为1的结点．

那么，由定理3.1.1（握手定理）设G是一个图，其结点集＝－合为V，边集合为E，则

得： 4+3+2+x=2（8-1），即x=5．应填5． 【易错点】

题中没有直接给出图Ｇ的边数，而是给出了结点的总度数，这里大家要清楚总度数和边数之间的关系。

【提示】

设G是有ｎ个结点，ｍ条边的连通图，必须删去Ｇ的( m-n+1 )条边，才能确定G的一棵生成树

求最小生成树的方法主要有避圈法与破圈法．那到底什么是避圈法和破圈法？我们一起来看一看： 避圈法：图G有n个顶点，以下算法产生的是最小生成树（避圈法由kfuskal给出. （1）选择最小的边e1，置边数i←1； （2）i=n-1结束，否则转3）；

（3）设定已选定e1 ，e2,，…，ei，，在G中选取不同于e1，e2,，…，ei的边ei+1，使{ e1，e2,，…，ei，ei+1}无回路，且ei+1是满足此条件的带权最小的边； （4）i←i+1，转2）． ? 破圈法：

（1）初始令 G0,= G, i←0；

（2）若Gi中不含圈，则转（3）；否则，设C为Gi中的一个圈，ei为C上带权最大的边，令Gi+1= Gi - ei ； i← i+1，转（1）．

（3）结束．

结束时G中的图为最小生成树。

最小生成树的权等于最小生成树各边权值的和。

[例1] 图G=，其中V={ a, b, c, d, e}，E={ (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (c, d), (d, e) }，对应边的权值依次为2、1、2、3、6、1、4及5，试

（1）画出Ｇ的图形； （2）写出Ｇ的邻接矩阵；

（3）求出Ｇ权最小的生成树及其权值． [解题过程]

（1）因为V={ a, b, c, d, e}，E={ (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (c, d), (d, e) }，对应边的权值依次为2、1、2、3、6、1、4及5，则G的图形表示为：

（2）根绝邻接矩阵的定义，写出邻接矩阵为： （3）用避圈法： 第1步：选(a, b)边； 第2步：选(a c)边； 第3步：选(c, e)边； 第4步：选(b, d)边．

这样，得到了最小的生成树，如下图中粗线所示． 最小的生成树的权为2+1+1+3=7．

【提示】 求最小生成树可以利用避圈法或者破圈法．

求最小生成树的权就是各边权值之和

设T是一棵根树，若T的每个分支点的出度至多为m，则称T为m叉树；若T的每个分支点的出度恰好等于m，则称T为m叉正则树；若T是m叉正则树，且每个树叶的层数均为树高，则称T为完全m叉正则树；若T是m叉树且为有序树，则称T为m叉有序树；若T是m叉正则树且为有序树，则称T为m叉正则有序树；若T是m叉完全正则树且为有序树，则称T为m叉完全正则有序树；若m=2，则T称为二叉树．

带权二叉树 ?给定一组权w1，w2，…，wt，不妨设w1≤w2≤…≤wt．设有一棵二叉树，共有t片树叶，分别带权w1，w2，…，wt，则该二叉树称为带权二叉树．

最优树? 设在有t个树叶的带权二叉树T中，带权为wi (i=1,…,t)的树叶，其通路长度为L(wi)，则将w(T) =?wiL(wi) (i=1,…,t)称为该带权二叉树的权．在所有带权w1，w2，…，wt的二叉树 中，w(T)最小的树称为最优树．

用Huffman算法得到的最优树． （Huffman）：设T为带权w1

≤w2≤…≤wt的最优树，若将以带权w1，w2的树叶为儿子的分枝点改为带权w1+w2的树叶，得到一棵树T’，则T’也是最优树．

最优树的权：每片树叶的权乘以它到树根的长度取和

正则m叉树结论? 设有正则m叉树，其树叶数为t，分枝数为i，则(m-1)i=t-1．

[例1] 画一棵带权为1, 2, 2, 3, 4的最优二叉树,计算它们的权 [解题过程]

Huffman算法：从1, 2, 2, 3, 4中选1, 2为最低 层结点，并从权数中删去，再添上他们的和数，从 小到大排列，即2，3，3，4；

再从2，3，3，4中选2，3为倒数第2层结点， 并从上述数列中删去，再添上他们的和数，从小到

大排列，即3，4，5；

然后，从3，4，5中选3，4为倒数第2层结点，

并从上述数列中删去，再添上他们的和数，从小到大排列， 即5，7；……

最优二叉树如右图所示。

最优二叉树权值为：1×3+2×3+2×2+3×2+4×2=27

【提示】

最优树的权：每片树叶的权乘以它到树根的长度取和

在求前缀码前，我们需要了解何为前缀码: 给定一个序列集合，若没有一个序列是另一个序列的前缀，该序列集合称为前缀码．

结论：任何一棵二叉树的树叶可对应一个前缀码． 任何一个前缀码都对应一个二叉树

【提示】

最优树的权：每片树叶的权乘以它到树根的长度取和．

[例1] 给定一个序列集合{000，001，01，10，0}，若去掉其中的元素 ，则该序列集合构成前缀码． 【答案】 0 【分析】

根据定义5.2.10 给定一个序列集合，若没有一个序列是另一个序列的前缀，则该序列集合为前缀码。

本章主要介绍命题、联结词的概念，命题公式与翻译，真值表与等价公式，重言式与蕴含式，范式和命题逻辑的推理理论等内容。经常涉及到的题型有： 将陈述句翻译成命题公式 求命题公式的真值 命题公式类型的判断 等价公式的证明 求范式和主范式

判断有效结论的直接证法和间接证

因此，在本章学习过程中希望大家要清楚地知道：

命题表述为具有确定真假意义的陈述句．命题必须具备二个条件：语句是陈述句；语句有唯一确定的真假意义．因此判断一个句子是否为命题，应首先判断它是否为陈述句，再判断它是否有唯一的真值．

例如，“北京是中国的首都”是陈述句，有确定的真假意义，是命题，为真命题．

将陈述句翻译成命题公式关键在于陈述句的逻辑含义要与命题公式的逻辑含义保持一致。因此首先要注意陈述句中表示特殊逻辑关系的词语的含义，其次要掌握五个联结词“”所表示的命题间的逻辑关系：“

，，

，

，

” 是唯一一元联结词，表示否定；合取联结词“”在语句中相

当于“不但…而且…”，“既…又…”；析取联结词“”在语句中表示“或”的含义；条件联结词“”在语句中表示“如果P则Q”或“只有Q，才P”；双条件联结词“”在语句中相当于“…当且仅当…”．

例如，“我们不能划船，又跑步”。设P：我们划船，G：我们跑步，那么该命题符号化为：

或．

[例1] 将语句“他是学生．”翻译成命题公式． （2009年10月试卷第11题） [解题过程]

依据命题必须具备的二个条件，可设P：他是学生， 则该语句翻译成命题公式为： P． [例2] 将语句“今天没有人来．”翻译成命题公式． [解题过程]

依据命题必须具备的二个条件以及否定联结词“ 可设 P：今天有人来，

”的定义，

则语句“今天没有人来．” 翻译成命题公式为 P。

[例3] 将语句“如果所有人今天都去参加活动，则明天的会议取消．”翻译成命题公式．

[解题过程]

在该语句中出现表示逻辑关系的连词“如果…，则…”，这样我们就很容易联想到条件联结词“示“如果…，则…”，但要注意的是，似乎P

”在语句中表

Q是“因果关系”，但是不一定总有因果关系，只要P，Q是命题，

那么PQ就是命题(即有真值)，不管P，Q是否有无因果关系． 因此，设P：所有人今天都去参加活动， Q：明天的会议取消，

于是该语句可翻译成命题公式为： PQ．

[例4] 将语句“如果所有人今天都去参加活动，则明天的会议取消．”翻译成命题公式． [解题过程] P

Q表示的基本逻辑关系是，Q是P的必要条件，P是Q的充分条件，因此复合命题“只要P，就Q”，

Q的形式．

“P仅当Q”，“只有Q才P”等都可以符号化为P 因此可设P：我去旅游， Q：我有时间，

则语句“我去旅游，仅当我有时间．”翻译成命题公式为：PQ． [例5] 将语句“小王去旅游，小李也去旅游．”翻译成命题公式． [解题过程]

合取联结词“”在语句中相当于“并且”，“不但…而且…”，“既…又…”．但要注意“”与 “并且”等是有区别的，“并且”等要考虑语义，而“合取”只考虑命题之间的关系以及复合命题的取值情况，不考虑语义． 因此，可设P：小王去旅游， Q：小李去旅游，

则语句“小王去旅游，小李也去旅游．”翻译成命题公式为：PQ．

一般将命题的合式公式简称为命题公式．要理解合式公式的递归定义： （1）单个命题变元本身是一个合式公式． （2）若A是合式公式，则┐A是合式公式．

（3）若A与B是合式公式，则（A∧B），（A∨B），（A→B）与（AB）是合式公式． （4）当且仅当能够有限次应用（1）、（2）、（3）所得到的包含命题变元，联结词和括号的符号串是合式公式．

显然，如果对一个命题公式中的命题变元不给以真值指派，则命题公式无真值可言．如果对命题公式中的每个命题变元都赋以真值（1或0），则命题公式就变成了一个有真值的命题，并可求出其真值．

对于特殊的命题公式（永真式和永假式），对命题公式中的命题变元不给以真值指派，利用常用的等价公式也可以求出其真值（永真式为1，永假式为0）．

对命题公式中的所有命题变元指派各种可能的真值组合，就可确定这个命题公式对应的取值，将命题变元的所有真值组合及命题公式对应的取值汇列成表，就得到命题公式的真值表．

如果一个命题公式有n个命题变元，那么命题变元的真值指派就可能出现种不同的组合．在真值表中是包含了命题变元的所有真值指派．例如，如果一个命题公式有3个命题变元，那么命题变元的真值指派就有8种不同的组合，作其真值表就是将这8种真值组合及命题公式对应的真值汇列成表．

要非常熟练地掌握命题公式的真值表作法，因为利用真值表可以判定命题公式类型，验证等价公式和蕴含式，求命题公式的主析取(合取)范式，在推理理论中判别有效结论． [例1] 命题公式的真值是_______ [解题过程]

依次利用蕴含等价式、结合律和零律，可将该命题公式化为：

因此该公式的真值是1。

对于命题的判断，存在着多种方法，也容易混淆，那我们来仔细分析一下他们的区分方法：

，

在各种真值指派下均为真的命题公式，称为重言式或永真式；在各种真值指派下均为假的命题公式，称为矛盾式或永假式；不是矛盾式的命题公式，称为可满足式。 判定命题公式类型的方法：

(1) 真值表法：任给命题公式，列出其真值表，若真值表的最后一列全为1，则该公式为永真式；若真值表的最后一列全为0，则该公式是永假式；若真值表的最后一列既非全1，又非全0，则该公式是可满足式。

(2) 等值演算法：利用常用的等价公式，对给定公式进行等值推导，若该公式的真值为1，则该公式为永真式；若该公式的真值为0，则该公式为永假式。既非永真，也非永假，则为非永真的可满足式。 那么在考试中是怎样考的呢？我们来看2道历年真题： [例1] 判断说明题（判断下列各题正误，并说明理由）

为永真

式． （2008年 7月试卷第14题） [答案] 正确． [分析]

因为联结词运算的优先次序为：

和否定律，对给定公式进行等值推导如下：

，再利用等价公式中的蕴含等价式，吸收律

因此该公式是永真式。

以上是利用等值演算法判断公式的类型，也可利用如下真值表法。

由真值表可见该公式在任意真值指派下的真值都是1，因此该公式是永真式。 [例2] 下列公式 ( )为重言式．

[答案] C [分析]

选A．错误. 因为利用蕴含等价式，可将词的定义可知选B．错误.

为矛盾式。

化为

即

，依据等价联结

因为利用蕴含等价式、分配律和结合律，可将化为

而用分配律和否定律得

依据等价联结词的定义可知选C．正确.

为可满足式。

因为利用蕴含等价式可将化为

。再依据等价联结词的定义可知该式为重言式。

，再利用结合律得

选D．错误. 因为利用分配律可将

依据等价联结词的定义可知

化为

为可满足式。

等价公式：给定两个命题公式A与B，设P1，P2，…，Pn为所有出现于A与B中的原子变元，若给P1，P2，…，Pn任一组真值指派，A与B的真值均相同，则称公式A与B是等价的或逻辑相等，记作，此公式可称为等价公式。

真值表法（验证公式等价）：将两个命题公式的真值表列出，在所有的真值指派下，两个公式的真值都对应相同，则说明两个公式等价，否则，就不等价。

等值演算法（证明公式等价）：利用教材182页的14个基本等价式对给定公式进行等值演算，可以证明命题公式等价。

那么在考试中是怎样考的呢？我们来看2道历年真题： [例1] 下列等价公式成立的为( )．

[答案] B [分析]

选A．错误.

因为依据德·摩根律， ，所以选B．正确.

因为依次利用蕴含等价式、分配律和蕴含等价式可得，

不等价 。

选C．错误.

而

其真值不等于1。

因为依次利用蕴含等价式、结合律、否定律和零律可得，

选D．错误.

因为依次利用分配律、否定律和同一律可得，

显然与Q不等价。

[例2] 下列公式成立的为( )。

[答案]D [分析]

选A．错误. 因为依据德·摩根律, 选B．错误.

（2010年 1月试卷第5题）

因为利用蕴含等价式可得，选C．错误.

因为 是一个蕴含式，依据蕴含的定义，该蕴含式成立只需证明蕴含等价式、分配律、否定律和同一律，

为重言式即可。依次利用

显然结果不是重言式，因此选D．正确.

不成立。

为真时，Q一定为真。

也可以利用直接证法来证明该蕴含式，思路是：证明

求范式和主范式，它们之间有什么区别呢，又应该怎么去求呢？我们一起来看一看：

求范式，包括求析取范式、合取范式、主析取范式和主合取范式。关键有两点：其一是准确掌握范式定义；其二是巧妙使用基本等价式中的分配律、同一律和摩根律，结果的前一步适当使用幂等律．

范式的相关定义有：

合取范式：一个命题公式称为合取范式，当且仅当它具有形式： A1∧A2∧…∧An ， （n1）

其中A1，A2，…，An均是由命题变元或其否定所组成的析取式． 析取范式：一个命题公式称为析取范式，当且仅当它具有形式： A1∨A2∨…∨An ， （n1）

其中A1，A2，…，An均是有命题变元或其否定所组成的合取式．

布尔合取、小项：n个命题变元的合取式，称为布尔合取或小项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次． 一般n个命题变元共有个小项．

布尔析取、大项：n个命题变元的析取式，称为布尔析取或大项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次． 一般n个命题变元共有个大项．

主析取范式：对于给定的命题公式，若有一个等价公式，它仅仅由小项的析取组成，则该等价式称为原式的主析取范式．

主合取范式：对于给定的命题变元，如果有一个等价公式，它仅仅由大项的合取组成，则该等价式称为原式的主合取范式． 求析取(合取)范式的步骤： ① 将公式中的联结词都化成

② 将否定联结词消去或移到各命题变元之前；

③ 利用分配律、结合律等，将公式化为析取(合取)范式． 求主析取范式(主合取范式)的方法：

真值表法：在命题公式的真值表中，真值为1的指派所对应的小项的析取，为此命题公式的主析取范式；在命题公式的真值表中，真值为0的指派所对应的大项的合取，为此命题公式的主合取范式．

等值演算法：利用等价公式，求命题公式A的主析取(合取)范式的步骤： ① 将公式A化为析取(合取)范式；

② 除去析取(合取)范式中永假(永真)的析取 (合取) 项，并将析取(合取)式中重复出现的合取项(析取项)和相同变元合并.

③ 对于不是小项（大项）的合取（析取）式，补入没有出现的命题变元，即通过合取（析取）添加

式，然后利用分配律展开公式．

．

一般地，若命题公式A的主析取范式为则A的主合取范式为

由此可见，命题公式A的主析取范式的小项个数与主合取范式的大项个数之和等于 [例1]求

的析取范式、合取范式、主析取范式、主合取范式．

（2008年7月试卷第

17题） [解题过程]

依据求析取(合取)范式的步骤可得，

（析取范式、合取范式、主合取范式）

因此该公式的主析取范式对应的小项为： 故该公式的主析取范式为：

此外，我们也可利用真值表法求该命题公式的主析取范式和主合取范式． P 0 0 0 0 1 1 1 1 Q 0 0 1 1 0 0 1 1 R 0 1 0 1 0 1 0 1 PQR 1 1 1 1 0 1 1 1 小项 ┐P∧┐Q∧┐R ┐P∧┐Q∧R ┐P∧Q∧┐R ┐P∧Q∧R P∧┐Q∧R P∧Q∧┐R P∧Q∧R 大项 ┐P∨Q∨R

表中所有小项的析取就是公式的主析取范式，所有大项的合取就是公式的主合取范式，从真值表中可以看出所得结果与用上述等值演算法所得结果相同．

[例2] 命题公式（P∨Q）→R的析取范式是 ( )

（2008年9月试卷第3题）

[答案]D [分析]

依据求析取范式的步骤可得， 这就是命题公式（P∨Q）→R的析取范式，虽然命题公式的析取范式不唯一，但这个结论与选项D相同，故选择D。

[例3] 试求出（P∨Q）→R的析取范式，合取范式，主合取范式．

（2009年1月试卷第

16题）

判断有效结论的方法有哪些？究竟什么是直接证法和间接证法，我们该如何去理解？让我们一起来看一看： 判断有效结论的过程就是论证过程，基本方法有真值表法、直接证法和间接证法。要重点掌握后两种方法．

直接证法：就是由一组给定的前提，利用一些公认的推理规则，并根据已知的等价公式和蕴含公式，推演得到有效结论的方法．

在证明过程中一般要用到的两个公认的推理规则，即P规则与T规则． P规则：前提在推导过程中的任何时候都可以引入使用．

T规则：在推导中，如果有一个或多个公式重言蕴含着公式C，则公式C可以作为前提在推导引用．

因此要掌握直接证法，就必须理解并掌握好教材第182页的14个等价公式和14个蕴含公式，并会使用P规则和T规则．

将证明的过程用三列的形式表示，第一列为序号，第二列为当前得到的结论，第三列为得到当前结论的理由或根据．E与I分别表示已经证明成立的等价式与蕴含式．

间接证法：有两种，一种为反证法，是由不相容的概念引出的一种间接证法．

相容、不相容：假设公式H1，H2，…，Hm中的命题变元为P1，P2，…，Pn，对于P1，P2，…，Pn的一些真值指派，如果能使H1∧H2∧…∧Hm的真值为T，则称公式H1，H1，…，Hm是相容的．如果对于P1，P2，…，Pn的每一组真值指派，使得H1∧H2∧…∧Hm的真值为F，则称公式H1，H2，…，Hm是不相容的． 其证明思路就是，如要证明，只要把作为前提使用，推出矛盾的结论即可．

另一种间接证法就是附加前提证明法：该方法使用的前提是有效结论以蕴含的形式出现，即具有这样的形式。则把B作为附加前提使用，只要推出结论C即可。即证明。通常将此方法称为CP规则．

[例1] 试证明（Ｐ∧Ｑ）→Ｒ，┐Ｒ∨Ｓ，┐ＳT ┐Ｐ∨┐Ｑ． [分析]

结论是┐Ｐ∨┐Ｑ，先从远离结论的前提┐Ｓ（或者┐Ｒ∨Ｓ）出发引入第一个前提┐Ｓ，然后根据析取三段论再引入一个含有Ｓ的前提┐Ｒ∨Ｓ（或者┐Ｓ），这样就可以去掉Ｓ了，只剩下Ｒ了，再引入一个含有Ｒ的前提（Ｐ∧Ｑ）→Ｒ，就又可以去掉Ｒ了，只剩下含有Ｐ、Ｑ了，这正是结论所需要的．

[证明过程] (直接证法)

① ┐Ｓ P ② ┐Ｒ∨Ｓ P

③ ┐Ｒ T ①② I ④ (Ｐ∧Ｑ)→Ｒ P ⑤ ┐Ｒ→ ┐(Ｐ∧Ｑ) T④I ⑥ ┐(Ｐ∧Ｑ) T③⑤I ⑦ ┐Ｐ∨┐Ｑ T⑥E

【提示】

判断有效结论的直接证法和间接证法，它的理论根据是14个等价公式（P167），14个蕴含式(P170-171)，三个规则(P规则、T规则和CP规则)。在这些公式中，我们并不需要全部记住，记住最基本的即可，在这些公式中，下列这些式子是最基本的和最常用，其它公式有的可以根据它推导出来。14个蕴含式中最常用和最基本的式子有(1)，(2)，(3)，(8)，(10)，(11)。14个等价式中（12）, （14）式用得较少。利用直接证明法和间接证明法来证明，一个关键问题就是在多个前提条件下，不知道按什么顺序来引入前提？一般的来说是根据析取三段

论（或假言推理）（即教材P170第（9）、（10）式），即一个前提中含有A，再引入一个含有A的前提，就可以去掉A了。这样我们可以先从远离结论的前提入手，逐步推导出结论．

本章主要介绍谓词逻辑的基本概念、基本定理与方法等。经常涉及到的题型有： 谓词公式的翻译

求辖域、约束变元、自由变元、变元换名 在有限个体域下消去量词

谓词推理演算

谓词

用以描述个体的性质或个体间关系的语法模式称为谓词。谓词命名式是谓词与个体和个体变元结合的表示形式，谓词命名式也简称为谓词。

谓词一般用大写字母P、Q、R等表示，个体一般用小写字母a、b、c等表示，个体变元就一般用小写字母x、y、z等表示。

谓词可以写成P(x，y)、H(x，y，z)、F(x)等形式。

[例1] 将语句“有人去上课．”翻译成谓词公式． [解题过程] 设P(x)：x是人， Q(x)：x去上课． 则语句“有人去上课．” 翻译成谓词公式为：

【易错点】

有同学会误表示为

．

【提示】

用存在量词

来表明个体的取值量，对各个不同的个体应用描述个体特性的特性谓词P(x)来

加以约束限制时，特性谓词作为合取项加入．

[例2] 将语句“所有的人都学习努力．”翻译成谓词公式． [解题过程] 设P(x)：x是人， Q(x)：x努力学习．

则语句“所有的人都努力学习．” 翻译成谓词公式为：

【易错点】

有同学会误表示为

【提示】

用全你量词

来表明个体的取值量，对各个不同的个体应用描述个体特性的特性谓词P(x)

来加以约束限制时，特性谓词作为条件式的前件加入．

将表明个体取值量上的词“任意”、“所有的”、“全部”、“凡是”、“一切”等称为全称量词。全称量词用表示。

将表明个体取值量上的词“存在”、“有的”、“有些”、“至少有”等称为存在量词。存在量词用表示。

在书写谓词时，通常将个体变元的个体域定义为全总个体域，然后根据需要对各个不同的个体应用描述个体特性的谓词（称为特性谓词）来加以约束限制。 在谓词形式中，特性谓词的加入有两条规则：

(1) 对全称量词，特性谓词作为蕴含式（条件式）的前件加入。 (2) 对存在量词，特性谓词作为合取项加入。

即在命题符号化时要注意：使用全称量词，特性谓词后用；使用存在量词，特性谓词后用。

设G(x)是一元谓词，个体域为D，则 命题xG(x)的真值： xG(x)取1值当且仅当对任意x xG(x)取0值当且仅当有一个 命题xG(x)的真值： xG(x)取1值当且仅当有一个 xG(x)取0值当且仅当对任意x

D，G(x)都取1值。

D，使得G()取0值。

D，使得G()取1值． D，G(x)都取0值．

,试 （2008年9月试卷第[例1]设谓词公式 16题）

（1）写出量词的辖域；

（2）指出该公式的自由变元和约束变元． [解题过程] （1）量词的辖域为 第1个量词的辖域为 第2个量词的辖域为（2）

与中的x，

， ．

中的y，以及

，

中的z为自由变元．

中的y为约束变元．

中的z，以及

【易错点】

求辖域容易出错，要注意式中括号的配对．

【提示】

紧跟量词后面的个体变元为该量词的指导变元，在该量词的辖域中与指导变元相同的变元为约束变元，与指导变元不同的或不在任何量词的辖域中的变元为自由变元。

谓词公式可由下述各条规则组成： (1) 原子公式是合式公式。

(2) 若A是合式公式，则A是合式公式。

(3) 若A与B均是合式公式，则(AB)，(AB)，(A→B)，(AB)是合式公式。 (4) 若A是合式公式，x是A中出现的任何变元，(x)A与(x)A均是合式公式。 (5) 仅有限次应用规则(1)至(4)构成的公式为合式公式。 由上定义知，命题演算公式也是谓词合式公式。

在变元换名过程中，涉及到一系列的概念，下面我们一起来了解一下吧：

对于 (x)P(x) 或 (x)P(x) 形式的公式，或后面所跟的个体变元x称为相应量词的指导变元。

紧接于量词之后最小的子公式称为量词的辖域。

在量词的辖域内指导变元的一切出现均称为变元的约束出现。约束出现的变元称为约束变元。 在公式中，变元的非约束出现称为变元的自由出现。自由出现的变元称为自由变元。

约束变元的换名规则：对约束变元进行换名，即将量词辖域中出现的某个约束变元和相应的指导变元，换成另一个辖域中未曾出现过的变元符号，公式中的其余部分不变。

自由变元的代入规则：对自由变元进行代入，即对自由变元用与原公式中所有变元不同的符号去代替，并且处处代替。

那么在考试中是怎样考的呢？我们来看1道历年真题：

[例1] 下面的推理是否正确，试予以说明． （2009年7月试卷第13题）

[答案]：错误． [分析]

第2步应为：F(y)

前提引入

US（1）．

G(x)

因为F(x)中的x是约束变元，而G(x)中的x是自由变元，换名时，约束变元与自由变元不能混淆。

【易错点】

约束变元与自由变元容易混淆． 【提示】

详细过程应为：

当个体域为有限集合

[例1] 设个体域D={a,b}，则谓词公式

时，消去量词的规则为：

消去量词后的等值式为 ．

[答案]

[解题过程]

所以：

，

,

【易错点】

容易用错合取、析取符号

【提示】

当个体育域为有限集合：

时，消去量词的规则为：

推理理论

谓词演算的推理是命题演算推理的推广和扩充，命题演算中的基本等价式，重言蕴含式以及P规则、T规则、CP规则在谓词演算中仍然适用． 谓词逻辑中几个常用的等价式：

（注：子公式B中不出现约束变元x）

谓词逻辑的推理演算新增加了添加与消去量词的四条规则：

(1) 全称指定规则（全称量词消去规则），表示为US，即：

此规则是对量词约束的变元任意指定一个个体，其逻辑含义是，如果(任取个体域中某个任意的个体c，而P(c)也是成立的．

(2) 全称推广规则（全称量词附加规则），表示为UG，即：

x)P(x)成立，则可以

此规则是对使得谓词P成立的个体c进行推广，其逻辑含义是，如果对于个体域中任意的个体c，有P(c)成立，则(x)P(x)也成立。

(3) 存在指定规则（存在量词消去规则），表示为ES，即：

此规则是对量词约束的变元指定一个个体，其逻辑含义是，如果(某个个体c使得P(c)成立。

(4) 存在推广规则（存在量词附加规则），表示为EG，即：

x)P(x)成立，则个体域中有

此规则是对使得谓词P成立的个体c进行推广，其逻辑含义是，如果对于个体域中存在某个个体c，使P(c)成立，则(x)P(x)也成立。

[例1] 试证明 [证明过程]

Ｐ ES（1）

T（2）Ｉ(化简规则)

EG（3） T（2）Ｉ(化简规则)

EG（5）

T（4）（6）I 【易错点】

推理规则不易理解和掌握

【提示】

（1）式引入前提后，根据存在指定规则提到（2）式，根据化简规则得到（3）式、（5）式，再根据存在推广规则分别得到（4）式、（6）式，最后根据合取引入规则要证明的结果（7）式．

本文来源：https://www.bwwdw.com/article/ze6o.html