第8讲 布尔代数 Boolean Algebra.

Presentation on theme: "第8讲 布尔代数 Boolean Algebra."— Presentation transcript:

1 第8讲 布尔代数 Boolean Algebra

2 布尔演算（布尔代数）——数理逻辑 Huntington公理布尔代数 格代数布尔代数

3 主要内容 8.1 格 8.2 格是一种代数结构 8.3 布尔代数

4 1 格？ 请回忆：偏序结构 偏序集、哈斯图 上界、最小上界 下界、最大下界 最大下界、最小上界若存在，则唯一？

5 1 格？ 示例 1 lub(a,b)=Ф glb(a,b)=e lub(a,e)=a glb(a,e)=e
lub(c,d)=f glb(c,d)=Ф

6 1 格？ 格(Lattice) 设〈L，≤〉是偏序集合，若a，bL，都有最大下界、最小上界;
则称〈L，≤〉是个格，且记glb(a,b)=ab, lub(a,b)=ab,并称它们为交和并。 注1: 由于最大下界、最小上界若存在则唯一，所以交、并是二元运算? 注2: 称<L, ,>为由格〈L，≤〉所诱导的代数系统。

7 1 格？ 示例 2

8 1 格？ 示例 3 设n是一正整数，Sn是n的所有因子的集合，D是整除关系,则<Sn,D>是格。 8 8 24 4 2 1 12 6 3 4 2 1 n=24 n=8

9 1 格？ 示例 4 设S是任意集合，(S)是幂集，偏序集合<S, >是格，其中A,B(S),AB=A∩B, AB=A∪B. S={a,b} S={1,2,3} {1,2,3} {2,3} {3} {1,3} {2} {1,2} {a,b} {a} {b} {1}

10 1 格？ 格的对偶原理 1) 集合S的偏序关系≤的逆关系≥也是偏序关系，若AS,其中≤的glb(A)对应于≥的lub(A),≤的lub(A)对应于≥的glb(A),所以，若<S,≤>是格，则<S, ≥>也是格，称这两个格互为对偶。

11 1 格？ 2) 因为<S,≤>的交是<S,≥>的并， <S,≤>的并是<S,≥> 的交，所以，关于格的一般性质的任意命题，如用≥替换≤，用替换，用替换，格的一般性质的任意命题仍成立，这称为格的对偶原理。

12 1 格？ 格的基本性质 1)自反性 a≤a 对偶: a≥a 2)反对称性 a≤b 且 a≥b  a=b
3)传递性 a≤b 且 b≤c  a≤c 对偶:a≥b 且 b≥c  a≥c

13 1 格？ 格的基本性质 4) 最大下界描述之一 ab≤a 对偶 ab≥a ab≤b 对偶 ab≥b 5）最大下界描述之二
c≤a,c≤b  c≤ab 对偶 c≥a,c≥b  c≥ab

14 1 格？ 格的基本性质 注: 格的证明思路：总是利 用反对称性。 6) 结合律
a(bc)=(ab)c 对偶 a(bc)=(ab)c 证： 令R=a(b c), R’=(ab)  c 则由4 R≤a, R≤bc  R≤a, R≤b, R≤c  R≤a b, R≤ c  R≤(ab) c  R≤R’ 同理可证：R≥R’ 所以 R=R’ 注: 格的证明思路：总是利 用反对称性。

15 1 格？ 格的基本性质 7)等幂律 aa=a 对偶 aa=a 8)吸收律 a(ab)=a 对偶 a(ab)=a

16 1 格？ 格的基本性质 9) a≤b  ab=a ab=b 证： a≤b a≤a, a≤b a≤ab 又 a≥ab

17 1 格？ 格的基本性质 证：ab≤a, a≤c  ab≤c ab≤b, b≤d  ab≤d  ab≤cd
10) a≤c,b≤d  ab≤cd ab≤cd 证：ab≤a, a≤c  ab≤c ab≤b, b≤d  ab≤d  ab≤cd

18 1 格？ 格的基本性质 11）保序性 b≤c  ab≤ac ab≤ac 证： 因为a≤a, b≤c
得证。

