当前位置：文档之家› 代数结构-布尔代数与格

代数结构-布尔代数与格

第七章格与布尔代数

第七章格与布尔代数 1. 说明什么叫格？ 2. 给定偏序集、、如下图所示，其中哪些不是格？为什么？ 3下面图哪些是格？对于不是格的，要说明原因。 4. 填空：是平凡格，当且仅当 ( ). 5.证明全序都是格。 6. 填空：设是格, 是由格诱导的代数系统。其中∨与∧是在A 上定义二元运算。: a,b ∈A 则 a ∨b 表示（）。 q (a) (b) (c) (d) ３２ 5 15 6 4 1 2 3

a ∧ b 表示（）。 7. 说明什么叫子格？ 8. 给定偏序集、、如下图所示，其中哪些不是格的子格？为什么？ 9.设是一个格,任取a,b ∈A,a也是格. 10.具有一、二、三个元素的格各有几种不同构形式？请分别请画出它们的哈斯图。 11.具有四个元素的格有几种不同构形式？请分别请画出它们的哈斯图。 12具有五个元素的格有几种不同构形式？请分别请画出它们的哈斯图。 13. 证明格中下面式子成立： (a ∧b)∨(c ∧d)≤(a ∨c)∧(b ∨d) a a c a

14. 请说出什么叫分配格？ 15. 指出判定一个格是分配格的充分且必要条件是在该格中没有任何子格与两个五元素非分配格之一同构。请画出这两个五元素非分配格。 16. 下面具有五个元素的格中，哪些是分配格？ 17.具有五个元素的格中，有几个不是分配格？请画出这些非分配格的图。 18. 验证下面格不是分配格。 19. 验证下面格不是分配格。 a b c d e

离散数学代数结构作业部分答案

第四章代数结构（作业）作业：P86：4、7、9 4、（1）若a和b是整数，则a+b+ab也是整数，故a*b也是整数，所以运算*是封闭的。（2）任选整数集合中的三个元素x,y和z。则有： (x*y)*z = (x+y+xy)*z = (x+y+xy)+z+(x+y+xy)×z = x+y+z+xy+xz+yz+xyz x*(y*z) = x*(y+z+yz) = x+(y+z+yz)+x×(y+z+yz) = x+y+z+yz+xy+xz+xyz = (x*y)*z 因此，*运算满足结合律。（3）假设e为（Z,*）的幺元，则有：任选整数集中的一个元素x，都有 0*x = 0+x+0×x=x且 x*0 = x+0+x×0=x 故0是(Z,*)的幺元。 7、N+上的所有元素都是（N+ ,*）等幂元；（N+ ,*）无幺元；（N+ ,*）的零元为1。 9、（A,*）中的等幂元：a、b、c、d；（A,*）中的幺元：b；（A,*）中的零元：c； a-1 = d，b-1 = b，c-1 不存在，d-1 = a，作业：P87：12、13、18 12、（A，*）到（N4,⊕4）的同构映射f为： f(a)=0, f(b)=1, f(c)=2, f(d)=3; 或者： f(a)=0, f(b)=3, f(c)=2, f(d)=1; 13、同构映射f为： f(0)=?, f(1)={a}, f(2)={b}, f(3)={a,b};

或者： f(0)=?, f(1)={b}, f(2)={a}, f(3)={a,b}; 18、任选a ∈N +,b ∈N +, 只需证明f(a+b)=f(a)+f(b) 由f 的定义可知：f(a+b)=2a+2b=f(a)+f(b)，故f 是（N +,+）到(E +,+)的同态映射。作业：P96：3，P97：7 3、(1)显然，*运算对Z 是封闭的。 (2) (a*b)*c = (3(a+b+2)+ab)*c = 3((3(a+b+2)+ab)+c+2)+(3(a+b+2)+ab)×c = 3(3a+3b+c+ab+8+ac+bc+2c)+abc = 3(3a+3b+3c+ab+ac+bc+8)+abc a*(b*c) = a*(3(b+c+2)+bc) = 3(a+(3(b+c+2)+bc)+2)+a(3(b+c+2)+bc) = 3(a+3b+3c+bc+8+ab+ac+2a)+abc = 3(3a+3b+3c+ab+ac+bc+8)+abc = (a*b)*c 故*运算满足结合律。（3）任选a ∈Z ，(-2)*a=a 且a*(-2)=a ，所以-2是(Z,*)的幺元。所以（Z,*）是独异点。 7、因为1为(A,*)运算的幺元，而且对任意A 的子集A ’,*在A ’上都是封闭和可结合的运算，因此，（A,*）的所有子独异点为(A ’,*)，其中A ’必须包含1。即：(A,*)的所有子独异点为： ({1},*),({1,2},*),({1,3},*),({1,4},*),({1,2,3},*),({1,2,4},*),({1,3,4},*),({1,2,3,4},*) P105：3、4、13 3、??????1100b a ×??????220 0b a ＝??? ?? ?212100b b a a ,a 1,a 2∈{1,-1}, 所以a 1×a 2∈{1,-1}，b 1×b 2∈{1,-1}。故（G,×）是封闭的。而 (??????1100b a ×??????2200b a )×??????3300b a =??????212 100b b a a ×????? ?3300b a =??????3213 2100b b b a a a ??????1100b a ×(????? ?22 00b a ×??????3300b a )=??????1100b a ×??????323 200b b a a =??????3213210 0b b b a a a 故（G,×）是可结合的。（也可以说因为矩阵乘法是可结合的。）

