哈尔滨理工大学：《离散数学 Discrete Mathematics》课程教学资源（PPT课件讲稿）16 布尔表达式

6-4布尔代数 定义641一个有补分配格称为布尔格。 求一个元素的补元素可以看作一元运算,称为补运算 定义6-42设是由布尔格是由布尔格≤p(S),> 是所诱导的代数系统。这个代数系统为布尔代数 当S=a,b时的运算表如表641所示。P-253页

1 6-4 布尔代数 定义6-4.1 一个有补分配格称为布尔格。 求一个元素的补元素可以看作一元运算，称为补运算。 定义6-4.2 设 是由布尔格 是所诱导的代数系统。称这个代数系统为布尔代数。 例1 设是由布尔格 是所诱导的代数系统。这个代数系统为布尔代数。 当S={a,b}时的运算表如表6-4.1所示。P-253页

表64.1 bs al 0{{ {a} }{a,b}{} {a,b} ta, b.a, b fa, b ta, b ∩ fa b] ta, b g 伪} b fa, bh {a{,b {a,b}

2

定理6-41在一个有界分配格中,对于布尔代数中的 任意两个元素a,b,必定有 (a)=a a∨b=a∧b a∧b=a∨b 日证明:只证第(2)个等式 先证互补的两个式子相并等于全上界“1”。 (ab)∨(a∧b)=(aVb)Va)∧(avb)∨b) =(b∨aVa)∧(aV(b∨b) (b∨1)∧aV1)=1 再证互补的两个式子相交等于全下界“0”。 (ab)∧(a∧b)=0

3 定理6-4.1 在一个有界分配格中，对于布尔代数中的 任意两个元素a，b，必定有 ( a )=a a∨b= a∧b a∧b= a∨b  证明：只证第(2)个等式 先证互补的两个式子相并等于全上界“1” 。 (a∨b)∨(a∧b)= ((a∨b)∨a)∧((a∨b)∨b) =(b∨(a∨a))∧(a∨(b∨b)) =(b∨1)∧(a∨1) =1 再证互补的两个式子相交等于全下界“0” 。 (a∨b)∧(a∧b)= 0 

