《第十二章格与布尔代数.ppt》由会员分享，可在线阅读，更多相关《第十二章格与布尔代数.ppt（42页珍藏版）》请在三一文库上搜索。
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，)来表示。,格,例 如图用哈斯图给出了一个
2、有5个元的格。,定义（见第86页定义2）A是一个非空集，(A，)是一个偏序集，若对于任意的元素a和b属于A，在A中存在a和b的最小上界及最大下界，就说(A，)是一个格。,例,右上图所示的偏序集 (D(30)，R)是格。 （详见练习7.33),例 右下图所示的偏序集 (1, 2, 3, 4, )不是格。 （详见第85页例1）,由格定义的代数系统,设(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
4、b, 且 c d，则有： ac bd (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，）是具有两个二元运
5、算和的代数系统，并且和运算适合上节定理3中描述的四个算律L1、L2、L3与L4。 如何设法利用和运算在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，)定
6、义的偏序集(A，)是格。,格的等价定义,定义1：设（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。 （吸收律） 则说（A，）是一个格。,例1 (Z+，)= (Z+，|),Z+是正整数集，对于任意的a，b Z+，规定 ab=(a，b)（即a和b的最大公约数）， ab=a，b（即a和b的最小公倍数） ab和ab是Z+上的两个二元运算 可以证明： (Z+
7、，)是一个格, 且与格(Z+，|)是一致的。,第十二章 格与布尔代数,12.1 格定义的代数系统 12.2 格的代数定义 12.3 一些特殊的格 12.4 有限布尔代数的唯一性 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分
8、别表示一个格的泛下界和泛上界。,例,在左图中，a是泛下界，b是泛上界。,在右图中，a是泛下界，e是泛上界。,例,格(2A，)中，A是泛上界，而是泛下界。,例,在格(Z+，| )中，1是泛下界，没有泛上界。,补元、有补格,设(A，)是一个格，0，1 A。 设aA ，若存在bA ，满足 ab=1，ab=0， 则称b为a的补元。 一个格，如果每一个元素都有补元，则称它为有补格。,注意，若a是b的补，那么b也是a的补。,定理(分配格的必要条件),在分配格中，如果一个元素有补元，那么这个补元是唯一的。,布尔格、补运算,定义：一个有补的分配格也称为布尔格。 设(A，)是一个布尔格，因为对于每一个元素有唯一
9、的补元，能定义A上的一个一元运算，并用“ ”表示，称之为补运算。 这样，对于A中的每一个元素a，a是a的补元。,布尔代数(Boolean Algebra),定义： 称一个布尔格(A，) 所定义代数系统 (A， ) 是一个布尔代数。,布尔代数的例子,D=1,2,3,5,6,10,15,30 (D, |),布尔代数的例子,S=21,2,3 (S, ),德摩根律,(A, )是一个布尔代数。对于任意的a，bA，有 ab= ab ab= ab,第十二章 格与布尔代数,12.1 格定义的代数系统 12.2 格的代数定义 12.3 一些特殊的格 12.4 有限布尔代数的唯一性 12.5 布尔函数和布尔表达式
10、,布尔代数(S)，),S是一个任意的集合，2S是S的幂集合， (2S，)是一个格，且是布尔格，记为布尔代数 (S)，)。 问题： 是否所有的布尔代数都是这样的形式呢？ 当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,布尔表达式(Boo
11、lean 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都可以用(A，)上的一个布尔表达式来表示？,问题的答案是否定的!,例 0,1,2,3上的 一个2元函数。,函数f就不存在 布尔表达式。,布尔函数(Boolean Function),定义 (A，)是一个布尔代数。从An到A的一个函数，如果它能由（n个变元的）的布尔表达式来表示，则称它为布尔函数。,二元素布尔代数(0,1，) 上的一个任意n元函数，都是布尔函数。,