离散数学试题及答案(3)

<5,4>,<5,5>}

八、设R1是A上的等价关系，R2是B上的等价关系，A≠?且B≠?。关系R满足：<，>∈R?∈R1且∈R2，证明R是A×B上的等价关系（10分）。

证明 对任意的∈A×B，由R1是A上的等价关系可得∈R1，由R2是B上的等价关系可得∈R2。再由R的定义，有<，>∈R，所以R是自反的。

对任意的、∈A×B，若R，则∈R1且∈R2。由R1对称得∈R1，由R2对称得∈R2。再由R的定义，有<，>∈R，即R，所以R是对称的。

对任意的、、∈A×B，若R且R，则∈R1且∈R2，∈R1且∈R2。由∈R1、∈R1及R1的传递性得∈R1，由∈R2、∈R2及R2的传递性得∈R1。再由R的定义，有<，>∈R，即R，所以R是传递的。

综上可得，R是A×B上的等价关系。

九、设f：A?B，g：B?C，h：C?A，证明：如果h?g?f＝IA，f?h?g＝IB，g?f?h＝IC，则f、g、h均为双射，并求出f－1、g－1和h－1（10分）。

解 因IA恒等函数，由h?g?f＝IA可得f是单射，h是满射；因IB恒等函数，由f?h?g＝IB可得g是单射，f是满射；因IC恒等函数，

由g?f?h＝IC可得h是单射，g是满射。从而f、g、h均为双射。

由h?g?f＝IA，得f－1＝h?g；由f?h?g＝IB，得g－1＝f?h；由g?f?h＝IC，得h－1＝g?f。