离散数学(二)布尔代数部分.pdf

离散数学离散数学 二二 第十一讲第十一讲 计算机学院计算机学院 焦晓鹏焦晓鹏 布尔代数布尔代数 布尔代数两个定义布尔代数两个定义1 11 1 布尔同态布尔同态2 2 主要内容主要内容 布尔代数的定义布尔代数的定义重点重点 重点和难点重点和难点 有限布尔代数的结构有限布尔代数的结构3 3 有限布尔代数的结构有限布尔代数的结构难点难点 一 布尔代数两个定义一 布尔代数两个定义 布尔代数的定义 布尔代数的定义 定义定义1 布尔代数 有界有补的分配格 定义定义1 是代数系统 和 是B上的二元运算 如果对任意的元 素a b c B 满足下列4条 则称为布尔代数布尔代数 1 交换律交换律 a b b a 和 a b b a 2 分配律分配律 a b c a b a c 和 a b c a b a c 3 全上全上 下下 界界 B中存在两个元素0和1 对B中任意元素a 满足 a 1 a 和 a 0 a 4 补元存在性补元存在性 对B中每一元素a都存在一元素a 满足 a a 0 和 a a 1 定义定义1 定义定义1 证明见下页 一 布尔代数两个定义一 布尔代数两个定义 定义定义1 定义定义1 显然 下面证明定义定义1 定义定义1 定义1 定义1 证明见下页 1 交换律交换律 运算 和 是可交换的 2 吸收律吸收律 要证明 a a b a 和 a a b a a a b a 0 a b a 0 b a 0 a 同理可证 a a b a 3 结合律结合律 要证明 a b c a b c i 首先证明a c b c a c b c 则a b a a 1 a c c a c a c b c b c b c c b ii 现证明 a b c a a b c a a b c a a b c a a b c a a b a c a a c a a a b c a a 所以 a b c a a b c a a b c a a b a c a a a b a c a 0 b a c a b a c a a b c a a a b a c a b a c a 所以 a b c a a b c a 一 布尔代数两个定义一 布尔代数两个定义 例例1 1 B1 20 2 B2 21 3 B4 22 4 S a1 an S 2n 为布尔代数为布尔代数 5 X A A是由变元p1 p2 pn 构成的合式公 式集 等价公式视为同一公式 最小项有2n个 X共2 2n 个命题公式 为布尔代数 结论结论 1 每一正整数n N 一定存在2n个元素的布尔代数 S a1 an S 2n 2 反之 对于任一有限布尔代数L 总存在自然数n N 使得 L 2n 它的元素个数必为2的幂次 二 布尔同态二 布尔同态 定义定义2 具有有限个元素的布尔代数称为具有有限个元素的布尔代数称为有限布尔代数有限布尔代数 定义定义3 设和是两个布尔代数 定义一 个映射f A B 如果在f的作用下能够保持布尔代数的所有运算 且 常数相对应 亦即对于任何a b A有 f a b f a f b f a b f a f b f a f a f 0 f 1 则称映射f A B是一个布尔同态布尔同态 三 有限布尔代数的结构三 有限布尔代数的结构 定义定义4 是格 有全下界0 a L 满足 1 a 0 2 不 b L使得0 b a 则称a为该布尔代数的一个原子原子 定义定义5 设 是一个格 且具有全下界0 如果有元素a盖住0 则称 元素a为原子 原子 与原子 与0相邻且比相邻且比0 大 大 盖住关系盖住关系 设a b是一个格中的两个元素 如果b a且b a 即b a 并且在此 格中再没有别的元素c 使得b c和c a 则称元素元素a覆盖元素覆盖元素b 例子例子 参见右图参见右图 d e均是原子 实际上 在布尔代数中 原子是B 0 的极小元 因为原子与0之 间不存在其他元素 三 有限布尔代数的结构三 有限布尔代数的结构 布尔代数的原子有以下性质 定理定理1 设是布尔代数 a B是原子的充分必要条件是a 0 且对B中任何元素x有 x a a 或 x a 0 I 定理定理2 设a b为布尔代数中任意两个原子且a b 则a b 0 定理定理1的证明的证明 先证必要性先证必要性 设a是原子 显然a 0 另设x a a 由于x a a 故x a a 据原子的定义和0 x a 可得x a 0 再证充分性再证充分性 设a 0 且对任意x B 有x a a或x a 0成立 若a不是原子 那么必有 b B 使0 b a 于是 b a b 因为b 0 b a 故b a b与式 I 矛盾 因 此 a只能是原子 三 有限布尔代数的结构三 有限布尔代数的结构 定理定理2的证明的证明 反证法反证法 假如a b 0 令a b c 若a b是原子且a b 0 则 0 c a 0 c b c a 时与a为原子相矛盾 c a时 结合0 c b 得0 a b 与b为原子相矛盾 所以a b 0 引理引理1 设是一有限布尔代数 则对于B中任一非 零元素b 恒有一原子a B 使a b 证明证明 任取b B且b 0 若b为原子 有b b 则命题已得证 若b不是原子 则必有b1 B 使得0 b1 b 若b1不是原子 存在b2使0 b2 b1 b 对b2重复上面的讨论 因为B有限 这一过程必将中止 上述过程产生的元素序列满足 0 b2 b1 b 即存在br br为原子 且0 br b 否则此序列无限长 三 有限布尔代数的结构三 有限布尔代数的结构 引理引理2 设是有限布尔代数 则 1 任意b c B 有b c 0当且仅当b c 2 对于B中任一原子a和任一非零元素b a b 和a b 两式中有且仅有一式 成立 证明证明 1 必要性必要性 若b c 0 证明b c b c c c b c c 0 c c b c c c b c 1 b c 所以b c c 故b c 充分性充分性 若b c 证明b c 0 c c 且b c 有b c c c 0 所以b c 0 2 先证先证a b 和和a b 两式不可能同时成立两式不可能同时成立 假如a b 和a b 同时成立 就有a b b 0 这与a是原子相矛盾 再证再证a b 和和a b 两式中必有一式成立两式中必有一式成立 因为a b a a是原子 所以只 能是a b 0或a b a 若a b 0 则 a b 0 由 1 得a b 若a b a 得 a b 命题得证 三 有限布尔代数的结构三 有限布尔代数的结构 引理引理2说明说明 原子是这样的元素 它把B中的元素分为两类 第一类是与 自己可比较的 包括自身 它小于等于这一类中的任一元素 第二类是与 自己不可比较的或是0 它小于等于这一类中任一元素的补元 为了加深对原子和定理7 4 2的认识 试考察图7 4 3 a 中 a1是原子 b 中 a1和a2是原子 c 中 a1 a2和a3是原子 在 a b c 三图中 虚线都是表 示原子a1将B的元素划分成两类 三 有限布尔代数的结构三 有限布尔代数的结构 引理引理3 设是一个有限布尔代数 若x是A中任意非零元素 a1 a2 ak是A中满足aj x的所有原子 j 1 2 k 则 x a1 a2 ak 证明证明 1 先证 a1 a2 ak x 记a1 a2 ak c 因为aj x 所以c x 2 再证 x a1 a2 ak c 由引理2 1 知 要证x c只需证x c 0 反设x c 0 于是必有一个原子a 使得a x c 又因x c x 和 x c c 所以 a x 和 a c 因为a是原子 且a x 所以a必是a1 a2 ak中的一 个 因此 a c 已有 a c 得a c c 即a 0 与a是原子矛盾 x c 0假设不成立 综合 1 和 2 引理得证 三 有限布尔代数的结构三 有限布尔代数的结构 引理引理4 设是一个有限布尔代数 若x是A中任意非零元素 a1 a2 ak是A中满足aj x的所有原子 j 1 2 k 则x a1 a2 ak是 将x表示为原子之并的唯一形式 证明证明 设有另一种表示形式为x b1 b2 bt 其中b1 b2 bt是原子 因 为x是b1 b2 bt的最小上界 所以必有b1 x b2 x bt x 而a1 a2 ak是A中满足ai x i 1 2 k 的所有原子 所以 必有t k且 b1 b2 bt a1 a2 ak 如果t k 那么在a1 a2 ak中必有一ai与b1 b2 bt全不相同 于是由 ai b1 b2 bt ai a1 a2 ak 可得ai 0 这是因为 ai b1 b2 bt 0 ai a1 a2 ak ai 与ai是原子矛盾 t k假设不成立 所以t k 定理得证 三 有限布尔代数的结构三 有限布尔代数的结构 定理定理3 Stone 表示定理表示定理 设 是由有限布尔格所 诱导的一个有限布尔代数 S是布尔格中的所有原子的集合 则和同构 证明证明 本定理的证明过程分两部分本定理的证明过程分两部分 1 构造一个映射构造一个映射 并证明它是双射并证明它是双射 既是单射又是满射既是单射又是满射 2 描述代数系统描述代数系统 证明证明和和同构同构 推论推论1 有限布尔格的元素个数必定等于有限布尔格的元素个数必定等于2n 其中 其中n是该布尔格中所有原是该布尔格中所有原 子的个数 子的个数 推论推论2 任何一个具有任何一个具有2n个元素的有限布尔代数都是同构的 个元素的有限布尔代数都是同构的 三 有限布尔代数的结构三 有限布尔代数的结构 第第 1 部分部分证明 证明 构造函数f A S a A 当a 0时 f 0 当a 1时 f 1 S 当a 0时 f a ai ai S ai a 令S1 ai ai S ai a f满射 一S1 S 令S1 a1 a2 ak 则由于运算 的封闭性 所以 a1 a2 ak a A 这就说明对 S1 S 必存在a A 使得f a S1 f单射 证明 a b A 当a b时有f a f b 等价于证明若f a f b 则a b 令f a f b a1 a2 ak S 由f a a1 a2 ak 知 a a1 a2 ak 由f b a1 a2 ak 知 b a1 a2 ak 所以a b 三 有限布尔代数的结构三 有限布尔代数的结构 第第 2 部分部分证明 证明 证明和同构 即需要 证明 a b A 有f a b f a f b 首先证明首先证明f a b f a f b a 0 b 0时 令a a1 a2 ak b b1 b2 bk x f a b 则x必是满