格与布尔代数

一、格的引入在上一章中讨论过偏序集与偏序关系时,已经把格定义为一种特殊的偏序集。下面, 先回顾一下几个有关概念。设是偏序集合, B 是A 的子集, 若任意 b∈B,b≤a,则a 是子集B 的上界。若a′也是B 的上界, 有a≤a′,也即a是B的上界集合的最小元，这时称a 是子集B 的最小上界, 记为lub(B)；类似地，若任意b∈B,a≤b,则a是B 的下界。若a′也是B 的下界, 有a′ ≤a, 称a 是子集B 的最大下界, 记为glb(B)。由最大元、最小元的唯一性可知，最大下界、最小上界若存在, 则唯一。此外, 若b ≤a 且b≠a, 则可用b是一个偏序集, 如果A 中任意两个元素均有最小上界和最大下界, 那么就说A 关于偏序“≤”作成一个格(Lattice), 有时直接称A 为格。当一个格A 中的元素是有限时, 称格A 是个有限格。对于一个有限格来说, A 中的偏序关系可以通过偏序集A 的哈斯图表示, 这个图也称为格A 的次序图。例子 1) 偏序集, 对于任意 S1, S2∈P(U), S1, S2?U, 有S1?S1∪S2,S2?S1∪S2, 并且若有子集S?U, 使得S1?S, S2?S, 必有S1∪S2?S。因此, 对于任意 S1, S2∈P(U), lub(S1, S2)=S1∪S2；同理可得, 对于任意 S1, S2∈P(U), glb(S1, S2)=S1∩S2, 于是是一个格。 2) 设n 是一个正整数, S n 是n 的所有因子的集合。例如, 当n=30 时, S30={1, 2, 3, 5, 6, 10, 15, 30}。设“|”是整除关系, 则由偏序集的哈斯图易知它是格。类似地, 也容易判断, , 也是格。其实, 对于偏序关系“|”, S n 中子集{i,j} 的最小上界就是i, j 的最小公倍数, 最大下界就是i,j 的最大公因数。 3) 设P 是所有的命题集合, “→”为蕴涵关系, 则对任意P1, P2∈P, glb(P1, P2)=P1 ∧P2,lub(P1, P2)=P1∨P2, 因此是一个格。注意, 如果偏序集是格, 则任意两个元素a、b 在格内存在唯一的最小上界和最

§8.5 逻辑代数公式化简习题2 - 2017-9-10

