当前位置：文档之家 › 7格与布尔代数习题

7格与布尔代数习题

  • 格式：pdf
  • 大小：298.92 KB
  • 文档页数：14

下载文档原格式

  / 14

合集下载

格和布尔代数

格和布尔代数
a,bL，若a≤b a∧b = a
分三步： 1) 证明’≤’是L上的偏序关系 2）证明 a,bL, {a,b}的下确界存在， 且 a∧b = glb(a,b)。 3）a,bL, {a,b}的上确界存在，且 lub(a,b) a∨b 具体证法见后面
1) 证明’≤’是L上的偏序关系 自反性：aL 由等幂律 a∧a=a, a≤a 反对称性：a,bL, 若a≤b, b≤a 则 a∧b=a, b∧a=b a = a∧b = b∧a = b 传递性：a,b,cL, 若 a≤b,b≤c 则a∧b=a, b∧c=b a∧c=(a∧b)∧c = a∧(b∧c)= a∧b=a a≤c
2、格的对偶原理
① 集合S的偏序关系≤的逆关系≥也是偏序关 系，若AS, 其中 ≤的glb(A) 对应于 ≥的lub(A), ≤的lub(A) 对应于 ≥的glb(A), 所以，若<S,≤>是格，则<S,≥>也是格， 称这两个格互为对偶。
2、格的对偶原理
② 因为<S,≤>的交是<S,≥>的并， <S,≤>的并是<S,≥>的交，
一般格只满足分配不等式： a∨(b∧c)≤(a∨b)∧(a∨c)
一、定义
设<L,∧,∨>是格，若a,b,cL，有： (1) a∧(b∨c)=(a∧b)∨(a∧c), (2) a∨(b∧c)=(a∨b)∧(a∨c), 则称 <L,∧,∨> 为分配格。
注：(1)(2)是互相等价的，由对偶原理，从一式可推
2）证明 a,bL, {a,b}的下确界存在， 且 a∧b=glb(a,b)。
a) 因为 (a∧b)∧a =(a∧a)∧b=a∧b a∧b≤a 同理a∧b≤b a∧b 是a,b的下界。

应用离散数学代数结构格和布尔代数题库试卷习题及答案

应用离散数学代数结构格和布尔代数题库试卷习题及答案

§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 都不具有整除关系，但是，但，不满足分配律，所以不是分配格。

离散数学(第二版)第7章格和布尔代数和

离散数学(第二版)第7章格和布尔代数和
第七章 格和布尔代数
离散数学(第二版)第7章格和布尔代 数和
第七章 格和布尔代数
7.1 格 与 子 格
本章将讨论另外两种代数系统——格与布尔代数， 它 们与群、 环、 域的基本不同之处是： 格与布尔代数的基集 都是一个偏序集。 这一序关系的建立及其与代数运算之间 的关系是介绍的要点。 格是具有两个二元运算的代数系统， 它是一个特殊的偏序集， 而布尔代数则是一个 特殊的格。
于是， 我们有下列对偶原理。
第七章 格和布尔代数
定理7.1.2 如果命题P在任意格〈L， 〉上成立， 则
将L中符号∨， ∧，
∧， ∨，
P*在任意格〈L， 〉上也成立， 这里P*称为P的对偶式。
在上述对偶原理中， “如果命题P在任意格〈L， 〉
上成立”的含义是指当命题P中的变量取值于L中， 且上确
界运算为∨， 下确界运算为∧， 则P对于它们也成立。
第七章 格和布尔代数
再设a=a∧b， 则a∨b=(a∧b)∨b=b(由吸收律)， 即
a∨b=b。
最后， 设b＝a∨b， 则由a a∨b可得a b。
因此， (1)中3个命题的等价性得证。
(2) 因为 a a∨b， a a∨c, 故a (a∨b)∧(a∨c)。 又
因为
b∧c b a∨b b∧c c a∨c
条件是b a, 则〈L, 也是偏序集。 我们把偏序集〈L, 和〈L, 称为是相互对偶的。 并且它们所对应的哈
斯图是互为颠倒的。 关于格我们有同样的性质。 定理7.1.1 若〈L, 是一个格， 则〈L, 也是一
个格, 且它的并、 交运算∨r, ∧r对任意a, b∈L满足 a∨rb=a∧b，a∧rb=a∨b
证明 先证幂等性成立。 由吸收律知 a∧a＝a∧(a∨(a∧b))＝a a∨a＝a∨(a∧(a∨b))＝a

