离散数学学习指导书

第1章 集 合

1.1 集合

1.1.1基本知识点：集合、元素、基数、包含、子集、集合相等、空集、全集、

幂集等。

基本理论：两个集合相等的充分必要条件是它们的元素相同；如果有限集合A

有n个元素，则幂集合2A有2n个元素。

基本计算：判断一个元素是否属于某个集合；判断两个集合是否具有包含关系；

求一个集合的幂集；

1.1.2重点与难点

(1) 集合与元素：集合是一个不能精确定义的基本概念，通常把具有某种共同性

质的事物归纳成一个整体，就形成一个集合，一般用大写字母

A,B,C等表示集合的名称。把组成集合的事物称为元素，一般

用小写字母a,b,c等表示。

(2)集合的表示方法：集合通常有两种表示方法，即列举法、描述法。 (3)包含与子集：对任意两个集合A和B，若对任意的a?A，必有a?B，则称A被B包含，或者B包含A，记作A?B。若A?B则称A是B的子集。

(4)空集、全集和幂集：不包含任何元素的集合称为空集，记作?。在一定范围

内所有集合均为某一集合的子集，则称该集合为全集，记为U。

由集合A的所有子集所构成的集合称为集合A的幂集，记为2A。 典型题解

例1：下面是用列举法表示的集合：

A?{sun，earth，moon} B?{a，b，c，?，z} C?{1，2，3，4，?}

有时列出集合中所有元素是不现实或不可能的，如上面的B和C，但只要在省略号前或后列出一定数量的元素，能使人们一看就能了解那些元素属于这个集合就可以。

例2：下面是用描述法表示的集合：

A?{x|x?Nx?1且x?1000} B?{x|x?R?x2?1?0}

1

例3：集合{a,a,b,b,c}与集合{a,b,c}没有区别，集合{a,b,c}与集合{c,b,a} 没

有区别，即{a,a,b,b,c}?{a,b,c}，{a,b,c}?{c,b,a}。

例4： 试证空集是唯一的。

证明：(1)假设存在空集?1和?2，由于空集是任何集合的子集，即

?1??2和?2??1；

这样，根据集合相等的定义就有?1??2，即空集是唯一的。

例5 设A?{a,b,c}，则A的子集有：0元子集1个：空集?；一元子集3个：

{a}{，b}{，c}；二元子集三个：{a,b}{，a,c}{，b,c}；三元子集一个：{a,b,c}。 所

以A的幂集为

2A?{?,{a},{b}{，c}{，a,b}{，a,c}{，b,c},{a,b,c}}

0 一般地说，对于含有n个元素的集合A，它的0元子集有Cn个，1元子集有m1n个，…，m元子集有Cn个，…，n元子集有Cn个。这样，根据二项式公 Cn式，子集的总数，也即是幂集的元素的个数为

012nCn?Cn?Cn???Cn?2n

1.2 集合的运算和文氏图

1.2.1基本知识点：

基本概念：集合的交、并、补、差和对称差运算、文氏图。 基本理论：集合的运算及其性质；补集的唯一性定理。

基本计算：计算集合的交、并、补、差和对称差等；用集合运算的性质判断两

个集合是否相等；用文氏图表示集合。

1.2.2重点与难点：

(1)集合运算的定义：AB?{x|x?A或x?B} AB?{x|x?A且x?B}

A??{x|x?E且x?A} A?B?A?B

A?B?(A?B)?(B?A)

(2)集合运算的性质：设A,B,C是全集U的任意子集，则

交换律：

结合律：

A?B?B?A，A?B?B?A (A?B)?C?A?(B?C)

(A?B)?C?A?(B?C)

分配律： A?(B?C)?(A?B)?(A?C)2

，

A?(B?C)?(A?B)?(A?C)

等幂律： A?A?A，A?A?A 同一律：A???A，AU?A 零一律：AU?U，A???? 互补律：AA??U，AA???

对合律：(Ac)c?A

吸收律：A?(A?B)?A，A?(A?B)?A

德·摩根律：(AB)??A?B?，(AB)??A?B?

(3)文氏图：

U A B U A B U

A A B

A A?BU A A?BU B A?A?BU A B A'A?BA?BA?B由文氏图容易看出下列关系成立：

A?B?A，A?B?B

A?A?B，B?A?B A?B?A，A?B?B?

A?B?A?B?B?A?B?A?A?B??

典型题解

例1设A?{a,b,c}，B?{a,x,y}，全集U?{a,b,c,x,y,z}，则

AB?{a,b,c,x,y}

A?B?{a} A??{x,y,z} A－B?{b,c}

A?B?{b,c,x,y}

例2证明分配律：A?(B?C)?(A?B)?(A?C)

3

证明：因为

x?A?(B?C) ?x?A或x?BC

?x?A或(x?B且x?C) ?(x?A或x?B)且(x?A或x?C)

?x?AB且x?AC ?x?(A?B)?(A?C)

所以A?(B?C)?(A?B)?(A?C)

例3 证明A?(B?C)?(A?B)?(A?C)

证明： x?A?(B?C)

?x?A且x?BC

?x?A且x?B?且x?C?

?(x?A且x?B?)且(x?A且x?C?)

?x?(A?B)且x?(A?C)

?x?(A?B)?(A?C)

1.3 分划和细分 1.3.1基本知识点：

基本概念：分划、分划块、细分、真细分。

基本理论：集合A的分划就是将集合A中的元素划分成几块，使得A的每一个元素必须

在某一块中，也仅在一块中。 基本计算：求集合的分划。

典型题解

例1 设A?{2,3,5,8,9,16,22,25,27,35}，按照A中元素是奇数或者偶数来区分，可将A中元素分划为两块：

B1?{3,5,9,25,2 7,35} B2?{2,8,16, 22}因此{B1,B2}是集合A的一个分划。

按照A中元素能被2整除、被3整除或被5整除来区分，又可将A中元素分为三块：

A1?{2,8,16, 22} A2?{3,9,2 7}4

A3?{5,25,3 5}因此{A1,A2,A3}也是集合A的一个分划。

按照A中元素能被2整除、被3整除或被4整除来区分，可得到A的如下几个非空子集：

C1?{2,8,16, 22} C2?{3,9,2 7} C3?{8,16 }因此{C1,C2,C3}不是集合A的一个分划，原因之一是C1,C3集合中有公共元素。 由上例子可知集合的分划并不唯一。

5

第2章 关 系

2.1 笛卡儿积与关系

2.1.1 基本知识点

基本概念：笛卡尔积，关系，二元关系，关系的性质

基本理论：关系的定义及表示；关系的性质(自反性、反自反性，对称性、反对称性、可传递性)

基本计算：关系的表示；关系与关系的交、并、补、差运算。

2.1.2 重点与难点 笛卡尔积：设A1,A2,称为A1,A2,,An是任意的集合，所有有序n元组(a1,a2,?An?{(a1,a2,,an)的集合，

,n}

,An的笛卡尔积，用A1?A2?即：A1?A2?,an?An，

?An表示，其中,an)|ai?Aii?1,2,a1?A1,a2?A2,关系：笛卡尔积A1?A2??An的任意一个子集称为n元关系，它是个集合，其

元素是n元组；当n?2时，称为A1到A2上二元关系。当A1?A2时称为集合A上的二元关系，简称关系。若(a,b)??，也可记作a?b，称a与b有关系?。若

(a,b)??，则记作a??b。

特殊及常见的关系 (1) 空关系：?；

(2) 集合A上的普遍关系：UA?{(ai,aj)|ai,aj?A}； (3) 集合A上的恒等关系：IA?{(ai,ai)|ai?A}

(4) 整数集合I上的整除关系：|?{(x,y)|?x,y?I,x整除y} (5) 整数集合I上的同余关系：{(x,y)|?x,y?I,x?y?km,k?I} (6) 实数集R上的小于关系：{(x,y)|?x,y?R,x?y} (7) 幂集合上的包含关系:??{(x,y)|?x,y?2A,x?y}

关系的表示方法

(1) 集合表示法：列举法和描述法；

(2) 矩阵表示法：用矩阵表示由有限集A到有限集B的关系； (3) 关系图表示法：用有向图来表示有限集合A上的关系； (4) 次序图：用无向图来特定地表示有限集A上的偏序关系。

关系的集合运算

关系是集合，因此关系的交、并、差、补运算与集合的运算一致；另一方面关

6

系与关系矩阵一一对应，因此可以用关系矩阵的布尔运算代替关系的运算。

2.2 关系的复合、关系的逆、关系的性质、闭包运算

2.2.1 基本知识

基本概念：关系的复合，关系的逆，关系的性质与关系的闭包 基本性质： (1) 关系复合的性质

(1)设?1:A?B，?2:B?C，?3:C?D，则有

(?1?2)?3??1(?2?3)

?1(?2??3)?(?1?2)?(?1?3)

(?1??2)?3?(?1?3)?(?2?3)

?1(?2??3)?(?1?2)?(?1?3)

(?1??2)?3?(?1?3)?(?2?3)

(2) 设?:A?A，则：?m?n??m?n，(?m)n??mn，这里m,n?N (3) 关系的逆运算具有以下性质：

(??1)?1??，(??r)?1???1?r?1，(?r)?1?r?1??1，(??r)?1???1?r?1 (4) 设?是集合A上的二元关系，则关系的性质可以描述为： (i)?具有自反性?IA?? (ii)?具有对称性?????1 (iii)?具有反对称性?????1?IA (iv) ?具有传递性??2??

2.2.2重点与难点

关系的闭包运算及关系性质的判断。 典型题解：

例1：设A?{a,b,c,d}

(1) 判断下列关系是否是自反关系

?1?{(a,b),(b,c)}

?2?{(a,a),(b,b),(c,c),(d,a)} ?3?{(a,a),(a,b),(d,d),(c,c),(b,b)} ?4?{(a,a),(b,b),(c,c),(d,d)}

(2) 判断下列关系是否是对称关系或者反对称关系

?5?{(a,b),(a,a),(b,a),(b,c),(c,b)}

?6?{(a,b),(a,a),(b,c),(d,c)}

7

?7?{(c,b),(a,a),(d,c),(c,d)} ?8?{(b,b),(d,d)}

(3) 判断下列关系是否可传递关系

