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

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