近世代数期末考试试题和答案解析

近世代数期末考试试题和答案解析

一、单项选择题(本大题共5小题，每小题3分，共15分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。

错选、多选或未选均无分。

1、设G 有6个元素的循环群，a 是生成元，则G 的子集（ ）是子群。

A 、{}aB 、{}e a ,C 、{}3,a eD 、{}3,,a a e 2、下面的代数系统（G ，*）中，（ ）不是群A 、G 为整数集合，*为加法B 、G 为偶数集合，*为加法C 、G 为有理数集合，*为加法D 、G 为有理数集合，*为乘法3、在自然数集N 上，下列哪种运算是可结合的？（ ）A 、a*b=a-bB 、a*b=max{a,b}C 、 a*b=a+2bD 、a*b=|a-b|4、设1σ、2σ、3σ是三个置换，其中1σ=（12）（23）（13），2σ=（24）（14），3σ=（1324），则3σ=（ ） A 、12σ B 、1σ2σ C 、22σ D 、2σ1σ5、任意一个具有2个或以上元的半群，它（ ）。

A 、不可能是群B 、不一定是群C 、一定是群D 、 是交换群二、填空题(本大题共10小题，每空3分，共30分)请在每小题的空格中填上正确答案。

错填、不填均无分。

1、凯莱定理说：任一个子群都同一个----------同构。

2、一个有单位元的无零因子-----称为整环。

3、已知群G 中的元素a 的阶等于50，则4a 的阶等于------。

4、a 的阶若是一个有限整数n ，那么G 与-------同构。

5、A={1.2.3} B={2.5.6} 那么A ∩B=-----。

6、若映射ϕ既是单射又是满射，则称ϕ为-----------------。

7、α叫做域F 的一个代数元，如果存在F 的-----n a a a ,,,10 使得010=+++n n a a a αα 。

8、a 是代数系统)0,(A 的元素，对任何A x ∈均成立x a x = ，则称a 为---------。

6.3格与布尔代数

6.3格与布尔代数

格的性质(续)
6)、保序性：如果b≤c，那么a∧b≤a∧c a ∨ b≤a∨c 7)、分配不等式: •
a∨(b∧c)≤(a∨b)∧(a∨c); a∧(b∨c)≥(a∧b)∨(a∧c); 8)、模不等式： a≤b a∨(b∧c) ≤b∧(a∨c)
下一页
证明： (a∨b)∨c=a∨(b∨c)
先证： (a∨b)∨c ≤ a∨(b∨c) ∵ a ≤ a∨(b∨c) b ≤ b∨c ≤a∨(b∨c) ∴a∨b≤ a∨(b∨c) 又：c ≤ a∨(b∨c) 从而， (a∨b)∨c ≤ a∨(b∨c) 同理有 a∨(b∨c) ≤(a∨b)∨c ， 由偏序的反传递性知，(a∨b)∨c=a∨(b∨c)
5的补元是2和3。
例：在<S24,|> 中
24 12 6 4 2 1 S24 8
最大元为24,最小元为1, 1和24互为补元, 3和8互为补元，
3
2,4,6,12均不存在补元。
例：
1 在如上图有界格中0和1互为补 a b c d 元而 a,b,c,d的补元均有三个， 譬如，a的补元是b，c，d。 0 1 a c 0 b 在下图中的有界格中，0和1互 为补元， 但a,b,c均不存在补元。
返回
代数格
定义10：设L是一个非空集合，∧，∨是L中的两 个二元运算，两个运算还满足a,b,c∈L (1)交换律 (2)结合律 a∧b=b∧a，a∨b=b∨a； (a∧b)∧c= a∧(b∧c)， (a∨b)∨c=a∨ (b∨c); (3)吸收律 a∧(b∨c)= a, a∨(b∧c)= a
例1：
记作(L,≤,1,0)或记(L,∧,0,0,1)
例:(Sn,|)是格,则其是有界格,其中最大元是n,最小元 是1,因x∈Sn,1|x,x|n。

离散数学作业册

离散数学作业册