?9?{(b,c),(c,c),(c,d),(b,d)} ?10?{(b,c),(c,b),(b,b),(a,d)} ?11?{(b,c),(d,a),(d,c)}

解：(1) ?1不是自反关系，因为对于所有的x?A，(x,x)均不在?1中； ?2是自反关系，但不是恒等关系； ?3是自反关系，但不是恒等关系； ?4是自反关系，也是恒等关系；

(2) ?5是对称关系，它不是反对称关系，因为a?b，但是(a,b)和(b,a)均出

现在?5中；

?6不是对称关系，因为(a,b)??6，(b,a)??6，?6是反对称关系； ?7不是对称关系，因为(c,b)??7，但是(b,c)??7，它也不是反对称关

系，因为c?d，但是(c,d),(d,c)均在?7中。

?8既是对称关系也是反对称关系。

(3) ?9是可传递关系，?10不是可传递关系，因为(c,b)??10，(b,c)??10，但

是(c,c)??10，?11是可传递关系。

例2用构造关系图的方法来求传递闭包t(?)。

设A?{a,b,c,d,e}，A上的关系?定义为??{(a,b),(b,a),(a,c),(求关c,e),(d,b)}系?的传递闭包t(?)。 解：先构造?的关系图，如下：

在?的关系图中，对每一个结点x，找出从x出发能到达所有结点，从结点a出

发能分别到达a,b,c,e，从结点b出发可分别到达结点a,b,c,e，从结点c出发可到达结点

e，从结点d出发可分别达到a,b,c,e

构造t(?)的关系图，如下图：

根据t(?)的关系图可得到相应的序偶：

t(?)?{(a,a),(a,b),(a,c),(a,e),(b,a),(b,b),(b,c)

(b,e),(c,e),(d,a),(d,b),(d,c),(d,e)}

2.3 集合的划分与等价关系

2.3.1基本知识点

基本概念：集合的划分，等价关系，等价类，商集

8

基本理论：

(1) 设?1和?2是非空集合A上的两个划分，若?1细分?2，且?2细分?1，则?1等于?2。

(2) 设?是集合A上的等价关系，则对任意a,b?A，或者[a]??[b?]或者

[a]??[b?]??。

基本计算

求有限集合所有划分的数目；求等价关系中元素的等价类集合、商集、生成的划分；求集合的划分诱导的等价关系。

2.3.2 重点与难点

(1)覆盖划分：划分一定是覆盖，覆盖不一定是划分。

(2)等价关系：设R是集合A上的关系，如果R具有自反性、对称性和传递性，则称R是A上的等价关系。此时若a,b?A且aRb，则称a等价于b。不难验证，普遍关系、恒等关系、模k同余关系都是等价关系。

2.4偏序关系

2.4.1基本知识点

基本概念：偏序关系、偏序集、哈斯图，极大远、极小元、最大元、最小元、上界、下界、上确界、下确界、全序、良序。 基本理论：

(1) 偏序关系的哈斯图表示

(2) 偏序集的某子集若存在最大元(最小元)，那么它一定是唯一的；极大元(极小

元)一定存在，但是不唯一

(3) 上界(下界)可能存在，也可能不存在，如果存在上界(下界)，上界(下界)可能

在该子集中，也可能不在该子集中，且不一定唯一； (4) 良序集一定是全序集；任一个有限的全序集一定是良序集 基本计算：求偏序关系的哈斯图；求偏序集合中的特殊元素。

2.4.2重点和难点

偏序关系的次序图：为形象直观的表示偏序关系，对偏序关系的关系图进行简化得到的图形为次序图。对哈斯图加上自回路、边的方向、传递后的有向边就得到了偏序关系的关系图

偏序集中的特殊元素：设?A,??是一偏序集合，B是A的子集，子集B的极大元是指B中没有比它更大的元素，是一种局部性质；最大元是指比B中所有元素

9

都大(可以相等)的元素，是全局性质。子集B的上界是指A中比B中所有元素都大(可以相等)的元素，在哈斯图中即B中的所有元素向上的路径都能共同到达的元素，有可能存在也有可能不存在，即使存在也可能不唯一；上确界是B的所有上界的最小者，有可能有多个上界但是无上确界。对于极小元、最小元、下界和下确界都可以这样类似去理解。

典型题解

