x~p

离散数学第三章集合与关系（1~7）

第三章集合与关系（1~7）

3-1集合的概念和表⽰法

说明集合的⽅法有两种：

列举法（eg.A={a,b,c,d}）

叙述法（eg.S₁={x|x是中国的省}）

我们⽤p(x)表⽰任何谓词，则{x|p(x)}可表⽰集合。如果p(b)为真，那么b∈A，否则b∉A

外延性原理：两个集合是相等的，当且仅当它们有相同的成员

两个集合A和B是相等的，记作A=B，两个集合不相等，则记作A≠B

集合的元素还可以允许是⼀个集合，例如：S={a,{1,2},p,{q}}。必须指出：q∈{q},但q∉S，同理1∈{1，2}，但1∉S

A⊆B：A是B的⼦集，或A包含在B内，或B包含A

A⊆B⇔∀x(x∈A→x∈B)

根据⼦集的定义，显然有：

A⊆A(⾃反性)

(A⊆B)∧(B⊆C)⇒(A⊆C)(传递性)

集合A和集合B相等的充分必要条件是这两个集合互为⼦集(★这个定理很重要，今后证明两个集合相等，主要利⽤这个互为⼦集的判定

条件)

A⊂B：A为B的真⼦集

A⊂B⇔(∀x)(x∈A→x∈B)∧(∃x)(x∈B∧x∉A)

A⊂B⇔A⊆B∧A≠B

空集(Φ)：不包含任何元素的集合

对任意⼀个集合A，Φ⊆A

全集(E):对任⼀x∈A，因A⊆E，故x∈E

幂集

给定集合A，由集合A的所有⼦集为元素组成的集合，称为集合A的幂集，记为P(A)。

eg1.求幂集：{a,{a}}

解：{Φ，{a}，{{a}}，{a,{a}}}

eg2.求幂集：{{1，{2，3}}}

解：{Φ，{{1，{2，3}}}}

eg3.求幂集：P(P(Φ))

解：P(P(Φ))={Φ，{Φ}}，则幂集为{Φ，{Φ}，{{Φ}}，{Φ，{Φ}}}

如果有限集合A有n个元素，则其幂集P(A)有2ⁿ个元素

3-2集合的运算

(1).集合的交(∩)

S=A∩B={x|(x∈A)∧(X∈B)}

性质

A∩A=A

A∩Φ=Φ

A∩E=A

A∩B=B∩A

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

n个集合A₁,A₂,…,An的交可记为：

(2).集合的并(∪)

S=A∪B={x|(x∈A)∨(x∈B)}

性质

A∪A=A

A∪E=E

A∪Φ=A

A∪B=B∪A

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

n个集合A₁,A₂,…,An的并可记为：

分配律

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

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

吸收律

A∪(A∩B)=A

A∩(A∪B)=A

A⊆B，当且仅当A∪B=B或A∩B=A

(3).集合的补(—，~)

相对补(—)

S=A—B={x|x∈A∧x∉B}={x|x∈A∧¬(x∈B)}(属于前者⽽不属于后者)

绝对补(~)

~A=E—A={x|x∈E∧x∉A}

性质

~(~A)=A

~E=Φ，~Φ=E

A∪~A=E，A∩~A=Φ

~(A∪B)=~A∩~B，~(A∩B)=~A∪~B

A—B=A∩~B(★)

A—B=A—(A∩B)

A∩(B—C)=(A∩B)—(A∩C)

若A⊆B，则：

~B⊆~A

(B—A)∪A=B

(4).集合的对称差(⊕)

S=A⊕B=(A—B)∪(B—A)={x|x∈A不可兼或x∈B}（A与B的并集去掉A与B的交集）

性质

A⊕B=B⊕A

A⊕Φ=A

A⊕A=Φ

A⊕B=(A∩~B)∪(~A∩B)

(A⊕B)⊕C=A⊕(B⊕C)

3-4序偶与笛卡尔积

序偶

⼀般地说，两个具有固定次序的客体组成⼀个序偶，它常常表达两个客体之间的关系，记作。

eg.<上、下>，<左、右>，<3，4>

序偶可以看作是具有两个元素的集合。但它与⼀般集合不同的是序偶具有确定的次序。在集合中{a,b}={b,a}，但对序偶≠

两个序偶相等，=当且仅当x=u,y=v

在序偶中，a称第⼀元素，b称第⼆元素

三元组是⼀个序偶，其第⼀元素本⾝也是⼀个序偶，可形式化为<,z>。<,z>≠>，因为>不是三元组

同理，四元组被定义为⼀个序偶，其第⼀元素为三元组，故四元组有形式为<,w>。这样，n元组可写为<,xn>。

⼀般地，n元组可简写为,第i个元素x(i)称作n元素组的第i个坐标

笛卡尔积

令A和B是任意两个集合，若序偶的第⼀个成员是A的元素，第⼆个元素是B的元素。所有这样的序偶集合，称为集合A和B的笛卡尔乘积或

直积，记作A×B

A×B={|(x∈A)∧(x∈B)}

A={α,β},B={1,2,3}

A×B={<α.1>,<α,2>,<α,3>,<β,1>,<β,2>,<β,3>}

B×A={<1,α>,<1,β>,<2,α>,<2,β>,<3,α>,<3,β>}

