Formal Concept Analysis Exercise Sheet 2, Winter Semester 2015/16 1. Lattice Theory Exercise 1 (line diagram) a) Define: What is a lattice? b) Find a preferably small lattice and draw its line diagram. c) Which of the following line diagrams does not represent a lattice? Why? (i) (ii) (iii) (iv) (v) Exercise 2 (complete lattice) a) Define: What is a complete lattice? b) Can you find a complete lattice among the lattices of Exercise 1c? c) Let P := (M, ≤) be an ordered set such that for every subset X of M the infimum ∧X exists. Show that P is a complete lattice. Exercise 3 Prove the following theorem: Let (L, ≤) be a lattice with supremum and infimum defined as usual. For any elements x, y, z ∈ L, the following holds: (i) x ∧ y = y ∧ x (ii) x ∨ y = y ∨ x (iii) x ∧ (y ∧ z) = (x ∧ y) ∧ z (iv) x ∨ (y ∨ z) = (x ∨ y) ∨ z (v) x ∧ (x ∨ y) = x (vi) x ∨ (x ∧ y) = x (vii) x ∧ x = x (viii) x ∨ x = x Exercise 4 (the first formal concepts) Try to compute all formal concepts of the formal context shown in Table 1.Formal Concept Analysis Exercise Sheet 2, Winter Semester 2015/16 1. Lattice Theory Exercise 1 (line diagram) a) Define: What is a lattice? b) Find a preferably small lattice and draw its line diagram. c) Which of the following line diagrams does not represent a lattice? Why? (i) (ii) (iii) (iv) (v) Exercise 2 (complete lattice) a) Define: What is a complete lattice? b) Can you find a complete lattice among the lattices of Exercise 1c? c) Let P := (M, ≤) be an ordered set such that for every subset X of M the infimum ∧X exists. Show that P is a complete lattice. Exercise 3 Prove the following theorem: Let (L, ≤) be a lattice with supremum and infimum defined as usual. For any elements x, y, z ∈ L, the following holds: (i) x ∧ y = y ∧ x (ii) x ∨ y = y ∨ x (iii) x ∧ (y ∧ z) = (x ∧ y) ∧ z (iv) x ∨ (y ∨ z) = (x ∨ y) ∨ z (v) x ∧ (x ∨ y) = x (vi) x ∨ (x ∧ y) = x (vii) x ∧ x = x (viii) x ∨ x = x Exercise 4 (the first formal concepts) Try to compute all formal concepts of the formal context shown in Table 1.