1/3
2/3
3/3
【数理逻辑】学习笔记 002 关系
一紙 痕
2021年09月12日 12:25
收录于文集
共32篇

上一篇://www.bilibili.com/read/cv13127573

【卡氏积】

卡氏积:集合X和Y的卡氏积定义为:

X%5Ctimes%20Y%3D%5Cleft%5C%7B%5Cleft(x%2Cy%5Cright)%7Cx%5Cin%20Xand%20y%5Cin%20Y%5Cright%5C%7D

例如:X%3D%5Cleft%5C%7Ba%2Cb%5Cright%5C%7D,Y%3D%5Cleft%5C%7B1%2C2%2C3%5Cright%5C%7D,那么就有X和Y的卡氏积

X%5Ctimes%20Y%3D%5Cleft%5C%7B%5Cleft(a%2C1%5Cright)%2C%5Cleft(a%2C2%5Cright)%2C%5Cleft(a%2C3%5Cright)%2C%5Cleft(b%2C1%5Cright)%2C%5Cleft(b%2C2%5Cright)%2C%5Cleft(b%2C3%5Cright)%5Cright%5C%7D

 卡氏积得名于数学家笛卡尔。

 

集合X和自身的卡氏积,也就是X%5Ctimes%20X可以写成X%5E2。

 

卡氏积中的元素称为有序对。因为它的元素顺序不能颠倒,所以得名。

我们常用的直角坐标就是有序对,%5Cleft(x%2Cy%5Cright)显然不能等同于%5Cleft(y%2Cx%5Cright)。

【二元关系】

二元关系:如果集合R是集合X和集合Y的卡氏积的子集(也就是R%5Csubseteq%20X%5Ctimes%20Y),则称R是X和Y之间的一个二元关系。

 

这个定义比较抽象,下面举个例子来理解下为什么这样定义,以及这样定义的好处是什么。

集合X=Y={我,父亲,母亲,祖父,祖母,外祖父,外祖母}

那么,X和Y的卡氏积应该就是下表中所有的元素(除了最左边一列和最上面一行)组成的集合(记为F):

现在,如果我们把红色字体的元素取出来,定义成一个集合R,那么显然有R是F(也就是X和Y的卡氏积)的子集。

这里R就是一种“亲子关系“,R中元素中的第一个人都是第二个人的双亲之一。

你也可以如法炮制,取F的另外子集,得到父子关系、母子关系、夫妻关系等等。

当然,F本身也是F的子集,所以F本身也是一个二元关系,也就是“亲人关系“。

 

用这种集合的方法来定义二元关系,提供了定义任意关系的可能性。

比如,任意抽出4个元素组成F的子集S={(父亲,母亲), (外祖父,父亲), (我,外祖父), (祖母,外祖母)},乍一看好像没有啥明显的共同关系。

但是如果有一天你发现,这4组人,有一个共同点是“一起玩过斗地主,并且第一个人是地主“。这样一种关系,就可以用集合S来表示这种关系了。

 

所以这种定义方法就具有很强的通用性。

 

如果x和y组成的%5Cleft(x%2Cy%5Cright)%5Cin%20R,则称x和y有关系R,可以记成xRy或者R%5Cleft(x%2Cy%5Cright)。

如果R%5Csubseteq%20X%5E2,也称R是X中的二元关系。

【相关概念】

定义域:R的定义域为dom(R)={x|存在y使得R(x,y)}

值域:R的值域为ran(R)={y|存在x使得R(x,y)}

像:集合U在关系R下的像定义为R[U]={y∈ran(R)|存在x∈U使得R(x,y)}

逆像:集合V在关系R下的逆像定义为R-1[V]={x∈dom(R)|存在y∈V使得R(x,y)}

如果觉得这几个概念理解有困难,可以看下图的例子来帮助理解。

逆:二元关系R的逆定义为R%5E%7B-1%7D%3D%5Cleft%5C%7B%5Cleft(x%2Cy%5Cright)%7C%5Cleft(y%2Cx%5Cright)%5Cin%20R%5Cright%5C%7D

 

可以参考大于和小于的关系,如果大于是R,那么小于就是R%5E%7B-1%7D,因为

x%3Ey等价于y%3Cx

 

复合:二元关系和的复合定义为

R%5Ccirc%20S%3D%5Cleft%5C%7B%5Cleft(x%2Cz%5Cright)%7C%E5%AD%98%E5%9C%A8y%E4%BD%BF%E5%BE%97%5Cleft(x%2Cy%5Cright)%5Cin%20R%E5%B9%B6%E4%B8%94%5Cleft(y%2Cz%5Cright)%5Cin%20S%5Cright%5C%7D

 

比如,大于等于和小于等于的复合就是:

%5Cgeq%5Ccirc%5Cle%3D%5Cleft%5C%7B%5Cleft(x%2Cz%5Cright)%7C%E5%AD%98%E5%9C%A8y%E4%BD%BF%E5%BE%97x%5Cgeq%20y%E5%B9%B6%E4%B8%94%20y%5Cle%20z%5Cright%5C%7D

再来个通俗点的例子:父子⚬父子=爷孙

【n元关系】

