离散数学：格与布尔代数

Abstract：逻辑代数实质是符号逻辑，布尔代数即逻辑代数，核心是类的演算。偏序关系是格的先修知识。当偏序集里的所有子集都有最大下界和最小上界时，称为格。其中有补分配格称为布尔代数（有补，分配，有界）。

布尔代数初导

逻辑代数实质是符号逻辑，德摩根与布尔算是逻辑代数的创始人，布尔代数即逻辑代数。

德摩根定律：

德摩根定律：一个组(aggregate)的反面(contrary)是各个组的反面的复合(compound)；一个复合的反面是各成分的反面的组合。

$$1-(x+y)=(1-x)(1-y)$$ $$1-xy=(1-x)+(1-y)$$

布尔代数

外延逻辑extensional logic：类(class)的逻辑

• 用小写字母表示类或集合，用大写字母表述个体元素
• 1:万有类，0：空类或零类
• xy：x，y中共有元素的集合；x + y：所有元素的集合；1 - x：x的补集；x - y：由不是y的x组成的类；xy = x：x包含在y中(x的外延小于y)；等号：表示两个类的同一性

矛盾律：$x（1+x）= 0$，即A不能既是A又是B

$$xy=yx$$ $$xx=x$$ $$x+y=y+x$$ $$x(u+v)=xu+xv$$

排中律：$x+(1-x)=1$，即任何东西不是A就是非A

$$1x=x$$ $$0x=0$$

布尔：延伸—命题逻辑

类的演算可以解释为命题的演算:

若x与y不是类而是命题，则xy是x与y的同时肯定；而x+y是x或y或两者的肯定；x=1表示命题x为真，x=0表示命题x为假，1-x表示x的否定。

格与布尔代数

偏序关系（偏序是格的先修知识）

偏序：设R为非空集合A上的关系，若R是自反的，反对称的，可传递的，则称R为A上的偏序关系，简称偏序。记作$≤$。如{1,2,4,8}是偏序关系。

常见的偏序关系：

• 整数集合R上的小于等于、大于等于关系
• 幂集（所有子集）中的包含关系
• 正整数的整除和整倍数关系

注：一个偏序的逆关系也是偏序。

偏序集：，即集合A与A上的偏序关系

覆盖：是一个偏序集，如果对任何x, y ∈ A, 有x≤y且x≠y, 不存在其他的元素z∈A, 能够让x≤z且z小于等于y即$x\leq y\wedge x\ne y\wedge \left( x\leq z\leq y\Rightarrow x=z\vee z=y \right)$成立，则称元素y覆盖x。

如：{1，2，4，8}中，8覆盖4，但8不能覆盖2（因为存在4∈A, 使x∈4且4≤8）

哈斯图：表示偏序关系的图。以小圈表示元素，如果有x, y∈A, x≤y且x≠y, 则把x的小圈画在y的小圈下面。而且如果y能够覆盖x的话，便在中间连上一条线（这条线的方向默认是从下往上的，所以不需要标注方向）。如：

偏序的重要概念

偏序与格的概念联系非常紧密

1.设是一个偏序集合，且有Q⊆，y∈Q。

最小元： 对任意x（x∈Q）有y≤x，则y为Q的最小元，通常记作0

最大元： 对任意x（x∈Q）有x≤y，则y为Q的最大元，通常记作1

极小元： 对任意x（x∈Q）且x≤y，有x=y成立，则y为Q的极小元

极大元： 对任意x（x∈Q）且y≤x，有x=y成立，则y为Q的极大元

2.设是一个偏序集合，并有Q⊆P，y∈P

上界：对任意x（x∈Q）有x≤y，则y为Q的上界，不一定唯一，注意y只是集合中的一个元素

下界：对任意x（x∈Q）有y≤x，则y为Q的下界，不一定唯一，注意y只是集合中的一个元素

最小上界：因为上界不一定唯一，那么Q中所有的上界中最小元即为最小上界

最大下界：因为下界不一定唯一，那么Q中所有的下界中最大元即为最大下界

注意：若某子集有N个“貌似最大下界”，且它们不在一条偏序路径上，则它们不具有可比性，因此没有最大下界。

如上图，A = {2,3}无最大下界！最小上界是6.

格与布尔代数的概念

1.格的第一种概念：（用偏序理解）

设是一个偏序集，对P中任意元素x和y，{x，y}组成的集合都有最大下界和最小上界，则称为格。

即，所有子集都有最大下界和最小上界。
attention:判断格里的子集都是二元的，{x，y}， 不能是{x, y, z}.
判断是否为格：当发现找不到两个元素, 使他们没有最大上界和最小上界, 则为格.

反例：下图中{b,c}无最大下界，因为d，e不具有可比性。

格的二元运算符号：

• x∧y: x与y最大下界（向上开口就是最大嘛）
• x∨y: x与y最小上界（向下开口就是最小嘛）

格的二元运算满足的运算定律：

• 交换律，结合律，等幂律，吸收率，无分配律
• 如果对该格有 a∧(b∨c) = (a∧c)∨(a∧b), 即满足分配律的话, 就是分配格。

2.格的第二种概念：（用代数系统理解）

概念：对具有两个二元计算的代数系统，如果和+满足交换律，结合律，吸收率（但是不一定要对+满足分配率），那么这个代数系统构成一个格。

子格： 设构成格, L是S的非空子集, 如果L关于格中的运算∨和∧仍然能够构成格, 那么L就是S的子格。
完全格：格的每个非空子集均有上下确界，则成为完全格。

有界格：若格有最小元0和最小元1(不记得了的话往上翻), 则成为有界格, 记作, 完全格必然有最小元和最大元。

补元：有界格中, 对任意元素a∈L, 若存在b∈L, 并且a∧b = 0, a∨b = 1, 则称b是a的补元，补元不一定唯一。

有补格：有界格中，每一个元素都有补元，则称为有补格。

布尔代数：

• 定义1：如果一个格是有补分配格，那么称为布尔代数。
• 定义2：设是含有两个二元运算的代数系统, +和满足交换律, 分配率, 同一律, 补元律, 那么就是一个布尔代数。同一律即a 1 = a , b + 0 = b。 补元律即a * a’ = 0, b + b’ = 1。

布尔代数——有补分配格：满足以下3个条件的格

• 满足分配律
• 有最小元和最大元
• 每个元素都有补元

Reference

格与布尔代数