# Problèmes de dénombrement et d’évaluation de bornes concernant les éléments du treillis distributif libre.
## Partie I.

G. Hansel

► To cite this version:

G. Hansel. Problèmes de dénombrement et d’évaluation de bornes concernant les éléments du treillis distributif libre. Partie I. Annales de l’ISUP, 1967, XVI (3), pp.157-218. hal-04083923

HAL Id: hal-04083923

https://hal.science/hal-04083923

Submitted on 27 Apr 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
PROBLÈMES DE DÉNOMBREMENT
ET D'ÉVALUATION

G. HANSEL

<figure><img src="image_2.png" /></figure>
PROBLÈMES DE DÉNOMBREMENT
ET D'ÉVALUATION

G. HANSEL

<figure><img src="image_3.png" /></figure>

EU-108-0830

Riv. Int. Statist. Univ. Paris
SÉRIE A, N° 108, 1-218
Monsieur le Professeur DUGUE m'a inspiré le sujet et a assuré la direction de ce travail.* Ses conseils et sa bienveillance ont été pour moi une aide inestimable. Je le prie de trouver ici l'expression de ma profonde reconnaissance.

Je remercie Monsieur le Professeur PISOT pour l'intérêt qu'il a bien voulu porter à mon travail et l'honneur qu'il m'a fait en acceptant de faire partie du jury de cette thèse.

Je remercie Monsieur le Professeur SCHUTZENBERGER de m'avoir accordé de très fructueux entretiens et de m'avoir proposé un sujet de thèse complémentaire qui m'a vivement intéressé.

<footnote>* Ce travail a fait l'objet d'une soutenance de thèse de Doctorat d'Etat le 2 juin 1967 à la Faculté des Sciences de Paris.</footnote>
La traviata è un luogo di sua own commissione di tutte le dottores d'Età e il 30 settembre 1981

Le lettres de these complémentaires du m's vécument interessent,

laquelle Monseur le Professeur SCHUTZENBERGER de

contredit de faire partie du jury de cette these,

lui voulut porter à mon travail et l'inscrire du l'i m's lui en ac-

ce que j'ai reconnu Monseur le Professeur FROT pour l'inscrit du l'i

les lettres de these reconnues de même que j'en ai ac-

ce que j'ai reconnu Monseur le Professeur FROT pour l'inscrit du l'i

les lettres de these reconnues de même que j'en ai ac-

ce que j'ai reconnu Monseur le Professeur FROT pour l'inscrit du l'i

les lettres de these reconnues de même que j'en ai ac-

ce que j'ai reconnu Monseur le Professeur FROT pour l'inscrit du l'i

les lettres de these reconnues de même que j'en ai ac-

ce que j'ai reconnu Monseur le Professeur FROT pour l'inscrit du l'i

les lettres de these reconnues de même que j'en ai ac-

ce que j'ai reconnu Monseur le Professeur FROT pour l'inscrit du l'i
Introduction

Les éléments du treillis distributif libre jouent, sous différentes
formes, un rôle important dans plusieurs domaines. Les "struc-
tures cohérentes" en fiabilité, les complexes, les fonctions booléennes
croissantes, sont autant d'aspects d'une même réalité mathématique.

Le problème du dénombrement des éléments du treillis dis-
tributif libre T_n à n générateurs a été posé par Dedekind [9] en 1897.
Les travaux de Gilbert [13], Yamamoto [39] et Korobkov [23] ont
permis d'établir les inégalités

$$
\left( \left[ \frac{n}{2} \right] = \text{partie entière de } \frac{n}{2} , C_n^p \text{ coefficient binomial} \right)
$$

L'objet du premier chapitre de ce travail est d'obtenir un ré-
sultat plus précis.

Considérons l'ensemble totalement ordonné B = {0,1}, avec
0 < 1, et soit Bⁿ le produit de n ensembles égaux à B, muni
de la structure d'ordre induite. Une fonction booléenne de n va-
riables est une application f : Bⁿ → B. L'ensemble Iⁿ des
fonctions booléennes croissantes de n variables et le treillis Tⁿ
sont isomorphes. Nous construirons une partition de Bⁿ en sous-
ensembles totalement ordonnés. Les propriétés de cette partition et
l'isomorphisme de Iⁿ et Tⁿ nous permettront de démontrer les
inégalités

$$
2^{c_n^{[\frac{n}{2}]}} < |T_n| < 3^{c_n^{[\frac{n}{2}]}}
$$

Au chapitre 2, nous donnerons une solution à un problème posé
par Korobkov. Etant donnée une fonction booléenne croissante $f \in I_n$,
déterminer un algorithme optimal permettant d'identifier la fonction f par des questions du type : quelle est la valeur de f en a(a ∈ Bⁿ) ?
Soit Ωⁿ l'ensemble des algorithmes possibles et k_f le nombre de questions posées pour identifier la fonction f si l'algorithme utilisé est A.

Nous montrerons que

$$ \min_{A \in \Omega^n} \max_{f \in I_n} k_f^A = C_n^{[\frac{n}{2}]} + C_n^{[\frac{n}{2}]+1} $$

Le chapitre 3 sera consacré à la démonstration d'une conjecture de Z. W. Birnbaum.

Soit un élément x = (x₁, x₂, ..., xᵢ, ..., xⁿ) ∈ Bⁿ. Nous appelons support de x et noterons s(x) l'ensemble

$$ s(x) = \{i \mid 1 \le i \le n, x_i = 1\} $$

Le nombre de coordonnées non nulles de x est |s(x)|. Soit une fonction croissante f ∈ Iₙ et soient Aⱼ et Aⱼ* les ensembles définis par

$$ A_j = \{x \mid x \in B^n, |s(x)| = j \text{ et } f(x) = 1\} $$

$$ A_j^* = \{x \mid x \in B^n, |s(x)| = j \text{ et } f(x) = 0\} $$

Nous montrerons que pour tout j ∈ {1, 2, ..., n-1} est vérifiée l'inégalité

$$ |A_j| \cdot |A_j^*| \le |A_{j+1}| \cdot |A_{j-1}| $$

Au chapitre 4, nous introduirons la notion de schéma de contacts. Un schéma de contacts est défini par la donnée de 3 ensembles, S (les sommets), A (les arêtes), et X (un ensemble de variables booléennes) et de deux applications

- une application Γ qui associe à tout élément a ∈ A un couple non ordonné (s, s') d'éléments de S.

- une application h : A → X.

Alors on peut associer de façon canonique à tout couple (s, s') ∈ S² une fonction booléenne fₛₛ, et l'on dit que le schéma "réalise" fₛₛ. Le problème fondamental est d'obtenir un schéma de contacts réalisant une fonction f donnée avec |A| minimal.

Nous étendrons les résultats de Shannon [37 bis] et Povarov [33] relatifs à la composition des schémas de contacts et exposerons
certains résultats de Hamming et Lupanov utilisés au chapitre suivant.

L'objet du chapitre 5 est de développer une méthode de construction d'un schéma de contacts réalisant une fonction booléenne croissante donnée (quelconque). Cette méthode, qui prend en compte le caractère croissant de la fonction à réaliser, est plus économique que les méthodes antérieures de Shannon [37 bis], Povarov [33] et Lupanov [29] qui visaient essentiellement le cas général.

De même au chapitre 6, nous montrerons que dans la classe des schémas de contacts de type série-parallèle, une fonction booléenne croissante peut être réalisée de façon plus économique qu'une fonction booléenne quelconque.

Le chapitre 7 sera consacré à l'étude d'une fonction booléenne croissante particulière, à savoir la fonction $F_n^2 \in I_n$ définie par

$$F_n^2(x) = \begin{cases} 1 & \text{si } |s(x)| \ge 2 \\ 0 & \text{sinon} \end{cases}$$

Soit $E_n^2$ le nombre minimal de contacts suffisant pour construire un schéma "fermant" de $F_n^2$. Lupanov [28] et Krichevskii [25] ont démontré les inégalités

$$\frac{1}{4} n \log_2 n \le E_n^2 < C_1 n \log_2 n, \text{ où } C_1 \text{ est une constante.}$$

Nous établirons tout d'abord que

$$n \log_2 n \le E_n^2 < (n \log_2 n) \left[ 1 + O \left( \frac{1}{\log_2 n} \right) \right]$$

De ce résultat nous pourrons déduire la valeur exacte* de $E_n^2$

$$\begin{gathered} \text{pour } 2^m \le n \le 2^{m+1} \\ E_n^2 = n(m+2) - 2^{m+1} \end{gathered} \quad (\text{m entier})$$

Nous établirons de plus une condition nécessaire et suffisante pour qu'un schéma "fermant" de $F_n^2$ ait un nombre de contacts minimal.

Au chapitre 8, nous étudierons la fonction booléenne symétrique $S_n^1$ définie par

$$S_n^1(x) = \begin{cases} 1 & \text{si } |s(x)| = 1 \\ 0 & \text{sinon} \end{cases}$$

-----------------

<footnote>* Krichevskii [26], s'appuyant sur nos premiers résultats, a aussi déterminé cette valeur indépendamment.</footnote>
Bien que cette fonction ne soit pas croissante, son étude est grandement facilitée par les résultats concernant la fonction $F_n^2$. Soit $E_{SP}(S_n^1)$ le nombre minimal de contacts suffisant pour construire un schéma de type série-parallèle de $S_n^1$. Korobkov [21] a montré que pour $2^m \le n \le 2^{m+1}$

$$E_{SP}(S_n^1) \le n(m+3) - 2^{m+1}$$

Nous montrerons qu'en fait

$$E_{SP}(S_n^1) = n(m+3) - 2^{m+1}$$

Au chapitre 9, nous introduirons la notion de schéma fonctionnel.

Nous donnerons de la méthode dite "de codage local", un exposé adapté à la construction d'un schéma fonctionnel réalisant une fonction booléenne croissante donnée. Puis, nous définirons un système de codage des fonctions booléennes croissantes qui conduit à une construction sensiblement plus économique que celles développées antérieurement par Reznik [34] Mechiporuk [31] et Korobkov [23].

Enfin au chapitre 10, dont le but est surtout d'ordre bibliographique, nous exposerons certains résultats importants obtenus par Kruskal [40] et Lupanov [41].
# 1. Résultats concernant le dénombrement du treillis distributif libre

## Introduction

Le problème de la détermination du nombre $|T_n|$ des éléments du treillis distributif libre à n générateurs, égal au nombre $|I_n|$ de fonctions booléennes croissantes de n variables, a été posé par Dedekind en 1897 [9]. Il fut résolu par cet auteur pour n = 4.

R. Church le résolut en 1940 [7] pour n = 5

M. Ward fit de même en 1946 [38] pour n = 6

Puis, à nouveau Church calcula ce nombre pour n = 7 en 1965 [8].

D'un autre côté, plusieurs auteurs ont recherché des bornes pour $|I_n|$.

E. N. Gibert a montré en 1953 [13] que $|I_n|$ vérifie les inégalités

$$2^{\frac{n}{2}} < |I_n| < 2^{\frac{n}{2}}$$

avec $\left[\frac{n}{2}\right]$ = partie entière de $\frac{n}{2}$.

Puis, Yamamoto, en 1954 [39], a établi

$$2^{\frac{n}{2}} < |I_n| < (b \sqrt{n}) 2^{\frac{n}{2}}$$

où b est une certaine constante.

Une série de publications de Korobkov de 1962 à 1965 aboutit aux résultats [23]

$$2^{\frac{n}{2}} < |I_n| < 2^{\frac{4.23}{n}} 2^{\frac{n}{2}} (1+\epsilon_n)$$
$$ (\varepsilon_n \longrightarrow 0 \text{ si } n \longrightarrow \infty) $$

$$ \text{et} \quad 2^{\left[\frac{n}{2}\right]} < |I_n| < 32^{\left[\frac{n}{2}\right]} $$

L'objet de ce chapitre [19] est de démontrer les inégalités plus précises

$$ 2^{\left[\frac{n}{2}\right]} < |I_n| < 3^{\left[\frac{n}{2}\right]} $$

# 1. Notations, Rappels [3, 6, 10]

Nous utiliserons les notations courantes de la théorie des ensembles. Signalons cependant quelques particularités : nous écrirons $|A|$ pour désigner le cardinal de l'ensemble $A$ ; si une famille d'ensembles $(E_i)_{i \in I}$ est une partition d'un ensemble $E$, nous écrirons $E = \sum_{i \in I} E_i$ ; enfin, nous noterons $A - B$ le complémentaire de l'ensemble $B \subset A$ par rapport à l'ensemble $A$.

## 1.1 - Ensembles ordonnés - Treillis

1.1.1. - Un ensemble $E$ est ordonné si est définie pour les éléments de cet ensemble une relation binaire notée $\leq$ satisfaisant aux axiomes

- pour tout $a \in E$ $a \leq a$ (réflexivité)

- $a \leq b$ et $b \leq a$ est équivalent à $a = b$ (antisymétrie)

- $a \leq b$ et $b \leq c$ implique $a \leq c$ (transitivité)

Si l'on a $a \leq b$ et $a \neq b$, on note $a < b$.

Dans un ensemble ordonné $E$, on appelle

élément nul ou plus petit élément un élément $0$ tel que

$$ 0 \leq a \text{ pour tout } a \in E; $$

* Une expression asymptotique de ces inégalités est

$$ \sqrt{\frac{2}{\pi}} \frac{2^n}{\sqrt{n}} \left[ 1 + O\left(\frac{1}{n}\right) \right] < \text{Log}_2 |I_n| < 1,58 \times \sqrt{\frac{2}{\pi}} \frac{2^n}{\sqrt{n}} \left[ 1 + O\left(\frac{1}{n}\right) \right] $$
élément universel ou plus grand élément un élément $1$ tel que
$$a \le 1 \text{ pour tout } a \in E.$$

On dit que $b$ couvre $a$ si $a < b$ et s'il n'existe pas $c \in E$ tel que $a < c < b$.

Si pour tout couple $(a, b)$ d'éléments d'un ensemble ordonné $C$, on a $a \le b$ ou $b \le a$, on dit que $C$ est **totalement ordonné** ou est une **chaîne**. La **longueur** d'une chaîne est le nombre de ses éléments.

Soit $E$ un ensemble ordonné.

Une chaîne $a_0 < a_1 < a_2 < \dots < a_1$ ... $a_n$, $a_1 \in E$, telle que $a_1$ couvre $a_{1-1}$ pour tout $i \in \{1, 2, \dots, n\}$ est dite **connexe**.

Soient $a$ et $b$ deux éléments de $E$, avec $a \le b$. L'ensemble des $x$ satisfaisant à $a \le x \le b$ s'appelle **intervalle fermé** $[a, b]$.

### 1.1.2. - Un treillis est un ensemble ordonné tel que pour tout couple d'éléments $(a, b)$ il existe un plus petit majorant (noté $a + b$) et un plus grand minorant (noté $a \cdot b$)*.

Une définition algébrique équivalente est la suivante : un treillis est un ensemble sur lequel sont définies deux opérations, une addition et une multiplication (notées $\dot{+}$ et $\dot{\cdot}$) possédant les propriétés suivantes

$$\text{idempotence} \qquad a \dot{+} a = a \cdot a = a \tag{1}$$

$$\text{commutativité} \qquad a \dot{+} b = b \dot{+} a \qquad a \cdot b = b \cdot a \tag{2}$$

$$\text{associativité} \qquad (a \dot{+} b) \dot{+} c = a \dot{+} (b \dot{+} c), (a \cdot b) \cdot c = a \cdot (b \cdot c) \tag{3}$$

$$\text{absorption} \qquad (a \dot{+} b) \cdot a = a \dot{+} (a \cdot b) = a \tag{4}$$

Un treillis est distributif si de plus, la multiplication est distributive par rapport à l'addition

$$a \cdot (b \dot{+} c) = (a \cdot b) + (a \cdot c) \tag{5}$$

On montre alors que l'addition est aussi distributive par rapport à la multiplication

$$a \dot{+} (b \cdot c) = (a \dot{+} b) \cdot (a \cdot c) \tag{6}$$

<footnote>* Nous noterons $\sum_{i \in I} a_i$ et $\prod_{i \in I} (a_i)$ respectivement le plus petit majorant et le plus grand minorant d'une famille d'éléments $(a_1)_{i \in I}$</footnote>
## 1. 2 - Algèbres booléennes

Soit un treillis possédant un élément nul $0$ et un élément universel $1$.

On appelle *complément* d'un élément $a$, tout élément $\bar{a}$ vérifiant les égalités

$$ \{ a \oplus \bar{a} = 1 \} \qquad (7) $$

$$ \{ a . \bar{a} = 0 \} \qquad (8) $$

Soit un intervalle fermé $[a, b]$ d'un treillis $T$. Un élément $x \in [a, b]$ est dit relativement complémenté dans $[a, b]$ s'il existe $y \in T$ tel que

$$ \{ \begin{array}{l} x \oplus y = b \\ x . y = a \end{array} \} $$

(y s'appelle *complément relatif* de x dans $[a, b]$).

Un treillis $T$ est complémenté si tout élément $a \in T$ possède au moins un complément $\bar{a}$.

Un treillis distributif et complémenté s'appelle *un treillis de Boole* ou encore une *algèbre de Boole*.

Dans une algèbre de Boole tout élément $x$ appartenant à un intervalle fermé $[a, b]$ possède un complément relatif et un seul dans $[a, b]$.

La complémentation est alors une opération possédant la propriété

$$ \bar{a} = a \qquad (9) $$

On montre également les règles de Morgan :

$$ \bar{a} \oplus \bar{b} = \overline{a . \bar{b}} \qquad (10) $$

$$ \overline{a \oplus b} = \overline{a . \bar{b}} \qquad (11) $$

## 1. 3 Sous-treillis - Sous-algèbres - Homomorphismes

1.3.1. - Un sous-treillis $T'$ d'un treillis $T$ (respectivement une sous-algèbre $A'$ d'une algèbre booléenne $A$) est un sous-ensemble
T' ⊂ T qui est un treillis pour les opérations + et . définies sur T (respect. un sous-ensemble $A' ⊂ A$ qui est une algèbre booléenne pour les opérations $\oplus, \_,$ - définies sur $A$).

**1.3.2.** - Etant donné un sous-ensemble $X ⊂ T$ (respectivement $X ⊂ A$), on appelle sous-treillis $T'$ engendré par $X$ (respect. sous-algèbre $A'$ engendrée par $X$), l'ensemble des éléments de $T$ (respect. de $A$) que l'on peut obtenir à partir des éléments de $X$ en appliquant un nombre fini de fois les opérations $\oplus$ et . (respectivement $\oplus, \_,$ -).

Les éléments de $X$ sont appelés générateurs de $T'$ (respect. de $A'$).