19 1 格？ 格的基本性质 a(bc)≤(ab)(ac) 对偶 a(bc)≥(ab)(ac) 证: a≤ab, a≤ac
12） 分配不等式 a(bc)≤(ab)(ac) 对偶 a(bc)≥(ab)(ac) 证: a≤ab, a≤ac  a≤(ab)(ac) b≤ab, c≤ac  bc≤(ab)(ac)（性质10）  a(bc)≤(ab)(ac)

20 2 格是代数结构 可将代数结构的有关概念应用于格

21 2 格是代数结构 偏序集（格）：代数结构？ 代数结构：偏序集（格）？
设<L; ,>是个代数结构，,是L上二个二元运算，若二元运算,均满足 结合律 交换律 吸收律(a(ab)=a,a (ab)=a)、 等幂律(aa=a,aa=a)， 则称<L, ,>是格。 注：定义中的等幂律可以消除，因它可由吸收律得到： aa= a( a( aa)) =a

22 2 格是代数结构 偏序集合的格、代数结构的格等价
若<L;,>是一个格（代数结构)，那么，L中存在一偏序关系≤,使a,bL ，有 lub(a,b)=ab, glb(a,b)=ab.

23 2 格是代数结构 如何定义偏序关系？ 在集合L上定义二元关系≤如下： (或：a,bL，若a≤b  ab=b)
a,bL，若a≤b  ab=a (或：a,bL，若a≤b  ab=b) 如何证明？ 1) ‘≤’是L上的偏序关系？ 2）a,bL, {a,b}的最大下界存在， 且glb(a,b)=ab。 3）a,bL, {a,b}的最小上界存在， 且lub(a,b)=ab

24 2 格是代数结构 1) 证明’≤’是L上的偏序关系 自反性： aL，由等幂律aa=a,有a≤a 反对称性：
a,bL, 若a≤b, b≤a，即ab=a,ba=b， 于是由交换律，有a=ab=ba=b 传递性： a,b,cL,若a≤b,b≤c，即ab=a, bc=b 于是，由ac=(ab)c = a(bc)= ab=a 得a≤c

25 2 格是代数结构 2)证明 a,bL,{a,b}的最大下界存在，且glb(a,b)=ab i) 下界存在,其一为ab：
由(ab)a=(aa)b=ab 有：ab≤a 同理，ab≤b 从而，ab 是a,b的下界。 ii) ab为最大下界： 设c 是a,b 的任一下界， 即c≤b, c≤a, 由c(ab)= (ca)b=cb=c 有：c≤ab 所以，ab 是a,b的最大下界。

26 2 格是代数结构 3) 同理可证? a,bL, {a,b}的最小上界存在，且lub(a,b)=ab
注：以后可根据需要，随意使用这二种定义和记法<L,≤>或<L;,>

27 2 格是代数结构 子格(subLattice)？ <L, ,>是个格，SL, 若S对运算
的子格。 示例 5 已知右图所示格<{a,b,c,d}, ,> 下列结构是否为其子格？ <{b,c,d},,> <{b,d}, ,> <{a,d}, ,> d c a b

28 2 格是代数结构 格同态? <S,*,+>,<L,,>是二个格,f: LS,
且a,bL 有 f(a*b)=f(a)f(b) f(a+b)=f(a)f(b) 称f是<L, *,+>到<S, ,>的格同态； 若f是双射,则<L,*,+>和<S,,>是同构的

29 2 格是代数结构 格同态的保序性： 证：a≤b  a*b=a f(a)f(b)=f(a*b)=f(a) f(a)≤’f(b)
即：f是格<L,*, +>到<L’,,>的同态映射， 若a,bL，a≤ b 则f(a)≤’f(b) 证：a≤b  a*b=a f(a)f(b)=f(a*b)=f(a) f(a)≤’f(b)

30 2 格是代数结构 示例 6 12 6 4 2 3 1 12 4 2 1 6 3 <S12，整除> <S12，小于等于> 显然，f: S12  S12 ,f(x)=x 则f是保序的， 即a整除b  f(a)小于等于f(b)但f不是同态的: f(3*2)=f(1)=1，而f(3)f(2)=2

31 2 格是代数结构 格同构的充要条件 设f是双射,则f是<A1,≤>到<A2,≤’>的格同构，当且仅当a,bA1,a≤bf(a)≤’f(b) 证：设上述二代数结构为<L,,>，<L’,*, +> 必要性： f是格同构,由格同态的保序性知 a≤b  f(a) ≤’f(b), 另一方面，设f(a) ≤’f(b) 则 f(a)=f(a)*f(b)=f(ab) 而f是双射, 故a= ab 所以a≤b

