离散数学学习指导书

第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

(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) (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

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