**1.3.3.** - Soient deux treillis $T$ et $T'$. Une application $f: T \rightarrow T'$ est un homomorphisme si quels que soient $x$ et $y \in T$, on a

$$ \begin{cases} f(x \oplus y) = f(x) \oplus f(y) \\ f(x \_ y) = f(x) \_ f(y) \end{cases} $$

Soient deux algèbres booléennes $A$ et $A'$. Une application $f: A \rightarrow A'$ est un homomorphisme si, quels que soient $x$ et $y \in A$ sont vérifiées les relations précédentes et si de plus

$$ f(\bar{x}) = \bar{f(x)} $$

## 1.4 - Treillis distributif et algèbre booléenne libres

Un treillis distributif $T_n$ (respect. une algèbre booléenne $\mathcal{A}_n$) est libre à n générateurs s'il est engendré (respect. si elle est engendrée) par un ensemble $X$ de cardinal $n$ et si, étant donné un treillis distributif quelconque $T$, (respect. étant donnée une algèbre booléenne quelconque $A$) toute application $f: X \rightarrow T$ (respect. $f: X \rightarrow A$) peut être prolongée en un homomorphisme de $T_n$ dans $T$ (respect. de $\mathcal{A}_n$ dans $A$).

Deux treillis distributifs (respect. deux algèbres booléennes) libres à n générateurs sont isomorphes. Nous parlerons donc du treillis distributif libre $T_n$ (de l'algèbre booléenne libre $\mathcal{A}_n$) à n générateurs. Nous noterons $x_1^*, x_2^*, \dots, x_n^*$ les générateurs de $T_n$ (ou de $\mathcal{A}_n$).

Un produit de générateurs sera appelé produit fondamental de $T_n$ (ou de $\mathcal{A}_n$).
Un produit de la forme $\prod_{i=1}^{n} \tilde{x}_{i}^{*}$, où $\tilde{x}_{i}^{*} = x_{i}^{*}$ ou $\bar{x}_{i}^{*}$ sera appelé produit élémentaire de $\alpha_{n}$.

**PROPOSITION 1.** — Soit $\{p, a_1, a_2, \dots, a_k\}$ un ensemble de produits fondamentaux de $T_n$.

$$1/ \text{L'égalité } p = \sum_{i=1}^{k} p a_i \text{ implique qu'il existe } i \in \{1, 2, \dots, k\} \\ \text{tel que } p = p a_1$$

$$2/ \text{L'inégalité } p \le \sum_{i=1}^{k} a_i \text{ implique qu'il existe } i \in \{1, 2, \dots, k\} \\ \text{tel que } p \le a_1.$$

**DÉMONSTRATION.** — 1/ L'ensemble totalement ordonné $B = \{0, 1\}$ (avec $0 < 1$) est un treillis distributif. Supposons par exemple que $p = \prod_{i=1}^{j} x_i^*$ et considérons l'application $f : X \to B$ définie par

$$f(x_1^*) = \begin{cases} 1 & \text{si } i \in \{1, 2, \dots, j\} \\ 0 & \text{sinon} \end{cases}$$

Supposons que $f$ puisse être prolongée en un homomorphisme de $T_n$ dans $B$. Il en résulte que

$$f(p) = \prod_{i=1}^{j} f(x_i^*) = 1$$

$$f(p) = \sum_{i=1}^{k} f(p) \cdot f(a_i) = \sum_{i=1}^{k} f(a_i)$$

Donc, il existe $i \in \{1, 2, \dots, k\}$ tel que $f(a_i) = 1$. Par suite, $a_1$ est produit de générateurs du sous-ensemble $\{x_1^*, x_2^*, \dots, x_j^*\}$ et $p a_1 = p$.

$$2/ \quad p \le \sum_{i=1}^{k} a_i \text{ implique } p = p \sum_{i=1}^{k} a_i = \sum_{i=1}^{k} p a_i$$

Donc, il existe (d'après 1/) $i \in \{1, 2, \dots, k\}$ tel que $p = p a_1$ soit $p \le a_1$.

**PROPOSITION 1 bis.** — Soient $q, b_1, b_2, \dots, b_k$ un ensemble de produits élémentaires de $\alpha_n$.

L'inégalité $q \le \sum_{i=1}^{k} b_i$ implique qu'il existe $i \in \{1, 2, \dots, k\}$ tel que $q = b_1$.
En effet $q \le \sum_{i=1}^{k} b_i$ implique $q = q \sum_{i=1}^{k} b_i = \sum_{i=1}^{k} q b_i$

or
$$ q b_i = \begin{cases} q & \text{si } q = b_i \\ 0 & \text{sinon} \end{cases} $$

**PROPOSITION 2.** – La décomposition d'un élément de $T_n$ en somme de produits fondamentaux incomparables existe et est unique.

L'existence d'une telle décomposition découle directement des propriétés de l'addition et de la multiplication dans $T_n$. Supposons qu'un élément $a \in T_n$ possède deux décompositions en somme de produits fondamentaux incomparables

$$ a = u_1 \dot{+} u_2 \dot{+} \dots \dot{+} u_i \dot{+} \dots \dot{+} u_r = v_1 \dot{+} v_2 \dot{+} \dots \dot{+} v_j \dot{+} \dots \dot{+} v_s $$

pour tout $i \in \{1, 2, \dots, r\}$, $u_i \le \sum_{j=1}^{s} v_j$, donc il existe $v_j$ tel que $u_i \le v_j$ (proposition 1) et de même, il existe $u_k$ tel que $v_j \le u_k$; par suite $u_1 \le v_j \le u_k$. Les éléments $u_j$ étant incomparables $u_1 = v_j = u_k$.

Les $u_i$ et $v_j$ sont égaux par paires.

Convention. – Dans la suite, nous ajouterons conventionnellement au treillis $T_n$ un élément nul $0$ et un élément universel $1$.

Exemple. – Le treillis distributif libre à 3 générateurs est représenté sur le tableau 1.

**PROPOSITION 3.** – La décomposition d'un élément de $\mathcal{A}_n$ comme somme de produits élémentaires distincts existe et est unique.

La démonstration de cette proposition est tout à fait similaire à celle de la proposition précédente. La proposition 1 bis est utilisée au lieu de la proposition 1.

## 1.5 - Fonctions booléennes et treillis libres

### 1.5.1. – Le treillis $B^n$.

Nous noterons $B$ l'ensemble totalement ordonné composé des deux éléments $0$ et $1$ (avec $0 < 1$) et $B^n$ le produit de n ensembles égaux à $B$.
<figure><img src="image_4.png" /><figcaption>Tableau I</figcaption></figure>

Bⁿ est ordonné par la relation

$(x_1, x_2, \dots, x_n) \le (y_1, y_2, \dots, y_n) \iff x_1 \le y_1 \text{ pour tout } i \in \{1, 2, \dots, n\}$

B et Bⁿ sont des treillis de Boole. Les règles de calcul dans B et dans Bⁿ sont les suivantes

$$
\begin{array}{l@{\qquad}l}
\text{a)} &
  \left.
  \begin{array}{@{}l@{}}
    1 \div 1 = 1 \div 0 = 0 \div 1 = 1. \ 1 = 1 \\
    0.0 = 0.1 \approx 1.0 = 0 \div 0 = 0
  \end{array}
  \right\} (12)
\end{array}
$$
$$ \left. \begin{array}{l} \bar{1} = 0 \\ \bar{0} = 1 \end{array} \right\} \qquad (13) $$

b) Soient $x = (x_1, x_2, ..., x_n)$ et $y = (y_1, y_2, ..., y_n)$ deux éléments de $B^n$.

$$ \text{On a} \quad \left. \begin{array}{l} x \oplus y = (x_1 \oplus y_1, x_2 \oplus y_2, \dots, x_n \oplus y_n) \\ x \cdot y = (x_1 \cdot y_1, x_2 \cdot y_2, \dots, x_n \cdot y_n) \end{array} \right\} \qquad (14) $$

$$ \bar{x} = (\bar{x}_1, \bar{x}_2, \dots, \bar{x}_n) \qquad (15) $$

Soit un élément $a = (a_1, a_2, ..., a_n) \in B^n$.

Nous appellerons *support de* $a$ et noterons $s(a)$ l'ensemble

$$ s(a) = \{i \mid 1 \le i \le n, a_i = 1\} $$

Al'élément $a \in B^n$, nous associons

un produit fondamental $\Phi_a \in T_n$ défini par

$$ \Phi_a = \prod_{i \in s(a)} x_i^* \quad (\text{si } a = (0, 0, \dots, 0), \text{ on pose } \Phi_a = 1) $$

un produit élémentaire $\chi_a \in \alpha_n$ défini par

$$ \chi_a = \prod_{i \in s(a)} x_i^* \cdot \prod_{j \notin s(a)} \bar{x}_j^* $$

*Exemple.* - A l'élément $a = (0101) \in B^4$ sont associés le produit fondamental $x_2^* \cdot x_4^*$ et le produit élémentaire $\bar{x}_1^* \cdot \bar{x}_2^* \cdot \bar{x}_3^* \cdot \bar{x}_4^*$.

### 1.5.2. - Fonctions booléennes

Une fonction booléenne de $n$ variables est une application $f: B^n \to B$. Nous noterons $\mathfrak{F}_n$ l'ensemble des fonctions booléennes de $n$ variables.

Une fonction booléenne est *croissante* si

$$ x \text{ et } y \in B^n, x \le y \implies f(x) < f(y) $$

Nous noterons $I_n$ l'ensemble des fonctions booléennes croissantes de $n$ variables.

Nous appellerons *ensemble caractéristique* $K_f$ d'une fonction booléenne $f$, l'ensemble défini par

$$ K_f = \{x \mid x \in B^n, f(x) = 1\} $$
Nous appellerons *ensemble fondamental* $M_f$ d'une fonction booléenne $f$, l'ensemble des éléments minimaux de son ensemble caractéristique $K_f$.

La donnée de $K_f$ définit parfaitement une fonction booléenne $f$.

Soit une fonction booléenne croissante $g$ et $M_g$ son ensemble fondamental. Pour tout $x \in B^n$, $g(x) = 1$ si et seulement si il existe $a \in M_g$ avec $a \le x$ et $g(a) = 1$.

Par conséquent, la donnée de $M_g$ définit parfaitement une fonction booléenne croissante $g$.

Nous ordonnons l'ensemble $\mathfrak{F}_n$ par la relation : $f \le g$ si et seulement si $K_f \subseteq K_g$.

Pour cette relation d'ordre, l'ensemble $I_n$ est un treillis distributif et l'ensemble $\mathfrak{F}_n$ est une algèbre booléenne.

Soient $f$ et $g$ deux fonctions de $\mathfrak{F}_n$ ayant pour ensembles caractéristiques $K_f$ et $K_g$.

$f, g$ est la fonction ayant pour ensemble caractéristique $K_f \cap K_g$

$f+g$ est la fonction ayant pour ensemble caractéristique $K_f \cup K_g$

$\bar{f}$ est la fonction ayant pour ensemble caractéristique $B^n - K_f$

### 1.5.3. - Isomorphismes entre $\mathcal{A}_n$ et $\mathfrak{F}_n$ et entre $T_n$ et $I_n$

**PROPOSITION 4.** - L'ensemble $I_n$ des fonctions booléennes croissantes de n variables et le treillis distributif libre $T_n$ à n générateurs sont isomorphes.

A une fonction $f \in I_n$ associons l'élément $t_f \in T_n$ défini par

$$t_f = \sum_{a \in M_f} \Phi_a$$

(si $M_f = \emptyset$ on pose $t_f = 0$)

(si $M_f = \{(0, 0, \dots, 0)\}$ on pose $t_f = 1$)