例1 设A?{a,b},B?{1,2,3},C?{p,q}，求A?B,B?A,A?(B?C),A?B?C。 解： A?B?{(a,1),(a,2),(a,3),(b,1),(b,2),(b,3)}； B?A?{(1,a),(a2,),a(3,b),(1b,), (b2

A?B?C?{(a,1,p),(a,1,q),(a,2,p),(a,2,q),(a,3,p),(a,3,q),(b,1,p),(b,1,q),(b,2,p),(b,2,q),(b,3,p),(b,3,q)} A?(B?C)?{(a,(1,p)),(a,(1,q)),(a,(2,p)),(a,(2,q)),(a,(3,p)),(a,(3,q)), (b,(1,p)),(b,(1,q)),(b,(2,p)),(b,(2,q)),(b,(3,p)),(b,(3,q))}

例2 下列各式成立吗？说明理由。 (1) (A?B)?(C?D)?(A?C)?(B?D)； (2) (A?B)?(C?D)?(A?C)?(B?D)； (3) (A?B)?(C?D)?(A?C)?(B?D)； (4) (A?B)?C?(A?C)?(B?C) 解：(1)不成立。反例：

设A?{1},B?{2},C?{3},D?{4}，则(A?B)?(C?D)?{(1,3),(1,4),(2,3),(2,4)}，而(A?C)?(B?D)?{(1,3),(2,4)}。

(2)不成立。反例：设A?{1},B?{2},，则(A?B)?(C?D)??，而C?D?{2}。 (A?C)?(B?D)?{(1,2)}(3)不成立。反例：设A?B?{1},C?{3},D?{4}，则(A?B)?(C?D)??，而

(A?C)?(B?D)?{(1,3),(1,4)}。

(4) 成立。

例3假设A?{1,2,B3?,4},定义A到B上的二元关系，

??{(x,y)|x?y是3的倍数}，用例举法表示关系?，并写出关系矩阵。

解：??{(1,5),(3,3),(3,6),(4,5)}，?的关系矩阵M?如下：

?01?00?M???110 0??010??0?1??0?

例4 设R,S分别是集合A?{3,4,6,8,9}上的模2同余和模3同余关系，求R?S，

R?S,R?S,R?。

解： R?{(3,3),(4,4),(6,6),(8,8),(9,9),(3,9),(9,3),(4,6),(6,4)(4,8),(8,4),(6,8),(8,6)}， S?{(3,3),(4,4),(6,6),(8,8),3()9,,(9 ),(9,6)}3),,9()3,,(69),,3()6,,(6，,9 R?S?{(3,3),(4,4),(6,6),(8,8),3()9， },9 R?S?{(3,3),(4,4),(6,6),(8,8),(9,9),(3,9),(9,3),(4,6),(6,4)(4,8),(8,4),(6,8),(8,6),(6,9),(9,6)(3,6),(6,3)}

R?S?{(4,6),(6,4),(4,8),(8,4),(6,8),(8,6)}

R??{(3,4),(4,3),(3,6),(6,3),(3,8),(8,3),(4,9),(9,4),(6,9),(9,6),(8,9),(9,8)}

例5 设集合A?{1,2,3}，回答以下问题： (1) 在集合A上可定义多少个二元关系？ (2) 在集合A上可定义多少个自反的二元关系？ (3) 在集合A上可定义多少个反自反的二元关系？ (4) 在集合A上可定义多少个对称的二元关系？

解：(1)521个，因为A?A有9个元素，所以A?A有29?512个子集。 (2)64个，因为关系必须包含恒等关系IA，26?64。 (3) 64个，因为关系不能含有元素(1,1)，(2,2)，(3,3)。

(4)64个，因为关系中元素(1,2)和(2,1)，(1,3)和(3,1)，(2,3)和(3,2)要么同时出现，要么同时不出现，则2?2?2?23?64。

例6 设R是集合A?{1,2,3,4}上的二元关系，其定义如下：

R?{(1,1),(3,1),(1,3),(3,3),(3,2),(4,3),(4,1),(4,2),(1,2)}，判定关系R的性质。

解：R不具有自反性，因为(2,2)不属于关系R；也没有对称性，因为(1,2)属于R，而(2,1)不属于R；也没有反对称性，因为(1,3)和(3,1)同时属于R。可传递性可以通过RR?R，因此R是可传递的。

例7 设R是集合A上的二元关系，试证明R是传递的当且仅当RR?R。 证明：必要性：对?(x,y)，由关系复合的定义，?z?A，使得?RR(x,z)?R,(z,y)?R，由于R是传递的，故有(x,y)?R，从而有RR?R成立；

充分性：若(,由关系复合的定义，?x,y,z?A，xy)?R且(y,z)?R，(x,z)?RR，由于RR?R，故有(x,z)?R，由定义知，R是可传递的。 例

8

设A?{1,2,3,4}，求A上的关系R?{(1,2),(，211

S?{(1,2),(2,1),(2,3),(2,4)}的传递闭包。

解：t(R)?{(1,2),(2,3),(3,4),(1,3),(2,4),(1,4)}；

t(S)?{(1,2),(2,1),(2,3),(2,4),(1,1),(2,2),(1,3),(1,4)}

例9 设集合A为有限集合，且#(A)=5，求A的所有不同的分划的个数。 解：秩为1的分划有1个

1秩为2的分划有C5?C?15个 312秩为3的分划有C5?C5C4/2?25个 2秩为4的分划有C5?10个

秩为5的分划有1个 总的分划数目为52个。

例10 证明整数集合Z上的模4同余关系?是等价关系，并求各元素的等价类集合，以及该等价关系诱导的对于Z的一个分划。 证明：因为对?i?Z,(i?i)/4?0?Z，即?具有自反性；

对?i,j?Z，若i?j，即(i?j)/4?Z，则显然有(j?i)/4?Z，即j?i，故?具有对称性；

对?i,j,k?Z，若i?j且j?k，即(i?j)/4?r?Z，(j?k)/4?s?Z，则有(i?k)/4?r?s?Z，即i?k，故?具有传递性，因此模4同余关系是等价关系。 各元素的等价类集合为

[0]??{,?12,?8,?4,0,4,8,12,}

[1]??{,?11,?7,?3,1,5,9,13,} [2]??{,?10,?6,?2,2,6,10,14,}

[3]??{,?9,?5,?1,3,7,11,15,}

由于不同等价类只有4个，且两两互不相交，故该等价关系诱导的Z的一个分划是{[0]?,[1]?,[2]?,[3]?}。

例11 设R是集合A上的自反关系，证明：R是A上的等价关系的充要条件是

?a,b,c?A，若aRb,aRc则bRc。

证明：充分性：?a?A，由于R是自反的，所以aRa。假设aRb，又因aRa，由已知条件得bRa，即R对称；又假设aRb，bRc，由于R对称，故有bRa，再由已知条件可得aRc，即R传递，因此R等价。

必要性：因为R是A上的等价关系，所以若aRb，aRc，由于R对称，有bRa。由bRa、aRc及R的传递性，可得bRc。

12

例12 判定下列命题是否恒真，并说明你的理由。

(1) 非空集合A上存在二元关系R，使得R既是A上的等价关系，又是A上的偏序关系。

(2) 设?A,R?是偏序集合，??B?A，若B有下界，则集合B有下确界。 解：(1)真命题，因为集合A的恒等关系IA既是A上的等价关系又是A上的偏序关系。

(2) 假命题。反例：设A?{a,b,c,d}，给定偏序集?A,R?的哈斯图如下图(1)所示，令B?{c,d}，则a,b均是其下界，但是B没有下确界。

图(1)

例13 对于下列每一种情况，举出有限集合和无限集合的例子各一个。 (1) 非空偏序集合，其中某些子集没有最大元；

(2) 非空偏序集合，其中有一个子集存在下确界，但是没有最小元； (3) 非空偏序集合，其中有一个子集存在上界，但没有上确界。

解：(1)令A?{1,2,3,4}，R?IA，则?A,R?是偏序集合，但是A没有最大元。 ?N,??是偏序集合，但是N没有最大元。

(2) 令A?{1,2,3}，R?IA?{(1,2),(1,3)}，则?A,R?是偏序集合，子集

B?{2,3}存在下确界1，但是没有最小元；

设A表示非负实数的集合，则?A,??是偏序集合。令B表示正实数的集合，则B存在下确界0，但是B没有最小元。

(3) 令A?{1,2,3,4}，R?IA?{(1,3),(2,3),(1,4),(2,4)}，则?A,R?是偏序集合，令B?{1,2}，则B存在上界3和4，但B没有上确界；

设A?[?1,0)?(0,1]，则?A,??是偏序集合，令B?[?1,0)，则(0,1]中的元素都是B的上界，但是B没有上确界。

例14 设A?{1,2,3,4,5,6,7,8,9,10,11,12}，偏序关系R是A上的整除关系，画出R的哈斯图，求子集{1,2,3,5}及{2,3,4,6}的极大元和极小元、最大元和最小元、上界和下界、上确界和下确界。

13

解：偏序关系的哈斯图如图(2)所示：

{1,2,3,5}的极大元是2,3,5；极小元是1；最大元无；最小元是1；上界无；

下界是1；上确界无；下确界是1；

{2,3,4,6}的极大元是4,6；极小元是2,3；最大元无；最小元是无；上界12；

下界是1；上确界是12；下确界是1；

图(2)

14

第3章 函 数

3.1 函数

3.1.1基本知识点

基本概念：函数、内射、满射、双射

基本理论：设f是A?B的函数，若A和B都是有限集合，A,B的元素个数相同，

则f是内射的充分必要条件是f是满射。

基本计算：判断二元关系是不是函数；判断函数是内射、满射还是双射；求函数

的的定义域和值域。

3.1.2重点与难点：

函数 设A和B是任意两个集合，f是A到B的二元关系，如果对于A中每一个

元素x，都有唯一的y?B，使得(x,y)?f，则称f是一个A到B的函数，记作：f是A?B的函数，对于A中任一元素a，B中对应的b?f(a)，称

b是a在函数f下的象，并称A是f的定义域，B为f的值域包。

(1) 函数也称为映射，是一种特殊的关系，集合A?B的任何子集都是关系，

但不一定是函数，函数要求对于定义域A中的每一个元素a，B中有且仅有一个元素与a对应，而关系没有这个限制。

(2) 两个函数相等是指：定义域和值域相同，而且定义域内每个元素对应的

象都相同。

内射：设有函数f: A?B，若当ai?aj时，有f(ai)?f(aj)，则称f为内射； 满射：设有函数f: A?B，若f(a)?B，则称f为满射；

双射：设有函数f: A?B，若f既是内射又是满射，则称f为双射。 特殊函数的判断：给定函数，判断其是内射、满射还是双射。

典型题解：

例1：设X?{12，},Y{,?}ab，则从X到Y的不同的二元关系有24?16，分别为：

?0?? ?1?{(1,a)} ?2?{(1,b)}

}?3?{(2,a)} ?4?{(2b,)?5?{(1,a)，(1,b)} ?6?{(1,a)，(2,b)}

?7?{(2,a)，(1,b)} ?8?{(2,a)，(2,b)} ?9?{(1,a)，(2,a)} ?10?{(1,b)，(2,b)} ?11?{(1,a)，(2,a)，(1,b)}

?12?{(1,a),(2,a)，(2,b)} ?14?{(2,a)，(1,b)，(2,b)}

?13?{(1,a)，(1,b)，(2,b)}

15

?15?{(1,a)，(2,a)，(1,b)，(2,b)}

但从X到Y的不同的函数只有22?4个，分别为：

f1??6?{(1,a)，(2,b)} f3??9?{(1,a)，(2,a)}

f2??7?{(2,a)，(1,b)}

f4??10?{(1,b，)(b2, )}例2判断下列函数是否为内射、满射、双射。为什么？

(1)f：R?R，f(x)??x2?2x?1；

(2)f：Z??R，f(x)?lnx，这里Z为正整数集合； (3) f：R?R，f(x)?2x?1；

?解：(1)f：R?R，f(x)??x2?2x?1是开口向下的抛物线，不是单调函数，并

且在x?1点取得极大值0。因此它既不是内射也不是满射。

(2) f：Z??R，f(x)?lnx是单调上升的，因此是内射。但不是满射，因为

Rf?{ln1，ln2，}?R。

(3)f：R?R，f(x)?2x?1既是内射又是满射，所以是双射。

例3 设X?{1,2,3,4,5}，Y?{a,b,c,d,e}，判断下列从X到Y的二元关系是否是

从X到Y的函数，若是函数，是否是内射、满射、双射？

(1)f1?{(1,a),(2,c),(3,b),(4,e),(5,d)} (2)f2?{(1,a),(2,d),(3,e)}

(3)f3?{(1,a),(2,c),(2,d),(3,e),(4,b)} (4)f4?{(1,a),(2,a),(3,a),(4,e),(5,d)}

解：f1是一个双射函数，f2和f3不是函数，f4是函数，但既不是内射也不是

满射。

例4 判断函数f:N?N?N，f((m,n))?mn是不是内射？是不是满射？ 解：对于N?N的两个不同的元素(2,2)和(4,1),根据函数的定义显然有

f((2,2))?f((4,1))?22?4，所以不是内射；对N中任一数k,显然(k,1)属于N?N，且f((k,1))?k1?k，所以f是满射。

例5 设f:X?Y是函数，A,B分别是X,Y的子集，试证f(A?B)?f(A)?f(B) 证明：对?y?f(A?B)，存在x?A?B，使f(x)?y，不妨设x?A，则

y?f(A)?右边，说明f(A?B)?f(A)?f(B)；

对?y?f(A)?f(B)，不妨设y?f(A)，即存在x?A?A?B使f(x)?y，即

y?f(A?B)?左边，说明f(A?B)?f(A)?f(B)。综上得证。

16

例6 设集合A?{a,b,c}，B?{0,1}，试问A到B上的关系有多少个？A到B上的函数有多少个？

解：因为A?B?{(a,0),)(b,0),(c,0),(a,1),(b,1),(c,1)}有6个元素，A?B有26个子集，所以A到B上的关系有26个；但是A到B上的函数只有23个。

3.2 函数的复合和逆函数

3.2.1基本知识

基本概念：函数的可逆性、函数的复合

基本理论：只有双射函数是可逆的；逆函数和复合函数的运算规律；复合函数的

性质；复合运算不满足交换律。

基本计算：判断函数的可逆性；求双射函数的逆函数；求两个已知函数的复合函

数；利用复合函数求两个集合之间的双射；利用复合函数的性质判断一个函数是否是内射、满射、双射。

3.2.2重点和难点：

逆函数 集合A到B的函数f作为一个二元关系，如果逆关系f?1是B到A的函数

则称f是可逆的，并称f?1是函数f的逆函数。

注：不是任一函数都有逆函数，只有双射函数才有逆函数。

复合函数：设f:A?B，g:B?C是两个函数，对任意a?A，定义

g，记f(a)?g(f(a))h?gf，称h:A?C是g和f的复合函数。 (2)一般fg?gf。

注：(1)复合函数gf成立的条件为Ran(f)?Dom(g)； 逆函数与复合函数的运算规律： (1) 若f:A?B是双射函数，则 (f?1)?1?f IB f f?1 ff?f IA?f f?AI f?1?BI

f?h(g f)(2) 若f:A?B，g:B?C，h:C?D都是函数，则 (hg)(i) (ii)

(3) 设f:A?B，设g:B?A都是函数则有以下运算规律

若gf?IA，则f是内射，g是满射；

若gf?IA，fg?IB，则f,g都是双射，且f?1?g，g?1?f；

17

(iii)

若f,g可逆，则gf可逆，且(gf)?1?f?1g?1。

复合函数的性质

性质1：设f：X?Y，g：Y?Z，则

(1)若f和g是满射，则f?g是满射；

(2)若f和g是单射，则f?g是内射；

(3)若f和g是双射，则f?g是双射。

(1)若f?g是满射，则g是满射； (2)若f?g是单射，则f是单射；

(3)若f?g是双射，则f是单射且g是满射。

性质2 ：设f：X?Y，g：Y?Z，则

典型题解

例1 设f:X?Y，g:Y?Z，举例说明：

(1)f?g是满射，但f不是满射；(2)f?g是内射，但g不是内射。 则f?g：X?Z，f?g(x1)?f?g(x2)?z，可见f?g是满射，但f不是满射。(2)设X?{x1,x2}，Y?{y1,y2,y3},Z?{z1,z2},f(x1)?y1,f(x2)?y2， 解：(1)设X?{x1,x2},Y?{y1,y2}， g(y1)?g(y2)?z，Z?{z}，f(x1)?f(x2)?y1，

g(y2)?z2，则f?g：X?Z，f?g(x1)?z1，f?g(x2)?z2，g(y1)?g(y3)?z1，

可见f?g是内射，但g不是内射。

例2 设f：X?Y，g：Y?Z，并且f和g都是可逆的，则

(1)(f?1)?1?f；

(2) (f?g)?1?g?1?f?1。

证明：(1)由逆函数的定义即得。

(2)因为f和g都是可逆的，所以f?1：Y?X， g?1：Z?Y，从而

g?1?f?1：Z?X。又因为f?g：X?Z，且

(g?1?f?1)?(f?g)?g?1?(f?1?f)?g?g?1?IY?g?IZ (f?g)?(g?1?f?1)?f?1?(g?g?1)?f?f?1?IY?f?IX 则(f?g)?1?g?1?f?1成立。

例3 设有函数f:R?R，f(x)?x2?1，g:R?R，g(x)?x?2，试求复合函数fg和gf；并说明复合函数是否内射？满射？双射？

解：根据复合函数的定义，fg?f(g(x))?f(y)?y2?1?(x?1)2?1，

gf?g(f(x))?g(y)?y?2?(x2?1)?2?x2?1。因为fg(0)?fg(?4)，所以

fg不是内射；又因为当b??1时，不存在实数a使得fg(a)?b，所以fg也

18

不是满射，因此更不是双射。

例4 设有函数g:A?B，f:B?C，试证(1)如果fg是内射，则g是内射；(2)如果fg是满射， 则f是满射。

证明：(1)用反证法，假设若g不是内射，即存在a1,a2?A，a1?a2但是

g(a1)?g(a2)，那么fg(a1)?f(g(a1))?f(g(a2))?fg(a2)，这与fg是内射相矛盾。从而说明g只能是内射。

(2) 反证法：假设f不是满射，即存在c?C，使得对任意b?B，f(b)?c。那么，对任意a?A，记b?g(a)，则b?B，fg(a)?f(g(a))?f(b)?c，这与

fg是满射相矛盾，因此f是满射。

19

第7章 格和布尔代数

7.1 偏序集

7.1.1 基本知识点：

基本概念：偏序集，上界，下界，最大下界，最小上界，最小元素，最大元素； 基本理论：偏序集的定义；最大下界和最小上界的唯一性；

基本计算：求偏序中两个元素的上界、下界、最大下界、最小上界，求偏序集的

最小元素和最大元素。

7.1.2 重点与难点

偏序集中元素的运算性质：对于偏序集?L,??中所有的元素l1,l2,l3?L，有

(1) l1?l1；

(2) 若l1?l2，l2?l1，则有l1?l2； (3) 若l1?l2，l2?l3，则有l1?l3； (4) l1?l1；

(5) 若l1?l2，l2?l1，则有l1?l2； (6) 若l1?l2，l2?l3，则有l1?l3；

典型题解：

例1 设A?{1,2,3,4,6,12}，因为A中元素都是正整数，所以‘整除’关系是A上的偏序关系，记作‘?’，则因为1?2,1?3所以1是2和3的下界，也是2和3的最大下界；因为2?6,3?6,2?12,3?12，所以6和12都是2和3的上界，但是6?12，所以

1?6,?11?2,?26是2和3的最小上界；因为

6?,21,2,3?12，所以,??和6都是6和12的下

界，但是6最大，所以6是6和12的最大下界。同理，显然12是6和12的上界，也是6和12的最小上界。

例2 设有集合U?{a,b,c}，U的幂集2U上的包含关系?是一个偏序关系，其哈斯图如图(1)所示，从图(1)看出{a,b,c}是{a,b}和{b,c}的上界，也是{a,b}和{b,c}的最小上界。其中{b}是他们的最大下界。{b}和?是{a,b}和{b,c}的下界，{a,b,c}和{a,b}是{a,b}和{b}的上界，其中{a,b}是最小上界。{a}{c}{a,c}

20

图(1)

7.2 格及其性质

7.2.1 基本知识点

基本概念：格，子格，格的性质，分配格，有界格，有补格 基本理论：

(1)设?L,??是格，定义L上的二元运算?和?：

l1?l2?glb(l1,l2)(最大下界) l1?l2?lub(l1,l2)(最小上界)

注：运算?和?满足交换律、结合律、幂等律和吸收律。

(2) 设?L,??是格，l1,l2是格?L,??的元素，则l1?l2?l2?l1?l2?l1?l1?l2； (3) 格的交换律：在格?L,??中，对任意的l1,l2?L，有

l1?l2?l2?l1l1?l2?l2?l1

l1?(l2?)l3?(l1?)l 2?l(4) 格的结合律：在格?L,??中，对于任意的l1,l2,l3?L，有 l1?(l2?l3)?(l1?l2)?l3 l?l?l l?l?l

(6) 格的吸收律：在格?L,??中，对于任意的l1,l2?L，有 l1?(l1?l2)?l1 l1?l2?l3?l4(5) 格的等幂律：在格?L,??中，对于任意的l?L，有

ll1?(l1?)l2?(7) 格的保序性：在格?L,??中，对任意的l1,l2,l3,l4?L，若l1?l3,l2?l4则：

l1?l2?l3?l4

(8) 格的分配不等式：在格?L,??中，对任意的l1,l2,l3?L，有下列分配不等式成立：l1?(l2?l3)?(l1?l2)?(l1?l3)，l1?(l2?l3)?(l1?l2)?(l1?l3) (9) 若格?L,?,?,??是分配格，若a?b?a?c，且a?b?a?c，则b?c。 (10) 若格?L,??有下界，则下界一定是唯一的；若格?L,??有上界，则上界一定是唯一的。

21

(11) 设格?L,??是一个有界格，下界为0，上界为1，则?l?L，必有 l?0?0l?1?ll?0?ll?1 ?1(12) 在有界分配格中，如果元素l有补元，则补元一定是唯一的。

基本计算：判断给定的偏序集是否是格；证明格中的等式和不等式；判断子集是否构成子格；理解格的性质；判断给定的格是否是分配格，是否是有补格。

7.2.2 重点与难点

格：设?L,??是一个偏序集，若?l1,l2?L，l1,l2有上确界和下确界，则称?L,??

是一个格。

子格：设?L,?,?,??是格，S是L的非空子集，若S关于L中的运算?,?仍然构

成格，则称S是L的子格。

分配格：在格?L,??中，对任意的l1,l2,l3?L，有

l1?(l2?l3)?(l1?l2)?(l1?l，)l1?(l2?l3)?(l1?l2)?(l1?l3) 3有界格：若格?L,??存在上界和下界，则称L是有界格，下界记为0，上界记1。 有补格：若格?L,?,?,??是有界格，对于L中的元素a，若存在元素b，使得 a?b?0,a?b?1，则称b是a的补元；在有界格中，若每个元素都有补

元，则称此格为有补格。

典型题解：

例1 考虑实数集R和小于等于关系?，说明?R,??是否构成格？对?x,y?R，求x?y,x?y。

解：(1) ?R,??是格，对于任意的两个实数都可以比较，且x,y的下确界为x和

y中最小者，x,y的上确界为x和y中最大者。

(2) x?y?glb(x,y)?min(x,y)，x?y?lub(x,y)?max(x,y)

例2 由下列集合L构成偏序集?L,??，其中?表示‘小于等于’的偏序关系，问其中哪几个偏序集是格？ (1) L?{1,2,3,4,6,12} (2) L?{1,2,3,4,6,8,12,14} (3) L?{1,2,3,4,5,6,7,8,9,10,11,12}

解：(1) ?L,??是格，其偏序关系的关系图如图(2)所示：

22

图(2)

由图(2)所示，每对元素都有上确界和下确界，所以?L,??是格。

(2) ?L,??不是格，因为8和14没有上确界。偏序关系的哈斯图如图(3)。

图(3)

(3) ?L,??不是格，因为3和7没有上确界，偏序关系的哈斯图如图(4)所示。

图(4)

例3 设?L,?,??是格，证明(1)?a,b?L，(a?b)?b?b；(2) a?b?b当且仅当

a?b?a。

b?(a?b)?b，证明：(1) (a?b)?b是a?b与b的最小上界，由上确界的定义知，

类似地，b是a?b与b的上界，所以又(a?b)?b?b，所以(a?b)?b?b。 (2) a?b?b，即a?b?glb(a,b)?b，等价于a?b?lub(a,b)?a。

23

例4 判断下列格是不是分配格、有界格、有补格？

(a)L1 (b)L2 (c) L3 解：(1) L1是分配格，L2和L3不是分配格。

可以验证在L1中，任意三个元素关于两个运算都满足分配律；

在L2中，c?(b?d)?c?e?c，(c?b)?(c?d)?a?a?a?c，所以不是分配格； 在L3中，a?(f?d)?a?e?a，(a?f)?(a?d)?c?c?c?a，所以不是分配格；

(2) 在L1中，a是下界，e是上界，a的补元是e，其他元素没有补元，所以L1不是有补格。在L2中，h是下界，e是上界，e的补元是h，其他元素没有补元，所以L2不是有补格。在L3中，e是上界，c是下界，e和c互补，a的补元有b,d,f,g，

d的补元a,f,g，f的补元a,b,d，b的补元有a,f,g，g的补元a,b,d，c的补元e，

所以L3是有补格。

24

第8章 图论

8.1 基本概念

8.1.1 基本知识点

基本概念：图，无向图，有向图，简单图，零图，平凡图，子图，完全图，补图，

正则图，图的同构，真子图，生成子图，连通，分图，短程，距离，伪图，多重图，有权图。

基本理论：握手定理：图的所有结点的度数之和等于边数的两倍；在有向图中，

所有结点的出度之和等于边数，所有结点的入度之和也等于边数；度数为奇数的结点个数一定为偶数。

基本计算：求完全图及简单图的结点数和边数的关系式；判断两个给定图是否同

构；求给定图的补图。

8.1.2 重点和难点

图的定义：一个图G是一个有序二元组(V,E)，记作G?(V,E)，其中： (1) V?{v1,v2,,vn}是一个非空有限集，V的元素称为G的结点或顶

点，V称为G的结点集；

(2) E是V中不同元素的非有序对偶的集合，这些对偶称为G的边，

而E称为G的边集。

有关术语：

(1) 若边e?{vi,vj}是G的边，则称结点vi和vj是邻接的，e和vi以及e和vj称为关联的。关联于同一结点的相异边称为是邻接得。 (2) 不与其他任何边相邻接得边称为是孤立边。 (3) 关联同一个结点的边称为自回路或者环。 (4) 只与一条边关联的结点称为是悬挂点。

无向图与有向图：每条边都是无方向的图称为无向图；每条边都具有方向的图称

为有向图。

零图和平凡图：仅由孤立点组成的图称为零图，仅由一个孤立点构成的图称为平

凡图。

简单图：不含平行边且不含长度为1的环的图称为简单图；含平行边的图称为多

重图。

子图：设有图G?(V,E)和G?(V,E)，

(1) 若V?V,E?E，则称G是G的子图；

(2) 若V?V,E?E且E?E，则称G是G的真子图；

25

(3) 若V?V,E?E，则称G是G的生成子图。 注：每个图都是自己的子图。

完全图：设图G?(V,E)是一个简单图，若V中任意两个不同的结点间都有边关

联，则称该图是一个完全图。

2注：一个完全(n,m)图，则m?Cn。

补图：图G的补图是由G的所有结点和为了使G成为完全图所需要添加的那些

边所组成的图，用G表示。

正则图：若图G的所有结点都具有同一度d，则称该图为d次正则图。 路：图G中l条边的序列{vi0,vi1},{vi1,vi2},路。

开路：若vi0?vil，则称该路为开路。 回路：若vi0?vil，则称该路为回路。 真路：若vi0,vi1,环：若vi0,vi1,接的。

连通：在图G中，任意两个结点均是连接的，则称图G是连通的，否则是不连

通的。

短程：在图G中，从结点vi到vj若由一条或者更多的路相连接，则其中必有长度

最短的路，称其为从vi到vj的短程。

距离：从vi到vj的短程的长度称为vi和vj间的距离，用d(vi,vj)表示。

,{vil?1,vil}称为连接vi0到vil的长度为l的

,vil各不相同，则称该路为真路。 ,vil各不相同，则称回路为环。

连接：在图G中，若存在一条路连接vi和vj，则称该图中的两个结点vi与vj是连

典型题解：

例1 证明在n个顶点的简单无向图G中，至少有两个结点的度相同，这里n?2。 证明：分三种情况讨论。

(1) G中无孤立点，则每个结点的度大于等于1，又由简单图的性质知每个结

点的度小于等于n?1，所以每个结点的度都属于集合{1,2,,n?1}，这是

在只有n?1个元素的集合中取n个元素，所以至少有两个结点的度相同。 (2) G中只有一个孤立点，则除孤立点外，每个结点的度大于等于1，又由简

单图的性质知每个非孤立点的度小于等于2，所以n?1个结点的度均属于集合{1,2,,n?2}，这是在只有n?2个元素的集合中取n?1个元素，所以

至少有两个结点的度相同。

(3) G中至少2个孤立点，则2个孤立点的度相同。

26

例2 下列各组数中，哪些能构成无向图的度数序列？哪些能构成无向简单图度

数序列？

(1) {1,1,1,2,3}；(2) {6,5,4,4,3,2,1}；(3){1,2,3,4,5}；(4){1,3,3,3}

解：非负整数序列能构成无向图的度数序列的充分必要条件是该序列之和为偶数。上述序列中(2)(3)中均有3个奇数，所以不能构成无向图的度数序列；(1)(4)能构成无向图的度数序列。(1)对应一个无向简单图，而(4)不能构成无向简单图的度数序列，因为若对应简单无向图G，设v1,v2,v3,v4是该图的4个结点，不妨设deg(v1)?1,deg(v2)?3,deg(v3)?3,deg(v4)?3，则结点v1仅仅能与v2,v3,v4之一相邻，不妨设与v2相邻，则除了v2能达到度数3外，其它两个点都达不到度数3，至多为2，因此矛盾，所以(4)不能构成无向简单图。

例3 考察下面图(a)和图(b)是否同构？

(a)

得到如下图：

(a) (b)

在图(a)中结点a,b相邻，而a?,b?不相邻，所以图(a)和图(b)不同构。

例4 求出下图的补图：

解：根据补图的定义，得补图如下：

27

(b)

解：图(a)和图(b)中都恰好有两个度为3的结点，分别将它们标记为a,b和a?,b?，

例5 下列各无向图中有几个结点？

(1)21条边，3个4度数结点，其余都是3度数的结点； (2) 12条边，各结点的度数相同。

解：设图中结点个数为n，根据握手定理： (1)

n?3?deg(v)?4?n?3?(n?n)?4?3?3?(n?3)?3n?3?42i11i?1n，所以

9?/。

(2) 设各结点的度数为k，则?deg(vi)?k?n?2m?2?12?24

1)若k?1，则n?24；2) 若k?2，则n?12；3)若k?3，则n?8；4)若k?4，则n?6；5)若k?4，则n?4；6)若k?8，则n?3。

