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 < AR> 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, < A, R > 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 < A, ≤>, 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