La famille d'éléments $(\Phi_a)_{a \in M_f}$ est constituée de produits fondamentaux incomparables. Il résulte de la proposition 2 que l'application $f \to t_f$ est une bijection de $I_n$ sur $T_n$.
D'autre part, soient deux fonctions $f$ et $g \in I_n$ et sup-
posons $f \le g$. Alors quel que soit $a \in M_f$, il existe $a' \in M_g$
avec $a' \le a$ et par suite $\Phi_a \le \Phi_{a'}$ d'où il résulte que $t_f \le t_g$.

L'application $f \to t_f$ est donc un isomorphisme de $I_n$ sur $T_n$.

Désormais, nous identifierons chaque fonction booléenne crois-
sante $f \in I_n$ avec l'élément $t_f \in T_n$ correspondant. Soit $a \in B^n$
le produit fondamental $\Phi_a \in T_n$ s'identifie à la fonction $\Phi_a \in I_n$
définie par

$$
\Phi_a(x) = \prod_{i \in S(a)} x_i \quad (\text{où } x = (x_1, x_2, \dots, x_n) \in B^n).
$$

En particulier, la fonction $g$ définie par

$$
g(x_1, x_2, \dots, x_n) = x_i
$$

s'identifie avec le générateur $x_i^*$ de $T_n$.

La fonction $f \in I_n$ ayant pour ensemble fondamental $M_f$ est
définie par

$$
f(x) = \sum_{a \in M_f} \Phi_a(x) = \sum_{a \in M_f} \prod_{i \in s(a)} x_i
$$

PROPOSITION 5. — L'ensemble $\mathfrak{F}_n$ des fonctions booléennes de n variables et l'algèbre booléenne libre $\mathfrak{A}_n$ où n générateurs sont isomorphes.

A une fonction $f \in \mathfrak{F}_n$ associons l'élément $\alpha_f \in \mathfrak{A}_n$ défini par

$$
\alpha_f = \sum_{a \in K_f} \chi_a.
$$

La famille d'éléments $(\alpha_a)_{a \in K_f}$ est constituée de produits élé-
mentaires distincts de $\mathfrak{A}_n$. De la proposition 3, il résulte que
l'application $f \to \alpha_f$ est bijective.

De plus $f \le g \to K_f \subset K_g \to \alpha_f \le \alpha_g$. Il y a donc isomorphisme entre $\mathfrak{F}_n$ et $\mathfrak{A}_n$.

Désormais, nous identifierons chaque fonction booléenne $f \in \mathfrak{F}_n$
avec l'élément $\alpha_f \in \mathfrak{A}_n$ correspondant. Le produit fondamental
$\chi_a \in \mathfrak{A}_n$ s'identifie à la fonction $\chi_a \in \mathfrak{F}_n$ définie par

$$
\chi_a(x) = \prod_{i \in S(a)} x_i . \prod_{j \in S(a)} \bar{x}_j
$$
La fonction $f \in \mathfrak{F}_n$ ayant pour ensemble caractéristique $K_f$ est définie par

$$f(x) = \sum_{a \in K_f'} \chi_a(x)$$

## 2. Partition de $B^n$ en chaînes connexes [19]

### 2.1. - THÉORÈME 1. - Il existe une partition du treillis de Boole $B$ en $C_n^{[\frac{n}{2}]}$ chaînes connexes qui a les propriétés suivantes

1/ Le nombre de chaînes de longueur $n-2p+1$ est $C_n^p - C_n^{p-1}$
$$ (0 \le p \le \lfloor \frac{n}{2} \rfloor, \text{ et on pose } C_n^{-1} = 0). $$

2/ Etant donnés trois éléments $a_1 < a_2 < a_3$ de $B^n$ formant une chaîne connexe et appartenant à une même chaîne de longueur $n-2p+1$, le complément relatif de $a_2$ dans l'intervalle fermé $[a_1, a_3]$ appartient à une chaîne de longueur $n-2p-1$.

### DÉMONSTRATION. - Pour $n=1, 2$ le théorème est vrai. Supposons $n > 2$.

1/ a) Posons

$$B_0^n = \{x \mid x = (x_1, x_2, \dots, x_n) \in B^n \text{ et } x_n = 0\}$$

$$B_1^n = \{x \mid x = (x_1, x_2, \dots, x_n) \in B^n \text{ et } x_n = 1\}$$

Les ensembles $B_0^n$ et $B_1^n$ constituent une partition de $B^n$.

Les applications

$$x^0 = (x_1, x_2, \dots, x_{n-1}, 0) \longrightarrow x^1 = (x_1, x_2, \dots, x_{n-1}, 1)$$

et

$$x^0 = (x_1, x_2, \dots, x_{n-1}, 0) \longrightarrow (x_1, x_2, \dots, x_{n-1})$$

établissent un isomorphisme entre $B_0^n, B_1^n$ et $B^{n-1}$.

b) Par hypothèse de récurrence, il existe des partitions de $B_0^n$ et $B_1^n$ en $C_{n-1}^{[\frac{n-1}{2}]}$ chaînes connexes ayant les propriétés énoncées dans le théorème. Nous supposons ces partitions isomorphes (dans l'isomorphisme $x^0 \longrightarrow x^1$). Elles définissent une partition de $B^n$ ("partition initiale").
Soient $J_0$ une chaîne de $B_0^n$, $y_0$ son plus grand élément, $J_1$ la chaîne de $B_1^n$ isomorphe de $J_0$, $y_1$ son plus grand élément image de $y_0$. $y_1$ couvre $y_0$ dans $B^n$.

Les ensembles $J = J_0 + \{y_1\}$ et $J' = J_1 - \{y_1\}$ sont donc des chaînes connexes de $B^n$.

On a

$$|J| = |J_0| + 1 \quad \text{et} \quad |J'| = |J_1| - 1$$

Nous conservons $J$ et $J'$ dans la partition finale recherchée de $B^n$.

c) La même construction est effectuée pour tous les couples de chaînes isomorphes de $B_0^n$ et de $B_1^n$.

Par conséquent, chaque chaîne de longueur $k$ de la partition initiale de $B_0^k$ (resp. de $B_1^k$) donne naissance à une chaîne de longueur $k+1$ (resp. $k-1$) de la partition finale de $B^n$. Par hypothèse de récurrence, le nombre de chaînes de longueur $n-2p$ (resp. $n-2p+2$) de la partition initiale de $B_0^n$ (resp. de $B_1^n$) est
$$C_{n-1}^p - C_{n-1}^{p-1} \quad (\text{resp. } C_{n-1}^{p-1} - C_{n-1}^{p-2}) \quad \text{avec } 0 \le p \le \lfloor \frac{n-1}{2} \rfloor \quad (\text{resp. } 1 \le p \le \lfloor \frac{n}{2} \rfloor).$$

Le nombre de chaînes de longueur $n-2p+1$ de la partition finale de $B^n$ est donc

$$C_{n-1}^p - C_{n-1}^{p-1} + C_{n-1}^{p-1} - C_{n-1}^{p-2} = C_n^p - C_n^{p-1} \quad (\text{avec } 0 \le p \le \lfloor \frac{n}{2} \rfloor)$$

Le nombre total de chaînes est $C_n^{\lfloor \frac{n}{2} \rfloor}$.

2/ Soient 3 éléments $a_1 < a_2 < a_3$, connexes, appartenant à l'une des chaînes de la partition finale obtenue et soit $a_1' \le a_2 \le a_3$. Par hypothèse de récurrence si $a_1$ et $a_3$ appartiennent à une chaîne de longueur $n-2p$ (resp. $n-2p+2$) de la partition initiale de $B_0^n$ (resp. de $B_1^n$), $a_1'$ appartient à une chaîne de longueur $n-2p-2$ (resp. $n-2p$) de cette partition ; donc dans la partition finale de $B^n$, $a_2$ appartient à une chaîne de longueur $n-2p+1$ et $a_2'$ à une chaîne de longueur $n-2p-1$.

Deux cas sont possibles :

a) Les trois éléments $a_1, a_2, a_3$ appartiennent au même sous-ensemble $B_0^n$ (resp. $B_1^n$) ; il en est alors de même de $a_2'$ ; par hypothèse de récurrence si $a_1$ et $a_3$ appartiennent à une chaîne de longueur $n-2p$ (resp. $n-2p+2$) de la partition initiale de $B_0^n$ (resp. de $B_1^n$), $a_2'$ appartient à une chaîne de longueur $n-2p-2$ (resp. $n-2p$) de cette partition ; donc dans la partition finale de $B^n$, $a_2$ appartient à une chaîne de longueur $n-2p+1$ et $a_2'$ à une chaîne de longueur $n-2p-1$.
b) $a_1, a_2 \in B_0^n$ et $a_3 \in B_1^n$. Soient $J_0$ et $J_1$ les chaînes isomorphes des partitions initiales de $B_0^n$ et de $B_1^n$ contenant $a_1$ et $a_2$ d'une part, $a_3$ d'autre part.

Soit $n-2p$ leur longueur.

$a_1$ et $a_2$ sont les deux plus grands éléments de $J_0, a_3$ est le plus grand élément de $J_1$ et est l'image de $a_2$ dans l'iso-morphisme $x^0 \to x^1$. Soit $b$ l'élément de $J_1$ couvert par $a_3$. $b$ est l'image de $a_1$.

On a donc $a_1 < b < a_3$ et $b$ est le complément relatif de $a_2$ dans l'intervalle fermé $[a_1, a_3]$ soit $b = a_2$.

Dans la partition finale de $B^n$, $a_2$ appartient à une chaîne de longueur $n-2p+1$ et $a'_2$ à une chaîne de longueur $n-2p-1$.