第8章 §8.5 逻辑代数公式化简习题2 1 第8章 §8.5 逻辑代数公式化简习题2 （一）考核内容 1、第8章掌握逻辑运算和逻辑门；掌握复合逻辑运算和复合逻辑门；掌握逻辑函数的表示方法；掌握逻辑代数的基本定理和常用公式；掌握逻辑函数的化简方法。 8.6 逻辑函数的化简 8.6. 1 化简的意义 1、所谓化简就是使逻辑函数中所包含的乘积项最少，而且每个乘积项所包含的变量因子最少，从而得到逻辑函数的最简与–或逻辑表达式。逻辑函数化简通常有以下两种方法：（1）公式化简法又称代数法，利用逻辑代数公式进行化简。它可以化简任意逻辑函数，但取决于经验、技巧、洞察力和对公式的熟练程度。（2）卡诺图法又称图解法。卡诺图化简比较直观、方便，但对于5变量以上的逻辑函数就失去直观性。 2、逻辑函数的最简形式同一逻辑关系的逻辑函数不是唯一的，它可以有几种不同表达式，异或、与或、与或非—非、与非—与非、或与非、与或非、或非—或非。一个逻辑函数的表达式可以有与或表达式、或与表达式、与非-与非表达式、或非-或非表达式、与或非表达式5种表示形式。（1）与或表达式：AC B A Y += （2）或与表达式：Y ))((C A B A ++= （3）与非-与非表达式：Y AC B ?= （4）或非-或非表达式：Y C A B A +++= （5）与或非表达式：Y C A B A += 3、公式化简法（1）、并项法：利用公式A B A AB =+，把两个乘积项合并起来，消去一个变量。例题1： B B A A B =+= （2）、吸收法：利用公式 A A B A =+，吸收掉多余的乘积项。例题2：E B D A AB Y ++= B A E B D A B A +=+++= （3）、消去法：利用公式B A B A A +=+，消去乘积项中多余的因子。例题3：AC AB Y += C B A A C B A ++=++= （4）、配项消项法：利用公式C A AB BC C A AB +=++，在函数与或表达式中加上多余的项— —冗余项，以消去更多的乘积项，从而获得最简与或式。例题4： B A C AB ABC Y ++=

离散数学结构习题5

习题5 1．设个体域D={a,b,c}，消去下列各式的量词： (1) x y(F(x)∧G(y)) (2) x y(F(x)∨G(y)) (3) xF(x)→yG(y) (4) x(F(x,y)→yG(y)) 答案 (1) x y(F(x)∧G(y)) xF(x)∧yG(y) (F(a)∧F(b))∧F(c))∧(G(a)∨G(b)∨G(c)) (2) x y(F(x)∨G(y)) xF(x)∨yG(y) (F(a)∧F(b)∧F(c))∨(G(a)∧G(b)∧G(c)) (3) xF(x)→yG(y) (F(a)∧F(b)∧F(c))→(G(a)∧G(b)∧G(c)) (4) x(F(x,y)→yG(y)) xF(x,y)→yG(y) (F(a,y)∨F(b,y)∨F(c,y))→(G(a)∨G(b)∨G(c)) 2．设个体域D={1,2}，请给出两种不同的解释I1和I2，使得下面公式在I1下都是真命题，而在I2下都是假命题。 (1) x(F(x)→G(x)) (2) x(F(x)∧G(x)) .(1) 答案 I1: F(x):x≤2,G(x):x≤3 F(1),F(2),G(1),G(2)均为真，所以 x(F(x)→G(x)) (F(1)→G(1)∧(F(2)→G(2))为真。 I2: F(x)同I1,G(x):x≤0 则F(1),F(2)均为真，而G(1),G(2)均为假， x(F(x)→G(x))为假。 (2)留给读者自己做。 3．给定解释I如下： (a) 个体域D={3,4}。 (b) (x)为(3)=4，(4)=3。 (c) (x,y)为(3,3)=(4,4)=0，(3,4)=(4,3)=1。答案试求下列公式在I下的真值： (1) x yF(x,y) (2) x yF(x,y)

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

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

倒例如：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 ∈A 1∧f (x)=y)}?B 所以B 1∈2B ，故此S ?2B ；又B 0=f (A)∈S (因为A ∈2A )，所以S 非空；对于任何B 1，B 2∈S ，存在着A 1，A 2∈2A ，使得B 1=f (A 1)，B 2=f (A 2)，从而 L ∪B{B 1，B 2}=B 1∪B 2=f (A 1)f (A 2) =f (A 1∪A 2) （习题三的8的1））由于A 1∪A 2?A ，即A 1∪A 2∈2A ，因此f (A 1∪A 2)∈S ，即上确界L ∪B{B 1，B 2}存在。对于任何B 1，B 2∈S ，定义A 1=f –1 (B 1)={x|x ∈A ∧f (x)∈B 1}，A 2=f -1 (B 2)={x|x ∈A ∧f (x)∈B 2}，则A 1，A 2∈2A ，且显然B 1=f (A 1)，B 2=f (A 2)，于是 GLB{B 1，B 2}=B 1∩B 2=f (A 1)∩f (A 2) ?f (A 1∩A 2) （习题三的8的2））又若y ∈B 1∩B 2，则y ∈B ，且y ∈B 2。由于y ∈B 1=f (A 1)={y|y ∈B ∧(x)(x ∈A 1∧f (x)=y)}，于是存在着x ∈A 1，使f (x)=y ，但是f (x)=y ∈B 2。故此x ∈A 2=f -1 (B 2)={x|x ∈A ∧f(x)∈B 2}，因此x ∈A 1∩A 2，从而y=f (x)∈f (A 1∩A 2)，所以 GLB{B 1，B 2}=B 1∩B 2=f (A 1)∩f (A 2) ?f (A 1∩A 2) 9 7 31

