格与布尔代数试题

第十章格和布尔代数习题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 )。

《离散数学》题库答案一、选择或填空（数理逻辑部分）1、下列哪些公式为永真蕴含式？( )(1)⌝Q=>Q →P (2)⌝Q=>P →Q (3)P=>P →Q (4)⌝P ∧(P ∨Q)=>⌝P答：（1），（4）2、下列公式中哪些是永真式？( )(1)(┐P ∧Q)→(Q →⌝R) (2)P →(Q →Q) (3)(P ∧Q)→P (4)P →(P ∨Q)答：（2），（3），（4）3、设有下列公式，请问哪几个是永真蕴涵式?( )(1)P=>P ∧Q (2) P ∧Q=>P (3) P ∧Q=>P ∨Q(4)P ∧(P →Q)=>Q (5) ⌝(P →Q)=>P (6) ⌝P ∧(P ∨Q)=>⌝P答：（2），（3），（4），（5），（6）4、公式∀x((A(x)→B(y ，x))∧ ∃z C(y ，z))→D(x)中，自由变元是( )，约束变元是( )。

答：x,y, x,z5、判断下列语句是不是命题。

若是，给出命题的真值。

( )(1) 北京是中华人民共和国的首都。

(2) 陕西师大是一座工厂。

(3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。

(5) 前进！ (6) 给我一杯水吧！答：（1） 是，T （2） 是，F （3） 不是（4） 是，T （5） 不是 （6） 不是6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是()。

答：所有人都不是大学生，有些人不会死7、设P ：我生病，Q ：我去学校，则下列命题可符号化为( )。

(1) 只有在生病时，我才不去学校 (2) 若我生病，则我不去学校(3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校答：（1） P Q →⌝ （2） Q P ⌝→ （3） Q P ⌝↔ （4）Q P →⌝8、设个体域为整数集，则下列公式的意义是( )。

(1) ∀x ∃y(x+y=0) (2) ∃y ∀x(x+y=0)答：（1）对任一整数x 存在整数 y 满足x+y=0（2）存在整数y 对任一整数x 满足x+y=09、设全体域D 是正整数集合，确定下列命题的真值：(1) ∀x ∃y (xy=y) ( ) (2) ∃x ∀y(x+y=y) ( )(3) ∃x ∀y(x+y=x) ( ) (4) ∀x ∃y(y=2x) ( )答：（1） F （2） F （3）F （4）T10、设谓词P(x)：x 是奇数，Q(x)：x 是偶数，谓词公式 ∃x(P(x)∨Q(x))在哪个个体域中为真?() (1) 自然数 (2) 实数 (3) 复数 (4) (1)--(3)均成立答：（1）11、命题“2是偶数或-3是负数”的否定是（ ）。

湖北大学研究生课程考试参考答案及评分标准一、概念题参考答案及评分标准：1.设2F 是二元有限域，n 为正整数，n F 2是2F 上的n 维向量空间，从n F 2到2F 的映射：22:F F f n →称为n 元布尔函数.一个n 元布尔函数f 可以表示为2F 上的含n 个变元的多项式:∑∈++++++=2)1()1)(1)(,,(),,(22112121F a n n nn i a x a xa x a a a f x x x f ΛK Kn i an aaF a n x x x a a a f ΛK 2122121),,(∑∈=.这里()11ni i i x a =++∏表示2F 中的加法运算，即模2的加法运算.形如上式的表示称为布尔函数f 的小项表示.若将小项表示展开并合并同类项，则会得到如下形式的一个多项式：n n nj i i i i i nj i j ij i ni i i n x x a x x ax x ax a a x x x f d dK ΛΛΛK K ΛK 1,11,1,102111),,(+++++=∑∑∑≤<<≤≤<≤=这里系数∈j i a K ,2F .评分标准：答出n 元布尔函数的定义得5分，答出其多项式表示得5分.2布尔函数的安全性指标主要有：平衡性、代数次数、差分均匀度、非线性度、相关免疫阶、弹性阶和代数免疫度等等.平衡性：一个n 元布尔函数是平衡的，当且仅当其真值表中0和1的个数相同，也就是该布尔函数的Hamming 重量为12n -.代数次数：密码体制中使用的布尔函数通常具有高的代数次数. 差分均匀度：设是一个n 元布尔函数，其差分均匀度定义为2220max max {|()()}n n f F a F x F f x a f x βδβ∈≠∈=∈+-=.非线性度：f 的非线性度()NL f 定义为f 和所有仿射函数的最小Hamming 距离：()min (,)min ()nnl A l A NL f d f l wt f l ∈∈==-.相关免疫阶：设是一个n 元布尔函数，其中是上独立且均匀分布的随机变量，如果与中任意个变元统计独立，则称是m 阶相关免疫函数。

离散数学习题解答习题五（第五章 格与布尔代数）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 中存在着两个元素没有上确界。

例如：812=LUB{8，12}不存在。

126312 4c) 〈L ，≼〉不是格。

因为L 中存在着两个元素没有上确界。

倒例如：46=LUB{4，6}不存在。

2．设A ，B 是两个集合，f 是从A 到B 的映射。

证明：〈S ，⊆〉是〈2B，⊆〉的子格。

其中S={y|y=f (x)，x ∈2A }[证] 对于任何B 1∈S ，存在着A 1∈2A ，使B 1=f （A 1），由于f(A 1)={y|y ∈B ∧(x)(x 863 124 12 10 84 2 6 973 1 5 10∈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。

第五章习题几个典型的代数系统.设A={0,1},试给出半群<A A,>的运算表,其中为函数的复合运算。

.设G={a+bi|a,b∈Z},i为虚数单位,即i2=-1.验证G关于复数加法构成群。

.设Z为整数集合,在Z上定义二元运算如下：x,y∈Z,x y=x+y-2问Z关于运算能否构成群为什么.设A={x|x∈R∧x≠0,1}.在A上定义六个函数如下：f 1(x)=x,f2(x)=x-1,f3(x)=1-x,f 4(x)=(1-x)-1,f5(x)=(x-1)x-1, f6(x)=x(x-1)-1令F为这六个函数构成的集合,运算为函数的复合运算。

(1) 给出运算的运算表。

(2) 验证<F,>是一个群。

.设G为群,且存在a∈G,使得 G={a k|k∈Z}, 证明G是交换群。

.证明群中运算满足消去律..设G为群,若x∈G有x2=e,证明G为交换群。

.设G为群,证明e为G中唯一的幂等元。

.证明4阶群必含2阶元。

设A={a+bi|a,b∈Z,i2=-1},证明A关于复数的加法和乘法构成环,称为高斯整数环。

.(1) 设R1,R2是环,证明R1与R2的直积R1×R2也是环。

(2) 若R1和R2为交换环和含幺环,证明R1×R2也是交换环和含幺环。

. 判断下列集合和给定运算是否构成环、整环和域,如果不能构成,说明理由。

(1) A={a+bi|a,b∈Z},其中i2=-1,运算为复数的加法和乘法。

(2) A={-1,0,1},运算为普通加法和乘法。

(3) A=M(Z),2阶整数矩阵的集合，运算为矩阵加法和乘法。

2(4) A是非零有理数集合Q*,运算为普通加法和乘法。

.设G是非阿贝尔群,证明G中存在元素a和b,a≠b,且ab=ba..设H是群G的子群,x∈G,令xHx-1={xhx-1|h∈H},证明xHx-1是G的子群,称为H的共轭子群。

.设(1) G上的二元运算为矩阵乘法,给出G的运算表(2) 试找出G的所有子群(3) 证明G的所有子群都是正规子群。

练习8.11．证明在布尔代数中a∨(a’∧b)=a∨b, a∧(a’∨b)=a∧b证明：a∨(a’∧b)=(a∨a’)∧(a∨b) 分配律=1∧(a∨b) 布尔代数的定义=a∨b 布尔代数的定义第二个式子是第一个式子的对偶式，对第一个式子用对偶原理即可得到。

2．证明：(1) (a∨b)∧(c∨d)=(a∧c)∨(b∧c)∨(a∧d)∨(b∧d)(2)(a∧b)∨(c∧d)=(a∨c)∧(b∨c)∧(a∨d)∧(b∨d)并推广到一般情况。

证明：只需证明第一式，用对偶原理即得第二式。

(a∨b)∧(c∨d)=((a∨b)∧c)∨((a∨b)∧d) 分配律=((a∧c)∨(b∧c))∨((a∧d)∨(b∧d)) 分配律= (a∧c)∨(b∧c)∨(a∧d)∨(b∧d) 结合律推广到一般情况：(1) (a1∨a2∨…∨an)∧(b1∨b2∨…∨bn)=(a1∧b1)∨(a1∧b2)∨…∨(a1∧bn)∨(a2∧b1)∨(a2∧b2)∨…∨(a2∧bn)∨…∨(an∧b1)∨(an∧b2)∨…∨(an∧bn)∨(2) (a1∧a2∧…∧an)∨(b1∧b2∧…∧bn)=(a1∨b1)∧(a1∨b2)∧…∧(a1∨bn)∧(a2∨b1)∧(a2∨b2)∧…∧(a2∨bn)∧…∧(an∨b1)∧(an∨b2)∧…∧(an∨bn)3. 证明：(1) (a’∧c’)∨(b∧c)∨(a∧b’)=(a’∧b)∨(a∧c)∨(b’∧c’)证明：左式=(a’∧c’)∨(b∧c)∨(a∧b’)=(((a’∧c’) ∨b) ∧((a’∧c’) ∨c) )∨(a∧b’) 分配律=((a’∨b)∧(c’∨b) ∧(a’∨c)∧(c’∨c))∨(a∧b’)分配律=((a’∨b)∧(c’∨b) ∧(a’∨c))∨(a∧b’)分配律= ((a’∨b)∧(c’∨b) ∧(a’∨c))∨(a∧b’)分配律=(((a’∨b)∧(c’∨b) ∧(a’∨c))∨a)∧(((a’∨b)∧(c’∨b) ∧(a’∨c))∨b’) 分配律= ((a’∨b∨a)∧(c’∨b∨a) ∧(a’∨c∨a))∧((a’∨b∨b’)∧(c’∨b∨b’) ∧(a’∨c∨b’))分配律= (c’∨b∨a)∧(a’∨c∨b’)布尔代数的定义右式=(a’∧b)∨(a∧c)∨(b’∧c’)=(((a’∧b) ∨a)∧((a’∧b)∨ c)))∨(b’∧c’) 分配律=(((a’∨a)∧(b∨a))∧((a’∨ c)∧(b∨ c)))∨(b’∧c’) 分配律=((b∨a)∧(a’∨ c)∧(b∨ c))∨(b’∧c’) 分配律=(((b∨a)∧(a’∨ c)∧(b∨ c))∨b’)∧(((b∨a)∧(a’∨ c)∧(b∨ c))∨c’)) 分配律=(((b∨a∨b’)∧(a’∨ c∨b’)∧(b∨ c∨b’)))∧(((b∨a∨c’)∧(a’∨ c∨c’)∧(b∨ c∨c’)))) 分配律=(a’∨ c∨b’)∧(b∨a∨c’)布尔代数的定义所以，左式=右式，即原式成立。