NOTATIONS. — Nous noterons $\pi_n$ la partition en chaînes de $B^s$ obtenue, $\mathcal{K}_{n-2p+1}$ l'ensemble des chaînes de longueur $n-2p+1$, $\mathcal{K}_{n-2p+1}^0$ (resp. $\mathcal{K}_{n-2p+1}^1$) les chaînes de $\mathcal{K}_{n-2p+1}$ obtenues à partir des chaînes initiales de $B_0^n$ par addition d'un élément (resp. de $B_1^n$ par suppression d'un élément).

Nous noterons $K_{n-2p+1}$ l'ensemble des éléments de $B^n$ appartenant à l'une des chaînes de $\mathcal{K}_{n-2p+1}$

$$K_{n-2p+1} = \bigcup_{j \in \mathcal{K}_{n-2p+1}} J$$

Le tableau 2 indique les partitions en chaînes de $B^1, B^2, B^3, B^4, B^5$.

## 2.2. - Suite adjointe - Propriétés

Soit une chaîne

$$J = \{a_1 < a_2 < \dots < a_{1-1} < a_1 < a_{1+1} < \dots < a_{n-2p+1}\} \in \mathcal{K}_{n-2p+1}$$

Désignons par $a'_1, 2 \le i \le n-2p$ le complément relatif de $a_1$ dans l'intervalle fermé $[a'_{1-1}, a'_{1+1}]$.

La suite $J' = (a'_2, a'_3, \dots a'_1, \dots a'_n)_{n-2p}$ sera appelée suite adjointe de la chaîne $J$.
Il résulte du théorème 1 que les éléments de $J'$ appartiennent à $K_{n-2p-1}$.

Les propriétés d'ordre des $a'_i$ sont précisées par la proposition suivante
<figure><img src="image_5.png" /><figcaption>Tableau 2</figcaption></figure>

PROPOSITION 6 (figure 1). - Soient $a'_{1-1}$, $a'_{1}$, $a'_{1+1}$ trois éléments successifs de la suite adjointe J' d'une chaîne $J \in \mathcal{K}_{n-2p+1}$ ($n-2p+1 \ge 3$)

$$1/ a'_{1-1} < a'_{1+1} \text{ quel que soit } i \in \{3, 4, \dots, n-2p-1\}$$

$$2/ a'_{1} \text{ et } a'_{1+1} \text{ sont des éléments incomparables quel que soit } i \in \{2, 3, \dots, n-2p-1\}.$$
## DÉMONSTRATION. -

1. On a $a'_{i-1} < a_i < a'_{i+1}$ par définition des nombres $a_i$.

2. $a_i$ et $a'_{i+1}$ sont incomparables. En effet, si l'on avait $a_i < a'_{i+1}$ ceci entrainerait $a_{i+1} = a_i + a'_i < a'_{i+1}$ ce qui est impossible.

Si l'on avait $a'_{i+1} < a_i$ ceci entrainerait $a_i < a'_{i+1} < a_i$, également impossible.

<figure><img src="image_6.png" /><figcaption>Fig. 1</figcaption></figure>

# 3. Étude du nombre $I_n$

## 3.1. - Éléments déterminés et indéterminés pour une fonction croissante

Considérons une chaîne $J \in \mathcal{K}_{n-2p+1}$, $n-2p+1 \ge 3$, J' sa suite adjointe et une fonction croissante $f \in I_n$.
Soit un élément $a_i \in J$. De la proposition 6, il découle
que

si $f(a'_{1-1}) = 1$ on a $f(a_1) = 1$ (puisque $f$ est croissante)

si $f(a'_{1+1}) = 0$ on a $f(a_1) = 0$

Si l'une de ces éventualités est réalisée, nous dirons que l'élément $a_i$ est "déterminé" pour la fonction $f$.

Si au contraire $f(a'_{1-1}) = 0$ et $f(a'_{1+1}) = 1$, nous dirons que $a_1$ est "indéterminé" pour $f$.

### 3.2. - Notations

Nous noterons $I_n(E)$ l'ensemble des applications croissantes définies sur un sous-ensemble $E \subset B^n$ et à valeurs dans $B$.

Soient deux sous-ensembles $E$ et $F$ de $B^n$ avec $F \subset E$ et soit une application $f$ définie sur un ensemble contenant $F$ et à valeurs dans $B$. Nous noterons $I_n(E, f, F)$ l'ensemble des applications croissantes de $E$ dans $B$ coincidant avec $f$ sur l'ensemble $F$.

### 3.3. - PROPOSITION 7. - Soient une chaîne $J \in \pi_n$, $J'$ sa suite adjointe, et une fonction croissante quelconque $f \in I_n$.

1. Le nombre d'éléments indéterminés de $J$ pour la fonction $f$ est 0 ou 2.

$$2/ |I_n(J \cup J', f, J')| = 1 \text{ ou } 3,$$

DÉMONSTRATION. - Supposons que $J \in \mathcal{K}_{n-2p+1} (n-2p+1 \ge 3)$ et considérons la suite des valeurs de $f$ sur $J'$

$$f(a_2'), f(a_3'), \dots, f(a_{1-1}'), f(a_1'), f(a_{1+1}'), \dots, f(a_{n-2p})'$$

Il découle de la proposition 6 que deux cas seulement sont possibles

a) Il existe $i \in \{1, 2, \dots, n-2p+1\}$ tel que

$$f(a_2') = f(a_3') = \dots = f(a_1') = 0$$

et

$$f(a_{1+1}') = f(a_{1+2}') = \dots = f(a_{n-2p}') = 1$$

(les cas $i=1$ et $i=n-2p+1$ correspondent respectivement à des suites composées entièrement de 1 et de 0).
Seuls les éléments $a_i$ et $a_{i+1}$ de $J$ sont indéterminés pour $f$.

D'autre part, soit une fonction $g \in I_n(J \cup J', f, J')$.

$$ \text{On a} \qquad g(a_j) = \begin{cases} 0 & \text{pour tout } j \le i - 1 \\ 1 & \text{pour tout } j \ge i + 2 \end{cases} $$

Aux points $a_i$ et $a_{i+1}$ trois cas sont possibles:

$$ g(a_1) = g(a_{1+1}) = 0 $$

$$ g(a_1) = 0 \text{ et } g(a_{1+1}) = 1 $$

$$ g(a_1) = g(a_{1+1}) = 1 $$

donc $|I_n(J \cup J', f, J')| = 3$.

b) Il existe $i \in \{2, 3, \dots, n-2p-1\}$ tel que

$$ f(a_i) = 1 \text{ et } f(a_{i+1}) = 0. $$

Aucun élément de $J$ n'est indéterminé.

Soit $g \in I_n(J \cup J', f, J')$.

$$ \text{on a} \qquad g(a_j) = \begin{cases} 0 & \text{pour tout } j < i \\ 1 & \text{pour tout } j \ge i + 1 \end{cases} $$

et par suite $|I_n(J \cup J', f, J')| = 1$.

### THÉORÈME 2 [19]. – Le nombre $|I_n|$ de fonctions booléennes croissantes de $n$ variables vérifie les inégalités*

$$ 2^{\left\lfloor \frac{n}{2} \right\rfloor} < |I_n| < 3^{\left\lfloor \frac{n}{2} \right\rfloor} \quad \left( \left\lfloor \frac{n}{2} \right\rfloor = \text{partie entière de } \frac{n}{2} \ , \ n > 1 \right) $$

### DÉMONSTRATION. – a) Borne inférieure.

La borne inférieure de $|I_n|$ s'obtient en définissant une classe particulière de fonctions croissantes. Considérons dans $I_n$ les produits fondamentaux de $\left\lfloor \frac{n}{2} \right\rfloor$ générateurs. Ces produits sont au nombre de $C_n^{\left\lfloor \frac{n}{2} \right\rfloor}$ et sont deux à deux incomparables.

• Si $n$ est pair, la borne supérieure peut même s'écrire

$$ 3^{\left\lfloor \frac{n}{2} \right\rfloor} \times 2^{\left\lfloor \frac{n}{2} \right\rfloor - 1} $$
$$c_n^{[\frac{n}{2}]}$$

D'après la proposition 2, il existe $2^{\frac{n}{2}}$ fonctions crois-santes différentes que l'on peut construire avec ces produits fondamentaux.

b) Borne supérieure.

Distinguons deux cas suivant la parité de n.

1/ n impair.

Considérons la partition de $B^n$

$$B^n = K_2 + K_4 + \dots + K_{21} + \dots + K_{n+1} \quad \text{; on a} \quad I_n(K_2) \le 3^{|\mathcal{X}_2|}$$

En effet, sur chaque chaîne de $\mathcal{K}_2$ une fonction croissante quelconque ne peut prendre que 3 couples de valeurs possibles.

$$\text{Puis} \quad I_n(K_2 \cup K_4) < I_n(K_2) \times \max_{f \in I_n} |I_n(K_2 \cup K_4, f, K_2)|$$

(L'inégalité est stricte car on peut construire une fonction de $I_n(K_2 \cup K_4)$ pour laquelle il existe une chaîne de $\mathcal{K}_4$ sans éléments indéterminés).

Soit une chaîne $J \in \mathcal{K}_4$ et soit $J'$ sa suite adjointe. D'après le théorème 1 les éléments de $J'$ sont contenus dans $K_2$ et il découle de la proposition 7 que

$$\max |I_n(K_2 \cup K_4, f, K_2)| \le 3^{|\mathcal{X}_4|}$$

Par suite

$$|I_n(K_2 \cup K_4)| < 3^{|\mathcal{X}_2| + |\mathcal{X}_4|}$$

En raisonnant par récurrence

$$|I_n| = |I_n(K_2 \cup K_4 \cup \dots \cup K_{n+1})| < 3^{|\mathcal{X}_2| + |\mathcal{X}_4| + \dots + |\mathcal{X}_{n+1}|} = 3^{c_n^{[\frac{n}{2}]}}$$

2/ n pair

$$B^n = K_1 + K_3 + \dots + K_{21+1} + \dots + K_{n+1}$$

$$|I_n(K_1)| = 2^{|\mathcal{X}_1|}$$

Le raisonnement s'achève comme précédemment et l'on obtient

$$|I_n| < 2^{|\mathcal{X}_1|} \times 3^{|\mathcal{X}_3| + \dots + |\mathcal{X}_{n+1}|} < 3^{c_n^{[\frac{n}{2}]}},$$
## 2. Identification d'une fonction booléenne croissante

### Introduction

Nous définirons plus loin une certaine classe $\Omega_n$ d'algorithmes permettant de reconstituer le tableau des valeurs d'une fonction booléenne croissante quelconque de n variables. Korobkov [23] a montré que le nombre $l(n)$ d'opérations d'un algorithme optimal de $\Omega_n$ obéit aux inégalités

$$ egin{cases} C_n^{[\frac{n}{2}]} + C_n^{[\frac{n}{2}]+1} \le l(n) \le B C_n^{[\frac{n}{2}]} (1 + \epsilon_n) \\ \\ \text{avec } B = \frac{8}{(\sqrt{16} - 1)^{3/2}} \approx 4,26, \epsilon_n \to 0 \text{ si } n \to \infty \end{cases} $$

l'objet du présent chapitre est d'établir le résultat

$$ l(n) = C_n^{[\frac{n}{2}]} + C_n^{[\frac{n}{2}]+1} $$

### 1. Ensembles résolvants d'une fonction booléenne croissante

Soient une fonction booléenne croissante $f \in I_n$ et un sous-ensemble $E \subset B^n$. Notons $I_n(f, E)$ l'ensemble des fonctions de $I_n$ coincidant avec $f$ sur l'ensemble $E$. On a évidemment $f \in I_n(f, E.)$ Si $I_n(f, E) = \{f\}$ nous dirons que $E$ est un ensemble résolvant pour la fonction $f$.

Soit une fonction $f \in I_n$, $K_f$ son ensemble caractéristique, $M_f$ son ensemble fondamental (ensemble des éléments minimaux de $K_f$) et soit $N_f$ l'ensemble des éléments maximaux de $B^n - K_f$
PROPOSITION 1. – L'ensemble $M_f \cup N_f$ est le plus petit ensemble résolvant d'une fonction $f \in I_n$.

f étant croissante, $M_f \cup N_f$ est résolvant pour $f$. Réciproquement montrons que si $E$ est résolvant pour $f$, $M_f \cup N_f \subset E$.

Supposons par exemple que $e \in M_f$ et $e \notin E$.

Considérons la fonction booléenne $g$ définie par

$$g(x) = \begin{cases} \frac{f(x)}{f(x)} & \text{si } x \neq e \\ \frac{f(x)}{f(x)} & \text{si } x = e \end{cases}$$

$g$ est croissante (quel que soit $x \le e$ on a bien $g(x) = 0$ puisque $e \in M_f$) coincide avec $f$ sur l'ensemble $E$ et diffère de $f$. E n'est donc pas résolvant pour $f$. On montre de même que $e \in N_f \implies e \in E$.

## 2. Algorithmes de détermination d'une fonction booléenne croissante

Soit une fonction $f \in \mathcal{F}_n$. Pour la définir sans ambiguïté il est nécessaire de connaître sa valeur en tous les points de $B^n$. Si par contre $f \in I_n$ le même résultat est atteint dès que l'on connaît sa valeur en chaque point d'un ensemble résolvant.

Supposons que soit donné un organe fonctionnel $O_f$ qui calcule pour un point quelconque $a \in B^n$ (input) la valeur $f(a)$ (output) de la fonction $f$ en ce point. Désignons par $\Omega_n$ l'ensemble des algorithmes permettant de reconstituer au moyen de l'organe $O_f$ le tableau complet des valeurs d'une fonction croissante quelconque $f \in I_n$.

Le "travail" d'un algorithme $A \in \Omega_n$ se décrit de la manière suivante

a) Un élément $a_1 \in B^n$ est choisi.

b) La valeur $f(a_1)$ est calculée par l'organe $O_f$ et elle est insérée dans le tableau des valeurs de $f$.

c) Si $f(a_1) = 1$ [resp. $f(a_1) = 0$] on a $f(b) = 1$ pour tout $b > a_1$ [resp. $f(b) = 0$ pour tout $b \le a_1$]. Ces nouvelles valeurs $f(b)$ sont insérées dans le tableau des valeurs de $f$.

d) Le choix d'un nouvel élément $a_2 \in B^n$ est effectué (ce choix dépend de $a_1$ et $f(a_1)$) et $f(a_2)$ est calculé par $O_f$.
Le processus continue ainsi jusqu'à ce que le tableau des valeurs de $f$ soit entièrement reconstitué.

Chaque algorithme $A \in \Omega_n$ est caractérisé par l'ensemble des suites $[a_1^A(f), a_2^A(f), \dots, a_{k^A(f)}^A(f)]$, $f \in I_n$, d'éléments entrant comme input dans $O_f$ jusqu'à reconstitution complète du tableau des valeurs de $f$. $k_f^A$ est le nombre d'opérations réalisées par $O_f$ pour identifier la fonction $f$ lorsque l'on utilise l'algorithme $A$.

La longueur $l(A)$ d'un algorithme $A \in \Omega_n$ est le nombre $l(A) = \text{Max}_{f \in I_n} k_f^A$.

Un algorithme $A^*$ est optimal s'il est de longueur minimale $l(n)$.

$$l(A^*) = l(n) = \text{Min}_{A \in \Omega_n} l(A) = \text{Min}_{A \in \Omega_n} \text{Max}_{f \in I_n} k_f^A$$

### 3. Détermination de $l(n)$

Korobkov [23] a posé le problème de l'évaluation de $l(n)$ et a montré que ce nombre vérifie les inégalités

$$ \left\{ \begin{array}{l} C_n^{\left[ \frac{n}{2} \right]} + C_n^{\left[ \frac{n}{2} \right] + 1} \le l(n) < B C_n^{\left[ \frac{n}{2} \right]} \quad [1 + \epsilon_n] \\[1em] \text{avec } B = \frac{8}{\left( \sqrt{16} - 1 \right)^{3/2}} \approx 4,26 \text{ et } \epsilon_n \to 0 \quad \text{si } n \to \infty \end{array} \right. $$

Nous allons montrer [19]

**THÉORÈME 1.** —

$$l(n) = C_n^{\left[ \frac{n}{2} \right]} + C_n^{\left[ \frac{n}{2} \right] + 1}$$

$$\frac{1}{\text{Montrons }} l(n) \ge C_n^{\left[ \frac{n}{2} \right]} + C_n^{\left[ \frac{n}{2} \right] + 1}$$

Le travail d'un algorithme $A \in \Omega_n$ s'achève lorsque la valeur de la fonction étudiée $f \in I_n$ a été calculée en chaque point d'un de ses ensembles résolvants.

Considérons la fonction $\varphi \in I_n$ définie par

$$\varphi(x) = \begin{cases} 1 & \text{si } |s(x)| \ge \left\lfloor \frac{n}{2} \right\rfloor + 1 \\ 0 & \text{si } |s(x)| \le \left\lfloor \frac{n}{2} \right\rfloor \end{cases}$$
Les ensembles $M_f$ et $N_f$ sont donc

$$M_f = \{ a/a \in \mathbb{B}^n \text{ et } |s(a)| = \lfloor \frac{n}{2} \rfloor + 1 \}$$

$$N_f = \{ a/a \in \mathbb{B}^n \text{ et } |s(a)| = \lfloor \frac{n}{2} \rfloor \}$$

Par suite

$$|M_f \cup N_f| = C_n^{\lfloor \frac{n}{2} \rfloor} + C_n^{\lfloor \frac{n}{2} \rfloor + 1}$$

Il résulte alors de la proposition 1, quel que soit $A \in \Omega_n$

$$k_{\Phi}^{A} \geq C_{n}^{\lfloor \frac{n}{2} \rfloor} + C_{n}^{\lfloor \frac{n}{2} \rfloor + 1}$$

2/ Nous allons définir un algorithme $A^*$ tel que

$$l(A^*) \leq C_n^{\lfloor \frac{n}{2} \rfloor} + C_n^{\lfloor \frac{n}{2} \rfloor + 1}$$

Considérons la partition en chaines $l_f_n$ de $\mathbb{B}^n$ et soit une fonction quelconque $f \in I_n$.

Il découle des résultats du chap. 1 (prop. 7 en particulier) que lorsque la valeur $f$ a été calculée en chaque point de $K_{n-2p-1}$ il subsiste sur chaque chaîne $J \in \mathcal{J}_{n-2p+1}$ deux éléments au plus pour lesquels elle n'est pas encore connue (les éléments indéterminés de $J$ pour $f$).

L'algorithme $A^*$ se décrit de la manière suivante

a) Calculer la valeur de $f$ en chaque point de $K_{n-2[\lfloor \frac{n}{2} \rfloor] + 1}$ (éléments des chaines les plus courtes).

b) Calculer la valeur de $f$ en chaque élément indéterminé des chaines de $\mathcal{J}_{n-2p+1}$ avec

$$p = \lfloor \frac{n}{2} \rfloor - 1, \lfloor \frac{n}{2} \rfloor - 2, \dots, 2, 1, 0 \text{ successivement}$$

Alors

$$l(A^*) \leq |K_{n-2[\lfloor \frac{n}{2} \rfloor + 1]}| + 2 \times |\pi_n - \mathcal{J}_{n-2[\lfloor \frac{n}{2} \rfloor + 1]}|$$
Si n est pair $|K_{n-2}[\frac{n}{2}]_{+1}| = |K_1| = |\mathcal{K}_{n-2}[\frac{n}{2}]_{+1}|$

$$l(A^*) \le C_n^{[\frac{n}{2}]} - C_n^{[\frac{n}{2}]-1} + 2 C_n^{[\frac{n}{2}]-1} = C_n^{[\frac{n}{2}]} + C_n^{[\frac{n}{2}]+1}$$

Si n est impair

$$K_{n-2}[\frac{n}{2}]_{+1} = 2|\mathcal{K}_{n-2}[\frac{n}{2}]_{+1}|$$

$$l(A^*) \le 2 C_n^{[\frac{n}{2}]} = C_n^{[\frac{n}{2}]} + C_n^{[\frac{n}{2}]+1}$$
Les ensembles $A_1, A_2, \dots, A_n$ sont des matrices de order 3 à 8. On a $A_1 = A_2 = \dots = A_n$.

$$A_1 = A_2 = \dots = A_n$$

On a donné $\mathbf{A} = [A_1 \quad A_2 \quad \dots \quad A_n]$. On a à la base

des coordonnées $[A_1 \quad A_2 \quad \dots \quad A_n]$.

$$A = [A_1 \quad A_2 \quad \dots \quad A_n]$$

Il suffit d'appliquer la proposition 7, et on a fait

