第十二章 格与布尔代数格与布尔代数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个元的格个元的格 定义（见第定义（见第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，，b∊A，，a∨ ∨b等于等于a和和b的最小上界，的最小上界，a∧ ∧b等于等于a和和b的最大上界的最大上界称（称（A，，∨∨，，∧∧）是由格）是由格(A，，≺ ≺)所定义的代数系统。
所定义的代数系统 注意：二元运算注意：二元运算∨∨通常称为并运算，二元运算通常称为并运算，二元运算∧∧通常通常称为交运算，因此，称为交运算，因此，a和和b的最小上界，也称的最小上界，也称a和和b的并的并；；a和和b的最大下界，也称的最大下界，也称a和和b的交的交 例设设2A是集合是集合A的幂集，（的幂集，（2A，，⊆）是一个格是一个格因此，它确定了一个对应的代数系统：因此，它确定了一个对应的代数系统：（（2A，，∨∨，，∧∧）对于任意的对于任意的x，，y∊A，由定义知，由定义知:x∨ ∨y=x∪y，，x∧ ∧y=x∩y 例设设Z+是正整数集，是正整数集，｜｜是是Z+上一个二元关系，上一个二元关系，（（Z+，，｜｜）是一个格是一个格在格（在格（Z+，，｜｜）所定义的代数系统：）所定义的代数系统：（（Z+，，∨∨，，∧∧））中，对于任意的中，对于任意的m，，n∊ ∊Z+，，m∨ ∨n=m和和n的最小公倍数；的最小公倍数；m∧ ∧n=m和和n的最大公约数的最大公约数 定理1对于格对于格(A，，≺ ≺)中的任意元素中的任意元素a和和b，有：，有：a ≺ ≺ a∨ ∨b (12.1)a∧ ∧b ≺ ≺ a (12.2) 定理2(A，，≺ ≺)是一个格，对于是一个格，对于A中的任意的中的任意的a、、b、、c和和d，，如果如果 a ≺ ≺ b, 且且 c ≺ ≺ d，则有：，则有：a∨ ∨c ≺ ≺ b∨ ∨d (12.3)a∧ ∧c ≺ ≺ b∧ ∧d (12.4) 定理定理3设设(A，，≺ ≺)是一个格，是一个格， （（A，，∨∨，，∧∧）是格）是格(A，，≺ ≺)定义的定义的代数系统，则对于任意的代数系统，则对于任意的a，，b，，c∊A，以下算律成立：，以下算律成立：L1：： a∧ ∧a=a，，a∨ ∨a=a；；（（幂等律幂等律））L2：： a∧ ∧b=b∧ ∧a，，a∨ ∨b=b∨ ∨a；；（（交换律交换律））L3：： (a∧ ∧b)∧ ∧c=a∧ ∧(b∧ ∧c)(a∨ ∨b)∨ ∨c=a∨ ∨(b∨ ∨c)；；（（结合律结合律））L4：： a∧ ∧(a∨ ∨b)=a，，a∨ ∨(a∧ ∧b)=a。
吸收律吸收律）） 第十二章 格与布尔代数格与布尔代数12.1 格定义的代数系统格定义的代数系统12.2 格的代数定义格的代数定义 12.3 一些特殊的格一些特殊的格12.4 有限布尔代数的唯一性有限布尔代数的唯一性12.5 布尔函数和布尔表达式布尔函数和布尔表达式 问题 设（设（A，，∨∨，，∧∧）是具有两个二元运算）是具有两个二元运算∨∨和和∧∧的代数系的代数系统，并且统，并且∨∨和和∧∧运算适合上节定理运算适合上节定理3中描述的四个算律中描述的四个算律L1、、L2、、L3与与L4如何如何设法利用设法利用∨∨和和∧∧运算在运算在A中引入一个偏序关系中引入一个偏序关系≺ ≺，，使使A关于这个偏序关系构成一个格？关于这个偏序关系构成一个格？ 问题问题(续续)问题问题: a∧ ∧b=a和和a∨ ∨b=b是否同时成立？是否同时成立？ 代数系统定义的二元关系代数系统定义的二元关系定义定义: 在集合在集合A上定义二元关系：上定义二元关系： 对于任意对于任意a，，b∊A，若，若 a∧ ∧b=a 成立成立(或或a∨ ∨b=b成立成立) ，， 则定义则定义a≺ ≺b。
验证验证: 所定义的二元关系是偏序关系所定义的二元关系是偏序关系•自反性自反性 •反对称性反对称性 •传递性传递性 所以所以, ≺ ≺是是A上的偏序关系，（上的偏序关系，（A，，≺ ≺）是一个）是一个偏序集 验证验证: 所定义的偏序集是格所定义的偏序集是格首先，证明对于任意的首先，证明对于任意的a，，b∊ ∊A，，a∧ ∧b是是a，，b的的最大下界最大下界可以证明可以证明a∨ ∨b是是a，，b的最小上界的最小上界总之，由代数系统总之，由代数系统(A，，∨∨，，∧∧)定义的偏序集定义的偏序集(A，，≺ ≺)是格 格的等价定义定义定义1：设（：设（A，，∨∨，，∧∧）是一个代数系统，）是一个代数系统，∨∨和和∧∧是是A上的两个封闭的二元运算，且满足算律：上的两个封闭的二元运算，且满足算律：对于任意的对于任意的a，，b，，c∊A，，L1：：a∧ ∧a=a，， a∨ ∨a=a；； （（幂等律幂等律））L2：：a∧ ∧b=b∧ ∧a，， a∨ ∨b=b∨ ∨a；； （（交换律交换律））L3：：(a∧ ∧b)∧ ∧c=a∧ ∧(b∧ ∧c) (a∨ ∨b)∨ ∨c=a∨ ∨(b∨ ∨c)；； （（结合律结合律））L4：：a∧ ∧(a∨ ∨b)=a，， a∨ ∨(a∧ ∧b)=a。
（（吸收律吸收律））则说（则说（A，，∨∨，，∧∧）是一个格是一个格 例例1 (Z+，，∨∨，，∧∧)= (Z+，，|)Z+是正整数集，对于任意的是正整数集，对于任意的a，，b ∊ Z+，规定，规定a∧ ∧b=(a，，b)（即（即a和和b的最大公约数），的最大公约数），a∨ ∨b=[a，，b]（即（即a和和b的最小公倍数）．的最小公倍数）．a∨ ∨b和和a∧ ∧b是是Z+上的两个二元运算上的两个二元运算可以证明：可以证明：(Z+，，∨∨，，∧∧)是一个格是一个格, 且与格且与格(Z+，，|)是一致的是一致的 第十二章 格与布尔代数格与布尔代数12.1 格定义的代数系统格定义的代数系统12.2 格的代数定义格的代数定义 12.3 一些特殊的格一些特殊的格12.4 有限布尔代数的唯一性有限布尔代数的唯一性12.5 布尔函数和布尔表达式布尔函数和布尔表达式 分配格分配格定义定义1 设设(A，，∨∨，，∧∧)是一个格，是一个格， 若对于任意若对于任意a，，b，，c∊A，有，有a∧ ∧(b∨ ∨c)= (a∧ ∧b)∨ ∨(a∧ ∧c)a∨ ∨(b∧ ∧c)= (a∨ ∨b)∧ ∧(a∨ ∨c) 则称则称(A，，∨∨，，∧∧)是一个分配格。
是一个分配格例例 (2A，，∪，，∩)是一个分配格是一个分配格 泛下界、泛上界定义定义2 设设(A，，≺ ≺)是一个格，是一个格，若存在若存在a∊A，对于任意，对于任意b∊A，，a ≺ ≺ b，，则称则称a为为泛下界泛下界；；若存在若存在e∊A，对于任意，对于任意b∊A，，b ≺ ≺ e，，则称则称e为为泛上界泛上界显然，泛上界和泛下界若存在必唯一用显然，泛上界和泛下界若存在必唯一用0和和1分别表分别表示一个格的泛下界和泛上界示一个格的泛下界和泛上界 例在左图中，在左图中，a是泛下界，是泛下界，b是泛上界是泛上界dcbaedbac在右图中，在右图中，a是泛下界，是泛下界，e是泛上界是泛上界 例格格(2A，，∪，，∩)中，中，A是泛上界，而是泛上界，而Ø是泛下界是泛下界A={1,2,3}{1,2}{1,3}{2,3}{1}{2}{3}Ø 例在格在格(Z+，，| )中，中，1是泛下界，没有泛上界是泛下界，没有泛上界 补元、有补格设设(A，，≺ ≺)是一个格，是一个格，0，，1 ∊ ∊A设设a∊ ∊A ，若存在，若存在b∊ ∊A ，满足，满足 a∨ ∨b=1，，a∧ ∧b=0，，则称则称b为为a的的补元补元。
一个格，如果每一个元素都有补元，则称它为一个格，如果每一个元素都有补元，则称它为有补格有补格注意，若注意，若a是是b的补，那么的补，那么b也是也是a的补 定理３定理３(分配格的必要条件分配格的必要条件)在分配格中，如果一个元素有补元，那么这个补元是唯在分配格中，如果一个元素有补元，那么这个补元是唯一的 布尔格、补运算布尔格、补运算定义定义：：一个有补的分配格也称为布尔格一个有补的分配格也称为布尔格设设(A，，≺ ≺)是一个布尔格，因为对于每一个元素有唯一是一个布尔格，因为对于每一个元素有唯一的补元，能定义的补元，能定义A上的一个一元运算，并用上的一个一元运算，并用“ “ ‾ ”表表示，称之为示，称之为补运算补运算 这样，对于这样，对于A中的每一个元素中的每一个元素a，，a是是a的补元 布尔代数(Boolean Algebra)定义：定义： 称一个布尔格称一个布尔格(A，，≺ ≺) 所定义代数系统定义代数系统 (A，，∨∨，，∧∧，， ‾ ) 是一个是一个布尔代数布尔代数 布尔代数的例子布尔代数的例子D={1,2,3,5,6,10,15,30}(D, |)30610152351 布尔代数的例子布尔代数的例子S=2{1,2,3}(S, ⊆){1,2,3}{1,2}{1,3}{2,3}{1}{2}{3}Ø 德德·摩根律摩根律(A,∨ ∨,∧ ∧, ‾)是一个布尔代数。
对于任意的是一个布尔代数对于任意的a，，b∊ ∊A，有，有a∨ ∨b= a∧ ∧ba∧ ∧b= a∨ ∨b 第十二章 格与布尔代数格与布尔代数12.1 格定义的代数系统格定义的代数系统12.2 格的代数定义格的代数定义 12.3 一些特殊的格一些特殊的格12.4 有限布尔代数的唯一性有限布尔代数的唯一性12.5 布尔函数和布尔表达式布尔函数和布尔表达式 布尔代数布尔代数(ρ(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元函数元函数f(0,0,0)0(0,0,1)0(0,1,0)1(0,1,1)0(1,0,0)1(1,0,1)1(1,1,0)0(1,1,1)1(a)表表12.1 布尔表达式(Boolean Expression)定义：设定义：设(A，，∨∨，，∧∧，，‾)是一个布尔代数，其上的是一个布尔代数，其上的一个布尔表达式是如下的表达式一个布尔表达式是如下的表达式：：(1) A中的每个元素是一个布尔表达式。
中的每个元素是一个布尔表达式2) 任意的一个变任意的一个变元元名是一个布尔表达式名是一个布尔表达式3) 如果如果e1和和e2是两个布尔表达式，那么，是两个布尔表达式，那么，e1，，e1∨ ∨e2，，e1∧ ∧e2都是布尔表达式都是布尔表达式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) ？？是否从是否从A An n到到A A的每一个函数的每一个函数f f都可以用都可以用(A(A，，∨∨，，∧∧，，‾) )上上的一个布尔表达式来表示？的一个布尔表达式来表示？问题的答案是否定的问题的答案是否定的! 例例 {0,1,2,3}上的上的 一个一个2元函数。
元函数f(0,0)1(0,1)0(0,2)0(0,3)3(1,0)1(1,1)1(1,2)0(1,3)3(2,0)2(2,1)0(2,2)1(2,3)1(3,0)3(3,1)0(3,2)0(3,3)2函数函数f就不存在就不存在布尔表达式布尔表达式 布尔函数(Boolean Function)定义定义 (A，，∨∨，，∧∧，，‾)是一个布尔代数从是一个布尔代数从An到到A的的一个函数，如果它能由（一个函数，如果它能由（n个变元的）的布尔表个变元的）的布尔表达式来表示，则称它为达式来表示，则称它为布尔函数布尔函数二元素布尔代数二元素布尔代数({0,1}，，∨∨，，∧∧，，‾) 上的一个任意上的一个任意n元元函数，都是布尔函数函数，都是布尔函数。