§4.7 格和布尔代数习题4.71．确定具有如图4.4所示哈斯图的偏序集是否为格。

图4.4 习题1的图解图(a)不是格，图(b)是格，图(c)是格。

2．证明每个有限格都有一个最小元素和一个最大元素。

证明：用反证法，假设某有限格中没有最大元素，只有极大元，则这几个极大元之间没有上确界，与格的定义矛盾，从而有限格中都有最大元素。

同理可证明有最小元素。

3．给出一个无限格的例子，使得（1）既没有最小元素也没有最大元素。

（2）有最小元素但没有最大元素。

（3）有最大元素但没有最小元素。

（4）有最小元素也有最大元素。

解：（1）对于偏序集<R，≤>，既没有最小元素也没有最大元素。

（2）对于偏序集<N，≤>，有最小元素0，但没有最大元素。

（3）对于偏序集<Z-，≤>，有最大元素-1，但没有最小元素。

（4）对于偏序集<[1,2]，≤>，有最大元素2，有最小元素1。

4．给出一个有限格的例子，其中至少1个元素有多于1个的补元，且至少1个元素没有补元。

解如下哈斯图所示的偏序集是一个格，元素e有补元a和d，元素a有补元e和d，元素d有补元a和e，但元素b和c都没有补元。

1bd5．设是有界格，证明：（1）若≥2，则中不存在以自身为补元的元素。

（2）若≥3，且是链（全序集），则不是有补格。

证明：（1） 用反证法，假设L 中存在一个元素a 以自身为补元，所以a -1=a.据有界格的定义，则a ⨁a =a =1，a ⨂a =a =0显然，二者矛盾。

因此若≥2，则中不存在以自身为补元的元素。

（2） 用反证法，假设L 是有补格，则L 中每个元素都是有补元的。

若a 和b 是补格， 则需要满足a ⨁b =1，a ⨂b =0，但是a,b 间不一定可以比较，也就是说不一定是全序集，与条件矛盾。

6．格是分配格吗？试分析之。

解：不是分配格，例如有三个数，c|a,b 与c,a 都不具有整除关系，但是，但，不满足分配律，所以不是分配格。