东南大学：《离散数学》课程教学资源（PPT课件讲稿）第六章 代数系统（格和布尔代数）

代数系统 第六章格和布尔代数 §1格的概念 §2分配格 §3有补格 §4*布尔代数

1 代数系统 第六章 格和布尔代数 §1格的概念 §2分配格 §3有补格 §4 *布尔代数

s1格的概念 1偏序集合格 《定义》格是一个偏序集合,其中每一对元素 a.b∈L都拥有一个最小上界和最大下界。通常用 a入b表示a和b的最大下界,用avb表示a和b的最小 上界。即GLB{a,b}=ab —称为元素a和b的保交运算, LUBa, b=avb —称为元素a和b的保联运算

2 §1格的概念 1.偏序集合格 《定义》格是一个偏序集合 ，其中每一对元素 都拥有一个最小上界和最大下界。通常用 表示a和b的最大下界，用 表示a和b的最小 上界。即： ——称为元素a和b的保交运算， ——称为元素a和b的保联运算。  L, a,b  L ab ab GLB{a,b} = a b LUB{a,b} = a  b

s1格的概念 例:以下均为偏序集合格(D为整除关系,Sn为n的因 子集合)

3 §1格的概念 例：以下均为偏序集合格（D为整除关系，Sn为n的因 子集合）

s1格的概念 2代数系统格 《定义》:设是一个格,如果在A上定义两个 二元运算v和∧,使得对于任意的a,b∈A,a∨b等 于a和b的最小上界,a∧b等于a和b的最大下界,那 么就称为由格L>所诱导的代数系统

4 §1格的概念 2.代数系统格 《定义》：设 是一个格，如果在A上定义两个 二元运算和，使得对于任意的a，bA，ab等 于a和b的最小上界，ab等于a和b的最大下界，那 么就称 为由格 所诱导的代数系统。  L,  L,

s1格的概念 格的主要性质: (1)格的对偶原理 设是格,“≤”的逆关系“≥”与L组成的偏序集 也是格。两者互为对偶。前者的GLB,LUB恰好 是后者的LUB,GLB。如有关于的有效命题, 将“≤”换成“≥”,“八”换成“v”,“V”换成 ∧”,便能得到的有效命题。反之亦然

5 §1格的概念 3.格的主要性质： (1)格的对偶原理 设是格，“≤”的逆关系“≥”与L组成的偏序集 也是格。两者互为对偶。前者的GLB，LUB恰好 是后者的LUB，GLB。如有关于的有效命题， 将“≤”换成“≥”，“”换成“”， “”换成 “”，便能得到的有效命题。反之亦然

s1格的概念 (2)对格中任意a和b,有aavb及absa (3)是格。对任意a,b,cd∈L,如asb,c≤d,则 avc≤bvd,a∧c≤b/d

6 §1格的概念 (2)对格中任意a和b，有a≤ab及ab≤a。 (3) 是格。对任意a,b,c,dL，如a≤b， c≤d，则 ac≤ bd， ac≤bd

7

7

s1格的概念 (4)(交换律)交和并运算是可交换的 (5)(结合律)交和并运算是可结合的

8 §1格的概念 (4)（交换律）交和并运算是可交换的。 (5)（结合律）交和并运算是可结合的

s1格的概念 (6)(幂等律)对L中每一个a,有aVa=a,a∧a=a。 (7)(吸收律)对L中任意a,b, 有av(ab)=aa∧(ab)=a

9 §1格的概念 (6)（幂等律）对L中每一个a，有aa=a，aa=a。 (7)（吸收律）对L中任意a，b， 有a(ab)=a a(ab)=a

§2分配格 对格所定义的代数系统,其运算∧和∨不一定满 足分配律 《定义》设是由所诱导的代数系统。如果 对任意的a,b,c∈L,满足: a∧(bvc=(a∧b)v(a∧c) 及av(b∧c)=(avb)∧(avc) 则称是分配格 10

10 §2分配格 对格所定义的代数系统，其运算和不一定满 足分配律。 《定义》设是由所诱导的代数系统。如果 对任意的a,b,cL，满足： a (b  c)=(a  b) (a  c) 及 a  (b  c)=(a  b)  (a  c) 则称是分配格