离散数学第4章-关系ppt课件.ppt

《离散数学第4章-关系ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章关系14-1.关系及其运算关系的基本概念“关系”是一个很基本的概念,为了用数学的方法来研究和讨论各种关系,下面从集合论的观点来描述关系.例:设A={a,b,c,d,e,f},a,b,c,d,e,f分别表示６个男人,其中a是b和c的父亲,b是d的父亲,c是e和f的父亲.则这6个人中所有符合父子关系的两个人可分别用有序偶(a,b),(a,c),(b,d),(c,e),(c,f)来表示，则集合Ｒ＝｛(a,b),(a,c),(b,d),(c,e),(c,f)｝可完整地描述出集合Ａ中元素的父子关系．称R为集合上的一个关系(父子关系).例:Ａ＝｛１，２，３｝上的小于关系可表示为

2、Ｒ＝｛(1,2),(1,3),(2,3)}2两个集合之间的关系设A={a,b,c,d},B={m,p,e},A中的元素a,b,c,d分别表示4位中学教师,B中的元素m,p,e分别表示数学课程、物理课程和英语课程。如果a和b是数学教师，c是物理教师，d是英语教师。则有序偶:(a,m),(b,m)(c,p),(d,e)表示了这4位教师和他们所讲授课程的关系。由这些有序偶作为元素构成的集合R={（a,m),(b,m)(c,p),(d,e)}称为A到B的二元关系。二元关系的实质是什么？3关系的实质由于二元关系就是符合某种特定要求的有序偶的集合.因此A到B的二元关系应是笛卡儿乘积A

3、×B的子集A上的二元关系应是A上的笛卡儿乘积A×A的子集。为了便于对二元关系进行一般性的讨论，下面把二元关系的概念抽象化，即抽象地把二元关系看做是笛卡儿乘积的子集。4二元关系的定义定义设A,B是集合，R是笛卡儿乘积A×B的子集，则称R为A到B的一个二元关系。例如:设A={a,b,c,d},B={x,y,z},令R={(a,y),(b,x),(b,y),(d,x)}由于R是A×B的子集，所以R是A到B的一个二元关系。类似,可定义n元关系.5n元关系的定义定义6二元关系的定义对于二元关系R,如果(a,b)∈R，也可记作aRb，并称a与b有关系R。如果(a,b)　R，也可记作a

4、Rb，并称a与b没有关系R。定义设A是集合，R是A上的笛卡儿乘积A×A的子集，则称R为A上的一个二元关系。例如:设A={1，2，3，4，5},R={（1，1）,（2，5）,（3，1）,（4,3）,(4,5)}，由于R是A×A的子集，所以R为A上的一个二元关系。7二元关系的定义域和值域定义设S是A到B的二元关系，使(x,y)∈S的所有x组成的集合称为S的定义域，记作D(S)；使(x,y)∈S的所有y组成的集合称为S的值域，记作C(S)或R(S)。易知:D(S)就是S的所有有序偶的第一个元素构成的集合,C(S)就是S的所有有序偶的第二个元素构成的集合.8求关系的定义域和值域例

5、如:设则R的定义域D(R)，值域C(R)9例1例1:设A={2，4，6，8}，R是A上的小于关系，即当a,b∈A且a

6、,（4，12）,（6，6）,（6，12）,（12，12）}，R的定义域D(R)={2，3，4，6，12}，R的值域C(R)={2，3，4，6，12}。11例3例3设A={a,b}，B={x，y}，写出所有A到B的二元关系。，12例3例3设A={a,b}，B={x，y}，写出所有A到B的二元关系。解:由于，所以，由此可知，A×B共有子集数为=16，即共有16种A到B的二元关系：，13例3的说明此例说明，当时，A到B共可定义种不同的二元关系。问:在一个有n个元素的集合A上，可以有多少种不同的二元关系？答：共有　　　种．14三种特殊的关系对于任意集合，空集和集合本身都是它的子集

7、，常称这两种子集为平凡子集。定义笛卡儿乘积A×B的两个平凡子集，空集　和A×B本身称为集合A到B的空关系和全域关系。定义设R是A上的二元关系且满足则称R为A上的恒等关系，并记作　　。15例子例4:设集合A={1，2，3}，R是A上的二元关系，当a,b∈A且a×b>0时，（a,b）∈R。则R={（1，1）,（1，2）,（1，3）,（2，2）,（2，1）,（2，3）,（3，1）,（3，2）,（3，3）}所以R是A上的全域关系。若令当a,b∈A且a×b<0时，（a,b）∈R，则R=即R是A上的空关系。例5:设A={a,b,c,d},