第一章命题逻辑命题与逻辑联结词1.判断下列语句是否是命题，不是划“×”，是划“√”，且指出它的真值.(1)所有的素数都是奇数. ( ) 其真值( )(2)明天有离散数学课吗 ( ) 其真值( )(3)326+>． ( ) 其真值( )(4)实践出真知. ( ) 其真值( )(5)这朵花真好看呀！ ( ) 其真值( )(6)5x=． ( ) 其真值( )(7)太阳系外有宇宙人． ( ) 其真值( )2.将下列命题符号化．(1)如果天下雨，那么我不去图书馆.(2)若地球上没有水和空气，则人类无法生存.(3)我们不能既划船又跑步．(4)大雁北回，春天来了.3.将下列复合命题分解成若干个原子命题，并找出适当的联结词.(1)天下雨，那么我不去图书馆.(2)若地球上没有水和空气，则人类无法生存.命题公式1. 判断下列各式是否是命题公式，不是的划“×”，是的划“√”．(1)(Q R∧S). ( )(2)((R(Q R)(P Q)). ( )(3) (P∨QR)S. ( )(4)((P Q)(Q P)). ( )2．写出五个常用命题联结词的真值表.真值表与等价公式1.指出下列命题的成真赋值与成假赋值．(1)(P∨Q).(2)P(Q P).2.构造真值表，判断下列公式的类型．(1)(P∧Q)∧(P∨Q).(2) P→(P∧┑Q))∨R.3.用等值演算法验证下列各等价式．(1) ((P→Q)∧(Q→R))→(P→R) T.(2)P(Q∧R)(P Q)∧(P R).(3)(P∨Q)∨(P∧Q)P．蕴涵式及其他联结词1.试证明下列各式为重言式．(1)(P Q)∧(Q R)(P R)．(2) (P→Q)→Q⇒P∨Q．(3)(P Q)⇒P Q．2.将下列公式化成与之等价且仅含{┑，∨}中联结词的公式．(1) (P∨Q)∧┑P(2) (P→(Q∨┑R))∧(┑P∧Q)3.证明{，∧}是最小全功能联结词组.4.设A、B、C为任意的三个命题公式，试问下面的结论是否正确(1)若A∧C B∧C，则A B．(2)若A B，则A B．(3)若A C B C，则A B．对偶与范式1.试给出下列命题公式的对偶式．(1)T∨(P∧Q)．(2)(P∧Q)∧(P∨Q)．2.试求下列各公式的主析取范式和主合取范式．(1) (P→(Q∧R))∧(┑P→(┑Q→R))．(2)((P Q)∧Q)∨R．(3)(P(Q∨R))∧(P∨(Q R)).3.试用将公式化为主范式的方法，证明下列各等价式．(1) (┑P∨Q)∧(P→R)⇔P→(Q∧R)(2) ┑(P↔Q)⇔(P∧┑Q)∨(┑P∧Q)推理理论1.试用推理规则，论证下列各式．(1) ┑(P∧┑Q),┑Q∨R,┑R⇒┑P(2) P∨Q,Q→R,P→S,┑S⇒R∧(P∨Q)(3) ┑P∨Q,┑Q∨R,R→S⇒P→S(4) P∨Q,P→R,Q→S⇒R∨S第二章谓词逻辑词的概念与表示1.用谓词表达写出下列命题．(1)高斯是数学家，但不是文学家.(2)小王既是运动员也是大学生.(3)张宁和李强都是三好学生.(4)若是x奇数，则2x不是奇数.命题函数与量词1.用谓词表达式写出下列命题．(1)每个计算机系的学生都学离散数学.(2)直线A平行于直线B当且仅当直线A不相交于直线B.(3)不存在既是奇数又是偶数的自然数.(4)没有运动员不是强壮的.(5)有些有理数是实数但不是整数. (6)所有学生都钦佩某些教师.谓词公式与变元的约束1.利用谓词公式翻译下列命题． (1)没有一个奇数是偶数.(2)一个整数是奇数，如果它的平方是奇数.2. 设个体域为自然数集N ，令P(x)：x 是素数；E(x)：x 是偶数； O(x)：x 是奇数；D(x ，y)：x 整除y ．将下列各式译成汉语． (1)x(E(x)∧D(x ，6))． (2)x(O(x)y(P(x)D(x ，y)))．3.指出下列表达示中的自由变元和约束变元，并指明量词的辖域． (1)()()(,)()()x F x Q x y xP x R x ∀∧→∃∨． (2)x(P(x ，y)∨Q(z))∧y(R(x ，y)zQ(z))．4.设个体域为A＝{a，b，c}，消去公式xP(x)∧xQ(x)中的量词．谓词演算的等价式与蕴含式1.试证下列等价式或蕴涵式,其中A(x),B(x)表示含x自由变量的公式,A,B 表示不含变量x（不论是自由的还是约束的）的公式.(1)（∀x A(x)→B）⇔(∃x(A(x)→B))．(2)（∃x A(x)→B）⇔∀x(A(x)→B)．2.试将下列公式化成等价的前束范式．(1)∃x（（┑∃yP(x,y)）→(∃zQ(z)→R(x))）．(2)x(F(x)G(x))(xF(x)xG(x))．谓词演算的推理理论1.证明下列推理．(1)所有有理数都是实数，某些有理数是整数。

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

