有限集上二元关系性质的判定

有限集合上二元关系性质的矩阵判别法作者：张亚蕾来源：《知识窗·教师版》2019年第06期摘要：从定义出发去判断集合A上的二元关系是否是自反、反自反、对称、反对称、传递比较困难。

基于此，本文从二元关系的关系矩阵出发，总结了一种二元关系性质判断的矩阵判别法，并给出了相应的证明。

关键词：有限集合; ;二元关系; ;等价关系; ;关系矩阵关系是我们日常生活中经常听到的一个词语，在平时的工作、学习和生活中，我们不可避免地要遇到和处理许多关系。

可以说，人的一生从出生到死亡，身边都有许多关系，如生活中的父母关系、兄弟关系、夫妻关系，工作中的同事关系、上下级关系，学习中的师生关系、同学关系等。

不管在社会现象中还是在自然现象中，几乎没有孤立存在的独立体，而是各种事物相互影响、相互依存、相互制约、相互促进，从而构成了有序链环。

人类社会的文明就是在不断地提示这些有序链环的进程中形成和发展的。

抽象地看，这些“有序链环”就是多元关系。

在数学中，关系可抽象为表达集合中元素之间的关系。

在离散数学中，关系是刻画元素之间相互联系的一个重要概念，离散数学中最基本的关系就是二元关系。

所谓二元关系，就是两个事物之间相互关系的数学抽象，它是一个十分基本而有用的数学工具。

二元关系不管在自然科学，还是在社会科学中都有着非常广泛的应用，它在模糊分析、数字电路设计、数据结构、数据库分析、數据挖掘等发面也有着广泛的应用。

在模糊数学中，模糊数的二元关系、数据结构就是一个二元组，计算机科学技术中的计算机程序的输入、输出关系和数据库的数据特性关系等都是二元关系的应用。

其中，关系数据库就是以关系及其运算作为理论基础。

离散数学还在数学的许多分支学科上有着重要应用，如近世代数利用等价关系将代数系统进行分类，进而加以研究。

关系也是点集拓扑中的一个重要概念，通过关系分类来研究集合元素之间的某种联系。

熟练掌握关系的定义和性质，是学好近世代数和点集拓扑的基础。

第七章二元关系§1 有序对与笛卡尔积定义两个元素x与y按一定顺序排列构成的二元组称为一个有序对（或序偶），记为〈x,y〉，称x 为第一元素，y为第二元素。

性质 (1) ,,x y x y y x≠⇒〈〉≠〈〉(2) ,,x y u v x u y v〈〉=〈〉⇔=∧=例25 2,45,242xx x yx y+=⎧〈+〉=〈+〉⇒⎨=+⎩3,2x y⇒==−定义：设A、B为两个集合，称{},x y x A y B〈〉∈∧∈为集合A与B的笛卡尔积，记为A×B。

性质：(1) ,A A×=×=∅∅∅∅(2)笛卡尔积不满足交换律与结合律(3)笛卡尔积对并、交满足分配律×=××∪∪A B C A B A C()()()×=××∪∪B C A B A C A()()()×=××∩∩A B C A B A C()()()×=××∩∩B C A B A C A()()()(4)A C B D A B C D⊆∧⊆⇒×⊆×例A={1,2}，求P(A)×A。

§2 二元关系定义设R是集合，若R=∅或A≠∅且A中元素均为有序对，则称R为一个二元关系。

若〈x,y〉∈R，则称x与y有关系R，记为xRy。

定义：设A与B是两个集合，由A×B的子集定义的二元关系称为A到B的二元关系；当A=B 时，称之为A上的二元关系。

例 设A ={0,1}，则R 1={〈0,0〉,〈1,1〉}，R 2=∅， R 3=A ×A 都是A 上的二元关系。

例 设A 是n 元集，则A ×A 有n 2个元素，于是A ×A 有22n 个子集，由此得A 上有22n 个二元关系。

例 设A 是任一集合① 称∅是A 上的空关系 ② 称A ×A 是A 上的全域关系③ 称{},A I x x x A =〈〉∈是A 上的恒等关系。

二元关系传递性的矩阵判别法摘要：通过关系矩阵M R研究有限集合上关系R的性质既直观又迅速，在有关二元关系的自反、反自反、对称、反对称以及可传递的研究中，前四种性质已有了关系矩阵判别方法。

而可传递关系R的特征较为复杂，所以不易从其关系矩阵M R中直接判别。

