Tài liệu Formal Concept Analysis

Formal Concept Analysis Springer Berlin Heidelberg New York Barcelona Hong Kong London Milan Paris Singapore Tokyo Bernhard Ganter · Rudolf Wille Formal Concept Analysis Mathematical Foundations With 105 Figures Springer Prof. Dr. Bernhard GllIttr IMtltut fIIr ~bra Faknltil ftrr Mathematik und Naturwi..enschaften TechniKhe Universitlt Dretden. D~l062 Dre.oden, Germany Prot Dr. Rudnlf Wille Arbeitlgruppe Allgemeine A1gebra Fachbere!ch Mathematik Thchnl.ch. Univenitit Darmstadt D-64l89 Darmatadt, Germany .....,.,. ClP 1SBN-l.3:mM4:O-6lm·5 e-ISBN-13:978-.:J..Ml-59&90~2 00I ! 10.HXnl97"'3-64l~mo~2 SpdDger-Veriag Berlin ~ New YDrk 'flU w.k it subject to ~ An . . uw lWlnId. wblt1lcr the wtdt ar put or the ..-.rIll .. ~ ~ th.t ripu 01 ..... ""'" npdIdnc. r-.e 01 ~ red:tIdr:Ia.. ~ ~ OD lIl1aolIm Qf ba CIf ~ ..,., _ . . . . iD. .... bub. DaplIcIdcm d U. pI1..}.Iir:Fm or pan. th.maI'lI permkle4 anJr adIr tM prm:bioat 01 1M em.w. ~:taw of ~ !J,196.\ la Its GU1'ttIIt ftftk:a,.and f""'M1 ...... tot UK -_tow. _....,.Ioo ___ vm.._~_r.. _ _ ... 4II~~lk:dift~ J!m ne _« pIftIl ciea4Ctt. JIIIII»I. ~ llC.in lib·p1bIatfon doeIlIOt ~ e9I!n I:a. tht-~t!lt ipetific .~tMt.o. ftuua' lRaemptiIta. the:dnut ~ Uld. ,.uiItDJI ud 1I:wrn:IiIn tm"b gnwaIwe.. ~""""* __ "r"" ....... I!ut.,."'...... ' ' 4.' 1 J 0 Cvra-~KOP);d+~lbl:4 ~ G(1, iIdd-free ~ $I'lN l~ -.,,~ ~3I!lw.-, a- Garrett Birkhoff with his application-oriented view of lattice theory! and Hartrnut von Hentig with his critical yet constructive understanding of science 2 have had a decisive influence on the genesis of Formal Concept Analysis. 1 2 G. Birkhoff: Lattice Theory. Amer. Math. Soc., Providence. 1st edition 1940, 2nd (revised) edition 1945, 3rd (new) edition 1967. H. von Hentig: MagieI' odeI' Magistel mands. The Duality Principle for ordered sets. The inverse relation?:: of an order relation < is also an order relation. It is called the dual order of <. A line diagram ofthe dual ordered set (M, :Sld := (M,?::) can be obtained from the line diagram of (M,:S) by a horizontal reflection. If (M,:Sl :::: (N , :Sld, the two orders are called dually isomorphic. We obtain the dual st.atement Ad of an order-theoretic statement A (which apart. from purely logical components only contains the symbol :S), if we replace in A the symbol :S by ?::. A holds for an ordered set, if and only if Ad holds for the dual ordered set. This Duality Principle is used to simplify definitions and proofs. If a theorem asserts two statements that are dual to each ot.her, we usually prove only one of them , the other one follows "dually", i.e. , with the same proof for the dual order. 0.2 Complete Lattice~ 5 Definition 9. Let (J1. <) be an ordered set and A a subset of M. A lower bound of A is an element .5 of Nl with .5 ~ a for all a E A. An upper bound of A is defined dually. If there is a largest element in the set of all lower bounds of A. it is called the infimum of A and is denoted by illf A or AA; dually, a least upper bound is called supremum and denoted by sup A or VA. If A = {.r. y}. we also write .r 1\ .11 for inf A and x V .11 for sup A. Infimum and supremum are frequently also called meet and join. 0 0.2 Complete Lattices Definition 10. An ordered set V := (V,~) is a lattice, if for any two elements J: andy in V the supremum x Vy and the infimum x 1\ y always exist. V is called a complete lattice, if the supremum VX and the infimum AX exist for any subset X of V. Every complete lattice V has a largest element, VV, called the unit element of the lattice, denoted by Iv. Dually, the smallest element OF is called the zero element. 0 .<1>.. . . . . J.i Figure 0.3 Line diagrams of the lattices with five elements. The definition of a complete lattice presupposes that supremum and infimum exist for every subset X, in particular for X = 0. We have A 0 = Iv and V 0 = OF, from which it follows that \/ =j:. 0 for every complete lattice. Every non-empty finite lattice is a complete lattice. We can reconstruct the order relation from the lattice operations infimum and supremum by = x 1\ Y ¢:::::} x V Y = .11. If T is an index set and X := {Xt I t E T} a subset of V, we also write VtET and instead of AX we write AtEI' Xt. x ~ .11 ¢:::::} x instead of VX The operations of the supremum and infimum. respectively, are associative. The familiar particular case of the associative laws. i.e., xl\(yl\z) = (J:l\y)l\z, respectively x V (y V z) = (.1.' V y) V.:. can be generalized as follows: If {Xt It E T} is a set of subsets of V, then ;1:t O. Order-theoretic I·ollndat iOlls (j v (v XI) = V(U XI) tET lET and dually 1\ (I\Xt) = 1\ (U Xt). tET tEl' The Duality Principle for lattices. The definitions of a lattice and a complete lattice. respectively, are self-dual: If (V,:::;) is a (complete) lattice, then so is (V, :::;)d = (V. 2:). Therefore, the Duality Principle for ordered sets carries over to lattices: We obtain the dual statement of an order-theoretic statement, if we replace the symbols:::;, V, 1\, V, 1\, 0\/, Iv etc. by 2:, 1\, V, 1\, V, lv, 0\/ etc. Proposition 1. An ordered set in which the infimum exists for every subset is a complete lattice. Proof. Let X be any subset of the ordered set. We have to prove that the supremum of X exists. The set .5 of all upper bounds of X has an infimum s (even if .5 is empty). Every element of X is a lower bound of S, i.e., :::; s. Hence s itself is all upper bound of X and consequently the supremum. 0 Examples of lattices. 1) For every set M the power-set ;P(}vI) , i.e., the set of all subsets of M, is ordered by set inclusion ~ and (;P(M),~) is a complete lattice. In this case the lattice operations supremum and infimum are set union and intersection. 2) Every closed real interval [a, b] in its natural order forms a complete lattice ([a, b],:::;) with the usual infimum and supremum, respectively. as lattice operations. The ordered set (1Ft <), on the other hand. is a lattice, but it is not complete: It lacks a greatest and a least element. We will give further examples of complete lattices from rnathematics in section 0.3. Definition 11. For an element v of a complete lattice V we define and ('* l\{xEVlv - Xem thêm -