布尔代数可用相互独立的亨廷顿公理给出, 即一个代数系统 (L, ∧,∨,-,0,1)是布 尔代数当且仅当交换律、分配律、同一律 及互补律成立;
有限布尔代数同构于某个集合上的幂集构 成的布尔代数；
两个有限布尔代数同构当且仅当它们所含 的元素个数相同.
返回本章首页
5 2019/12/4
本章小结
第七章 格与布尔代数
布尔代数是计算机科学最重要的基础理论之 一,它在开关网络及数字电路的设计上有广 泛深入的应用. 布尔代数是计算机科学工作者必备的基础知 识，应掌握格与布尔代数的一般理论和方法， 除§3 Stone定理的证明细节可根据具体情 况删减外，其他内容应很好地掌握.
返回首页
1 2019/12/4
本章我们介绍了代数格、偏序格，并证 明了这两种格的等价性，此外我们还介 绍了对偶原理、分配格、有补格、布尔 代数等概念.布尔代数是数字逻辑的基 础、在学习数字逻辑时会更深刻地体会 到布尔代数在计算机中的应用.
返回本章首页
6 2019/12/4
第一节 格的概念(1)
格有两种等价的定义:一种是从偏序集 的角度给出格的定义，这种定义可以借 助哈斯（Hasse）图来表示，因而比较 直观，易于理解，这样定义的格称为偏 序格；另一种是从代数系统的角度来给 出格的定义，这种定义方法我们在上一 章的群、环的定义中已有所体会，用代 数系统的方法定义的格称为代数格.
主要概念有:有界格、余元素(或补元素) 、 有余格、分配格等.
主要结论有: 1.格的基本性质(见教材定理7.2.1); 2.序集构成的格是分配格; 3.在有界分配格中,若某个元素有补元,
则补元惟一.ຫໍສະໝຸດ 返回本章首页4 2019/12/4
第三节 布尔代数

离散数学9-格与布尔代数

(2)类似于(1)可证，3)由(1)和(2)得证。
17
定理4: 设<A, ∨, ∧>是格，对任意a, b, cA，有 (1)若a≤b和c≤d，则a∧c≤b∧d，a∨c≤b∨d (2)若a≤b，则a∧c≤b∧c，a∨c≤b∨c
18
证明：(1)如果a≤b，又b≤b∨d, 由传递性得 a≤b∨d, 类似由c≤d， d≤b∨d，由传递性得 c≤b∨d,这说明b∨d是{a, c}的上界，而a∨c是{a, c}的最小上界，所以a∨c≤b∨d。类似可证 a∧c≤b∧d。
则称b是a的补元，记为a′。若b是a的补元，则a也是b的补 元，即a与b互为补元。 一般说来，一个元素可以有其补元 ，未必唯一，也可能无补元。0′=1和1′=0。
37
定义12: 在有界格中，如果每个元素都有补元，则称格是有 补格。
由于补元的定义是在有界格中给出的，可知，有补格一定是 有界格。
38
定理11: 在有界分配格中，如果某元素有补元，则补元是唯 一的。
34
定理9: 设<A, ∧,∨, 0, 1>是有界格，则对于A中任意元素 a 都有 a∨1 = 1 a∧1 = a a∨0 = a a∧0 = 0
1称为全上界或最大元，0称为全下界或最小元。
图9-6中(a)(b)(c)都有最大元和最小元，所以都是有界格。
35
定理10: 有限格必定是有界格。
36
定义11: 设<A,∨,∧>是有界格，aA，如果存在bA使得 a∨b = 1 a∧b = 0
31
定义8: 设<A,∨,∧>是格，如果A中存在元素a,使得对于A中 任意元素x 都有a≼x，则称a为格(A , ≤)的全下界，用0表 示。如果L中存在元素 a, 使得对于L中任意元素 x 都有 x≼a则称a为格(A , ≤)的全上界，用1表示。全下界即是格 的最小元，是唯一的。全上界即是格的最大元，是唯一的 。