可以将卡氏积和二元关系都推广到n元:

 

n元卡氏积:

X_1%5Ctimes%20X_2%5Ctimes%5Ccdots%5Ctimes%20X_n%3D%5Cleft%5C%7B%5Cleft(x_1%2Cx_2%2C%5Ccdots%2Cx_n%5Cright)%7Cx_1%5Cin%20X_1%E4%B8%94%20x_2%5Cin%20X_2%5Ccdots%20x_n%5Cin%20X_n%5Cright%5C%7D

 

n元关系:如果集合R是n个集合X_1%2CX_2%2C%5Ccdots%2CX_n的卡氏积的子集(R%5Csubseteq%20X_1%5Ctimes%20X_2%5Ctimes%5Ccdots%5Ctimes%20X_n),那么就称R是X_1%2CX_2%2C%5Ccdots%2CX_n上的n元关系。

【习题选解】

习题1.3.3 判断下列命题是否对所有集合A, B, C和D成立,并给出理由:

(1)%09A%5Ctimes%5Cleft(B%5Ccup%20C%5Cright)%3D%5Cleft(A%5Ctimes%20B%5Cright)%5Ccup%5Cleft(A%5Ctimes%20C%5Cright)

(2)%09%5Cleft(A%5Ctimes%20B%5Cright)%5Ccap%5Cleft(C%5Ctimes%20D%5Cright)%3D%5Cleft(A%5Ccap%20C%5Cright)%5Ctimes%5Cleft(B%5Ccap%20D%5Cright)

(3)%09%5Cleft(A%5Ctimes%20B%5Cright)%5Ccup%5Cleft(C%5Ctimes%20D%5Cright)%3D%5Cleft(A%5Ccup%20C%5Cright)%5Ctimes%5Cleft(B%5Ccup%20D%5Cright)

解:

(1)     根据卡氏积的定义:

左边=%5Cleft%5C%7B%5Cleft(x%2Cy%5Cright)%7Cx%5Cin%20A%2Cy%5Cin%20B%5Ccup%20C%5Cright%5C%7D

右边=%5Cleft%5C%7B%5Cleft(x%2Cy%5Cright)%7Cx%5Cin%20A%2Cy%5Cin%20B%5Cright%5C%7D%5Ccup%5Cleft%5C%7B%5Cleft(x%2Cy%5Cright)%7Cx%5Cin%20A%2Cy%5Cin%20C%5Cright%5C%7D

%3D%5Cleft%5C%7B%5Cleft(x%2Cy%5Cright)%7Cx%5Cin%20A%2Cy%5Cin%20B%5C%20or%5C%20x%5Cin%20A%2Cy%5Cin%20C%5Cright%5C%7D

%3D%5Cleft%5C%7B%5Cleft(x%2Cy%5Cright)%7Cx%5Cin%20A%2Cy%5Cin%20B%5Ccup%20C%5Cright%5C%7D

所以左边=右边,(1)成立

(2)     根据卡氏积的定义:

左边=%5Cleft%5C%7B%5Cleft(x%2Cy%5Cright)%7Cx%5Cin%20A%2Cy%5Cin%20B%5Cright%5C%7D%5Ccap%5Cleft%5C%7B%5Cleft(x%2Cy%5Cright)%7Cx%5Cin%20C%2Cy%5Cin%20D%5Cright%5C%7D

%3D%5Cleft%5C%7B%5Cleft(x%2Cy%5Cright)%7Cx%5Cin%20A%2Cy%5Cin%20B%2Cx%5Cin%20C%2Cy%5Cin%20D%5Cright%5C%7D

%3D%5Cleft%5C%7B%5Cleft(x%2Cy%5Cright)%7Cx%5Cin%20A%5Ccap%20C%2Cy%5Cin%20B%5Ccap%20D%5Cright%5C%7D

右边=%5Cleft%5C%7B%5Cleft(x%2Cy%5Cright)%7Cx%5Cin%20A%5Ccap%20C%2Cy%5Cin%20B%5Ccap%20D%5Cright%5C%7D

所以左边=右边,(2)成立

(3)     取A%3D%5Cleft%5C%7B1%5Cright%5C%7D%2CB%3D%5Cleft%5C%7Ba%5Cright%5C%7D%2CC%3D%5Cleft%5C%7B2%5Cright%5C%7D%2CD%3D%5Cleft%5C%7Bb%5Cright%5C%7D

左边=%5Cleft%5C%7B%5Cleft(1%2Ca%5Cright)%5Cright%5C%7D%5Ccup%5Cleft%5C%7B%5Cleft(2%2Cb%5Cright)%5Cright%5C%7D

%3D%5Cleft%5C%7B%5Cleft(1%2Ca%5Cright)%2C%5Cleft(2%2Cb%5Cright)%5Cright%5C%7D

%3D%5Cleft%5C%7B%5Cleft(1%2Ca%5Cright)%2C%5Cleft(1%2Cb%5Cright)%2C%5Cleft(2%2Ca%5Cright)%2C%5Cleft(2%2Cb%5Cright)%5Cright%5C%7D

此时左边与右边不等,所以(3)不成立

【词汇中英日对照表】