离散数学－代数结构 南京大学计算机科学与技术系

Presentation on theme: "离散数学－代数结构 南京大学计算机科学与技术系"— Presentation transcript:

1 离散数学－代数结构 南京大学计算机科学与技术系
布尔代数 离散数学－代数结构 南京大学计算机科学与技术系

2 内容提要 布尔函数 布尔代数 布尔代数的抽象定义 布尔代数的性质 有限布尔代数 布尔代数与数字逻辑电路设计

3 布尔函数 令B={0, 1}, Bn={(x1, …, xn)| xiB, i =1, …, n}, 从Bn到B 的函数称为n度布尔函数， f : BnB。 取值范围为B的变元称为布尔变元 ，xB。 n度布尔函数的个数：22n (22 , 24 , 28, …) 三种说法 含n个命题变量的命题逻辑表达式 n度布尔函数 f : BnB 有n个输入和一个输出的逻辑电路

4 一个逻辑电路设计的例子 举重比赛中三个裁判中两个或者两个以上判定为成功则该次成绩有效, 设计一个电子打分器, 输出一个结果: “成功”或”失败”。 x y z f(x,y,z) 布尔函数: f(x,y,z)=1 iff. x,y,z 至少有两个为1。 相应的布尔表达式: (xyz) (xyz) (xyz) (xyz)

5 回顾：命题表达式的主析取范式 求 (pq)  r 的主析取范式 (¬p r)  (q r)  (p¬q¬r ) （析取范式）
(¬p ¬q  r)  (¬p  q  r)  (p  q  r)  (p ¬q¬r ) (¬p ¬q  r)  (¬p  q  r)  (p¬q¬r)  (p  q  r) ¬p  r  ¬p  (¬q  q)  r  (¬p  ¬q  r )  (¬p  q  r ) q  r  ( p  q  r )  (¬p  q  r )

6 集合{0, 1}上的运算 布尔和 1+1=1, 1+0=1, 0+1=1, 0+0=0 布尔积
11=1, 1 0=0, 01=0, 00=0 补 0=1, 1=0

7 布尔函数上的运算 布尔和 (f+g)(x1, …, xn)= f(x1, …, xn)+g(x1, …, xn) 布尔积
补函数 f (x1, …, xn)= f(x1, …, xn)

8 布尔恒等式（1） 等 式 名 称 x+(y+z)=(x+y)+z x (yz)=(xy)  z 结合律 x+y = y+x
等 式 名 称 x+(y+z)=(x+y)+z x (yz)=(xy)  z 结合律 x+y = y+x xy = yx 交换律 x+(yz)=(x+y)(x+z) x (y+z)=xy +x z 分配律 x+0 = x x1 = x 同一律 x + x =1 x  x =0 补律

9 布尔恒等式（2） 等 式 名 称 x+(xy)=x x (x+y)=x 吸收律 x+x = x xx = x 幂等律 x+1 = 1
等 式 名 称 x+(xy)=x x (x+y)=x 吸收律 x+x = x xx = x 幂等律 x+1 = 1 x0 = 0 支配律 x = x 双重补律 (x  y) = x + y (x+y) = x  y 德摩根律

10 布尔代数的抽象定义 一个布尔代数是一个集合B，它有二元运算和、一元运算 以及特殊元素0和1，且x, y, zB, 下列性质成立：
x(yz)=(xy)z x(yz)=(xy)z 结合律 xy =yx xy= yx 交换律 x(yz)=(xy)(xz) x(yz)=(xy) (xz) 分配律 x0 = x x1 = x 同一律 x  x =1 x  x =0 补 律 a,b分别是◦和*的单位元蕴含两者之一：a是全下界，0是上确界运算，b是全上界，*是下确界运算；a是全上界，0是下确界运算，b是全下界，*是上确界运算；