32 2 格是代数结构 由此看出，同构的二个格，其哈斯图相同？ 充分性： 已知a,b A1, a≤b  f(a)≤’f(b）
需证f是同构, 需证明:f(ab)= f(a)*f(b)即可。 令 c= ab 则 c≤a  f(c)≤’f(a) c≤b  f(c)≤’f(b) 于是，f(c)≤’f(a)*f(b) (1) 令 f(a)*f(b)=f(d) 则 f(d)≤’f(a)  d≤a f(d)≤’f(b)  d≤b 故 d≤ab=c 所以f(d) ≤’f(c) ，即f(a)*f(b) ≤’f(c)（2） 所以，由(1)（2）有f(ab)=f(c)=f(a)*f(b) 证毕。 由此看出，同构的二个格，其哈斯图相同？

33 3 布尔代数 分配格、模格、有补格、有补分配格 布尔代数

34 3 布尔代数 格的最大元、最小元，分别记为1、0；有界格 1、0是唯一的吗？ 示例 7 0是的单位元，1是的单位元？
设S=｛2，3，4，…，100｝，对于普通的数之间的小于或等于关系≤，〈S，≤〉是一个格，其最大元素1=100，最小元素0=2。 1、0是唯一的吗？ 0是的单位元，1是的单位元？

35 3 布尔代数 补元 设<L,,,0,1>是有界格，aL，若存在bL，有ab=0,ab=1，则称b为a的补元，记为a’。 1 若a是b的补元，则b也是a的补元？ 2 有界格中，0，1互为补元？ 3 补元可以不存在，可以不唯一？

36 3 布尔代数 示例 8 a) a的补元是b,c， b的补元是a,c, c的补元是a,b b) a,b,c 均不存在补元 1 a c b 1
a a) a的补元是b,c， b的补元是a,c, c的补元是a,b b) a,b,c 均不存在补元 1 b c a

37 3 布尔代数 若一个格既是有补格，又是分配格， 则此格称为有补分配格， 又称布尔代数(Boolean Algebra) 。 有补格
若在一个有界格中，每个元素至少有一 个补元，则称此格为有补格。 有补分配格 若一个格既是有补格，又是分配格， 则此格称为有补分配格， 又称布尔代数(Boolean Algebra) 。

38 3 布尔代数 示例 9：布尔代数 集合代数，命题代数，开关代数为布尔代数
(因为满足结合律、交换律、吸收律、分配律、存在补元及0，1） 1) 集合代数<P(S), ∩,∪, ,,S>是布尔代数 2) 开关代数<{0,1}, ,, ,0 ,1>是布尔代数,其中 为与运算,为或运算, 为非运算.

39 3 布尔代数 十条定律 设<S;∨,∧,->是一个布尔代数,a,b,c是S中任意三个元素，在S中成立以下算律。    1) 交换律     2) 结合律  3) 等幂律     4) 吸收律  5) 分配律     6) 同一律     7) 零一律     8) 互补律     9) 对合律    10) 德·摩根律 以上十条定律并不都是独立的, 均可由交换律、分配律、同一律和互补律得到。

40 3 布尔代数 示例 10 设<L, , , ´,0,1>是布尔代数,则有: 1) aL, (a´)´=a
2) a,bL,(ab)´=a´b´ 2) 证明: (ab)  ( a´b ´) = (ab a´) (abb´) = ((aa´)  b) (a (bb´)) = (1b) (a 1)=1, (ab) ( a´b ´) = (a a´b´) (ba´b´) = ((a a´)b´ ) ((b b´) a´) = (0b´ ) (0 a´) = 0. 所以 a´b ´是 ab的补元,即 (ab) ´ = a´b ´ 同理可证 ( ab) ´= a ´ b ´

41 3 布尔代数 几个个结论： Bool(n)中任意函数可以表示为多个Bool(n)的原子(也称为基本积或最小项)的运算
布尔代数的每一子代数仍是布尔代数。 一个布尔代数的每一满同态像均是布尔代数。 有限布尔代数与某集合代数同构