本文对有限集合上的可传递关系进行了一般的讨论，并给出了定理及其证明，在此基础上给出通过其关系矩阵M R判别关系R的可传递性的方法，使得对可传递关系的判别变得非常简洁、有效。

判断一个二元关系是否具有传递性，从定义与关系图的方法比较繁琐，利用关系矩阵判断其传递性,能避免繁琐的过程，文中通过对二元关系传递性定义的深入分析, 利用关系矩阵中元素的特点与关系，通过深入研究二元关系性质和相关定理，提出了四种利用关系矩阵判断传递性的有效方法，分别为中途点判别法、复合矩阵法、十字型法、传递闭包法，同时给阐述了各方法的实用性，给出了利用关系矩阵判定二元关系传递性的简捷高效的算法，具体算法在计算机上能够高速有效的运行，然后对传递性程度进行了研究，具有一定的理论价值跟现实价值。

关键词：二元关系；传递性；关系矩阵；传递闭包；Matrix Criterion For Transitive of Binary Relation Abstract:Through the relationship matrix M R,studying the nature of a finite set of relations R is intuitive and fast, in the reflexive anti-reflexive,symmetric, antisymmetric and transitive binary relations study, the nature of the first four have a relationship matrix Identification methods. But transitive relation R is complicated, so It is not easy to determine directly from their relationship matrix M R. In this paper, it passed on a general discussion of a finite set of the transitive relationship , and gives the theorem and its proof, on this basis, identification methods for transitive of the relationship R is given by matrix M R so that the identification for transitive of the relationship R could be passed very simply and effectively. Determining whether a binary relation is transitive or not is more complicated from the definition and diagram, the use of relation matrix can avoid the cumbersome process, the paper proposed four effective methods with relationship matrix through in-depth analysisfor the definition of binary relation , the use of Characteristics and relationship ofthe elements in relationship matrix and through studying the nature of binary relations and related theorems,whichwere half-way point criterion, composite matrix,cross-shaped method, transitive closure Method, the methods were also be explained the practicality, the paper also given some simple and efficient algorithms based on relation matrix and the specific algorithms can run fast and effective in the computer, then the degree of transmission was studied ,has some theoretical value and the actual value.Key words:Binary relation ;Transitive ;Relationship Matrix ;Transitive closure;121 前言首先，二元关系是离散数学中一个重要的内容，是以有序对为元素的集合。

网络学院离散数学模拟试题1 考试时间120 分钟考试方式：开卷专业年级姓名学号一、选择填空题(每个空格3分,共30分)1．设A，B是集合，且φA，则_____必定成立。

D-B=A．A=B B．B⊆A C．A∩B=φD．A⊆B 2．{φ,{φ}}－φ=_____;CＡ. φ B. {φ} C. {φ,{φ}} D. {{φ}}3．设集合A={{0}}，则P(A) =_____。

DA. P(P({0}))B. P({0})∪φC. P({0})∪{{0}}D. {φ,{{0}}}4．设有集合A={1,2,3,4}，则从A到{0,1}的不同的函数有____个。

EA．0 B．1 C．4 D．12 E. 16 F. 24 G. 32 5．设G=(a)为12阶循环群，则G没有____阶子群。

EA．1 B．2 C．3 D．4 E. 5 F. 66．凡_____都满足消去律。

DA. 代数系统B. 半群C. 独异点D. 群7．从无向完全图K中至少删除____条边后，所得的图将成为平面图。

B5A．0 B．1 C．2 D．38．若无向图G是有99个结点，9个连通分量，则G中的边数必_____。

C A. ≤90 B. =90 C. ≥90 D. =100 E. ≥1009．下列句子中为命题的是_____。

AA．今天不是星期六。

B．考场内禁用手机！C．今天是周末吗？D．今天真冷呀！10． 任意两个不同极大项的析取式必为______。

AA. 永真公式B. 可满足公式C. 永假公式D. 等值公式二、求出谓词公式(,)(,,)u v F u v w G u v w ∃∃→∀的前束范式。

(10分)解：(,)(,,)u v F u v w G u v w ∃∃→∀ ⇔1111(,)(,,)u u F u v w G u v w ∃∃→∀ ⇔111(,)(,,)u v F u v w G u v w ⌝∃∃∨∀ ⇔1111(,)(,,)u y F u v w G u v w ∀∀⌝∨∀⇔1111(,)(,,)u v wF u vG u v w ∀∀∀⌝∨（）三、用形式证明的方法证明下列论证的有效性：“本班有些同学是有经验的C++程序员，任何C++程序员都知道对象的概念。