[数据结构与算法]离散数学考点之有界格

如题：2021年10月

分析

学会从集合到关系，函数到代数，最后到图，这种抽象过程。没总结完，时间有些紧，还有差不多一月就要考试了，离散与结构还有太多没看完的部分了，所以其他记录在了自己的纸质的资料上了，不再写在这里了。
答案为D,全上界与全下界互为补元，所以至少存在两个元素有补元

基本知识

什么是格？

具有最小上界和最大下界，具有这种性质的偏序集，称为格。
关于最大下界和最小上界，一定要想像出这个图来：{a,b}的最小上界是c,{e,f}的最大下界是d

关于偏序集

自反性+反对称性（也就是要么处于对角线要么就关于对角线没有对应的点）+传递性（可理解成线性递增）就是偏序的关系，这样的关系构成的集合就是偏序集。

格的表示

<A,$\le$?>是一个偏序集，如果A中的任意两个元素都有最小上界和最大下界，则称<A,$\le$?>为格。
其实是一个有序对的表示方法。具体含义为：A表示集合，$\le$?表示集合元素的关系。这不正是面向对象语言中类的定义吗？

格所诱导的代数系统

<A,$?$,$?$>,也是有序对，并运算对应的是任意两元素的最小上界，交运算对应的是最大下界。如脑补出下图：注意，图是由代数定义表示出来的，而不是图推导出了定义。

子格

如果B是A的非空子集，如果A中的并和交运算关于B封闭，则称<B,$\le$?>是A的子格。
若仅满足B是A的非空子集，则<B,$\le$?>一定是偏序集，并不一定是格，即使是格也不一定是A的子格。

对偶原理

设P是对任意格都为真的命题，如果在命题中把$\le$?换成$\ge$,$?$换成$?$，$?$换成$?$就得到另一个命题，称为对偶命题。

格的基本性质

1. 对任意a,b,都小于a并b（最小上界）,同时，都大于最大下界a交b
2. 传递性，a$\le$?b,c$\le$?d,则a并b$\le$?b并d,交也存在一样的运算
3. 诱导代数系统满足交换律、结合律、幂等律、吸收律