§3.3 二元关系的性质与闭包
习题3.3
1. 确定下列整数集合上的关系R是否是自反的、反自反的、对称的、反对称的和传递（1）x?y （5）x?y
2的，其中?x，y??R，当且仅当
（2）xy?1 （4）x?y(mod7) （6）x?y
（8）x与y都是负的或都是非负的
2（3）x?y?1或x?y?1
（7）x是y的倍数
解 （2）、（4）、（6）、（8）略
（1）不是自反的，是反自反的，是对称的，不是反对称的，不是传递的。 （3）不是自反的，是反自反的，是对称的，不是反对称的，不是传递的。 （5）不是自反的，不是反自反的，不是对称的，是反对称的，不是传递的。 （7）是自反的，不是反自反的，不是对称的，是反对称的，是传递的。 2. 设A?{a，b，c，d}，
（1）给出A上的一个关系R，要求R既不是自反的又不是反自反的； （2）给出A上的一个关系R，要求R既是对称的又是反对称的； （3）给出A上的一个关系R，要求R既不是对称的又不是反对称的； （4）给出A上的一个关系R，要求R是传递的但R?R不是传递的。
?1 解 略
3. 设A是一个n元集合，问A上有多少个关系？这其中又有多少个关系是
（1）对称的？
2
（2）反对称的？ （4）反自反的？
（6）既不是自反的也不是反自反的？
22（3）非对称的？
（5）自反的和对称的？
解 （2）、（4）、（6）略
A是一个n元集合，所以A?A有n个元素，它的子集的个数为2n，所以A上有2n个关系。
（1）将A?A中的元素分为三部分：第一部分是n个?a,a?类型的序偶，第二部分是n(n?1)/2个?a,b?类型的序偶，第三部分是n(n?1)/2个?b,a?类型的序偶。
01n(n?1)/201n?(C?C???C)(C?C???C) n(n?1)/2n(n?1)/2n(n?1)/2nnnA上对称关系的个数
?2n(n?1)/2?2n?2n(n?1)/2
n(n?1)/2（2）A上反对称关系的个数与A上对称关系的个数相等?2（
3
）
01(Cn(n?1)/2?Cn(n?1)/2。
A上对称关系的个数为
n(n?1)/201n???Cn(n?1)/2)(Cn?Cn???Cn)，其中又是自反的仅为
1 / 4
01n(n?1)/2nn(n?1)/2(Cn?C???C)?C(n?1)/2n(n?1)/2n(n?1)/2n?2个。
4. 根据下列关系的关系矩阵判断它们是否是自反的？反自反的？对称的？反对称的？
传递的？并求出相应的关系，画出相应的关系图。文档来自于网络搜索 MR1MR4?110??1?，M??0??111R2??????101???1?111??0?，M??1??011R5??????011???110??1?100?，M?R3???10???111??1?111?，M?R6???00???111?11??11?? 11?00??00??
MR7MR
解 略
10?101??110??0?，M??111?，M??1??110R8R9?????????011???011???1?101??100??0?，M??11?，M??1??100R11R12?????????010???101???011?01??11?? 01?10??11??
5. 设R和S是集合A上的二元关系，试证表3.2的有关论断，即： （1）当R和S是自反的，则R?S、R?S、R?S和R则不一定。
（2）当R和S是反自反的，则R?S、R?S、R?S和R也是反自反的；而R和
?1c?1也是自反的；而R和R?ScR?S则不一定。
（3）当R和S是对称的，则R?S、R?S、R、R?S和Rc?1也是对称的；而R?Sc则不一定。
（4）当R和S是反对称的，则R?S、R?S和R?1也是反对称的；而R?S、R和
cR?S则不一定。
（5）当R和S是传递的，则R?S和R也是传递的。而R?S、R、R?S和R?S?1则不一定。
解 （2）、（4）、（5）略
（1）因为R和S是自反的，所以?a?A，都有?a,a??R??a,a??S，从而
?a?A，都有?a,a??R?S、?a,a??R?S、?a,a??R?S和?a,a??R?1，
所以他们也是自反的。
而R和R?S则不一定是自反的，例如：取集合A?{a，b，c}及其上的自反关系
cR?{?a，a?，?a,b?,?b，b?，?c，c?}和S?{?a，a?，?a,b?,?b，b?}，而
Rc?{?a,c?,?b,a?,?b,c?,?c,a?,?c,b?}和R?S?{?a,b?}都不是自反的。
2 / 4
（3）因为R和S是对称的，所以?a,b?A，若?a,b??R则?b,a??R，若
?a,b??S则?b,a??S，从而?a,b?A，若?a,b??R?S，则?b,a??R?S；
cc若?a,b??R?S，则?b,a??R?S；若?a,b??R，则?b,a??R；若
?a,b??R?S，则?b,a??R?S；若?a,b??R?1，则?b,a??R?1，所以他们也
是对称的。文档来自于网络搜索 而R?S则不一定是对称的，例如：取集合A?{a，b，c}及其上的对称关系
R?{?a,b?,?b，a?}和S?{?b，b?}，而R?S?{?a,b?}不是对称的。
6.
设
A?{a，b，c}及其上的关系
R?{?a，a?，?a，b?，?b，c?，?c，c?}，求自反闭包r(R)、对称闭包s(R)和传
递闭包t(R)。
?a，b?，?b,b?,?b，c?，?c，c?} 解 自反闭包r(R)?{?a，a?，?a，b?，?b,a?,?b，c?，?c,b?,?c，c?} 对称闭包s(R)?{?a，a?，?a，b?，?b，c?，?c，c?,?a,c?} 传递闭包t(R)?{?a，a?，
，2?，?1，4?，?3，3?，?4，1?}，求包含R的最小关系使得它7. 设关系R?{?1是
（1）自反的和传递的。
（2）对称的和传递的。
（3）自反的、对称的和传递的。
解 略
8. 根据下列关系的关系矩阵分别求出它们的自反闭包r(R)、对称闭包s(R)和传递闭包t(R)的关系矩阵。
?110??MR??000????110??
?011??MS??111????100??
解 两个关系的闭包的关系矩阵分别如下：
?110??111??110??M?101?M?000?Mr(R)??010??s(R)t(R)??????????111??，?110??，?110?? ?111??011??111??M?111?M?111???Mr(S)??111s(S)t(S)??????????110??，?111?? ?101??，
9. 设R的关系图如图3.5所示，试给出自反闭包r(R)、对称闭包s(R)和传递闭包t(R)的关系图。
3 / 4
《应用离散数学》方景龙版-. 元关系的性质与闭包