(A×B)∩(B×A)=∅

可得出A×B≠B×A

若A=∅或B=∅，则A×B=∅

(A×B)×C≠A×(B×C)

设A,B,C为任意三个集合，即有：

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

A×(B∩C)=(A×B)∩(A×C)

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

(A∩B)×C=(A×C)∩(B×C)

若C≠∅,则A⊆B⇔(A×B⊆B×C)⇔(C×A⊆C×B)

3-5关系及其表⽰

任⼀序偶的集合确定了⼀个⼆元关系R，R中任⼀序偶可记作∈R或xRy。不在R中的任⼀序偶可记作∉R

前域：令R为⼆元关系，由∈R的所有x组成的集合domR称为R的前域，即：domR={x|(∃y)(∈R)}

值域：使∈R的所有y组成的集合ranR称作R的值域，即：ranR={y|(∃x)(∈R)}

域：R的前域和值域⼀起称作R的域，记作FLDR，即：FLDR=domR∪ranR

设A={1，2，3，5}，B={1，2，4}，H={<1,2>,<1,4>,<2,4>,<3,4>}

解：domH={1,2,3}ranH={2,4}FLDH={1,2,3,4}(重复多余的去掉)

令X和Y是任意两个集合，直积X×Y的⼦集R称作X到Y的关系

把X×Y的两个平凡⼦集X×Y和∅，分别称作X到Y的全域关系和空关系

当X=Y时，关系R是X×X的⼦集，这时称R为在X上的⼆元关系

设X={1，2，3，4}，求X上的关系>及dom>，ran>

解：>={<2,1>,<3,1>,<3,2>,<4,1>,<4,2>,<4,3>}

dom>={2,3,4},ran>={1,2,3}

设I(x)是X上的⼆元关系且满⾜I(x)={|x∈X},则称I(x)是X上的恒等关系

A={1,2,3}，则I(A)={<1,1>,<2,2>,<3,3>}

若Z和S是从集合X到集合Y的两个关系，则Z，S的并、交、补、差仍是X到Y的关系

eg.设A={1，2，3，4}，写出集合A上⼤于关系>的关系矩阵

解：>={<2,1>,<3,1>,<3,2>,<4,1>,<4,2>,<4,3>}

关系图：关系集合,对于x(i)Ry(i),则⽤箭头由x(i)指向y(i)

eg.设A={1，2，3，4，5}，在A上的⼆元关系R给定为：R={<1,5>,<1,4>,<2,3>,<3,1>,<3,4>,<4,4>}画出R的关系图

3-6关系的性质

(1).⾃反

设R为定义在集合X上的⼆元关系，如果对于每个x∈X，有xRx,则称⼆元关系R是⾃反的

R在X上⾃反⇔(∀x)(x∈X→xRx)

eg.A={1,2,3}

R₁={<1,1>,<2,2>},R₂={<1,1>,<2,2>,<3,3>}

则R₁不是⾃反的，R₂是⾃反的

(2).对称

对于每个x,y∈X，每当xRy,就有yRx，则称集合X上关系R是对称的(有则必须要有)

R在X上对称⇔(∀x)(∀y)(x∈X∧y∈X∧xRy→yRx)

A={1,2,3}

R₁={<1,2>,<2,1>},R₂={<1,2>,<2,1>,<1,1>},R₃={<1,2>,<2,1>,<2,3>}

R₁,R₂是对称的，R₃不对称

(3).传递

对于任意x,y,z∈X,每当xRy,yRz时就有xRz，称关系R在X上是传递的

A={1,2,3}

R₁={<1,2>,<2,2>},R₂={<1,2>},R₃={<1,2>,<2,3>,<1,3>,<2,1>}

R₁,R₂是传递的，R₃因没有<1,1>,<2,2>，所以不传递

(4).反⾃反

对于每个x∈X，都有∉R,则R称作反⾃反的

R在X上反⾃反⇔(∀x)(x∈X→∉R)

⼀个不是⾃反的关系，不⼀定就是反⾃反的

(5).反对称

除了外，不含有其他对称元素

A={1,2,3}

R₁={<1,1>,<2,2>},R₂={<1,2>,<1,3>},R₃={<1,2>,<2,3>,<1,3>,<2,1>}

R₁,R₂是反对称的，R₃不反对称

可能有某种关系，既是对称的，⼜是反对称的；也可能既不对称，也不反对称

空集除了⾃反以外，其他性质都有

3-7集合关系和逆关系

复合关系

定义：设R为X到Y的关系，S为从Y到Z的关系，则R○S称为R和S的复合关系

eg.R={<1,2>,<3,4>,<2,2>},S={<4,2>,<2,5>,<3,1>,<1,3>}

解：R○S={<1,5>,<3,2>,<2,5>}

S○R={<4,2>,<3,2>,<1,4>}≠R○S

(R○S)○R={<3,2>}

R○(S○R)={<3,2>}

R○R={<1,2>,<2,2>}

S○S={<4,5>,<3,3>,<1,1>}

R○R○R={<1,2>,<2,2>}

R○R○R○R…○R○R(n个R相乘)=Rⁿ

复合关系也可⽤矩阵表⽰

逆关系

定义：设R为X到Y的⼆元关系，如将R中每⼀序偶的元素顺序互换，所得到的的集合称为R的逆关系，记作R^c