Nous allons présenter les notions fondamentales de l’AFC, les structures conceptuelles qu’elle utilise et le mécanisme de scaling conceptuel qui permet de traiter les contextes non binaires comme nous allons le voir.

QUELQUES ÉLÉMENTS DE LA THÉORIE DES TREILLIS

Dans cette section, nous allons nous contenter d’exposer certaines notions fondamentales de la théorie des treillis.

Ensembles ordonnés

Dans ce qui suit, nous allons énoncer plusieurs définitions et propriétés qui vont servir à la proposition d’algorithmes pour la construction de treillis de concepts.

Définition 1 (ensemble ordonné) Un couple (E,≤) formé d’un ensemble E et d’une relation d’ordre ≤ est appelé ensemble ordonné.

Dans un ensemble ordonné (E,≤), pour une paire d’éléments x, y ∈ E, on dira que x et y sont comparables si x ≤ y ou y ≤ x. Si tous les éléments sont comparables, on dit que l’ordre est total, sinon il n’est que partiel. Pour deux éléments comparables et différents, x ≤ y et x ≠y, on note x < y.

Les éléments d’un ensemble ordonné sont liés par la “relation de couverture” induite par l’ordre. Formellement, la couverture est définie de la manière suivante :

Définition 2 (relation de couverture) Soient (E,≤) un ensemble ordonné et x, y ∈ E. On dit que y couvre x (ou y est un successeur de x, x est un prédécesseur de y), noté x ≺ y, si x < y, x ≤ z < y ⇒ z = x.

Exemple : Dans l’ensemble N des entiers naturels, pour tout x, il n’existe aucun nombre entre x et x+1. Ainsi, le nombre x+1 couvre le nombre x.

Diagramme de Hasse d’une relation d’ordre

Un aspect très utile des ensembles ordonnés est la représentation graphique. En effet, tout ensemble ordonné (E,≤) peut être représenté de façon schématique par un diagramme appelé “‘diagramme de Hasse” qui est un graphe où les nœuds sont les éléments de E et les arcs représentent la relation de couverture entre éléments. La réalisation du diagramme consiste à :
— Étape (i) : ∀x ∈ E, associer un point p(x) dans le plan cartésien,
— Étape (ii) : ∀x, y ∈ E, tel que x ≤ y, tracer un segment l(x, y) entre p(x) et p(y),
— Contraintes : faire l’étape (i) et (ii) en respectant les conditions suivantes :
— Si x ≤ y, alors l’ordonnée de p(x) est inférieure à celle de p(y),
— Un point p(z) ne peut se trouver sur le segment l(x, y) si z ≠ x et z ≠ y.

Éléments particuliers d’un ensemble ordonné 

Définition 3 (Chaîne et antichaîne) Une chaîne d’un ensemble ordonné (E,≤) est une partie S de E tel que quel que soit (x, y) ∈ S² , x ≤ y ou y ≤ x. Un ensemble tel que x≤ y ⇒ x = y est appelé une antichaîne. Une chaîne S (resp. antichaîne) est dite maximale si et seulement si quel que soit l’élément x ∈ E \ S, l’ensemble S∪ {x} n’est pas une chaîne (resp. antichaîne).

Définition 4 (majorant – minorant) Soient (E,≤) un ensemble ordonné et S une partie non vide de E. On dit qu’un élément a est un majorant (respectivement un minorant) de S, si pour tout x de S, x ≤ a (respectivement x ≥ a).

Définition 5 (infimum – supremum) Soient (E,≤) un ensemble ordonné et S une partie non vide de E. L’infimum, ou encore la borne inférieure, noté V² (respectivement supremum ou borne supérieure noté W³ ) de S est le plus grand (respectivement le plus petit) élément, s’il existe, de l’ensemble des minorants (resp. des majorants) de S.