为原子集的布尔代数.pptVIP

计算机学院 计算机科学与工程学院 冯伟森 Emeil ： fws365@scu.edu.cn 2008 年 12 月 16 日星期二 * 计算机学院 * 布尔代数 在有补分配格中每个元都有补元而且补元惟一，则可以将求元素的补元“ˉ”作为一种一元运算。称有补分配格B, 为布尔格。 布尔格又称为布尔代数。它包含三种运算 ∨, ∧,ˉ，有两个特殊元0，1。 因而布尔格B, 又写成B,∨, ∧,ˉ,0,1，以突出其代数特征。 若一个布尔代数的元素个数是有限的，则称此布尔代数为有限布尔代数。 * 计算机学院 * * 计算机学院 * 布尔代数的性质 布尔代数是有补分配格，有补分配格B， 必须满足： 是格 分配律成立 有最大元和最小元（有界）； 每个元的补元存在而且唯一； 最大元1和最小元0可以用下面的同一律和零律来描述：在B中存在两个元素0和1，使得对任意a∈B，有 a∧1＝a，a∨0＝a；a∨1＝1，a∧0＝0。 * 计算机学院 * 补元的存在可以用下面的互补律来描述： 对任意a∈B，存在 ∈B，使得 a∧ ＝0，a∨ ＝1。 因此,布尔代数B,∨, ∧,ˉ,0,1满足下面的 运算规律： 定理17.13 设a,b,c是布尔代数 B,∨, ∧,ˉ,0,1中的任意元素，则 ① a∨b=b∨a, a∧b=b∧a。 (交换律) ② a∨(b∨c)=(a∨b)∨c, a∧(b∧c)=(a∧b)∧c。 ③ a∨(b∧c)=a, a∧(a∨b)=a。 (吸收律) ④ a∧a=a,a∨a=a. (幂等律) ⑤ (分配律) * 计算机学院 * (结合律) ⑥ 如果a∨b=a∨c且a∧b=a∧c，则b=c.(消去律) ⑦ 0≤a≤1. (有界律) ⑧ a∨0=a,a∧1=a. (同一律) ⑨ a∨1=1,a∧0=0. (零律) ⑩ a∨ =1,a∧ =0. (互补律) 定理的证明参见前面各节。 * 计算机学院 * (De.Morgan定律) 例17-4.1 幂集格2S,? 是布尔代数。相应的运 算为并、交、补，最大元是S，最小元是空集，因 而可以写成 2S,∪，∩，ˉ ，? ，S的形式。 例17-4.2 因子格D30，|是布尔代数，前面已经 证明它是分配格，由习题十七第19题，30=2*3*5， 所以它又是有补格，因而是布尔格。它对应的运 算是lcm、gcd，补运算用“ˉ”表示:?n=30/n， 最小元是1，最大元是30。于是，这个布尔代数可 写为D30,lcm,gcd, ˉ,1,30。 * 计算机学院 * * 计算机学院 * 定义17.11 在布尔格〈B， 〉中，直接盖住最小元0的元素称为原子。 解释： 即a是格中的原子，则不能存在元素b使得0≤b≤a。 例如在幂集格〈2S，?〉中，由S中单元素构成的子集都是原子，其余的就不是原子。 * 计算机学院 * 定理17.14 在有限布尔代数B,∨, ∧,ˉ,0,1中，a、b是不同原子，x、y是任意元素，则 a∧b=0； a≤x 和 a≤ 两式中有且仅有一式成立； a≤x∨y 当且仅当a≤x或者a≤y 。 证明：①由于a∧b ≤a且a∧b ≤b,不可能存在a∧b=a或a∧b=b的情况。因为它导致a≤b或b≤a的结果与原子定义矛盾，因此只能a∧b=0。 由于a∧x≤a且a是原子，必然a∧x=a或a∧x=0之一成立。前者表明a≤x，而当a∧x=0时， ∵ a∧(x∨?x )= (a∧x)∨(a∧?x )=a ∴ a ∧?x =a，即 a≤?x。 其次，两式不可能同时成立，否则a≤x∧?x =0。 * 计算机学院 * 有 仅有 ③如果a≤x∨y，那么a∧(x∨y)=a，即(a∧x)∨(a∧y)=a。由于a是原子，必然a∧x=a或a∧y=a，即a≤x或a≤y。 反之，如果a≤x或者a≤y，都能导出 a≤x∨y的结论。 * 计算机学院 * 定理17.15 设由有限布尔代数B,∨，∧,ˉ,0,1的全体原子构成的集合为S={a1,a2,，…，an}，则对B中任何不是0的元素x，存在ai1,ai2…aik∈S, aij≤x(j=1,2, …,k)使得 x=