离散数学教案 编号：C1301 课时安排： 2学时教学课型：理论课√实验课口习题课口实践课口其它口 题目（教学章、节或主题）： Ch13格与布尔代数 §13.1格的定义与性质 §132子格与格同态 教学目的要求（分掌握、熟悉、了解三个层次）： 1.理解格的定义、子格概念 2.掌握格的性质 3.了解格同态定义 教学重点、难点： 1)重点：掌握格的定义及基本性质：了解子格的定义与格同态的概念 2)难点：子格的定义与格同态的概念 教学方法： 利用黑板，CAI课件等教学 教学用具 黑板，CAI课件及其辅助设备。 教学内容（注明：◆重点#难点？疑点）： 一、概念(25分钟) 1.定义设是偏序集，如果xy∈S,xy都有最小上界和最大下界则称S关于≤构成一个格 xVy表示x和y的最小上界 xAy表示x和y的最大下界 例1设n为正整数，Sn为n的正因子的集合，D为整除关系，则构成格 xy∈Sn,xVy是xy的最小公倍数xyxy是xy的最大公约数(xy) 例2格,和 2.对偶原理 设f是含有格中的元素以及符号=≤，≥，V,Λ的命题，令是将f中的≤改写成≥将≥改写成≤ V改写成入，改写成V所得到的命题，称为的对偶命愿根据格的对偶原理若对一切格为真，则伴也为 一切格为真】 例3，在格中有(aVb)八c≤c成立，则有 (aAb)Vc≥c成立. 性质与运算(20分钟) 定理设为格，则运算V和适合交换律、结合律、幂等律和吸收律，即 (1)Va,bEL aVb=bVa,aAb=bAa
1301 离 散 数 学 教 案 编号：C1301 课时安排： 2 学时 教学课型：理论课√ 实验课□ 习题课□ 实践课□ 其它□ 题目（教学章、节或主题）： Ch13 格与布尔代数 §13.1 格的定义与性质 §13.2 子格与格同态 教学目的要求（分掌握、熟悉、了解三个层次）： 1. 理解格的定义、子格概念 2. 掌握格的性质 3. 了解格同态定义 教学重点、难点： 1） 重点： 掌握格的定义及基本性质；了解子格的定义与格同态的概念 2） 难点：子格的定义与格同态的概念 教学方法: 利用黑板,CAI 课件等教学. 教学用具: 黑板,CAI 课件及其辅助设备. 教学内容（注明：* 重点 # 难点 ？疑点）： *一、概念（25 分钟） 1. 定义 设是偏序集,如果 x,y∈S,{x,y}都有最小上界和最大下界,则称S关于≤构成一个格. x∨y 表示 x 和 y 的最小上界 x∧y 表示 x 和 y 的最大下界. 例 1 设 n 为正整数,Sn 为 n 的正因子的集合,D 为整除关系,则构成格. x,y∈Sn, x∨y 是 x,y 的最小公倍数[x,y], x∧y 是 x,y 的最大公约数(x,y) 例 2 格,和 2．对偶原理 设 f 是含有格中的元素以及符号=,≤,≥, ∨,∧的命题,令 f*是将 f 中的≤改写成≥,将≥改写成≤, ∨改写成∧,∧改写成∨所得到的命题,称为 f 的对偶命题.根据格的对偶原理,若 f 对一切格为真,则 f*也对 一切格为真. 例 3,在格中有 (a∨b)∧c≤c 成立, 则有 (a∧b)∨c≥c 成立. 二、 性质与运算（20 分钟） 1．定理 设为格,则运算∨和∧适合交换律、结合律、幂等律和吸收律,即 (1) a,b∈L 有 a∨b＝b∨a, a∧b＝b∧a
(2)廿a,b,ceL有(aVb)Vc=aV(bVc, (aAb)Ac=aA(bAc). 3a∈L有 a/a=aa八a=a (4)Yab∈L有aV(a人b)=aaA(aVb)=a 格的另一个等价的定义 设 >是具有两个 元运算的代数系统，且对于幸和运算适合交换律、结合律、吸收律，则可以适当定义 S中的偏序≤使得构成一个格，且Ha,b∈S aAb=a*b. aVb=ab. 三、子格与格同态(40分钟) 1.定义设(L,A,V)是格，S是L的非空子集，若S关于L中的运算入和v仍构成格， 则称(S,V)是格(L,A,)的子格 例1.(S6,D)是(S4,D)的子格。 2.定义.设L×,⊕)和(S,人，V)是两个格，L到S内的映射g称为L×,®)到(S,八，V)的格同态映 射，如果对任意a,b∈L,都有 g (axb)=g (a)Ag (b) g(a⊕b)=g(a)Vg(b) 3.定义.格L到L内的同态映射称为格的自同态映射。 4.定义.若g是L到S上的同态映射，且是一对一的，则称g是格同构映射，并称格L与格S是同构 的 例2.设S={ab，p(S)={仲，a,b,ab,则(p(S,n,U)是一个格。 规定映射g为：g)=g{a)=中，gb)g(a,bb。证g是同态映射 四、课堂小结（约5分钟） 1302
1302 (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. 2．格的另一个等价的定义. 设是具有两个二元运算的代数系统,且对于*和运算适合交换律、结合律、吸收律,则可以适当定义 S 中的偏序≤使得构成一个格,且 a,b∈S a∧b=a*b, a∨b=ab. 三、子格与格同态（40 分钟） 1．定义 设（L，，）是格，S 是 L 的非空子集，若 S 关于 L 中的运算和仍构成格， 则称（S，，）是格（L，，）的子格。 例 1.（S6，D）是（S24，D）的子格。 2. 定义. 设(L,×,⊕)和(S,∧,∨)是两个格，L 到 S 内的映射 g 称为(L,×,⊕)到(S,∧,∨)的格同态映 射，如果对任意 a，b∈L，都有 g（a×b）= g（a）∧g（b） g（a⊕b）= g（a）∨g（b）. 3．定义. 格 L 到 L 内的同态映射称为格的自同态映射。 4．定义. 若 g 是 L 到 S 上的同态映射,且是一对一的，则称 g 是格同构映射,并称格 L 与格 S 是同构 的。 例 2. 设 S={a,b},ρ(S)={,{a},{b},{a,b}}，则(ρ(S)，∩，∪）是一个格。 规定映射 g 为：g() = g({a}) =， g({b})=g({a，b})= {b}。证 g 是同态映射。 四、课堂小结（约 5 分钟）
离散数学教案 编号：C1302 课时安排： 2学时教学课型：理论课√实验课口习题课口实践课口其它口 题目（教学章、节或主题）： Ch13格与布尔代数 §13.3分配格与有补格 8134布尔代数 教学目的要求（分掌握、热悉、了解三个层次）： 1.理解理解布尔代数的定义 3.掌握分配格与有补格 教学内容（注明：◆重点#难点？疑点）： 、分配格与有补格(30分钟) l.定义设是格.a,b,c∈L有aA(bVc)=(aAb)V(aAc) aV(bAc)=(aVb)A(aVc) 成立则称L为分配格 2.定义 若在格中存在一个元素b∈La≤b或b≤)，则称a为格L的全下界（或全上界） 对于一个格L,全下界如果存在，则是唯一的，记为0.同样地，若全上界存在也是唯一的，记为1 具有全上界和全下界的格称为有界格，记作 3.定义设是有界格a∈L,若存在b∈L使得a八b=0,aVb=1则称b为a的补元 4.定义在格中有的元素无补元，有的元素有补元，有的元素有多个补元，如果格中每个元素都至少有一个 补元则称这个格为有补格. 对分配格L来说，如果a∈L有补元，则一定有唯一的补元，a. 二、布尔代数概念(20分钟) 定义如果格是有补分配格，则称L为布尔格，也叫做布尔代数 由于布尔代数L中的每个元都有唯一的补元，求补运算也可以看成是L中的一元运算因此，布尔代数 可记为,其中表示求补运算. 例1集合代数是布尔代数 开关代数是布尔代数其中A为与运算，V为或运算，一为非运算 三、性质与运算(40分钟) 1.定埋设是布尔代数.则有：
1303 离 散 数 学 教 案 编号：C1302 课时安排： 2 学时 教学课型：理论课√ 实验课□ 习题课□ 实践课□ 其它□ 题目（教学章、节或主题）： Ch13 格与布尔代数 §13.3 分配格与有补格 §13.4 布尔代数 教学目的要求（分掌握、熟悉、了解三个层次）： 1. 理解理解布尔代数的定义 3．掌握分配格与有补格 教学内容（注明：* 重点 # 难点 ？疑点）： 一、分配格与有补格（30 分钟） 1．定义 设是格. a,b,c∈L 有 a∧(b∨c)＝(a∧b)∨(a∧c) a∨(b∧c)＝(a∨b)∧(a∨c) 成立,则称 L 为分配格 2．定义 若在格中存在一个元素 a,b∈L, a≤b 或(b≤a),则称 a 为格 L 的全下界(或全上界) 对于一个格 L,全下界如果存在,则是唯一的,记为 0.同样地,若全上界存在也是唯一的,记为 1, 具有全上界和全下界的格称为有界格,记作 3．定义 设是有界格a∈L,若存在 b∈L 使得 a∧b＝0,a∨b＝1,则称 b 为 a 的补元. 4．定义 在格中有的元素无补元,有的元素有补元,有的元素有多个补元,如果格中每个元素都至少有一个 补元,则称这个格为有补格. 对分配格 L 来说,如果 a∈L 有补元,则一定有唯一的补元,a’. 二、布尔代数概念（20 分钟） 定义 如果格是有补分配格,则称 L 为布尔格,也叫做布尔代数. 由于布尔代数L 中的每个元都有唯一的补元,求补运算也可以看成是 L中的一元运算.因此,布尔代数L 可记为,其中'表示求补运算. 例 1 集合代数是布尔代数. 开关代数是布尔代数,其中∧为与运算,∨为或运算, ￢为非运算. 三、 性质与运算（40 分钟） 1．定埋 设是布尔代数,则有:
a∈L,(a)'=a a,b∈L,(aVb)=a∧b'；(a∧b)=aVb' 2.定义设L是格，0eL,aL若beL有0(b≤a一b=a,则称a是L中的原子 3.定理 若L是有限布尔代数，则L含有2n个元n∈N),并且L与 同构，其中S是一个n元集合. 例13.14（§13.4） 四、课堂小结（约5分钟） 1304
1304 a∈L,(a')'＝a, a,b∈L, (a∨b)'=a'∧b' ； (a∧b)'=a'∨b' 2．定义 设 L 是格，0L，aL 若bL 有 0 b a b=a ，则称 a 是 L 中的原子 3．定理 若 L 是有限布尔代数,则 L 含有 2n 个元(n∈N),并且 L 与 同构,其中 S 是一个 n 元集合. 例 13.14 (§13.4) 四、课堂小结（约 5 分钟）