Discrete mathematics Yi Li Software school Fudan universit March 5. 2013
. . Discrete Mathematics Yi Li Software School Fudan University March 5, 2013 Yi Li (Fudan University) Discrete Mathematics March 5, 2013 1 / 17
Review o Review of a partial order set Review of abstract algebra Lattice and sublattice
Review Review of a partial order set Review of abstract algebra Lattice and Sublattice Yi Li (Fudan University) Discrete Mathematics March 5, 2013 2 / 17
utline o Special Lattices o Boolean Algebra
Outline Special Lattices Boolean Algebra Yi Li (Fudan University) Discrete Mathematics March 5, 2013 3 / 17
Idea efinition(Ring Given a ring R and a nonempty set I CR. I is an ideal of R if it subjects to o For any a,b∈I,a-b∈1. o For any a∈I,r∈R,ar,ra∈1 Definition(Lattice) a subset of a lattice is an ideal if it is a sublattice of L and a∈ I and a∈ imply that a∩a∈ A proper ideal I of L is prime if a,b∈ L and a∩b∈I imply that a∈rorb∈I
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 5, 2013 4 / 17
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: Ideal 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 5, 2013 5 / 17
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 fr∈ 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 5, 2013 6 / 17
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 o I=id(h) if and only if Ⅰ={x|x≤hoU…Uhn-1 for some n≥1and ho,…,hn-1∈H} O For a∈L,id(a)={ cnala∈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 5, 2013 7 / 17
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=fa1,., 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 5, 2013 8 / 17
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 a Ua=1 anda∩ 0 Sometimes, we can relax the restrictions by defining complement of b relative to a as bub =a, bnb=0 if 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 ′ such that a ∪ a ′ = 1 and a ∩ a ′ = 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 5, 2013 9 / 17
S pecial Lattice am dle Given a posetdescribed in following fir igure 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 5, 2013 10 / 17