例6 证明在9个工厂之间，不可能每个工厂只与其他3格工厂有业务联系，也不可能只有4个工厂与偶数个工厂有业务联系。

证明：将9个工厂看作9个结点，两个工厂有业务联系时看成对应两结点之间有边。

(1) 假设每个工厂只与其他3个工厂业务有联系，则每个结点的度数为3，所有结点的度数之和为27，这与结点度数之总和为偶数(边数的 2倍)矛盾，所以不可能每个工厂只与其他3个工厂有业务联系。

(2) 假设只有4个工厂均与偶数个工厂有业务联系，其他5个工厂均与奇数个工厂有业务联系，则4个偶数之和是偶数，5个奇数之和是奇数，从而9格结点的度数之和为奇数。这也与结点度数之总和为偶数相矛盾，所以不可能只有4格工厂与偶数个工厂有业务联系。

例7 设G为n阶简单无向图，n?2且n为奇数，G和G的补图G中度数为奇数的结点个数是否一定相等？证明你的结论！

解：一定相等。因为n?2且为奇数，对于奇数个结点的无向完全图，每个结点的度数必为偶数。若G的奇结点有k个，则对应补图G在这k个结点的度数必为奇数(偶数-奇数=奇数)；而对于G的偶结点，其在补图G中仍为偶结点(偶数-偶

28

i?1n数=偶数)，所以G和G的补图G中度数为奇数的结点个数是一定相等。 例8 已知n阶无向简单图G有m条边，各结点的度数均为3。 (1) 若m?3n?6，证明G在同构的意义下唯一，并求m,n； (2) 若n?6，证明G在同构的意义下不唯一。

