《应用离散数学》方景龙版-. 元关系的性质与闭包.docVIP

§3.3 二元关系的性质与闭包 习题3.3 1. 确定下列整数集合上的关系是否是自反的、反自反的、对称的、反对称的和传递的，其中，当且仅当 （1） （2） （3） （4） （5） （6） （7）是的倍数 （8）与都是负的或都是非负的 解 （2）、（4）、（6）、（8）略 （1）不是自反的，是反自反的，是对称的，不是反对称的，不是传递的。 （3）不是自反的，是反自反的，是对称的，不是反对称的，不是传递的。 （5）不是自反的，不是反自反的，不是对称的，是反对称的，不是传递的。 （7）是自反的，不是反自反的，不是对称的，是反对称的，是传递的。 2. 设， （1）给出上的一个关系，要求既不是自反的又不是反自反的； （2）给出上的一个关系，要求既是对称的又是反对称的； （3）给出上的一个关系，要求既不是对称的又不是反对称的； （4）给出上的一个关系，要求是传递的但不是传递的。 解 略 3. 设是一个元集合，问上有多少个关系？这其中又有多少个关系是 （1）对称的？ （2）反对称的？ （3）非对称的？ （4）反自反的？ （5）自反的和对称的？ （6）既不是自反的也不是反自反的？ 解 （2）、（4）、（6）略 是一个元集合，所以有个元素，它的子集的个数为，所以上有个关系。 （1）将中的元素分为三部分：第一部分是个类型的序偶，第二部分是个类型的序偶，第三部分是个类型的序偶。 上对称关系的个数 （2）上反对称关系的个数与上对称关系的个数相等。 （3）上对称关系的个数为，其中又是自反的仅为个。 4. 根据下列关系的关系矩阵判断它们是否是自反的？反自反的？对称的？反对称的？传递的？并求出相应的关系，画出相应的关系图。 解 略 5. 设和是集合上的二元关系，试证表3.2的有关论断，即： （1）当和是自反的，则、、和也是自反的；而和则不一定。 （2）当和是反自反的，则、、和也是反自反的；而和则不一定。 （3）当和是对称的，则、、、和也是对称的；而则不一定。 （4）当和是反对称的，则、和也是反对称的；而、和则???一定。 （5）当和是传递的，则和也是传递的。而、、和则不一定。 解 （2）、（4）、（5）略 （1）因为和是自反的，所以，都有，从而，都有、、和，所以他们也是自反的。 而和则不一定是自反的，例如：取集合及其上的自反关系和，而和都不是自反的。 （3）因为和是对称的，所以，若则，若则，从而，若，则；若，则；若，则；若，则；若，则，所以他们也是对称的。 而则不一定是对称的，例如：取集合及其上的对称关系和，而不是对称的。 6. 设及其上的关系，求自反闭包、对称闭包和传递闭包。 解 自反闭包 对称闭包 传递闭包 7. 设关系，求包含的最小关系使得它是 （1）自反的和传递的。 （2）对称的和传递的。 （3）自反的、对称的和传递的。 解 略 8. 根据下列关系的关系矩阵分别求出它们的自反闭包、对称闭包和传递闭包的关系矩阵。 解 两个关系的闭包的关系矩阵分别如下： ，， ，， 9. 设的关系图如图3.5所示，试给出自反闭包、对称闭包和传递闭包的关系图。 a b c d e 图3.5 习题9的图 解 略 10. 设是集合上的关系， （1）若是自反的，证明和也是自反的。 （2）若是对称的，证明和也是对称的。 （3）若是传递的，证明也是传递的。 解 略 11. 设和是集合上的关系，且，证明 ，， 解 略