3~离散数学习题解答(第五章)格与布尔代数5

106离散数学习题解答习题五（第五章格与布尔代数）1．设〈L，≼〉是半序集，≼是L上的整除关系。问当L取下列集合时，〈L，≼〉是否是格。a)L={1，2，3，4，6，12}b)L={1，2，3，4，6，8，12}c)L={1，2，3，4，5，6，8，9，10}[解]a)〈L，≼〉是格，因为L中任两个元素都有上、下确界。b)〈L，≼〉不是格。因为L中存在着两个元素没有上确界。例如：812=LUB{8，12}不存在。c)〈L，≼〉不是格。因为L中存在着两个元素没有上确界。12631248631241210107倒例如：46=LUB{4，6}不存在。2．设A，B是两个集合，f是从A到B的映射。证明：〈S，⊆〉是〈2B，⊆〉的子格。其中S={y|y=f(x)，x∈2A}[证]对于任何B1∈S，存在着A1∈2A，使B1=f（A1），由于f(A1)={y|y∈B∧(x)(x∈A1∧f(x)=y)}⊆B所以B1∈2B，故此S⊆2B；又B0=f(A)∈S(因为A∈2A)，所以S非空；对于任何B1，B2∈S，存在着A1，A2∈2A，使得B1=f(A1)，B2=f(A2)，从而L∪B{B1，B2}=B1∪B2=f(A1)f(A2)=f(A1∪A2)（习题三的8的1））由于A1∪A2⊆A，即A1∪A2∈2A，因此f(A1∪A2)∈S，即上确界L∪B{B1，B2}存在。对于任何B1，B2∈S，定义A1=f–1(B1)={x|x∈A∧f(x)∈B1}，A2=f-1(B2)={x|x∈A∧f(x)∈B2}，则A1，A2∈2A，且显然B1=f(A1)，B2=f(A2)，于是GLB{B1，B2}=B1∩B2=f(A1)∩f(A2)⊇f(A1∩A2)（习题三的8的2））又若y∈B1∩B2，则y∈B，且y∈B2。由于y∈B1=f(A1)={y|y∈B∧(x)(x∈A1∧f(x)=y)}，于是存在着x∈A1，使f(x)=y，但是f(x)=y∈B2。故此x∈A2=f-1(B2)={x|x∈A∧f(x)∈B2}，因此x∈A1∩A2，从而y=f(x)∈f(A1∩A2)，所以GLB{B1，B2}=B1∩B2=f(A1)∩f(A2)⊆f(A1∩A2)这说明GLB{B1，B2}=B1∩B2=f(A1)∩f(A2)=f(A1∩A2)于是从A1∩A2∈2A可知f(A1∩A2)∈S，即下确界GLB{B1，B2}存在。因此，〈S，⊆〉是〈2B，⊆〉的子格。3．设〈L，≼〉是格，任取a，b∈L且a≼b。证明〈B，≼〉是格。其中842698731510108B={x|x∈L且a≼x≼b}[证]显然B⊆L；根据自反性及a≼b≼b所以a，b∈B，故此B非空；对于任何x，y∈B，则有a≼x≼b及a≼y≼b，由于x，y∈L，故有z1=xy为下确界∈L存在。我们只需证明z1，z2∈B即可，证明方法有二，方法一为：由于a≼x，所以ax=x，于是z1=xy=(ax)y（利用ax=x）=a(xy)（由运算结合律）因此a≼z1；另一方面，由y≼b可知yb=b，由x≼b可知xb=b，于是z1b=(xy)b=x(yb)（由运算结合律）=xb（利用yb=b）=b（利用xb=b）因此z1≼b，即a≼z1≼b所以z1∈B由于a≼x及a≼y，所以a*x=a，a*y=a，因而a*z2=a*(x*y)=(a*x)*y（由*运算结合律）=a*y（利用a*x=a）=a（利用a*y=a）因而a≼z2；又由于y≼b，所以y*b=y于是z2=x*y=x*(y*b)=(x*y)*b（利用*运算结合律）=z2*b从而z2≼b，即a≼z2≼b所以z2∈B因此〈B，≼〉是格（是格〈L，≼〉的子格）。方法二：根据上、下确界性质，由a≼x，a≼y，可得a≼x*y，（见附页数）4．设〈L，≼，*，〉是格。a，b∈L，证明：（附页）a≼x≼y，即a≼z2，a≼又由x≼b，y≼b，可得xy≼b，x*y≼y≼b，即z1≼b，z2≼b109所以a≼z1≼b，a≼z2≼b，故此z1，z2∈Ba*b≺a且a*b≺ba与b是不可比较的。[证]先证用反证法，假设a与b是可比较的，于是有a≼b或者b≼a。当a≼b时，a*b=a与a*b≺a（得a*b≠a）矛盾；当b≼a时，a*b=b与a*b≺b（得a*b≠b）矛盾；因此假设错误，a与b是不可比较的。次证由于a*b≼a，a*b≼b。如果a*b≼a，则a≼b，与a和b不可比较的已知条件矛盾，所以a*b≠a，故此a*b≺a；如果a*b=b，则b≼a，也与a和b不可比较的已知条件矛盾，所以a*b≠b，故此可得a*b≺b。5．设〈L，≼，*，〉是格。证明：a)(a*b)(c*d)≼(ac)*(bd)b)(a*b)(b*c)≼(ca)≼(ab)*(bc)*(ca)[证]a)方法一，根据上、下确界的性质，由a*b≼a≼ac及a*b≼b≼bd所以得到a*b≼(ac)*(bd)又由c*d≼c≼ac及c*d≼d≼bd，所以得到c*d≼(ac)*(bd)因此(a*b)(c*d)≼(ac)*(bd)方法二(a*b)(c*d)≼[(ac)*(ad)]*[(ac)*(bd)]（分配不等式，交换律，结合律，保序性）≼(ac)*(bd)（保序性）b)方法一，根据上、下确界的性质由a*b≼a≼ab，a*b≼b≼bc，a*b≼a≼ca可得a*b≼(ab)*(bc)*(ca)同理可得b*c≼(ab)*(bc)*(ca)及c*a≼(ab)*(bc)*(ca)所以(ab)(bc)(ca)≼(ab)*(bc)*(ca)方法二：(ab)(bc)(ca)110≼[b*(ac)](c*a)（交换律，结合律，分配不等式，保序性）≼[b(c*a)]*[(ac)(c*a)]（分配不等式，交换律，）≼[(ab)*(bc)]*(ac)（分配不等式，结合律，交换律，吸收律，保序性）≼(ab)*(bc)*(ca)（结合律）6．设I是整数集合。证明：〈I，min，max〉是分配格。[证]由于整数集合I是全序集，所以任何两个整数的最小者和最大者是存在的，因此〈I，min，max〉是格是显然的。下面我们来证〈I，min，max〉满足分配律对于任何a，b，c∈I有a*(bc)=min{a，max{b，c}}(a*b)(a*c)=min{min{a，b}，min{a，c}}（1）若b≤c时，当（a）a≤b，则a≤c，故此min{a，max{b，c}}=min{a，c}=amax{min{a，b}，min{a，c}}=max{a，a}=a（b）b≤a≤c，则min{a，max{b，c}}=min{a，c}=amax{min{a，b}，min{a，c}}=max{b，a}=a（c）c≤a，则b≤a，因此min{a，max{b，c}}=min{a，c}=cmax{min{a，b}，min{a，c}}=max{b，a}=c（2）若c≤b时，当（a）a≤c，则a≤b，故此min{a，max{b，c}}=min{a，b}max{min{a，b}，min{a，c}}=min{a，a}=a（b）c≤a≤b，则min{a，max{b，c}}=min{a，b}=amax{min{a，b}，min{a，c}}=max{a，c}=a（c）b≤a，则c≤a，因此min{a，max{b，c}}=min{a，b}=bmax{min{a，b}}，min{a，c}}=max{b，c}=b综合（1）（2）总有a*(bc)=(ab)*(ac)111根据对偶原理，就还有a(b*c)=(ab)*(ac)因此〈I，min，max〉是分配格。7．设〈A，*，，max〉是分配格，a，b∈A且a≼b。证明：f(x)=(xa)*b是从A到B的同态函数。其它B={x|x∈A且a≼x≼b}[证]由于a≼xa，及已知a≼b，所以a≼(xa)*b；其次(xa)*b≼b，所以a≼f(x)≼b，因而f(x)是从A到B的函数。对于任何x，y∈A，f(xy)=((xy)a)*b=((xa)(ya))*b（幂等律，交换律，结合律）=((x*a)b)((ya)*b)（分配律）=f(x)f(y)f(x*y)=((x*y)a)*b=((xa)*(ya))*b（分配律）=((xa)*b)((ya)*b)（幂等律，交换律，结合律）=f(x)*f(y)所以，f满足同态公式，因而f是从A到B的同态函数。8．证明：一个格是分配格的充分必要条件是a，b，c∈L，有(a*b)(b*c)(c*a)=(ab)*(bc)*(ca)[证]必要性。对于任何a，b，c∈L，(a*b)(b*c)(c*a)=(b*(ac))(c*a)（交换律，分配律）=(b(c*a))*((ac)(c*a))（分配律）=(bc)*(ba)*(ac)（分配律，吸收律）=(ab)*(bc)*(ca)（交换律）充分性，f满足同态公式，因而f是从A到B的同态函数。8．证明：一个格是分配格的充分必要条件是a，b，c∈L，有(a*b)(b*c)(c*a)=(ab)*(bc)*(ca)[证]必要性。对于任何a，b，c∈L，(a*b)(b*c)(c*a)=(b*(ac))(c*a)（交换，分配律）112=(b(c*a))((ac)(c*a))（分配律）=(bc)*(ba)*(ac)（分配律，吸收律）=(ab)*(bc)*(ca)（交换律）充分性，对于任何a，b，c∈La(b*c)=(a(a*c))(b*c)（吸收律）=((a(a*b))(a*c))(b*c)（吸收律）=(a*b)(b*c)(c*a)a（交换律，结合律）=((ab)*(bc)*(ca))a（已知条件）=((ab)*(ac)*(bc))((bc)*a)a（交换律，吸收律）=((ab)*(ac)*(bc))((bc)*a)(a*(ab)*(ac))（吸收律）=(((ab)*(ac))(bc))*((bc)a)*(a((ab))*(ac)))（已知条件）=(((ab)*(ac))(bc))*(abc)*((ab)*(ac))（因为a((ab)*(ac))=(ab)*(ac)=(((ab)*(ac))(bc))*(((ab)c)*(ab)*(ac)（结合律）=(((ab)*(ac))(bc))*((ab)*(ac))（吸收律，结合律）=(ab)*(ac)（吸收律）根据对偶原理还有a*(bc)=(ab)*(ac)所以格L是分配格。9．设〈L，≼〉是格。其Hasse图如右a)找出格中每个元素的补元；b)此格是有补格吗？c)此格是分配格吗？[解]a)最小元0=i；最大元1=a；故此格为有界格。a和i互为补元；f和C互为补元；其余b，d，e，g，h等都没有补元。b)根据a)可知，此格不是有补格。c)此格不是分配格，因为f(g*h)=fi=f(fg)*(fh)=b*d=d因为去掉g结点后所形成的子格与分配格〈S24，I，GCD，LCM，1，24〉同构，因此若此格不是分配格，则必有子格cehabdfig113h*(fg)=h*b=h(h*f)(h*g)=ii=I〈S24，I，GCD，LCM，1，24〉两个不是分配格的特殊格与两个不是分配格的特殊格同构，并且此子格必含有g点。而特殊不分配格之图或是含有五个结点的圈，或是有六个结点：gebdfi；gebdhi；gehdfi；或是有八个结：gecabdfi；gecabdhi；或是只有一个四结点的圈：gehi。因此此格绝不会有含g点的子格与两个不是分配格的特殊格同构。10．设〈L，≼，*，〉是有界格。x，y∈L，证明：a)若xy=0，则x=0且y=0。b