代数系统练习题答案

代数系统练习题答案1. 以下集合和运算是否构成代数系统？如果构成，说明该系统是否满足结合律、交换律？求出该运算的幺元、零元和所有可逆元素的逆元.1) P关于对称差运算⊕，其中P为幂集.构成代数系统；满足结合律、交换律；幺元φ；无零元；逆元为自身。

2) A={a,b,c}，*运算如下表所示：构成代数系统；满足结合律、交换律；无幺元；无逆元；零元b.2. 设集合A={a,b}，那么在A上可以定义多少不同的二元运算？在A上可以定义多少不同的具有交换律的二元运算？24个不同的二元运算；23个不同的具有交换律的二元运算3. 设A={1,2},B是A上的等价关系的集合.1) 列出B的元素.元集合上只有2种划分，因此只有2个等价关系，即B={IA，EA}2) 给出代数系统V=的运算表.3) 求出V的幺元、零元和所有可逆元素的逆元.幺元EA、零元IA；只有EA可逆，其逆元为EA.4) 说明V是否为半群、独异点和群？V是为半群、独异点，不是群4. 设A={a,b,c}，构造A上的二元运算*，使得a*b=c,c*b=b，且*运算满足幂等律、交换律.1) 给出关于*运算的一个运算表.其中表中？位置可以是a、b、c。

2) *运算是否满足结合律，为什么？不满足结合律；a*=c ≠*b=b5. 设是一个代数系统。

*是R上的一个二元运算，使得对于R中的任意元素a,b都有a*b=a+b+a·b.证明：: 是独异点.6. 如果是半群，且*是可交换的.证明：如果S中有元素a,b,使得a*a=a和b*b=b，则*=a*b.*= a**b结合律= a**b 交换律= *= a*b.7. 设是一个群,则?a,b,c∈S。

试证明：群G中具有消去律,即成立: 如果a·b=a·c ,b·a=c·a 那么b=c.8. 设是群，a∈G .现定义一种新的二元运算⊙：x⊙y=x*a*y，?x,y∈G .证明：也是群 .证明：显然⊙是G上的一个二元运算。

离散数学 格与布尔代数


P’: a∨b≥a
{a,b}的最大下界≤a {a,b}的最小上界≥a
三. 格的性质
<A,∨,∧>是由格<A,≤>诱导的代数系统。a,b,c,d∈A 1. a≤a∨b b≤a∨b a∧b≤a a∧b≤b
此性质由运算∨和∧的定义直接得证。 2.如果a≤b，c≤d，则 a∨c≤b∨d，a∧c≤b∧d。 证明：如果a≤b，又b≤b∨d，由传递性得 a≤b∨d, 类似由c≤d， d≤b∨d，由传递性得 c≤b∨d, 这说明b∨d是 {a,c} 的一个上界，而a∨c是 {a,c} 的最小上
可见它们同构。
格同构，它们的哈斯图的形状一定相同。
具有1、2、3个元素的格分别同构于含有一、二、三 个
元素的链。
a
a
a
b
b c
具有4个元素的格分别同构a 于下面两种格形 a式之一：
b
c
b
c
d
d
具有5个素的格分别同构于下面五种格形式之一：
a b c b
d
e
a c d b e
a c b
d e
a
c
d
c
e
a b
d e
2. 格同态的保序性
定理：设f是格<A1,≤1> 到<A2, ≤2> 的同态映射，则对任 何a,b∈A1，如果a≤1b，则 f(a)≤2f(b)。 证明：令<A1,∨1,∧1>和 <A2,∨2,∧2>是格<A1,≤1> 和
<A2, ≤2>诱导的代数系统，任取a,b∈A1，设a≤1b， 则 a∧1b=a f(a∧1b)=f(a) 即 f(a)∧2f(b)=f(a) 而 f(a)∧2f(b) ≤2f(b) 所以 f(a)≤2f(b). 3. 格同构的保序性
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

