十二章节格与布尔代数

1、第十二章 格与布尔代数12.1 格定义的代数系统12.2 格的代数定义 12.3 一些特殊的格12.4 有限布尔代数的唯一性12.5 布尔函数和布尔表达式复习：偏序集、格格是一个偏序集，在这个偏序集中，每两个元素有唯一一个最小上界和唯一一个最大下界。定义（见第85页定义1） 设A是一个非空集合， R是A上的一个二元关系，若R有自反性、反对称性、传递性，说R是A上的一个偏序关系。 并称(A，R)是一个偏序集。 注意： 对于一个偏序关系，往往用记号“”来表示。 若(a，b) ，记为a b，读做“ a小于等于b”。 一个偏序集，通常用符号(A，)来表示。格例 如图用哈斯图给出了一个有5个元的格。 定

2、义（见第86页定义2）A是一个非空集，(A，)是一个偏序集，若对于任意的元素a和b属于A，在A中存在a和b的最小上界及最大下界，就说(A，)是一个格。a1a2a4a5a3例30610152351右上图所示的偏序集(D(30)，R)是格。（详见练习7.33)例 右下图所示的偏序集 (1, 2, 3, 4, )不是格。 （详见第85页例1）1234由格定义的代数系统设(A，)是一个格，定义代数系统（A，）, 其中和是A上的两个二元运算， 对于任意的a，bA，ab等于a和b的最小上界，ab等于a和b的最大上界。称（A，）是由格(A，)所定义的代数系统。 注意：二元运算通常称为并运算，二元运算通常称为

3、交运算，因此，a和b的最小上界，也称a和b的并；a和b的最大下界，也称a和b的交。 例设2A是集合A的幂集，（2A，）是一个格。因此，它确定了一个对应的代数系统：（2A，）。对于任意的x，yA，由定义知:xy=xy，xy=xy。例设Z+是正整数集，是Z+上一个二元关系，（Z+，）是一个格。在格（Z+，）所定义的代数系统：（Z+，）中，对于任意的m，nZ+，mn=m和n的最小公倍数；mn=m和n的最大公约数。定理1对于格(A，)中的任意元素a和b，有：a ab (12.1)ab a (12.2)定理2(A，)是一个格，对于A中的任意的a、b、c和d，如果 a b, 且 c d，则有：ac bd

4、(12.3)ac bd (12.4)定理3设(A，)是一个格， （A，）是格(A，)定义的代数系统，则对于任意的a，b，cA，以下算律成立：L1：aa=a，aa=a；（幂等律）L2：ab=ba，ab=ba；（交换律）L3：(ab)c=a(bc)(ab)c=a(bc)；（结合律）L4：a(ab)=a，a(ab)=a。（吸收律）第十二章 格与布尔代数12.1 格定义的代数系统12.2 格的代数定义 12.3 一些特殊的格12.4 有限布尔代数的唯一性12.5 布尔函数和布尔表达式问题 设（A，）是具有两个二元运算和的代数系统，并且和运算适合上节定理3中描述的四个算律L1、L2、L3与L4。如何设法

5、利用和运算在A中引入一个偏序关系，使A关于这个偏序关系构成一个格？问题(续)问题: ab=a和ab=b是否同时成立？代数系统定义的二元关系定义: 在集合A上定义二元关系： 对于任意a，bA，若 ab=a 成立(或ab=b成立) ， 则定义ab。验证: 所定义的二元关系是偏序关系自反性反对称性传递性所以, 是A上的偏序关系，（A，）是一个偏序集。 验证: 所定义的偏序集是格首先，证明对于任意的a，bA，ab是a，b的最大下界。可以证明ab是a，b的最小上界。总之，由代数系统(A，)定义的偏序集(A，)是格。格的等价定义定义1：设（A，）是一个代数系统，和是A上的两个封闭的二元运算，且满足算律：对