$$A = [A_1 \quad A_2 \quad \dots \quad A_n]$$

3. On applique d'abord un algèbrique $\mathbf{d}$ tel que

$$A = [A_1 \quad A_2 \quad \dots \quad A_n]$$

Considérant la partition en chaînes $k_1, k_2, \dots, k_n$ de $\mathbf{d}$ et calculant la fonction générale $f(\mathbf{k})$,

il détermine des résultats de ces, l'exp. 1, et particulièrement que le valeur $f$ a des coordonnées de chaque point de $K_n$, il réitère par chaque chaîne $f$ les deux éléments en lui pour laquelle il est plus密切 avec les éléments indiqués minimums de $f$ pour $f$.

L'algorithme $\mathbf{d}$ est déduit de la méthode suivante :

a) Calculer la valeur de $f$ en chaque point de $K_n$ (d'après des chaînes les plus courtes).

b) Calculer la valeur de $f$ en chaque élément individuel des chaînes de $K_n$ avec

$$f = [f_1 \quad f_2 \quad \dots \quad f_n] = [f_1 \quad f_2 \quad \dots \quad f_n] \text{ avec } f_i \text{ le ième élément}$$

Alors :

$$f = [f_1 \quad f_2 \quad \dots \quad f_n] \text{ et } K_n = [K_1 \quad K_2 \quad \dots \quad K_n]$$
### 3. Une inégalité

L'objet de ce chapitre est de démontrer certaines inégalités caractérisant les fonctions booléennes croissantes (théorème 1). Ces inégalités étaient une conjecture de Z. W. Birnbaum et nous en avons donné une première démonstration en [15].

#### 1. - Propositions auxiliaires.

Soit une fonction booléenne croissante $f \in I_n$ et soit $K_f$ son ensemble caractéristique. $K_f$ est la réunion d'une famille $(A_j)_{0 \le j \le n}$ de $n+1$ sous-ensembles disjoints (certains pouvant être vides) définis par

$$A_j = \{a \mid a \in K_f \text{ et } |s(a)| = j\}$$

De même $B^n - K_f$ est la réunion d'une famille $(A_j^*)_{0 \le j \le n}$ de $n+1$ sous-ensembles disjoints définis par

$$A_j^* = \{a \mid a \in B_f \text{ et } |s(a)| = j\}$$

Notons encore pour tout $j \in \{0, 1, \dots, n\}$

$$\Gamma_j = \{a \mid a \in B^n \text{ et } |s(a)| = j\}$$

La famille $(\Gamma_j)_{0 \le j \le n}$ constitue une partition de $B^n$.

On a de plus

$$\Gamma_j = A_j \cup A_j^*$$

et

$$|\Gamma_j| = C_n^j = |A_j| + |A_j^*| \quad (1)$$

**PROPOSITION 1.** [4] - Soit une fonction booléenne croissante $f \in I_n$. Quel que soit $j \in \{0, 1, \dots, n-1\}$ sont vérifiées les inégalités
$$ (n-j) |A_j| \le (j+1) |A_{j+1}| \quad (2) $$

et

$$ (j+1) |A_{j+1}^*| \le (n-j) |A_j^*| \quad (3) $$

DÉMONSTRATION. — Il découle de (1) que les inégalités (2) et (3) sont équivalentes. La proposition est alors une conséquence immédiate d'une proposition plus forte (proposition 2) que nous allons démontrer.

Soit un élément $x \in B^n$. Nous noterons $T(x)$ [resp. $S(x)$] l'ensemble des éléments de $B^n$ qui couvrent $x$ (resp. qui sont couverts par $x$).

Soit un élément $a^* \in A_j^*$. Nous poserons

$$ C(a^*) = T(a^*) \cap A_{j+1} $$

On peut alors énoncer

PROPOSITION 2. — Une condition nécessaire pour qu'une fonction booléenne de n variables soit croissante est que pour tout $j \in \{0, 1, \dots, n-1\}$ on ait

$$ (n-j) |A_j| + \sum_{a^* \in A_j^*} |C(a^*)| = (j+1) \cdot |A_{j+1}| \quad (4) $$

DÉMONSTRATION. — a) Remarquons tout d'abord que

$$ \text{quel que soit } a \in \Gamma_j \text{ on a } |T(a)| = n-j \quad (5) $$

$$ \text{quel que soit } a \in \Gamma_{j+1} \text{ on a } |S(a)| = j+1 \quad (5 \text{ bis}) $$

b) Pour qu'une fonction booléenne soit croissante, il faut et il suffit que pour tout $j \in \{0, 1, 2, \dots, n-1\}$ et pour tout $a \in A_j$ on ait $T(a) \subset A_{j+1}$.

c) Soit alors $\Delta_j$ le sous-ensemble de $B^n \times B^n$ défini par

$$ \Delta_j = \{(d, d') \mid d' \in A_{j+1} \text{ et } d \in S(d')\} $$

Par définition de $\Delta_j$ et en tenant compte de (5 bis)

$$ |\Delta_j| = (j+1) |A_{j+1}| $$

D'un autre côté, par définition des ensembles $C(a^*)$ et en tenant compte de (5) et de b)

$$ |\Delta_j| = (n-j) |A_j| + \sum_{a^* \in A_j^*} |C(a^*)| $$
**PROPOSITION 3.** — Soit une fonction booléenne $f \in I_n$. Il existe deux fonctions $f_0$ et $f_1$ appartenant à $I_{n-1}$, déterminées de façon unique et telles que

$$- f_0 \le f_1$$

- Pour tout $x = (x_1, x_2, \dots, x_n) \in B^n$ on a

$$f(x_1, x_2, \dots, x_n) = x_n f_1(x_1, x_2, \dots, x_{n-1}) + f_0(x_1, x_2, \dots, x_{n-1})$$

a) Posons

$$x^0 = (x_1, x_2, \dots, x_{n-1}, 0)$$

$$x^1 = (x_1, x_2, \dots, x_{n-1}, 1)$$

Nous définissons deux fonctions $f_0$ et $f_1$ de $I_{n-1}$ par

$$f_0(x_1, x_2, \dots, x_{n-1}) = f(x^0)$$

$$f_1(x_1, x_2, \dots, x_{n-1}) = f(x^1)$$

les fonctions $f_0$ et $f_1$ ont les propriétés cherchées.

b) Supposons qu'il existe deux couples de fonctions $(f_0, f_1)$ et $(f'_0, f'_1)$ obéissant aux conditions posées.

Pour tout $x^0$ on a

$$f(x^0) = f_0(x_1, x_2, \dots, x_{n-1}) = f'_0(x_1, x_2, \dots, x_{n-1})$$

Donc $f_0 = f'_0$.

Pour tout $x^1$ on a

$$f(x^1) = f_1(x_1, x_2, \dots, x_{n-1}) + f_0(x_1, x_2, \dots, x_{n-1})$$

$$= f'_1(x_1, x_2, \dots, x_{n-1}) + f'_0(x_1, x_2, \dots, x_{n-1})$$

Donc $f_1 + f_0 = f'_1 + f'_0$.

Mais $f_0 \le f_1$ entraîne $f_1 + f_0 = f_1$ et de même

$$f'_0 \le f'_1 \text{ entraîne } f'_1 + f'_0 = f'_1$$

On a donc $f_1 = f'_1$.

**PROPOSITION 4.** — Pour toute fonction booléenne croissante $f \in I_n$ les inégalités suivantes sont vérifiées
$$|A_1| \cdot |A_1^*| \le |A_2| \quad (6)$$

$$|A_{n-1}| \cdot |A_{n-1}^*| \le |A_{n-2}^*| \quad (6 \text{ bis})$$

DEMONSTRATION. – a) Soit un élément $a \in A_1$. f étant croissante, $T(a) \subset A_2$. De plus $|T(a)| = n-1$ et si $a$ et $b$ sont deux éléments distincts de $A_1$ on a $|T(a) \cap T(b)| = 1$.

Il en résulte que

$$|A_2| \ge (n-1) + (n-2) + \dots + n - |A_1| \ge |A_1| \quad (n - |A_1|)$$

En tenant compte de (1), on obtient (6).

b) Soit un élément $a^* \in A_{n-1}^*$. f étant croissante, $S(a) \subset A_{n-2}^*$. De plus $|S(a^*)| = n-1$ et si $a^*$ et $b^*$ sont deux éléments distincts de $A_{n-1}^*$, on a $|S(a^*) \cap S(b^*)| = 1$, il en résulte que

$$|A_{n-2}^*| \ge (n-1) + (n-2) + \dots (n - |A_{n-1}^*|) \ge |A_{n-1}^*| \quad (n - |A_{n-1}^*|)$$

En tenant compte de (1), on obtient (6 bis)

## 2. – Etablissement de la conjecture de Z.W. Birnbaum

### THÉORÈME 1. – Soit une fonction booléenne croissante $f \in I_n$. Pour tout $j \in \{1, 2, \dots, n-1\}$ on $a^*$

$$|A_j| \cdot |A_j^*| \le |A_{j+1}| \cdot |A_{j-1}^*|$$

### DÉMONSTRATION. – a) Résultats préliminaires.

D'après la proposition 3, il existe deux fonctions $f_0$ et $f_1 \in I_{n-1}$ telles que

$$\left\{ \begin{array}{l} f(x_1, x_2, \dots, x_{n-1}, x_n) = x_n f_1(x_1, x_2, \dots, x_{n-1}) + f_0(x_1, x_2, \dots, x_{n-1}) \\ f_0 \le f_1 \end{array} \right. \quad (8)$$

Soient $K_{f_0}$ et $K_{f_1}$ leurs ensembles caractéristiques dans $\mathbb{B}^{n-1}$ et posons

$$A_j^0 = \{a \mid a \in K_{f_0}, |s(a)| = j\}, \quad j = (0, 1, \dots, n-1)$$

* Si $|A_{j-1}^*|$ et $|A_j|$ ne sont pas nuls, ces inégalités ont l'expression plus significative

$$\frac{|A_j^*|}{|A_{j-1}^*|} \le \frac{|A_{j+1}|}{|A_j|}$$
$$A_j^0 = \{a \mid a \in B^{n-1} - K_{f_0}, |s(a)| = j\}, \quad j = (0, 1, \dots, n-1)$$

On a

$$|A_j^0| + |A_j^{0*}| = C_{n-1}^j \quad (9)$$

On définit de manière analogue les ensembles $A_j^1$ et $A_j^{1*}$ pour la fonction $f_1$ et l'on a

$$|A_j^1| + |A_j^{1*}| = C_{n-1}^j \quad (9 \text{ bis})$$

De (8), il résulte que pour tout $j \in \{0, 1, \dots, n-1\}$

$$|A_j^0| \le |A_j^1| \quad (10)$$

$$|A_j^{1*}| \le |A_j^{0*}| \quad (10 \text{ bis})$$

Soit un élément $a = (a_1, a_2, \dots, a_{n-1}, a_n) \in B^n$

De (7), il résulte que

$$f(a_1, a_2, \dots, a_{n-1}, a_n) = a_n f_1(a_1, a_2, \dots, a_{n-1}) + f_0(a_1, a_2, \dots, a_{n-1})$$

Par suite, est vraie la double implication

$$(a_1, a_2, \dots, a_n) \in A_j \iff \left\{ \begin{array}{l} \text{ou bien } a_n = 0 \text{ et } (a_1, a_2, \dots, a_{n-1}) \in A_j^0 \\ \text{ou bien } a_n = 1 \text{ et } (a_1, a_2, \dots, a_{n-1}) \in A_{j-1}^1 \end{array} \right.$$

Considérons l'application de $B^n$ dans $B^{n-1}$ définie par

$$(x_1, x_2, \dots, x_{n-1}, x_n) \to (x_1, x_2, \dots, x_{n-1}).$$

La restriction de cette application à l'ensemble $A_j$ est une bijection de l'ensemble $A_j \subset B^n$ sur l'ensemble $(A_{j-1}^1 \cup A_j^0) \subset B^{n-1}$. $A_{j-1}^1$ et $A_j^0$ étant disjoints, on a donc pour $j \in \{1, 2, \dots, n-1\}$

$$|A_j| = |A_{j-1}^1| + |A_j^0| \quad (11)$$

Utilisant (1), (9) et (9 bis), on obtient pour tout $j \in \{1, 2, \dots, n-1\}$

$$|A_j^*| = |A_{j-1}^*| + |A_j^0| \quad (11 \text{ bis})$$

Les fonctions $f_0$ et $f_1$ étant croissantes, de la proposition 1 utilisée pour une fonction de $I_{n-1}$, il découle pour tout $j \in \{1, 2, \dots, n-1\}$

$$j | A_j^0| \le (n-j) | A_{j-1}^0| \quad (12)$$
$$ (n-j) \quad |A_{j-1}^1| \le j \quad |A_j^1| \qquad (13) $$

En multipliant membre à membre les inégalités (12) et (13), on obtient pour tout $j \in \{1, 2, \dots, n-1\}$

$$ |A_{j-1}^1| \cdot |A_j^{0*}| \le |A_j^1| \cdot |A_{j-1}^{0*}| \qquad (14) $$

b) Nous allons maintenant démontrer le théorème par récurrence sur le nombre $n$ de variables. Pour $n=2$ le théorème découle de la proposition 4 [inégalité (6)]. Supposons qu'il soit vrai jusqu'au rang $n-1$ et montrons qu'il l'est encore au rang $n$.
Pour $j=1$ (resp. $j=n-1$) le théorème découle de l'inégalité (6) (resp. (6 bis))

Supposons $2 \le j \le n-2$.

En vertu de (11) et (11 bis), l'inégalité à démontrer s'écrit

$$ (|A_{j-1}^1| + |A_j^0|) (|A_{j-1}^{1*}| + |A_j^{0*}|) \le (|A_j^1| + |A_{j+1}^0|)(|A_{j-2}^{1*}| + |A_{j-1}^{0*}|) $$

Soit en développant

$$ \begin{aligned} & \underbrace{|A_{j-1}^1| \cdot |A_{j-1}^{1*}| + |A_j^0| \cdot |A_j^{0*}|}_{\text{K}} + \underbrace{|A_{j-1}^1| \cdot |A_j^{0*}| + |A_j^0| \cdot |A_{j-1}^{1*}|}_{\text{L}} \\ & \le \underbrace{|A_j^1| \cdot |A_{j-2}^{1*}| + |A_{j+1}^0| \cdot |A_{j-1}^{0*}|}_{\text{M}} + \underbrace{|A_j^1| \cdot |A_{j-1}^{0*}| + |A_{j+1}^0| \cdot |A_{j-2}^{1*}|}_{\text{N}} \end{aligned} $$

Par hypothèse de récurrence $K \le M$. Il suffit donc de démontrer $L \le N$.

Par hypothèse de récurrence, nous pouvons appliquer le théorème aux deux facteurs du dernier terme de $N$. Il suffira donc de démontrer *

$$ L \le |A_j^1| \cdot |A_{j-1}^{0*}| + \frac{|A_j^0| \cdot |A_{j-1}^{0*}|}{|A_{j-1}^{0*}|} \times \frac{|A_{j-1}^1| \cdot |A_{j-1}^{1*}|}{|A_j^1|} \qquad (15) $$

Posons

$$ |A_j^{0*}| \cdot |A_{j-1}^1| = P $$

$$ |A_j^0| \cdot |A_{j-1}^{1*}| = Q $$

$$ |A_j^1| \cdot |A_{j-1}^{0*}| = R $$

<footnote>* si $|A_{j-1}^{0*}| = 0$ l'inégalité $L \le N$ est immédiate car on a $|A_{j-1}^{0*}| = |A_j^0| = |A_{j-1}^{1*}| = 0$. Il en est de même si $|A_j^1| = 0$ car alors $|A_j^1| = |A_{j-1}^1| = |A_j^0| = 0$.</footnote>
L'inégalité (15) à démontrer s'écrit $P + Q = < R + \frac{PQ}{R}$ soit encore

$(R - P) (R - Q) \geq O$.

De (10) et (10 bis) il résulte $R \geq Q$. De (14) il résulte $R \geq P$.

COROLLAIRE. — Pour toute fonction booléenne croissante $f \in I_n$ les inégalités suivantes sont vérifiées*

$$|A_i^*| \cdot |A_{j+1}| \le |A_{i+1}| \cdot |A_j^*| \quad \begin{cases} i \in \{1, 2, \dots, n-1\} \\ j \in \{0, 1, \dots, n-2\} \\ j < i \end{cases}$$

En effet, d'après le théorème précédent, on peut écrire la suite d'inégalités

$$\begin{align*} |A_{j+1}| \cdot |A_{j+1}^*| &\le |A_{j+2}| \cdot |A_j^*| \\ |A_{j+2}| \cdot |A_{j+2}^*| &\le |A_{j+3}| \cdot |A_{j+1}^*| \\ |A_i| \cdot |A_i^*| &\le |A_{i+1}| \cdot |A_{i-1}^*| \end{align*}$$

En multipliant ces inégalités membre à membre, on obtient le résultat cherché.

$$\frac{|A_i^*|}{|A_j^*|} \le \frac{|A_{i+1}|}{|A_{j+1}|}$$

<footnote>* Si $|A_j^*|$ et $|A_{j+1}|$ ne sont pas nuls ces inégalités s'écrivent de façon plus expressive</footnote>
(1) $\lim_{x \to 0} (x + \frac{1}{x}) = e$

In multiplication, multiplications by 1 are always identity (1). In multiplication by 0, the multiplicative identity is 0, and the multiplicative inverse is 1.

(2) De (1) et (10) on a applique la formule (11) et (12).

En multiplication, la somme est le produit de la multiplication par l'opposé. On a : $a \cdot 0 = 0$ et $a \cdot a = a^2$.
Pour $a \neq 0$, on a $a \cdot a = a^2 \neq a$.
Pour $a = 0$, on a $a \cdot a = 0$.

En addition, la somme est le produit de la multiplication par l'opposé. On a : $a + 0 = a$ et $a + a = a^2$.
Pour $a \neq 0$, on a $a + a = a^2 \neq a$.

$$ (A + B) \cdot C = A \cdot C + B \cdot C $$

$$ A \cdot (B + C) = A \cdot B + A \cdot C $$

En multiplication, la somme est le produit de la multiplication par l'opposé. On a : $A \cdot B \cdot C = A \cdot (B \cdot C)$.

$$ (A + B) \cdot (C + D) = (A \cdot C) + (B \cdot C) + (A \cdot D) + (B \cdot D) $$

Par conséquent, $A \cdot B \cdot C \cdot D = (A \cdot B) \cdot (C \cdot D)$.

Par conséquent, $(A \cdot B) \cdot C \cdot D = (A \cdot B) \cdot (C \cdot D)$ et $(A \cdot B) \cdot (C \cdot D) = (A \cdot B) \cdot (D \cdot C)$.

$$ (A + B) \cdot (C + D) = (A \cdot C) + (B \cdot C) + (A \cdot D) + (B \cdot D) $$

$$ (A + B) \cdot C = A \cdot C + B \cdot C $$

$$ A \cdot (B + C) = A \cdot B + A \cdot C $$

En addition, la somme est le produit de la multiplication par l'opposé. On a : $A \cdot B \cdot C \cdot D = A \cdot (B \cdot C) \cdot D$.
# 4. Les schémas de contacts - Étude générale

L'objet de ce chapitre est de définir la notion de schéma de contacts, de renforcer les résultats de Shannon [37 bis] et Povarov [32] concernant la composition des schémas et d'exposer certains résultats de Hamming [14] et de Lupanov [29] dont nous aurons besoin au chapitre suivant.

## 1. Rappel de théorie des graphes

1.1. - Un multigraphe non orienté $G = (S, A, \Gamma)$ est défini par la donnée

- d'un ensemble $S$ dont les éléments sont les sommets de $G$

- d'un ensemble $A$ dont les éléments sont les arêtes de $G$

- d'une application $\Gamma$ qui à chaque arête $a \in A$ assochie une paire non ordonnée $\{s, s'\}$ de sommets de $G$. s et s' sont les extrémités de l'arête $a$. Une arête $a$ dont l'une des extrémités est un sommet $s$ est appelée incidente à $s$. Deux sommets $s$ et $s'$ sont adjacents s'il existe une arête ayant pour extrémités $s$ et $s'$. Nous considérerons toujours des ensembles $S$ et $A$ finis.

