谭尚旺， 宁文杰

(中国石油大学(华东) 理学院， 山东 青岛266580)

1 引 言

对集合X上的关系R和F,令D(R)和C(R)分别表示R的定义域和值域,R∘F表示R与F的复合，Rk表示k个R的复合，t(R)表示R的传递闭包. 文中未定义的概念和记号见文献[1-2].

离散数学是信息类学科的重要基础课，关系是离散数学的重要内容之一. 各类离散数学教材都详细讨论了关系的闭包运算(例如，文献[1-3]). 在关系的各种闭包运算中以传递闭包的计算最为复杂和困难. 因此，大量文献对传递闭包的计算方法和应用进行了讨论，而关于传遍包与关系其它运算之间联系的讨论则较少. 许多文献都给出了下面一个结论(例如，文献[1]).

定理1设R和F是集合X上两个关系，则t(R∪F)⊇t(R)∪t(F).

由定理1知t(R∪F)⊆t(R)∪t(F)等价于t(R∪F)=t(R)∪t(F). 因此，在学习离散数学课程中，学生问及下面的问题：

问题1设R和F是集合X上两个关系，问是否存在使t(R∪F)=t(R)∪t(F)成立的非平凡充分必要条件？

受问题1的启发，学生进一步问及下面两个问题：

问题2设R和F是集合X上两个关系，问是否存在使t(R∩F)=t(R)∩t(F)成立的非平凡充分必要条件？

问题3设R和F是集合X上两个关系，问是否存在使t(R∘F)=t(R)∘t(F)成立的非平凡充分必要条件？对任意正整数m,是否存在使t(Rm)=[t(R)]m成立的非平凡充分必要条件？

尽管目前离散数学教材、教学参考书和涉及关系传递闭包的论文很多，但遗憾的是没有发现上述问题的任何答案. 因此，为解除学生学习上的疑惑和丰富离散数学的教学内容，在[4]中已经对问题1给出了回答. 本文将利用关系图的有关概念给出问题2和问题……