6、于任意的a，b，cA，L1：aa=a， aa=a； （幂等律）L2：ab=ba， ab=ba； （交换律）L3：(ab)c=a(bc) (ab)c=a(bc)； （结合律）L4：a(ab)=a， a(ab)=a。 （吸收律）则说（A，）是一个格。例1 (Z+，)= (Z+，|)Z+是正整数集，对于任意的a，b Z+，规定ab=(a，b)（即a和b的最大公约数），ab=a，b（即a和b的最小公倍数）ab和ab是Z+上的两个二元运算可以证明：(Z+，)是一个格, 且与格(Z+，|)是一致的。第十二章 格与布尔代数12.1 格定义的代数系统12.2 格的代数定义 12.3 一些特殊的格12.4 有限

7、布尔代数的唯一性12.5 布尔函数和布尔表达式分配格定义1 设(A，)是一个格， 若对于任意a，b，cA，有a(bc)= (ab)(ac)a(bc)= (ab)(ac) 则称(A，)是一个分配格。例 (2A，)是一个分配格。泛下界、泛上界定义2 设(A，)是一个格，若存在aA，对于任意bA，a b，则称a为泛下界；若存在eA，对于任意bA，b e，则称e为泛上界。显然，泛上界和泛下界若存在必唯一。用0和1分别表示一个格的泛下界和泛上界。例在左图中，a是泛下界，b是泛上界。dcbaedbac在右图中，a是泛下界，e是泛上界。例格(2A，)中，A是泛上界，而是泛下界。A=1,2,31,21,32,

8、3123例在格(Z+，| )中，1是泛下界，没有泛上界。补元、有补格设(A，)是一个格，0，1 A。设aA ，若存在bA ，满足 ab=1，ab=0，则称b为a的补元。一个格，如果每一个元素都有补元，则称它为有补格。注意，若a是b的补，那么b也是a的补。定理(分配格的必要条件)在分配格中，如果一个元素有补元，那么这个补元是唯一的。布尔格、补运算定义：一个有补的分配格也称为布尔格。设(A，)是一个布尔格，因为对于每一个元素有唯一的补元，能定义A上的一个一元运算，并用“ ”表示，称之为补运算。 这样，对于A中的每一个元素a，a是a的补元。布尔代数(Boolean Algebra)定义： 称一个布尔

9、格(A，) 所定义代数系统 (A， ) 是一个布尔代数。 布尔代数的例子D=1,2,3,5,6,10,15,30(D, |)30610152351布尔代数的例子S=21,2,3(S, )1,2,31,21,32,3123德摩根律(A, )是一个布尔代数。对于任意的a，bA，有ab= abab= ab第十二章 格与布尔代数12.1 格定义的代数系统12.2 格的代数定义 12.3 一些特殊的格12.4 有限布尔代数的唯一性12.5 布尔函数和布尔表达式布尔代数(S)，)S是一个任意的集合，2S是S的幂集合，(2S，)是一个格，且是布尔格，记为布尔代数 (S)，)。问题：是否所有的布尔代数都是这样

10、的形式呢？当A是一个有限集，也就是(A，)是一个有限布尔代数时，这一问题的答案是肯定的。第十二章 格与布尔代数12.1 格定义的代数系统12.2 格的代数定义 12.3 一些特殊的格12.4 有限布尔代数的唯一性12.5 布尔函数和布尔表达式问题设(A，)是一个布尔代数，n(1)是一个正整数，如何表示一个An到A的函数(映射)、也就是A上的一个n元函数？例 0,1上的一个3元函数(a)表12.1布尔表达式(Boolean Expression)定义：设(A，)是一个布尔代数，其上的一个布尔表达式是如下的表达式：(1) A中的每个元素是一个布尔表达式。(2) 任意的一个变元名是一个布尔表达式。(3) 如果e1和e2是两个布尔表达式，那么，e1，e1e2，e1e2都是布尔表达式。(4) 所有的布尔表达式都是有限次的运用(1)、(2)、(3)所得。E(x1，x2，xn)一个含有n个不同变元的布尔表达式，通常称为n个变元的布尔表达式。通常用E(x1，x2，xn)表达有n个变元x1，xn的一个布尔表达式。E(x1，x2，xn) n元函数不难看出，一个布尔表达式E(x1，x2，xn) 就表示了一个从An到A的一个函数。问题：n元函数 E(x1，x2，xn) ？是否从An到A的每一个函数f都可以