格与布尔代数试题

、选择题(每小题2分，共30分) 1、N 是自然数集，是小于等于关系, 则 N, 是(C )。 (A)有界格 (B) 有补格 (C)分配格 (D) 2、在有界格中，若只有一个元素有补元, 有补分配格则补元( C ) (A)必唯 (B) 不唯 (C)不一定唯 (D) 可能唯 3、 F 面是一些偏序集的哈斯图，判断哪一个为格( C ) d c e e e c D A C B D ) (A)分配格 (B)有补格 (C)布尔格 (D) 有界格 6设L,是一条链，其中L -3，贝U L, ( C ) (A)不是格 (B) 是有补格 5、只含有有限个元素的格称为有限格, 有限格必是(

(C)是分配格 (D) 是布尔格 7、设A 为一个集合， P(A), 为有补格，P(A)中每个元素的补元(A ) (A) 存在且唯一 (B) 不存在 (C)存在但不唯一 (D)可能存在 8、设代是一个有界格，若它也是有补格，只要满足( B ) (A)每个元素都有一个补元 (B)每个元素都至少有一个补元 9、如下哈斯图(C )表示的关系构成有补格。 (C)每个元素都无补元 (D)每个元素都有多个补元 10、如图给出的哈斯图表示的格中( (A)a (C)e (D) f 11、设格 B, 2如图所示，它们的运算分别为和，。令 f(a) X !, f(b) X 2, f (c) X 4, f (d) X 8，则 f ( B ) B )元素无补元。 d g c

(A)是格同态映射 (B)不是格同态映射系。贝U 30的补元为 (B) 30 (D) 70 f (a) 2 f(b)是格同构的( (B)充分条件 ,其中定义为：对于n 1 , n 2 L, n 1 n 2 当且仅当n 1是n 2的因子。问其中哪几个偏序集是格(说明理由)。(共6 分) a)、L {1,2,3,4,6,12} b)、L {1,2,3,4,6,8,12,14} C)、L {1,2,3,4,5,6,7,8,9,10,11,12} 、图中为格L 所对应的哈斯图。(共10分) (C) 是格同构映射 (D) 是自同态映射 (A) 2n (B) (C) 2n (D) 4n 13、在布尔格 A, 中有3个原子a 1,a 2,a 3则6 ( B ) (A) a 2 a 3 (B) a 2 a 3 (C) a 2 a 3 (D) a 2 a 3 14、在布尔格代中, A {X | X 是5的整数倍且是210的正因子} , |为整除关 (A)15 (C)35 15、设A, 1和 B, 2 是两个格, f 是A 到B 的双射，则对任意的a,b A ，有 (A)必要条件 (C)充要条件 (D)既不充分也不必要、由下列集合L 构成的偏序集 L,

离散数学结构试题集5-7

离散数学12格和布尔代数

