Discrete Mathematics(II) Spring 2013 Lecture 2: Lattice(Im) 1 Introduction In this lecture, we will introduce some special lattices. And a very special structure called a Boolean algebra will be discussed in detail, which has a great many applications in computer science 2 de We have already learned ideal of a ring. A lattice is an algebraic structure which looks like a ring for both have two operations. Similarly, a lattice also has a special structure named as the same Definition 1. A subset I of a lattice L is an ideal if it is a sublattice of L and a E I and aE L imply that a∩a∈I Specially, A proper ideal I of L is prime if a,b∈ L and an b∈ I imply that a∈Iorb∈I. Specially, (0f and L itself are two trivial ideals. Let's consider the following example ad i ample 1. Given a lattice and two sublattices P and I as shown in Figure 1, where P=a, 0f Figure 1: Ideal and prime ideal According to the definition, P is a prime ideal and I is just an ideal. Why is I not prime? Since the intersection of any number of conver sublattices(ideals)is a convex sublattice(ideal) unless void, we can define the convex sublattice generated by a subset H, and the ideal generated by a subset h of the lattice L, provided that H=0. The ideal generated by a subset H will be denoted by id(H), and if H= fal, we write id(a) for id(a); we shall call id(a)a principal ideal. A commonly used notation for id(H)is(H and for id(a) it is(a We first introduce a concept. For an order P, a subset A C P is called down-set if E A and y<a imply that y∈A.Discrete Mathematics (II) Spring 2013 Lecture 2: Lattice(II) Lecturer: Yi Li 1 Introduction In this lecture, we will introduce some special lattices. And a very special structure called a Boolean algebra will be discussed in detail, which has a great many applications in computer science. 2 Ideal We have already learned ideal of a ring. A lattice is an algebraic structure which looks like a ring for both have two operations. Similarly, a lattice also has a special structure named as the same as ideal. Definition 1. 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. Specially, A proper ideal I of L is prime if a, b ∈ L and a ∩ b ∈ I imply that a ∈ I or b ∈ I. Specially, {0} and L itself are two trivial ideals. Let’s consider the following example. Example 1. Given a lattice and two sublattices P and I as shown in Figure 1, where P = {a, 0} and I = {0}. 0 a b 1 I P Figure 1: Ideal and prime ideal According to the definition, P is a prime ideal and I is just an ideal. Why is I not prime? Since the intersection of any number of convex sublattices(ideals) is a convex sublattice(ideal) unless void, we can define the convex sublattice generated by a subset H, and the ideal generated by a subset H of the lattice L, provided that H = ∅. 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. A commonly used notation for id(H) is (H] and for id(a) it is (a]. We first introduce a concept. For an order P, a subset A ⊆ P is called down-set if x ∈ A and y ≤ x imply that y ∈ A. 1