第十二章格与布尔代数.ppt

第十二章 格与布尔代数,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，)是一个格。,例,右上图所示的偏序集(D(30)，R)是格。（详见练习7.33),例 右下图所示的偏序集(1,2,3,4,)不是格。（详见第85页例1）,由格定义的代数系统,设(A，)是一个格，定义代数系统（A，）,其中和是A上的两个二元运算，对于任意的a，bA，ab等于a和b的最小上界，ab等于a和b的最大上界。称（A，）是由格(A，)所定义的代数系统。,注意：二元运算通常称为并运算，二元运算通常称为交运算，因此，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(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。如何设法利用和运算在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上的两个封闭的二元运算，且满足算律：对于任意的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 有限布尔代数的唯一性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是泛上界。,在右图中，a是泛下界，e是泛上界。,例,格(2A，)中，A是泛上界，而是泛下界。,例,在格(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),定义：称一个布尔格(A，)所定义代数系统(A，)是一个布尔代数。,布尔代数的例子,D=1,2,3,5,6,10,15,30(D,|),布尔代数的例子,S=21,2,3(S,),德摩根律,(A,)是一个布尔代数。对于任意的a，bA，有ab=abab=ab,第十二章 格与布尔代数,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元函数,(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都可以用(A，)上的一个布尔表达式来表示？,问题的答案是否定的!,例 0,1,2,3上的 一个2元函数。,函数f就不存在布尔表达式。,布尔函数(Boolean Function),定义(A，)是一个布尔代数。从An到A的一个函数，如果它能由（n个变元的）的布尔表达式来表示，则称它为布尔函数。,二元素布尔代数(0,1，)上的一个任意n元函数，都是布尔函数。,