复旦大学：《离散数学》习题课讲义（李弋）01 Review of partial order set Review of abstract algebra Lattice and Sublattice

Discrete mathematics Software school Fudan University February 24, 2014

. . Discrete Mathematics Yi Li Software School Fudan University February 24, 2014 Yi Li (Fudan University) Discrete Mathematics February 24, 2014 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 24, 2014 2 / 15

Introduction Intensively explored area o By 1960s, 1, 500 papers and books e By 1970s, 2, 700 papers and books e 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 proposition logic O At the end of 19th century, Charles S. Pierce and Ernst Schroder O Independently, Richar Dedekind o Until mid-1930s, garrett birkhoff developed 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 24, 2014 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 24, 2014 4 / 15

Poset Definition Given a poset A,<>, we can define

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 24, 2014 5 / 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

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 24, 2014 5 / 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

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 24, 2014 5 / 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 o a is greatest if for every b∈A, we have b≤a

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 24, 2014 5 / 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 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 24, 2014 5 / 15

Poset Definition Given a poset A, < and a set Sca

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 24, 2014 6 / 15