证明：(1)由于各顶点的度数均为3，现有n个结点，m条边，所以 故n?2。 3m?degv(ii?1n 2?)?3n?m又m?3n?6?3?2，故m?6，则n?4。 3m?6?2m?6此时所得的无向图如下图(a)所示，该图为4个结点的无向完全图，对于4个结点的完全图，在同构意义下唯一。

(a) (2) 若n?6，有?deg(vi)?3?6?18?2m 故m?18/2?9。

i?1n此时有n?6,m?9，且每个结点的度数为3，对于无向简单图，6个结点，9条边及每个结点度数为3的图如图(b)(c)所示，这两个图是非同构的。所以n?6,m?9，结点度数全为3的图在同构的意义下不唯一。

(b) (c)

8.2 图的矩阵表示

8.2.1 基本知识点：

基本概念：邻接矩阵，关联矩阵，邻接向量矩阵，连接矩阵，布尔矩阵，布尔矩

阵运算。

基本理论：邻接矩阵、关联矩阵与结点度数的关系；邻接矩阵的乘幂与任意两结

点间路的条数的关系；图的连通性与连接矩阵的关系。

基本计算：求图的邻接矩阵和关联矩阵；利用邻接矩阵求结点的度；利用邻接矩

29

阵的幂判断任意两结点间不同长度的路的条数；求矩阵的连接矩阵；利用连接矩阵判断无向图的连通性。

8.2.2 重点与难点

邻接矩阵：设G?(V,E)，其中V?{v1,v2,矩阵，其中元素

,vn}，n阶方阵A?(aij)称为G的邻接

?1若{vi,vj}?Eaij??否则?0,vn}，m条边e1,e2,,em，则关联矩