Un multigraphe se dessine sur le plan en représentant chaque sommet par un point et chaque arête par un trait joignant ses extrémités.

1.2. - Transformations de multigraphes.

Soit $G = (S, A, \Gamma)$ un multigraphe.
a) Soit un sous-ensemble $K \subset S$. On appelle sous-multigraphe engendré par $K$ (ou obtenu par suppression de $S-K$) le multi-graphe $G_K = (K, A_K, \Gamma_{A_K})$ défini de la façon suivante

- l'ensemble de ses sommets est $K$;

- l'ensemble de ses arêtes est l'ensemble $A_K \subset A$ dont les éléments ont leurs deux extrémités dans $K$;

- l'application $\Gamma_{A_K}$ est la restriction de $\Gamma$ à $A_K$.

b) Soit un sous-ensemble $L \subset A$. On appelle multigraphe partiel engendré par $L$ (ou obtenu par suppression de $A-L$) le multi-graphe $G^L = (S, L, \Gamma_L)$ ainsi défini

- l'ensemble de ses sommets est $S$;

- l'ensemble de ses arêtes est $L$;

- l'application $\Gamma_L$ est la restriction de $\Gamma$ à $L$.

c) Soit un sous-ensemble $K \subset S$.

On appellera *graphe obtenu par contraction des sommets de K* le multigraphe obtenu à partir de $G$ au moyen des transformations suivantes

- les sommets de $K$ sont remplacés par un sommet unique $k$;

- les arêtes dont les deux extrémités appartiennent à $K$ sont supprimées;

- chaque arête dont une extrémité $s$ est élément de $K$ et l'autre $s'$ est élément de $S-K$ est remplacée par une arête ayant pour extrémités $k$ et $s'$.

Le sommet $k$ est appelé le *contracté* de l'ensemble $K$.

### 1.3. - Chaînes, cycles, coupes.

Une chaîne $C$ d'un multigraphe est définie par la donnée d'une suite $(s_0, s_1, ..., s_i, ..., s_k)$ de sommets et d'une suite $(a_1, a_2, ..., a_i, ..., a_k)$ d'arêtes telles que pour tout $i \in \{1, 2, ..., k\}$ l'arête $a_i$ a pour extrémités $s_{i-1}$ et $s_i$.

On dit que la chaîne $C$ relie les sommets $s_0$ et $s_k$. Par abus de langage les suites $(s_1)_{0 \le i \le k}$ et $(a_i)_{1 \le i \le k}$ seront aussi appelées chaînes.

Une chaîne élémentaire est une chaîne dont les sommets (et par conséquent les arêtes) sont distincts.
Un cycle est une chaîne dont les extrémités $s_0$ et $s_k$ coincident.

Un cycle est élémentaire si tous ses sommets autres que $s_0$ et $s_k$ sont distincts.

Un multigraphe est connexe s'il existe une chaîne qui relie tout couple de sommets distincts s et s'. (Un sommet isolé est connexe).

Les sous-multigraphes connexes maximaux d'un multigraphe sont ses composantes connexes. Les composantes connexes définissent une partition de l'ensemble des sommets d'un multigraphe.

On appelle coupe d'un multigraphe connexe $G = (S, A, \Gamma)$ un ensemble d'arêtes $L \subset A$ tel que le multigraphe $G^{A-L} = (S, A-L, \Gamma_{A-L})$ n'est pas connexe.

Une coupe $L$ est minimale s'il n'existe pas de coupe $L'$ contenant dans $L$ (avec $L' \neq L$).

**PROPOSITION 1.** - Si une coupe $L$ d'un graphe connexe $G = (S, A, \Gamma)$ est minimale, il existe une partition de $S$ en deux sous-ensembles $S_1$ et $S_2$ tels que $L$ est l'ensemble des arêtes ayant une extrémité dans $S_1$ et l'autre dans $S_2$.

En effet, $L$ étant une coupe minimale, le graphe partiel $G^{A-L}$ n'a que deux composantes connexes qui déterminent une partition de $S$ en deux sous-ensembles $S_1$ et $S_2$.

# 2. Schémas de contacts

## 2.1. - Définition

Un schéma de contacts $H = (G, h)$ est défini par la donnée

- d'un multigraphe $G = (S, A, \Gamma)$ ;

- d'un ensemble $X_n = \{x_1, x_2, \dots, x_n; \bar{x}_1, \bar{x}_2, \dots, \bar{x}_n\}$ de variables booléennes appelées *variables de contact* ;

- d'une application $h : A \to X_n$ qui associe une variable de contact à chaque arête $a \in A$.

Les couples $[a, h(a)]$ sont appelés *contacts* du schéma.

La partie $h(a)$ est l'argument du contact $[a, h(a)]$.

Les contacts ayant pour argument la variable $x_i \in X_n$ sont appelés $x_i$-contacts.
Lorsqu'il n'y a pas de confusion possible, on peut désigner les contacts d'un schéma par leur argument affecté ou non d'un deuxième indice permettant de les distinguer.

<figure><img src="image_7.png" /><figcaption>Fig. 1</figcaption></figure>

Par exemple, on dira que les contacts du schéma représenté sur la figure 1 sont $x_1, x_2, x'_1, x'_2, \bar{x}_3$.

Les contacts dont l'argument est élément du sous-ensemble $\{x_1, x_2, \dots, x_n\}$ (resp. $\{\bar{x}_1, \bar{x}_2, \dots, \bar{x}_n\}$) sont appelés contacts fermants (resp. ouvrants).

Un schéma est fermant (resp. ouvrant) si tous ses contacts sont fermants (resp. ouvrants).

## 2.2. - Fonctions de transmission.

Soient un schéma de contacts $H = (G, h)$ et deux sommets $s$ et $s'$ de $G$.

Considérons une chaîne $c$ reliant $s$ et $s'$ et ayant pour suite d'arêtes $(a_1, a_2, \dots, a_i, \dots, a_k)$.

On appelle fonction de transmission (ou plus simplement transmission) de la chaîne $c$ la fonction booléenne $\tau_c \in \mathfrak{T}_n$ définie par

$$ \tau_c(x) = \prod_{i=1}^{k} h(a_i), \quad x = (x_1, x_2, \dots, x_n) $$

Soit $C_{ss'}$ l'ensemble des chaines reliant $s$ et $s'$. On appelle fonction de transmission $f_{ss'}$ entre $s$ et $s'$ la fonction booléenne

$$ f_{ss'} = \sum_{c \in C_{ss'}} \tau_c $$

Si $s = s'$ on pose $f_{ss'} \equiv 1$.

Si $C_{ss'}$ est vide, on pose $f_{ss'} \equiv 0$.

En vertu des relations d'absorption, on peut restreindre la sommation à l'ensemble des chaînes élémentaires reliant $s$ et $s'$.

**EXEMPLE.** – Considérons le schéma représenté par la figure 2.

La fonction de transmission $f_{ss'}$ entre $s$ et $s'$ est définie par

$$ f_{ss'}(x) = x_1 x_2 + x_1 x_3 x_4 + \bar{x}_1 x_3 x_2 + \bar{x}_1 x_4 $$
<figure><img src="image_8.png" /><figcaption>Fig. 2</figcaption></figure>

Etant donné un schéma de contacts, l'ensemble de ses fonctions de transmission $F = \{f_{ss} / (s, s') \in S^2\}$ est parfaitement déterminé.

Par contre, il peut exister plusieurs schémas de contacts ayant pour ensemble de fonctions de transmission un ensemble F complètement ou partiellement spécifié.

Le critère d'optimalité le plus fréquemment retenu est la minimisation du nombre $|A|$ des contacts.

### 2.3. - Schémas $(p_1, p_2)$-polaires.

Un schéma $(p_1, p_2)$-polaire [noté $H(p_1, p_2)$] est défini par la donnée

- d'un schéma de contacts $H = (G, h)$ (avec $G = (S, A, \Gamma)$)

- de deux sous-ensembles $I = \{i_1, i_2, \dots, i_{p_1}\}$ et $T = \{t_1, t_2, \dots, t_{p_2}\}$ contenus dans $S$. Les éléments de $I$ (resp. de $T$) sont appelés pôles d'entrée (resp. de sortie) du schéma.

Un schéma $(1, 1)$-polaire est appelé bipolaire.

A un schéma $(p_1, p_2)$-polaire est associée une matrice $M = [a_{kl}]$ avec $a_{kl} = f_{i_A t_i}^{k}$ (transmission entre $i_k$ et $t_1$).

On dit qu'un schéma $H(p_1, p_2)$ réalise les fonctions

$$ (f_{ij}) \quad i \in \{i_1, i_2, \dots, i_{p_1}\} $$

$$ j \in \{t_1, t_2, \dots, t_{p_2}\} $$

## 3. Les schémas disjonctifs

### 3.1. - Définitions.

Un schéma $G(p_1, p_2)$ est fortement disjonctif si pour tout couple $(i_j, i_1)$ de pôles d'entrée différents et tout couple $(t_k, t_1)$ de pôles de sortie différents, on a

$$ f_{i_k i_1} = f_{t_k t_1} = 0 $$

### 3.2. - Soient un schéma $H(p_1, p_2)$ et deux partitions des pôles d'entrée et de sortie, respectivement
$$I = I_1 + I_2 + \dots + I_{m_1} \quad \text{et} \quad T = T_1 + T_2 + \dots + T_{m_2}$$

Pour tout $j \in \{1, 2, \dots, m_1\}$ (resp. pour tout $k \in \{1, 2, \dots, m_2\}$) contractons les pôles de l'ensemble $I_j$ en un sommet unique $i_j^*$ (resp. de l'ensemble $T_k$ en un sommet unique $t_k^*$).

Notons $H^*(m_1, m_2)$ le schéma obtenu alors en choisissant $i_1^*$, $i_2^*$, ..., $i_{m_1}^*$ pour pôles d'entrée et $t_1^*$, $t_2^*$, ..., $t_{m_2}^*$ pour pôles de sortie.