定义64.3具有有限个元素的布尔代数称为有限布 尔代数。 定义6-44设和是两个 布尔代数如果存在着A到B的双射f,对于任意的a3b∈A 都有 fasb=f(a)vf(b) f(a∧b)=f(a)∧f(b) fa=f(a 则称和同构 可以证明对于每一正整数n,必存在着2个元素的布 尔代数;反之,任一有限布尔代数它的元素个数必为2的幂 次

4 定义6-4.3 具有有限个元素的布尔代数称为有限布 尔代数。 定义6-4.4 设和是两个 布尔代数,如果存在着A到B的双射f,对于任意的a,b A, 都有 f(a∨b)=f(a)∨f(b) f(a∧b)=f(a)∧f(b) f(a)=f(a) 则称和同构。 可以证明,对于每一正整数n,必存在着2 n个元素的布 尔代数;反之,任一有限布尔代数,它的元素个数必为2的幂 次

定义6-45设是一个格,且具有全下界0, 如果有元素a盖住0,则称元素a为原子 原子:与0相邻且比0大” 定理642设是一个具有全下界0的有限格 则对于任何一个非零元素b(即不等于全下界0的元素) 至少存在一个原子a,使得a≤b。 口证明:若b是原子,则有b≤b,若b不是原子,则必 有b存在,使得0-b1是一个有下界的有限格,所以通过有限不骤 总可以找到一个原子b,使得0<b…<b2<b1<b口

5 定义6-4.5 设 是一个格，且具有全下界0， 如果有元素a盖住0，则称元素a为原子。 原子：与0相邻且比0“大” 定理6-4.2 设 是一个具有全下界0的有限格， 则对于任何一个非零元素b（即不等于全下界0的元素） 至少存在一个原子a ，使得a ≤ b 。  证明：若b是原子，则有b ≤ b ，若b不是原子，则必 有b1存在，使得0b1b 若b1是原子，则定理得证，否则，必存在b2使得 0b2b1b 由于是一个有下界的有限格，所以通过有限不骤 总可以找到一个原子bi ，使得0bi... b2b1b 

引理6-41设在一个布尔格中b∧c=0当且仅当b≤c 口证明:(1)先证b/c=0→bsc 若b∧c=0,因为0Vc=c, 则(bAc)∨c=c 根据分配性,就有 (bVc)∧(cVc)=c 即(bVc)∧1=c 所以 bVC=c 又因为b≤b∨c 所以 ≤c (2)再证bsc→b∧c=0 若b≤C,则b∧c<c∧c即b∧c<0,所以b∧c=0口

6 引理6-4.1 设在一个布尔格中,b∧c=0当且仅当b ≤c。  证明：(1)先证 b∧c=0  b ≤ c 若 b∧c=0， 因为 0∨c=c ， 则 (b∧c)∨c=c 根据分配性，就有 (b∨c) ∧ (c∨c) =c 即 (b∨c) ∧1 =c 所以 b∨c =c 又因为 b ≤ b∨c 所以 b ≤ c (2)再证 b ≤ c  b∧c=0 若b≤c,则b∧cc∧c,即b∧c0，所以b∧c=0 

引理6-42设是一个有限布尔代数若 b是A中任意非零元素,a1,a2,…,ak是A中满足asb 的所有原子(j=1,2,,k),则 b=a,va2 V.Va k 口证明:(1先证a1Va2V…aksb 记a1Va2…Vak=c因为a]sb,所以csb (2)再证bsa1Va2V…ak 由引理641知要证bc若是原子,只需证b∧c=0, 反设b∧c≠0,于是必有一个原子a,使得asb∧c 又因b∧csb,和b∧c≤c,所以asb和asc, 因为a是原子且asb所以a必是a1a2,…,ak中的 个因此asc,已有asc,得asc∧c,即a0,与a是原子矛盾 b∧c≠0假设不成立。综合(们和(2定理得证。□°

7  证明：(1)先证 a1∨a2∨…∨ak ≤ b 记a1∨a2∨…∨ak =c,因为aj ≤ b,所以c ≤ b。 (2)再证 b ≤ a1∨a2∨…∨ak 由引理6-4.1知,要证b≤c若是原子,只需证b∧c=0, 反设b∧c≠0,于是必有一个原子a,使得a≤b∧c。 又因b∧c≤b,和 b∧c≤c, 所以 a≤b 和 a≤c , 因为a是原子,且a≤b,所以a必是a1 , a2 , …, ak中的一 个,因此 a≤c,已有a≤c,得a≤c∧c,即a≤0, 与a是原子矛盾。 b∧c≠0假设不成立 。综合(1)和(2)定理得证。 引理6-4.2 设是一个有限布尔代数,若 b是A中 任意非零元素， a1 , a2 , … , ak是A中满足aj ≤b 的所有原子（j=1,2,…,k） ,则 b = a1∨a2∨…∨ak

引理6-43设是一个有限布尔代数若b 是A中任意非零元素,a1a2,…a1是A中满足asb的 所有原子(j=1,2,,k),则b=a1Va2…Va1是将b表示 为原子之并的唯一形式。 口证明设有另一种表示形式为b=a1Va1Vat 其中a11,1是原子。因为b是a131”,的最小上 界所以必有a1Sb,a2≤b,…,atsb。而a1,a,…,a是A 中所有满足a1≤b(i=1,2,,k)的不同原子。 所以必有t≤k 反设tk那么在a1,a2,…,ak中必有apo且a0≠an 于是由a∧(a1 Vaiv.va)=a∧(aVa2Va 即(ap0∧a1)y(a∧a2)∨…V(ap0∧ay =(a0∧a1(ap∧a2)y…y(ap∧a) 导致的0=a矛盾。tk假设不成立。T=k定理得证

8 引理6-4.3 设是一个有限布尔代数,若b 是A中 任意非零元素， a1 , a2 , … ,ak是A中满足aj ≤b的 所有原子（j=1,2,…,k） ,则b = a1∨a2∨…∨ak是将b表示 为原子之并的唯一形式。  证明:设有另一种表示形式为b=aj1∨aj1∨…∨ajt 其中aj1,aj1,…,ajt是原子。因为b是aj1,aj1,…,ajt的最小上 界,所以必有aj1 ≤ b, aj2 ≤ b,..., ajt ≤ b。而a1 , a2 , … , ak是A 中所有满足ai ≤ b （i=1,2,…,k）的不同原子。 所以必有 t≤k 反设tk,那么在a1 , a2 , … , ak中必有aj0且aj0≠ajl 于是,由aj0∧(aj1∨aj1∨…∨ajt)= aj0∧(a1∨a2∨…∨ak ) 即 (aj0∧aj1)∨ (aj0∧aj2)∨ … ∨ (aj0∧ ajt) = (aj0∧a1 )∨ (aj0∧a2 )∨ … ∨ (aj0∧ ak ) 导致的0= aj0矛盾。tk假设不成立。 T=k定理得证。

引理644在一个布尔格中,对A中任意 个原子a和另一个非零元素b,a<b和ab两式中有且 仅有一式成立。 日证明:(1)先证a<b和a两式不可能同时成立 反设a<b和a-b同时成立,就有a<b∧b=0,这 与a是原子相矛盾,即a-b和a-b不同时成立。 (2)再证a-b和a<5两式中必有一式成立 因为a∧b<a,a是原子,所以只能是 a∧b=0或a∧b=a 若a∧b=0,则a∧(b)=0,由引理641得 a-6 若a∧b=a由引理6-1.6得a<b

9 引理6-4.4 在一个布尔格中,对A中 任意一 个原子a和另一个非零元素b，ab 和ab两式中有且 仅有一式成立。  证明：(1)先证ab 和ab两式不可能同时成立 反设ab 和ab同时成立，就有ab∧b=0，这 与a是原子相矛盾，即ab 和ab不同时成立。 (2)再证ab 和ab两式中必有一式成立 因为a∧ba, a是原子,所以只能是 a∧b=0 或 a∧b=a 若a∧b=0，则 a∧(b) =0 ，由引理6-4.1得 ab； 若a∧b=a,由引理6-1.6得ab。 

定理6-43 Stone表示定理)设是由 有限布尔格所诱导的一个有限布尔代数,S是布 尔格中的所有原子的集合,则和同构。 口证明:本定理的证明过程分三部分 (1)构造一个映射,并证明它是双射(既是入射又是满 射) (2描述代数系统和 同构并证明之; (3)总结概括结论。 10

10 定理6-4.3(Stone 表示定理) 设 是由 有限布尔格所诱导的一个有限布尔代数， S是布 尔格中的所有原子的集合，则和同构。  证明：本定理的证明过程分三部分 (1)构造一个映射，并证明它是双射（既是入射又是满 射）； (2)描述代数系统和 同构并证明之； (3)总结概括结论