下载文档原格式
第十章格和布尔代数习题10.1 1．解 ⑴不是，因为L 中的元素对{2,3}没有最小上界；⑵是，因为L=｛1,2,3,4,6,9,12,18,36｝任何一对元素a ,b ，都有最小上界和最大下界；⑶是，与⑵同理；⑷不是，因为L 中的元素对{6,7}没有最小上界不存在最小上界。
2．证明 ⑴因为，a ≤b,所以，a ∨b=b ；又因为，b ≤c,所以，b ∧c=b 。
故a ∨b=b ∧c ；⑵因为，a ≤b ≤c,所以，a ∧b=a,b ∧c=b,而a ∨b=b ，因此，(a ∧b )∨(b ∧c )=b ；又a ∨b=b,b ∨c=c,而b ∧c=b, 因此，(a ∨b )∧(b ∨c )=b 。
即(a ∧b)∨(b ∧c)=(a ∨b)∧(b ∨c)。
习题10.21．解 由图1知：＜S 1,≤＞不是＜L,≤＞的子格，这是因为，e ∨f=g ∉S 1;＜S 2,≤＞不是＜L,≤＞的子格， ∵e ∧f=c ∉S 2;＜S 3,≤＞是＜L,≤＞的子格.2．解 S 24的包含5个元素的子格有如下的8个：S 1={1,3,6,12,24}, S 2={1,2,6,12,24}, S 3={1,2,4,12,24}, S 4={1,2,4,8,24},S 5={1,2,3,6,12}, S 6={1,2,4,6,12}, S 7={2,4,6,12,24}, S 7={2,4,8,12,24}.3．证明 因为，一条线上的任何两个元素都有（偏序）关系，所以，都有最大下界和最小上界，故它是格，又因为它是<L ，∨,∧>的子集，即是<L ，∨,∧>的子代数，故是子格。
4．证明 由(10-4)有，a ∧b ≤a ,由已知a ≤c ,由偏序关系的传递性有，a ∧b ≤c ；同理 a ∧b ≤d 。
由(10-5)和以上两式有，a ∧b ≤c ∧d .5．证明 因为由(10-4)有，a ∧b ≤a ，因此，(a ∧b )∨(c ∧d )≤a ∨(c ∧d ) ①由分配不等式有，a ∨(c ∧d )≤(a ∨c )∧(a ∨d ) ②再由由(10-4)有，(a ∨c )∧(a ∨d ) ≤a ∨c ③由偏序关系的传递性和①②③则有，(a ∧b )∨(c ∧d )≤a ∨c同理 (a ∧b )∨(c ∧d )≤b ∨d因此有， (a ∧b )∨(c ∧d )≤(a ∨c ) ∧(b ∨d )。
第十三章格与布尔代数13.1 格的定义与性质一、格作为偏序集的定义1．格的定义定义13.1设<S,>是偏序集,如果x,y S,{x,y}都有最小上界和最大下界,则称S 关于偏序作成一个格。
由于最小上界和最大下界的唯一性,可以把求{x,y}的最小上界和最大下界看成x与y的二元运算∨和∧,即求x∨y和x∧y分别表示x与y的最小上界和最大下界。
这里要说明一点，本章中出现的∨和∧符号只代表格中的运算，而不再有其它的含义。
2．格的实例例13.1设n是正整数,S n是n的正因子的集合。
D为整除关系,则偏序集<S n,D>构成格。
x,y∈S n,x∨y是lcm(x,y),即x与y的最小公倍数。
x∧y是gcd(x,y),即x与y的最大公约数。
图13.1给出了格<S8,D>，<S6,D>和<S30,D>.图13.1例13.2 判断下列偏序集是否构成格,并说明理由。
(1) <P(B),>,其中P(B)是集合B的幂集。
(2) <Z,≤>,其中Z是整数集,≤为小于或等于关系。
(3) 偏序集的哈斯图分别在图13.2中给出。
二．格的性质1．对偶原理定义13.2设f是含有格中元素以及符号=,,,∨和∧的命题。
令f*是将f中的替换成,替换成,∨替换成∧,∧替换成∨所得到的命题。
称f*为f的对偶命题。
例如,在格中令f是(a∨b)∧c c, 则f*是(a∧b)∨c c .格的对偶原理设f是含有格中元素以及符号=,,,∨和∧等的命题。
若f对一切格为真,则f的对偶命题f*也对一切格为真。
例如,对一切格L都有a,b∈L,a∧b a那么对一切格L都有a,b∈L,a∨b a许多格的性质都是互为对偶命题的。
有了格的对偶原理,在证明格的性质时,只须证明其中的一个命题就可以了。
2. 运算性质定理13.1设<L,>是格,则运算∨和∧适合交换律、结合律、幂等律和吸收律,即(1) a,b ∈L 有a∨b=b∨a, a∧b=b∧a(2) a,b,c∈L 有(a∨b)∨c=a∨(b∨c), (a∧b)∧c=a∧(b∧c)(3) a∈L 有a∨a=a, a∧a=a(4) a,b∈L 有a∨(a∧b)=a, a∧(a∨b)=a证(1)a∨b和b∨a分别是{a,b}和{b,a}的最小上界。
离散数学--⼗⼀章格与布尔代数格的定义与性质:布尔代数是计算机逻辑设计的基础，它是由格引出的。
格⼜是从偏序集引出的。
所以我们先回顾⼀下偏序集中的⼀些概念。
偏序集简单来说就是集合A中有⾃反，反⾃反，传递的关系具体可以看第七章我们结合Hasse图看如下关系：假如 A={1,2,3,6,12,24,36} 且有如下关系如果：B={2，3，6}最⼤|⼩元定义：y是B的最⼩元⇔∃y∈B∧∀x(x∈B→y≤x)y是B的最⼤元⇔∃y∈B∧∀x(x∈B→x≤y)最⼤|⼩元是唯⼀的（类⽐函数的最值）⽽极⼤|⼩元不唯⼀B最⼤元6 ，最⼩元⽆B中Hasse图的最底（顶）层，且这⼀层只有⼀个点才能是最⼩（⼤）元极⼤|⼩元定义：y是B的极⼩元⇔∃y∈B∧¬∃x(x∈B∧x≤y)y是B的极⼤元⇔∃y∈B∧¬∃x(x∈B∧y≤x)这⾥⾯B的极⼩元是 {2，3}，极⼤元是 {6}B中Hasse图的最底（顶）层，则是极⼩（⼤）元上下界定义：y是B的下界⇔∃y∈A∧∀x(x∈B→y≤x)y是B的上界⇔∃y∈A∧∀x(x∈B→x≤y)⽐如 B上界 {12，24，36} 下界 {1}Hasse图中B的最底（顶）层，包括这⼀层和这⼀层下⾯（上⾯）的所有元素构成的集合则是下（上）界确界定义：B的上确界（最⼩上界）下确界（最⼤下界）就是上界的min，下界的max结合Hasse 图理解若B={2，3，6} 有如上图的关系格讲这么多终于到格的定义了其实只要⼀个偏序集中任意⼦集都有上下确界就是格了莫名很简洁暗⽰判断格要疯狂枚举格诱导的代数系统交并运算设<A, ≤>是格,在A上定义⼆元运算∨和∧为:∀a,b∈Aa∨b=LUB {a,b} |{a,b}的最⼩上界.Least Upper Bounda∧b=GLB {a,b} |{a,b}的最⼤下界.Greatest Lower Bound称<A,∨,∧>是由格<A,≤>诱导的代数系统. (∨-并,∧-交)就是⽤符号定义了上下确界⽽已并且有：设<L, ≼>是格则有运算∨和∧适合交换律、结合律、幂等律和吸收律<==> 设<S, ∗, ◦ >是代数系统, ∗和◦是⼆元运算, 如果∗和◦满⾜交换律、结合律和吸收律, 则<S, ∗,◦>构成格.注意⼀下吸收率就好了：a∨(a∧b) = a, a∧(a∨b) = a各种格分配格如果交并还满⾜分配率就叫分配格有界格如果B是A时仍有上下确界则此时的格为有界格，这个确界分别称为全上|下界⼀般将全上界记为1 ，全下界记为0，⼀般将有界格L记为<L,∧,∨,0,1>.有限格L={a1,a2,…,an}是有界格, 则a1∧a2∧…∧an是L的全下界, a1∨a2∨…∨an是L的全上界.0是关于∧运算的零元,∨运算的单位元；1是关于∨运算的零元,∧运算的单位元.有补格有补元的格称为有补格a∧b = 0 和 a∨b = 1成⽴, 则称b是a的补元在任何有界格中, 全下界0与全上界1互补对于⼀般元素, 可能存在补元, 也可能不存在补元. 如果存在补元, 可能是惟⼀的, 也可能是多个补元.对于有界分配格, 如果元素存在补元, ⼀定是惟⼀的⼦群格没有特别懂对⼀个群先找出它的所有⼦群⽐如Z12 <0>,<1>,<2>,<3> ,<6>就是所有⼦群|也满⾜格的定义？也是⼦格然后再画所有⼦群（⼦格）的Hasse图就⾏了布尔代数本质上就是⼀个集合如果⼀个格是有补分配格, 则称它为布尔格或布尔代数. 布尔代数标记为<B,∧,∨,′, 0, 1>, ′为求补运算这⾥⾯的 ' 的运算规律相当于 ‘否’(a' )' =a∀a,b∈B, (a∧b)′ = a′∨b′, (a∨b) ′= a′∧b′(0∧b)∨(a∧0) = 0∨0 = 0(1∨b′)∧(a′∨1) = 1∧1 = 1(a∧b)∧(a′∨b′) = (a∧b∧a′)∨(a∧b∧b′)注意⼀下：Sn代表 n的因⼦所构成的集合|别到时候不知道⽐如 s6={1，2，3，6}。