关联矩阵：设G?(V,E)，其中V?{v1,v2,阵I?(bij)是一个n?m的矩阵，其中元素

?1若vi和ej是关联的bij?? 否则?0

连接矩阵：设G?(V,E)，其中V?{v1,v2,矩阵，其中元素

,vn}，n阶方阵C?(cij)称为G的连接

?1若vi到vj存在一条路cij??否则?0布尔矩阵和布尔运算：如果一个矩阵的所有元素均为0或1，则称这种矩阵为布

尔矩阵；对于布尔矩阵来说，若矩阵运算中元素的相加与相乘均规定为布尔加与布尔乘，则这种矩阵运算称为布尔矩阵运算。

求图的连接矩阵的两种方法：

(1) 利用邻接矩阵：若图G?(V,E)，#(V)?n，则Bn?A?A2??An，其中矩

阵Bn的(i,j)项元素bij给出连接vi和vj的长度小于或等于n的路的总和，若这个数不为0，则结点vi和vj是连接的；如果这个元素为零，则结点vi和vj非连接；若Bn每个元素都不为0，则判断图G是连通的，否则G不是连通的图。 (2) 利用布尔矩阵运算：C?A[?]A(2)[?][?]A(n)。对于任意的正整数l，当且仅

(l)当存在有连接vi到vj的长为l的路时，A(l)的(i,j)项元素aij?1，因此若G是

连通的则矩阵C中每个元素均为1，否则为非连通的。 邻接矩阵与路的条数的关系：设G?(V,E)，其中V?{v1,v2,记为A，则Al(l?1,2,3,)

,vn}，其邻接矩阵

(l)的(i,j)项元素aij是连接vi到vj的长度为l的路的总数。

典型题解：

例1 分别写出下图(a)的邻接矩阵，并根据矩阵的元素求图(a)中结点v1的度数

30

(a) 解：邻接矩阵为：

?0?1A???1??1100110011?1??1??0?图G是无向图，结点v1的度为矩阵A的第一行或第一列的元素之和，即deg(v1)?3。 注：求邻接矩阵时，首先要将图的结点排序，排序方式不同，得到的矩阵也不同，这些矩阵可以通过相应的行列变换相互得到。如果两个图有这样的邻接矩阵，其中的一个可通过另一个交换某些行和列而得到，则这两个图是同构的。

例2 图G如下图所示，试用矩阵方法来求图中长度为4的路有几条？有多少条回路？有多少条是从v3到v4的路？ 解：

首先求邻接矩阵A及A4：

?0110??1101??1111??1212??1000??0110? ?1101??1111??A2???A??34???A???11 ? ? 0 1 0 0 0 1 ? A??0111??1102??????????0001??0001? ?0001??0001?G中长度为4的路的条数为A4的全部非零元素之和，即15条。G中长度为4的

回路的条数仅为A4中对角线上元素之和：即3条。

(4)从v3到v4的长度为4的路的条数为a34?2，即有2条。

例3 图G由邻接矩阵A给出，问G是否连通？其中A如下：

?0?1?A??1??0??01100?0100??1000??0001?0010??31

解法一：直接由邻接矩阵给出图G的一个图解，如下图：

显然图G是不连通的。 求图G的连接矩阵： ?1?C?A[?]A(2)[?]A(3)[?]A(4)[?]A(5)= ?1?1 ??0

??0 解法二：

1100?1100??1100??0011?0011??因为矩阵C中含有0元素，所以G不连通。

8.4欧拉图和哈密顿图

8.4.1 基本知识点

基本概念：欧拉路，欧拉图，哈密顿路，哈密顿图。

基本理论：(1)无向图G具有欧拉路的充分必要条件是它连通且有2个或0个奇

结点。

(2) 无向图G是欧拉图的充分必要条件是它连通且所有结点的度均

为偶数。

(3) 哈密顿图的必要条件和充分条件。

基本计算：判断一个图是否是欧拉图；判断一个图是否是哈密顿图。

8.4.2 重点与难点

欧拉路及欧拉图：通过图G的每条边一次且仅一次的开路称为图G的欧拉路；

通过图G的每条边一次且仅一次的回路称为图G的欧拉回路；具有欧拉回路的图称为欧拉图。

哈密顿路与哈密顿图：通过图G的每个结点一次且一次的环称为哈密顿环；具有

哈密顿环的图称为哈密顿图；通过图G的每个结点一次且一次的开路称为哈密顿路。

哈密顿图判定的一个必要条件：

若图G?(V,E)是哈密顿图，则对于V的任何一个非空子集S，有

32

W(G?S)??S

这里W(G?S)表示G?S中分图的个数。

存在哈密顿路的一个充分条件：

设无向图G是具有n个结点的简单图，如果G中每一对相邻的结点度数之和大于等于n?1，则G中存在一条哈密顿路；若G中每一对不相邻的结点度数之和大于等于n，则G是哈密顿图。

典型题解：

例1 判断下面图(a)和(b)能否一笔画出，为什么？

(a) (b)

解：将图(a)中各线段的交点看做结点，将各线段看成边，因为图中的奇结点的个数超过2，所以该图不存在欧拉路和欧拉回路，也就是不能一笔画出。将(b)用同样方法处理，可知最高和最低处结点的度为1，其他结点的度为偶数，且是连通的，因此是欧拉图，即能一笔画出。

例2 若图G是欧拉图，则G中没有割边。

证明：用反证法证明：设e?{u,v}是G的一割边，因为G是欧拉图，因此e?{u,v}必在G的一个欧拉回路上?上。故从?中删去边e得连接u与v的一条路?，因此可得一条连接u,v的真路L，于是e在L?{e}的环路中，e不是割边，这与假设矛盾，因此假设不成立，即G中没有割边。

例3 确定n取怎样的值，n阶完全图Kn为欧拉图。

解：n阶完全图Kn有n个结点，每个结点的度数为n?1，故当n为奇数，n?1为偶数时，Kn为欧拉图。

例4 下图(a)(b)(c)给出了三个图，试判断哪个图是欧拉图，哪个是哈密顿图，哪个图有欧拉路。

33

(a) (b)

(c)

解：(1) 图(a)中除v2，v3度数为奇数外，其余结点均是偶数。故图(a)中有欧拉路

v2v1v3v2v4v5v8v2v5v6v8v3v6v7v3，又v1v3v7v6v8v5v4v2v1是哈密顿环，所图(a)表示的图是哈密顿图。

(2) 图(b)中每个结点的度数为偶数，故图(b)是欧拉图，其一个欧拉回路为

v1v2v7v3v2v6v3v4v5v6v7v8v1，且v1v2v3v4v5v6v7v8v1是一个哈密顿环，所以图(b)表示的图也是哈密顿图。

(3) 图(c)中每个结点的度数均为奇数，所以图(c)既不是欧拉图，也没有欧拉路，但是v1v2v3v4v8v7v6v5v1哈密顿环，因此图(c)哈密顿图。

8.5 树

8.5.1 基本知识点

基本概念：树，树林，树叶，生成树，最小生成树。

基本理论：树的等价定义；具有两个或者更多结点的树至少有两片树叶。 基本计算：给定一个图求它的生成树；利用Kruskal算法求出给定加权图的最小生成树。

8.5.2 重点与难点

树和树林：不包含环的连通图称为树，不包含环的图(即每个分图都是树的图)称

为树林；一个孤立点也是一棵树。

树叶：把树中度为1的结点称为树叶。

树的等价定义：(1)每两个结点之间由唯一的真路相连接的图是树；

34

(2)m?n?1的连通图是树；(3) m?n?1且无环的图是树。 生成树：若连通图G的一个生成子图T是一棵树，则称T为G的生成树。 最小生成树：设G?(V,E,f)是一连通的有权图，若T是G的一棵生成树，T的

e)树枝的集合为E(T)，则T的所有树枝的权的和 W ( T ) ? ? f (

称为T的权。若生成树T0在所有生成树中有最小的权，则称T0是

G的最小生成树。

e?E(T)典型题解：

例1 判定下面各类图是否为树： (1) 有n个结点、n?1条边的连通图； (2) 每对结点间都有路的图； (3) 有n个结点、n?1条边的图。 解(1) 由树的等价定义知(1)表示的是树。

(2) 该类图不一定是树，其条件只能保证图是连通的；

(3) 该类图不一定是树，条件只能保证m?n?1，但是不一定连通，如下图(a)

(a)

例2 一棵树T有两个结点度数为2，一个结点度数为3，三个结点度数为4，问它有几个叶结点。

解：设T有n个结点，m条边，x个叶结点，则n?2?1?3?x?6?x。则

m?n?1?5?x，由握手定理知：2m?19?x，则2?(5?x)?19?x，即x?9。

因此，T有9个叶结点。

例3 在下图(a)中所示的有权图G中，求一棵最小生成树T，并计算其权值。 解：利用Kruskal算法求出给定加权图的最小生成树如下图(b)： 其权值为：5?6?8?10?29。

35

(a) (b)

第9章 命题逻辑

9.1 命题和命题联结词

9.1.1 基本知识点

基本概念：命题、命题变元、命题符号化、联结词、复合命题。

基本理论：复合命题对应复合语句，用联结词连接的命题也具有真假意义。 基本计算：判断给定语句是否是命题；用各种联结词将复合命题符号化。

9.1.2 重点与难点

命题：命题表述为具有确定真假的陈述句。命题必须具备两个条件：1)语句是陈

述句；2) 语句有唯一确定的真假意义。常用大写字母P,QR,题。

原子命题：不能再分解的命题称为原子命题。 复合命题：用联结词联结而成的命题成为复合命题。

命题变元：若P表示一个确定的命题时称为命题常元，命题常元的真值是确定的

0或1，在不声明的情况下一般用P,Q,R,命题联结词：

1)否定联结词：P是一个命题，命题P的否定或非P称为P的否命题，记作?P，

称‘?’为否定联结词。?P为真当且仅当P为假。

2)合取联结词：P,Q是两个命题，命题‘P并且Q’或‘P和Q’称为P与Q的

合取式，记作P?Q。称?为合取联结词，P?Q为真当且仅当P与Q同时为真。

3)析取联结词：命题‘P或Q’称为P与Q的析取式，记作P?Q。P,Q是两个命题，

称?为析取联结词，P?Q为真当且仅当P与Q至少有一个为真。析取?表示的‘或者’是‘相容或’。‘异或’是表示P或Q中恰好有一个成立。

4)蕴含联结词：P,Q是两个命题，命题‘如果P则Q’称为P与Q的蕴含式，记

作P?Q。称?为蕴含联结词，P?Q为假当且仅当P为真，且Q为假。

5)等值联结词：P,Q是两个命题，命题‘P当且仅当Q’称为P与Q的等值式，

记作P?Q。称?为合取联结词，P?Q为真当且仅当P与Q真值相同。

36

等表示命

等表示命题变元，命题变

元的真值是不确定的，即有0和1两种可能。

典型题解

例1 判断下列语句是否为命题？不是请说明理由，是则指出是原子命题还是复合命题。 1)2是有理数。 2)10能被5整除。 3)x?y?4。 4)明天下雨吗？ 5)明天天气晴朗。 6)这朵花真美啊！ 7)全体起立！

8) 地球外的星球上也有生物。 9) 2?3?4。 10) 2?3?5。

11) 如果a和b是偶数，则a?b也是偶数。 12) 正方形的面积相等当且仅当长相等。

解：4)是疑问句，6)是感叹句，7)是祈使句，所以这三个都不是陈述句，也就不是命题。3)虽然是陈述句，但是真值不唯一，因此也不是命题。其余都是陈述句，且真值都唯一，因此是命题。1)2)5)8)9)10)不能再分解，因此是原子命题，11)12)是复合命题。

