复旦大学：《离散数学 Discrete Mathematics（下）》英文课件（赵一鸣）19/32

冷定理1710布尔格(B;s中任a,b∈B,有: (1)a的补元是唯一的。 (2)(aAb)=avb, avb =aAb 冷(3)a∧b=0÷→a≤b' 冷(4)a")=a

❖ 定理17.10:布尔格(B;≤)中任a,bB,有: ❖ (1)a的补元是唯一的。 ❖ (2)(ab)'=a'b',(ab)'=a'b'。 ❖ (3)ab=0a≤b'。 ❖ (4)(a')'=a

冷证明:(1)设a1a2为a的补元则有ava=1, a4a=0,ava=1,a2∧a=0 冷目标是a=a2 冷(2)要证(aAb)=avb即证 冷(aby(avb")?=?1,(a∧b)(avb")?=?0 冷(3)由ab=0,证明a≤b, 令关键是如何由ab=0引出a与b的联系 冷注意到定理171(2)a≤b当且仅当ab=a; 因此可考虑由ab=0,导出ab=a 冷由a≤b证明ab=0, 利用保序性

❖ 证明:(1)设a1 ,a2为a的补元,则有a1a=1, a1a=0,a2a=1, a2a=0, ❖ 目标是a1=a2 ❖ (2)要证(ab)'=a'b',即证 ❖ (ab) (a'b')=1, (ab)(a'b')=0 ❖ (3)由ab=0,证明a≤b', ❖ 关键是如何由ab=0引出a与b'的联系. ❖ 注意到定理17.1(2):a≤b当且仅当ab=a; ❖ 因此可考虑由ab=0,导出ab'=a ❖ 由a≤b',证明ab=0, ❖ 利用保序性

今由(B;)定义了运算,而a的补元a也 是B中的元素,且分配格补元唯 "看作为B上的一元运算。 [BV,八]为代数系统,又称为布尔优数

❖ 由(B;≤)定义了,运算，而a的补元a'也 是B中的元素，且分配格补元唯一 ❖ '看作为B上的一元运算。 ❖ [B;,,']为代数系统，又称为布尔代数

冷布尔代数[B;v,∧]是有补分配格,具有性 质LL4 冷L幂等律:ava=aaAa=a; L2交换律avb=bva,ab=ba; 冷L3结合律av(bvc)=( avb)vc (b∧c)=(a∧b)∧c 冷L4吸收律:av(ab)=a,aA(avb)=a 冷分配格,满足分配等式D1D2 冷D1av(bAC)}=(avb)A(avc)(abv(a∧C=a(by &o D2: (aab(aAcv(bac=lavb)(avc)(bvc)

❖ 布尔代数[B;,,']是有补分配格,具有性 质L1~L4 , ❖ L1幂等律:aa=a,aa=a; ❖ L2交换律:ab=ba,ab=ba; ❖ L3结合律:a(bc)=(ab)c, ❖ a(bc)=(ab)c; ❖ L4吸收律:a(ab)=a, a(ab)=a。 ❖ 分配格,满足分配等式D1~D2 , ❖ D1 :a(bc)=(ab)(ac);(ab)(ac)=a(b c) ❖ D2 :(ab)(ac)(bc)=(ab)(ac)(bc)

有补格:一定是有界格,每个元素有补元, 满足 B1B2和C1C 1 35 B1:av1=1;a∧0=0 B,a∧1=a;av0=a cava=1,a∧a"=0 ☆C2:0=1 C3 anb)=avb, avb)=aAb

❖ 有补格:一定是有界格,每个元素有补元, 满足B1、B2和C1~C3 , ❖ B1 :a1=1;a0=0 ❖ B2 :a1=a;a0=a ❖ C1 :aa'=1,aa'=0 ❖ C2 :0'=1 ❖ C3 :(ab)'=a'b',(ab)'=a'b’

冷和入定义即为P1并可得到P2P3 冷P1a∨b是a和b的最小上界,a~b是a和b 的最大下界 冷P2asb当且仅当ab=a 令P3:a∧b=0÷a≤b 冷上述性质并不是相互独立的,可以从其 中几个推出另外几个性质

❖ 和定义即为P1 ,并可得到P2~P3 , ❖ P1 :ab是a和b的最小上界，ab是a和b 的最大下界 ❖ P2 :a≤b当且仅当ab=a ❖ P3 :ab=0a≤b’ ❖ 上述性质并不是相互独立的，可以从其 中几个推出另外几个性质

定理1711:B至少包含两个元素,和入为B 上的两个二元运算,为B上的一元运算若 对任何ab,c∈B满足 (H1avb=bva, aAb=bAao (H2)ab∧c=(avb)入avc);(ab(a入C= a∧(bvc) 冷(H3)在B中存在零元0使a0=a,aA0=0,存 在单位元1,使a入1=a,av11。 冷(Ha'∈B使aAa=0,ava=1。 冷则[BV,^为布尔代数

❖ 定理17.11:B至少包含两个元素,和为B 上的两个二元运算,'为B上的一元运算,若 对任何a,b,cB满足: ❖ (H1 )ab=ba,ab=ba。 ❖ (H2 )a(bc)=(ab)(ac);(ab)(ac)= a(bc) ❖ (H3 )在B中存在零元0,使a0=a,a0=0,存 在单位元1,使a1=a,a1=1。 ❖ (H4 )a'B,使aa'=0,aa'=1。 ❖ 则[B;,,']为布尔代数

[B;∨,∧,]为代数系统,,为定义在B 上的二元运算,为定义在B上的 元运算,满足条件(H1)~(H小,则称B为 布尔代数

❖[B; ,,']为代数系统,,,为定义在B 上的二元运算,’为定义在B上的一 元运算, 满足条件(H1 )~(H4 ),则称B为 布尔代数

二、布尔环 冷定义:在布尔代数[Bv,]中,定义B上的 二元运算+及·如下:任a,b∈B 冷a+b=(ab)v(ab),ab=a∧b 冷容易验证在一般的布尔代数[B;]上定 义的[B;+,]是可交换的有单位元环。我 们称这样的环为布尔环 冷定义17.12:[Bv八]为布尔代数如上定 义+,,则有[B;+,]为环称此环为布尔环

❖ 二、布尔环 ❖ 定义:在布尔代数[B;,,']中,定义B上的 二元运算+及·如下:任a,bB ❖ a+b=(ab')(a'b),a·b=ab ❖ 容易验证在一般的布尔代数[B;,,']上定 义的[B;+,·]是可交换的有单位元环。我 们称这样的环为布尔环 ❖ 定义17.12:[B;,,']为布尔代数,如上定 义+,·,则有[B;+,·]为环,称此环为布尔环

定理1712:[B;+,]为布尔环则对任 a∈Ba2=a,且2a=0。 冷引理:设[A;+,]为环若对任a∈Aa2=a, 则必有2a=0。 冷给定的有单位元1的环[B;+,]若它的每个 元素都是幂等元,且定义任a,b∈Ba=1a, avb=a+b-ab,a~b=ab,可以得到一个代 数系统[B;V,]可以验证它满足H~H4, 因此所定义的代数系统[B;2]是布尔代 数

❖ 定理17.12:[B;+,·]为布尔环,则对任 aB,a2=a,且2a=0。 ❖ 引理：设[A;+,·]为环,若对任aA,a2=a, 则必有2a=0。 ❖ 给定的有单位元1的环[B;+,·],若它的每个 元素都是幂等元,且定义任a,bB,a'=1-a, ab=a+b-a·b,ab=a·b,可以得到一个代 数系统[B;,,'],可以验证它满足H1~H4 , 因此所定义的代数系统[B;,,']是布尔代 数