第6章 二元关系.pptVIP

* * * * * * * * * * * * * * * * * * * 把集合上的关系进行分类 * * * * * * * * * * * * * * * * * * * * * * * * 考虑当关系图和关系矩阵的情况下如何计算并交补差 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 黑点：所有可能，笛卡尔积 红点：就坐情况，二元关系，笛卡尔积的子集 * * * * * * * * * * * * * * * * * * 6.4.5关系性质的应用 例6.4.11 假设点i和j之间有路当且仅当从结点i通过图中的边能够到达结点j，其中点i到点j的路上边的数目称为该路的长度。 （1）找出图6.4.5中从点c 开始的长度为1的所有的路； （2）找出图6.4.5中从点c 开始的长度为2的所有的路； （3）找出图6.4.5中长度 为2的所有的路。 d b c f a e 图6.4.5 * 例6.4.11 解 （1）图6.4.5中从点c开始的长度为1的所有的路有两条:c→d和c→e； （2）图6.4.5中从点c开始的长度为2的所有的路有两条： c→d→b和c→e→f； （3）图6.4.5中长度为2的所有的路有： a→c→e,a→c→d,a→b→b,a→b→f,b→b→f, b→f→d,c→d→b,c→e→f,d→c→d,d→c→e, d→b→b,d→b→f,e→f→d,f→d→b,f→d→c共15条。 * 6.5关系的闭包运算 对于一个给定的关系，可能不具有某一个特殊性质。但是，如果我们希望它具有该特定的性质，那么应该怎么做呢？ 例如，对给定集合A={1,2,3}上的关系R={1,1,1,2,2,1}，它不具有自反性。根据自反性的定义，在关系R中添加2,2，3,3这两个元素后，所得到的新关系就具有自反性。另外，还可以添加2,2，3,3，1,3，得到的新关系仍然具有自反性。 * 6.5.1关系的闭包 定义6.5.1 设R是定义在A上的关系，若存在A上的另一个关系R′，满足： （1）R′是自反的(对称的、或传递的)； （2）对任何自反的(对称的、或传递的)关系R〞，如果R? R〞，就有R′? R〞，则称为R的自反闭包(ReflexiveClosure)(对称闭包(SymmetricClosure)、或传递闭包(TransitiveClosure))，分别记为r(R)(s(R)或t(R))。 从定义6.5.1可以看出，关系的闭包是增加最少元素，使其具备所需性质的扩充。 * 例6.5.1 设A={1,2,3}，R={1,1,1,2,2,1,1,3}是A上的关系。试求R的自反闭包、对称闭包和传递闭包。 解 由关系的自反性定义知，R是自反的当且仅当对a∈A，都有a,a∈R，因此，在R中添上2,2和3,3后得到的新关系就具有自反性，且满足自反闭包的定义，即 r(R)={1,1,2,2,3,3,1,2,2,1,1,3}; * 例6.5.1(续) 由关系的对称性定义知，R是对称的当且仅当对a,b∈A，若a,b∈R，则必有b,a∈R，因此，在R中添上3,1后得到的新关系就具有对称性，且满足对称闭包的定义，即 s(R)={1,1,1,2,2,1,1,3,3,1}； 由关系的传递性定义知，R是传递的当且仅当对a,b,c∈A，若a,b∈R，且b,c∈R，则必有a,c∈R，因此，在R中添上2,2和2,3后得到的新关系就具有传递性，且满足传递闭包的定义。即 t(R)={1,1,1,2,2,1,1,3,2,2,2,3}。 * 例6.5.2 求下列关系的r(R),s(R)和t(R)。 （1）定义在整数集Z上的“＜”关系； （2）定义在整数集Z上的“=”关系。 * 例6.5.2 解 （1）定义在Z上的“＜”关系的 r(R)为“≤”， s(R)为“≠”， t(R)为“＜”； （2）定义在Z上的“=”关系的 r(R)为“=”， s(R)为“=”， t(R)为“=”。 * 例6.5.3 设集合A={1,2,3,4}，R={1,2,2,2,2,3, 3,4}是定义在A上的二元关系。 （1）画出R的关系图； （2）求出r(R),s(R),t(R),并画出其相应的关系图。 解（1）R的关系图见下图； 2 4 1 3 * 例6.5.3（续）（2） r(R)={1,2,2,2,2,3,3,4,1,1,3,3,4,4}； s(R)={1,2,2,2,2,3,2,1,3,2,3,4,4,3}；t(R)={1,2,2,2,2,3,1,3,3,4,1,4,2,4}。 r(R)，s(R)