所以<B,≤>是<A,≤>的子格.
9
(6).设<A,≤>是有界格, 对于任何x,y∈A, 证明 a). x∨y=0 , 则 x=y=0 b). x∧y=1, 则 x=y=1 证明: a) x=x∧(x∨y)=x∧0=0 y=y∧(y∨x)=y∧0=0 b) x=x∨(x∧y)=x∨1=1 y=y∨(y∧x)=y∨1=1 P260(2).设<S,∨,∧,¯ >是布尔代数，x,y∈S, 证明: x≤y 当且仅当 y x 证明: 充分性 已知 y x
(9).证明格中成立: 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)≤(a∨c) ∵ (c∧d)≤c≤(a∨c) ∴ (c∧d)≤(a∨c) ∴ (a∧b)∨(c∧d)≤(a∨c) 同理 (a∧b)≤(b∨d) (c∧d)≤(b∨d) ∴ (a∧b)∨(c∧d)≤(b∨d) ∴(a∧b)∨(c∧d)≤(a∨c)∧(b∨d) b) ∵ (a∧b)≤(a∨b), (a∧b)≤(b∨c) ,(a∧b)≤(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).

(5).设<A,≤>是分配格,a,b∈A, 且a<b, 证明 f(x)=(x∨a)∧b 是一个从A到B的同态映射. 其中 B={x|x∈A且a≤x≤b} 证明:先证 f 是从A到B的映射:任取x∈A, 由f的定义得 f(x)=(x∨a)∧b 显然 (x∨a)∧b≤b 而 (x∨a)∧b=(x∧b)∨(a∧b)=(x∧b)∨a (因a<b a∧b=a) ∴ a≤(x∨a)∧b≤b 即a≤f(x)≤b ∴f(x)∈B ∴ dom f=A. 又由于∨和∧的定义知(x∧b)∨a是唯一的. 即f(x)是唯一的. 所以f 是从A到B的映射. 再证f 满足同态等式:任取x1,x2∈A, f(x1∧x2)=((x1∧x2)∨a)∧b=((x1∨a)∧(x2∨a))∧b =((x1∨a)∧b)∧((x2∨a)∧b) =f(x1)∧f(x2) f(x1∨x2)=((x1∨x2)∨a)∧b=((x1∨a)∨(x2∨a))∧b =((x1∨a)∧b)∨((x2∨a)∧b) =f(x1)∨f(x2) ∴f 是同态映射.7
5
P248(2).下面哪个是分配格? 1 a 2 b c 3 d e 5 f (b) (a)



a

b


d g
c

4

e


(c)

f

a

解:判定一个格是否分配格,看它是否含有 b c d 五元素的非分配格形式的子格. e g a (a)图好像可以去掉b或c后 a f b 得到如下图: c c (c) d e d 但它们不是(a)的子格. f f 1 a 因d∨e=b b∧c=e c 2 3 4 b,e不在子集里. ∴(a)是分配格. d e 5 (b)也是分配格. (c)不是分配格. f 6
3
(7).设a,b是格<A, ≤>中的两个元素,证明: a). a∧b=b 当且仅当a∨b=a. b). a∧b<b和a∧b<a,当且仅当 a与b是不可比较的. 证明:a)充分性: 已知a∨b=a b=b∧(b∨a)= b∧(a∨b) =b∧a=a∧b 必要性:已知a∧b=b , a=a∨(a∧b)=a∨b b)充分性:已知a与b是不可比较的. 因a∧b≤b, a∧b≤a, 如果a∧b=b, 则有b≤a, 如果a∧b=a, 则有a≤b, 都与a与b是不可比较的矛盾. 所以有: a∧b≤b∧ a∧b≠b,于是有 a∧b<b a∧b≤a∧ a∧b≠a,于是有 a∧b<a 必要性:已知a∧b<b和a∧b<a, 假设a与b是可比较的.则要 么a≤b,要么b≤a. 于是要么a∧b=a 要么a∧b=b. 这与 4 a∧b<b和a∧b<a矛盾.所以a与b是不可比较的.
第七章 习题课
P242 (1).
a
b


f

l


1


d
c

g i



h j
m
o



n

p
q
2 5



3


4
6