例2 将下列命题符号化： 1) 2不是素数； 2) 2是素数和偶数；

3) 2虽然是素数，但是不是偶数； 4) 2不但不是素数，而且也不是偶数。

解：用命题P：2是素数，Q：2是偶数。则符号化结果： 1)?P；2)：P?Q；3)P??Q；4)?P??Q。

例3 将下列命题符号化： 1)如果天不下雨，我就去公园； 2)只有天不下雨，我才去公园； 3) 除非天下雨，否则我就去公园； 4) 如果天下雨，我就不去公园； 5) 只有天下雨，我才去公园；

37

6) 天不下雨仅当我不去公园。 解：P：天下雨，Q：我去公园，则：

1) ?P?Q，2) Q??P；3)?Q?P；4)P??Q；5)Q?P；6)?P??Q。

例4 设P：小王是游泳冠军；Q：小王是百米赛冠军，将下列各公式翻译成自然语句。 1) P?Q；

解：小王是游泳冠军或者百米赛冠军。 2) P?Q；

解：小王既是游泳冠军也是百米赛冠军。 3) P??Q；

解：小王是游泳冠军不是百米赛冠军。 4) ?P?Q；

解：小王不是游泳冠军但是百米赛冠军。 5) P?Q；

解：小王是游泳冠军等同于百米赛冠军。 6) ?P?Q；

解：如果小王不是游泳冠军则一定是百米赛冠军。

9.2 命题公式

9.2.1 基本知识点

基本概念：命题公式，真值指派，真值表，重言式，矛盾式，可满足式。 基本理论：含有n个命题变元的命题公式共有2n组指派，将命题公式在所有赋值

下取值的情况列成表就构成了真值表。

基本计算：利用真值表判断命题的类型。

9.2.2 重点与难点 命题公式的递归定义： 1) 0和1是命题公式； 2) 命题变元是命题公式；

3) 如果A是命题公式，则?A是命题公式；

4) 如果A,B是命题公式，则A?B,A?B,A?B,A?B也是命题公式； 5) 只有有限次地利用上述1)2)3)4)而产生的符号串才是命题公式。 命题公式的真值指派：

38

设A为一命题公式，含有命题变元P1,P2,为A关于P1,P2,

,Pn，给PP12,Pn一组确定的取值，称

,Pn的一组真值指派。

永真式：若命题公式A在它所赋值下取值均为真，则称A是永真式。 矛盾式：若命题公式A在它所赋值下取值均为假，则称A是矛盾式。

可满足式：若命题公式A在它所赋值下至少存在一组赋值是真，则称A是可满足

式。

典型题解

例1 下列各符号串中，哪些是命题公式，哪些不是？ (1) P?Q?R (2) (P?Q)? (3) ?R?(P?R) (4) P?QR (5) P?Q?R (6) (P?Q)??R (7) PQR

解：根据命题公式的递归定义，(3)(5)(6)是命题公式而其余则不是。(1)中Q和R之间不能用?做联结词；(2)中二元运算?右边无运算对象；(4)中Q和R中无联结词；(7)中三个运算对象之间无运算符。

例2 设P：2是整数；Q：西安是陕西省省会；R：18有四个素因子；S：世界上面积最大的国家是加拿大。求下列复合命题的真值： (1) (P?Q)?(?R?S) (2) (P??Q?R??S)?(Q?P) (3) ((R?S)?P)?(?P??Q)

解：先确定P,Q,R,S的真值：P,Q是真命题；18的素因子有6个，所以R是假命题，世界上面积最大的国家是俄罗斯，所以S是假命题。将P,Q,R,S的真值代入命题公式中得(1)(2)(3)(4)的真值分别是0,1,0,1。

例3 判定下列公式的类型(永真式，矛盾式，可满足式) (1) (P?Q)?(?Q??P) (2) P?(Q?R) (3) ?(P?Q)?Q

39

解：分别做出这三个公式的真值表如下 (1) P Q ?P ?Q P?Q ?Q??P (P?Q)?(?Q??P) 0 0 1 1 0 1 0 1 1 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 因此(1)式是永真式。 (2) P Q R Q?R P?(Q?R) 0 0 0 0 1 1 1 1 (3) 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 1 1 0 0 0 0 0 1 1 1 因此(2)式是可满足式。

P Q P?Q ?(P?Q) ?(P?Q)?Q 0 0 1 1

0 1 0 1 1 1 0 1 0 0 1 0 0 0 0 0 因此(3)式是矛盾式。

9.3 命题公式的等值关系和蕴含关系

9.3.1 基本知识点

基本概念：等值公式，蕴含公式，等值关系，蕴含关系。

基本理论：设A,B是两个命题公式，若A?B为重言式，则称公式A,B是等值

的公式，记作A?B；若公式A?B是重言式，则称公式A蕴含公式B，记作A?B。

基本计算：判断给定的两个命题公式之间的等值或者蕴含关系。 9.3.2 重点和难点

40

代换实例：设A是一个命题公式，P1,P2,,Pn是其中出现的所有命题变元。则

(1) 用某些公式代换A中的某些命题变元；

(2) 若用公式Qi代换Pi，则必须用Qi代换A中所有的Pi。 那么，由此得到的新公式B是公式A的一个代换实例

代入规则：对于重言式中得任一命题变元出现的每一处均用同一命题公式代入，

得到的仍然是重言式。

子公式：如果C是公式A的一部分，也就是C是A中连续的几个符号，而C本身

也是一个公式，则称C是A的子公式。

置换规则：设C是A的子公式，且C?D，如果将公式A中得子公式C置换成

公式D之后，得到的公式是B，则A?B。

注：证明两个命题公式的等值关系可以采用(1)真值表方法，(2)根据置换和代入

规则从一个公式导出另一个公式。

典型题解

例1 验证等值式

(1) ?(?P??Q)??(?P?Q)?P (2) P?(Q?R)?Q?(P?R) (3) P?(Q?P)??P?(P??Q) (4) ?(P?Q)?(P??Q)?(?P?Q) 证明：(1)?(?P??Q)??(?P?Q) ?(P?Q)?(P?? )Q ?P?(Q??Q) ?P?1 ?P

(2) P?(Q?R)

??P?(?Q?R) ??Q?(?P?R) ?Q?(P?R) (3) 等式左边转化为：

P?(Q?P)

??P?(?Q?P)

?(?P?P)??Q?1??Q?1

等式右边转化为：?P?(P??Q)?P?(?P??Q) ?(P??P)??Q?1??Q?1

41

(4) 等式左边转化为： ??((P?Q)?(Q?P )) ??((?P?Q)?(Q?

例2 构造真值表证明： (1) P?Q?P?(P?Q) (2) (P?Q)?Q?P?Q (3) (P?Q)??P?Q 证明：(1) P Q P?Q P?(P?Q) (P?Q)?(P?(P?Q)) )?P?))(P??Q)?(?P?Q0 0 1 1 (2) 0 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 由上表可知(P?Q)?(P?(P?Q))永真，因此原式的蕴含关系成立。

P Q P?Q (P?Q)?Q P?Q ((P?Q)?Q)?(P?Q) 0 0 1 1 0 1 0 1 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1 1 由上表可知((P?Q)?Q)?(P?Q)永真，因此原式的蕴含关系成立。 (3) P Q P?Q ?P (P?Q)??P ((P?Q)??P)?Q 0 0 1 1

0 1 0 1 0 1 1 1 1 0 1 1 0 0 0 0 1 1 1 1 同理可知原式的蕴含关系成立。 例3 证明：若A?B?A?B，则A?B

证明：若A?B?A?B，则根据定义可得一定有(A?B)?(A?B)重言式，化简后可得(?A?B)?(?B?A)?1，所以(?A?B)?1，(?B?A)?1，即必须有

A为0、B为0或者A为1、B为1。

42

9.4 范式

9.4.1 基本知识点

基本概念：质合取式，质析取式，析取范式，合取范式，最小项，最大项，主析

取范式，主合取范式。

基本理论：对任一命题公式(P1,P2,,Pn)，若不计最小项和最大项的次序，则公

式的主析取和主合取范式的形式是唯一的。

基本计算：求一个命题公式质取范式，合取范式，主析取范式和主合取范式。

9.4.2 重点和难点

质合取式：一个由命题变元或者命题变元的否定所组成的合取式称为质合取式，

例如P,Q,P?Q,P??P等。

质析取式：一个由命题变元或者命题变元的否定所组成的析取式称为质析取式， 例如P,Q,P?Q,P??Q,?P?Q等。

析取范式：一个由质合取式的析取构成的公式称为析取范式。 合取范式：一个由质析取式的合取构成的公式称为合取范式。 最小项：设有命题变元P1,P2,,Pn，形如?Pi?的命题公式称为由命题变元

i?1nP1,P2,P1,P2,?,Pn所构成的最小项，其中每个Pi或?Pi。 i为P最大项：设有命题变元P1,P2,,Pn，形如?Pi?的命题公式称为由命题变元

i?1n?,Pn所构成的最大项，其中每个Pi或?Pi。 i为P主析取范式：由不同最小项所组成的析取式，称为主析取范式。 主合取范式：由不同最大项所组成的合取式，称为主合取范式。

注：两个具有等值关系的命题公式，其主析取和主合取范式一定是一致的。 注：求给定一个命题公式的主析取范式和主合取范式的方法有 (1) 真值表 (2) 等价置换

步骤如下1) 消去公式中得运算符?,?，分别将P?Q置换为?P?Q，将

P?Q置换为(P?Q)?(?P??Q)或者(P??Q)?(?P?Q)；

2) 将否定号?向内深入，使之只作用于命题变元：利用德摩根定律

将公式中出现的?(P?Q)转换为?P??Q，?(P?Q)置换为

?P??Q；

3) 利用双重否定律将?(?P)置换为P； 4) 利用分配律将公式变成所需要的范式；

5) 利用同一律消去矛盾的质合取式(重言的质析取式)；

6) 利用等幂律消去相同的质合取式(质析取式)，消去质合取式(质析

43

取式)中相同的合取项(析取项)；

7) 利用同一律、分配律将不包含某一命题变元的质合取式(质析取式)