Soit $f_{i_j^* t_k^*}^*$ la transmission entre le pôle $i_j^*$ et le pôle $t_k^*$ dans $H^*(m_1, m_2)$.

Nous dirons que $H(p_1, p_2)$ est faiblement disjonctif si quelles que soient les partitions choisies de ses pôles et quels que soient j et k on a

$$f_{i_j^* t_k^*}^* = \sum_{\substack{i \in I_j \\ t \in T_k}} f_{1t}$$

(où $f_{1t}$ désigne la transmission entre i et t dans H).

En particulier, on montrera qu'un schéma fortement disjonctif est faiblement disjonctif.

<figure><img src="image_9.png" /><figcaption>Fig. 3</figcaption></figure>

EXEMPLES. – a) Le schéma de la figure 3 est un schéma (1,8)-polaire réalisant entre le pôle d'entrée I et ses 8 pôles de sortie tous les produits élémentaires de 3 variables. (Un schéma ayant cette propriété s'appelle un arbre de décodage).

Le schéma représenté ci-dessus est fortement disjonctif.

b) Le schéma de la figure 4, où tous les sommets autres que I (pôle d'entrée) sont considérés comme pôles de sortie, réalise
<figure><img src="image_10.png" /><figcaption>Fig. 4</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>Fig. 5</figcaption></figure>

tous les produits fondamentaux de trois variables. Il n'est pas faiblement disjonctif. En effet si l'on contracte les pôles a et b on a

$$f_{I^*c*}^*(x_1, x_2, x_3) = (x_1^+ + x_2) x_3 \quad \text{alors que} \quad f_{Ic}(x_1, x_2, x_3) = x_2 x_3$$

c) Le schéma de la figure 5 réalise entre I et ses pôles $(t_1)_{1 \le i \le 7}$ tous les produits fondamentaux de trois variables. Il est faiblement disjonctif.

**3.3. PROPOSITION 2.** — Une condition nécessaire et suffisante pour qu'un schéma $H(1, p_2)$ soit faiblement disjonctif est que pour tout triplet $(t_j, t_k, t_l)_{j \neq l}$ de pôles de sortie soit vérifiée l'inégalité

$$f_{It_j} \ge f_{It_k} \cdot f_{t_l t_j} \quad (1)$$

(I étant le pôle d'entrée du schéma).

**DÉMONSTRATION.** — Condition nécessaire : Contractons les pôles de sortie $t_k$ et $t_l$ et notons $t^*$ leur contracté.

Le schéma H étant faiblement disjonctif, on doit avoir

$$f_{I^*t^*}^* = f_{It_k} + f_{It_l}$$

et

$$f_{I^*t_j^*}^* = f_{It_j}$$

Nous pouvons alors écrire la suite d'inégalités

$$f_{It_j} \ge f_{I^*t^*} \cdot f_{t^*t_j^*} \ge (f_{It_k} + f_{It_l}) (f_{t_l t_j} + f_{t_k t_j}) \ge f_{It_k} \cdot f_{t_l t_j}$$
*Condition suffisante:* Soit T l'ensemble des pôles de sortie de H. La partition $T = T_1 + T_2 + ... + T_{m_2}$ définit $H^*(1, m_2)$ : Nous noterons $t_1^*, t_2^*, ... t_{m_2}^*$ les pôles de sortie de $H^*$.

Il faut montrer que quel que soit $i \in \{1, 2, ..., m_2\}$ on a

$$f_{I^*t_1^*}^* = \sum_{t \in T_1} f_{It}$$

On a évidemment

$$f_{I^*t_1^*}^* \geq \sum_{t \in T_1} f_{It}$$

Il suffit donc de montrer que la transmission $\tau_{c^*}$ de toute chaîne élémentaire $c^*$ reliant $I^*$ et $t_1^*$ dans $H^*$ vérifie

$$\tau_{c^*} \leq \sum_{t \in T_1} f_{It}$$

Soient $t_{a_1}^*, t_{a_2}^*, ... t_{a_{s-1}}^*, t_{a_s}^* = t_1^*$ les pôles de sortie successifs de $H^*$ par lesquels passe la chaîne $c^*$.

Notons $c_{t_{a_j}^* t_{a_{j+1}}^*}^*$ la partie de $c^*$ qui relie $t_{a_j}^*$ et $t_{a_{j+1}}^*$. Il existe nécessairement dans le schéma initial deux pôles de sortie $\alpha_j \in T_{a_j}$ et $\beta_{j+1} \in T_{a_{j+1}}$ ainsi qu'une chaîne $c_{\alpha_j \beta_{j+1}}$ reliant $\alpha_j$ et $\beta_{j+1}$ et dont la transmission $\tau_{c_{\alpha_j \beta_{j+1}}}$ vérifie

$$\tau_{c_{\alpha_j \beta_{j+1}}} = \tau_{c_{t_{a_j}^* t_{a_{j+1}}^*}}^*$$

Ceci est vrai pour tout $j \in \{1, 2, ..., s-1\}$

Si nous posons $\alpha_0 = I$ et $t_{a_0}^* = I^*$ c'est encore vrai pour $j=0$. Nous pouvons donc écrire

$$\tau_{c^*} = \prod_{j=0}^{s-1} \tau_{c_{t_{a_j}^*} t_{a_{j+1}}^*} = \prod_{j=0}^{s-1} \tau_{c_{\alpha_j \beta_{j+1}}} \leq \prod_{j=0}^{s-1} f_{\alpha_j \beta_{j+1}}$$

Alors en appliquant (1) s fois successivement, on obtient

$$\prod_{j=0}^{s-1} f_{\alpha_j \beta_{j+1}} \le f_I \beta_s \le \sum_{t \in T_1} f_{It} \quad (\text{car } \beta_s \in T_1)$$

On déduit immédiatement de la proposition précédente l'énoncé suivant

**PROPOSITION 3.** — Une condition nécessaire et suffisante pour qu'un schéma $H(p_1, p_2)$ soit faiblement disjonctif est que
- pour tout triplet $(i_j, i_k, i_l)_{j \neq l}$ de pôles d'entrée et pour tout pôle de sortie $t$, on ait $f_{t i_j} \ge f_{t i_k}$. $f_{i_l i_j}$.

- pour tout triplet $(t_j, t_k, t_l)_{j \neq l}$ de pôles de sortie et pour tout pôle d'entrée $i$, on ait $f_{i t_j} \ge f_{i t_k}$. $f_{t_l t_j}$.

COROLLAIRE. - Un schéma fortement disjonctif est faiblement disjonctif.

# 4. Opérations sur les schémas $(p_1, p_2)$ - polaires

## 4.1. - Juxtaposition.

Considérons deux schémas de contacts $H(p_1, p_2)$ et $H'(p'_1, p'_2)$ ayant pour ensembles de pôles d'entrée (resp. de sortie) $I$ et $I'$ (resp. $T$ et $T'$).

Nous appellerons juxtaposé des schémas $H$ et $H'$ le schéma $H''(p_1 + p'_1, p_2 + p'_2)$ obtenu en maintenant inchangés les schémas $H$ et $H'$, en prenant pour ensemble de pôles d'entrée $I'' = I + I'$ et pour ensemble de pôles de sortie $T'' = T + T'$.

