应用离散数学集合与关系二元关系的性质与闭包题库试卷习题及答案

应用离散数学集合与关系PAGE§三.三二元关系地质与闭包题三.三 一.确定下列整数集合上地关系是否是自反地,反自反地,对称地,反对称地与传递地,其,当且仅当 （一） （二） （三） （四） （五） （六）（七）是地倍数 （八）与都是负地或都是非负地 解不是自反地,是反自反地,是对称地,不是反对称地,不是传递地。不是自反地,也不是反自反地,是对称地,不是反对称地,是传递地。不是自反地,是反自反地,是对称地,不是反对称地,不是传递地。是自反地,不是反自反地,是对称地,不是反对称地,是传递地。不是自反地,不是反自反地,不是对称地,是反对称地,不是传递地。不是自反地,也不是反自反地,不是对称地,是反对称地,不是传递地。是自反地,不是反自反地,不是对称地,是反对称地,是传递地。是自反地,不是反自反地,是对称地,不是反对称地,是传递地。二.设,（一）给出上地一个关系,要求既不是自反地又不是反自反地;（二）给出上地一个关系,要求既是对称地又是反对称地;（三）给出上地一个关系,要求既不是对称地又不是反对称地;（四）给出上地一个关系,要求是传递地但不是传递地。 解（一）R={⟨a,a⟩,⟨b,b⟩,⟨b,c⟩}（二）R={⟨a,a⟩,⟨b,b⟩,⟨c,c⟩}（三）R={⟨a,a⟩,⟨a,b⟩,⟨b,a⟩,⟨b,c⟩}（四）R={⟨a,a⟩,⟨b,c⟩} 三.根据下列关系地关系矩阵判断它们是否是自反地？反自反地？对称地？反对称地？传递地？并求出相应地关系,画出相应地关系图。 解假设A={a,b,c}R一是自反地,不是反自反地,不是对称地,也不是反对称地,不是传递地。R一={⟨a,a⟩,⟨a,b⟩,⟨b,a⟩,⟨b,b⟩,⟨b,c⟩,⟨c,a⟩,⟨c,c⟩}babaccR二不是自反地,不是反自反地,不是对称地,是反对称地,是传递地。R二={⟨a,a⟩,⟨a,b⟩,⟨c,a⟩,⟨c,b⟩}babaccR三是自反地,不是反自反地,是对称地,不是反对称地,是传递地。R三={⟨a,a⟩,⟨a,b⟩,⟨a,c⟩,⟨b,a⟩,⟨b,b⟩,⟨b,c⟩,⟨c,a⟩,⟨c,b⟩,⟨c,c⟩}babaccR四是自反地,不是反自反地,不是对称地,不是反对称地,是传递地。R四={⟨a,a⟩,⟨a,b⟩,⟨a,c⟩,⟨b,b⟩,⟨b,c⟩,⟨c,b⟩,⟨c,c⟩}babaccR五不是自反地,不是反自反地,不是对称地,不是反对称地,不是传递地。R五={⟨a,b⟩,⟨a,c⟩,⟨b,a⟩,⟨b,b⟩,⟨b,c⟩,⟨c,a⟩}ababccR六不是自反地,不是反自反地,是对称地,不是反对称地,不是传递地。R六={⟨a,a⟩,⟨a,b⟩,⟨a,c⟩,⟨b,a⟩,⟨c,a⟩}babaccR七是自反地,不是反自反地,不是对称地,是反对称地,不是传递地。R七={⟨a,a⟩,⟨a,c⟩,⟨b,a⟩,⟨b,b⟩,⟨c,b⟩,⟨c,c⟩}babaccR八是自反地,不是反自反地,是对称地,不是反对称地,不是传递地。R八={⟨a,a⟩,⟨a,b⟩,⟨b,a⟩,⟨b,b⟩,⟨b,c⟩,⟨c,b⟩,⟨c,c⟩}babaccR九不是自反地,不是反自反地,是对称地,不是反对称地,不是传递地。R九={⟨a,b⟩,⟨a,c⟩,⟨b,a⟩,⟨b,c⟩,⟨c,a⟩,⟨c,b⟩,⟨c,c⟩}ababcc四.设与是集合上地二元关系,试证表三.二地有关论断,即:（一）当与是自反地,则,,与也是自反地;而与则不一定。（二）当与是反自反地,则,,与也是反自反地;而与则不一定。（三）当与是对称地,则,,,与也是对称地;而则不一定。（四）当与是反对称地,则,与也是反对称地;而,与则不一定。（五）当与是传递地,则与也是传递地。而,,与则不一定。 解 （一）因为与是自反地,所以,都有,从而,都有,,与,所以它们也是自反地。而与则不一定是自反地,例如:取集合与其上地自反关系与,而与都不是自反地。（二）因为与是反自反地,所以,都有<a,a>R∧<a,a>S,从而,都有<a,a>,<a,a>,<a,a>R-S与<a,a>,所以它们也是反自反地。而与R。S则不一定是反自反地,例如:取集合与其上地反自反关系R={⟨a,b⟩,⟨a,c⟩,⟨b,a⟩}与S={⟨b,c⟩,⟨c,a⟩,⟨c,b⟩},其RC={⟨a,a⟩,⟨b,b⟩,⟨b,c⟩,⟨c,a⟩,⟨c,b⟩,⟨c,c⟩}却是自反地,不是反自反地。R。S={⟨a,a⟩,⟨a,b⟩,⟨a,c⟩}也不是反自反地。 （三）因为与是对称地,所以,若则,若则,从而,若,则;若,则;若,则;若,则;若,则,所以它们也是对称地。而则不一定是对称地,例如:取集合与其上地对称关系与,而不是对称地。（四））因为与是反对称地,所以当a≠b时,若有<a,b>∈R则<b,a>R,若有<a,b>∈S则<b,a>S,从而当,都有<a,b>∈,<a,b>∈R-S与<a,b>∈,都有<b,a>,<b,a>R-S,<b,a>,所以它们也是反对称地。而,与R。S则不一定是反对称地,例如:取集合与其上地反对称关系R={⟨a,b⟩,⟨a,c⟩,⟨c,c⟩}与S={⟨b,c⟩,⟨c,a⟩,⟨a,b⟩},其RC={⟨a,a⟩,⟨b,a⟩⟨b,b⟩,⟨b,c⟩,⟨c,a⟩,⟨c,b⟩}却不是反对称地。=R={⟨a,b⟩,⟨a,c⟩,⟨c,c⟩,⟨b,c⟩,⟨c,a⟩}不是反对称地。R。S={⟨a,a⟩,⟨a,c⟩,⟨c,a⟩}也不是反对称地。（五）因为当与是传递地,说明R二R,S二S,则（RS）二R二S二RS,所以RS是传递地。（R-一）二R-一,所以R-一也是传递地。但是,,与则不一定是传递地。例如:取集合与其上地传递关系R={⟨a,b⟩,⟨a,c⟩,⟨c,c⟩}与S={⟨b,c⟩,⟨c,a⟩,⟨b,a⟩},但是={⟨a,b⟩,⟨a,c⟩,⟨c,c⟩,⟨b,c⟩,⟨c,a⟩,⟨b,a⟩}却不是传递地,同样,={⟨a,a⟩,⟨b,a⟩,⟨b,b⟩,⟨b,c⟩,⟨c,a⟩,⟨c,b⟩}不是传递地。={⟨a,a⟩,⟨a,c⟩,⟨c,a⟩}不是传递地。五.设与其上地关系,求自反闭包,对称闭包与传递闭包。 解自反闭包对称闭包传递闭包六.设关系,求包含地最小关系使得它是（一）自反地与传递地。 （二）对称地与传递地。（三）自反地,对称地与传递地。解（一）用公式rt(R)={⟨一,一⟩,⟨一,二⟩,⟨一,四⟩,⟨二,二⟩,⟨三,三⟩,⟨四,一⟩,⟨四,二⟩,⟨四,四⟩}（二）用公式ts(R)={⟨一,一⟩,⟨一,二⟩,⟨一,四⟩,⟨二,一⟩,⟨二,二⟩,⟨二,四⟩,⟨三,三⟩,⟨四,一⟩,⟨四,二⟩,⟨四,四⟩}（三）用公式rts(R)={⟨一,一⟩,⟨一,二⟩,⟨一,四⟩,⟨二,一⟩,⟨二,二⟩,⟨二,四⟩,⟨三,三⟩,⟨四,一⟩,⟨四,二⟩,⟨四,四⟩}七.根据下列关系地关系矩阵分别求出它们地自反闭包,对称闭包与传递闭包地关系矩阵。 解两个关系地闭包地关系矩阵分别如下:,,,,八.设地关系图如图三.五所示,试给出自反闭包,对称闭包与传递闭包地关系图。aabcde图三.五题九地图 解:据上面地关系图得R={⟨a,b⟩,⟨b,c⟩,⟨b,e⟩,⟨c,d⟩,⟨d,c⟩,⟨e,e⟩},从而得r(R)={⟨a,a⟩,⟨a,b⟩,⟨b,b⟩,⟨b,c⟩,⟨b,e⟩,⟨c,c⟩,⟨c,d⟩,⟨d,c⟩,⟨d,d⟩,⟨e,e⟩},其关系图如下abdabdceces(R)={⟨a,b⟩,⟨b,a⟩,⟨b,c⟩,⟨b,e⟩,⟨c,b⟩,⟨c,d⟩,⟨d,c⟩,⟨e,b⟩,⟨e,e⟩},其关系图如下bacdebacdet(R)={⟨a,c⟩,⟨a,e⟩,⟨b,d⟩,⟨b,e⟩,⟨c,c⟩,⟨d,d⟩,⟨e,e⟩},其关系图如下bacdebacde九.设是集合上地关系, （一）若是自反地,证明与也是自反地。 （二）若是对称地,证明与也是对称地。 （三）若是传递地,证明也是传递地。 解若是自反地,则IA,则IA,IA,从而与也是自反地。若是对称地,则R-一=R,(R二)-一=(R-一)二=