置换为包含有这一命题变元的质合取式(质析取式)。

典型题解

例1 分别用两种方法求命题公式P?(Q?R)?(P?Q?R)主析取范式和主合取

范式。 解：真值表如下： P Q R Q?R P?(Q?R) P?Q?R P?(Q?R)?(P?Q?R) 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 求主析取范式，先找出真值表中取真值为1的赋值行分别为000,001,010,111。 根据

?0当Pi*??Pi?i?? *?1当Pi?Pi可得主析取范式为(?P??Q??R)?(?P??Q?R)?(?P?Q??R)?(P?Q?R)

类似的，先找出真值表中取真值为0的赋值行分别为011,100,101,110。 根据

?1当Pi*??Pi?i?? *?0当Pi?Pi可得主合取范式为(P??Q??R)?(?P?Q?R)?(?P?Q??R)?(?P??Q?R)

用等值法求解如下：

P?(Q?R)?(P?Q?R)

??(P?(Q?R))?(P?Q?R) ?(?P?(?Q??R))?(P?Q?R)

?(?P?(P?Q?R))?((?Q??R)?(P?Q?R))

?(?P?P)?(?P?Q)?(?P?R)?(?Q??R?P)?(?Q??R?Q)?(?Q??R?R)?(?P?Q)?(?P?R)?(?Q??R?P)

?(?P?Q?(?R?R))?(?P?R?(?Q?Q))?(?Q??R?P)

?(?P?Q??R)?(?P?Q?R)?(?P?R??Q)?(?P?R?Q)?(?Q??R?P) ?(P??Q??R)?(?P?Q?R)?(?P?Q??R)?(?P??Q?R)

44

注：由上述过程可知，一个命题公式的主析取和主合取范式是一一对应的，求出一个，另一个可以很方便的求出。

9.5 命题演算的推理理论

9.5.1 基本知识点

基本概念：有效结论，永真蕴含式，推理规则。 基本理论：直接证明法，间接证明法。

基本计算：利用各种推理规则构造推理的证明；推理是从前提推出结论的过程，

前提是指已知的命题公式，结论是从前提应用推理规则推出的命题公式。

9.5.2 重点和难点 永真蕴含式：设H1,H2,推理规则：

(1) 前提引入规则：在证明的任何步骤上都可以引用前提。

(2) 结论引入规则：在证明的任何步骤上所得的结论都可以在其后的证明中引

用。

(3) 置换规则：在证明的任何步骤上，命题公式的子公式都可以用与之等值的其

他命题公式置换。

(4) 代入规则：在证明的任何步骤上，重言式中得任一命题变元都可以用一命题

公式代入，得到的仍是重言式。

直接证明法：由一组前提，利用一些公认的推理规则，根据已知的蕴含式和等值

式推导出有效结论的方法称为直接证明法。

蕴含证明规则：如果能够从Q和前提集合P中推导出R来，则就能够从P中推导

出Q?R来。

间接证明法：把结论的否定当作附加前提与给定前提一起推证，若能推导出矛盾，

则说明结论是有效的。

如果H1?H2?Hn和C是一些命题公式，

?Hn?C则

称前提从前提H1,H2,,Hn推出有效结论C

典型题解：

例1 判断下列推理是否正确：

(1) 如果天气凉爽，小李就不去游泳。天气凉爽，所以小李没去游泳。 (2) 如果天气凉爽，小李就不去游泳。天气炎热，所以小李去游泳。 解：(1) P：天气凉爽；Q：小李去游泳。 前提：P??Q,P；

45

结论：?Q。

推理形式结构为：((P??Q)?P)??Q 解法一：真值表法。真值表如下： P Q ?Q P??Q (P??Q)?P ((P??Q)?P)??Q 0 0 1 1 0 1 0 1 1 0 1 0 1 1 1 0 0 0 1 0 1 1 1 1 由上式知((P??Q)?P)??Q是重言式，所以推理证明。 解法二：等值演算法

((P??Q)?P)??Q

??((?P??Q)?P)??Q

?(P?Q)??P??Q ?(P?Q)??(P?Q)?1

(2) 同理可证，不是有效结论。

例2 试证?B是?B?D，(E??F)??D，?E的有效结论。

证明：?B是前提公式?B?D的一析取项，又?E既不是(E??F)??D的前件，也不是其后件的非，因此用直接证明法不易推导，故采用间接证明法。

编号 (1) (2) (3) (4) (5) (6) (7) (8) (9) (10)

所以?B是前提的有效结论。

例2 用两种以上的方法证明(P?Q)?R?(R?P)?(S?P)

46

公式 ?(?B) ?B?D D 依据 附加前提 前提 (1)，(2) 前提 (3)，(4) (5) (6) (7) 前提 (8)，(9) (E??F)??D ?(E??F) ?(?E??F) E?F E ?E E??E 证明：方法一：假定后件(R?P)?(S?P)为假，则(R?P)为真，且(S?P)为假，由S?P为假可得S为真，P为假；在根据R?P为真可得R为假，于是

P?Q为真，(P?Q)?R为假，因此，(P?Q)?R?(R?P)?(S?P)。

方法二：用形式证明法证明，如下：

编号 公式 (1) (2) (3) (4) (5) (P?Q)?R 依据 前提 附加前提 (1) (2) (3) (4) (5) (6) (2)(7) R?P (P?Q)?P ?(?P?Q)?P (P??Q)?P (6) P (7) S?P (8) (R?P)?(S?P) 方法三：

((P?Q)?R)?((R?P)?(S?P)) ??(?(?P?Q)?R)?(?(?R?P)?(?S?P))

?((?P?Q)??R)?(R??P)?(?S?P)

?[((?P?Q)?(R??P))?(?R?(R??P))]?(?S?P) ?[(Q??P)?(?R??P)]?(?S?P)

?(Q??R)??P?(?S?P) ?(Q??R)?(?P?P)??S

?1

得证。

例3 证明?(P?Q)?(P?Q)??(P?Q) 证明；分析法证明。

先证?(P?Q)?(P?Q)??(P?Q) 假定?(P?Q)为真，则P?Q为假。

(1) 若P为真，则Q为假，此时P?Q为真，P?Q为假，因此?(P?Q)为真，因此(P?Q)??(P?Q)为真。

(2) 若P为假，则Q为真，类似(1)可证明(P?Q)??(P?Q)也为真。 于是?(P?Q)?(P?Q)??(P?Q)得证。

47

下证(P?Q)??(P?Q)??(P?Q) 假定?(P?Q)为假，则P?Q为真。

(1) 若P为真，则Q为真，此时P?Q为真，所以(P?Q)??(P?Q)?(P?Q)为假，

为假。

(2) 若P为假，则Q为假，此时P?Q为假，从而(P?Q)??(P?Q)为假，因此

得证。

命题等值关系得证。

例4 将下述推理符号化，并判断是否正确。

有红、黄、蓝、白四队参加足球联赛，如果红队第三，则当黄队第二时，蓝队第四，或者白队不是第一，或者红队第三，事实上，黄队第二。因此，如果白队第一，那么蓝队第四。

解：设P：红队第三；Q：黄队第二；R：蓝队第四；S：白队第一。则上述推理符号化为P?(Q?R),?S?P,Q?S?R。形式证明过程如下：

编号 公式 (1) ?S?P 依据 前提 附加前提 (1)(2) (3)(4) 前提 (5)(6) (2)(7) (2) S (3) P (5) Q?R (6) Q (7)

因此上述文字推理正确。

R (4) P?(Q?R) 前提 (8) S?R 例5 小李或者小张是先进工作者。如果小李是先进工作者，你是会知道的。如果小张是先进工作者，小赵也是先进工作者。你不知道小李是先进工作者，问谁是先进工作者？试利用逻辑推理来确定谁是先进工作者，并写出推理过程。 解：先将已知条件符号化。

令P：小李是先进工作者；Q：小张是先进工作者；R：你知道小李是先进工作者；T：小赵是先进工作者。

由条件得推理的前提是：P?Q,P?R,Q?T,?R 下面根据已知的前提进行形式推理，其推理过程如下表：

48

编号 公式 (1) (2) (3) (4) (5) (6) (7) (8)

依据 前提 前提 (1)(2) 前提 (4)(3) (5)(6) (5)(7) P?R ?R ?P P?Q Q T Q?T 前提 Q?T 由上述推理知小张和小王是先进工作者。

49

第10章 谓词逻辑

10.1 谓词、个体和量词

10.1.1 基本知识点

基本概念：个体，个体域，全总个体域，谓词，全称量词，存在量词，存在唯一

量词，特性谓词。

基本理论：对简单命题做进一步分析，研究它们的形式结构及内部的逻辑关系，

分析其中的个体词、谓词、量词等，这就是谓词逻辑研究的内容。

基本计算：在谓词逻辑中将命题符号化。

10.1.2 重点与难点

个体：以独立存在的客体，可以具体特定，也可以抽象泛指。 个体常元：表示具体或特定的个体的词，一般用a,b,c,个体变元：表示抽象或者泛指的个体的词，常用x,y,z,由n元谓词P和n个个体变元x1,x2,为P(x1,x2,表示。 表示。

简单命题函数：由一个谓词和若干个个体变元组成的表达式称为简单命题函数。

表示,xn组成的命题函数，

,xn)。

复合命题函数：由一个或若干个简单命题函数以及逻辑联结词所组成的命题形式

为复合命题函数。

个体域：由个体组成的集合，在不同的个体域中，同一个命题的符号化的形式可

能不同。

全总个体域：宇宙间的一切事物个体组成的个体域。如果事先没有给定个体域，

都应该以全总个体域为个体域。

谓词：用来刻画个体的性质或个体之间的关系的词。

一元谓词：谓词只有一个个体。常用来描述个体所具有的性质。例如，用F(x)表

示‘x是白色的’。

n元谓词：含n个个体的谓词称为n元谓词，描述个体之间的关系。

全称量词：符号?表示‘所有的’，‘每一个’，‘任何一个’。 存在量词：符号?表示‘存在着’，‘有一个’，‘至少有一个’。 存在唯一量词：符号?!表示‘存在唯一的’，‘恰好有一个’。

典型题解：

例1 将下列命题用谓词符号化：

50

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