11 布尔代数举例 ({0, 1}, +,  , , 0, 1)为布尔代数 n度布尔函数全体也构成一个布尔代数
({0, 1}, +,  , , 0, 1)为布尔代数 n度布尔函数全体也构成一个布尔代数 布尔和 布尔积 补函数 全取0的函数、全取1的函数 A的幂集也构成一个布尔代数((A), ⋂, ⋃, , , A） a,b分别是◦和*的单位元蕴含两者之一：a是全下界，0是上确界运算，b是全上界，*是下确界运算；a是全上界，0是下确界运算，b是全下界，*是上确界运算；

12 布尔代数举例 Bn={(x1, …, xn)| xiB, i =1, …, n}构成布尔代数
x= (a1 , …, an), y=(b1 , …, bn), aiB, biB x  y = (c1 , …, cn), where ci=aibi x  y = (d1 , …, dn), where di=aibi x= (e1 , …, en), where ei=ai a,b分别是◦和*的单位元蕴含两者之一：a是全下界，0是上确界运算，b是全上界，*是下确界运算；a是全上界，0是下确界运算，b是全下界，*是上确界运算；

13 布尔代数的性质 结合律、交换律、分配律、同一律、补律 蕴含：支配律、吸收律、幂等律、双重补律、德摩根律
证明支配律： xB, x1=1, x0=0 x1= 1(x  1)= (x  x)(x 1)= x  (x  1)= x  x=1 x0= 0(x 0) =(x  x) (x 0)= x  (x  0)= x  x=0

14 布尔代数的性质 证明吸收律 证明幂等律 x  (xy)= (x1)  (xy)= x  (1y) = x1 = x
x  x= x  (x0) = x (应用同一律、吸收律） 吸收律 幂等律 x  x = x  ( x  (xx) ) = x (两次应用吸收律）

15 布尔代数的性质 引理：x, y, zB, 若 xz=yz 且 xz = yz ，则 x = y 证明双重补律
x = x(xz) = x  (yz) = (x  y) (x  z ) //吸收律/分配律 y = y(y z ) = y  (xz) = (y  x) (y  z ) 证明双重补律 x  x =1= x  x x  x =0= x  x x = x

16 布尔代数的性质 证明德摩根律： x, yB, (xy)= x  y; 根据补元的唯一性，只需证明x  y是xy的补元。
(xy) (x  y)= (x  x  y )(y  x  y ) =1 (xy) (x  y)= (x  y x ) (x  y  y ) =0

17 布尔代数的性质 结合律 交换律 分配律 同一律 补律 支配律 吸收律 幂等律 双重补律 德摩根律 格 布尔代数：有补的分配格

18 格中的原子 定义：设L是格，L中有最小元(全下界)0，给定元素a0, 若xL, 有： 0≺x≼a  x=a 则称a是L中的原子
（原子是覆盖最小元的那些元素。） 设a, b是格L中的原子，若ab, 则ab=0 假设a  b0, 注意：ab≼a且ab≼b，由原子的定义： ab=a, ab=b, a=b, 矛盾。

19 格中的原子 a a a c c b b b d 原子 c d d e e (1) (2) (3)

20 有限布尔代数的表示定理 任一有限布尔代数B 同构于 B中所有的原子构成的集合A的幂集代数系统P(A)。
即(B, , , ', 0, 1)  (P(A), ⋂, ⋃, , , A) 备注（关于无限布尔代数） 2N，即无限的0/1序列x0, x1, x2, … 这一无限布尔代数有原子 2N的一个子代数：周期序列（Periodic sequence） 这个布尔代数没有原子

21 有限布尔代数（示例） {2,3,5} 30 {2,3} 6 {2,5} {3,5} 10 15 {3} 3 {5} {2} 5 2  1

22 有限布尔代数基数是2的整数次幂 任何有限布尔代数的基数为2n, n是自然数。 等势的有限布尔代数均同构
设B是有限代数系统，A是B中所有原子的集合。 则：BP(A), |B|=|P(A)|=2|A| 等势的有限布尔代数均同构

23 有限布尔代数（举例） 与含n个元素的集合的幂集代数系统同构的布尔代数记为Bn n=0 n=2 n=1 n=3 001 111 110 011
101 010 100 000 11 10 01 00 n=0 n=1 1 n=2 n=3

24 Hasse Diagrams of Isomorphic Lattices
111 110 001 011 101 010 100 000 {2,3,5} {2,3} {5} {3,5} {2,5} {3} {2}  {a,b,c} {a,b} {c} {b,c} {a,c} {b} {a} 

25 Bn as Product of n B’s B1, ({0,1}, , , 1, 0, ’), is denoted as B.
For any n≥1, Bn =BB...B, where BB...B is given the product partial order.

26 Hasse Diagram of Bn n=0 n=2 n=1 n=3 1 11 10 01 001 00 100 000 111 110
101 011 10 01 010 n=0 001 00 100 n=2 000 n=1 n=3

27 Examples Dn is the poset of all positive divisors of n with the partial order “divisibility”. 30 6 6 15 10 D20 is not a Boolean algebra 2 3 3 5 2 1 1 D30 D6

28 Dn as Boolean Algebra Let n=p1p2...pk, where the pi are distinct primes. Then Dn is a Boolean algebra. Let S={p1, p2, ... pk}, and for any subset T of S, aT is the product of the primes in T. Note: any divisor of n must be some aT. And we have aT|n for any T. For any subsets V,T, VT iff. aV|aT, and aVaT=GCD(aV, aT) and aVaT=LCM(aV, aT). f: P(S)Dn given by f(T)= aT is an isomorphism from P(S) to Dn.

29 Proof of Non-Boolean Algebra
If n is a positive integer and p2|n, where p is a prime number, then Dn is not a Boolean algebra. Proof Since p2|n, n= p2q for some positive integer q. Note that p is also an element of Dn, then if Dn is a Boolean algebra, p must have a complement p’, which means GCD(p, p’)=1 and LCM(p, p’)=n. So, pp’=n, which leads to p’=pq. So, GCD(p, pq)=1, contradiction.

30 下列格是否构成布尔代数？ 24 8 4 6 2 3 12 1

31 布尔代数与数字逻辑电路设计 一个有n个输入、一个输出的逻辑电路对应于一个用 含n个布尔变量的布尔代数表达式定义的布尔函数 f : BnB。
布尔函数的表达式：{和、积、补}是函数完全的。 用门电路元件（并、交、否）搭出所需的逻辑电路。 电路极小化：卡诺图

32 作业 教材内容：[屈婉玲] 11.2节 课后习题： pp. 262—263 13—14 16—19 p. 219 13—14 16—19