On note $H'' = [H; H']$.

Si $M, M', M''$ sont les matrices associées aux schémas $H, H', H''$, on a

$$M'' = \begin{bmatrix} M & O \\ O & M' \end{bmatrix}$$

Nous noterons $H^{(k)}(kp_1, kp_2)$ ou plus simplement $H^{(k)}$ le schéma obtenu par juxtaposition de $k$ schémas identiques.

## 4.2. - Composi tion.

Soient deux schémas $H(p_1, p_2)$ et $H'(p_2, p_3)$ et soient $t_1, t_2, \dots, t_{p_2}$ les pôles de sortie de $H$ et $i'_1, i'_2, \dots, i'_{p_2}$ les pôles d'entrée de $H'$.

Nous appellerons schéma composé de $H$ et $H'$ et noterons $H_0 H'$ le schéma $H''(p_1, p_3)$ obtenu en contractant les pôles de sortie de $H$ avec les pôles d'entrée de $H'$ de même indice et en choisissant pour pôles d'entrée (resp. de sortie) de $H''$ les pôles d'entrée de $H$ (resp. les pôles de sortie de $H'$).

Soient $M, M', M''$ les matrices associées à $H, H', H''$ Shannon [37 bis] et Povarov [32] ont montré que si $H$ et $H'$ sont fortement disjonctifs, on a la relation $M'' = M \cdot M'$ (les additions étant effectuées au sens booléen).
Nous allons étendre ce résultat. Nous noterons $f_{ab}$ (resp. $f'_{ab}$ ou $f''_{ab}$) les fonctions de transmission entre a et b dans H (resp. H' ou H'').

THÉORÈME 1 [20]. — Si deux schémas $H(p_1, p_2)$ et $H'(p_2, p_3)$ sont faiblement disjonctifs et ont pour matrices associées $M$ et $M'$, la matrice de leur composé $H'' = H \circ H'$ est $M'' = M \cdot M'$.

DÉMONSTRATION. — Soient $i_j$ et $t'_k$ deux pôles d'entrée et de sortie de $H''$. On a évidemment

$$f''_{i_j t'_k} \ge \sum_{l=1}^{p_2} f_{i_j t_l} \cdot f'_{i'_l t'_k}$$

Montrons inversement que la transmission $\tau_{c'_{i'_j t'_k}}$ de toute chaîne élémentaire $c''_{i'_j t'_k}$ reliant $i_j$ et $t'_k$ dans $H''$ vérifie

$$\tau_{c''_{i'_j t'_k}} \le \sum_{l=1}^{p_2} f_{i'_j t_l} \cdot f'_{i'_l t'_k}$$

La chaîne $c''_{i'_j t'_k}$ peut être décomposée en une suite de chaînes plus courtes contenues alternativement dans les multigraphes $G = (S, A, \Gamma)$ et $G' = (S', A', \Gamma')$ de $H$ et $H'$. Nous définissons ces chaînes par leurs sommets

$$ \left. \begin{array}{l} (i_j \dots s_1) \ (s_1 \dots s_2) \ \dots \ (s_{2\lambda} \dots s_{2\lambda+1}) \ (s_{2\lambda+1} \dots s_{2\lambda+2}) \ \dots \ (s_{2m+1} \dots t'_k) \\ (s_{2\lambda} \dots s_{2\lambda+1}) \in S \\ (s_{2\lambda+1} \dots s_{2\lambda+2}) \in S' \end{array} \right\} \quad \text{pour } \lambda \in \{0, 1, \dots m\} $$

Désignons par

$c_{i_j s_1}, c'_{s_1 s_2}, \dots c_{s_2 \lambda} s_{2\lambda+1}, c'_{s_{2\lambda+1} s_{2\lambda+2}}, \dots c'_{s_{2m+1} t'_k}$ ces parties successives de $c'_{i_j t'_k}$.

Nous pouvons écrire

$$ \begin{aligned} \tau_{c''_{i'_j t'_k}} &= \tau_{c_{i'_j s_1}} \cdot \prod_{\lambda=1}^{m} \tau_{c_{s_2 \lambda} s_{2 \lambda+1}} \cdot \tau_{c'_{2m+1 t'_k}} \cdot \prod_{\lambda=0}^{m-1} \tau_{c'_{s_{2\lambda+1} s_{2\lambda+2}}} \\ &\le f_{i'_j s_1} \cdot \prod_{\lambda=1}^{m} f_{s_2 \lambda s_{2\lambda+1}} \cdot f'_{s_{2m+1} t'_k} \cdot \prod_{\lambda=0}^{m-1} f'_{s_{2\lambda+1} s_{2\lambda+2}} \end{aligned} $$

H et $H'$ étant faiblement disjonctifs, il découle de la pro-
position 3 que

$$\tau_{c''_{i'_j t'_k}} \le f_{i'_j s_{2m+1}} \cdot f'_{s_{2m+1} t'_k} \le \sum_{l=1}^{p_2} f_{i'_j t_l} \cdot f'_{i'_l t'_k}$$
## 5. Schémas de type série-parallèle

Considérons le juxtaposé $\{H_1; H_2\}$ de deux schémas bipolaires $H_1$ et $H_2$ ayant pour pôles d'entrée $I_1$ et $I_2$ et pour pôles de sortie $T_1$ et $T_2$. Le schéma H obtenu en contractant $I_1$ et $I_2$ d'une part, $T_1$ et $T_2$ d'autre part, et en choisissant pour pôle d'entrée (resp. de sortie) le contracté de $I_1$ et $I_2$ (resp. de $T_1$ et $T_2$) est appelé *connexion en parallèle de H₁ et H₂*.

Le schéma $H' = H_1 \circ H_2$, composé de $H_1$ et $H_2$ est appelé *connexion en série de H₁ et H₂*.

Un schéma bipolaire est de type série-parallèle s'il n'a qu'un seul contact ou s'il est une connexion en série ou en parallèle de deux schémas de type série-parallèle.

La proposition suivante découle immédiatement de ces définitions.

**PROPOSITION 3.** – Soient deux schémas bipolaires $H_1$ et $H_2$, $f_1$ et $f_2$ les fonctions de transmissions réalisées par ces deux schémas. La connexion en parallèle de $H_1$ et $H_2$ réalise la fonction $f_1 + f_2$. La connexion en série de $H_1$ et $H_2$ réalise la fonction $f_1 \cdot f_2$.

Considérons une fonction booléenne $f \in \mathfrak{F}_n$ et soit $E_f$ une expression de la fonction $f$ au moyen des générateurs $x_1^*, x_2^*, \dots, x_n^*$ et des opérations d'addition, de multiplication et de complémentation. Nous noterons $l(E_f)$ le nombre d'apparitions des générateurs dans l'expression $E_f$.

**PROPOSITION 4.** – Soit une fonction $f \in \mathfrak{F}_n$, $E_f$ une expression de $f$. Il existe un schéma bipolaire de type série-parallèle réalisant la fonction $f$ et ayant $l(E_f)$ contacts.

En effet, au moyen des règles de l'algèbre booléenne, il est toujours possible de transformer $E_f$ en une expression $E'_f$ où le signe de la complémentation n'apparait que sur les générateurs et telle que $l(E'_f) = l(E_f)$.

La proposition 3 permet alors de construire le schéma cherché.
## 6. Construction d'un schéma H (1, 2ⁿ) réalisant tous les produits élémentaires de n variables (arbre de décodage)

Les résultats exposés dans cette section sont dûs à Shannon, Hamming [14] et Lupanov [29]. Nous considérerons exceptionnellement l'ensemble $B = \{0, 1\}$ comme le corps des entiers modulo 2 et $B^n$ comme un espace vectoriel sur ce corps. La somme de deux vecteurs $\vec{a}$ et $\vec{b} \in B^n$ sera notée $\vec{a} \oplus \vec{b}$.

### 6.1. - Partition de $B^n$ en sphères de rayon unité

Soient deux éléments $\vec{a}$ et $\vec{b} \in B^n$. On appelle *distance* $d(\vec{a}, \vec{b})$ des éléments $\vec{a}$ et $\vec{b}$ le nombre de coordonnées par lesquels ils diffèrent.

L'ensemble $\mathfrak{S}_n = \{\vec{x} | \vec{x} \in B^n \text{ et } d(\vec{a}, \vec{x}) = 1\}$ appelle sphère de centre $\vec{a}$ et de rayon 1.

Posons :

$$Z_2^n = \{\vec{x} | \vec{x} \in B^n, |s(\vec{x})| \geq 2\}$$

On a :

$$|Z_2^n| = 2^n - m - 1$$

Soit $L$ la matrice à $2^n - m - 1$ lignes et $m$ colonnes constituée par les éléments de $Z_2^n$ (rangés dans un ordre quelconque).

$$L = \left\{ \begin{array}{c} \begin{array}{|c|c|c|c|c|c|c|} \hline 1 & 1 & 0 & 0 & \dots & 0 \\ \hline 1 & 0 & 1 & 0 & \dots & 0 \\ \hline \multicolumn{7}{c}{\text{m colonnes}} \\ 1 & 1 & 1 & \dots & 1 & 1 \\ \hline \end{array} & 2^n - m - 1 \\ \hline \end{array} \right\}$$

$U_{2^{m}-m-1}$ désignant la matrice unité d'ordre $2^m - m - 1$ posons :

$$M_m^0 = ||U_{2^m - m - 1}, L||$$

Les lignes de cette nouvelle matrice peuvent être considérées comme des éléments de $B^{2^m-1}$. Notons $\mathfrak{M}_m^0$ l'ensemble de ces
<table><caption>Tableau 1</caption><tbody><tr><td>a<sub>1</sub></td><td>1</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td></tr><tr><td>a<sub>2</sub></td><td>0</td><td>1</td><td>0</td><td>0</td><td>1</td><td>0</td><td>1</td></tr><tr><td>a<sub>3</sub></td><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td><td>1</td><td>1</td></tr><tr><td>a<sub>4</sub></td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>a<sub>1</sub></td><td>1</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td></tr><tr><td>a<sub>2</sub></td><td>0</td><td>1</td><td>0</td><td>0</td><td>1</td><td>0</td><td>1</td></tr><tr><td>a<sub>3</sub></td><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td><td>1</td><td>1</td></tr><tr><td>a<sub>4</sub></td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><td>a<sub>1</sub> &oplus; a<sub>2</sub></td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td></tr><tr><td>a<sub>1</sub> &oplus; a<sub>3</sub></td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td></tr><tr><td>a<sub>1</sub> &oplus; a<sub>4</sub></td><td>1</td><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td><td>1</td></tr><tr><td>a<sub>2</sub> &oplus; a<sub>3</sub></td><td>0</td><td>1</td><td>1</td><td>0</td><td>1</td><td>1</td><td>0</td></tr><tr><td>a<sub>2</sub> &oplus; a<sub>4</sub></td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td></tr><tr><td>a<sub>3</sub> &oplus; a<sub>4</sub></td><td>0</td><td>0</td><td>1</td><td>1</td><td>1</td><td>0</td><td>0</td></tr><tr><td>a<sub>1</sub> &oplus; a<sub>2</sub> &oplus; a<sub>3</sub></td><td>1</td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>a<sub>1</sub> &oplus; a<sub>2</sub> &oplus; a<sub>4</sub></td><td>1</td><td>1</td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td></tr><tr><td>a<sub>1</sub> &oplus; a<sub>3</sub> &oplus; a<sub>4</sub></td><td>1</td><td>0</td><td>1</td><td>1</td><td>0</td><td>1</td><td>0</td></tr><tr><td>a<sub>2</sub> &oplus; a<sub>3</sub> &oplus; a<sub>4</sub></td><td>0</td><td>1</td><td>1</td><td>1</td><td>0</td><td>0</td><td>1</td></tr><tr><td>a<sub>1</sub> &oplus; a<sub>2</sub> &oplus; a<sub>3</sub> &oplus; a<sub>4</sub></td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr></tbody></table>

éléments. Soit alors $\mathcal{M}_m$ l'ensemble des combinaisons linéaires des éléments de $\mathcal{M}_m^0$. Le tableau 1 représente les éléments de $\mathcal{M}_3$.

Les éléments de $\mathcal{M}_m^0$ étant linéairement indépendants, $\mathcal{M}_m$ contient $2^{2^m-1}$ éléments distincts. On peut alors énoncer

LEMME 1 [14]. — La distance entre deux éléments quelconques de $\mathcal{M}_m$ est supérieure ou égale à 3.

DÉMONSTRATION. — a) Quels que soient $\vec{a}$ et $\vec{b}$ appartenant à $\mathcal{M}_m$, on a $a \oplus b \in \mathcal{M}_m$. Comme $d(\vec{a}, \vec{b}) = |s(\vec{a} \oplus \vec{b})|$ il suffit donc de montrer que pour tout élément $\vec{a} \in \mathcal{M}_m$ on a $|s(\vec{a})| \ge 3$, (ou $|s(\vec{a})| = 0$)
Désignons par $N(\hat{a})$, $N_1(\hat{a})$, $N_2(\hat{a})$ respectivement le nombre de coordonnées non nulles

- de $\hat{a}$

- parmi les $2^m - m - 1$ premières coordonnées de $\hat{a}$

- parmi les m dernières coordonnées de $\hat{a}$

$$N(\hat{a}) = N_1(\hat{a}) + N_2(\hat{a}).$$

Par définition de $\mathfrak{N}_m$, on a $N_1(\hat{a}) \ge 1$ pour tout $\hat{a} \ne 0$.

On distingue alors 3 cas

$$1/ \quad N_1(\hat{a}) = 1 \quad \text{alors} \quad \hat{a} \in \mathfrak{N}_m^0 \quad \text{et} \quad N_2(\hat{a}) \ge 2$$

$$2/ \quad N_1(\hat{a}) = 2 \quad \text{alors} \quad a = \hat{a}_1 \oplus \hat{a}_2 \quad \text{où} \quad \hat{a}_1, \hat{a}_2 \in \mathfrak{N}_m^0 \quad \text{et donc} \\ N_2(\hat{a}) \ge 1$$

$$3/ \quad N_1(\hat{a}) \ge 3.$$

LEMME 2 [29] - *Il existe une partition de $B^{2^m}$ en $\frac{2^{2^m}}{2^m}$ sphères de rayon-unité.*

Considérons l'ensemble des sphères de rayon unité ayant pour centre les éléments de $B^{2^m}$ de la forme $\hat{a}' = (a_0, \hat{a})$ avec $a_0 \in B$, $\hat{a} \in \mathfrak{N}_m$. Montrons que ces sphères sont deux à deux disjointes.

Soient $\hat{a}' = (a_0, \hat{a})$ et $\hat{b}' = (b_0, \hat{b})$ les centres de deux sphères distinctes $\mathfrak{S}_{\hat{a}'}$ et $\mathfrak{S}_{\hat{b}'}$.

1/ Si $\hat{a}' \ne \hat{b}'$ alors d'après le lemme 1 $d(\hat{a}', \hat{b}) \ge 3$ et par conséquent $\mathfrak{S}_{\hat{a}'}$ et $\mathfrak{S}_{\hat{b}'}$ sont disjointes.

2/ Supposons $\hat{a} = \hat{b} = (a_1, a_2, \dots, a_{2^m-1})$ et $a_0 \ne b_0$. La sphère $\mathfrak{S}_{\hat{a}'}$ contient les éléments $(b_0, a_1, a_2, \dots, a_{2^m-1})$, $(a_0, \bar{a}_1, a_2, \dots, a_{2^m-1})$ ... $(a_0, a_1, a_2, \dots, \bar{a}_{2^m-1})$ et la sphère $\mathfrak{S}_{\hat{b}'}$ contient les éléments $(a_0, a_1, a_2, \dots, a_{2^m-1})$, $(b_0, \bar{a}_1, a_2, \dots, a_{2^m-1})$ ... $(b_0, a_1, a_2, \dots, \bar{a}_{2^m-1})$. Ici encore $\mathfrak{S}_{\hat{a}'}$ et $\mathfrak{S}_{\hat{b}'}$ sont disjointes.

Le nombre des sphères est $2 \times 2^{2^m-1}$ ; chacune contenant $2^m$ éléments, tout élément de $B^{2^m}$ appartient donc à une et une seule sphère.
Posons $r = 2^n$, désignons par $S_1(1 \le l \le \frac{2^r}{r})$ la lèmysphère de la partition de $B^r$ définie par le lemme précédent et soit $\chi_{S_1}(x_1, x_2, \dots, x_r)$ sa fonction caractéristique.

Posons de plus $$ x_1^\sigma = \begin{cases} \frac{x_1}{x_1} & \text{si } \sigma = 1 \\ \frac{x_1}{x_1} & \text{si } \sigma = 0 \end{cases} $$

**PROPOSITION 5.** — Si $\vec{a} = (a_1, a_2, \dots, a_r)$ est le centre de $S_1$, la fonction $\chi_1$ vérifie les égalités

$$1/ \quad \chi_{S_1}(x_1, x_2, \dots, x_r) \cdot x_1^{\vec{a}_1} = x_1^{a_1} x_2^{a_2} \cdots x_{1-1}^{a_{1-1}} x_1^{\vec{a}_1} x_1^{a_1+1} \cdots x_r^{a_r}$$

$$2/ \quad \chi_{S_1}(x_1, x_2, \dots, x_r) \cdot x_1^{\vec{a}_1} x_2^{\vec{a}_2} \cdots = 0 \quad \text{pour} \quad 1 \le i \le j \le r$$

En effet

$$\chi_{S_1}(x_1, x_2, \dots, x_r) = x_1^{\vec{a}_1} x_2^{\vec{a}_2} \cdots x_r^{\vec{a}_r} + x_1^{a_1} x_2^{a_2} \cdots x_r^{a_r} + \cdots + x_1^{a_1} x_2^{a_2} \cdots x_r^{a_r}$$

## 6.2. - Construction d'un arbre de décodage - Méthode de Shannon.

Un arbre de décodage d'ordre $n$ est un schéma de contacts $D(1, 2^n)$ réalisant entre son pôle d'entrée et ses pôles de sortie tous les produits élémentaires de $n$ générateurs.

**PROPOSITION 6.** — *Un arbre de décodage* $D(1, 2^n)$ *fortement disjonctif peut être construit au moyen de* $2^{n+1} - 2$ *contacts.*

Le schéma $D(1, 2^n)$ est représenté sur la figure 6.

<figure><img src="image_12.png" /><figcaption>Fig. 6</figcaption></figure>
Désignons par $D_1$ l'arbre de décodage à deux contacts pour la seule variable $x_1$ (figure 7).

<figure><img src="image_13.png" /><figcaption>Fig. 7</figcaption></figure>

En utilisant les notations de la section 3 on a

$$D = D_1 \circ D_2^{(2)} \circ D_3^{(2^2)} \dots \circ D_1^{(2^{1-1})} \circ \dots \circ D_n^{(2^{n-1})}$$

Le nombre de contacts de D est $2^{n+1} - 2$.

### 6.3. - Construction d'un arbre de décodage - Méthode de Lupanov.

Soit un nombre $r = 2^m$ (m entier), vérifiant $r \le n$. Identifiant les ensembles $B^n$ et $B^r \times B^{n-r}$ il résulte du lemme 2 que l'on peut écrire

$$B^n = \sum_{l=1}^{2^r} \mathfrak{S}_1 \times B^{n-r}$$

Soit un élément

$$x = (x_1, x_2, \dots, x_r, x_{r+1}, \dots, x_n) \in B^n$$

Posons

$$x = (u, v)$$

avec

$$u = (x_1, x_2, \dots, x_r) \in B^r$$

$$v = (x_{r+1}, x_{r+2}, \dots, x_n) \in B^{n-r}$$

**LEMME 3.** – *Un schéma* $H_1(1, r2^{n-r})$, *faiblement disjonctif, réa-* lisant tous les produits élémentaires associés à l'ensemble $\mathfrak{S}_1 \times B^{n-r}$ *ne nécessite pour sa construction pas plus de* $r^2 + (2^{n-r+1} - 2) + r2^{n-r}$ *contacts.*

**DÉMONSTRATION.** – a) La fonction caractéristique $u \to \chi_{\mathfrak{S}_1}(u)$ de la sphère $\mathfrak{S}_1$ peut être réalisée par un schéma bipolaire $S_1$ ayant $r^2$ contacts ou moins (par exemple par un schéma série-parallèle construit selon l'expression de $\chi_{\mathfrak{S}_1}$ donnée plus haut).

b) Un arbre de décodage $D(1, 2^{n-r})$ pour les variables $x_{r+1}, x_{r+2}, \dots, x_n$ peut être construit avec $(2^{n-r+1}-2)$ contacts (proposition 6).
c) Soit $a = (a_1, a_2, \dots a_r)$ le centre de $S_1$ et désignons par $R_1(1, r)$ un schéma réalisant les $r$ fonctions $x \to x_1^{a_1}, 1 \le i \le r$ avec $r$ contacts (figure 8).

<figure><img src="image_14.png" /><figcaption>Fig. 8</figcaption></figure>

Considérons alors le schéma $H_1 = S_1 \circ D \circ R_1^{(2^{n-r})}$ (figure 9) pour tout $b \in B^{n-r}$ contacts.

<figure><img src="image_15.png" /><figcaption>Fig. 9</figcaption></figure>

Le schéma $S_1 \circ D$ est un schéma $(1, 2^{n-r})$-polaire qui pour tout $b \in B^{n-r}$ réalise la fonction

$$ (u, v) \to \chi_{S_1}(u) \cdot \chi_b(v) $$

Il résulte alors de la proposition (5.1) que le schéma $H_1$ réalise tous les $r 2^{n-r}$ produits élémentaires associés aux éléments de $S_1 \times B^{n-r}$.

(En effet si

$$ i \in \{1, 2, \dots, r\}, \chi_{S_1}(u), \chi_b(v), x_1^{\tilde{a}_1} = \chi_{\alpha}(u), \chi_b(v) = \chi_{(\alpha b)}(u, v) $$
avec

$$ \alpha = (a_1, a_2, \dots a_{1-1}, \bar{a}_1, a_{1+1}, \dots a_r) \in \mathbb{S}_I. $$

Montrons que $H_1$ est faiblement disjonctif : soient $t, t', t''$ ($t' \neq t''$) trois pôles de sortie de $H_1$.

On a

$$ f_{It}(x) \leq \chi_I(u) $$

$$ f_{t',t''}(x) \leq x_i^{\bar{a}_i} x_j^{\bar{a}_j} \quad 1 \leq i < j \leq r $$

Il résulte de la proposition 5.2 que pour tout $x \in \mathbb{B}^n$

$$ f_{It}(x) \cdot f_{t',t''}(x) \leq \chi_I(u) \cdot x_i^{\bar{a}_i} x_j^{\bar{a}_j} = 0 \leq f_{It''}(x) $$

D'après la proposition 2, $H_1$ est donc un schéma faiblement disjonctif.

IMPRIMERIE LOUIS-JEAN

Publications scientifiques et littéraires
TYPO - OFFSET

05 - GAP - Téléphone 14-23/14-24
Dépôt légal : n° 441 1968

Pour les références et la Table des matières voir le Fascicule 4

<figure><img src="image_16.png" /></figure>