格与布尔代数第5章格与布尔代数5万字-.doc

应用离散数学格与布尔代数

杭电－方景龙第五章PAGE37

第5章：格与布尔代数

格与布尔代数是代数系统中的又一类重要代数系统。这两个代数系统与第4章讨论的代数系统之间存在着一个重要的区别：在格与布尔代数中，偏序关系具有重要的意义。为了强调偏序关系的作用，我们将分别从偏序关系和代数系统两个方面引入格的概念。

给格附加一定的限制后，格就转化为布尔代数，即布尔代数是一种特别的格。

布尔代数最初是作为对逻辑思维法则的研究而出现的，创立者是英国哲学家和数学家布尔〔G.Boole〕。自布尔之后，许多数学家对布尔代数的一般化作了许多努力，特别是斯通〔M.H.Stone〕，他的工作可以说是对现代布尔代数的发展开创了一个新阶段。

1938年，香农〔C.E.Shannon〕发表了《继电器和开关电路的符号分析》一文，为布尔代数在工艺技术中的应用开创了道路，从而出现了开关代数。为了给开关代数奠定基础，于是自然形成了二值布尔代数，即逻辑代数。自香农之后，人们应用布尔代数对电路作了大量研究，并形成了网络理论。

格与布尔代数不仅是代数学的一个分支，而且在近代解析几何、半序空间等方面也都有重要的作用，同时，格与布尔代数在计算机科学中也有十分重要的作用，可直接用于开关理论和逻辑制定、密码学、计算机理论科学等。

§5.1偏序关系与偏序集

1.基本概念

我们常用关系对集合的某些元素或全体元素进行排序。例如，使用包涵着字对的关系对字排序，其中按照字典顺序排在的前面。使用包涵着任务对的关系安排任务，其中任务必需在任务之前完成。使用包涵着整数对的关系安排整数，其中小于。当我们再把所有形如的序偶加到这些关系中时就得到一个自反的、反对称的和传递的关系，即偏序关系。

设是集合上的关系，如果是自反的、反对称的和传递的，则称是上的偏序关系。偏序关系通常用符号表示，通常记为并读着“先于〞。带有偏序关系的集合叫做偏序集，当我们需要指明时，记作。

意为且，读着“严格先于〞。也是集合上的关系，并且是反自反的、反对称的和传递的，叫做上的半序。显然，如果是偏序，则为半序，反之，如果是半序，则为偏序。

意为，读着“后于〞。也是集合上的偏序关系，叫做的对偶序，相应的偏序集称为的对偶集。显然对偶序是关系的逆，即。

〔1〕设是实数集合，为小于或等于关系，则是上的偏序关系，是偏序集。

〔2〕设是正整数集合，整除记作“〞，例如，，等等，则这种整除关系“〞是上的偏序关系，是偏序集。

〔3〕整除关系“〞不是整数集合上的偏序关系。特别地，“〞在上不是反对称的，例如有和，但。〔注意：说整除是指存在整数，使得〕

〔4〕在整数集合上，定义关系：当且仅当存在正整数使得，例如因为所以。则是上的偏序关系，是偏序集。

〔5〕设是集合的幂集，是集合的包涵于关系，则是幂集上的偏序关系，是偏序集。 ■

为了更直观地研究偏序关系和偏序集，可借助于哈斯〔Hass〕图。哈斯图的画法可描述为：设是偏序集，中的每个元素用节点表示，假设，且，则节点画于节点的下面；假设且与之间不存在另一个使得和，则与之间用一线段连接。

显然，哈斯图是关系图的一种简化，它是依据偏序关系的自反和传递特点去掉了关系图中所有环和某些线段后的简化图。

〔1〕集合在整除关系下构成偏序集，它的哈斯图如图5.1〔a〕所示。

〔2〕集合的幂集在集合的包涵于关系下构成偏序集，它的哈斯图如图5.1〔b〕所示。

12

12

12

36

3

2

6

(a)

φ

{a,b}

{a,b,c}

{a,c}

{b,c}

{a}

{c}

{b}

(b)

偏序集的哈斯图 ■

假设和是偏序集上的两个元素。如果

或。

我们就说和是可比较的。否则我们就说和是不可比较的，并记作。

“偏〞是用来定义偏序集的，因为集合上某些元素是不可比较的。假设的每一对元素都是可比较的，则称为全序集，相应的偏序就称为全序。全序集也叫做线性序集或叫做链。虽然偏序集可能不是全序集，但它的子集仍有可能是全序集。很显然，全序集的每一个子集都是全序集。

〔1〕偏序集是全序集，的每个子集在偏序关系下也都是全序集。

〔2〕合计偏序集。21和7可比较，因为；但3和5不可比较，因为既没有也没有。因此不是全序集，但是在整除关系下的全序子集。

〔3〕关于含有两个或两个以上元素的集合，偏序集不是全序集。例如，假设和属于，那么中的与是不可比较的。而是在偏序关系下的全序子集。 ■

2.偏序集中的特别元素

设是偏序集，是的子集。中的一个元素叫做的极小元，如果中没有其它元素严格先于。类似地，中的一个元素叫做的极大元，如果中没有其它元素严格后于。

极小