The multiple facets of the canonical direct implicational basis

Karell Bertet (1) , Bernard Monjardet (2)

1 L3I - Laboratoire Informatique, Image et Interaction - EA 2118
2 CERMSEM - CEntre de Recherche en Mathématiques, Statistique et Économie Mathématique

Closure systems on a set S arises in many areas as relational databases, data-mining, formal concept analysis, artificial intelligence, logical programming or lattice theory. Implicational systems represents an efficient and convenient tool to deal with a closure system, and have been studied in various areas, with different terminology. This paper states the equality between five implicational systems issued from different works and satisfying various properties. The three main properties are the directness, canonical and minimality properties, thus the name canonical direct implicational basis given to this unique implicational system. This paper also gives the link between the canonical direct implicational basis and the Horn functions (via the prime implicants). It concludes by the necessity to compare more closely related works made independantly, and with different terminology in order to take advantage of the results really new.

Les systèmes de fermeture (dits aussi familles de Moore) définis sur un ensemble sont présents dans de nombreux domaines de mathématiques ou d'informatique : bases de données relationnelles, fouille des données, analyse des concepts, intelligence artificielle, programmation logique ou théorie des treillis. Les systèmes d'implications sont un outil efficace pour travailler sur les systèmes de fermeture, qui a été utilisé dans la plupart de ces domaines, mais souvent avec des terminologies différentes. Nous démontrons dans ce papier l'identité de cinq systèmes d'implications étudiés dans des contextes différents et pour des propriétés variées. Les trois principales propriétés de ces systèmes sont celles d'être directs, canoniques et minimaux (d'où le nom de base canonique directe). Nous décrivons aussi le lien entre cette base directe et les fonctions de Horn (via la notion de premier impliquant d'une fonction booléenne). Nous concluons par la nécessité de comparer de façon plus approfondie des travaux faits indépendamment et sous des terminologies variées, mais en fait similaires, afin de pouvoir profiter des résultats réellement nouveaux.

Mots clés: Horn function; lattice; canonical direct basis; closure system; closure operator; implicational system

Mots clés: base canonique directe; opérateur de fermeture; fonction de Horn; système d'implications; système de fermeture; treillis

Domaines: Economies et finances

Karell Bertet, Bernard Monjardet. The multiple facets of the canonical direct implicational basis. 2005. ⟨halshs-00195577⟩