当前位置:高等教育资讯网  >  中国高校课件下载中心  >  大学文库  >  浏览文档

复旦大学:《离散数学 Discrete Mathematics》英文讲稿_02 Special Lattices Boolean Algebra

资源类别:文库,文档格式:PDF,文档页数:17,文件大小:166.58KB,团购合买
点击下载完整版文档(PDF)

Discrete mathematics Yi Li Software school Fudan universit March 6. 2012

Discrete Mathematics Yi Li Software School Fudan University March 6, 2012 Yi Li (Fudan University) Discrete Mathematics March 6, 2012 1 / 1

Review o Review of a partial order set o Review of abstract algebra o Lattice and Sublattice

Review Review of a partial order set Review of abstract algebra Lattice and Sublattice Yi Li (Fudan University) Discrete Mathematics March 6, 2012 2 / 1

utline Special Lattices o Boolean Algebra

Outline Special Lattices Boolean Algebra Yi Li (Fudan University) Discrete Mathematics March 6, 2012 3 / 1

Idea Definition(Ri Given a ring R and a nonempty set I CR. I is an ideal of R if it subjects to For any a,b∈I,a-b∈1. For any a∈I,r∈R,ar,Ta∈I. Definition( Lattice) A subset of a lattice is an ideal if it is a sublattice of L and x∈ I and a∈ L imply that a na∈I A proper ideal I of L is prime if a,b∈ L and a∩b∈I imply that a∈Iorb∈r

Ideal Definition (Ring) Given a ring R and a nonempty set I ⊆ R. I is an ideal of R if it subjects to: 1 For any a, b ∈ I, a − b ∈ I. 2 For any a ∈ I, r ∈ R, ar, ra ∈ I. Definition (Lattice) A subset I of a lattice L is an ideal if it is a sublattice of L and x ∈ I and a ∈ L imply that x ∩ a ∈ I. A proper ideal I of L is prime if a, b ∈ L and a ∩ b ∈ I imply that a ∈ I or b ∈ I. Yi Li (Fudan University) Discrete Mathematics March 6, 2012 4 / 1

Idea am dle Given a lattice and sublattice p and i as shown in the following Figure, where P=a,0 and I=0f Figure: ldeal and prime ideal

Ideal Example Given a lattice and sublattice P and I as shown in the following Figure, where P = {a, 0} and I = {0}. 0 a b 1 I P Figure: Ideal and prime ideal Yi Li (Fudan University) Discrete Mathematics March 6, 2012 5 / 1

Idea Definition o The ideal generated by a subset H will be denoted by id(H), and if H=af, we write id(a) for id(a) we shall call id(a)a principal ideal. o For an order P, a subset A C P is called down-set fx∈ A and y< c imply that y∈A

Ideal Definition 1 The ideal generated by a subset H will be denoted by id(H), and if H = {a}, we write id(a) for id(a); we shall call id(a) a principal ideal. 2 For an order P, a subset A ⊆ P is called down-set if x ∈ A and y ≤ x imply that y ∈ A. Yi Li (Fudan University) Discrete Mathematics March 6, 2012 6 / 1

Idea 「The eorem Let l be a lattice and let H and i be nonempty subsets o I is an ideal if and only if the following two conditions hold oa,b∈ I implies that a∪b∈I, o I is a down-set oI=id(h) if and only if I={x|x≤hoU…Uhn-1 for some n>1and he han-1∈H} O For a∈L,id(a)={x∩ax∈L}

Ideal Theorem Let L be a lattice and let H and I be nonempty subsets of L. 1 I is an ideal if and only if the following two conditions hold: 1 a, b ∈ I implies that a ∪ b ∈ I, 2 I is a down-set. 2 I = id(H) if and only if I = {x|x ≤ h0 ∪ · · · ∪ hn−1 for some n ≥ 1 and h0, . . . , hn−1 ∈ H}. 3 For a ∈ L, id(a) = {x ∩ a|x ∈ L}. Yi Li (Fudan University) Discrete Mathematics March 6, 2012 7 / 1

S pecial Lattice Definition a lattice L is complete if any finte or infinite) subset A=aili e I has a least upper bound Uierai and a greatest lower bound∩∈ra Definition A lattice L is bounded if it has a greatest element 1 and a least element 0 Theorem Finite lattice L=al,., an is bounded

Special Lattice Definition A lattice L is complete if any(finte or infinite) subset A = {ai |i ∈ I} has a least upper bound ∪i∈Iai and a greatest lower bound ∩i∈Iai . Definition A lattice L is bounded if it has a greatest element 1 and a least element 0. Theorem Finite lattice L = {a1, . . . , an} is bounded. Yi Li (Fudan University) Discrete Mathematics March 6, 2012 8 / 1

S pecial Lattice Definition A lattice L with 0 and 1 is said to be complemented if for every a e L there exists an a' such that aua=1 anda∩a′=0 Sometimes, we can relax the restrictions by defining complement of b relative to a as b∪b=a,b∩b1=0if 6, b1 s a Xam e is complemented for any nonempty set s

Special Lattice Definition A lattice L with 0 and 1 is said to be complemented if for every a ∈ L there exists an a 0 such that a ∪ a 0 = 1 and a ∩ a 0 = 0. Sometimes, we can relax the restrictions by defining complement of b relative to a as b ∪ b1 = a, b ∩ b1 = 0 if b, b1 ≤ a. Example is complemented for any nonempty set S. Yi Li (Fudan University) Discrete Mathematics March 6, 2012 9 / 1

S pecial Lattice am dle Given a posetdescribed in following figure Figure: Complemented Lattice

Special Lattice Example Given a poset described in following figure. a b c 1 0 Figure: Complemented Lattice. Yi Li (Fudan University) Discrete Mathematics March 6, 2012 10 / 1

点击下载完整版文档(PDF)VIP每日下载上限内不扣除下载券和下载次数;
按次数下载不扣除下载券;
注册用户24小时内重复下载只扣除一次;
顺序:VIP每日次数-->可用次数-->下载券;
共17页,试读已结束,阅读完整版请下载
相关文档

关于我们|帮助中心|下载说明|相关软件|意见反馈|联系我们

Copyright © 2008-现在 cucdc.com 高等教育资讯网 版权所有