偏序关系哈斯图的一种求解方法
邹又姣，冉占军，王晓峰
（西安理工大学应用数学系，陕西西安７１００４８）
摘要
引入基本边和生成边的概念，并从偏序关系的特性人手，给出一种通过计算基本边和生成边来求解
偏序关系哈斯图的方法。
关键词
哈斯图；偏序关系；基本边；生战边
０１５８
中图分类号文献标识码
Ａ
文章编号１００８—１３９９（２０１３）０１—００５５—０３
在计算机科学中，关系的概念具有十分重要的意义。而偏序关系是关系中比较典型和重要的一种关系，它是集合上的传递关系，同时还提供了一种比较集合元素间次序的工具，其偏序关系的关系图
地描述了偏序集合中元素间的次序关系。
对给定的偏序集（Ａ，≤），它的盖住关系是唯一的，我们可以用盖住的定义求解哈斯图。
例１
给定集合Ａ一｛２，３，６，８），令
≤一｛＜ｚ，ｙ＞：ｏＺ＂整除Ｙ｝，
——哈斯图简单形象地描述了集合间元素的这种
次序关系。
离散数学教材中一般采用计算盖住关系的方法来求解一个偏序关系的哈斯图ｎ。］，这种方法在比较元素的次序时运算量大，容易出错，并且有时运用起来比较困难，学生普遍感觉比较棘手。有些学者对哈斯图进行了研究并给出了一些重要的求解方法［４，但这些方法学生不易掌握，运用困难。
本文通过研究偏序关系的性质，分析并证明了偏序关系的哈斯图运算转化为关系的复合运算，这一方法思路清晰，让学生在求解哈斯图时有法可依。
１
、
画出这个偏序关系的哈斯图。
解
由题意可得偏序关系
≤一｛（２，２），（３，３），（６，６），（８，８＞，
２，６＞，（２，８），＜３，６）｝，
所以
ＣＯＶＡ一｛（２，６＞，＜２，８），（３，６）），
其哈斯图如图１所示。
预备知识
定义１¨。２３
设Ａ是一个集合，如果Ａ上的一个
图１
二元关系尺满足自反性、反对称性和传递性，则称Ｒ是Ａ上的一个偏序关系，记作≤，序偶（Ａ，≤＞称为偏序集。
定义２¨１
例１哈斯图
如用“盖住”的定义来求解关系Ｒ的基本边，我们需要一一考虑（２，６），（２，８＞和（３，６）这三个序偶
在偏集中，如果ｚ，ｙ∈Ａ，ｚ≤ｙ，
是否是盖住关系里的元素，而在考虑每一个序偶比如（２，６＞时都要将２和６与集合Ａ中的元素２，３，６，８进行比较。对这个例子而言，比较的次数为
ＡＩ×２×ｔ一４×２×３—２４，
ｚ≠Ｙ且没有其他元素ｚ满足ｚ≤ｚ，ｚ≤ｙ，则称元素Ｙ盖住元素ｚ，并记
ＣＯＶＡ一｛（ｚ，了＞：ｚ，Ｙ∈Ａ；Ｙ盖住ｚ）。哈斯图是偏序关系的关系图的简化，它更清楚
收稿日期：２０１０—１１—２５；修改日期：２０１２—１２－２４
基金项目：西安理工大学精品课程建设项目（离散数学）
作者简介：邹又姣（１９７５一），女，湖北孝感人，博士研究生，讲师，从事
密码学研究．Ｅｍａｉｌ：ｙｊｚｏｕ２００９＠１２６．ｃｏｒｎ
冉占军（１９７７－－），男，河南郑州人，讲师，从事计算机软件及应用研究。Ｅｍａｉｌ：ｒａｎｚｈｊ＠１２６．ｃｏｒｎ
王晓峰（１９６６－－）．女，河南人，博士，教授．从事密码理论及
其中
ｔ—ＩＲ—ＪＡ１，
而ｋ为Ａ上的相等关系。当Ｉ
Ａ
Ｉ较大或者ｔ的值较
大时这个运算量就更大了，而且这种方法在比较元素的大小时很容易出错。
定义３Ｅ卜胡
设Ｒ是Ａ上的二元关系，如果有另
一个关系Ｒ７满足
（１）Ｒ７是可传递的．
应用研究。Ｅｍａｉｌ：ｘｆｗａｎ９６６＠ｓｉｎａ．ｃｏｍ．ｃａ
５６
高等数学研究
（２）Ｒ７三Ｒ．
然而Ｒ２∈Ｒ，从而
Ｒ３一Ｒ２。Ｒ
Ｒ４一Ｒ３。Ｒ
（３）对任何可传递关系彤，如果有彤三Ｒ，就
奄Ｒ］Ｒ；．
则称Ｒ７是Ｒ的传递闭包。
定理１Ⅲ
设Ｉ
Ａ
ＥＲ２，
Ｅ
Ｒ２。ＲＥＲ２，…
Ｒ”一［Ｒ２．
Ｉ一押，Ｒ是Ａ上的二元关系，
于是关系Ｒ的生成边为
Ｒ２
则Ｒ的传递闭包
ｔ（Ｒ）一ＲＵＲ２
Ｕ
Ｒ３
Ｕ…Ｕ
Ｒ“一Ｒ２．
ＵＲ３Ｕ…ＵＲ”．
结论１的基本边集合
设Ｒ是Ａ上的拟序关系，那么关系尺
定理２Ｅ２１设Ｒ是Ａ上的二元关系，那么Ｒ是
传递的当且仅当ｔ（Ｒ）一Ｒ．
２
ＣＯＶＡ—Ｒ—Ｒ２．
Ａ上的偏序关系Ｒ是Ａ上的自反、反对称、传递
偏序关系的哈斯图求解法
由于定义法求解关系Ｒ的哈斯图存在运算量
关系，我们如何利用结论１得到其基本边集合呢？
结论２的基本边集合
ＣＯＶＡ一（Ｒ一厶）一（Ｒ一厶）２．
设Ｒ是Ａ上的偏序关系，那么关系Ｒ
大、比较时容易出错的特点，在此，我们给出了一种便于计算的简单方法。这种方法在关系Ｒ中的元素较多时优点尤为明显。
２．１
证明
设Ｒ７一Ｒ一厶，若Ｒ７是Ａ上的拟序关
方法的提出和证明
为了清楚地表示出偏序关系的哈斯图中的边及
系，则由结论１即证。
显然关系Ｒ７是Ａ上的反自反关系。下证Ｒ７是Ａ
后续方法描述的方便起见，我们引入一个新的概念。
定义４
上的可传递关系。
设（口，６），＜６，ｆ＞∈Ｒ７，由Ｒ７反自反知ａ，ｂ，Ｃ互不相同，则（以，６＞，（ｂ，ｆ）∈Ｒ．而Ｒ是Ａ上的可传递关系，从而得到＜口，ｃ）∈Ｒ且ａ≠ｆ。故Ｒ７是Ａ上的可传递关系。
２．２
把ＣＯＶＡ中的元素称为基本边，把在
Ｒ中而不在ＣｏＶＡ中的边称为由基本边通过传递性生成的边，简称生成边。
由定理１和定理２得到，如果Ｒ是Ａ上的传递关
系，则
Ｒ２
应用举例及两种方法运算量的比较
例２
Ｕ．Ｒ３Ｕ…ＵＲ”∈Ｒ，
对Ａ一｛ａ，ｂ，ｆ，ｄ，ｅ）上的偏序关系
从而有
Ｒ１ＥＲ（ｉ一２，３，…，竹）．
Ｒ一｛（ａ，口＞，（ａ，６），（ａ，ｃ＞，＜口，ｄ），（ａ，８＞，
＜ｂ，６＞，（ｂ，ｆ），＜ｂ，ｅ），＜ｃ，ｆ＞，（ｂ，Ｐ＞，
．
若Ｒ是Ａ上的拟序关系，即Ｒ是反自反的、可传递的，现来分析这种关系的基本边。假设（ａ，６＞∈Ｒ，（６，ｆ）∈Ｒ，由Ｒ是Ａ上的反自反关系，有ａ≠ｂ，ｂ≠ｆ；又由Ｒ是Ａ上的传递关系，有（ａ，ｆ）∈Ｒ并且ｎ≠Ｃ。而｛（口，６＞｝。｛（６，ｃ）｝一｛＜口，ｆ）｝，从而得到：如果＜ｎ，６），（６，ｆ）是Ｒ的基本边，则由其通过传递关系生成的边（ａ，ｃ）必然在Ｒ２中，并且ａ≠ｃ。而且所有由两条基本边通过传递关系生成的边必然在Ｒ２中。
如果有三条基本边（口，６），（ｂ，ｃ＞，（ｆ，ｄ＞∈Ｒ，则由Ｒ是Ａ上的传递关系，有＜口，ｆ＞∈Ｒ且口，６，ｆ，ｄ互
不相同。而
｛（口，６））。｛（ｂ，ｆ））一｛＜ａ，ｆ＞）∈Ｒ２，．｛（口，ｆ）｝。｛（ｆ，ｄ））一｛（ｎ，ｄ＞｝∈Ｒ３，
（ｄ，ｄ＞，（ｄ，Ｐ＞，（ｅ，Ｐ＞），
画出其哈斯图。
解
因为
Ｒ一厶一｛（ａ，６），＜ａ，ｆ），（ａ，ｄ＞，（ａ，Ｐ＞，
（ｂ，ｆ），＜ｂ，Ｐ＞，（Ｃ，ｅ），（ｄ，ｅ）｝，（Ｒ—ｊＡ）２一｛（ａ，ｆ＞，（口，ｅ），（ｂ，Ｐ）），
所以
ＣＫ）、厂４一｛＜口，６），（口，ｄ＞，（６，ｆ），（ｃ，已），（ｄ，ｅ＞），
其哈斯图如图２所示。
即由三条基本边通过传递性生成的边必然在Ｒ３中。
由ｉ条基本边通过传递关系生成的边必然在Ｒ。中，从而关系Ｒ的生成边为Ｒ其基本边
ＣＯＶＡ—Ｒ—Ｒ２ＵＲ３
２
图２例２哈斯图
ＵＲ３Ｕ…ＵＲ”，故对于例２而言，用定义法求解ＣＯＶＡ需要比较８０次，而如果用本文中提出的方法，仅需要比较运算２４次数。比如Ｒ一，。中的序偶（口，６＞，因为Ｒ—Ｌ
Ｕ…Ｕ
Ｒ”。
第１６卷第１期邹又姣，冉占军，王晓峰：偏序关系哈斯图的一种求解方法５７
是反自反、反对称关系，所以（６，６），（６，口）∈Ｒ—Ｊ。，我们无需进行相关比较，而只需要判断是否有
参考文献
（６，ｃ），（６，ｄ＞，＜６，Ｐ＞ＥＲ——ｊ＾且Ⅱ可。
关系Ｒ中的元素越多，通过这种方法计算［１］左孝凌，李为缢，刘永才．离散数学［Ｍ］．上海：上海科学
ＣＯＶＡ的运算量的优点越明显。
技术文献出版社，２００４：１４０—１４１．
［２］方世昌．离散数学［Ｍ］．２版．西安：西安电子科技大学出
３
结束语
版社，２００６：１０７—１０８．
偏序关系是集合上的传递关系，它提供了一种
［３］徐洁磐．离散数学导论［Ｍ］．２版．北京：高等教育出版
社，２０００：４０—４１．
比较集合元素间次序的工具，其哈斯图简单形象地［４］丁树良，罗芬．求偏序关系Ｈａｓｓｅ图的算法［Ｊ］．江西师
描述了集合间元素的关系，然而对一个给定的偏序范大学学报：自然科学版．２００５，２９（２）：１５０—１５２．
关系，哈斯图的求解在离散数学教材中没有给出一［５］潘美芹，丁志军．一个快速求解哈斯图的算法［Ｊ］．山东
个简单易执行的方法。基于此，本人通过对偏序关系科技大学学报：自然科学版．２００３，２２（３）：８９—９０．
的理论分析，给出了一个求解偏序关系哈斯图的简［６］范懿．一个有关哈斯图的解析方法［Ｊ］．上海第二工业大
单方法，该方法运算量小，便于学生接受和掌握。
学学报．２００３（１）：１７—２２．
ＡＳｏｌｕｔｉｏｎｏｆＨａｓｓｅＤｉａｇｒａｍｗｉｔｈＰａｒｔｉａｌ－－ｏｒｄｅｒＲｅｌａｔｉｏｎ
ＺＯＵＹｏｕｊｉａｏ。
ＲＡＮＺｈａｎｊ
ｕｎ．
ＷＡＮＧ
Ｘｉａｏｆｅｎｇ
（ＭａｔｈｅｍａｔｉｃｓＤｅｐａｒｔｍｅｎｔ，Ｘｉ’ａｎＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ，Ｘｉ’ａｎ７１００４８，ＰＲＣ）
Ａｂｓｔｒａｃｔ：Ｔｈｅｃｏｎｃｅｐｔｓｏｆｔｈｅｂａｓｉｃｅｄｇｅａｎｄｔｈｅｇｅｎｅｒａｔｉｎｇｅｄｇｅ
ａｒｅ
ｉｎｔｒｏｄｕｃｅｄ．Ｗｉｔｈ
ｔｈｅ
ｃｈａｒａｃｔｅｒｉｓｔｉｃｓｏｆｔｈｅｐａｒｔｉａｌｏｒｄｅｒｒｅｌａｔｉｏｎ，ｔｈｅＨａｓｓｅｄｉａｇｒａｍｉｓａｎａｌｙｚｅｄｂｙｃｏｍｐｕｔｉｎｇｔｈｅｂａｓｉｃｅｄｇｅｓａｎｄｔｈｅｇｅｎｅｒａｔｉｎｇｅｄｇｅｓ．
Ｋｅｙｗｏｒｄｓ：ＨａｓｓｅＤｉａｇｒａｍ，ｐａｒｔｉａｌｏｒｄｅｒｉｎｇｒｅｌａｔｉｏｎ，ｂａｓｉｃｅｄｇｅ，ｇｅｎｅｒａｔｉｏｎｅｄｇｅ
（上接第５４页）
根据罗尔定理，存在ｅ∈（ｏ，１），使
Ｆ７（ｅ）一ｅ５［厂（手）一，（手）］一０，
参考文献
因为ｅ５≠０，故必有
Ｅｌｉ莫国良，唐志丰．微积分学：上册［Ｍ］．杭州：浙江大学
／’（ｅ）一厂（∈）。
出版社，２００９：６９．
上述例题的求解过程说明，“逆”用函数积求导［２］徐兵．高等数学证明题５００例解析［Ｍ］．北京：高等教育
法则，有时候可使证明简洁，因此值得思索与学习。
出版社，２００７：１４－１５．
ＲｅｖｅｒｓｉｎｇｔｈｅＰｒｏｄｕｃｔＲｕｌｅｆｏｒＤｅｒｉｖａｔｉｖｅｓ
ＷＵ
Ｌｉｎｃｏｎｇ，ＬＩＵＧｕｉｍｅｉ，
ＭＯ
Ｇｕｏｌｉａｎｇ
（ＺｈｅｊｉａｎｇＵｎｉｖｅｒｓｉｔｙＣｉｔｙＣｏｌｌｅｇｅ，Ｈａｎｇｚｈｏｕ３１００１５，ＰＲＣ）
Ａｂｓｔｒａｃｔ：
Ａｐｐｌｙｉｎｇｔｈｅｐｒｏｄｕｃｔｒｕｌｅｆｏｒｄｅｒｉｖａｔｉｖｅｓｒｅｖｅｒｓｅｌｙ，ｓｏｍｅｄｉｆｆｅｒｅｎｔｉａｌｅｑｕａｔｉｏｎｓ
ｏｒ
ｍｅａｎｖａｌｕｅｐｒｏｂｌｅｍｓｏｆｄｅｒｉｖａｔｉｖｅｓｃａｎ
ｂｅｓｏｌｖｅｄｅａｓｉｌｙ．Ｓｅｖｅｒａｌｓｕｃｈｅｘａｍｐｌｅｓ
ａｒｅ
ｐｒｅｓｅｎｔｅｄ
ｔｏ
ｉｌｌｕｓｔｒａｔｅｔｈｅｉｄｅａａｎｄｔｅｃｈｎｉｑｕｅ．
Ｋｅｙｗｏｒｄｓ：ｐｒｏｄｕｃｔｒｕｌｅｆｏｒｄｅｒｉｖａｔｉｖｅ，ｆｉｒｓｔｏｒｄｅｒｌｉｎｅａｒｄｉｆｆｅｒｅｎｔｉａｌ
ｅｑｕａｔｉｏｎ，ｄｉｆｆｅｒｅｎｔｉａｌ
ｍｅａｎｖａｌｕｅｐｒｏｂｌｅｍ
万方数据
偏序关系哈斯图的一种求解方法
作者：作者单位：刊名：英文刊名：年，卷(期)：
邹又姣， 冉占军， 王晓峰， ZOU Youjiao， RAN Zhanjun， WANG Xiaofeng西安理工大学应用数学系,陕西西安,710048高等数学研究
Studies in College Mathematics2013,16(1)
1. 左孝凌;李为鑑;刘永才 离散数学 20042. 方世昌 离散数学 20063. 徐洁磐 离散数学导论 2000
4. 丁树良;罗芬 求偏序关系Hasse图的算法[期刊论文]-江西师范大学学报(自然科学版) 2005(02)5. 潘美芹;丁志军 一个快速求解哈斯图的算法[期刊论文]-山东科技大学学报(自然科学版) 2003(03)6. 范懿 一个有关哈斯图的解析方法[期刊论文]-上海第二工业大学学报 2003(01)
引用本文格式：邹又姣. 冉占军. 王晓峰. ZOU Youjiao. RAN Zhanjun. WANG Xiaofeng 偏序关系哈斯图的一种求解方法[期刊论文]-高等数学研究 2013(1)
偏序关系哈斯图的一种求解方法
邹又姣，冉占军，王晓峰
（西安理工大学应用数学系，陕西西安７１００４８）
摘要
引入基本边和生成边的概念，并从偏序关系的特性人手，给出一种通过计算基本边和生成边来求解
偏序关系哈斯图的方法。
关键词
哈斯图；偏序关系；基本边；生战边
０１５８
中图分类号文献标识码
Ａ
文章编号１００８—１３９９（２０１３）０１—００５５—０３
在计算机科学中，关系的概念具有十分重要的意义。而偏序关系是关系中比较典型和重要的一种关系，它是集合上的传递关系，同时还提供了一种比较集合元素间次序的工具，其偏序关系的关系图
地描述了偏序集合中元素间的次序关系。
对给定的偏序集（Ａ，≤），它的盖住关系是唯一的，我们可以用盖住的定义求解哈斯图。
例１
给定集合Ａ一｛２，３，６，８），令
≤一｛＜ｚ，ｙ＞：ｏＺ＂整除Ｙ｝，
——哈斯图简单形象地描述了集合间元素的这种
次序关系。
离散数学教材中一般采用计算盖住关系的方法来求解一个偏序关系的哈斯图ｎ。］，这种方法在比较元素的次序时运算量大，容易出错，并且有时运用起来比较困难，学生普遍感觉比较棘手。有些学者对哈斯图进行了研究并给出了一些重要的求解方法［４，但这些方法学生不易掌握，运用困难。
本文通过研究偏序关系的性质，分析并证明了偏序关系的哈斯图运算转化为关系的复合运算，这一方法思路清晰，让学生在求解哈斯图时有法可依。
１
、
画出这个偏序关系的哈斯图。
解
由题意可得偏序关系
≤一｛（２，２），（３，３），（６，６），（８，８＞，
２，６＞，（２，８），＜３，６）｝，
所以
ＣＯＶＡ一｛（２，６＞，＜２，８），（３，６）），
其哈斯图如图１所示。
预备知识
定义１¨。２３
设Ａ是一个集合，如果Ａ上的一个
图１
二元关系尺满足自反性、反对称性和传递性，则称Ｒ是Ａ上的一个偏序关系，记作≤，序偶（Ａ，≤＞称为偏序集。
定义２¨１
例１哈斯图
如用“盖住”的定义来求解关系Ｒ的基本边，我们需要一一考虑（２，６），（２，８＞和（３，６）这三个序偶
在偏集中，如果ｚ，ｙ∈Ａ，ｚ≤ｙ，
是否是盖住关系里的元素，而在考虑每一个序偶比如（２，６＞时都要将２和６与集合Ａ中的元素２，３，６，８进行比较。对这个例子而言，比较的次数为
ＡＩ×２×ｔ一４×２×３—２４，
ｚ≠Ｙ且没有其他元素ｚ满足ｚ≤ｚ，ｚ≤ｙ，则称元素Ｙ盖住元素ｚ，并记
ＣＯＶＡ一｛（ｚ，了＞：ｚ，Ｙ∈Ａ；Ｙ盖住ｚ）。哈斯图是偏序关系的关系图的简化，它更清楚
收稿日期：２０１０—１１—２５；修改日期：２０１２—１２－２４
基金项目：西安理工大学精品课程建设项目（离散数学）
作者简介：邹又姣（１９７５一），女，湖北孝感人，博士研究生，讲师，从事
密码学研究．Ｅｍａｉｌ：ｙｊｚｏｕ２００９＠１２６．ｃｏｒｎ
冉占军（１９７７－－），男，河南郑州人，讲师，从事计算机软件及应用研究。Ｅｍａｉｌ：ｒａｎｚｈｊ＠１２６．ｃｏｒｎ
王晓峰（１９６６－－）．女，河南人，博士，教授．从事密码理论及
其中
ｔ—ＩＲ—ＪＡ１，
而ｋ为Ａ上的相等关系。当Ｉ
Ａ
Ｉ较大或者ｔ的值较
大时这个运算量就更大了，而且这种方法在比较元素的大小时很容易出错。
定义３Ｅ卜胡
设Ｒ是Ａ上的二元关系，如果有另
一个关系Ｒ７满足
（１）Ｒ７是可传递的．
应用研究。Ｅｍａｉｌ：ｘｆｗａｎ９６６＠ｓｉｎａ．ｃｏｍ．ｃａ
５６
高等数学研究
（２）Ｒ７三Ｒ．
然而Ｒ２∈Ｒ，从而
Ｒ３一Ｒ２。Ｒ
Ｒ４一Ｒ３。Ｒ
（３）对任何可传递关系彤，如果有彤三Ｒ，就
奄Ｒ］Ｒ；．
则称Ｒ７是Ｒ的传递闭包。
定理１Ⅲ
设Ｉ
Ａ
ＥＲ２，
Ｅ
Ｒ２。ＲＥＲ２，…
Ｒ”一［Ｒ２．
Ｉ一押，Ｒ是Ａ上的二元关系，
于是关系Ｒ的生成边为
Ｒ２
则Ｒ的传递闭包
ｔ（Ｒ）一ＲＵＲ２
Ｕ
Ｒ３
Ｕ…Ｕ
Ｒ“一Ｒ２．
ＵＲ３Ｕ…ＵＲ”．
结论１的基本边集合
设Ｒ是Ａ上的拟序关系，那么关系尺
定理２Ｅ２１设Ｒ是Ａ上的二元关系，那么Ｒ是
传递的当且仅当ｔ（Ｒ）一Ｒ．
２
ＣＯＶＡ—Ｒ—Ｒ２．
Ａ上的偏序关系Ｒ是Ａ上的自反、反对称、传递
偏序关系的哈斯图求解法
由于定义法求解关系Ｒ的哈斯图存在运算量
关系，我们如何利用结论１得到其基本边集合呢？
结论２的基本边集合
ＣＯＶＡ一（Ｒ一厶）一（Ｒ一厶）２．
设Ｒ是Ａ上的偏序关系，那么关系Ｒ
大、比较时容易出错的特点，在此，我们给出了一种便于计算的简单方法。这种方法在关系Ｒ中的元素较多时优点尤为明显。
２．１
证明
设Ｒ７一Ｒ一厶，若Ｒ７是Ａ上的拟序关
方法的提出和证明
为了清楚地表示出偏序关系的哈斯图中的边及
系，则由结论１即证。
显然关系Ｒ７是Ａ上的反自反关系。下证Ｒ７是Ａ
后续方法描述的方便起见，我们引入一个新的概念。
定义４
上的可传递关系。
设（口，６），＜６，ｆ＞∈Ｒ７，由Ｒ７反自反知ａ，ｂ，Ｃ互不相同，则（以，６＞，（ｂ，ｆ）∈Ｒ．而Ｒ是Ａ上的可传递关系，从而得到＜口，ｃ）∈Ｒ且ａ≠ｆ。故Ｒ７是Ａ上的可传递关系。
２．２
把ＣＯＶＡ中的元素称为基本边，把在
Ｒ中而不在ＣｏＶＡ中的边称为由基本边通过传递性生成的边，简称生成边。
由定理１和定理２得到，如果Ｒ是Ａ上的传递关
系，则
Ｒ２
应用举例及两种方法运算量的比较
例２
Ｕ．Ｒ３Ｕ…ＵＲ”∈Ｒ，
对Ａ一｛ａ，ｂ，ｆ，ｄ，ｅ）上的偏序关系
从而有
Ｒ１ＥＲ（ｉ一２，３，…，竹）．
Ｒ一｛（ａ，口＞，（ａ，６），（ａ，ｃ＞，＜口，ｄ），（ａ，８＞，
＜ｂ，６＞，（ｂ，ｆ），＜ｂ，ｅ），＜ｃ，ｆ＞，（ｂ，Ｐ＞，
．
若Ｒ是Ａ上的拟序关系，即Ｒ是反自反的、可传递的，现来分析这种关系的基本边。假设（ａ，６＞∈Ｒ，（６，ｆ）∈Ｒ，由Ｒ是Ａ上的反自反关系，有ａ≠ｂ，ｂ≠ｆ；又由Ｒ是Ａ上的传递关系，有（ａ，ｆ）∈Ｒ并且ｎ≠Ｃ。而｛（口，６＞｝。｛（６，ｃ）｝一｛＜口，ｆ）｝，从而得到：如果＜ｎ，６），（６，ｆ）是Ｒ的基本边，则由其通过传递关系生成的边（ａ，ｃ）必然在Ｒ２中，并且ａ≠ｃ。而且所有由两条基本边通过传递关系生成的边必然在Ｒ２中。
如果有三条基本边（口，６），（ｂ，ｃ＞，（ｆ，ｄ＞∈Ｒ，则由Ｒ是Ａ上的传递关系，有＜口，ｆ＞∈Ｒ且口，６，ｆ，ｄ互
不相同。而
｛（口，６））。｛（ｂ，ｆ））一｛＜ａ，ｆ＞）∈Ｒ２，．｛（口，ｆ）｝。｛（ｆ，ｄ））一｛（ｎ，ｄ＞｝∈Ｒ３，
（ｄ，ｄ＞，（ｄ，Ｐ＞，（ｅ，Ｐ＞），
画出其哈斯图。
解
因为
Ｒ一厶一｛（ａ，６），＜ａ，ｆ），（ａ，ｄ＞，（ａ，Ｐ＞，
（ｂ，ｆ），＜ｂ，Ｐ＞，（Ｃ，ｅ），（ｄ，ｅ）｝，（Ｒ—ｊＡ）２一｛（ａ，ｆ＞，（口，ｅ），（ｂ，Ｐ）），
所以
ＣＫ）、厂４一｛＜口，６），（口，ｄ＞，（６，ｆ），（ｃ，已），（ｄ，ｅ＞），
其哈斯图如图２所示。
即由三条基本边通过传递性生成的边必然在Ｒ３中。
由ｉ条基本边通过传递关系生成的边必然在Ｒ。中，从而关系Ｒ的生成边为Ｒ其基本边
ＣＯＶＡ—Ｒ—Ｒ２ＵＲ３
２
图２例２哈斯图
ＵＲ３Ｕ…ＵＲ”，故对于例２而言，用定义法求解ＣＯＶＡ需要比较８０次，而如果用本文中提出的方法，仅需要比较运算２４次数。比如Ｒ一，。中的序偶（口，６＞，因为Ｒ—Ｌ
Ｕ…Ｕ
Ｒ”。
第１６卷第１期邹又姣，冉占军，王晓峰：偏序关系哈斯图的一种求解方法５７
是反自反、反对称关系，所以（６，６），（６，口）∈Ｒ—Ｊ。，我们无需进行相关比较，而只需要判断是否有
参考文献
（６，ｃ），（６，ｄ＞，＜６，Ｐ＞ＥＲ——ｊ＾且Ⅱ可。
关系Ｒ中的元素越多，通过这种方法计算［１］左孝凌，李为缢，刘永才．离散数学［Ｍ］．上海：上海科学
ＣＯＶＡ的运算量的优点越明显。
技术文献出版社，２００４：１４０—１４１．
［２］方世昌．离散数学［Ｍ］．２版．西安：西安电子科技大学出
３
结束语
版社，２００６：１０７—１０８．
偏序关系是集合上的传递关系，它提供了一种
［３］徐洁磐．离散数学导论［Ｍ］．２版．北京：高等教育出版
社，２０００：４０—４１．
比较集合元素间次序的工具，其哈斯图简单形象地［４］丁树良，罗芬．求偏序关系Ｈａｓｓｅ图的算法［Ｊ］．江西师
描述了集合间元素的关系，然而对一个给定的偏序范大学学报：自然科学版．２００５，２９（２）：１５０—１５２．
关系，哈斯图的求解在离散数学教材中没有给出一［５］潘美芹，丁志军．一个快速求解哈斯图的算法［Ｊ］．山东
个简单易执行的方法。基于此，本人通过对偏序关系科技大学学报：自然科学版．２００３，２２（３）：８９—９０．
的理论分析，给出了一个求解偏序关系哈斯图的简［６］范懿．一个有关哈斯图的解析方法［Ｊ］．上海第二工业大
单方法，该方法运算量小，便于学生接受和掌握。
学学报．２００３（１）：１７—２２．
ＡＳｏｌｕｔｉｏｎｏｆＨａｓｓｅＤｉａｇｒａｍｗｉｔｈＰａｒｔｉａｌ－－ｏｒｄｅｒＲｅｌａｔｉｏｎ
ＺＯＵＹｏｕｊｉａｏ。
ＲＡＮＺｈａｎｊ
ｕｎ．
ＷＡＮＧ
Ｘｉａｏｆｅｎｇ
（ＭａｔｈｅｍａｔｉｃｓＤｅｐａｒｔｍｅｎｔ，Ｘｉ’ａｎＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ，Ｘｉ’ａｎ７１００４８，ＰＲＣ）
Ａｂｓｔｒａｃｔ：Ｔｈｅｃｏｎｃｅｐｔｓｏｆｔｈｅｂａｓｉｃｅｄｇｅａｎｄｔｈｅｇｅｎｅｒａｔｉｎｇｅｄｇｅ
ａｒｅ
ｉｎｔｒｏｄｕｃｅｄ．Ｗｉｔｈ
ｔｈｅ
ｃｈａｒａｃｔｅｒｉｓｔｉｃｓｏｆｔｈｅｐａｒｔｉａｌｏｒｄｅｒｒｅｌａｔｉｏｎ，ｔｈｅＨａｓｓｅｄｉａｇｒａｍｉｓａｎａｌｙｚｅｄｂｙｃｏｍｐｕｔｉｎｇｔｈｅｂａｓｉｃｅｄｇｅｓａｎｄｔｈｅｇｅｎｅｒａｔｉｎｇｅｄｇｅｓ．
Ｋｅｙｗｏｒｄｓ：ＨａｓｓｅＤｉａｇｒａｍ，ｐａｒｔｉａｌｏｒｄｅｒｉｎｇｒｅｌａｔｉｏｎ，ｂａｓｉｃｅｄｇｅ，ｇｅｎｅｒａｔｉｏｎｅｄｇｅ
（上接第５４页）
根据罗尔定理，存在ｅ∈（ｏ，１），使
Ｆ７（ｅ）一ｅ５［厂（手）一，（手）］一０，
参考文献
因为ｅ５≠０，故必有
Ｅｌｉ莫国良，唐志丰．微积分学：上册［Ｍ］．杭州：浙江大学
／’（ｅ）一厂（∈）。
出版社，２００９：６９．
上述例题的求解过程说明，“逆”用函数积求导［２］徐兵．高等数学证明题５００例解析［Ｍ］．北京：高等教育
法则，有时候可使证明简洁，因此值得思索与学习。
出版社，２００７：１４－１５．
ＲｅｖｅｒｓｉｎｇｔｈｅＰｒｏｄｕｃｔＲｕｌｅｆｏｒＤｅｒｉｖａｔｉｖｅｓ
ＷＵ
Ｌｉｎｃｏｎｇ，ＬＩＵＧｕｉｍｅｉ，
ＭＯ
Ｇｕｏｌｉａｎｇ
（ＺｈｅｊｉａｎｇＵｎｉｖｅｒｓｉｔｙＣｉｔｙＣｏｌｌｅｇｅ，Ｈａｎｇｚｈｏｕ３１００１５，ＰＲＣ）
Ａｂｓｔｒａｃｔ：
Ａｐｐｌｙｉｎｇｔｈｅｐｒｏｄｕｃｔｒｕｌｅｆｏｒｄｅｒｉｖａｔｉｖｅｓｒｅｖｅｒｓｅｌｙ，ｓｏｍｅｄｉｆｆｅｒｅｎｔｉａｌｅｑｕａｔｉｏｎｓ
ｏｒ
ｍｅａｎｖａｌｕｅｐｒｏｂｌｅｍｓｏｆｄｅｒｉｖａｔｉｖｅｓｃａｎ
ｂｅｓｏｌｖｅｄｅａｓｉｌｙ．Ｓｅｖｅｒａｌｓｕｃｈｅｘａｍｐｌｅｓ
ａｒｅ
ｐｒｅｓｅｎｔｅｄ
ｔｏ
ｉｌｌｕｓｔｒａｔｅｔｈｅｉｄｅａａｎｄｔｅｃｈｎｉｑｕｅ．
Ｋｅｙｗｏｒｄｓ：ｐｒｏｄｕｃｔｒｕｌｅｆｏｒｄｅｒｉｖａｔｉｖｅ，ｆｉｒｓｔｏｒｄｅｒｌｉｎｅａｒｄｉｆｆｅｒｅｎｔｉａｌ
ｅｑｕａｔｉｏｎ，ｄｉｆｆｅｒｅｎｔｉａｌ
ｍｅａｎｖａｌｕｅｐｒｏｂｌｅｍ
万方数据
偏序关系哈斯图的一种求解方法
作者：作者单位：刊名：英文刊名：年，卷(期)：
邹又姣， 冉占军， 王晓峰， ZOU Youjiao， RAN Zhanjun， WANG Xiaofeng西安理工大学应用数学系,陕西西安,710048高等数学研究
Studies in College Mathematics2013,16(1)
1. 左孝凌;李为鑑;刘永才 离散数学 20042. 方世昌 离散数学 20063. 徐洁磐 离散数学导论 2000
4. 丁树良;罗芬 求偏序关系Hasse图的算法[期刊论文]-江西师范大学学报(自然科学版) 2005(02)5. 潘美芹;丁志军 一个快速求解哈斯图的算法[期刊论文]-山东科技大学学报(自然科学版) 2003(03)6. 范懿 一个有关哈斯图的解析方法[期刊论文]-上海第二工业大学学报 2003(01)
引用本文格式：邹又姣. 冉占军. 王晓峰. ZOU Youjiao. RAN Zhanjun. WANG Xiaofeng 偏序关系哈斯图的一种求解方法[期刊论文]-高等数学研究 2013(1)