西北工业大学《离散数学（第6版）》课件-第7章格与布尔代数.pdfVIP

第七章 格与布尔代数 1 2008-2018 by Li Weigang. All rights reserved. 主要内容 格的定义及性质 子格  分配格、有界格、有补格 布尔代数 2 7.1 格的定义与性质 7.1 L , + L , 定义 设 是非空集合 和 是 上的两个二元运算 如果它 , , a,b,c L 们满足交换律 结合律和吸收率 即 ∈ 有 (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 b) = a, a (a+b) = a 则称代数系统 是格 也称代数格 L,+ , , . 例如, 非空集合 的幂集 构成的代数系统 ∪ 是格 (1) A P(A) P(A), ∩, . (2) Z+ : 正整数集 与其上定义的两个运算 gcd(a, b) 两个正整数的最大公因数 lcm(a, b) 两个正整数的最小公倍数 + 构成代数系统Z , gcd, lcm是格. 3 格的性质 1 . 格的性质 格满足幂等律 7.1 L,+ , , a L a+a a, a a a . 定理 设 是格 则 ∈ 有 证 由吸收律易证a+a a+(a (a+a)) a, a a a (a+ (a a)) a . 格的性质 格的子代数必为格 2 . 定理 设 是格 是它的子代数其中 7.2 L,+ , , H,+ , (  H L), 则 必为格 称为 的子格 H,+ , , L,+ , . a,b,c H, a,b,c L, L , a,b,c , 证 设 ∈ 则 ∈ 是格 则 满足交换律 结合律 , H