第十二章格和布尔代数 12.1 设c b a ,,是格),( A 中的元素，求证：如果b a ，则)()(c a b c b a ∨∧∧∨ 证明因为b a ，且)(c a a ∨ ，所以)(c a b a ∨∧ 。又因为b c b ∧，且c a c c b ∨∧ ，所以)(c a b c b ∨∧∧ 。即)(c a b ∨∧是a 和c b ∧的上界，从而有： )()(c a b c b a ∨∧∧∨ 。 12.2 设c b a ,,是格),( A 中的元素，求证：（1）)()()(c a b a c b a ∨∧∨∧∨ （2）)( )()(c b a c a b a ∨∧∧∨∧ (1)证明因为c a a b a a ∨∨ ,，所以)()(c a b a a ∨∧∨ 。又因为b a b c b ∨∧ ，且c a c c b ∨∧ ，所以)()(c a b a c b ∨∧∨∧ 。即)()(c a b a ∨∧∨是a 和c b ∧的上界。所以，)()()(c a b a c b a ∨∧∨∧∨ 。（2）证明因为a b a ∧，a c a ∧，则有a c a b a )()(∧∨∧。又因为b b a ∧，有c b b b a ∨∧ ，同理c b c a ∨∧ 。从而有c b c a b a ∨∧∨∧ )()(。即)()(c a b a ∧∨∧是a 和c b ∨的下界。因此，)( )()(c b a c a b a ∨∧∧∨∧ 。 10.3 设),,(∧∨A 是一个代数系统，其中∨和∧是满足吸收律的二元运算，证明：∨和∧也满足等幂律。证明

因为∨和∧是满足吸收律，所以a b a a =∨∧)(，a b a a =∧∨)(。于是有： )((b a a a a a ∧∨∧=∧ )(c a a ∨∧= （其中b a c ∧=） a = 同理可证，a a a =∨。故∨和∧也满足等幂律。 10.4 证明：一个格是可分配的，当且仅当对于这个格中的任意元素a ，b 和c ，有 )()(c b a c b a ∧∨∧∨ 证明（1）必要性因为a c a ∧和c b c b ∧∧ ，所以)()()(c b a c b c a ∧∨∧∨∧ 。又因为格为分配格，所以)()()(c b c a c b a ∧∨∧=∧∨。因此，)()(c b a c b a ∧∨∧∨ 。（2）充分性因为对于c b a ,,?，有)()(c b a c b a ∧∨∧∨ ，则 )()()(c c b a c b a ∧∧∨=∧∨ （等幂律） c c b a ∧∧∨=))(( （结合律） c c b a ∧∧∨))(( （假设） c a c b ∧∨∧=))(( （交换律） )()(c a c b ∧∨∧ （假设）又因为b a a ∨ ，c c ，所以c b a c a ∧∨∧)( ；同理，c b a c b ∧∨∧)( 因此，c b a c b c a ∧∨∧∨∧)()()( 综上所述，)()()(c b c a c b a ∧∨∧=∧∨ 故该格是可分配的。 10.5 证明一个格),( A 是分配的，当且仅当对A 中的任意元素a ，b 和c ，有 )()()()()()(a c c b b a a c c b b a ∨∧∨∧∨=∧∨∧∨∧

逻辑代数的基本公式和常用公式

逻辑代数的基本公式和常用公式一．基本定义与运算代数是以字母代替数,称因变量为自变量的函数,函数有定义域和值域。——这些都是大家耳熟能详的概念。如或；当自变量的取值（定义域）只有0和1（非0即1）函数的取值也只有0和1（非0即1）两个数——这种代数就是逻辑代数，这种变量就是逻辑变量，这种函数就是逻辑函数。逻辑代数，亦称布尔代数，是英国数学家乔治布尔（George Boole）于1849年创立的。在当时，这种代数纯粹是一种数学游戏，自然没有物理意义，也没有现实意义。在其诞生100多年后才发现其应用和价值。其规定： 1．所有可能出现的数只有0和1两个。 2．基本运算只有“与”、“或”、“非”三种。与运算（逻辑与、逻辑乘）定义为（为与运算符，后用代替） 00＝0 01＝0 10＝0 11＝1 或 00＝0 01＝0 10＝0 11＝1 或运算（逻辑或、逻辑加）定义为（为或运算符，后用＋代替） 00＝0 01＝1 10＝1 11＝1 或 0＋0＝0 0＋1＝1 1＋0＝1 1＋1＝1 非运算（取反）定义为：

至此布尔代数宣告诞生。二、基本公式如果用字母来代替数（字母的取值非0即1），根据布尔定义的三种基本运算，我们马上可推出下列基本公式： A A＝A A+A=A A0＝0 A+0=A A1＝A A+1=1 =+= 上述公式的证明可用穷举法。如果对字母变量所有可能的取值，等式两边始终相等，该公式即告成立。现以=+为例进行证明。对A、B两个逻辑变量，其所有可能的取值为00、01、10、11四种（不可能有第五种情况）列表如下：

由此可知： =+ 成立。用上述方法读者很容易证明：三、常用公式 1．左边＝＝右边 2．左边＝＝右边例题：将下列函数化为最简与或表达式。（公式1：） = (公式2：) （）

离散数学知识点

说明：定义：红色表示。定理性质：橙色表示。公式：蓝色表示。算法:绿色表示页码：灰色表示数理逻辑： 1.命题公式：命题，联结词(，，，，)，合式公式，子公式 2.公式的真值：赋值，求值函数，真值表，等值式，重言式，矛盾式 3.范式：析取范式，极小项，主析取范式，合取范式，极大项，主合取范式 4.联结词的完备集：真值函数，异或，条件否定，与非，或非，联结词完备集 5.推理理论：重言蕴含式，有效结论，P规则，T规则， CP规则，推理 6.谓词与量词:谓词，个体词，论域，全称量词，存在量词 7.项与公式:项，原子公式，合式公式，自由变元，约束变元，辖域，换名，代入 8.公式语义:解释，赋值，有效的，可满足的，不可满足的 9.前束范式:前束范式 10.推理理论:逻辑蕴含式，有效结论，-规则（US），+规则（UG），-规则(ES)， +规则(EG), 推理集合论： 1.集合: 集合, 外延性原理, , , , 空集, 全集, 幂集, 文氏图, 交, 并, 差, 补, 对称差 2.关系: 序偶, 笛卡尔积, 关系, domR, ranR, 关系图, 空关系, 全域关系, 恒等关系 3.关系性质与闭包:自反的, 反自反的, 对称的, 反对称的, 传递的,自反闭包 r(R), 对称闭包 s(R), 传递闭包 t(R) 4.等价关系: 等价关系, 等价类, 商集, 划分

5.偏序关系:偏序, 哈斯图, 全序(线序), 极大元/极小元, 最大元/最小元, 上界/下界 6.函数: 函数, 常函数, 恒等函数, 满射,入射,双射，反函数, 复合函数 7.集合基数:基数, 等势, 有限集/无限集, 可数集, 不可数集代数结构： 1.运算及其性质：运算，封闭的,可交换的,可结合的,可分配的,吸收律, 幂等的，幺元,零元,逆元 2.代数系统：代数系统，子代数，积代数，同态，同构。 3.群与子群：半群,子半群,元素的幂，独异点，群，群的阶数，子群,平凡子群，陪集，拉格朗日（Lagrange）定理 4.阿贝尔群和循环群：阿贝尔群(交换群)，循环群,生成元 5.环与域：环，交换环，含幺环，整环，域 6.格与布尔代数：格，对偶原理，子格，分配格，有界格，有补格，布尔代数，有限布尔代数的表示定理图论： 1.图的基本概念：无向图、有向图、关联与相邻、简单图、完全图、正则图、子图、补图，握手定理，图的同构 2.图的连通性:通路，回路，简单通路，简单回路（迹）初级通路（路径），初级回路（圈），点连通，连通图，点割集，割点，边割集，割边，点连通度，边连通度，弱连通图，单向连通图，强连通图，二部图（二分图） 3.图的矩阵表示：关联矩阵，邻接矩阵，可达矩阵 4.欧拉图与哈密顿图：欧拉通路、欧拉回路、欧拉图、半欧拉图，哈密顿通路、哈密顿回路、哈密顿图、半哈密顿图 5.无向树与根树：无向树，生成树，最小生成树，Kruskal，根树，m叉树，最优二叉树，Huffman算法 6.平面图:平面图，面，欧拉公式，Kuratoski定理

格与布尔代数格与布尔代数万字

第5章：格与布尔代数格与布尔代数是代数系统中的又一类重要代数系统。这两个代数系统与第4章讨论的代数系统之间存在着一个重要的区别：在格与布尔代数中，偏序关系具有重要的意义。为了强调偏序关系的作用，我们将分别从偏序关系和代数系统两个方面引入格的概念。给格附加一定的限制后，格就转化为布尔代数，即布尔代数是一种特殊的格。布尔代数最初是作为对逻辑思维法则的研究而出现的，创立者是英国哲学家和数学家布尔（G .Boole ）。自布尔之后，许多数学家对布尔代数的一般化作了许多努力，特别是斯通（M.H.Stone ），他的工作可以说是对现代布尔代数的发展开创了一个新阶段。 1938年，香农（C.E.Shannon ）发表了《继电器和开关电路的符号分析》一文，为布尔代数在工艺技术中的应用开创了道路，从而出现了开关代数。为了给开关代数奠定基础，于是自然形成了二值布尔代数，即逻辑代数。自香农之后，人们应用布尔代数对电路作了大量研究，并形成了网络理论。格与布尔代数不仅是代数学的一个分支，而且在近代解析几何、半序空间等方面也都有重要的作用，同时，格与布尔代数在计算机科学中也有十分重要的作用，可直接用于开关理论和逻辑设计、密码学、计算机理论科学等。 §5.1 偏序关系与偏序集 1. 基本概念我们常用关系对集合的某些元素或全体元素进行排序。例如，使用包含着字对>∈<π，X 。 b a π意为b a π且b a ≠，读着“a 严格先于b ” 。π也是集合X 上的关系，并且是反自反的、反对称的和传递的，叫做X 上的半序。显然，如果π是偏序，则X I -π为半序π，

离散数学结构习题13

习题13参考答案 1.图13.9中给出六个偏序集的哈斯图。判断其中哪些是格。如果不是格,说明理由。图13.9 答案：(1),(3),(6)是格。(2)中的{e,d}没有最大下界。(4)中的{d,e}没有最大下界。(5)中的{a,b}没有最大下界。 2.下列各集合对于整除关系都构成偏序集,判断哪些偏序集是格。 (1) L={1,2,3,4,5} (2) L={1,2,3,6,12} (3) L={1,2,3,4,6,9,12,18,36} (4) L={1,2,22,...,2n},n∈Z+ 答案：(1)不是格,其他都是。

3.(1)画出Klein四元群的子群格。 (2)画出模12的整数群Z12的子群格。 (3)画出3元对称群S3的子群格。答案：(1) (2) (3) 4.设L是格,求以下公式的对偶式: (1) a∧(a∨b) a (2) a∨(b∧c)(a∨b)∧(a∨c) (3) b∨(c∧a)(b∨c)∧a 答案：(1) a∨(a∧b) a (2) a∧(b∨c)(a∧b)∨(a∧c) (3) b∧(c∨a)(b∧c)∨a

5.设L是格,a,b,c∈L,且a b c,证明 a∨b=b∧c 答案：a∨b=b b∧c=b 6.针对图13.10中的格L1,L2和L3,求出他们的所有子格。图13.10 答案： L1的子格：{a},{b},{c},{d},{a,b},{a,c},{a,d}, {b,d},{c,d},{a,b,d},{a,c,d},L1 L2的子格：{a1},{d1},L2 L3的子格：{a2},{b2},{c2},{d2},{a2,b2},{a2,c2}, {a2,d2},{b2,c2},{b2,d2},{c2,d2},{a2,b2,c2}, {a2,b2,d2},{a2,c2,d2},{b2,c2,d2},L3 7.针对图13.9中的每个格,如果格中的元素存在补元,则求出这些补元。答案：（1）a与d互补；b,c没有补元。（3）a与f互补；b的补元为c,d；c的补元为b,e；d的补元为b,e；e的补元为c,d. （6）a与f互补；b的补元为e；c和d没有补元；e的补元为b. 8.说明图13.9中的每个格是否为分配格、有补格和布尔格,并说明理由。答案：（1）是分配格，因为不包含与钻石格和五角格同构的子格；不是有补格和布尔格，b,c没有补元。（3）不是分配格，不是布尔格，因为包含五角格作为子格；是有补格，a与f互补，b和e的补元有c,d；c,d的补元有b,e. （6）是分配格，因为没有5元子格与钻石格或五角格同构；不是有

离散数学结构习题8

习题8 1. 设f：N→N，且求f(0)，f({0})，f(1)，f({1})，f({0，2，4，6，…})，f({4，6，8})，f({1，3，5，7})。 2. 设A={1，2}，B={a，b，c}，求B A。 3.给定函数f和集合A，B如下： (1) f：R→R，f(x)=x，A={8}，B={4} (2) f：R→R+，f(x)=2x，A={1}，B={1，2} (3) f：N→N×N，f(x)=} (4) f：N→N，f(x)=2x+1，A={2，3}，B={1，3} (5) f：Z→N，f(x)=|x|，A={-1，2}，B={1} (6) f：S→S，S=[0，1]，f(x)=x/2+1/4，A=(0，1)，B=[1/4，1/2] (7) f：S→R，S=[0，+∞]，f(x)=1/(x+1)，A={0，1/2}，B={1/2} (8) f：S→R+，S=(0，1)，f(x)=1/x，A=S，B={2，3}。对以上每一组f和A，B，分别回答以下问题： (a) f是不是满射，单射和双射的?如果f是双射的，求f的反函数。 (b)求A在f下的像f(A)和B在f下的完全原像f-1(B)。 4.判断下列函数中那些是满射的？哪些是单射的？哪些是双射的？ (1) f：N→N，f(x)=x2+2 (2) f：N→N，f(x)=(x)mod 3，x除以3的余数。 (3) f：N→N， (4) f：N→{0，1}， (5) f：N-{0}→R，f(x)=log10x (6) f：R→R，f(x)=x2-2x-15 5.设A={1，2，3，4}，A1={1，2}，A2={1}，A3=，求A1，A2，A3和A的特征函数A1， A2，A3和A。 6.设A={a，b，c}。R为A上的等价关系，且 R={<a，b>，}∪I A 求自然映射g：A→A/R。 7．设f，g，h∈R R，且 f(x)=x+3，g(x)=2x+1，h(x)= 求f g，g f，f f，g g，h f，g h，f h，g h f。 8．设f，g，h∈N N，且有

第七章格与布尔代数

离散数学结构习题D

习题13 1.图13.9中给出六个偏序集的哈斯图。判断其中哪些是格。如果不是格,说明理由。图13.9 答案：(1),(3),(6)是格。(2)中的{e,d}没有最大下界。(4)中的{d,e}没有最大下界。(5)中的{a,b}没有最大下界。 2.下列各集合对于整除关系都构成偏序集,判断哪些偏序集是格。 (1) L={1,2,3,4,5} (2) L={1,2,3,6,12} (3) L={1,2,3,4,6,9,12,18,36} (4) L={1,2,22,...,2n},n∈Z+ 答案：(1)不是格,其他都是。

答案：a∨b=b b∧c=b 6.针对图13.10中的格L1,L2和L3,求出他们的所有子格。图13.10 答案： L1的子格：{a},{b},{c},{d},{a,b},{a,c},{a,d}, {b,d},{c,d},{a,b,d},{a,c,d},L1 L2的子格：{a1},{d1},L2 L3的子格：{a2},{b2},{c2},{d2},{a2,b2},{a2,c2}, {a2,d2},{b2,c2},{b2,d2},{c2,d2},{a2,b2,c2}, {a2,b2,d2},{a2,c2,d2},{b2,c2,d2},L3 7.针对图13.9中的每个格,如果格中的元素存在补元,则求出这些补元。答案：（1）a与d互补；b,c没有补元。（3）a与f互补；b的补元为c,d；c的补元为b,e；d的补元为b,e；e的补元为c,d. （6）a与f互补；b的补元为e；c和d没有补元；e的补元为b. 8.说明图13.9中的每个格是否为分配格、有补格和布尔格,并说明理由。答案：（1）是分配格，因为不包含与钻石格和五角格同构的子格；不是有补格和布尔格，b,c没有补元。（3）不是分配格，不是布尔格，因为包含五角格作为子格；是有补格，a与f互补，b和e 的补元有c,d；c,d的补元有b,e. （6）是分配格，因为没有5元子格与钻石格或五角格同构；不是有补格，也不是布尔格，因为c和d没有补元。 9.对以下各小题给定的集合和运算判断它们是哪一类代数系统(半群,独异点,群,环,域,格,布尔代数),并说明理由。 (1) S1={0，1,-1}，运算为普通加法和乘法。 (2) S2={a1,a2,...,a n},a i,a j∈S2,a i*a j=a i.这里的n是给定的正整数,且n≥2. (3) S3={0,1},*为普通乘法。 (4) S4={1,2,5,7,10,14,35,70},和*分别表示求最小公倍数和最大公约数运算。 (5) S5={0,1,2},*为模3加法,为模3乘法。答案：（1）不是代数系统，对于加法不封闭。（2）半群，运算封闭，有结合律，没有单位元。（3）半群与独异点，乘法封闭，有结合律，单位元是1，但是0没有逆元。（4）格与布尔代数。两个运算满足交换、相互分配、同一律、补元律。（5）环与域，{0,1,2}关于模3加构成交换群、{1,2}关于模3乘构成交换群，模3乘关于模3加有分配律。

相关主题

 离散数学格与布尔代数

离散数学代数结构部分

格与布尔代数

离散数学结构

逻辑代数的基本定律

逻辑代数的基本公式

文本预览

相关文档

离散数学12格和布尔代数

离散数学格与布尔代数

离散数学课件_7 格与布尔代数

离散数学第11章格与布尔代数

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

最新离散数学第十五章格与布尔代数简

离散数学格与布尔代数

格与布尔代数(离散数学)

离散数学格与布尔代数优秀课件

离散数学格与布尔代数

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

离散数学习题解答第五章格与布尔代数.doc

离散数学格与布尔代数(精选)

离散数学第十五章格与布尔代数(简)

离散数学格与布尔代数ppt课件

离散数学chap6格与布尔代数

离散数学格与布尔代数

离散数学第09章格和布尔代数

最新文档

幼儿园小班科学《小动物过冬》PPT课件教案

2021年春新青岛版(五四制)科学四年级下册 20.《露和霜》教学课件

自然教育课件

小学语文优质课火烧云教材分析及课件

(超详)高中语文知识点归纳汇总

高中语文基础知识点总结(5篇)

高中语文基础知识点总结(最新)

高中语文知识点整理总结

高中语文知识点归纳

高中语文基础知识点总结大全

超详细的高中语文知识点归纳

高考语文知识点总结高中

高中语文知识点总结归纳

高中语文知识点整理总结

高中语文知识点归纳

高中语文知识点归纳(大全)

高中语文知识点总结归纳(汇总8篇)

高中语文基础知识点整理

化工厂应急预案

化工消防应急预案(精选8篇)