布尔代数

布尔代数 离散数学－代数结构 南京大学计算机科学与技术系 上一讲内容的回顾  偏序格  格的对偶原理  格的性质  代数格  分配格  有界格与有补格 布尔代数  布尔格  布尔代数系统  布尔代数的性质  布尔代数的同态与同构  有限布尔代数的表示定理  有限布尔代数的基数 布尔格  定义：有补分配格称为布尔格，记为 〈B, ∧, ∨, ‘, 0, 1〉  两个二元运算：“保交”（∧）,“保联”（∨） ，  一个一元运算：“求补” （‘）  两个常量 (零元运算)：“全上界”1，“全下界”0  布尔格的例子  集合的幂集格〈P(B), ⋂, ⋃, ∼, ∅, B〉  逻辑代数〈{0,1}, ∧, ∨, ¬, 0, 1〉 布尔格满足的性质  〈ρ(B), ⋂, ⋃, ∼, ∅, B〉是有补分配格，即布尔格  集合交运算满足交换、结合律  集合并运算满足交换、结合律  集合交与并运算相互满足吸收律 （上述三点说明这是格）  集合交与并运算相互满足分配律，因此是分配格  定义ρ(B)上的关系R，xRy iff. x⋂y=x, 则R即集合包含关系， 是偏序，空集与B本身分别是最小、最大元素，因此是有 界格  对任意x∈ρ(B), ∼x=B-x即为唯一的补元，因此是布尔格。 布尔代数系统  布尔代数〈B,*,◦,▵, a, b〉是代数系统，其中：*和 ◦是二元运算，▵是一元运算，a, b∈B是零元运算 (常量)，且满足下列系统公理：  *和◦满足交换律：∀x,y∈B, x*y=y*x, x◦y=y◦x  *对◦，◦对*均满足分配律： ∀x,y,z, x*(y◦z)=(x*y)◦(x*z), x◦(y*z)=(x◦y)*(x◦z)  a,b分别是◦和*的单位元：∀x∈B, x◦a=x, x*b=x  *和◦满足补元律：∀x∈B: x*(▵x)=a, x◦(▵x)=b 布尔代数是代数格  设〈B,*,◦,▵, a, b〉是布尔代数  〈B,*,◦〉是代数格 ：交换律、吸收律、结合律  从而是分配格（分配律） //只需证明吸收律、结合律。 证明布尔代数是代数格  引理1(a,b分别是*和◦的零元) ∀x∈B, x◦b=b, x*a=a  x◦b=b*(x◦b)=(x◦▵x)*(x◦b)=x◦(▵x*b)=x◦▵x=b  x*a=a◦(x*a)=(x*▵x)◦(x*a)=x*(▵x◦a)=x*▵x=a  引理2：∀x, y, z∈B, x◦y=x◦z且▵x◦y=▵x◦z ⇒ y=z  由前提可得(x◦y)*(▵x◦y)=(x◦z)*(▵x◦z) ⇒ (x*▵x)◦y=(x*▵x)◦z ⇒ a◦y=a◦z ⇒ y=z a是关于“◦”的单位元 证明布尔代数是代数格（续）  证明吸收律  x◦(x*y)=(x*b)◦(x*y)=x*(b◦y)=x*b=x (引理1：b◦y=b)  x*(x◦y)=(x◦a)*(x◦y)=x◦(a*y)=x◦a=x (引理1： a*y=a)  证明结合律  注意：x◦(x*(y*z))=x=x◦((x*y)*z)  且▵x◦(x*(y*z))= ▵x◦(y*z) = ▵x◦((x*y)*z)  由引理2：x*(y*z)=(x*y)*z； //同理可证◦满足结合律。 用分配律与两 次吸收律 布尔代数是有界的、有补的  已经得到〈B,*,◦ 〉是代数格（分配格）  运算*和◦ 可以写作∧和∨  〈B,*,◦〉是有界的  最小元和最大元分别为a和b，即0和1  （单位元）∀x∈B, x◦a=x, x*b=x ⇒ a≼x， x≼b  a与b互为补元  ▵x即为x的补， ∴▵也就是求补运算 '。 布尔代数中与补元有关的性质  双重否定律：∀a∈B, (a')'=a  a和(a')'都是a'的补元，分配格中补元是唯一的。  德摩根律：∀a,b∈B, (a∧b)'=a'∨b'; (a∨b)'=a'∧b'  根据补元的唯一性，只需证明a'∨b'是a∧b的补元。  (a∧b)∨(a'∨b')=(a∨a'∨b')∧(b∨a'∨b') =(1∨b') ∧(1∨a')=1  (a∧b)∧(a'∨b')=(a∧b∧a')∨(a∧b∧b')=(0∧b)∨(a∧0)=0  同理可得：(a∨b)'=a'∧b' 布尔代数中的次序关系  ∀a,b∈B, a≼b ⇔ a∧b'=0 ⇔ a'∨b=1 ⇔a∧b=a ⇔ a∨b=b 这里只需要证明a≼b ⇔ a ∧ b'=0 ⇔ a'∨b=1  a≼b ⇒ a ∧ b'=0 a≼b, b'≼b', ∴a ∧ b'≼b ∧ b', 但b ∧ b'=0, ∴a ∧ b'=0  a ∧ b'=0 ⇒ a'∨b=1 注意0和1互为补元，a' ∨ b = (a∧b')'=1  a' ∨ b=1 ⇒ a≼b: 如果能证明a∨b=b, 则可得a≼b。 a ∨ b=(a∨b)∧ 1=(a ∨ b) ∧(a'∨ b)=(a ∧ a')∨ b=0 ∨b=b 布尔代数同态与同构  定义：设〈B1, ∧, ∨, ' , 0 , 1〉和〈B2, ⋂, ⋃, -, θ, E〉是两个 布尔代数。如果存在ϕ: B1 → B2, 满足：∀a,b∈B1, 有：  (1) ϕ(a∨b) = ϕ(a) ⋃ ϕ(b)  (2) ϕ(a∧b) = ϕ(a) ⋂ ϕ(b)  (3) ϕ(a') = -ϕ(a) 则称ϕ是B1到B2的同态映射。(若ϕ是双射，则是同构)  其实，上述3个等式不是独立的。  (2)+(3)⇒(1): ϕ(a∨b)=ϕ(((a∨b)')')= -ϕ((a∨b)')= -ϕ(a'∧ b')= -(ϕ(a')⋂ϕ(b'))= -(-ϕ(a)⋂-ϕ(b))=ϕ(a)⋃ϕ(b)  同理：(1)+(3)⇒(2) 格中的原子  定义：设L是格，L中有最小元(全下界)0，给定元素 a≠0, 若∀b∈L, 有： 0≺b≼a ⇒ b=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, 矛盾。 格中的原子 a b c d a b d a b c d e (1) (2) (3) e c 原子 有限布尔代数元素的原子表示  T(x)表示所有小于或等于x的原子的集合。这里x是 非0元素。  设T(x)={ a1,a2,…,an}，则x可以表示为a1∨a2∨ … ∨an。  令y=a1∨a2∨…∨an。显然y≼x, 只需证明x≼y, 这等价于 x∧y'=0。  假设x∧y'≠0, 则存在L中的原子t, 满足0≺t≼x∧y', 则 t≼x, 因此t∈T(x), 令t=ai, 由ai=t≼y'可得：ai∧y'=ai。  ai∧y'=ai∧(a1∨a2∨…∨an)'=ai∧(a1'∧a2'∧…∧an')=0 (注意： ai∧ai'=0)，从而ai=ai∧y'=0, 这与原子的定义矛盾。 ∴ x∧y'=0，即x≼y, ∴x=y= a1∨a2∨ … ∨ an。 原子表示的唯一性  给定x, T(x)是唯一确定的。  令T1(x)={a1,a2,…,an}, T2(x)={b1,b2,…,bm}。  反证法。不失一般性，假设ai∉{ b1,b2,…,bm},  ai和诸bj均是原子，∴ai∧bj=0 (j=1,2,…,m)。 ∴ ai∧x=ai∧(b1∨b2∨…∨ bm)=0 ai≼x, ∴ai=ai∧x=0, 与原子的定义矛盾。 ∴ T1(x)=T2(x)。 有限布尔代数的表示定理  任一有限布尔代数B 同构于 B中所有的原子构成的 集合A的幂集代数系统P(A)。 即：〈B, ∧, ∨, ', 0, 1〉≅ 〈P(A), ⋂, ⋃, ∼, ∅, A〉  备注（关于无限布尔代数）  2N，即无限的0/1序列x0, x1, x2, …  这一无限布尔代数有原子  2N的一个子代数：周期序列（Periodic sequence）  这个布尔代数没有原子 {2,3,5} {2,3} {5} {3,5} {2,5} {3} {2} ∅ 30 6 5 15 10 3 2 1 注意：B中任一x对应唯一的T(x)∈P(A), T(x)是小于 或等于x的原子的集合。 ϕ: B → P(A), ∀x∈B, ϕ(x)=T(x)是同态映射。 有限布尔代数的表示定理的证明  ϕ: B → P(A), ∀x∈B, ϕ(x)=T(x)是同态映射。  ϕ(x∧y) = T(x∧y) = {b|b∈A, b≼x∧y} = {b|(b∈A, b≼x)且 (b∈A, b≼y)} = {b|b∈A,b≼x}⋂{b|b∈A,b≼y} = T(x)⋂T(y) = ϕ(x)⋂ϕ(y)  令x=a1 ∨ a2 ∨ … ∨ an , y=b1 ∨ b2 ∨ … ∨ bm 。 则x ∨ y= a1 ∨ … ∨ an ∨ b1 ∨ … ∨ bm , 显然：ϕ(x∨y) = T(x∨y) = T(x)⋃T(y) = ϕ(x) ⋃ ϕ(y)  设x'是x在B中的补元。注意： ϕ(x)⋃ϕ(x')=ϕ(x ∨ x')=ϕ(1)=A 且 ϕ(x)⋂ϕ(x')=ϕ(x ∧ x')=ϕ(0)=∅ ∴ϕ(x') = ∼ϕ(x) 有限布尔代数基数是2的整数次幂  ϕ(x)=T(x)也是同构映射。  单射：若ϕ(x)=ϕ(y), 即T(x)=T(y)={a1,a2,…,an}, ∴x= y = a1∨ a2 ∨ … ∨ an 。  满射：对任意的{a1,a2,…,an}∈P(A), 则x=a1 ∨a2 ∨…∨an∈B, 且ϕ(x)=T(x)= {a1,a2,…,an}  任何有限布尔代数的基数为2n, n是自然数。  设B是有限代数系统，A是B中所有原子的集合。 则：B≅P(A), ∴|B|=|P(A)|=2|A| 等势的布尔代数系统均同构  设B1和B2是有限布尔代数，且|B1|=|B2|；A1,A2分别是相应 的原子的集合。由同构关系的传递性，只需证明： P(A1)≅P(A2)。  显然A1,A2等势，存在从A1到A2的双射，令其为f 。  定义ϕ: P(A1)P(A2), ∀x⊆A1, ϕ(x)={f(t)|t∈x}, 记为f(x), 显然ϕ是双射。  一般地，对f:XY, 若A,B都 是X的子集，则： f(A⋃B)=f(A)⋃f(B) f(A⋂B)⊆f(A)⋂f(B); 但对于单射f, f(A⋂B)=f(A)⋂f(B)。 由这两个等式成立，可得：f(∼x)=∼f(x)。  因此ϕ是同构映射。 最小的几个有限布尔代数 001 111 110 011 101 010 100 000 11 10 01 00 n=0 n=1 0 1 n=2 n=3 与含n个元素的集合的幂集代数 系统同构的布尔代数记为Bn。 Hasse Diagrams of Isomorphic Lattices {a,b,c} {a,b} {c} {b,c} {a,c} {b} {a} ∅ {2,3,5} {2,3} {5} {3,5} {2,5} {3} {2} ∅ 111 110 001 011 101 010 100 000 Lattice Bn  Each element is labeled by a sequence of 0’s and 1’s of length n.  For any elements x=a1a2...an, y= b1b2...bn, in Bn (each ai,bi is 0 or 1):  x≼y iff. ak≼bk for k=1,2,...,n.  x ∧ y = c1c2...cn, where ck=min{ ak,bk }  x ∨ y = d1d2...dn, where dk=max{ ak,bk }  x has a complement x’ = z1z2...zn, where zk=1 if xk=0, and zk=0 if xk=1. Bn as Product of n B’s  B1, ({0,1}, ∧, ∨, 1, 0, ’), is denoted as B.  For any n≥1, Bn is the product B×B×...×B of B, n factors, where B×B×...×B is given the product partial order. Product partial order: . allfor ifonly and if kyxyx kk ≤≤ Hasse Diagrams of Bn 001 111 110 011 101 010 100 000 11 10 01 00 n=0 n=1 0 1 n=2 n=3 Some Examples Dn is the poset of all positive divisors of n with the partial order “divisibility”. 6 2 3 1 D6 5 30 6 15 10 3 2 1 D30 D20 is not a Boolean algebra 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. Proof of Non-Boolean Algebra  For a given poset, if any of the formula satisfied by set axioms can’t be satisfied, the poset is not a Boolean algebra.  Example 1 Proof of Non-Boolean Algebra  Example 2: 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. 布尔代数与数字逻辑电路设计  与含n个元素的集合的幂集代数系统同构的布尔代数 记为Bn。逻辑代数系统是B1。  Bn的每一个元素可以看做一个长度为n的二进字符串。  一个有n个输入、一个输出的逻辑电路对应于一个用 含n个布尔变量的布尔代数表达式定义的布尔函数 f : B1n→B1, 也可以看做 f : Bn→B1 。  在确定表示该函数的布尔表达式后，很容易用门电路 元件搭出所需要的逻辑电路。  因此，关键问题是如何确定所需的布尔表达式，并将 其化为最简形式。 一个逻辑电路设计的例子  举重比赛中三个裁判中两个或者两个以上判定为成功则该 次成绩有效, 设计一个电子打分器, 输出一个结果: “成功” 或”失败”。 布尔函数: f(x,y,z)=1 iff. x,y,z 至少有两个为1。 x z y 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 f(x,y,z) 0 0 0 1 0 1 1 1 相应的布尔表达式: (x’∧y∧z)∨ (x∧y’∧z)∨ (x∧y∧z’)∨ (x∧y∧z) 基本逻辑元件 x y x ∨ y “或”门 x y x ∧ y “与”门 x x’ 反相器 电路设计 相应的布尔表达式: (x’∧y∧z)∨ (x∧y’∧z)∨ (x∧y∧z’)∨ (x∧y∧z) x y z x’ y’ z’ f(x,y,z) 太复杂! 用卡诺图化简布尔表达式 x z y 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 f(x,y,z) 0 0 0 1 0 1 1 1 x’ x yz y’z yz’ y’z’ 0 0 1 0 1 0 1 1 简化后的表达式: (y∧z)∨ (x∧z)∨ (x∧y) 改进后的电路设计 相应的布尔表达式: (y∧z)∨ (x∧z)∨ (x∧y) x y z f(x,y,z) x y z x’ y’ z’ 作业  P. 219  12-14  16-19 卡诺图（Karnaugh map）n=2 基本位置 f: B2→B 00 01 10 11 y’ x’ x y x’∧y’ x∧y’ x∧y x’∧y f(x,y)=(x’∧y’)∨(x’∧y) x y f(x,y) 0 0 1 1 0 1 0 1 1 1 0 0 y’ y x x’ 1 0 0 1 用卡诺图化简布尔表达式 基本位置 f: B2→B 00 01 10 11 y’ x’ x y x’∧y’ x∧y’ x∧y x’∧y f(x,y)=(x’∧y’)∨(x’∧y)∨(x∧y’) x y f(x,y) 0 0 1 1 0 1 0 1 1 1 1 0 y’ y x x’ 1 1 0 1 f(x,y) = x’ ∨ y ’ 卡诺图 n=3 00 01 10 11 0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 0 1 0 1 1 1 1 1 1 1 0 x’ x x’∧y’∧z’ x∧y’∧z x’∧y’∧z’ x’∧y’∧z x’∧y∧z x∧y∧z x’∧y∧z’ x∧y∧z’ y∧z’ y∧z y’∧z y’∧z’ y’ y z z’ 化简三个变量的布尔表达式 x z y 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 f(x,y,z) 1 0 1 0 1 0 1 1 表达式: (x’∧y’∧z’)∨ (x’∧y∧z’)∨ (x∧y’∧z’)∨ (x∧y∧z’)∨ (x∧y∧z) x’ x yz y’z yz’ y’z’ 1 1 1 1 1 0 0 0 z’ So, z’∨(x∧y) 布尔代数 上一讲内容的回顾 布尔代数 布尔格 布尔格满足的性质 布尔代数系统 布尔代数是代数格 证明布尔代数是代数格 证明布尔代数是代数格（续） 布尔代数是有界的、有补的 布尔代数中与补元有关的性质 布尔代数中的次序关系 布尔代数同态与同构 格中的原子 格中的原子 有限布尔代数元素的原子表示 原子表示的唯一性 有限布尔代数的表示定理 幻灯片编号 19 幻灯片编号 20 有限布尔代数的表示定理的证明 有限布尔代数基数是2的整数次幂 等势的布尔代数系统均同构 最小的几个有限布尔代数 Hasse Diagrams of Isomorphic Lattices Lattice Bn Bn as Product of n B’s Hasse Diagrams of Bn Some Examples Dn as Boolean Algebra Proof of Non-Boolean Algebra Proof of Non-Boolean Algebra 布尔代数与数字逻辑电路设计 一个逻辑电路设计的例子 基本逻辑元件 电路设计 �用卡诺图化简布尔表达式 改进后的电路设计 作业 卡诺图（Karnaugh map）n=2 用卡诺图化简布尔表达式 卡诺图　 n=3 化简三个变量的布尔表达式