离散概念及例题.docx

。集合A的基数用|A|或card(A)表示没有任何元素的集合称为空集合,简称为空集。,由A的所有不同子集为元素组成的集合称为集合A的幂集合(powerset),简称为幂集,记作为P(A)|A|=n,则|P(A)|=,plement),简称为补集,记作为~A对于集合A和B,证明AÅB=(A–B)È(B–A)对于集合A、B和C,证明:如果AÅB=AÅC,则B=C关系由两个元素x和y按照一定的次序排列成的二元组称为一个有序对或序偶,记作<x,y>在一个序偶中,如果两个元素不相同,那么它们是不能交换次序的,称为序偶元素的有次序性,简称为有序性由n个元素a1,a2,a3,…,an按照一定次序组成的n元组称为n元序偶(orderedn-tuple),记为<a1,a2,a3,…,an>对于集合A和B,以A中元素为第一元素,B中元素为第二元素组成序偶,所有这样的序偶组成的集合称为A和B的笛卡尔积(Cartesianproduct),记作A´B,形式化表示为 A´B={<x,y>|xÎA,yÎB}:设A={a},B={b,c},C=Æ,D={1,2},列写出笛卡尔积A´B、B´A、A´C、C´A、A´(B´D)和(A´B)´D中的元素。解:A´B={<a,b>,<a,c>}B´A={<b,a>,<c,a>}A´C=C´A=ÆB´D={<b,1>,<c,1>,<b,2>,<c,2>}A´(B´D)={<a,<b,1>>,<a,<c,1>>,<a,<b,2>>,<a,<c,2>>}(A´B)´D={<<a,b>,1>,<<a,b>,2>,<<a,c>,1>,<<a,c>,2>}对于任意集合A、B、C和D,如果AÍC且BÍD,那么A´BÍC´D。如果一个集合的全体元素都是序偶,则称这个集合为一个二元关系,简称为关系,记作R。对于某个二元关系R,若<x,y>ÎR,则称x与y以R相关,也常记为xRy,如果<x,y>ÏR,则称x与y不以R相关,记作x-R-y。设|A|=n,|B|=m,A到B总共可能有多少个不同的二元关系?|A´B|=m×n,集合|P(A´B)|=2m×n次方,所以,从A到B的关系有2m×n次方个|A|=n,A上总共可能有多少个不同的二元关系?|A´B|=,集合|P(A´A)|=,A上的关系有2n×n次方个空关系:对于任意集合A,空集Æ称为A上的空关系全关系:当R={<x,y>|xÎA,yÎA},即R=A2时,称R为A上的全关系,记为EA恒等关系:设R是A上的二元关系,且满足R={<x,x>|xÎA},则称R是A上的恒等关系,:对于A={1,2,3},试列写出A上的全域关系和恒等关系。解:A上的全域关系为EA={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>,<3,1>,<3,2>,<3,3>};A上的恒等关系为IA={<1,1>,<2,2>,<3,3>}对于n个非空集合A1、A2、A3、…、An,称笛卡尔积A1´A2´A3´…´An的任意子集为依赖于A1´A2´A3´…´An的n元关系对于集合A上的关系R,如果任意元素(所有元素)xÎA,都有<x,x>ÎR,那么称集合A上的关系R具有自反性如果任意元素(所有元素)xÎA,都有<x,x>ÏR,那么称集合A上的关系R具有反自反性设R为集合A上的关系,对于任意元素xÎA和yÎA,如果<x,y>ÎR,那么<y,x>ÎR,则称集合A上的关系R具有对称性对于任意元素xÎA和yÎA,如果仅当x=y时,<x,y>ÎR且<y,x>ÎR,则称集合A上的关系R具有反对称性自反性反自反性对称性反对称性传递性定义对于所有aÎA都有<a,a>ÎR对于所有aÎA都有<a,a>ÏR若<a,b>ÎR,则有<b,a>ÎR若<a,b>ÎR并且<b,a>ÎR,则有a=b若<a,b>ÎR并且<b,c>ÎR,则有<a,c>ÎR集合IAÍRR∩IA=ÆR=R-1R∩R-1ÍIAR2ÍR关系图图中每个结点都有环图中每个结点都无环任意两个不同的结点间(要么没有弧,要么有方向相反的一对弧)。任意两个结点间至多有一条弧若a到b有弧,b到c有弧,则a到c有弧关系矩阵主对角线上全为1主对角线上全为0对称阵反对称阵(rij和rji不能同时为1)如果rik=1并且rkj=1,则rij=1对称与反对称概念不是对立的,因为一个关系可以同时具有这两种性质或者同时不具有这两种性质。设R为集合A上的关系,对于任意元素xÎA、yÎA和zÎA,如果<x,y>ÎR且<y,z>ÎR,那么<x,z>ÎR,则称集合A上的关系R具有传递性设集合A={1,2,3,4}、B={a,b,c,d}和C={2,3,