Discrete mathematics Yi li Software school Fudan University February 28, 2012
Discrete Mathematics Yi Li Software School Fudan University February 28, 2012 Yi Li (Fudan University) Discrete Mathematics February 28, 2012 1 / 15
utline o Review of partial order set o Review of abstract algebra o Lattice and Sublattice
Outline Review of partial order set Review of abstract algebra Lattice and Sublattice Yi Li (Fudan University) Discrete Mathematics February 28, 2012 2 / 15
Introduction o Intensively explored area o By 1960s, 1, 500 papers and books e By 1970s, 2, 700 papers and books o By 1980s, 3, 200 papers and books o By 1990s, 3, 600 papers and books o History O By 1850, George Boole's attempt to formalize roposition logic O At the end of 19th century, Charles S. Pierce and Ernst Schroder endently, Richar Dedekind mid-1930s Garrett Birkhoff develo loped general theory on lattice
Introduction Intensively explored area 1 By 1960s, 1,500 papers and books 2 By 1970s, 2,700 papers and books 3 By 1980s, 3,200 papers and books 4 By 1990s, 3,600 papers and books History 1 By 1850, George Boole’s attempt to formalize proposition logic. 2 At the end of 19th century, Charles S. Pierce and Ernst Schr¨oder 3 Independently, Richar Dedekind. 4 Until mid-1930’s, Garrett Birkhoff developed general theory on lattice. Yi Li (Fudan University) Discrete Mathematics February 28, 2012 3 / 15
Partial order set( Poset) Definition Given a set a and a relation R on it is called a partially ordered set( poset in brief)if R is reflexive, antisymmetric and transitive
Partial order set(Poset) Definition Given a set A and a relation R on it, is called a partially ordered set(poset in brief) if R is reflexive, antisymmetric and transitive. Yi Li (Fudan University) Discrete Mathematics February 28, 2012 4 / 15
Poset Definition Given a poset A, <> we can define o a is maximal if there does not exist b e A such that a< b e a is minimal if there does not exist b e a such that a is greatest if for every b∈A, we have b≤a a is least if for every b∈A, we have a≤b
Poset Definition Given a poset , we can define: 1 a is maximal if there does not exist b ∈ A such that a ≤ b. 2 a is minimal if there does not exist b ∈ A such that b ≤ a. 3 a is greatest if for every b ∈ A, we have b ≤ a. 4 a is least if for every b ∈ A, we have a ≤ b. Yi Li (Fudan University) Discrete Mathematics February 28, 2012 5 / 15
Poset Definition Given a poset A, < and a set SCa u∈ A is a upper bound of s if s≤ u for every s∈S. @lE A is a lower bound of s if l≤ s for every s∈S
Poset Definition Given a poset and a set S ⊆ A. 1 u ∈ A is a upper bound of S if s ≤ u for every s ∈ S. 2 l ∈ A is a lower bound of S if l ≤ s for every s ∈ S. Yi Li (Fudan University) Discrete Mathematics February 28, 2012 6 / 15
Poset Definition Given a poset A, < and a set Sca o u is a least upper bound of S, (LUB(S)), if u is the upper bound of s and u u' for any other er bound u of o l is a greatest lower bound of S, GLB(S)), if l is the upper bound of s and l'<l for any other lower bound l' of s Theorem A poset has at most one lUb or GLB
Poset Definition Given a poset and a set S ⊆ A. 1 u is a least upper bound of S, (LUB(S)), if u is the upper bound of S and u ≤ u 0 for any other upper bound u 0 of S. 2 l is a greatest lower bound of S, (GLB(S)), if l is the upper bound of S and l 0 ≤ l for any other lower bound l 0 of S. Theorem A poset has at most one LUB or GLB. Yi Li (Fudan University) Discrete Mathematics February 28, 2012 7 / 15
Lattice Definition A lattice(structure )is a poset in which any two elements a, b have a Lub(a, b) and a glb(a, b) From now on, we define aUb= LU B(a, b)and anb=glB(a, b)in brief. We also call them join and meet respectively
Lattice Definition A lattice (structure) is a poset in which any two elements a, b have a LUB(a, b) and a GLB(a, b). From now on, we define a ∪ b = LUB(a, b) and a ∩ b = GLB(a, b) in brief. We also call them join and meet respectively. Yi Li (Fudan University) Discrete Mathematics February 28, 2012 8 / 15
Representation Lattice O Hasse diagram o Joint/ meet table
Representation Lattice 1 Hasse diagram 2 Joint/meet table Yi Li (Fudan University) Discrete Mathematics February 28, 2012 9 / 15
Lattice operty The Lattice has the following properties o Commutative:a∩b=b∩a,aUb=b∪a O Associative (a∩b)nc=an(bnc),(a∪b)uc=aU(bUc) idempotent:a∩a=a,a∪a=a o Absorption:(a∪b)∩a=a,(anb)∪a=a operty a lattice could be divided into a join-semilattice and a meet-semilattice
Lattice Property The Lattice has the following properties: 1 Commutative: a ∩ b = b ∩ a, a ∪ b = b ∪ a. 2 Associative: (a ∩ b) ∩ c = a ∩ (b ∩ c),(a ∪ b) ∪ c = a ∪ (b ∪ c). 3 Idempotent: a ∩ a = a, a ∪ a = a. 4 Absorption: (a ∪ b) ∩ a = a,(a ∩ b) ∪ a = a. Property A lattice could be divided into a join-semilattice and a meet-semilattice. Yi Li (Fudan University) Discrete Mathematics February 28, 2012 10 / 15