格和布尔代数复习.ppt

离散数学 第七章 格和布尔代数 定理7-1.3 设A,?是一个格，由格A,?所诱导的代数系统为A,?,?，则对任意a,b,c,d?A，有 (1) a ? b=b ? a a ? b=b ? a (交换律) (2) a ? (b ? c)=(a ? b) ? c a ? (b ? c)=(a ? b) ? c (结合律) (3) a ? a = a a ? a = a (幂等律) (4) a ? (a ? b)=a a ? (a ? b)=a (吸收律) 分 配 格 分 配 格 有 补 格 布尔代数 * * 定义7-1.1 设A,?是一个偏序集(自反、反对称、传递),如果A中任意两个元素都有最小上界(上确界)和最大下界(下确界) ,则称A,?为格. 例: 设偏序集{1,2,3,4,6,9,12,18,36},|， 判断是否为格？ 1 3 9 2 4 12 18 6 36 格的概念 格 不是格 定义7-1.2 设A, ?是一个格，如果在A上定义两个二元运算∨和∧,使得对于任意的a,b?A，a∨b等于a和b的最小上界，a∧b等于a和b的最大下界，那么，就称A,∨,∧是由格A, ?所诱导的代数系统。二元运算∨和∧分别称为并运算和交运算。 例 给定S={a,b}，P(S)={?,{a},{b},{a,b}}，那么，格P(S),?如下图所示。 ? {a} {b} {a,b} {a} {a} {a,b} {a,b} {b} {a,b} {b} {a,b} {a,b} {a,b} {a,b} {a,b} ? {a} {b} {a,b} ? {a} {b} {a,b} ∨ {a,b} {b} {a} {?} ? ? ? ? ? {a} ? {a} ? ? {b} {b} ? {a} {b} {a,b} ? {a} {b} {a,b} ? {a} {b} {a,b} ∧ 而由格P(S),?所诱导的代数系统为P(S),∨,∧，其中运算∨是集合的并，运算∧是集合的交。故∨和∧的运算表可分别由如下的两个表所示。 定义7-1.3 设A, ?是一个格，由A, ?诱导的代数系统为P(S),∨,∧，设B?A且B≠?,如果A中的这两个运算∨和∧关于B是封闭的，则称B, ?是A, ?的子格。 注意：对于格A,?,设B是A的非空子集，尽管B,?必定是一个偏序集，然而B,?不一定是格，而且即使B,?是格，也不一定是A,?的子格。 例 设S,?是一个格，其中S={a,b,c,d,e,f,g,h}, 如图所示。取 S1={a,b,d,f} S2={c,e,g,h} S3={a,b,c,d,e,g,h} a b c d e f g h 从图中容易看出，S1,?和S2,?都是S,?的子格，而S3,?虽然是格，但它不是S,?的子格，这是因为b∧d=f?S3 a b c d e g h 格的对偶原理 集合S的偏序关系≤的逆关系≥也是偏序关系，所以如果S,≤是格，则S,≥也是格，称这两个格互为对偶。 因为S,≤的交是S,≥的并，S,≤的并是S,≥的交，所以关于格的一般性质的任意命题，如用≥替换≤，用?替换?，用?替换?，格的一般性质的任意命题仍成立，这称为格的对偶原理。 格的性质 定理7-1.1 设A,?是一个格，对任意a,b∈A，有 a? a ? b b? a ? b a ? b ?a a ? b ? b 定理7-1.2 设A,?是一个格，对任意a,b,c,d∈A，如果a ? b 和c ? d，则: a ? c ? b ? d a ? c ? b ? d 推论 设A,?是一个格，