r 7 8 k e (a) (b) (c) (d) (a)不是格 因为d和e没有下确界,也没有上确界. (d)不是格5和6没有下确界,7和8既没下确界,也没上确界. f 进一步问,如果是格,哪些是分配格?哪些是有补格? h (b)不是分配格,因去掉结点i后的子格如图所示 g j 但它是有补格. (c)不是分配格(去m,p),不是有补格. k 1
(a b) (a b ) (a a b ) (b a b ) 0 0 0 所以 a b 有补元 a b 所以 a b B (a b) (a b ) (a a b ) (b a b ) 1 1 1 ( a b) ( a b ) ( a b a ) ( a b b ) 0 0 0 所以 a b 有补元 a b 所以 a b B
即 yx y yx y yx y y 所以 x y
必要性: 已知 x≤y
x y x x y x 即 x y x 所以 y x
10
P269(1).设 E(x 1,x 2,x 3) (x 1 x 2) (x 2 x 3) (x 2 x 3) 是<{0,1},∨,∧, ¯> x1 x2 x3 E (x1, x2 , x3) 上的一个布尔表达 0 0 0 0 式.分别写出它的析 0 0 1 1 取范式与合取范式. 0 1 0 0 方法1.用真值表 0 1 1 1 E ( x1, x 2, x 3) 1 0 0 0 ( x1 x 2 x 3 ) 1 0 1 1 ( x1 x 2 x 3 ) 1 1 0 1 ( x 1 x 2 x 3) 1 1 1 1
可见与用真值表求的结果相同.
13
格与布尔代数
到此结束
14
E ( x1, x 2, x 3) ( x 1 x 2 x 3) ( x 1 x 2 x 3) ( x1 x 2 x 3) ( x1 x 2 x 3) ( x1 x 2 x 3)
11
方法2. 用等价变换的方法.
E ( x1, x 2, x 3) ( x1 x 2) ( x 2 x 3) ( x 2 x 3) ( x1 x 2 ( x 3 x 3)) (( x1 x 1) x 2 x 3) (( x1 x 1) x 2 x 3) ( x1 x 2 x 3 ) ( x 1 x 2 x 3 ) ( x 1 x 2 x 3 ) ( x 1 x 2 x 3 ) ( x1 x 2 x 3 ) ( x 1 x 2 x 3 ) ( x1 x 2 x 3 ) ( x 1 x 2 x 3 ) ( x 1 x 2 x 3 ) ( x1 x 2 x 3 ) ( x 1 x 2 x 3 )
这是析取范式. 求它的合取范式可能要麻烦一些. 下面求合取范式:
12
E ( x1, x 2, x 3) ( x1 x 2) ( x 2 x 3) ( x 2 x 3) ( x1 x 2) (( x 2 x 2) x 3) ( x1 x 2 ) x 3 ( x1 x 3 ) ( x 2 x 3 ) ( x1 ( x 2 x 2) x 3) (( x1 x 1) x 2 x 3) ( x1 x 2 x 3 ) ( x1 x 2 x 3 ) ( x1 x 2 x 3 ) ( x 1 x 2 x 3 ) ( x1 x 2 x 3 ) ( x1 x 2 x 3 ) ( x 1 x 2 x 3 )

8
(4). 在有界分配格中,证明具有补元的那些元素组成一个 子格. 证明: 设<A,≤>是有界分配格,令B ={ y | ӯ∈A} 任取a,b∈B, ā, ¯ b ∈A, ā∧ ¯ b∈A, ā∨ ¯ b ∈A 下面证明∨和∧在B上封闭,即a∨b和a∧b都有补元: ( a b) ( a b ) ( a b a ) ( a b b ) 1 1 1
1 P252(1). 给出有界格如图 a)哪些元素有补元? a b c b)该格是分配格吗? d e f g c)该格是有补格吗? 解:a) a、c、d、f、g 无补元 ; 0 b和e互为补元 ; 0和1互为补元. a b) 不是分配格, 因为它含有子格如下图. d e c) 它不是有补格,因为很多元素无补元. f (3).证明具有两个或更多个元素的格中 不存 0 在以自身为补元的元素. 证明:设<A,≤>是格,且|A|≥2, 假设有a∈A,使得 ā=a ∴a≠0, a≠1, 但是有 1=a∨ā =a∨a=a 0=a∧ā =a∧a=a 产生矛盾. 所以不存在以自身为补元的元素.





(2). 设≤是L上的整除关系,下面偏序集中,哪些是格? 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} 12 4