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

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 II. Annales de l’ISUP, 1967, XVI (4), pp.219-294. hal-04083925

HAL Id: hal-04083925

https://hal.science/hal-04083925

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>
<figure><img src="image_3.png" /></figure>

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

G. HANZET

FACULTÉ
DE
NÉCESSITÉ
PROBLEME
DE
DÉMONSTRATION
DE
PROBLEMES
DE
DÉMONSTRÉMENT

ET D'EVALUATION

G. HANZET

PROBLEME DE DÉMONSTRÉMENT

$$ (a-b)(a-b^2)(a-b^3)(a-b^4) $$

Si $a > b$ et $a \neq b$ et $a \neq b^2$ et $a \neq b^3$ et $a \neq b^4$,

$$ (a-b)(a-b^2) $$

Ou

Si $a < b$ et $a \neq b$ et $a \neq b^2$ et $a \neq b^3$ et $a \neq b^4$,

$$ (a-b)(a-b^2)(a-b^3)(a-b^4) $$

Si $a > b$ et $a \neq b$ et $a \neq b^2$ et $a \neq b^3$ et $a \neq b^4$,

Ou

Publ. Par. Scien. Unité Dussa

SÉRIE C, N° 500
# 5. Schémas de contacts et fonctions booléennes croissantes

## Introduction

Désignons par $E_f$ le nombre minimal de contacts suffisant pour construire un schéma bipolaire réalisant une fonction booléenne donnée $f$.

Posons

$$E(n) = \max_{f \in \mathcal{F}_n} E_f$$

$$E^+(n) = \max_{f \in \mathcal{I}_n} E_f$$

Soit $I_n^s$ l'ensemble des fonctions booléennes croissantes de $n$ variables pouvant être réalisées par un schéma ayant $s$ contacts (ou moins).

On peut montrer (section 3, théorème 2) à partir de résultats de Shannon [37 bis] que quel que soit $\varepsilon > 0$,

$$\text{pour} \quad s = \sqrt{\frac{2}{\pi}} \frac{2^n}{n\sqrt{n}} (1-\varepsilon) \quad \lim_{n \to \infty} \frac{|I_n^s|}{|I_n|} = 0$$

En d'autres termes, lorsque $n$ est assez grand, la plupart des fonctions de $I_n$ exigent pour leur réalisation plus de

$$\sqrt{\frac{2}{\pi}} \frac{2^n}{n\sqrt{n}} (1 - \varepsilon) \text{ contacts et par conséquent}$$

$$\sqrt{\frac{2}{\pi}} \frac{2^n}{n\sqrt{n}} (1 - \varepsilon) < E^+(n)$$

D'un autre côté, Lupanov [29] a montré en donnant une procédure de construction explicite que toute fonction $f \in \mathcal{F}_n$ peut être réalisée par un schéma bipolaire contenant moins de $\frac{2^n}{n} \left[ 1 + O\left(\frac{1}{\sqrt{n}}\right) \right]$ contacts*.

<footnote>* Ce résultat, joint aux travaux antérieurs de Shannon [37 bis] établit que $E(n) \sim \frac{2^n}{n}$.</footnote>
Cependant cette procédure, lorsqu'elle est appliquée à une fonction croissante, ne conduit pas à des résultats sensiblement meilleurs. Il en est de même des méthodes antérieurement développées par Shannon [37 bis] et Povarov [32, 33].

L'objet du présent chapitre [20] est d'exposer une nouvelle méthode permettant de réaliser toute fonction croissante $f \in L_1$ par un schéma ayant moins de

$$ \frac{2^{n+1}(\text{Log}_2 n)}{n \sqrt{\pi n}} \left[ 1 + O\left( \frac{1}{\text{Log}_2 n} \right) \right] \text{ contacts} $$

Ceci établit, pour $n$ assez grand, les inégalités

$$ \sqrt{\frac{2}{\pi}} \frac{2^n}{n\sqrt{n}} (1-\epsilon) < E^+(n) < \sqrt{2} (\text{Log}_2 n) \sqrt{\frac{2}{\pi}} \frac{2^n}{n\sqrt{n}} \left[ 1 + O\left( \frac{1}{\text{Log}_2 n} \right) \right] $$

La méthode de construction présentée abaisse donc de $\sqrt{\frac{n\pi}{2}}$ à $\sqrt{2} \text{Log}_2 n$ le rapport entre les bornes supérieures et inférieures de $E^+(n)$.

# 1. Décomposition des fonctions booléennes

## 1.1. - Cas général

1.1.1. - Une fonction booléenne $f: B^n \rightarrow B$ peut être identifiée à une application de $B^k \times B^{n-k}$ dans $B$.

Notons

$$ x = (x_1, x_2, \dots, x_k, x_{k+1}, \dots, x_n) = (y, z) $$

$$ \text{avec } y = (x_1, x_2, \dots, x_k) \in B^k $$

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

Soient $a_1, a_2, \dots, a_{2^k}$ (respect. $b_1, b_2, \dots, b_{2^k}$) les éléments de $B^k$ (respect. de $B^{n-k}$) disposés dans un certain ordre.

La fonction $f$ est définie par la donnée d'une table à double entrée (tableau 1) indiquant pour chaque couple $(a, b)$ la valeur $f(a, b)$.
Considérons des partitions de $B^k$ et $B^{n-k}$

$$B^k = L_1 + L_2 + \dots + L_{i_1} + \dots + L_{i_p}$$

$$B^{n-k} = C_1 + C_2 + \dots + C_j + \dots + C_q$$

Soient $f_{ij} : B^k \times B^{n-k} \rightarrow B$ la fonction coincidant avec $f$ sur $L_1 \times C_j$ et nulle partout ailleurs. Alors pour tout $x \in B^n$

$$f(x) = \sum_{i,j} f_{i,j}(y, z) \quad (1)$$

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

1.1.2. - Soit $\alpha_1, \alpha_2, \dots, \alpha_{|L_1|}$ la suite des éléments de $L_1$ et soit $f_{ij}^* : C_j \to B^{|L_1|}$ l'application définie par

$$z \to f_{ij}^*(z) = [f_{ij}(\alpha_1, z), f_{ij}(\alpha_2, z), \dots, f_{ij}(\alpha_{|L_1|}, z)]$$
Cette application induit une partition de $C_j$ en classes d'équivalence.

Posons

$$C_{j,i}^t = \{z \mid z \in C_j \text{ et } f_{ij}^*(z) = t\}$$

alors

$$C_j = \sum_{t \in f_{ij}^*(C_j)} C_{j,i}^t \quad (i \in \{1, 2, \dots, p\}) \qquad (2)$$

Pour tout $i \in \{1, 2, \dots, p\}$, le nombre $|f_{ij}^*(C_j)|$ de classes d'équivalence vérifie

$$|f_{ij}^*(C_j)| \le 2^{|L_i|}$$

D'autre part, à tout $t \in B^{|L_i|}$ nous associons le sous-ensemble $L_i^t \subset L_i$ défini par

$$L_i^t = \{\alpha_\lambda \mid \alpha_\lambda \in L_i \text{ et } \lambda \in s(t)\}$$

(rappelons que $s(t)$ désigne le support de $t$).

Sur le tableau 1, nous avons indiqué les éléments de $L_i^t$ et $C_{j,i}^t$ pour $t = (1, 0, 1, 0) : L_i^{1010} = \{\alpha_1, \alpha_3\}$ et $C_{j,i}^{1010} = \{\beta_1, \beta_3\}$.

1.1.3. - Soit $f_{ij}^t : B^k \times B^{n-k} \to B$ la fonction coincidant avec $f_{ij}$ sur $L_i \times C_{j,i}^t$ et nulle partout ailleurs.

De (2) il résulte que

$$f_{ij}(y, z) = \sum_{t \in f_{ij}^*(C_j)} f_{ij}^t(y, z) \qquad (3)$$

Mais, par définition de l'ensemble $L_i^t$, la fonction $f_{ij}^t$ a pour ensemble caractéristique $K_{f_{ij}^t} = L_i^t \times C_{j,i}^t$ et par conséquent

$$f_{ij}^t(y, z) = \chi_{L_i^t}(y) \cdot \chi_{C_{j,i}^t}(z) \qquad (4)$$

où $y \to \chi_{L_i^t}(y)$ (respect. $z \to \chi_{C_{j,i}^t}(z)$) est la fonction caractéristique de $L_i^t$ (respect. de $C_{j,i}^t$).

Il résulte de (1), (3), (4) que nous pouvons énoncer

**PROPOSITION 1.** - Toute fonction booléenne $f \in \mathfrak{F}_n$ peut se décomposer selon l'expression

$$f(x) = \sum_{i=1}^{p} \sum_{j=1}^{q} \sum_{t \in f_{ij}^*(C_j)} \chi_{L_i^t}(y) \cdot \chi_{C_{j,i}^t}(z) \qquad (5)$$
## 1.2. - Cas d'une fonction croissante

Soit une fonction $g \in \mathcal{F}_n$ et soit $K_g$ son ensemble caractéristique. Nous noterons $g^+$ la fonction croissante de n variables ayant pour ensemble fondamental $Mg^+$ l'ensemble des éléments minimaux de $K_g$

$$g^+(x) = \begin{cases} 1 & \text{s'il existe } a \le x \text{ tel que } g(a) = 1 \\ 0 & \text{sinon} \end{cases}$$

En particulier considérons un produit élémentaire

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

on a

$$\chi_a^+ = \prod_{i \in s(a)} x_i^* = \Phi_a$$

($\Phi_a$ produit fondamental associé à l'élément a)

**PROPOSITION 2.** — Toute fonction booléenne croissante $f \in I_n$ peut se décomposer selon l'expression

$$f(x) = \sum_{i=1}^{p} \cdot \sum_{j=1}^{q} \cdot \sum_{t \in f_{ij}^*(c_j)} \chi_{L_i^t}^*(y) \cdot \chi_{c_j, i}^*(z) \quad (6)$$

**DÉMONSTRATION.** — Comme $\chi_{L_i^t}^* \ge \chi_{L_i^t}^*(y)$ on a, en tenant compte de la proposition 1

$$f(x) \le \sum_{i=1}^{p} \cdot \sum_{j=1}^{q} \cdot \sum_{t \in f_{ij}^*(c_j)} \chi_{L_i^t}^*(y) \cdot \chi_{c_j, i}^*(z)$$

Montrons l'inégalité opposée.

Soit un élément $(a, b) \in B^k \times B^{n-k}$ et supposons qu'il existe $i, j, t$ tels que $\chi_{L_i^t}^*(a) = \chi_{c_j, i}^*(b) = 1$.

Par définition de $\chi_{L_i^t}^*$ il existe $a' \le a$ tel que $\chi_{L_i^t}^*(a') = 1$ donc $f(a', b) = 1$ et $f$ étant croissante, on a $f(a, b) = 1$.

## 2. Construction d'un schéma bipolaire pour une fonction $f \in I_n$

Nous allons appliquer la décomposition précédente pour construire un schéma de contacts bipolaire réalisant une fonction croissante quelconque donnée $f \in I_n$.
## 2.1 - Choix des ensembles ($L_i$) $1 \le i \le p$

Considérons la partition $\Pi_k$ de $B^k$ en $C_k^{[\frac{k}{2}]}$ chaînes con- nexes obtenue au chapitre 1. Disposons les chaînes de $\Pi_k$ dans un certain ordre

$$ \Pi_k = \{J_1, J_2, \dots, J_{\lambda}, \dots, J_{\frac{k}{2}}\} $$

De plus, pour simplifier les écritures ultérieures, posons

$$ |J_{\lambda}| + 1 = j_{\lambda}, \quad 1 \le \lambda \le \left\lfloor C_k^{[\frac{k}{2}]} \right\rfloor $$

On a donc

$$ \sum_{\lambda=1}^{[\frac{k}{2}]} j_{\lambda} = 2^{k} + C_{k}^{[\frac{k}{2}]} $$

Les nombres $j_\lambda$ étant tous positifs, leur moyenne arithmétique est supérieure à leur moyenne géométrique et par suite

$$ \prod_{\lambda=1}^{[\frac{k}{2}]} j_{\lambda} \le \left( \frac{2^k}{C_k^{[\frac{k}{2}]}} + 1 \right)^{C_k^{[\frac{k}{2}]}} $$

D'autre part, quel que soit $\lambda \in \{1, 2, \dots, C_k^{[\frac{k}{2}]}\}, 2 \le j_\lambda \le k+2$.

Posons maintenant $d = \lfloor \frac{n}{2} - \sqrt{n} \rfloor$ et définissons les nombres $d_1, d_2, \dots, d_{\frac{1}{2}}, \dots, d_{\frac{n}{2}-1}$ par les inégalités

$$ \left. \begin{array}{r@{\,}c@{\,}l@{\quad}l} \displaystyle\prod_{\lambda=1}^{d_1} & j_{\lambda} & \le 2^d & < \displaystyle\prod_{\lambda=1}^{d_1+1} j_{\lambda} \\[1.5ex] \displaystyle\prod_{\lambda=d_1+1}^{d_2} & j_{\lambda} & \le 2^d & < \displaystyle\prod_{\lambda=d_1+1}^{d_2+1} j_{\lambda} \\[1.5ex] \multicolumn{3}{c}{\text{...................}} \\[1.5ex] \displaystyle\prod_{\lambda=d_1-1}^{d_1} & j_{\lambda} & \le 2^d & < \displaystyle\prod_{\lambda=d_1-1}^{d_1+1} j_{\lambda} \\[1.5ex] \multicolumn{3}{c}{\text{...................}} \\[1.5ex] \multicolumn{3}{c}{\left. \begin{array}{l} \displaystyle\prod_{\lambda=d_{\frac{1}{2}}-1}^{[\frac{k}{2}]} j_{\lambda} \\ \le 2^d \quad \text{et} \quad d_p = C_k^{[\frac{k}{2}]} \end{array} \right|} \end{array} \right\} (7) $$
Nous définissons alors les ensembles $(L_1)_{1 \le i \le p}$ par $L_1 = \sum_{\lambda=d_{i-1}+1}^{d_i} J_\lambda$

Considérant les membres de droite des inégalités (7) on obtient

$$2^{d(p-1)} \le \left( \prod_{\lambda=1}^{k} j_\lambda \right) \left( \prod_{i=1}^{p-2} j_{\lambda_i+1} \right) < \left( \frac{2^k}{c_k^{\frac{k}{2}}} + 1 \right) c_k^{\frac{k}{2}} (k+2)^{p-2}$$

d'où il découle

$$p < \frac{C_k^{\frac{k}{2}} \log \left( \frac{2^k}{C_k^{\frac{k}{2}}} + 1 \right)}{d - \log_2(k+2)} + 1 \quad (8)$$

Enfin, des membres de gauche des inégalités (7), il suit

$$d_1 - d_{1-1} \le d \quad \text{pour tout} \quad i \in \{1, 2, \dots, p\} \quad (9) \\ \text{(on pose } d_0 = 0)$$

## 2.2 - Choix des ensembles $(C_i)_{1 \le i \le q}$

Soit $r$ une puissance entière de 2 vérifiant l'inégalité $r \le n-k$. D'après le lemme 2 du chapitre précédent, il existe une partition de $\mathbb{B}^r$ en sphères de rayon unité

$$\mathbb{B}^r = \sum_{j=1}^{\frac{2^r}{r}} \mathfrak{S}_j \quad (\text{où } \mathfrak{S}_j \text{ est la j\`eme sphère}).$$

Cette partition induit sur $\mathbb{B}^{n-k}$ (identité au produit $\mathbb{B}^r \times \mathbb{B}^{n-k-r}$) la partition

$$\mathbb{B}^{n-k} = \sum_{j=1}^{\frac{2^r}{r}} \mathfrak{S}_j \times \mathbb{B}^{n-k-r}$$

Nous choisissons pour ensemble $C_j, 1 \le j \le \frac{2^r}{r}$

$$C_j = \mathfrak{S}_j \times \mathbb{B}^{n-k-r}$$
PROPOSITION 3. - Le nombre $|f_{ij}^*(C_j)|$ de classes d'équivalence de $C_j$ suivant l'application $f_{ij}^* : C_j \to B^{|L_i|}$ vérifie l'inégalité

$$|f_{ij}^*(C_j)| \le 2^d$$

DÉMONSTRATION. - Considérons l'ensemble $L_i = \sum_{\lambda=d_{i-1}+1}^{d_i} J_\lambda$ et soient $a_\lambda^1, a_\lambda^2, \dots, a_\lambda^T, \dots, a_\lambda^{v\lambda}$ les éléments de la chaîne $J_\lambda$ disposés dans l'ordre décroissant.

Soit un élément quelconque $b \in C_j$ et notons $t_b^\lambda$ la suite

$$t_b^\lambda = [f_{ij}(a_\lambda^1, b), f_{ij}(a_\lambda^2, b), \dots, f_{ij}(a_\lambda^T, b), \dots, f_{ij}(a_\lambda^{v\lambda}, b)]$$

Soit $m_b^\lambda$ le plus grand entier (s'il existe) tel que $f_{ij}(a_\lambda^{\underline{m_b^\lambda}}, b) = 1$.

La fonction $f_{ij}$ est croissante sur $L_i \times C_j$ et par suite

$$f_{ij}(a_\lambda^T, b) = \begin{cases} 1 & \text{si } \tau \le m_b^\lambda \\ 0 & \text{si } \tau > m_b^\lambda \end{cases}$$

La suite $t_b^\lambda$ est donc bien définie par la valeur de $m_b^\lambda$ et le nombre de suites $t_b^\lambda$ possibles distinctes, b variant et $\lambda$ restant fixe est $|J_\lambda| + 1 = j_\lambda$.

Or, l'élément $f_{ij}^*(b) \in B^{|L_i|}$ est constitué par la juxtaposition des suites $t_b^\lambda, d_{i-1} + 1 \le \lambda \le d_i$.

Par conséquent

$$|f_{ij}^*(C_j)| \le \sum_{\lambda=d_{i-1}+1}^{d_i} j_\lambda \le 2^d \quad (\text{d'après les inégalités (7)})$$

## 2.3 - Construction d'un schéma de f - Borne supérieure pour $E^*(n)$

### 2.3.1. - Principe.

Posons

$$\sum_{t \in f_{ij}^*(C_j)} \chi_{L_i^t}^+(y_i) \cdot \chi_{C_j, i}^t(z) = \phi_{i,j}(y, z)$$

Pour chaque couple $(i, j)$, $i \in \{1, 2, \dots, p\}$, $j \in \{1, 2, \dots, \lfloor \frac{2^r}{r} \rfloor\}$ on construit un schéma bipolaire $H_{ij}$ réalisant la fonction $\varphi_{ij}$. Le schéma réalisant $f$ est alors obtenu en connectant en parallèle les schémas $H_{ij}$.
Soit $H_{ij}^1(1, |f_{ij}^*(C_j)|)$ un schéma faiblement disjonctif qui, pour tout $t \in f_{ij}^*(C_j)$, réalise la fonction $y \to \chi_{L_i}^t(y)$.

Soit $H_{ij}^2(|f_{ij}^*(C_j)|, 1)$ un schéma faiblement disjonctif qui pour tout $t \in f_{ij}^*(C_j)$, réalise la fonction $z \to \chi_{C_{j,i}}^t(z)$.

Soit $H_{ij} = H_{ij}^1 \circ H_{ij}^2$ le schéma composé de $H_{ij}^1$ et $H_{ij}^2$ obtenu en contractant entre eux les pôles de sortie de $H_{ij}^1$ et les pôles d'entrée de $H_{ij}^2$ correspondant aux mêmes valeurs de $t$.

D'après le théorème 1 du chapitre précédent, $H_{ij}$ réalise la fonction $\varphi_{ij}$.

### 2.3.2. - Construction de $H_{ij}^1$

**PROPOSITION 4.** - Le schéma $H_{ij}^1$ peut être construit avec $2^d \text{ k d contacts (ou moins).}$

**DÉMONSTRATION.** - Pour tout $t \in f_{ij}^*(C_j)$ on construit un schéma bipolaire $H_{ij}^{1t}$ qui réalise la fonction $y \to \chi_{L_i}^t(y)$. $H_{ij}^1$ est alors obtenu en contractant en un pôle unique $I$ les pôles d'entrée de la juxtaposition de ces schémas $H_{ij}^{1t}$ (figure 1). Ainsi $H_{ij}^1$ est faiblement disjonctif.

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

Compte tenu de la proposition 3, il nous suffit de démontrer que quel que soit $t \in f_{ij}^*(C_j)$, le schéma $H_{ij}^{1t}$ peut être construit avec k d contacts (ou moins).

Or $L_i^t$ est réunion de $(d_i - d_{i-1})$ sous-ensembles disjoints

$$L_i^t = \bigcup_{\lambda=d_{i-1}+1}^{d_i} (L_i^t \cap J_\lambda)$$

L'ensemble $L_i^t \cap J_\lambda$, contenu dans la chaîne $J_\lambda$, est totalement ordonné (ou vide).

Soit $\mu_{i\lambda}^t$ son plus petit élément.

Alors on peut écrire

$$\chi_{L_i^t}^t(y) = \sum_{\lambda=d_{i-1}+1}^{d_i} \sum_{a \in L_i^t \cap J_\lambda} \Phi_a(y) = \sum_{\lambda=d_{i-1}+1}^{d_i} \Phi_{\mu_{i\lambda}^t}(y)$$

Un produit fondamental $y \to \Phi_{\mu_{i\lambda}^t}^t(y)$ peut toujours être réalisé avec k contacts (ou moins) en série.
Comme $d_1 - d_{1-1} \le d$ (d'après 9), un schéma bipolaire de type série-parallèle $H_{ij}^t$ peut toujours être construit avec $kd$ contacts.

Remarque. – Le schéma $H_{ij}^1$ obtenu est fermant.

### 2.3.3. - Construction de $H_{ij}^2$

**PROPOSITION 5.** – Un schéma $H_{ij}^2$ peut être construit avec moins de $r^2 + 2^{n-k-r+1} + r 2^{n-k-r}$ contacts.

$$ \text{Par définition } C_j := \mathcal{S}_j \times B^{n-k-r} $$

Il résulte du lemme 3 du chapitre précédent que l'on peut construire un schéma faiblement disjonctif, ($|C_j|, 1$)-polaire, réalisant tous les produits élémentaires associés aux éléments de $C_j$ avec moins de $r^2 + 2^{n-k-r+1} + r 2^{n-k-r}$ contacts. En contractant les pôles d'entrée de ce schéma conformément à la partition $C_j = \sum_{t \in f_{ij}^*(c_j)} C_{j,1}^t$, on obtient le schéma $H_{ij}^2$ cherché.

### 2.3.4. THÉORÈME 1. –

$$ E'(n) < \frac{2^{n+1}}{n \sqrt{\pi n}} \log_2 n \left[ 1 + O\left( \frac{1}{\log_2 n} \right) \right] $$

**DÉMONSTRATION.** – Soit une fonction croissante quelconque $f \in I_h$. On peut construire un schéma bipolaire de $f$ par la méthode exposée en 2.3.1. D'après les propositions 4 et 5, la réalisation d'une fonction $\varphi_{ij}$ exige moins de $2^d k d + r^2 + 2^{n-k-r+1} + r 2^{n-k-r}$ contacts. Par conséquent le nombre minimal $E_f$ de contacts suffisant pour réaliser $f$ vérifie

$$ E_f < p \cdot \frac{2^r}{r} (2^d k d + r^2 + 2^{n-k-r+1} + r 2^{n-k-r}) $$

Soit en tenant compte de l'inégalité (8)

$$ E_f < \underbrace{\left( \frac{C_k^{\left[ \frac{k}{2} \right]} \log_2 \left( \frac{2^k}{C_k^{\left[ \frac{k}{2} \right]}} + 1 \right)}{d - \log_2 (k+2)} + 1 \right)}_{A} + \underbrace{\frac{2^r}{r} (2^d k d + r^2 + 2^{n-k-r+1} + r 2^{n-k-r})}_{B} + \underbrace{C_c}_{C} $$
Utilisant les inégalités [11]

$$ \sqrt{2\pi k} k^k e^{-k} e^{\frac{1}{12k+1}} < k! < \sqrt{2\pi k} k^k e^{-k} e^{\frac{1}{12k}} \quad (10) $$

On peut montrer que

$$ C_k^{\left[\frac{k}{2}\right]} \log_2\left(\frac{2^k}{\left[\frac{k}{2}\right]} + 1\right) < \sqrt{\frac{2}{\pi}} \frac{2^k}{\sqrt{k}} \log_2 \sqrt{k} \left[1 + O\left(\frac{1}{\log_2 k}\right)\right] $$

Posons alors

$$ r = 2^{\left[\frac{1}{2} \log_2 n\right]} $$

$$ \text{d'où il découle } \frac{\sqrt{n}}{2} < r \le \sqrt{n} $$

$$ d = \left\lfloor \frac{n}{2} - \sqrt{n} \right\rfloor $$

$$ k = \left\lfloor \frac{n}{2} - 3 \log_2 n \right\rfloor $$

On obtient

$$ BC = 2^{n-k} \left[ 1 + O\left( \frac{1}{\sqrt{n}} \right) \right] $$

et

$$ ABC < \sqrt{\frac{2}{\pi}} \frac{2^n}{\sqrt{k}} \frac{\log_2 \sqrt{k}}{\frac{n}{2}} \left[ 1 + O\left( \frac{1}{\log_2 k} \right) \right] \left[ 1 + O\left( \frac{1}{\sqrt{n}} \right) \right] $$

d'où

$$ E_f < \frac{2^{n+1}}{n\sqrt{n\pi}} \log_2 n \left[ 1 + O\left( \frac{1}{\log_2 n} \right) \right] $$

La fonction f étant choisie arbitrairement dans $I_n$, le théorème s'en déduit.
### 3. Borne inférieure pour $E^*(n)$

Nous reprenons ici les notations définies en introduction de ce chapitre. De plus, nous désignons par $\mathfrak{F}_n^s$ l'ensemble des fonctions de $\mathfrak{F}_n$ pouvant être réalisées par un schéma bipolaire ayant s contacts (ou moins).

Nous donnons sans démonstration le lemme suivant dû à Shannon [37 bis].

**LEMME 1.**

$$|\mathfrak{F}_n^s| < (12 \text{ ns})^s$$

Nous allons maintenant démontrer

THÉORÈME 2. — Quel que soit $\varepsilon > 0$, si $s = \sqrt{\frac{2}{\pi} \frac{2^n}{n\sqrt{n}}} (1-\varepsilon)$, alors $\lim_{n \to +\infty} \frac{|I_n^s|}{|I_n|} = 0$. Par conséquent pour $n$ assez grand

$$E^+(n) > \sqrt{\frac{2}{\pi} \frac{2^n}{n\sqrt{n}}} (1-\varepsilon)$$

**DÉMONSTRATION.**

a) Au chapitre 1, nous avons montré

$$|I_n| \ge 2^{\frac{n}{2}} \qquad (11)$$

Utilisant les inégalités (10), on montre

$$C_n^{[\frac{n}{2}]} > \sqrt{\frac{2}{\pi} \frac{2^n}{\sqrt{n}}} \left[1 - o\left(\frac{1}{\sqrt{n}}\right)\right] \qquad (12)$$

b) Il résulte du lemme 1 que

$$|I_n^s| \le |\mathfrak{F}_n^s| \le (12 \text{ ns})^s \qquad (13)$$

$$\text{Posons } s = \sqrt{\frac{2}{\pi} \frac{2^n}{n\sqrt{n}}} (1-\varepsilon)$$

De (13) découle que

$$\text{Log}_2 |I_n^s| < \sqrt{\frac{2}{\pi} \frac{2^n}{\sqrt{n}}} (1-\varepsilon) \left[ 1 + O\left(\frac{1}{n}\right) \right]$$
Puis de (11), (12), (14), il suit que

$$ \left| \frac{I_n^s}{I_n} \right| < 2^{\left[ \frac{2}{\pi} \frac{2^n}{\sqrt{n}} \cdot (-\epsilon + 0(\frac{1}{n})) \right]} $$

$$ \text{donc } \lim_{n \to \infty} \frac{|I_n^s|}{|I_n|} = 0 $$

CONCLUSION. - Pour n assez grand le nombre $E^+(n)$ vérifie les inégalités

$$ (1-\epsilon) \sqrt{\frac{2}{\pi}} \frac{2^n}{n\sqrt{n}} < E^+(n) < (\sqrt{2} \log_2 n) \sqrt{\frac{2}{\pi}} \frac{2^n}{n\sqrt{n}} \left[ 1 + O\left( \frac{1}{\log_2 n} \right) \right] $$
1. Forme inférieure pour $n \ge 3$

Pareille de (11), (12), (13), (14), il est shown

$$ \left[ \left( \frac{1}{2} \right)^{\frac{1}{2}} \right]^{\frac{1}{2}} = \frac{1}{\sqrt{2}} $$

Nous montrons que la suite $\{a_n\}$ est stationnaire et que la suite $\{b_n\}$ de $a_n$ pouvant être résolue par un procédé linéaire et local (en module)

Considérant l'équation (14) en module, on obtient

$$ \lim_{n \to \infty} \left[ \left( \frac{1}{\sqrt{n}} \right)^{\frac{1}{2}} \right]^{\frac{1}{2}} = \frac{1}{\sqrt{2}} \quad (15) $$

Nous allons maintenant démontrer

trifacile à démontrer que $\lim_{n \to \infty} \left( \frac{1}{\sqrt{n}} \right)^{\frac{1}{2}} = \frac{1}{\sqrt{2}}$

d'après le lemme 1.1.1.2. Donc, $\lim_{n \to \infty} \left( \frac{1}{\sqrt{n}} \right)^{\frac{1}{2}} = 0$. Donc, en appliquant le lemme 1.1.1.2 à $\sqrt{2}$, nous obtenons

$$ E(\sqrt{2}) = \sqrt{\frac{2}{\sqrt{2}}} = \sqrt{\frac{2}{\sqrt{1-\sqrt{2}}}} = \sqrt{\frac{2}{\sqrt{2-\sqrt{4}}}} = \sqrt{\frac{2}{\sqrt{2-1}}} = 1 $$

## DÉMONSTRATION -

1. En chapter 1, nous avons montré

$$ (14) \qquad (15) $$

Utilisant les équations (14), on obtient

$$ c_n = \sqrt{\frac{2}{n}} \quad (n=1, 2, \dots) $$

(16)

2. Il est évident du lemme 1.1.1.2 que

$$ (17) \qquad (18) $$

$$ \text{Donnons } x = \sqrt{\frac{2}{n\sqrt{2}}} \quad (19) $$

(19)

De (19) démontrer que

$$ \lim_{n \to \infty} \left[ \left( \frac{1}{\sqrt{n}} \right)^{\frac{1}{2}} \right]^{\frac{1}{2}} = \frac{1}{\sqrt{2}} $$
# 6. Schémas de contacts de type série-parallèle

## Introduction

Désignons par $E_{SP}^f$ (respectivement $E_{SPF}^f$) le nombre minimal de contacts suffisant pour construire un schéma bipolaire de type série-parallèle (respect. de type série-parallèle et fermant) d'une fonction booléenne $f$ (respect. d'une fonction booléenne croissante $f^*$).

Posons

$$E_{SP}(n) = \max_{f \in \mathcal{F}_n} E_{SP}^f$$

$$E_{SPF}^+(n) = \max_{f \in I_n} E_{SP}^f$$

$$E_{SPF}^+(n) = \max_{f \in I_n} E_{SPF}^f$$

Soit $I_n^{s,SP}$ l'ensemble des fonctions croissantes de n variables, pouvant être réalisées par un schéma bipolaire de type série-parallèle ayant s contacts (ou moins).

On peut montrer (théorème 2) que quel que soit $\epsilon > 0$ pour

$$s = \sqrt{\frac{2}{\pi}} \frac{2^n}{\sqrt{n} \mathrm{Log}_2 n} (1-\epsilon) \quad \lim_{n \to \infty} \frac{|I_{n,s,SP}^s|}{|I_n|} = 0$$

En d'autres termes, la plupart des fonctions de $I_n$ exigent pour leur réalisation par un schéma série-parallèle plus de $\sqrt{\frac{2}{\pi}} \frac{2^n}{\sqrt{n} \mathrm{Log}_2 n} (1-\epsilon)$ contacts et par suite

$$\sqrt{\frac{2}{\pi}} \frac{2^n}{\sqrt{n} \mathrm{Log}_2 n} (1-\epsilon) < E_{SP}^+(n).$$

D'un autre côté, Lupanov [29] a montré que toute fonction $f \in \mathcal{F}_n$ peut être réalisée par un schéma bipolaire de type série-

<footnote>* Une fonction croissante étant une somme de produits fondamentaux peut toujours être réalisée par un schéma fermant.</footnote>
parallèle ayant moins de $\frac{2^n}{\text{Log}_2 n} \left[ 1 + 0 \left( \frac{\text{Log}_2 \text{Log}_2 n}{\text{Log}_2 n} \right) \right]$ contacts*. Mais sa méthode de construction ne conduit pas à de meilleurs résultats lorsqu'elle est appliquée à une fonction croissante.

L'objet du présent chapitre est d'exposer une méthode permettant de réaliser toute fonction croissante $f \in I_n$ par un schéma de type série-parallèle et fermant ayant moins de

$$ (\text{Log}_2 n) \sqrt{\frac{2}{\pi}} \frac{2^{n-2}}{\sqrt{n}} \left[ 1 + 0 \left( \frac{1}{\text{Log}_2 n} \right) \right] \text{ contacts.} $$

Ceci établit que pour $n$ assez grand

$$ \frac{1}{\text{Log}_2 n} \sqrt{\frac{2}{\pi}} \frac{2^n}{\sqrt{n}} (1-\epsilon) < E_{\text{SP}}^{+}(n) \ll E_{\text{SPP}}^{+}(n) < \frac{\text{Log}_2 n}{4} \sqrt{\frac{2}{\pi}} \frac{2^n}{\sqrt{n}} \left[ 1 + 0 \left( \frac{1}{\text{Log}_2 n} \right) \right] $$

Le rapport des bornes supérieures et inférieures de $E_{\text{SP}}^{+}(n)$ et $E_{\text{SPP}}^{+}(n)$ est ainsi abaissé de $\sqrt{\frac{n\pi}{2}}$ à $\frac{(\text{Log}_2 n)^2}{4}$

# 1. Décomposition d'une fonction booléenne croissante

Soit une fonction booléenne $f \in I_n$. Considérons la première décomposition de $f$ obtenue au chapitre précédent (proposition 1). Nous la simplifions en posant $B^{n-k} = C_1$. Nous avons $f_i^* \text{ au lieu de } f_{i,1}^*$ et $B_{i,t}^{n-k} \text{ au lieu de } C_{i,1}^t$. Nous pouvons alors écrire

$$ f(x) = \sum_{i=1}^{p} \cdot \sum_{t \in f_i^*(B^{n-k})} \chi_{L_i^t(y)} \cdot \chi_{B_{i,t}^{n-k}(z)} $$

il en résulte la proposition suivante

PROPOSITION 1. — Toute fonction booléenne croissante $f \in I_n$ peut se décomposer selon l'expression

$$ f(x) = \sum_{i=1}^{p} \cdot \sum_{t \in f_i^*(B^{n-k})} \chi_{L_i^t(y)} \cdot \chi_{B_{i,t}^{n-k}(z)} \quad (1) $$

La démonstration est similaire à celle de la proposition 2 du chapitre précédent.

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

<footnote>* Ce résultat, joint à ceux obtenus antérieurement par Riordan et Shannon [35] établit que $E_{\text{SP}}(n) \sim \frac{2^n}{\text{Log}_2 n}$.</footnote>

<footnote>** En fait nous avons appris, après remise du manuscrit que Suboch (Problemy Kibernetiki, 17) a obtenu par une autre méthode de meilleurs résultats.</footnote>
## 2. Construction d'un schéma série-parallèle fermant - Borne supérieure pour $E_{SPF}^*(n)$

### 2.1. - Principe.

Les ensembles $L_i, 1 \le i \le p$ sont définis de la même façon qu'au chapitre précédent.

Posons

$$ \sum_{t \in f_i^*(B^{n-k})} \chi_{L_i^t(y)}^+ \cdot \chi_{B_{i,t}^{n-k}(z)}^+ = \phi_i(y, z) $$

Pour tout $i \in \{1, 2, \dots, p\}$ on construit un schéma série-parallèle fermant $H_i$ réalisant la fonction $\phi_i$. Les schémas $H_i, 1 \le i \le p$ sont ensuite connectés en parallèle conformément à la proposition 1.

### 2.2. PROPOSITION 2. - Pour tout $i \in \{1, 2, \dots, p\}$, un schéma $H_i$ peut être construit avec $2^d \text{kd} + (n-k) 2^{n-k-1}$ contacts.

DEMONSTRATION. - a) La justaposition de $|f_i^*(B^{n-k})|$ schémas bipolaires, de type série-parallèle et fermants réalisant toutes les fonctions $y \to \chi_{L_i^t(y)}^+$, $t \in f_i^*(B^{n-k})$, i fixé, peut être construite avec $2^d \text{kd}$ contacts ou moins (cf. proposition 4 du chapitre précédent).

Soit $H_i^1(1, |f_i^*(B^{n-k})|)$ le schéma obtenu en contractant en un pôle d'entrée unique I les pôles d'entrée de cette juxtaposition. $H_i^1$ est faiblement disjonctif.

b) Soit un élément $b \in B^{n-k}$. Le produit fondamental $z \to \Phi_b(z)$ peut être réalisé par un schéma bipolaire fermant formé de $|s(b)|$ contacts en série.

Par conséquent, la juxtaposition de $2^{n-k}$ schémas bipolaires fermants, formés chacun de contacts en série, et réalisant tous les produits fondamentaux $z \to \Phi_b(z)$, $b \in B^{n-k}$, peut être construite avec $(n-k) 2^{n-k-1}$ contacts*.

Soit $H_i^2(|f_i^*(B^{n-k})|)$, 1) le schéma obtenu en contractant les pôles d'entrée de cette juxtaposition conformément à la partition $B^{n-k} = \sum_{t \in f_i^*(B^{n-k})} B_{i,t}^{n-k}$ et en contractant les pôles de sortie en un pôle unique $T$.

* En effet $$ \sum_{z \in B^{n-k}} |s(z)| = \sum_{i=1}^{n-k} i C_{n-k}^i = (n-k) 2^{n-k-1} $$
Pour tout $t \in t_1^*(B^{n-k})$, le schéma $H_1^2$ réalise la fonction $z \to \chi_{B_1,t}^{n-k}(z)$. D'autre part, il est faiblement disjonctif.

c) Soit $H_1 = H_1^1$. $H_1^2$ le schéma composé de $H_1^1$ et $H_1^2$ obtenu en contractant entre eux les pôles de sortie de $H_1^1$ et les pôles d'entrée de $H_1^2$ correspondant aux mêmes valeurs de $t$.

Le schéma $H_1$ réalise la fonction $\varphi_1$ avec $2^d \mathrm{kd} + (n-k)^{n-k-1}$ contacts ou moins, est fermant et de type série-parallèle.

### 2.3. THÉORÈME 1. -

$$E_{SPF}^{+}(n) < \sqrt{\frac{2}{\pi}} \frac{2^{n-2}}{\sqrt{n}} (\mathrm{Log}_2 n) \left[ 1 + O\left(\frac{1}{\mathrm{Log}_2 n}\right) \right]$$

DEMONSTRATION. – Soit une fonction croissante quelconque $f \in I_n$. On peut construire un schéma fermant, série parallèle et réalisant $f$ par la méthode exposée en 2.1.

De la proposition 2, il résulte alors que le nombre minimal $E_{SPF}^f$ de contacts suffisant pour effectuer cette construction vérifie l'inégalité

$$E_{SPF}^f < p [2^d \mathrm{kd} + (n-k) 2^{n-k-1}]$$

Mais on sait (inégalité 8 du chapitre précédent) que

$$p < \frac{C_k^{\left[\frac{k}{2}\right]} \log_2 \left( \frac{2^k}{\left[\frac{k}{2}\right]} + 1 \right)}{d - \log_2(k+2)}$$

Posons

$$k = [n - \sqrt{n} - 3 \log_2 n]$$

$$d = [\sqrt{n}]$$

Alors

$$2^d \mathrm{kd} + (n-k) 2^{n-k-1} = 2^{n-k-1} \sqrt{n} \left[ 1 + O\left( \frac{\log_2 n}{\sqrt{n}} \right) \right]$$

et

$$p < \frac{1}{2} \sqrt{\frac{2}{\pi}} \frac{2^k}{n} (\mathrm{Log}_2 n) \left[ 1 + O\left( \frac{1}{\mathrm{Log}_2 n} \right) \right]$$

Le théorème s'en déduit.
### 3. Borne inférieure pour $E_{sp}^*(n)$

Nous reprenons les notations introduites au début de ce chapitre. De plus, nous désignons par $\mathfrak{F}_{n,sp}^s$ l'ensemble des fonctions de $\mathfrak{F}_n$ pouvant être réalisées par un schéma bipolaire de type série-parrallèle contenant s contacts ou moins.

Nous donnons sans démonstration le lemme suivant dû à Riordan et Shannon [35]

LEMME 1. - $|\mathfrak{F}_{n,sp}^s| < (8n)^s$

Nous allons maintenant démontrer

$$ \text{THÉORÈME 2. - Quel que soit } \varepsilon > 0 \text{ si } s = \sqrt{\frac{2}{\pi}} \frac{2^n}{\sqrt{n} \ Log_2 n} (1-\varepsilon) \\ \text{alors} $$

$$ \lim_{n \to +\infty} \frac{|I_{n,sp}^s|}{|I_n|} = 0 $$

$$ \text{Par conséquent, pour n assez grand } E_{sp}^*(n) > \sqrt{\frac{2}{\pi}} \frac{2^n}{\sqrt{n} \ Log_2 n} (1-\varepsilon) $$

DÉMONSTRATION. -

a) Au chapitre précédent, nous avons montré que

$$ |I_n| > 2 \sqrt{\frac{2}{\pi}} \frac{2^n}{\sqrt{n}} [1 - o(1/n)] \quad (2) $$

b) D'après le lemme 1

$$ |I_{n,sp}^s| \le |\mathfrak{F}_{n,sp}^s| < (8n)^s $$

Posons

$$ s = \sqrt{\frac{2}{\pi}} \frac{2^n}{\sqrt{n} \ Log_2 n} (1-\varepsilon) $$

on obtient

$$ \mathrm{Log}_2 (|I_{n,sp}^s|) < \sqrt{\frac{2}{\pi}} \frac{2^n(1-\varepsilon)}{\sqrt{n}} \left[ 1 + O\left( \frac{1}{\mathrm{Log}_2 n} \right) \right] \quad (3) $$

De (2) et (3) il suit que

$$ \frac{|I_{n,sp}^s|}{|I_n|} < 2 \sqrt{\frac{2}{\pi}} \frac{2^n}{\sqrt{n}} [-\varepsilon + O(\frac{1}{\mathrm{Log}_2 n})] $$
donc

$$ \lim_{n \to +\infty} \frac{|I_{n,SP}^s|}{|I_n|} = 0 $$

## Conclusion

Pour $n$ assez grand, les nombres $E_{SP}^+(n)$ et $E_{SPF}^+(n)$ vérifient les inégalités

$$ \frac{1}{\text{Log}_2 n} \sqrt{\frac{2}{\pi}} \frac{2^n}{\sqrt{n}} (1-\varepsilon) < E_{SP}^+(n) \le E_{SPF}^+(n) < \frac{\text{Log}_2 n}{4} \sqrt{\frac{2}{\pi}} \frac{2^n}{\sqrt{n}} \left[ 1 + O\left(\frac{1}{\text{Log}_2 n}\right) \right] $$
# 7. Étude de la fonction $F_n^2$

## Introduction

Considérons la fonction booléenne de n variables $F_n^2$ définie par

$$F_n^2(x) = \begin{cases} 1 & \text{si } |s(x)| \ge 2 \\ 0 & \text{sinon} \end{cases} \quad (x = (x_1, x_2, \dots, x_n) \in \mathbb{B}^n)$$

Cette fonction est croissante. Or, il découle directement de la proposition 2 du chapitre 1 que toute fonction booléenne croissante peut être réalisée par un schéma bipolaire fermant.

Désignons alors par $E_n^2$ le nombre minimal de contacts suffisant pour construire un schéma bipolaire fermant de $F_n^2$.

Lupanov [28] a montré que le nombre $E_n^2$ vérifie les inégalités

$$C_1 \frac{n \log_e n}{\log_e \log_e n} \le E_n^2 \le C_2 n \log_2 n$$

où $C_1$ et $C_2$ sont des constantes.

Puis, Krichevskii [25] améliorant la première de ces inégalités a montré que

$$\frac{1}{4} n \log_2 n \le E_n^2$$

Nous établirons [16] tout d'abord que

$$n \log_2 n \le E_n^2 < \left( 1 + \frac{1 - \log_2 e + \log_2 \log_2 e}{\log_2 n} \right) n \log_2 n,$$

ce qui montre que $E_n^2$ est un infiniment grand équivalent à $n \log_2 n$.
De ce résultat, nous pourrons déduire [17]* la valeur exacte du nombre $E_n^2$, à savoir

$$ egin{cases} E_n^2 = n(m+2) - 2^{m+1} \\ \text{pour tout } n \text{ tel que } 2^m \le n < 2^{m+1} \quad (m \text{ entier, } \ge 0) \end{cases} $$

Puis, nous étendrons cette égalité à une classe particulière de schémas, les schémas série-parallèle non redondants (définis plus loin).

Enfin, nous démontrerons [18] une condition nécessaire et suffisante pour qu'un schéma fermant de la fonction $F_n^2$ soit minimal.

# 1. Réduction d'un schéma de la fonction $F_n^2$

Dans la suite de ce chapitre, le terme "schéma" signifiera "schéma bipolaire fermant". Nous utiliserons les notions introduites au chapitre 4.

## 1.1. - Expression explicite de $F_n^2(x)$

La fonction $F_n^2$ est définie par

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

ou ce qui revient au même

$$ F_n^2(x) = \sum_{k \le K \le K_n} x_k x_j $$

## 1.2. - Définitions

Considérons un schéma $H = (G, h)$ (avec $G = (S, A, \Gamma)$) réalisant la fonction $F_n^2$. Soit $I$ son pôle d'entrée et $T$ son pôle de sortie. Nous appellerons sommets intermédiaires les sommets de $G$ autres que $I$ et $T$ et contacts intermédiaires les contacts $[a, h(a)]$ dont l'arête $a$, a pour extrémités deux sommets intermédiaires.

<footnote>* Krichevskii [26] s'appuyant sur nos premiers résultats, a aussi déterminé cette valeur indépendamment. Nous donnerons ici notre propre démonstration.</footnote>
<figure><img src="image_7.png" /><figcaption>Fig. 1</figcaption></figure>

Exemple. — Le schéma représenté sur la figure 1 réalise la fonction

$$F_3^2(x_1, x_2, x_3) = x_1x_2 + x_1x_3 + x_2x_3$$

Les sommets a et b sont "intermédiaires" ainsi que les $x_3$-contact qui les relie.

A chaque sommet $s \in S$, nous associons deux nombres appelés niveaux (supérieur et inférieur).

Le niveau supérieur (resp. inférieur) de s est le nombre d'arêtes de la plus courte chaîne reliant s au pôle d'entrée I (resp. de sortie T).

Nous appellerons chaîne $x_1$-primaire (resp. $(x_1, x_j)$-secondaire) une chaîne dont tous les contacts ont pour argument la même variable $x_i$ (resp. l'une des deux variables $x_i$ ou $x_j$, chacune de ces variables apparaissant au moins une fois).

Nous appellerons chaîne polaire une chaîne reliant I et T.

Enfin, étant donné un schéma* H, nous noterons $N_H$ l'ensemble des couples $(i, j), i \neq j$, tels qu'il existe dans H une chaîne polaire et $(x_1, x_j)$-secondaire.

**1.3. PROPOSITION 1.** — Une condition nécessaire et suffisante pour qu'un schéma H réalise la fonction $F_n^2$ est que

$$- N_H = \{(i, j) | (i, j) \in \{1, 2, \dots, n\}^2 \text{ et } i \neq j\}$$

- Il existe aucune chaîne à la fois polaire et primaire (évident d'après 1.1).

*Conséquence.* — Si un schéma H réalise la fonction $F_n^2$ toute transformation qui ne diminue pas $N_H$ et ne crée aucune chaîne polaire primaire peut être effectuée sans altérer la fonction réalisée.

En particulier, un contact dont l'arête n'appartient à aucune chaîne polaire secondaire peut être supprimé. De même, il va de soi que si deux arêtes ont les mêmes extrémités et le même argument, l'une d'elles peut être supprimée. Nous supposerons toujours ces suppressions effectuées.

Nous allons considérer dans la suite plusieurs transformations de ce genre et qui de plus diminuent ou laissent inchangés le nombre de contacts d'un schéma.

<footnote>* Rappelons que dans ce chapitre le terme "schéma" signifie schéma bipolaire fermant.</footnote>
### 1.4. - Transformations des schémas de $F_n^2$

Soit un schéma $H = (G, h)$ réalisant $F_n^2$.

**1.4.1.** - Supposons qu'un $x_1$-contact relie un pôle (par exemple $I$) à un sommet intermédiaire quelconque $s$ (figure 2a) et qu'un deuxième $x_1$-contact relie $s$ à un autre sommet $s'$ (nécessairement distinct de $T$ sinon $I$ et $T$ seraient reliés par une chaîne $x_1$-primaire).

<figure><img src="image_8.png" /><figcaption>Fig. 2</figcaption></figure>

Soit $H$ le schéma obtenu (figure 2b) en connectant directement ce deuxième $x_1$-contact entre $I$ et $s'$. Cette transformation ne crée pas de chaîne polaire primaire et de plus $N_H = N_H'$. Par conséquent, $H$ réalise toujours $F_n^2$. De plus, les nombres de contacts de $H$ et $H'$ sont égaux.

Par la suite, nous supposerons que toutes les transformations de ce genre ont été effectuées. Ainsi, nous pourrons restreindre l'étude aux schémas réalisant $F_n^2$ et ayant la propriété suivante:

**PROPRIÉTÉ 1.** - Si un sommet $s$ est relié directement à $I$ (ou à $T$) par un $x_1$-contact, il n'est relié à aucun autre sommet par un $x_1$-contact.

**1.4.2.** - Considérons un sommet $s$ dont au moins l'un des deux niveaux, par exemple son niveau supérieur, dépasse ou est égal à 2. Nous allons montrer que la contraction de $s$ avec le pôle $T$ ne change pas la fonction $F_n^2$ réalisée.

En effet, considérons (figure 3a) une chaîne polaire $(x_1, x_j)$-secondaire passant par $s$. Désignons par $x_1^1, x_1^2, \dots, x_1^j, x_1^j, x_2^1, \dots, x_j^1$ les différents contacts de la chaîne en donnant des indices supérieurs croissant de $I$ vers $T$.
Comme nous supposons que le schéma vérifie la propriété 1, les deux premiers contacts de la chaîne sont

soit $x_i^1$ suivi de $x_j^1$ (cas de la figure 3a) ;

soit $x_j^1$ suivi de $x_i^1$.

Si l'on contracte s et T, il subsiste donc dans le schéma H' obtenu une chaîne polaire $(x_i, x_j)$-secondaire (figure 3b).

Comme d'autre part, toujours d'après la propriété 1, il n'existe aucune chaîne primaire reliant I et s, la contraction de s et T ne crée aucune chaîne polaire primaire. H' réalise donc encore $F_n^2$.

L'application systématique de ce procédé de réduction conduit à un schéma réalisant $F_n^2$ et vérifiant

**PROPRIÉTÉ 2.** – Tous les sommets intermédiaires ont leurs deux niveaux égaux à 1.

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

**1.4.3.** – Supposons qu'il existe dans H un cycle constitué par un ensemble de contacts ayant tous pour argument la même variable $x_i$ (figure 4a) (cycle passant uniquement par des sommets intermédiaires d'après la propriété 1). La suppression d'un contact quelconque du cycle (figure 4b) ne change pas la fonction $F_n^2$ réalisée par le schéma. On obtient ainsi un schéma de $F_n^2$ vérifiant

**PROPRIÉTÉ 3.** – Il n'existe aucun cycle de contacts intermédiaires ayant tous pour argument la même variable $x_i$.
<figure><img src="image_10.png" /><figcaption>Fig. 4</figcaption></figure>

1.4.4. - Nous appellerons *schémas réduits* les schémas ayant les propriétés 1, 2, 3. On peut toujours, sans augmenter le nombre des contacts, transformer un schéma quelconque de $F_n^2$ en un schéma réduit (réalisant encore $F_n^2$). L'étude du nombre $E_n^{2*}$ peut donc être faite en se limitant aux schémas réduits.

## 2. Recherche d'une borne inférieure pour $E_n^2$

Le multigraphe d'un schéma réduit quelconque de $F_n^2$ peut se représenter sur une sphère (figure 5) : les pôles I et T sont les extrémités d'un diamètre, les autres sommets a, b, c, ...d sont placés sur un grand cercle, sont adjacents à I et T d'une part, et reliés entre eux de façon quelconque d'autre part.

### 2.1. - Définitions

Nous considérons un schéma réduit H réalisant la fonction $F_n^2$.

Un faisceau est l'ensemble des contacts incidents aux pôles I ou T et à un même sommet intermédiaire.

Un demi-faisceau supérieur (resp. inférieur) est l'ensemble des contacts d'un faisceau, incidents au pôle d'entrée I (resp. de sortie T) et au sommet intermédiaire du faisceau.

<footnote>* Rappelons que c'est le nombre minimal de contacts suffisant pour construire un schéma de $F_n^2$.</footnote>
<figure><img src="image_11.png" /><figcaption>Fig. 5</figcaption></figure>

Précisons qu'un faisceau (ou un demi-faisceau) ne contient aucun contact intermédiaire.

<figure><img src="image_12.png" /><figcaption>T
Fig. 6</figcaption></figure>

*Exemple.* — Le schéma de la figure 6 réalise $F_3^2(x_1, x_2, x_3)$.

Il comprend deux faisceaux

$$K_1 = \{x_1, x_2, x_3\} \text{ en a}$$

et

$$K_2 = \{x_2, x_3\} \text{ en b}$$

Il comprend deux demi-faisceaux supérieurs

$$A_1 = \{x_1\}, A_2 = \{x_2\}$$

et deux demi-faisceaux inférieurs

$$B_1 = \{x'_2, x_3\} \text{ et } B_2 = \{x'_3\}.$$

Supposons que H contienne p faisceaux $K_1, K_2, \dots, K_f, \dots, K_p$ le faisceau $K_1$, ($1 \le i \le p$), étant composé des deux demi-faisceaux $A_1$ et $B_1$
Nous appellerons famille complète de demi-faisceaux une famille $(Z_1)_{1\le i\le p}$, où $Z_1$ est soit le demi-faisceau supérieur $A_1$, soit le demi-faisceau inférieur $B_1$.

Si un schéma contient p faisceaux, il existe donc $2^p$ familles complètes de demi-faisceaux.

*Exemple.* – Pour le schéma de la figure 6, les familles complètes de demi-faisceaux sont

$$[\{x_1\}, \{x_2\}], [\{x_1\}, \{x_3\}], [\{x_2\}, x_3], \{x_2\}], [\{x_2\}, x_3], \{x_3\}]$$

Nous appellerons coupe polaire du schéma $H = (G, h)$ une coupe $L$ telle que les pôles $I$ et $T$ appartiennent à des composantes connexes différentes du multigraphe partiel $G^{A-L}$.

## 2.2. – Étude des coupes polaires

Considérons un schéma réduit $H$ réalisant $F_n^2$ et contenant $p$ faisceaux. Soit $(Z_1)_{1\le i\le p}$ une famille complète de demi-faisceaux.

Désignons par $A_{1_1}, A_{1_2}, \dots A_{1_\lambda} \dots A_{1_1}$ (respectivement $B_{j_1}, B_{j_2}, \dots B_{j_\mu}, \dots B_{j_m}$) les demi-faisceaux supérieurs (resp. inférieurs) de cette famille et par $S_1 = \{a_{1_1}, a_{1_2}, \dots a_{1_\lambda} \dots a_{1_1}\}$ (resp. $S_2 = \{b_{j_1}, b_{j_2}, \dots b_{j_\mu}, \dots b_{j_m}\}$) l'ensemble des sommets intermédiaires de ces demi-faisceaux.

Nous pouvons énoncer

**PROPOSITION 2.** – Toute coupe polaire minimale de $H$ est constituée de la réunion de l'ensemble des contacts d'une famille complète $(Z_1)_{1\le i\le p}$ de demi-faisceaux et de l'ensemble des contacts intermédiaires ayant une extrémité dans $S_1$ et l'autre dans $S_2$.

**DÉMONSTRATION.** – D'après la proposition 1 du chapitre 4, toute coupe polaire minimale détermine une partition de l'ensemble $S$ des sommets de $H$ en deux sous-ensembles $S_1$ et $S_2$ avec $I \in S_1$ et $T \in S_2$ et elle contient les arêtes ayant un couple d'extrémités $(s, s')$ avec $s \in S_1$ et $s' \in S_2$. Cet ensemble d'arêtes peut être partagé en trois sous-ensembles disjoints (certains pouvant être vides)

$$1/ \text{ les arêtes } (s, s') \text{ avec } s = I \text{ et } s' \in S_2 - T$$

$$2/ \text{ les arêtes } (s, s') \text{ avec } s = T \text{ et } s' \in S_1 - I.$$

Les éléments de ces deux sous-ensembles sont les arêtes d'une famille complète de demi-faisceaux.
3/ les arêtes (s, s') avec s ∈ S₁ - I et s' ∈ S₂ - T.

**PROPOSITION 3.** – *Il existe 2<sup>p</sup> coupes polaires minimales distinctes d'un schéma réduit de F<sub>n</sub><sup>2</sup> contenant p faisceaux; réciproquement s'il existe k coupes polaires minimales distinctes d'un schéma réduit H, ce schéma contient Log<sub>2</sub>k faisceaux.*

En effet, le nombre de partitions de S en deux sous-ensembles S₁ et S₂ avec I ∈ S₁ et T ∈ S₂ est 2<sup>p</sup>.

Les coupes polaires minimales correspondant à deux partitions sont distinctes (d'après la proposition précédente).

**PROPOSITION 4.** – *Dans un schéma de F<sub>n</sub><sup>2</sup> le nombre d'arguments distincts des contacts d'une coupe polaire est égal ou supérieur à n-1.*

En effet, soient x₁ et xⱼ deux variables de contact et considérons une coupe polaire quelconque. Le schéma contient au moins une chaîne polaire (x₁, xⱼ)-secondaire et par suite, il existe au moins une arête de la coupe ayant pour argument l'une des deux variables x₁ ou xⱼ. Ceci étant vrai quels que soient x₁ et xⱼ, la proposition s' en déduit.

*Conséquence.* – Considérons deux coupes polaires minimales C¹ et C² d'un schéma réduit de F<sub>n</sub><sup>2</sup>. Si C¹ ne contient pas de x₁-contact et si C² ne contient pas de xⱼ-contact (x₁ ≠ xⱼ), les coupes C¹ et C² sont distinctes.

### 2.3. - Détermination du nombre de coupes polaires minimales sans x₁-contacts

**PROPOSITION 5.** – *Dans un multigraphe sans cycles G = (S, A, Γ) le nombre c de composantes connexes est c = |S| - |A|.*

Ceci se montre immédiatement par récurrence sur le nombre des arêtes.

Soit un schéma réduit H = (G, h) et soit αᵢ l'ensemble des arêtes intermédiaires ayant pour argument la variable xᵢ. Notons G*αᵢ le multigraphe obtenu à partir du multigraphe partiel Gᵃᵢ = (S, αᵢ, Γαᵢ) en supprimant les pôles I et T ainsi que les sommets intermédiaires des faisceaux contenant des xᵢ-contacts.

*Exemple.* – Pour le schéma représenté sur la figure 7a, le multigraphe G*αᵢ est celui de la figure 7b.
<figure><img src="image_13.png" /><figcaption>Fig. 7</figcaption></figure>

**PROPOSITION 6.** – Soit un schéma réduit $H = (G, h)$ réalisant la fonction $F_h^n$ et soit $\mathbb{C}$ une coupe polaire minimale ne contenant pas de $x_1$-contacts. Les demi-faisceaux de $\mathbb{C}$ associés aux sommets d'une même composante connexe de $G^{*a_1}$ sont ou bien tous supérieurs, ou bien tous inférieurs.

**DEMONSTRATION.** – Supposons par exemple que dans la coupe $\mathbb{C}$ le demi-faisceau associé à un sommet intermédiaire $s$ soit supérieur. L'ensemble des sommets adjacents à $s$ dans $G^{*a_1}$ doivent également avoir des demi-faisceaux associés supérieurs. En effet, si ce n'était pas le cas, la coupe $\mathbb{C}$ comprendrait (proposition 2) des $x_1$-contacts intermédiaires. Le même raisonnement peut être répété de proche en proche de sorte que tous les sommets appartenant à la même composante connexe que $s$ dans $G^{*a_1}$ ont des demi-faisceaux associés supérieurs.

**LEMME 1.** – Soit un schéma réduit $H$ réalisant la fonction $F_h^n$, soit $a_1$ le nombre de ses $x_1$-contacts intermédiaires, et soit $p_1$ le nombre de faisceaux de $H$ ne contenant pas de $x_1$-contacts. Le nombre de coupes polaires minimales de $H$ ne contenant pas de $x_1$-contacts est $2^{p_1-a_1}$.

**DÉMONSTRATION.** – D'après la propriété 3 des schémas réduits $G^{*a_1}$ n'a pas de cycles et par conséquent, d'après la proposition 5 il a $p_1 - a_1$ composantes connexes. Chaque coupe polaire minimale sans $x_1$-contact est définie par le caractère supérieur ou inférieur des demi-faisceaux associés aux sommets de chaque composante connexe de $G^{*a_1}$ (proposition 6). Il y a donc $2^{p_1-a_1}$ coupes polaires minimales sans $x_1$-contact.
2.4. THÉORÈME 1 (borne inférieure pour $E_n^2$). — Le nombre minimal $E_n^2$ de contacts suffisant pour construire un schéma bipolaire fermant de la fonction $F_n^2$ vérifie l'inégalité

$$E_n^2 > n \log_2 n$$

DÉMONSTRATION. — Soit un schéma réduit minimal H réalisant $F_n^2$ et désignons par

p le nombre de ses faisceaux

$p_1$ le nombre de faisceaux ne contenant pas de $x_1$-contacts

$a_1$ le nombre de $x_1$-contacts intermédiaires.

Le nombre de contacts $E_n^2$ du schéma est alors

$$E_n^2 = \underbrace{np - (p_1 + p_2 + \dots + p_n)}_{\text{contacts des faisceaux}} + \underbrace{(a_1 + a_2 + \dots + a_n)}_{\text{contacts intermédiaires}} \quad (1)$$

D'après le lemme 1 et la conséquence de la proposition 4, le schéma contient au moins $\sum_{i=1}^{n} 2^{p_i-a_i}$ coupes polaires minimales distinctes et il découle alors de la proposition 3 que le nombre p de faisceaux vérifie l'inégalité

$$p \ge \log_2 \left( \sum_{i=1}^{n} 2^{p_i-a_i} \right)$$

et par suite d'après (1)

$$E_n^2 \ge n \log_2 \left( \sum_{i=1}^{n} 2^{p_i-a_i} \right) - \sum_{i=1}^{n} (p_i - a_i) \quad (2)$$

La moyenne arithmétique des nombres $2^{p_i-a_i}$, $i = (1, 2, \dots, n)$ est supérieure à leur moyenne géométrique

$$\frac{1}{n} \sum_{i=1}^{n} 2^{p_i-a_i} \ge \left( 2^{\sum_{i=1}^{n} p_i-a_i} \right)^{\frac{1}{n}}$$

En prenant les logarithmes des deux membres, on obtient

$$E_n^2 \ge n \log_2 \left( \sum_{i=1}^{n} 2^{p_i-a_i} \right) - \sum_{i=1}^{n} (p_i-a_i) \ge n \log_2 n$$
Remarque. – L'égalité $E_n^2 = n \log_2 n$ a lieu lorsque

$$p_1 - a_1 = p_2 - a_2 = \dots = p_n - a_n = \lambda.$$

Chaque variable $x_i$ est alors argument de $p - \lambda$ contacts et l'on a $E_n^2 = n(p - \lambda) = n \log_2 n$. Ceci suppose que $n$ soit une puissance entière de 2.

### 3. Recherche d'une borne supérieure pour $E_n^2$

#### 3.1. - Inégalités préliminaires.

PROPOSITION 7. – Quel que soit $k \in \{1, 2, \dots, n-1\}$, les nombres $E_n^2, E_k^2, E_{n-k}^2$ vérifient l'inégalité

$$E_n^2 \le n + E_k^2 + E_{n-k}^2$$

(On pose $E_1^2 = 0$)

DÉMONSTRATION. – Considérons la juxtaposition $H = \{H_1; H_2; H_3\}$ de trois schémas $H_1, H_2, H_3$ tels que

$H_1$ réalise la fonction

$$f(x_1, x_2, \dots, x_n) = (x_1 + x_2 + \dots + x_k) (x_{k+1} + x_{k+2} + \dots + x_n)$$

au moyen de $n$ contacts.

$H_2$ est un schéma minimal réalisant la fonction $F_k^2(x_1, x_2, \dots, x_k)$ au moyen de $E_k^2$ contacts.

$H_3$ est un schéma minimal réalisant la fonction $F_{n-k}^2(x_{k+1}, x_{k+2}, \dots, x_n)$ au moyen de $E_{n-k}^2$ contacts.

Si l'on contracte en un même sommet $I$ les pôles d'entrée de $H$ et en un même sommet $T$ ses pôles de sortie (figure 8), le schéma obtenu réalise la fonction $F_n^2(x_1, x_2, \dots, x_n)$ avec $n + E_k^2 + E_{n-k}^2$ contacts.

<figure><img src="image_14.png" /><figcaption>Fig. 8</figcaption></figure>
**PROPOSITION 8.** - Pour tout $n$ tel que $2^m \le n \le 2^{m+1}$ (m entier)
le nombre $E_n^2$ obéit à l'inégalité

$$E_n^2 \le n(m+2) - 2^{m+1}$$

Nous allons démontrer cette proposition par récurrence sur $m$. Pour $n = 2, 3, 4$ ($m = 1$) elle se montre facilement. Supposons qu'elle soit vraie pour $2^{m-1} \le n \le 2^m$ et montrons qu'elle l'est en-core pour $2^m \le n \le 2^{m+1}$. $n$ vérifiant ces dernières inégalités, on peut trouver $k$ tel que

$$2^{m-1} \le k \le 2^m \quad \text{et} \quad 2^{m-1} \le n-k \le 2^m$$

Par hypothèse de récurrence et d'après la proposition 7

$$E_n^2 \le n + E_k^2 + E_{n-k}^2 \le n + k(m+1) - 2^m + (n-k)(m+1) - 2^m$$

soit

$$E_n^2 \le n(m+2) - 2^{m+1}$$

**3.2.** **THÉORÈME 2** (Borne supérieure pour $E_n^2$). - Le nombre $E_n^2$ obéit à l'inégalité

$$E_n^2 < \left( 1 + \frac{1 - \text{Log}_2 e + \text{Log}_2 \text{Log}_2 e}{\text{Log}_2 n} \right) n \text{Log}_2 n$$

$$(1 - \text{Log}_2 e + \text{Log}_2 \text{Log}_2 e) \approx 0,0861).$$

**DEMONSTRATION.** - Considérons la fonction numérique définie par

$$f(x) = x(m+2) - 2^{m+1} - x \text{Log}_2 x - x(1 - \text{Log}_2 e + \text{Log}_2 \text{Log}_2 e)$$

a) Montrons que pour $2^m \le x \le 2^{m+1}$ on a toujours $f(x) \le 0$.

En effet

$$f(2^m) = -2^m(1 - \text{Log}_2 e + \text{Log}_2 \text{Log}_2 e) < 0$$

$$f(2^{m+1}) = -2^{m+1}(1 - \text{Log}_2 e + \text{Log}_2 \text{Log}_2 e) < 0$$

La dérivée de $f(x)$ est

$$f'(x) = m + 2 - \text{Log}_2 x - \text{Log}_2 e - (1 - \text{Log}_2 e + \text{Log}_2 \text{Log}_2 e).$$

Elle ne s'annule que pour la valeur

$$x^* = \frac{2^{m+1}}{2^{\text{Log}_2 \text{Log}_2 e}} = \frac{2^{m+1}}{\text{Log}_2 e}$$
Il est facile de vérifier que

$$f\left(\frac{2^{m+1}}{\mathrm{Log}_2 e}\right) = 0 \quad \text{donc} \quad f(x) < 0 \quad \text{si} \quad 2^m \le x \le 2^{m+1}$$

b) Pour $2^m < x < 2^{m+1}$ on a donc

$$x(m+2) - 2^{m+1} \le \left( 1 - \frac{1 - \mathrm{Log}_2 e + \mathrm{Log}_2 \mathrm{Log}_2 e}{\mathrm{Log}_2 x} \right) \times \mathrm{Log}_2 x.$$

D'après la proposition 8, on peut réaliser $F_n^2$ au moyen de $n(m+1) - 2^{m+1}$ contacts si $2^m < n < 2^{m+1}$. En observant que $\frac{2^{m+1}}{\mathrm{Log}_2 e}$ n'est pas entier, on obtient l'inégalité stricte donnée dans l'énoncé du théorème.

COROLLAIRE DES THÉORÈMES 1 ET 2. – $E_n^2$ est un infiniment grand équivalent à $n \log_2 n$.

### 4. Recherche de la valeur exacte $E_n^2$

Nous allons montrer que la borne supérieure obtenue plus haut dans la proposition 8 est en réalité égale au nombre $E_n^2$.

THÉORÈME 3 [17]. – Pour tout $n$ tel que $2^m \le n \le 2^{m+1}$, (m entier) le nombre minimal $E_n^2$ de contacts suffisant pour réaliser un schéma bipolaire fermant de la fonction $F_n^2$ est

$$E_n^2 = n(m+2) - 2^{m+1}.$$

DÉMONSTRATION. – $E_n^2 \le n(m+2) - 2^{m+1}$ (proposition 8)

Nous allons montrer en raisonnant par l'absurde que

$$E_n^2 \ge n(m+2) - 2^{m+1}$$

Supposons qu'il existe un schéma de $F_n^2$ ayant un nombre $K_n^2$ de contacts tel que

$$K_n^2 \le n(m+2) - 2^{m+1} - 1.$$
Au moins une des variables, $x_1$ par exemple, est argument d'un nombre $b_1$ de contacts avec

$$b_1 \le \frac{K_n^2}{n} = m + 2 - \frac{2^{m+1} + 1}{n}$$

soit $b_1 \le m$ puisque $b_1$ est entier.

On peut alors réaliser un schéma de la fonction $F_{n+1}^2(x_1, x_2, \dots, x_{n+1})$ de la façon suivante

1/ En parallèle avec chaque $x_1$-contact du schéma initial, on introduit un $x_{n+1}$-contact.

Alors pour tout couple $(x_{n+1}, x_1)$ avec $i \in \{2, 3, \dots, n\}$ il existe une chaîne polaire $(x_i, x_{n+1})$-secondaire.

2/ On introduit dans le schéma obtenu un nouveau faisceau en connectant en série un $x_1$-contact avec un $x_{n+1}$-contact. La fonction $F_{n+1}^2(x_1, x_2, \dots, x_n, x_{n+1}) = \sum_{1 \le i < j \le n} x_i x_j + \sum_{1 \le i \le n \le j \le n+1} x_i x_{n+1}$ est donc réalisée et ceci avec un nombre de contacts $K_{n+1}^2 \le (m+2) + K_n^2$ soit

$$K_{n+1}^2 \le (n+1)(m+1) - 2^{m+1} - 1.$$

En effectuant le même raisonnement et la même construction $2^{m+1}-n$ fois, on obtient finalement un schéma de $F_{2^{m+1}}^2(x_1, x_2, \dots, x_{2^{m+1}})$ construit avec un nombre de contacts $K_{2^{m+1}}^2 \le 2^{m+1}(m+2) - 2^{m+1} - 1$ soit

$$K_{2^{m+1}}^2 \le (m+1) 2^{m+1} - 1.$$

Or ceci est impossible d'après le théorème 1.

## 5. Extension des résultats précédents

Nous dirons qu'un schéma bipolaire H réalisant une fonction croissante $f \in I_n$ est non redondant s'il existe une correspondance biunivoque entre l'ensemble fondamental $M_f$ et l'ensemble des chaînes polaires élémentaires de H qui associe à tout $a \in M_f$ une chaîne $c_a$ de transmission $\tau_c = \Phi_a$. $(\Phi_a$ produit fondamental associé à l'élément a). En particulier, un schéma non redondant réalisant la fonction $F_n^2$ a $C_n^2$ chaines polaires élémentaires dont les transmissions sont $x_i^* x_j^*$, $1 \le i < j \le n$.
On peut alors énoncer

THÉORÈME 4. — Le nombre minimal $G_n^2$ de contacts suffisant pour construire un schéma bipolaire, fermant, de type série-parallèle, et non redondant de la fonction $F_n^2$ est égal à $E_n^2$.

Il est évident que $G_n^2 \ge E_n^2$.

Montrons l'inégalité opposée.

Les démonstrations des propositions 7 et 8 se répètent iden-
tiquement en ajoutant aux hypothèses de récurrence que les schémas
$H_2$ et $H_3$ sont de type série-parallèle et non redondants. Donc

$$
G_n^2 \le n(m+2) - 2^{m+1} = E_n^2.
$$

6. Caractérisation des schémas minimaux de $F_n^2$

Nous avons démontré (proposition 4) que toute coupe polaire d'un schéma de $F_n^2$ contient des contacts d'au moins $n-1$ variables.

Nous appellerons *coupe complète* une coupe polaire contenant des contacts de toutes les variables. Nous montrerons qu'un schéma réduit de $F_n^2$ qui contient des coupes polaires minimales complètes (en abrégé c.p.m.c.) ne saurait être minimal et nous approfondirons la relation existant entre le nombre de contacts d'un schéma et le nombre de ses c.p.m.c.

6.1. - Résultats préliminaires.

6.1.1. PROPOSITION 9. — Pour n tel que $2^m < n \le 2^{m+1}$, tout schéma réduit de $F_n^2$ contient au moins $m+1$ faisceaux.

En effet, pour tout $i \in \{1, 2, \dots, n\}$ il existe au moins une coupe polaire minimale ne contenant pas de $x_i$-contacts (Lemme 1). Tout schéma réduit de $F_n^2$ contient donc au moins $n$ coupes polaires minimales distinctes. (Conséquence de la proposition 4). La proposition découle alors directement de la proposition 3.

PROPOSITION 10. — *Supposons* $2^m < n \le 2^{m+1}$

Tout schéma réduit de $F_n^2$ contenant $m+1$ faisceaux (minimum possible) et contenant une c.p.m.c. n'est pas minimal.
DEMONSTRATION. – Supposons qu'un schéma réduit minimal de $F_n^2$ soit construit avec $m+1$ faisceaux et qu'il contienne une c. p. m. c. Etant minimal, il contient $E_n^2 = n(m+2) - 2^{m+1}$ contacts (Théorème 3).

Montrons qu'il suffit d'ajouter un $x_{n+1}$-contact à chacun des $m+1$ demi-faisceaux non contenus dans la coupe complète pour obtenir un schéma réalisant $F_{n+1}^2(x_1 x_2 \dots x_{n+1})$. Soit $i \in \{1, 2, \dots, n\}$. S'il existe un $x_1$-contact dans l'un des demi-faisceaux de la c. p. m. c. alors il y aura une chaîne polaire et $(x_1, x_{n+1})$-secondaire dans le schéma obtenu. Supposons au contraire que les $x_i$-contacts de la c. p. m. c. soient tous intermédiaires ; soient $s$ et $s'$ les extrémités de l'un quelconque de ces $x_i$-contacts. Les demi-faisceaux de la coupe associés à $s$ et $s'$ sont, l'un supérieur et l'autre inférieur (proposition 2) et par suite il existera encore une chaîne $(x_1, x_{n+1})$-secondaire dans le schéma obtenu.

On aurait alors construit un schéma de $F_{n+1}^2(x_1 x_2 \dots x_{n+1})$ avec $n(m+2) - 2^{m+1} + m + 1 = (n+1)(m+2) - 2^{m+1} - 1$ contacts ce qui est impossible d'après le théorème 3.

Cette proposition montre dans un cas particulier simple que l'existence d'une c. p. m. c. est incompatible avec la minimalité d'un schéma.

**6.1.2.** - Soit un schéma réduit H réalisant la fonction $F_n^2$ et désignons par $b_i$, $i = (1, 2, \dots, n)$ le nombre de ses $x_i$-contacts.

Posons également

$$b = \min_i b_i$$

$$B = \max_i b_i$$

Un schéma pour lequel $B - b < 1$ sera appelé égalitaire.

Un schéma pour lequel $B - b = 2$ sera appelé semi-égalitaire.

**PROPOSITION 11.** – *Un schéma réduit de $F_n^2$ qui n'est ni égalitaire, ni semi-égalitaire n'est pas minimal.*

Supposons qu'un schéma réduit de $F_n^2$ soit construit avec $\sum_{i=1}^n b_i = \beta$ contacts et d'autre part que les nombres $b_1$ et $b_2$ (par exemple) vérifient $b_2 \ge b_1 + 3$.

Le nombre de contacts du schéma peut être diminué par les transformations suivantes

- Suppression des $x_2$-contacts.
- Introduction d'un $x_2$-contact en parallèle avec chaque $x_1$-contact.

- Introduction d'un nouveau faisceau composé d'un $x_1$-contact en série avec un $x_2$-contact.

La fonction $F_n^2$ se trouve alors réalisée au moyen de $\beta' = \beta - b_2 + b_1 + 2$ contacts et l'on a bien $\beta' \le \beta - 1$.

Cette proposition montre que la minimalité d'un schéma est en relation avec son caractère "égalitaire".

Le théorème et les corollaires que nous allons démontrer précisent l'importance relative des deux facteurs mis en évidence dans les propositions précédentes.

## 6.2. - Détermination du surplus d'un schéma

Nous supposons $2^m < n \le 2^{m+1}$. Le nombre minimal de contacts d'un schéma réduit de $F_n^2$ est $n(m+2) - 2^{m+1}$ (théorème 3).

Nous appellerons surplus d'un schéma réduit de $F_n^2$ ayant $\beta$ contacts, le nombre $\sigma = \beta - n(m+2) + 2^{m+1}$.

De plus, nous désignons par

- $p$ le nombre des faisceaux.

- $g$ le nombre des coupes polaires minimales complètes.

- $c_i$ le nombre de variables apparaissant comme argument de $i$ contacts.

THEOREME 5. - Le surplus $\sigma$ d'un schéma réduit réalisant la fonction $F_n^2$ est donné par l'égalité

$$2^{p-m-1}\sigma = g + \sum_{i=1}^{m-1} [2^{p-i} - 2^{p-m-1}(m-i+2)] c_i + \sum_{i=m+2}^{p} [2^{p-i} - 2^{p-m-1}(m-i+2)] c_i$$

DÉMONSTRATION. - De la définition des nombres $\sigma$ et $c_i$, il découle

$$\sum_{i=1}^{p} c_i = n$$

$$\sum_{i=1}^{p} i c_i = \beta = n(m+2) - 2^{m+1} + \sigma$$

Si une variable $x_j$ est argument de $i$ contacts, il y a $2^{p-i}$ coupes polaires minimales ne contenant pas de contacts de cette variable (ceci découle du Lemme 1 car $i = (p - p_j) + a_j$).
Les $2^p$ coupes polaires minimales du schéma se répartissent en coupes complètes et non complètes

$$2^p = g + \sum_{i=1}^{p} c_i 2^{p-i} \quad (3)$$

Les égalités (1) et (2) s'écrivent encore

$$c_m + c_{m+1} = n - \sum_{i=1}^{m-1} c_i - \sum_{i=m+2}^{p} c_i \quad (4)$$

$$mc_m + (m+1) c_{m+1} = n(m+2) - 2^{m+1} + \sigma - \sum_{i=1}^{m-1} i c_i - \sum_{i=m+2}^{p} ic_i \quad (5)$$

On en déduit

$$c_m = 2^{m+1} - n - \sigma - \sum_{i=1}^{m-1} (m-i+1) c_i - \sum_{i=m+2}^{p} (m-i+1) c_i \quad (6)$$

$$c_{m+1} = 2n - 2^{m+1} + \sigma + \sum_{i=1}^{m-1} (m-i) c_i + \sum_{i=m+2}^{p} (m-i) c_i$$

En remplaçant $c_m$ et $c_{m+1}$ par leurs valeurs dans (3), il vient

$$ \begin{aligned} 2^p &= g + \sum_{i=1}^{m-1} c_i 2^{p-i} + \sum_{i=m+2}^{p} c_i 2^{p-i} + 2^{p-m-1} [2 c_m + c_{m+1}] \\ &= g + \sum_{i=1}^{m-1} c_i 2^{p-i} + \sum_{i=m+2}^{p} c_i 2^{p-i} + 2^{p-m-1} \left[ 2^{m+1} - \sigma - \sum_{i=1}^{m-1} (m-i+2) c_i \right. \\ & \qquad \left. - \sum_{i=m+2}^{p} (m-i+2) c_i \right] \end{aligned} $$

le théorème s'en déduit

COROLLAIRE 1. - Pour qu'un schéma réduit réalisant la fonction $F_n^2$ soit minimal, il faut et il suffit que les deux conditions suivantes soient remplies

1/ Le schéma ne contient pas de coupe polaire minimale complète.

2/ Le schéma est égalitaire et seuls les nombres $c_m$ et $c_{m+1}$ ne sont pas nuls.

Ce corollaire s'obtient immédiatement à partir du théorème précédent si l'on observe que pour $i = (1, 2, ..., m-1)$ on a toujours

$$2^{p-i} - 2^{p-m-1} (m-i+2) > 0.$$
COROLLAIRE 2. - Dans un schéma de $F_n^2$ réduit, égalitaire, ayant m+1 faisceaux (minimum possible) le surplus $\sigma$ est égal au nombre g de coupes polaires minimales complètes.

En effet, le schéma contient au moins $n(m+2) - 2^{m+1}$ contacts; donc au moins une variable apparaît comme argument de $m+1$ contacts. Le schéma étant réduit, égalitaire et possédant $m+1$ faisceaux, seuls les nombres $c_m$ et $c_{m+1}$ ne sont pas nuls. Le corollaire se déduit alors immédiatement du théorème.
## 8. Étude de la fonction $S_n^1$

Considérons la fonction booléenne symétrique $S_n^1 \in \mathcal{F}_n$ définie par

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

Soit $E_{SP}(S_n^1)$ le nombre minimal de contacts suffisant pour construire un schéma bipolaire de type série-parallèle réalisant la fonction $S_n^1$.

Korobkov [21] a montré que pour $n$ vérifiant les inégalités $2^{m} \le n \le 2^{m+1}$ on a

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

Nous nous proposons dans ce chapitre de démontrer qu'en fait

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

# 1. La dualité dans les multigraphes et les schémas de contacts

## 1.1. - Dualité dans les multigraphes

1.1.1. - On dit qu'un multigraphe $G = (S, A, \Gamma)$ est planaire s'il est possible de le représenter sur un plan de sorte que les sommets soient des points distincts, les arêtes des courbes simples et que deux arêtes ne se rencontrent pas en dehors de leurs extrémités.

Soit $G$ un multigraphe planaire ; une face de $G$ est une région de plan limitée par des arêtes et qui ne contient ni sommets ni arêtes en son intérieur. Le contour d'une face est le cycle formé par ses arêtes frontières.
1.1.2. - Soit $G = (S, A, \Gamma)$ un multigraphe planaire. Désignons par $R = \{r_1, r_2, \dots, r_k\}$ l'ensemble de ses contours de face. Un multigraphe $G^* = (S^*, A^*, \Gamma^*)$ est appelé dual de $G$ s'il existe deux bijections $\theta : A \to A^*$ et $\omega : R \to S^*$ telles que

$a \in A$ et $a \in r_1 \cap r_j$ ($i \neq j$) $\Longleftrightarrow$ $a^* = \theta(a)$ a pour extrémités les sommets $r_i^* = \omega(r_i)$ et $r_j^* = \omega(r_j)$.

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

*Exemple.* - Sur la figure 1, nous avons représenté un multigraphe $G$ (en traits pleins) et un dual $G^*$ (en pointillé). $G^*$ est obtenu en plaçant à l'intérieur de chaque contour de face $r \in R$ un sommet $r^*$ de $G^*$. A chaque arête $a \in A$ est alors associée une arête $a^*$ qui relie les sommets intérieurs aux deux contours de face auxquels $a$ appartient.

Le théorème suivant est dû à Whitney. Nous le donnons sans démonstration.

### THÉORÈME 1 [38]. -

1/ Si un multigraphe $G^*$ est dual d'un multigraphe $G$,

$G$ est dual de $G^*$.

2/ Un multigraphe $G$ possède un dual si et seulement si il est planaire.

## 1.2. - Dualité dans les schémas de contacts bipolaires.

Considérons un schéma de contacts bipolaire $H = (G, h)$. Désignons par $(G + a_0)$ le multigraphe $G$ augmenté d'une arête auxiliaire $a_0$ ayant pour extrémités les pôles $I$ et $T$.

On dit que le schéma $H$ est planaire si le multigraphe $(G + a_0)$ est planaire.

Soient alors $(G^* + a_0^*)$ un multigraphe dual de $(G + a_0)$, et $G^*$ le multigraphe partiel obtenu à partir de $(G^* + a_0^*)$ par suppression de l'arête $a_0^* = \theta(a_0)$.

On appelle schéma dual du schéma $H = (G, h)$ un schéma bipolaire $H^* = (G^*, h^*)$ tel que

$1/h^*(a^*) = h(a)$ pour tout $a^* \in A^*$.
2/ H* a pour pôles I* et T* les extrémités de a₀*. Shannon [37] a montré le résultat suivant

PROPOSITION 1. - Les fonctions booléennes f et f* réalisées par deux schémas bipolaires duaux H et H* sont complémentaires (f*=1).

## 2. Etude des fonctions $S_n^1$ et $\bar{S}_n^1$

La fonction $\bar{S}_n^1$, complémentaire de la fonction $S_n^1$, est définie par

$$ (\text{où } F_n^2(x) = \sum_{1 \le i < j \le n} x_i x_j \qquad \bar{S}_n^1(x) = F_n^2(x) + \bar{x}_1 \bar{x}_2 \dots \bar{x}_n) $$

Un schéma de contacts de type série-parallèle est planaire et admet pour dual un schéma de type série-parallèle. Il résulte alors de la proposition 1 que $E_{SP}(S_n^1) = E_{SP}(\bar{S}_n^1)$.

Nous étudierons ce dernier nombre.

### 2.1. - Notations

Soient H un schéma bipolaire quelconque, $f_H \in \mathfrak{F}_n$ la fonction réalisée par H.

Nous poserons

$$ N_H = \{(i, j) | (i, j) \in \{1, 2, \dots, n\}^2, i \neq j \text{ et } x_i^* x_j^* \leq f_H\} $$

$$ N_0 = \{(i, j) | (i, j) \in \{1, 2, \dots, n\}^2 \text{ et } i \neq j\} $$

Nous désignerons par $\varphi_H$ l'ensemble des chaînes polaires élémentaires de H de transmission non nulle.

Soit c une chaîne quelconque de H. Nous noterons $P_c$ l'ensemble des variables qui sont arguments de contacts fermants de la chaîne c.

Nous poserons

$$ \varphi_H^1 = \{c \mid c \in \varphi_H \text{ et } |P_c| = 1\} $$

$$ \varphi_H^2 = \{c \mid c \in \varphi_H \text{ et } |P_c| = 2\} $$
Enfin, nous appellerons $W_H$ le nombre de contacts fermants de H

<figure><img src="image_16.png" /><figcaption>Fig. 2</figcaption></figure>

Exemple. — Le schéma représenté sur la figure 2 réalise la fonction

$$f_H = x_1^* x_2^* + x_2^* \bar{x}_3^* x_4^* \\ N_H = \{(1, 2)\}, W_H = 4$$

Soient $c_1$ et $c_2$ les deux chaînes polaires élémentaires de ce schéma

$$P_{c_1} = \{x_1, x_2\}, P_{c_2} = \{x_2, x_4\}, \varphi_H^1 = \emptyset, \varphi_H^2 = \{c_1, c_2\}$$

**PROPOSITION 2.** — Si un schéma bipolaire H réalise l'une des fonctions $\bar{S}_n^1$ ou $F_n^2$ on a

$$1/ N_H = N_0$$

$$2/ \varphi_H^1 = \emptyset$$

Si ces conditions sont remplies et si H est fermant, H réalise la fonction $F_n^2$.

Cette proposition ne fait que traduire les définitions de $\bar{S}_n^1$ et $F_n^2$.

**2.2. LEMME 1.** — Soit $H^0$ un schéma bipolaire de type série-parallèle, réalisant la fonction $\bar{S}_n^1$. Si $2^m \le n \le 2^{m+1}$ (m entier)

$$W_{H0} \ge n(m+2) - 2^{m+1}$$

**DEMONSTRATION.** — Ce lemme sera démontré en déterminant une suite de transformations du schéma $H^0$ en un schéma fermant de $F_n^2$ dans lequel le nombre des contacts n'est pas supérieur à $W_{H0}$. Le lemme découle alors directement du théorème 3 du chapitre précédent.

Nous supposerons qu'après chaque transformation les contacts qui n'appartiennent à aucune chaine polaire élémentaire sont supprimés.

1/ Par définition de $\bar{S}_n^1$ il ne peut exister de contact incident aux deux pôles I et T. Le schéma $H^0$ étant de type série-parallèle, il existe donc 2p schémas bipolaires $U_1^0, U_2^0, \dots, U_p^0$ et $V_1^0, V_2^0, \dots, V_p^0$ tels que $H^0$ est une connexion en parallèle de la famille de schémas $(U_\lambda^0 \circ V_\lambda^0)_{\lambda \le \lambda_p}$
Posons

$$U_{\lambda}^{0} \circ V_{\lambda}^{0} = H_{\lambda}^{0}$$

### Transformation 1.

Tout sous-schéma $H_{\lambda}^{0}$ composé uniquement de contacts ouvrants est supprimé.

Le schéma $H^0$ est ainsi transformé en un schéma $H^1$, connexion en parallèle d'une famille de schéma $(H_{\lambda j}^0)_{1 \le j \le p_1}$ avec $p_1 \ll p$.

On a

$$N_{H^1} = N_{H^0} = N_0$$

$$\varphi_{H^1}^1 = \varphi_{H^0}^1 = \emptyset$$

$$W_{H^1}^1 = W_{H^0}^1$$

2/ Considérons un sous-schéma $U_{\mu}^0 \circ V_{\mu}^0$ de $H^1$, soit $s_{\mu}$ le sommet commun à $U_{\mu}^0$ et $V_{\mu}^0$ et soit une chaîne élémentaire $c \in \varphi_{U_{\mu}^0}^1 \cup \varphi_{V_{\mu}^0}^1$. Supposons par exemple que $P_c = \{x_1\}$

### Transformation 2.

α) Les $x_1$-contacts de la chaîne $c$ sont supprimés.

β) Si $c \in \varphi_{U_{\mu}^0}^1$ (respect. $c \in \varphi_{V_{\mu}^0}^1$), un $x_1$-contact d'extrémités $I$ et $s_{\mu}$ (respect. $T$ et $s_{\mu}$) est introduit.

γ) La même transformation est effectuée pour toutes les chaînes de

$$\bigcup_{j=1}^{p_1} (\varphi_{U_{\mu_j}^0}^1 \cup \varphi_{V_{\lambda_j}^0}^1)$$

Soit $H^2$ le schéma ainsi obtenu. $H^2$ est une connexion en parallèle d'une famille de schémas $(U_{\nu}^2 \circ V_{\nu}^2)_{1 \le \nu \le p_1}$. La figure 3 représente l'un de ces schémas $U_{\nu}^2 \circ V_{\nu}^2$.

$U_{\nu}^2$ (respect. $V_{\nu}^2$) est une connexion en parallèle d'un ensemble (pouvant être vide) de contacts fermants et éventuellement d'un schéma $U_{\nu}^3$ (respect. $V_{\nu}^3$) tel que $\varphi_{U_{\nu}^3}^1 = \emptyset$ (respect. $\varphi_{U_{\nu}^3}^1 = \emptyset$)

Comme

$$f_{H^2} \ge f_{H^1}$$

on a

$$N_0 = N_{H^1} \subset N_{H^2} \subset N_0$$

donc

$$N_{H^2} = N_0$$
<figure><img src="image_17.png" /><figcaption>Fig. 3</figcaption></figure>

D'autre part, on a encore $\varphi_{H^2}^1 = \emptyset$ ($\varphi_{H^2}^1 \neq \emptyset$ impliquerait $\varphi_{H^1}^1 \neq \emptyset$) Enfin $W_{H^2} \leq W_{H^1}$.

### Transformation 3.

Pour tout $v \in \{1, 2, ..., p_1\}$, les sous-schémas $U_v^3$ et $V_v^3$, (s'ils existent) sont connectés directement entre I et T (figure 4).

Soit $H^3$ le schéma ainsi obtenu. Comme précédemment $f_{H^3}^3 \geq f_{H^2}^3 \longrightarrow N_{H^3} = N_0$.

D'autre part $\varphi_{H^3}^1 = \emptyset$ et $W_{H^3} \leq W_{H^2}$.

### Transformation 4.

Tout contact ouvrant incident aux deux pôles I et T est supprimé.

Soit $H^4$ le schéma ainsi obtenu. On a encore $N_{N^4} = N_0$, $\varphi_{H^4}^1 = \emptyset$ et $W_{H^4} = W_{H^3} \leq W_{H^0}$.

Le schéma $H^4$ ne contient aucun contact incident aux deux pôles I et T (ni contact ouvrant par suite de la transformation 4, ni contact fermant car $\varphi_{H^4}^1 = \emptyset$).

La suite des 4 transformations décrites plus haut peut donc être effectuée à nouveau. A l'issue d'un nombre fini 1 de transformations, le schéma $H^1$ obtenu est fermant, $N_{H^1} = N_0$ et $\varphi_{H^1}^1 = \emptyset$. Donc, d'après la proposition 2, $H^1$ réalise la fonction $F_n^2$.

Comme $W_{H^1} \leq W_{H^0}$, le lemme se trouve démontré.
2.3. THÉORÈME 2 (détermination de $E_{SP}(S_n^1)$). – Si $2^n \le n \le 2^{m+1}$

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

DÉMONSTRATION. –

a) L'inégalité $E_{SP}(S_n^1) < n(m+3) - 2^{m+1}$ a été obtenue par Korobkov [21]

b) Soit un schéma H bipolaire et de type série-parallèle réalisant la fonction $\tilde{S}_n^1$.

$$\text{D'après le lemme 1, } W_H \ge n(m+2) - 2^{m+1}$$

D'autre part, par définition de $\tilde{S}_n^1$, il existe une chaîne positive élémentaire de H ayant pour fonction de transmission $\prod_{i=1}^{n} \bar{x}_i^*$. Pour tout $i \in \{1, 2, \dots, n\}$, le schéma H contient au moins un $\bar{x}_i$-contact. Le nombre de contacts de H est donc supérieur au égal à $W_H + n$. Par suite : $E_{SP}(\tilde{S}_n^1) \ge n(m+3) - 2^{m+1}$.

<figure><img src="image_18.png" /><figcaption>Fig. 4</figcaption></figure>
L'ÉTHOREME S (démonstration de $R_{1234}$) - it $i \in \{1, 2, 3, 4\}$ -

$$R_{1234} \cdot R_{1234}^{-1} = R_{1234}^{-1} \cdot R_{1234}$$

DEMONSTRATION :

1. Développer $R_{1234} \cdot R_{1234}^{-1} - R_{1234}^{-1} \cdot R_{1234}$ et de même par $R_{1234} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1}$

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

2. Soutenir la hypothèse $R_{1234} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1} = R_{1234}^{-1} \cdot R_{1234}$ et de même la hypothèse $R_{1234} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1} = R_{1234}^{-1} \cdot R_{1234}$.

3. Démontrer que $R_{1234} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1} = R_{1234}^{-1} \cdot R_{1234}$, il existe une équation posée par $R_{1234}$ parmi $R_{1234} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1}$.

4. Démontrer que $R_{1234} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1} = R_{1234}^{-1} \cdot R_{1234}$, il est donc équivalent à montrer que $R_{1234} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1} = R_{1234}^{-1} \cdot R_{1234}$, lequel est équivalent à montrer que tout $R_{1234} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1} = R_{1234}^{-1} \cdot R_{1234}$, laquelle est équivalent à montrer que tout $R_{1234} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1} = R_{1234}^{-1} \cdot R_{1234}^{-1}$, laquelle est équivalent à montrer que tout $R_{1234} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1} = R_{1234}^{-1} \cdot R_{1234}^{-1}$.

5. Démontrer que $R_{1234} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1} = R_{1234}^{-1} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1}$.

6. Démontrer que $R_{1234} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1} = R_{1234}^{-1} \cdot R_{1234}^{-1}$.

TRANSFORMATION :

1

7. Démontrer que $R_{1234} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1} = R_{1234}^{-1} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1}$.

8. Démontrer que $R_{1234} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1} = R_{1234}^{-1} \cdot R_{1234}^{-1}$.

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

9. Démontrer que $R_{1234} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1} = R_{1234}^{-1} \cdot R_{1234}^{-1}$.

TRANSFORMATION :

10. Démontrer que $R_{1234} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1} = R_{1234}^{-1} \cdot R_{1234}^{-1}$.

11. Démontrer que $R_{1234} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1} = R_{1234}^{-1} \cdot R_{1234}^{-1}$.

12. Démontrer que $R_{1234} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1} = R_{1234}^{-1} \cdot R_{1234}^{-1}$.

13. Démontrer que $R_{1234} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1} = R_{1234}^{-1} \cdot R_{1234}^{-1}$.

14. Démontrer que $R_{1234} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1} = R_{1234}^{-1} \cdot R_{1234}^{-1}$.

15. Démontrer que $R_{1234} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1} \cdot R_{1234}^{-1} = R_{1234}^{-1} \cdot R_{1234}^{-1}$.
# 9. Schémas fonctionnels et fonctions booléennes croissantes

## Introduction

Nous définirons (sections 1 et 2) la notion de schéma fonctionnel. Soit $\mathcal{L}_f$ le nombre minimal d'éléments suffisant pour construire un schéma fonctionnel réalisant la fonction booléenne $f \in \mathfrak{F}_n$ et posons

$$ \max_{f \in \mathfrak{F}_n} \mathcal{L}_f = \mathcal{L}^+(n) $$

Lupanov [30] a montré que

$$ \sqrt{\frac{2}{\pi} \frac{2^n}{n\sqrt{n}} [1 - O(1)]} < \mathcal{L}^+(n) $$

D'un autre côté Reznik [34] a donné une méthode permettant de construire un schéma fonctionnel réalisant une fonction quelconque de $I_n$ et a ainsi démontré l'inégalité

$$ \mathcal{L}^+(n) < A_1 \frac{2^n}{n\sqrt{n}} (\log_2 n)^2 \quad \text{où } A_1 \text{ est une constante.} $$

Nechiporuk [31] a amélioré ce résultat en obtenant

$$ \mathcal{L}^+(n) < A_2 \frac{2^n}{n\sqrt{n}} (\log_2 n) \quad (A_2 \text{ constante}). $$

Puis Korobkov [23] utilisant la méthode dite de "codage local" a démontré

$$ \left\{ \begin{array}{l} \mathcal{L}^+(n) < A_3 \sqrt{\frac{2}{\pi} \frac{2^n}{n\sqrt{n}}} [1 + O(1)] \\ \text{avec } A_3 = \frac{8}{\frac{3}{(\sqrt{16}-1)^2}} \approx 4,27 \end{array} \right. $$
Nous nous proposons dans ce chapitre de définir un nouveau système de codage des fonctions booléennes croissantes. Cela nous permettra de démontrer l'inégalité

$$ \left\{ \begin{array}{l} \mathcal{L}^*(n) < A_4 \sqrt{\frac{2}{\pi} \frac{2^n}{n \sqrt{n}}} \left[ 1 + O\left( \frac{1}{\log_2 n} \right) \right] \\ \text{avec } A_4 = \log_2 3 \approx 1,58 \end{array} \right. $$

Le rapport des bornes supérieures et inférieures obtenues pour $\mathcal{L}^*(n)$ est ainsi abaissé de 4,27 à 1,58.

# 1. Graphes fonctionnels

## 1.1. - Graphes orientés

Un *graphe orienté* $G = (S, A, \Gamma)$ est défini par la donnée de
- Un ensemble $S$ dont les éléments sont les sommets de $G$;
- Un ensemble $A$ dont les éléments sont les arcs de $G$;
- Une application *injective* $\Gamma: A \to S^2$ qui, à tout arc $a \in A$ associe une paire *ordonnée* $(s, s')$ de sommets de $G$.

$s$ (respect. $s'$) est l'origine (respect. l'extrémité) de $a$. On dit également que $a$ est incident à $s$ vers l'extérieur (respect. à $s'$ vers l'intérieur).

Un graphe fini orienté se dessine sur le plan en représentant chaque sommet par un point et chaque arc par un trait (muni d'une flèche) reliant son origine à son extrémité.

Les notions de sous-graphe et de graphe partiel orientés, ainsi que la notion de graphe obtenu par contraction d'un ensemble de sommets se définissent comme au chapitre 4, les arêtes étant remplacées par les arcs.

Un *chemin* d'un graphe orienté est défini par la donnée d'une suite $(s_0, s_1, \dots, s_{1-1}, s_1, \dots, s_k)$ de sommets et d'une suite $(a_1, a_2, \dots, a_{1-1}, \dots, a_k)$ d'arcs, telles que pour tout $i \in \{1, 2, \dots, k\}$,

<footnote>* Nous garderons autant que possible des notations similaires pour les éléments correspondant des graphes orientés et des multigraphes non orientés définis au chapitre 4.</footnote>
l'arc $a_i$ a pour origine le sommet $s_{i-1}$ et pour extrémité le sommet $s_i$.

Les sommets $s_0$ et $s_k$ sont respectivement l'origine et l'extrémité du chemin. La longueur d'un chemin est le nombre de ses arcs. Un chemin élémentaire est un chemin dont les sommets sont distincts.

Un circuit est un chemin dont l'origine $s_0$ coincide avec l'extrémité $s_k$.

Soit un sommet $s \in S$. Nous noterons $A_s^-$ (respect. $A_s^+$) l'ensemble des arcs incidents à $s$ vers l'intérieur (respect. vers l'extérieur et $S_s^+$ (respect. $S_s^-$) l'ensemble de leurs origines (respect. de leurs extrémités).

## 1.2. Graphes fonctionnels.

### 1.2.1. - Nous appellerons graphe fonctionnel un graphe orienté, fini, et sans circuit $G = (S, A, \Gamma)$.

### 1.2.2. - L'ensemble $S$ des sommets d'un graphe fonctionnel est la réunion de $(p+1)$ sous-ensembles disjoints $E_0, E_1, \dots, E_p$ (certains pouvant être vides) définis par

$$E_i = \{s/s \in S \text{ et } |A_s^-| = i\}$$

Les éléments de $E_0$ (qui n'est jamais vide) sont appelés pôles d'entrée de $G$.

Les éléments de $E = \bigcup_{i=1}^p E_i$ sont appelés sommets fonctionnels de $G$.

### 1.2.3. - Soit un sommet $s \in S$. Désignons par $c_s$ l'ensemble des chemins élémentaires ayant pour origine un élément quelconque de $E_0$ et pour extrémité le sommet $s$.

Nous définissons une fonction numérique $\varphi : S \to N$ ($N$ l'ensemble des entiers naturels) par

$\varphi(s) = i$ si le plus long chemin de $c_s$ a pour longueur $i$ (si $s \in E_0$, $\varphi(s) = 0$).

$G$ étant fini et sans circuit, la fonction $\varphi$ est définie pour tout $s \in S$.

Posons $p' = \max_{s \in S} \varphi(s)$ et définissons la famille d'ensembles $(E_1', \dots, E_{p'}')$ par

$$E_i' = \{s \in S \text{ et } \varphi(s) = i\}$$
Nous pouvons énoncer

## PROPOSITION 1. -

a) La famille d'ensembles $(E_i)_{0 \le i \le p}$ constitue une partition de S.

$$b) \text{ pour tout } e \in E_i', S_e^- \subset \sum_{j=0}^{i-1} E_j$$

## DÉMONSTRATION. -

a) On a évidemment $E_i' \cap E_j' = \emptyset$ si $i \neq j$ et $\bigcup_{i=0}^p E_i' = S$. Par définition de $p', E_p'$, n'est pas vide.

Soit un sommet $e \in E_p'$, $\text{Max}_{s \in S_e^-} \varphi(s) = p' - 1$, donc $E_{p'-1}'$ n'est pas vide et de même, par récurrence, aucun ensemble $E_i'$, $0 \le i \le p'$, n'est vide.

$$b) \text{ Si } e \in E_i' \text{ et } s \in S_e^-, \varphi(s) \le i-1.$$

# 2. Schémas fonctionnels

## 2.1. - Définition.

Soit $G = (S, A, \Gamma)$ un graphe fonctionnel vérifiant la condition supplémentaire $\text{Max}_{e \in E} |S_e^-| \le 2$.

Alors

$$S = E_0 \cup E_1 \cup E_2 \quad \text{et} \quad E = E_1 \cup E_2$$

Posons

$$O_1 = \{-\}, \ O_2 = \{\dagger, \ .\}, \ O = O_1 \cup O_2$$

Les éléments de $O$ seront appelés **opérateurs**. Les éléments $\dagger, \ ., -$ seonr appelés **recptectivement** addition, multiplication, complémentation.

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

- du graphe fonctionnel $G = (S, A, \Gamma)$;

- d'une application $h : E \to O$ qui associe à chaque sommet $e \in E_i$ ($i = 1, 2$) un opérateur $h_e \in O_i$.

Les couples $(e, h_e)$ sont appelés **éléments fonctionnels** du schéma.
## 2.2. Schémas fonctionnels et fonctions booléennes

### 2.2.1. - Correspondance entre sommets et fonctions booléennes.

Considérons un schéma fonctionnel $H = (G, h)$ et soient $i_1, i_2, \dots, i_j, \dots, i_n$ ses pôles d'entrée. Aupôle $i_j, j \in \{1, 2, \dots, n\}$ associons la fonction booléenne $x_j^* \in \mathbb{F}_n$ (fonction définie par $x_j^*(x_1, x_2, \dots, x_n) = x_j$). La proposition 1 permet alors d'associer à chaque sommet $e \in E$ une fonction booléenne $f_e$ définie par récurrence sur les ensembles $E_0^1, E_1^1, \dots, E_p^1$. Soit $e \in E_k^1$ ($S_e^- \subset \sum_{i=0}^{k-1} E_i$)

a) si $e \in E_1$ et $S_e^- = \{s\}$ on pose $f_e = \bar{f}_s$

b) Supposons $e \in E_2$ et $S_e^- = \{s, s'\}$;

si $h_e = \dot{+}$, on pose $f_e = f_s + f_s'$;

si $h_e = \cdot$, on pose $f_e = f_s \cdot f_s'$.

Plus généralement à une famille de sommets $(s_i)_{1 \le i \le q}$ sera associée une famille $(f_{s_i})_{1 \le i \le q}$ de fonctions booléennes ou ce qui revient au même une application $f: B^n \to B^q$.

On dit qu'un schéma fonctionnel $H$ réalise la fonction $f: B^n \to B^q$ s'il existe dans $H$ une famille de sommets $(s_i)_{1 \le i \le q}$ dont l'application associée soit $f$.

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

### 2.2.2. Exemple.
Le schéma fonctionnel représenté sur la figure 1 réalise 7 fonctions booléennes différentes, la valeur de chacune étant indiquée au sommet correspondant. Les pôles d'entrée sont représentés par des points et les sommets fonctionnels par des cercles.

En chaque sommet fonctionnel est indiqué l'opérateur associé.

## 2.3. - Composition des schémas fonctionnels.

Considérons deux schémas fonctionnels $H$ et $H'$, soit $I' = \{i'_1, i'_2, \dots, i'_q\}$ l'ensemble des pôles d'entrée de $H'$ et soit $X$ une application de $I'$ dans l'ensemble $S$ des sommets de $H$. On appelle schéma composé de $H$ et $H'$ suivant $\alpha$ et on note $H' \circ H(\alpha)$ (ou $H' \circ H$ s'il n'y a pas ambiguïté) le schéma obtenu en contractant chaque pôle d'entrée $i'_j$ de $H'$ avec le sommet $\alpha(i'_j)$ et en maintenant au sommet obtenu l'opérateur initial $h_\alpha(i'_j)$.
La proposition suivante résulte alors immédiatement des définitions posées.

**PROPOSITION 2.** - Soient $f : B^n \to B^q$ l'application associée à la famille $[\alpha(i'_j)]_{1 \le i \le q}^{1 \le j \le q}$ de sommets de $H$ et $f' : B^q \to B^r$ l'application associée à une famille $(s'_i)_{1 \le i \le r}$ de sommets de $H'$. Dans le schéma $H' \circ H(\alpha)$, l'application associée à la famille $(s'_i)_{1 \le i \le r}$ est $f' \circ f$.

### 3. Résultats auxiliaires

**3.1. PROPOSITION 3.** - Un schéma fonctionnel réalisant tous les produits élémentaires de $n$ générateurs $x_1^*, x_2^*, \dots, x_n^*$ ne nécessite pas plus de $n + (n-1)2^n$ éléments fonctionnels.

En effet, la réalisation de la famille $(\bar{x}_i^*)_{1 \le i \le n}$ demande $n$ complémentations. Puis, chaque produit élémentaire $\chi_a$ peut être réalisé avec $n-1$ multiplications.

<figure><img src="image_22.png" /><figcaption>Fig. 2</figcaption></figure>

La figure 2 représente un schéma fonctionnel réalisant les 4 produits élémentaires de 2 générateurs $x_1^*$ et $x_2^*$.

**3.2.** - Le lemme suivant est dû à Lupanov [29]. Nous le donnons sans démonstration.

**LEMME 1.** - Toute fonction boo-léenne $f \in \mathfrak{F}_n$ peut être réalisée par un schéma fonctionnel dont le nombre d'éléments est inférieur à $\frac{2^n}{n} \left[ 1 + 0 \left( \frac{\log_2 n}{n} \right) \right]$.

### 4. Construction d'un schéma fonctionnel par codage local

Nous exposons dans cette section la méthode dite "de codage local". L'idée première de cette méthode remonte à Blokh [5] qui l'a appliquée à la construction de schémas de contacts.

Elle a été par la suite utilisée par divers auteurs pour la construction de schémas fonctionnels. Nous en donnerons ici une
présentation adaptée à la construction d'un schéma fonctionnel réa-
lisant une fonction booléenne croissante donnée.

4.1. - Tableau des valeurs d'une fonction $g \in \mathfrak{F}_k$

Soit $(a_1, a_2, \dots a_j, \dots a_{2k})$ la suite des éléments de $B^k$
disposés dans un certain ordre. Soit une fonction $g \in \mathfrak{F}_k$. Nous ap-
pellerons "tableau des valeurs de $g$" l'élément $\mathfrak{C}_g \in B^{2^k}$ défini par

$$
\mathfrak{C}_g = [g(a_1), g(a_2), \dots g(a_j), \dots g(a_{2k})]
$$

4.2. - Fonctions de codage ; longueur et largeur d'un codage

4.2.1. – Soit un sous-ensemble $A \subset \mathfrak{F}_k$. Nous appellerons fonction de codage de $A$ (ou plus simplement codage) une application injective $c : A \longrightarrow B^m$.

Pour une fonction $g \in A$, l'élément $c(g) \in B^m$ sera appelé
code de la fonction $g$.

$m$ est la longueur du codage de $A$.

L'ensemble $\mathfrak{F}_k$, lui-même peut être codé de façon triviale par
l'application $g \to \mathfrak{C}_g$. Ce codage a pour longueur $2^k$.

4.2.2. – Soit une fonction $g \in A$ et $c(g) = (c_1^g, c_2^g, \dots c_m^g)$ son
code. L'application $c$ étant injective, la connaissance de $c(g)$
permet de calculer le tableau $\mathfrak{C}_g$ des valeurs de $g$. Plus pré-
cisément, il existe une famille de $2^k$ applications $(\Delta_j)_{1 \le j \le 2^k}$, où
$\Delta_j$ est une application de $B^m$ dans $B$ telle que pour tout $g \in A$,
on a

$$
\Delta_j(c_1^g, c_2^g, \dots c_m^g) = g(a_j)
$$

Nous dirons que le codage $c$ a pour largeur $\mu$ si pour tout
$j \in \{1, 2, \dots, 2^k\}$ on peut trouver

a) deux familles de nombres entiers positifs $(p_r^j)_{1 \le r \le \beta_j}$ et $(q_s^j)_{1 \le s \le \gamma_j}$ telles que

$$
p_1^j < p_2^j < \dots < p_r^j < \dots < p_{\beta_j}^j < m
$$

$$
q_1^j < q_2^j < \dots < q_s^j < \dots < q_{\gamma_j}^j < j
$$

$$
\beta_j + \gamma_j = \mu_j, \quad \max_{1 \le j \le 2^k} \mu_j = \mu
$$

b) une application $\Delta_j : B^{\mu_j} \longrightarrow B$ telle que pour tout $g \in A$
$$ \Delta_j^* [c_{p_1}^{g_1}, \dots, c_{p_r}^{g_r}, \dots, c_{p_1}^{g_1}, g(a_1), \dots, g(a_{q_1}), \dots, g(a_{q_r}), \dots, g(a_{q_2}), \dots, g(a_{q_r})] \\ = \Delta_j [c_1^{g_1}, c_2^{g_2}, \dots, c_m^{g_m}] = g(a_j) $$

En d'autres termes $g(a_j)$ peut être calculé connaissant $\beta_j$ chiffres du code dont la place dans le code ne dépend que de $a_j$ (et non de $g$) et connaissant les valeurs de $g$ en $\gamma_j$ points de $B^k$ qui précèdent $a_j$ dans l'ordre choisi et qui ne dépendent également que de $a_j$.

De plus $\max_{1 \le j \le 2^k} (\beta_j + \gamma_j) = \mu$.

On a évidemment $\mu < m$ car on peut toujours choisir $\Delta_j^* = \Delta_j$.

### 4.3. Schéma de codage local d'une fonction $f \in \mathcal{F}_n$

**4.3.1. DÉFINITION.** – Soit une fonction booléenne $f \in \mathcal{F}_n$ que nous identifions à une application $f: B^k \times B^{n-k} \longrightarrow B$.

Nous posons

$$ (x_1, x_2, \dots, x_k) = y $$

$$ (x_{k+1}, x_{k+2}, \dots, x_n) = z $$

Soient deux éléments $a \in B^k$ et $b \in B^{n-k}$. Les fonctions $f^a \in \mathcal{F}_{n-k}$ et $f_b \in \mathcal{F}_k$ seront définies par

$$ f^a(z) = f(a, z) $$

$$ f_b(y) = f(y, b) $$

Puis, nous définissons le sous-ensemble $A_f^k \subset \mathcal{F}_k$ par

$$ A_f^k = \{f_z \mid z \in B^{n-k}\} $$

Soit $c$ un codage de longueur $m$ de l'ensemble $A_f^k$.

On appelle *schéma de codage local d'une fonction* $f \in \mathcal{F}_n$ un schéma fonctionnel $H_c^f$ qui réalise l'application $l_f: B^k \times B^{n-k} \longrightarrow B^k \times B^m$ définie par

$$ (y, z) \xrightarrow{1_f} [y, c(f_z)] $$

En d'autres termes, un tel schéma calcule, à partir de l'élément $z$ se présentant à ses $n-k$ derniers pôles d'entrée, le code de la fonction $f_z$. Les $k$ premiers pôles d'entrée de $H_c$
n'interviennent qu'à titre accessoire et ne sont reliés à aucun sommet fonctionnel. On peut donc identifier $H_c^f$ à un schéma fonctionnel réalisant m fonctions booléennes des n-k variables $x_{k+1}, x_{k+2}, \dots, x_n$. Nous noterons ces fonctions $l_1, l_2, \dots, l_m$.

**4.3.2.** - Construction d'un schéma de codage local $H_c^f$. Considérons une partition de $B^{n-k}$ telle que

$$ \left\{ \begin{array}{l} B^{n-k} = \sum_{j=1}^{q} C_j \\ |C_j| = d \quad \text{pour } 1 \le j \le q-1 \quad (d \text{ entier positif}) \\ |C_q| \le d \end{array} \right. $$

Par suite $q = \lfloor \frac{2^{n-k}}{d} \rfloor$ (j p ! = plus petit entier supérieur ou égal à p)

Nous définissons le sous-ensemble $\alpha_{n-k}^d \subset \mathfrak{F}_{n-k}$ par

$\alpha_{n-k}^d = \{1/1 \in \mathfrak{F}_{n-k} \text{ et il existe } j \in \{1, 2, \dots, q\} \text{ tel que } K_1 \subset C_j\}$

(où $K_1$ est l'ensemble caractéristique de la fonction 1).

On a donc

$$ |\alpha_{n-k}^d| \le q 2^d $$

Puis, nous définissons une partition de $\alpha_{n-k}^d$ en $d+1$ sous-ensembles par

$$ \left\{ \begin{array}{l} \alpha_{n-k}^d = \sum_{i=0}^{d} \alpha_{n-k}^{d,i} \\ \text{avec } \alpha_{n-k}^{d,i} = \{1/1 \in \alpha_{n-k}^d \text{ et } |K_1| = i\} \end{array} \right. $$

**PROPOSITION 4.** - On peut construire un schéma fonctionnel $H_{\alpha^d}$ qui réalise toutes les fonctions de $\alpha_{n-k}^d$ et dont le nombre $\mathcal{L}_{H_{\alpha^d}}^{n-k}$ d'éléments vérifie

$$ \mathcal{L}_{H_{\alpha^d}} \le (n-k) + (n-k-1) 2^{n-k} + q 2^d $$

## DÉMONSTRATION. -

a) D'après la proposition 3, un schéma D réalisant tous les produits élémentaires $z \to \chi_b(z)$, $b \in B^{n-k}$, peut être construit avec $(n-k) + (n-k-1) 2^{n-k}$ éléments fonctionnels.
b) Montrons que, le schéma D étant construit, l'ensemble des fonctions de $\mathcal{A}_{n-k}^d$ peut être réalisé avec moins de $|\mathcal{A}_{n-k}^d| \ll q 2^d$ éléments fonctionnels

- La fonction identiquement nulle peut être réalisée avec une multiplication $(\chi_b, \chi_b' = 0 \text{ si } b \neq b')$.

- Les fonctions de $\mathcal{A}_{n-k}^{d,1}$ sont déjà réalisées par le schéma D

- Puis par récurrence, toute fonction de $\mathcal{A}_{n-k}^{d,1}$ peut être réalisée avec une addition à partir d'une fonction de $\mathcal{A}_{n-k}^{d,1-1}$ et d'un produit élémentaire $\chi_b$.

**PROPOSITION 5.** — Soit une fonction $f \in \mathfrak{F}_n$. S'il existe un codage de longueur $m$ pour l'ensemble $A_f^k$, on peut construire un schéma de codage local $H_c^f$ dont le nombre $\mathcal{L}_{H_c^f}^d$ d'éléments fonctionnels vérifie

$$ \mathcal{L}_{H_c^f}^d \ll \mathcal{L}_{\mathcal{A}_{n-k}^d}^d + (q-1)m $$

**DEMONSTRATION.** — Soient $l_1, l_2, \dots, l_i, \dots, l_m$ les fonctions que doit réaliser le schéma $H_c^f$. Soit $l_{ij} : B^{n-k} \to B$ la fonction coincidant avec $l_i$ sur $C_j$ et nulle partout ailleurs

$$ l_i = \sum_{j=1}^{q} l_{ij} \qquad (1) $$

Les fonctions $l_{ij}$ appartiennent à $\mathcal{A}_{n-k}^d$. Le schéma $H_{\mathcal{A}_d}$ étant construit, une fonction $l_i$ peut alors être réalisée avec $q^{n-k-1}$ additions selon la décomposition (1).

### 4.4. - Schéma de décodage local d'une fonction $f \in \mathfrak{F}_n$

4.4.1. — Considérons l'application $\Delta_f : B^k \times c(A_f^k) \to B^k \times B^{2^k}$ définie par

$$ [y, c(f_z)] \xrightarrow{\Delta_f} (y, \mathcal{C}_{f_z}) $$

On appelle schéma de décodage local de la fonction $f$ un schéma fonctionnel $H_D^f$ qui réalise une fonction quelconque

$$ \Delta : B^k \times B^m \to B^k \times B^{2^k} \text{ coincidant avec } \Delta_f \text{ sur } B^k \times c(A_f^k) $$

En d'autres termes, le schéma $H_D^f$ calcule, à partir du code de la fonction $f_z$ qui se présente à ses derniers pôles d'entrée, le tableau $\mathcal{C}_{f_z}$ des valeurs de cette fonction.

Ici encore, les k premiers pôles d'entrée jouent un rôle accessoire. On peut donc identifier tout d'abord $H_D^f$ avec un
schéma fonctionnel réalisant une famille $(\Delta_j)_{1\le j\le 2^k}$ de $2^k$ fonctions de m variables où la fonction $\Delta_j$ est telle que pour tout $g \in A_f^k$,

$$ \Delta_j(c_1^g, c_2^g, \dots, c_m^g) = g(a_j) $$

Cependant si la largeur du codage est $\mu$, la construction de $H_D^f$ s'identifie avec la construction de $2^k$ schémas réalisant successivement chacun une fonction de $\mu$ variables au plus.

Du lemme 1 découle alors

**PROPOSITION 6.** — Si $\mu$ est la largeur du codage de $A_f^k$, un schéma de décodage $H_D^f$ peut être construit avec un nombre $\mathcal{L}_{H_D^f}$ d'éléments fonctionnels vérifiant

$$ \mathcal{L}_{H_D^f} < 2^k \cdot \frac{2^\mu}{\mu} \left[ 1 + O\left( \frac{\log_2 \mu}{\mu} \right) \right] $$

**4.4.2.** — Nous allons aussi démontrer

**PROPOSITION 7.** — Soient une fonction $f \in \mathfrak{F}_n$, $H_c^f$ et $H_D^f$ des schémas de codage et de décodage local de la fonction $f$. Il existe un schéma composé $H_D^f \circ H_c^f(\alpha)$ réalisant la famille de fonctions $(f^{\alpha j})_{1 \le j \le 2^k}$.

En effet, de la proposition 2 découle qu'il existe un schéma composé $H_D^f \circ H_c^f(\alpha)$ réalisant la fonction $\Delta_f \circ l_f$, laquelle est définie par

$$ (y, z) \xrightarrow{\Delta_f \circ l_f} (y, \mathfrak{C}_{f,z}) $$

Or

$$ \mathfrak{C}_{f,z} = [f_z(a_1), f_z(a_2), \dots, f_z(a_{2^k})] = [f(a_1, z), f(a_2, z), \dots, f(a_{2^k}, z)] \quad [f^{a_1}(z), f^{a_2}(z), \dots, f^{a_{2^k}}(z)] $$

**4.5.** — **Schéma terminal d'une fonction** $f \in \mathfrak{F}_n$

Posons $\mathfrak{C}_f^k = \{ \mathfrak{C}_{f,z} \mid z \in \mathbb{B}^{n-k} \}$

Considérons l'application $t_f : \mathbb{B}^k \times \mathfrak{C}_f^k \to \mathbb{B}$ définie par

$$ (y, \mathfrak{C}_{f,z}) \xrightarrow{t_f} f(y, z) $$

On appelle **schéma terminal** $H_T^f$ d'une fonction $f$ un schéma réalisant une application quelconque $t : \mathbb{B}^k \times \mathbb{B}^{2^k} \to \mathbb{B}$ coïncidant avec $t_f$ sur l'ensemble $\mathbb{B}^k \times \mathfrak{C}_f^k$.

Le schéma $H_T^f$ calcule la valeur de la fonction $f$ au point
x = (y, z), à partir de l'élément y, se présentant à ses k premiers pôles d'entrée, et du tableau $\mathcal{T}_{f,z}$ des valeurs de la fonction $f_z$ se présentant à ses $2^k$ derniers pôles d'entrée. Comme $f = t_f \circ \Delta_f \circ l_f$, il découle de la proposition 2 qu'il existe un composé $H_T^f \circ H_D^f \circ H_C^f$ des schémas $H_T^f, H_D^f, H_C^f$ qui réalise la fonction $f$.

## PROPOSITION 8. -

1/ Toute fonction booléenne $f \in \mathfrak{T}_n$ se décompose selon l'expression

$$f(x) = \sum_{j=1}^{2^k} \chi_{a_j}(y) \cdot f^{a_j}(z) \quad (1)$$

2/ Après construction des schémas $H_C^f$ et $H_D^f$, on peut construire un schéma terminal $H_T^f$ dont le nombre $\mathcal{L}_{H_T^f}^k$ d'éléments fonctionnels vérifie

$$\mathcal{L}_{H_T^f}^k < k + (k+1) 2^k$$

## DÉMONSTRATION. -

1/ La décomposition (1) s'obtient en considérant la partition suivante de $B^n = B^k \times B^{n-k}$

$$B^n = \sum_{j=1}^{2^k} \{a_j\} \times B^{n-k}$$

$(y, z) \longrightarrow \chi_{a_j}(y) \cdot f^{a_j}(z)$ n'est autre que la fonction coincidant avec $f$ sur $\{a_j\} \times B^{n-k}$ et nulle partout ailleurs.

2/ D'après la proposition 3, la famille $(\chi_{a_j})_{1 \le j \le 2^k}$ des produits élémentaires des k générateurs $x_1^*, x_2^*, \dots, x_k^*$ peut être réalisée par un schéma D' ne contenant pas plus de $k + (k-1) 2^k$ éléments fonctionnels.

Comme le schéma $H_D \circ H_C$ réalise la famille de fonctions $(f^{a_j})_{1 \le j \le 2^k}$ (proposition 7), on peut à partir des sommets de D' et de $H_D \circ H_C$, réaliser avec $2^k$ multiplications, la famille de fonctions $[(y, z) \longrightarrow \chi_{a_j}(y) \cdot f^{a_j}(z)]_{1 \le j \le 2^k}$.

La fonction $f$ peut alors être réalisée selon l'expression (1) avec $2^k - 1$ additions. On a donc

$$\mathcal{L}_{H_T^f}^k \le k + (k-1) 2^k + 2^k + 2^k - 1 = k - 1 + (k+1) 2^k$$
# 5. Construction d'un schéma fonctionnel réalisant une fonction croissante donnée $f \in I_n$ (borne supérieure de $\mathcal{L}_{(n)}^*$)

## 5.1. - Codage de l'ensemble $I_k$

### 5.1.1. - Définition d'une application $\sigma_g$. Propriétés.

Considérons une fonction croissante $g \in I_k$ et soit $\pi_k$ la partition en chaînes de $B^k$ (cf. chap. 1).

Soit $\mathbb{C}_0^g$ (respect. $\mathbb{C}_2^g$), l'ensemble des chaînes de $\pi_k$ dont le nombre d'éléments indéterminés est $0$ (resp. $2$) pour la fonction $g$.

On a*

$$ \pi_k = \mathcal{K}_1 \cup \mathcal{K}_2 \cup \mathbb{C}_0^g \cup \mathbb{C}_2^g $$

Nous définissons une application $\sigma_g : \pi_k \to \{0, 1, 2\}$ de la façon suivante

a) Si $J \in \mathcal{K}_1$, $\sigma_g(J) = g(\alpha_1)$ où $\alpha_1$ est l'élément unique de J.

b) Si $J \in \mathcal{K}_2$ et si $\alpha_1 < \alpha_2$ sont les éléments de J, nous posons

$$ \sigma_g(J) = 0 \quad \text{si} \quad g(\alpha_1) = g(\alpha_2) = 0 $$

$$ \sigma_g(J) = 1 \quad \text{si} \quad g(\alpha_1) = 0 \quad \text{et} \quad g(\alpha_2) = 1 $$

$$ \sigma_g(J) = 2 \quad \text{si} \quad g(\alpha_1) = g(\alpha_2) = 1 $$

c) Si $J \in \mathbb{C}_0^g$, $\sigma_g(J) = 0$

d) Si $J \in \mathbb{C}_2^g$ et si $\alpha_1 < \alpha_{1+1}$ sont les éléments indéterminés de $J$, $\sigma_g(J)$ est défini comme en b), $\alpha_1$ et $\alpha_2$ étant remplacés respectivement par $\alpha_1$ et $\alpha_{1+1}$.

Soient $\alpha_{1-1} < \alpha_1 < \alpha_{1+1}$ trois éléments successifs d'une même chaîne $J \in \pi_k$ et soit $\alpha_1^*$ le complément relatif de $\alpha_1$ dans l'intervalle fermé $[\alpha_{1-1}, \alpha_{1+1}]$. Nous pouvons alors énoncer

**PROPOSITION 9.** – Soit une chaîne $J \in \pi_k$ et un élément $\alpha_1 \in J$.

a) Si $J \in \mathcal{K}_1 \cup \mathcal{K}_2$, il existe une application

$$ \theta_{\alpha_1}: \{0, 1, 2\} \to B $$

telle que pour tout $g \in I_k$, $\theta_{\alpha_1}[\sigma_g(J)] = g(\alpha_1)$.

<footnote>* Rappelons que nous désignons par $\mathcal{K}_{k-2p+1}$ l'ensemble des chaînes de longueur $k-2p+1$ de $\pi_k$.</footnote>
b) Si $J \in \mathcal{K}_{k-2p+1}$ avec $k-2p+1 > 2$, il existe une application $\theta_{\alpha_1}: \{0, 1, 2\} \times B^3 \to B$ telle que pour tout $g \in I_k$

$$ \theta_{\alpha_1}[\sigma_g(J), g(\alpha'_{1-1}), g(\alpha'_1), g(\alpha'_{1+1})] = g(\alpha_1) $$

[Dans le cas où un seul élément (respect. deux éléments seulement, parmi $\alpha'_{1-1}$, $\alpha'_1$, $\alpha'_{1+1}$ existe (respect. existent), l'application $\theta_{\alpha_1}$ est définie sur $\{0, 1, 2\} \times B$, (respect. $\{0, 1, 2\} \times B^2$)].

DÉMONSTRATION. — La proposition exprime que $g(\alpha_1)$ est toujours calculable en fonction de $\sigma_g(J), g(\alpha'_{1-1}), g(\alpha'_1), g(\alpha'_{1+1})$.

a) Si $j \in \mathcal{K}_1 \cup \mathcal{K}_2$ cela découle de la définition même de $\sigma_g$.

b) Supposons $J \in \mathcal{K}_{k-2p+1}$ avec $k-2p+1 > 2$.

Le triplet $g(\alpha'_{1-1}), g(\alpha'_1), g(\alpha'_{1+1})$ peut prendre 6 valeurs seulement (d'après la proposition 6 du chapitre 1).

<table><thead><tr><th></th><th>A</th><th>B</th><th>C</th><th>D</th><th>E</th><th>F</th></tr></thead><tbody><tr><th>g(α'<sub>1-1</sub>)</th><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td></tr><tr><th>g(α'<sub>1</sub>)</th><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td><td>1</td></tr><tr><th>g(α'<sub>1+1</sub>)</th><td>0</td><td>1</td><td>0</td><td>1</td><td>1</td><td>1</td></tr></tbody></table>

Dans les cas A, C, E, F, l'élément $\alpha$ est "déterminé" pour la fonction $g$ et $g(\alpha_1)$ ne dépend que du triplet $[g(\alpha'_{1-1}), g(\alpha'_1), g(\alpha'_{1+1})]$.

Dans le cas B, les éléments $\alpha_1$ et $\alpha_{1+1}$ sont indéterminés pour $g$ et $g(\alpha_1) = \text{Max}[0, \sigma_g(J) - 1]$.

Dans le cas D, les éléments $\alpha_{1-1}$ et $\alpha_1$ sont indéterminés pour $g$ et $g(\alpha_1) = \text{Min}[0, \sigma_g(J)]$.

Dans tous les cas $g(\alpha_1)$ est calculable en fonction de $g(\alpha'_{1-1}), g(\alpha'_1), g(\alpha'_{1+1})$ et $\sigma_g(J)$ seulement.

### 5.1.2. — Définition d'une application $c_1$. Propriétés
Nous définissons l'application $c_1: I_k \to \{0, 1, 2\}^{c_k[\frac{k}{2}]}$ par $c_1(g) = [\sigma_g(J_1), \sigma_g(J_2), \dots, \sigma_g(J_{\frac{k}{2}})]$. (où $J_1, J_2, \dots, J_{\frac{k}{2}} \in c_k[\frac{k}{2}]$ sont les chaînes de $\pi_k$).
PROPOSITION 10. – L'application $c_1$ est injective.

En effet, d'après le théorème 1 du chapitre 1, si $\alpha_1$ appartient à une chaîne de $\mathcal{H}_{k-2p+1}$, les éléments $\alpha_{1-1}^1, \alpha_1^1, \alpha_{1+1}^1$ appartiennent à des chaînes de $\mathcal{H}_{k-2p-1}$. Disposons les éléments de $B^k$ dans l'ordre des chaînes de longueur croissante. Il résulte alors de la proposition 9 que le tableau $\mathfrak{G}_g$ des valeurs de $g$ peut être calculé à partir des seuls nombres de la suite $c_1(g)$. Donc $c_1$ est une application injective.

5.1.3. – Définition d'un codage c de $I_k$

Posons

$$ \delta = [\mathrm{Log}_3 k], \delta' = ] \delta \mathrm{Log}_2 3 [, p = \left[ \frac{C_k^{[\frac{k}{2}]} }{\delta} \right] $$

Divisons la suite $c_1(g) = [\sigma_g(J_1), \sigma_g(J_2), \dots, \sigma_g(J_{\frac{k}{2}})]$ en p sous-suites successives de longueur $\delta$ (la dernière sous-suite pouvant être de longueur inférieure).

Notons $\Sigma_g^\lambda$ la $\lambda$-sous-suite ainsi obtenue

$$ \left\{ \begin{array}{l} \Sigma_g^\lambda = [\sigma_g(J_{(\lambda-1)\delta+1}), \sigma_g(J_{(\lambda-1)\delta+2}), \dots, \sigma_g(J_{\lambda\delta})] \\ 1 < \lambda < p \end{array} \right. $$

Ainsi, nous pouvons écrire

$$ c_1(g) = (\Sigma_g^1, \Sigma_g^2, \dots, \Sigma_g^p) $$

$\Sigma_g^\lambda$ peut être considéré comme un nombre naturel $n_g^\lambda$ compris entre 0 et $3^\delta - 1$, écrit dans le système numérique à base 3. Ce même nombre $n_g^\lambda$ peut se représenter dans le système binaire par une suite $\Sigma_g^{1\lambda}$ de 0 et de 1 de longueur $\delta = ]\delta \times \mathrm{Log}_2 3[$ (on ajoute éventuellement des 0 à gauche pour compléter la suite).

La correspondance entre les $\Sigma_g^\lambda$ et les $\Sigma_g^{1\lambda}$ est biunivoque. La suite $[\Sigma_g^{11}, \Sigma_g^{12}, \dots, \Sigma_g^{1p}]$ de 0 et de 1 obtenue par juxtaposition des suites $\Sigma_g^{1\lambda}$, $1 < \lambda < p$, a pour longueur $p\delta'$.

Définissons l'application $c_2 : c_1(I_k) \to B^{p\delta'}$ par

$$ c_2[c_1(g)] = [\Sigma_g^{11}, \Sigma_g^{12}, \dots, \Sigma_g^{1p}] $$

L'application $c_2$ est injective. Il en est de même (conséquence de la proposition 10) de l'application composée $c = c_2 \circ c_1$.

c est donc un codage de l'ensemble $I_k$.
### 5.1.4. - Propriétés du codage c.

**PROPOSITION 11.** - Le codage c q pour longueur m = pδ' et pour largeur μ = δ' + 3.

#### DÉMONSTRATION. -

1/ c est une application de $I_k$ dans $B^{p\delta'}$.

Donc $m = p\delta'$.

2/ Considérons la suite $(a_1, a_2, \dots, a_j, \dots, a_{2k})$ des éléments de $B^k$ rangés par ordre de chaînes de longueur croissante.

Notons $J^a_j$ la chaîne de $\pi_k$ à laquelle appartient $a_j$. Supposons que $J^a_j \in \mathcal{J}_{k-2p+1}$ et soient $\alpha_1^j < \alpha_2^j < \dots < \alpha_{i-1}^j < \alpha_{i+1}^j < \dots < \alpha_{k-2p+1}^j$ les éléments de $J^a_j$. On a par exemple $a_j = \alpha_1^j$.

Soient $J'^{a_j}$ la suite adjointe de $J^a_j$ et $\alpha'^j = (2 \le i \le k-2p)$ le complément relatif de $\alpha_1^j$ dans l'intervalle fermé $[\alpha_{1-1}^j, \alpha_{1,1}^j]$. Les éléments $\alpha_1'^{j-1}, \alpha_1'^{j}, \alpha_1'^{j+1}, \text{s'ils existent, appartiennent à des chaînes de } \mathcal{J}_{k-2p+1} \text{ et précèdent donc } a_j \text{ dans l'ordre choisi. Supposons par exemple } \alpha_{i-1}^j = a_{q_1}, \alpha_1'^j = a_{q_2}, \alpha_1'^{j+1} = a_{q_3} \text{ et } q_1 < q_2 < q_3 < j$. D'après la proposition 9, $g(a_j)$ peut être calculé en fonction de $\sigma_g(J'^{a_j})$, $g(a_{q_1})$, $g(a_{q_2})$, $g(a_{q_3})$ seulement.

3/ Soit $\Sigma_g^{\lambda_j}$ la sous-suite de $c_1(g)$ à laquelle appartient $\sigma_g(J'^{a_j})$. La correspondance entre les suites $\Sigma_g^{\lambda_j}$ et $\Sigma_g^{\lambda'_j}$ étant biunivoque, $\sigma_g(J'^{a_j})$ peut être calculé en fonction des chiffres du code appartenant à la suite $\Sigma_g^{\lambda'_j}$.

Posons $(\lambda_j - 1)\delta' = u$.

On a alors

$$ \Sigma_g^{\lambda'_j} = (c_{u+1}^g, c_{u+2}^g, \dots, c_{u+\delta'}^g) $$

Finalement, $g(a_j)$ peut être calculé en fonction de $c_{u+1}^g, c_{u+2}^g, \dots, c_{u+\delta'}^g$ ; $g(a_{q_1})$, $g(a_{q_2})$, $g(a_{q_3})$.

Il existe donc une application $\Delta_j^* : B^{\delta'+3} \to B$ telle que pour tout $g \in I_k$

$$ \Delta_j^*[c_{u+1}^g, c_{u+2}^g, \dots, c_{u+\delta'}^g, g(a_{q_1}), g(a_{q_2}), g(a_{q_3})] = g(a_j). $$

Les indices $u+1, u+2, \dots, u+\delta'$ ne dépendent que de $a_j$. Il en est de même de $q_1, q_2, q_3$ et $q_1 < q_2 < q_3 < j$. Le code c a donc une largeur $\mu = \delta' + 3$.
## 5.2 - Application de la méthode de codage local à la construction d'un schéma fonctionnel réalisant une fonction croissante donnée.

### THÉORÈME 1 [19]. -

$$ \ell^+(n) < (\log_2 3) \sqrt{\frac{2}{\pi}} \frac{2^n}{n\sqrt{n}} \left[ 1 + o\left(\frac{1}{\log_2 n}\right) \right] $$

**DÉMONSTRATION.** - Soit une fonction quelconque $f \in I_n$. Nous appliquons la méthode de construction d'un schéma par codage local décrite dans la section 4 pour réaliser la fonction $f$. $f$ étant croissante, il en résulte que $A_f \subset I_k$. La restriction à l'ensemble $A_f^k$ du codage $c$ de $I_k$ défini en 5.1.3 est un codage de $A_f^k$.

D'après la proposition 11, la longueur $m$ et la largeur $\mu$ de ce codage sont

$$ m = p\delta' $$

$$ \mu = \delta' + 3 $$

avec

$$ p = ] \frac{C_k^{[\frac{k}{2}]} }{\delta} [ \text{et } \delta' = ] \delta . \log_2 3 [ $$

Il en résulte que

$$ m \ll C_k^{[\frac{k}{2}]} (\log_2 3) \left[ 1 + \frac{\delta}{C_k^{[\frac{k}{2}]} } \right] \left[ 1 + \frac{1}{\delta} \right] $$

Le nombre minimal $\ell_f$ d'éléments fonctionnels suffisant pour réaliser la fonction $f$ vérifie

$$ \ell_f \ll \ell_{H_C^f} + \ell_{H_D^f} + \ell_{H_T^f} $$

Il découle des propositions 4, 5, 6, 8 que

$$ \ell_f < n-k + (n-k-1)2^{n-k} + q2^d + (q-1)m + 2^k \cdot \frac{2^\mu}{\mu} \left[ 1 + o\left( \frac{\log_2 \mu}{\mu} \right) \right] + k + (k+1)2^k \quad \begin{array}{c} \text{A} \\ \text{B} \\ \text{C} \\ \text{D} \\ \text{E} \end{array} $$

avec

$$ q = \left\lfloor \frac{2^{n-k}}{d} \right\rfloor $$
Posons

$$k = [n-3 \ Log_2 n], \ d = [n-5 \ Log_2 n], \ \delta = [Log_3 k]$$

On obtient alors

$$A \sim 3(\text{Log}_2 n) \frac{2^n}{n^3}, \quad B \sim \frac{2^n}{n^3}, \quad D \sim \frac{2^n}{n^2 \text{Log}_2 n}, \quad E \sim \frac{2^n}{n^2}$$

$$C < \frac{2^{n-k}}{d} \times \sqrt{\frac{2}{\pi}} \frac{2^k}{\sqrt{k}} (\text{Log}_2 3) \left[ 1 + O\left(\frac{1}{k}\right) \right] \left[ 1 + O\left(\frac{\text{Log}_2 k}{k^2}\right) \right] \left[ 1 + O\left(\frac{1}{\text{Log}_2 k}\right) \right]$$

Soit

$$C < \sqrt{\frac{2}{\pi}} \frac{2^n}{n\sqrt{n}} (\text{Log}_2 3) \left[ 1 + O\left(\frac{1}{\text{Log}_2 n}\right) \right]$$

Le théorème se déduit immédiatement de ces résultats.

## Conclusion

En tenant compte des résultats obtenus par Lupanov (cf. Introduction de ce chapitre) le nombre $\mathcal{L}^+(n)$ obéit, pour $n$ assez grand, aux inégalités

$$\sqrt{\frac{2}{\pi}} \frac{2^n}{n\sqrt{n}} (1-\epsilon) < \mathcal{L}^+(n) < (\text{Log}_2 3) \sqrt{\frac{2}{\pi}} \frac{2^n}{n\sqrt{n}} \left[ 1 + O\left(\frac{1}{\text{Log}_2 n}\right) \right]$$
# 10. Résultats de Kruskal et Lupanov

Le but de ce chapitre est principalement d'ordre bibliographique. Dans une première partie nous présenterons certains résultats de Kruskal [40] relatifs aux fonctions booléennes croissantes*. Dans une seconde partie nous exposerons une méthode de décomposition des fonctions booléennes symétriques croissantes donnée récemment par Lupanov qui permet d'obtenir pour ces fonctions une construction de schémas de contacts particulièrement économique [41].

## 1. Résultats de Kruskal

### 1.1. - Représentation "canonique" des entiers positifs.

Le coefficient binomial $C_n^k$ est une fonction croissante de $n$. Soient $a$ et $j$ deux entiers positifs. On peut écrire $a$ d'une façon et d'une seule sous la forme

$$a = C_{n_j}^j + C_{n_{j-1}}^{j-1} + \dots + C_{n_p}^p + \dots + C_{n_k}^k \quad (1)$$

où pour tout $p \le j$, $n_p$ est le plus grand entier tel que

$$C_{n_p}^p \le a - C_{n_j}^j - C_{n_{j-1}}^{j-1} - \dots - C_{n_{p+1}}^{p+1} < C_{n_{p+1}}^p$$

Une telle représentation sera appelée *canonique* (d'ordre $j$) et notée $(a)_j = (n_j, n_{j-1}, \dots, n_k)_j$

Il résulte de la relation de Pascal et de la relation

$$\sum_{i=0}^{p} C_{n_p-p+i}^{i} = C_{n_p+1}^{p}$$

<footnote>* La démonstration du lemme 1 est originale et plus simple que celle initialement donnée par Kruskal.</footnote>
que (1) est une représentation canonique de a si et seulement si

$$n_j > n_{j-1} > \dots > n_p > \dots > n_k \ge 1$$

a et $(a)_j$ étant définis par (1) et (2) nous poserons

$$(a_j') = (n_j, n_{j-1}, \dots, n_k)_{j'} = C_{n_j}^{j'} + C_{n_{j-1}}^{j'-1} + \dots + C_{n_p}^{p+j'-j} + \dots + C_{n_k}^{k+j'-j}$$

(Par convention $C_n^p = 0$ si $p < 0$ ou $p > n$). On montre

PROPOSITION 1. – a $\le b$ entraine $(a)_j^{j'} \le (b)_j^{j'}$

## 1.2. - Rappels - Notations.

Soit une fonction booléenne croissante $f \in I_n$. De la pro-
position 3 du chapitre 3 résulte que pour tout $i \in \{1, 2, \dots, n\}$,
il existe deux fonctions $f_0^i$ et $f_1^i \in I_{n-1}$, déterminées de façon unique
et telles que

$$- f_0^i \le f_1^i$$

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

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

Considérons les ensembles

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

$$A_{j-1,i}^{*} = \{x \mid x \in B^{n-1} - K_{f_1^i} \text{ et } |s(x)| = j-1\}$$

$$A_{j,i}^{0*} = \{x \mid x \in B^{n-1} - K_{f_0^i} \text{ et } |s(x)| = j\}$$

On a la relation

$$|A_j^*| = |A_{j-1,i}^*| + |A_{j,i}^{0*}|$$

Dans la suite pour simplifier les écritures nous noterons

$$|A_{j-1,i}^*| = d_i \text{ et } |A_{j,i}^{0*}| = e_i$$

(l'indice j est supposé fixé une fois pour toutes).

La quantité $d_i$ (respect. $e_i$) a une interprétation simple, c'est le nombre d'éléments de $A_j^*$ dont le support contient (respect. ne contient pas) le chiffre $i$.
Enfin nous poserons

$$d = \min_i d_i$$

$$e = \max_i e_i$$

De la relation (3) il résulte

$$d + e = |A_j^*| \quad (4)$$

De plus est vérifiée la relation

$$\sum_{i=1}^{n} d_i = j |A_j^*| \quad (5)$$

### 1.3. - Fonctions booléennes "en cascade"

Une fonction booléenne croissante peut être définie par la donnée des éléments maximaux de $B^n - K_f$.

Considérons une suite d'entiers

$$n_j > n_{j-1} > \dots > n_{k+1} > n_k \ge 1$$

Nous dirons qu'une fonction booléenne croissante $f \in I_{n_j+1}$ est "en cascade" et de type $(n_j, n_{j-1}, \dots, n_k)$ si les éléments maximaux $a_j, a_{j-1}, \dots, a_k$ de $B^n - K_f$ ont pour support

$$s(a_j) = \{1, 2, \dots, n_j\}$$

$$s(a_{j-1}) = \{1, 2, \dots, n_{j-1}, n_j + 1\}$$

$$s(a_{j-2}) = \{1, 2, \dots, n_{j-2}, n_j, n_j + 1\}$$

$$s(a_p) = \{1, 2, \dots, n_p, n_{p+2}, n_{p+3}, \dots, n_{j-1}, n_j, n_j + 1\}$$

$$s(a_k) = \{1, 2, \dots, n_k, n_{k+2}, \dots, n_j, n_j + 1\}$$

**THÉORÈME 1.** - Soit $f$ une fonction en cascade de type $(n_j, n_{j-1}, \dots, n_k)$. Alors $|A_j^*| = (n_j, n_{j-1}, \dots, n_k)^{j'}$

**DÉMONSTRATION.** - $B^n - K_f$ est la réunion de $j-k+1$ sous-ensembles disjoints
$$D_j = \{x \mid s(x) \subseteq s(a_j)\}$$

$$D_{j-1} = \{x \mid \{n_j + 1\} \subseteq s(x) \subseteq s(a_{j-1})\}$$

$$D_p = \{x \mid \{n_{p+2}, n_{p+3}, \dots, n_j, n_j + 1\} \subseteq s(x) \subseteq s(a_p)\}$$

$$D_k = \{x \mid \{n_{k+2}, n_{k+3}, \dots, n_j, n_j + 1\} \subseteq s(x) \subseteq s(a_k)\}$$

Or on a

$$|A_j^* \cap D_p| = C_{n_p}^{p+j'-j}$$

Le théorème s'en déduit

**1.4. LEMME 1.** – *Pour toute fonction $f \in I_n$*

Si $|A_j^*| \ge 2$ et $j \ge 1$ on a

$$d \le (e)^{j-1}_j$$

**DÉMONSTRATION.** – De (5) on déduit l'inégalité

$$d \le \frac{j |A_j^*|}{n} \qquad (6)$$

Distinguons deux cas

a) La représentation canonique d'ordre $j$ de $|A_j^*|$ ne contient qu'un terme $|A_j^*| = C_{n_j}^j$ ($n_j \ge j + 1$)

Alors de (6) il découle

$$d \le C_{n_{j-1}}^{j-1} \text{ et par conséquent } e \ge C_{n_{j-1}}^j \quad (\text{cf. (4)})$$

On a donc bien $d \le (e)^{j-1}_j$

b) La représentation canonique d'ordre $j$ de $|A_j^*|$ contient plusieurs termes

Soit $((|A_j^*|)_j) = (n_j, n_{j-1}, \dots, n_p, n_k)_j$ cette représentation.

On a $n \ge n_i + 1$

Soit $f'$ la fonction en cascade de type $(n_j, n_{j-1}, \dots, n_k)$ et $d'_1, d'_2, \dots, d'_{n_j+1}$ les nombres correspondants ; ils vérifient

$$\sum_{i=1}^{n_j+1} d'_i = j |A_j^*| \qquad (8)$$
De la définition des fonctions en cascade il résulte que

$$ \operatorname{Max}_i d'_i = d'_1 = C_{n_{j-1}}^{j-1} + C_{n_{j-1}'}^{j-2} + \dots + C_{n_k-1}^{k-1} > \frac{\sum_j A_j^*}{n_j + 1} \quad (9) $$

(l'inégalité stricte est vérifiée car il y a au moins deux termes dans la représentation canonique de $|A_j^*|$)

De (6), (7), (9) il résulte

$$ d \le d'_1 - 1 \quad (10) $$

Soit alors $\mu \in \{k, k+1, \dots, j\}$ le plus grand entier, s'il existe, tel que $n_\mu = \mu$

On vérifie que

$$ d'_1 - 1 \le C_{n_{j-1}}^{j-1} + C_{n_{j-1}'}^{j-2} + \dots + C_{n_{\mu+1}'}^{\mu} + C_{\mu}^{\mu-1} = (|A_j^*| - d'_1 + 1)_j^{j-1} \quad (11) $$

De (10), (11) et de la proposition (1) il résulte

$$ d \le d'_1 - 1 \le [ |A_j^*| - (d'_1 - 1) ]_j^{j-1} \le ( |A_j^*| - d )_j^{j-1} = (e)_j^{j-1} $$

**1.5. THÉORÈME 2.** — Sott'une fonction booléenne croissante quelconque $f \in \mathcal{L}_n$. Si la représentation canonique d'ordre $j$ de $|A_j^*|$ est

$$ |A_j^*| = (n_j, n_{j-1}, \dots, n_k)_j $$

$$ \text{si} \quad j' \ge j \quad |A_{j, \cdot}^*| \le (n_j, n_{j-1}, \dots, n_k)_j^{j'} $$

$$ \text{si} \quad j' \le j \quad |A_{j, \cdot}^*| \ge (n_j, n_{j-1}, \dots, n_k)_j^{j'} $$

La démonstration de ce théorème étant fort longue nous en indiquons seulement le principe. Raisonnant par récurrence sur $n$ on obtient les relations

$$ |A_{j, \cdot}^*| = |A_{j, \cdot, 1, 1}| + |A_{j, \cdot, 1, 1}| \le (d)_{j-1}^{j'-1} + (e)_j^{j'} $$

On montre alors que sous les contraintes

$$ d + e = |A_j^*| \quad \text{et} \quad d \le (e)_j^{j-1} $$

on a

$$ \operatorname{Max}[(d)_{j-1}^{j'-1} + (e)_j^{j'}] = (A_j^*)_j^{j'} $$
## 2. Résultats de Lupanov [41]

### 2.1. - Fonctions booléennes symétriques

Soit $\sigma_n$ le groupe symétrique de degré $n$. Une fonction booléenne $f \in \mathfrak{F}_n$ est dite *symétrique* si pour toute permutation $\sigma \in \sigma_n$ et pour tout $x = (x_1, x_2, \dots, x_n) \in \mathbb{B}^n$, on a

$$f(x_{\sigma(1)}, x_{\sigma(2)}, \dots, x_{\sigma(n)}) = f(x_1, x_2, \dots, x_n).$$

Il en résulte que la valeur d'une fonction symétrique $f$ en $x$ ne dépend que du nombre $|s(x)|$ de coordonnées non nulles de $x$.

Soit un sous-ensemble $K \subset \{0, 1, \dots, n\}$ et soit $S_n^K$ la fonction symétrique définie par

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

Les fonctions $S_n^{\{i\}}$, $i \in \{1, 2, \dots, n\}$ sont appelées *fonctions symétriques élémentaires*.

Les fonctions symétriques *croissantes* sont de la forme $S_n^{(p, p+1, \dots, n)}$.

On posera $S^{(p, p+1, \dots, n)} = F_n^p$.

### 2.2. - Fonctions booléennes périodiques.

Une fonction symétrique $S_n^K$ est *periodique*, de période $d$, si $i \in K \iff i+md \in K$ pour tout entier tel que $0 \le i+md \le n$.

Pour définir une fonction $S_n^K$ de période $d$, il suffit de se donner l'ensemble $K_d = K \cap \{0, 1, \dots, d-1\}$.

Nous noterons $T_n^{K_d}$ une fonction ainsi définie.

Nous dirons que deux fonctions $T_n^{K_d}$ et $T_n^{K'_d}$ (de même période $d$) sont *semblables* si les éléments de $K'_d$ se déduisent de ceux de $K_d$ par addition modulo $d$ d'un même entier $j$. Il est clair que la similitude est une relation d'équivalence.

On appelle *fonction périodique élémentaire* $T_n^{d, 1}$ de base $i$ et de période $d$, la fonction définie par $K_d = \{i\}$.

### 2.3. - Propriétés des fonctions périodiques.

Dans la suite, nous noterons $\bar{i}(d)$ (ou plus simplement $\bar{i}$ s'il n'y a pas ambiguïté sur la période) l'unique élément congru à $i$ modulo $d$ et compris entre $0$ et $d-1$.
## PROPOSITION 2. -

$$ \text{a)} \quad S_n^K = \sum_{i \in K} S_n^{\{i\}} $$

$$ \text{b)} \quad T_n^{K_d} = \sum_{i \in K_d} T_n^{d, i} $$

$$ \text{c)} \quad \text{Si } d > n+1, \quad S_n^{\{i\}} = T_n^{d, i} $$

Cette proposition résulte immédiatement des définitions posées.

La proposition suivante donne une propriété très utile des fonctions booléennes périodiques.

**PROPOSITION 3.** - Soient $d_1$ et $d_2$ deux entiers premiers entre eux, i un entier vérifiant $0 \le i < d_1d_2$, et soient $i_1 = \bar{i}(d_1)$ et $i_2 = \bar{i}(d_2)$. On a la relation

$$ T_n^{d_1 d_2^i} = T_n^{d_1^i} T_n^{i_1} T_n^{d_2^i} $$

Cette relation s'obtient en montrant que

$$ p \equiv i \mod(d_1 d_2) \iff [p \equiv i_1 \mod d_1 \text{ et } p \equiv i_2 \mod d_2] $$

$(i_1 \text{ et } i_2 \text{ étant donnés, on montre que } i \text{ est unique}).$

A partir des propositions 2 et 3, on obtient

## PROPOSITION 4. -

1/ Soient s et t deux entiers premiers entre eux tels que $st \ge n+1$. Toute fonction $S_n^K$ peut se décomposer selon une expression

$$ S_n^K = \sum_{i=0}^{t-1} T_n^{t, i} \cdot T_n^{K_i} \quad \text{où pour tout } i \in \{0, 1, \dots, t-1\}, \quad T_n^{K_i} \text{ est une fonction périodique de période s.} $$

2/ Si de plus $S_n^K$ est croissante, on peut trouver deux fonctions $T_n^{K_1}$ et $T_n^{K_2}$ telles que toute fonction $T_n^{K_1}$, $0 \le i \le t-1$, soit semblable à l'une d'entre elles.

## DÉMONSTRATION. -

1/ La décomposition de $S_n^K$ s'obtient en appliquant successivement a) et c) de la proposition 2, puis la proposition 3, puis b' de la proposition 2.

$$ \text{2/ Supposons } S_n^K = F_n^p. $$
Utilisant la proposition 3, on obtient

$$F_n^p = \sum_{i=p}^{p+t-1} T_n^{t, \overline{I}(t)} [T_n^{s, \overline{I}(s)} + T_n^{s, \overline{i+t}(s)} + \dots + T_n^{s, \overline{s, \overline{i+k_i t}(s)}}]$$

où pour tout $i$ tel que $p \le i \le p+t-1$, $k_i$ vérifie $n-t+1 \le i+k_i t \le n$

Posons

$$T_n^{\overline{k}_s^i} = [T_n^{s, \overline{I}(s)} + T_n^{s, \overline{i+t}(s)} + \dots + T_n^{s, \overline{s, \overline{i+k_i t}(s)}}]$$

Les fonctions $T_n^{\overline{k}_s^i}$, $p \le i \le p+t-1$, sont à l'ordre près les mêmes que les fonctions $T_n^{\overline{k}_s^i}$, $0 \le i \le t-1$ obtenues dans la décomposition du $1/.$

D'autre part

si $p \le i \le n-k$ t, $T_n^{\overline{k}_s^i}$ et $T_n^{\overline{k}_s^p}$ sont semblables

si $n-k_p t+1 \le i \le p+t-1$ $T_n^{\overline{k}_s^i}$ et $T_n^{\overline{k}_s^{n-k_p t+1}}$ sont semblables.

On obtient la proposition en posant

$$\lambda = p \quad \text{et} \quad \mu = n-k_p t+1.$$

## 2.4.- Réalisation des fonctions périodiques par des schémas de contacts.

### PROPOSITION 5. -

1/ Un schéma de contacts fortement disjonctif, (d-d) polaire ayant pour pôles d'entrée $i_0, i_1, \dots, i_{d-1}$ et pour pôles de sortie $t_0, t_1, \dots, t_{d-1}$ et tel que $f_{i_j t_k} = T_n^{d, k-j}$ peut être construit avec 2 dn contacts.

2/ Un schéma de contacts fortement disjonctif (d-1)polaire réalisant toutes les fonctions semblables à une fonction périodique $T_n^{\overline{k}_d}$ donnée peut être construit avec 2 dn contacts.

### DEMONSTRATION. -

<figure><img src="image_23.png" /><figcaption>Fig. 1</figcaption></figure>
1/ Considérons le schéma $S_j(d, d)$ (figure 1) où pour tout $k \in \{0, 1, \dots, d-1\}$ le pôle $i_k$ est relié à $t_k$ par un $x_j$-contact et à $t_{k+1}$ par un $x_j$-contact ($i_{d-1}$ est relié à $t_0$ par un $x_j$-contact).

<figure><img src="image_24.png" /><figcaption>Fig. 2</figcaption></figure>

Le schéma $S_1 \circ S_2 \circ \dots S_n$ obtenu (figure 2) par composition des schémas $S_i, 1 \le i \le n$ a la propriété indiquée.

2/ Il résulte de 1/ qu'entre le pôle $i_0$ et les pôles $t_0, t_1, \dots, t_{d-1}$ sont réalisées respectivement les fonctions

$$T_n^{d,0}, T_n^{d,1}, \dots, T_n^{d,d-1}$$

Soit alors une fonction périodique quel-
conque $T_n^{K_d}$ ; on a

$$T_n^{K_d} = \sum_{i \in K_d} T_n^{d, i}$$

Si l'on contracte en un pôle unique de sortie $t$ la famille de pôles de sortie $(t_i)_{i \in K_d}$, la fonction réalisée entre $i_0$ et $t$ est $T_n^{K_d}$. On vérifie que les fonctions réalisées entre $i_0, i_1, \dots, i_{d-1}$ et $t$ sont toutes les fonctions semblables à $T_n^{K_d}$.

**2.5. THÉORÈME 3.** – Toute fonction booléenne symétrique croissante de $n$ variables peut être réalisée par un schéma ne contenant pas plus de

$$6 n^2 \left[ 1 + 0 \left( \frac{1}{\sqrt{n}} \right) \right] \text{ contacts.}$$

DÉMONSTRATION. – Soient $s$ et $t$ deux entiers premiers entre eux tels que $st \ge n+1$. Il résulte des propositions 4 et 5 que toute fonction symétrique croissante $F_n^p$ peut être réalisée à partir de 3 schémas (d, 1)-polaires fortement disjonctifs

- un schéma $S_1$ réalisant toutes les fonctions $T_n^{t,1}$, $0 \le i \le t-1$ qui ne contient pas plus de 2 tn contacts.

- deux schémas $S_2$ et $S_3$ réalisant respectivement les fonctions semblables à $T_n^{K_1}$ et à $T_n^{K_2}$ et qui ne contiennent pas plus de 2 sn contacts chacun.

Posons

$$s = ]\sqrt{n}[ \quad t = ]\sqrt{n}[- + 1$$

$s$ et $t$ sont premiers entre eux. Le nombre total de contacts du schéma obtenu n'est pas supérieur à
$$2 n(2 s + t) = 6 n^{\frac{3}{2}} \left[ 1 + O\left( \frac{1}{\sqrt{n}} \right) \right].$$

Remarque. – Lupanov a appliqué la même méthode aux fonctions symétriques quelconques et obtenu ainsi des résultats meilleurs que ceux obtenus antérieurement par Shannon [37 bis].
Références

[1] BECKENBACH (E. F.). - *Applied combinatorial mathematics*, John Wiley, New York (1964).

[2] BERGE (C.). - *Théorie des graphes et ses applications*, Dunod, Paris (1958).

[3] BIRKHOFF (C.). - Lattice theory, Amer. Math. Soc. Colloq. Publ., 25 (1961).

[4] BIRNBAUM (Z. W.), ESARY (J. D.) & SAUNDERS (S. C.). - Multicomponent systems and structures and their reliability, Technometrics, 3 (1961), 55-77.

[5] BLOKH (A.). - Synthèse de schémas de contacts (p. q.) polaires, Dokl. Akad. Nauk SSSR, 111/5 (1956), 1017-1019.

[6] CARVALLO (M.). - *Monographie des treillis et algèbre de Boole*, Gauthiers-Villars, Paris (1962).

[7] CHURCH (R.). - Numerical analysis of certain free distributive structures, Duke Math. J., 6 (1940), 732-734.

[8] CHURCH (R.). - Ennumeration by rank of the elements of the free distributive lattice with seven generators, Notice Amer. Math. Soc., 12/6 (1965), 732-734.

[9] DEDEKIND (R.). - *Über Zerlegungen von Zahlen durch ihre grossten gemeinsamen Teiler*, Festschrift Hoch Braunschweig, (1897), u. Ges. Werke, bd II, 103-148.

[10] DUBREUIL (P.) & DUBREUIL-JACOTIN (M. L.). - *Leçons d'algèbre moderne*, Dunod, Paris (1953).

[10bis] DUBREUIL-JACOTIN (M. L.), LESIEUR (L.) & CROISOT (A.). - *Leçons sur la théorie des treillis, des structures algébriques et ordonnées et des treillis géométriques*, Gauthier-Villars, Paris (1953).

[11] FELLER (W.). - *An introduction to probability theory and its applications*, John Wiley, New York, 1 (1958).
[12] GHOUILA-HOURI (A.). Flots et tensions dans un graphe, Ann. Sci. Ecole Norm. Sup., 81, 3ème série (1964), 267-339.

[13] GILBERT (E. N.). Lattice theoretic properties of frontal switching functions, J. Mathematical Phys., 33 (1954), 57-67.

[14] HAMMING (L.). Error detecting and error correcting codes, Bell. System tech. J., 29/1 (1950), 147-160.

[15] HANSEL (G.). Contribution à la théorie de la sécurité de fonctionnement, Thèse de 3ème cycle, Faculté des Sciences de Paris (1962).

[16] HANSEL (G.). Nombre minimal de contacts de fermeture nécessaires pour réaliser une fonction booléenne symétrique de n variables, C.R. Acad. Sci. Paris, 258 (1964), 6037-6040.

[17] HANSEL (G.). Nombre de lettres nécessaires pour écrire une fonction symétrique de n variables, C. R. Acad. Sci. Paris, 261 (1965), 4297-4300.

[18] HANSEL (G.). Résultats concernant le nombre minimal de contacts nécessaires pour réaliser certaines fonctions booléennes symétriques, C. R. Acad. Sci. Paris, 262 (1966), 679-681.

[19] HANSEL (G.). Sur le nombre de fonctions booléennes monotones de n variables, C. R. Acad. Sci. Paris, 262 (1966), 1088-1090.

[20] HANSEL (G.). Construction d'un schéma de contacts bipolaires réalisant une fonction booléenne isotone, C. R. Acad. Sci. Paris, 263 (1966), 651-654.

[21] KOROBKOV (B. K.). Réalisation d'une fonction symétrique, Dokl. Akad. Nauk SSSR, 109/2 (1956), 260-263.

[22] KOROBKOV (B. K.). Estimation du nombre des fonctions monotones de l'algèbre logique et complexité d'un algorithme trouvant un ensemble résolvant pour une fonction monotone arbitraire de l'algèbre logique, Dokl. Akad. Nauk SSSR, 150/4 (1963), 744-747.

[23] KOROBKOV (B. K.). Sur les fonctions monotones de l'algèbre logique, Problemy Kibernet., 13 (1964), 5-28.

[24] KRICHEVSKII (R.E.). Complexité d'un schéma de contacts réalisant une fonction de l'algèbre logique, Dokl. Akad. Nauk SSSR, 151/4 (1963), 803-806.

[25] KRICHEVSKII (R.E.). Sur la complexité de schémas de contacts en série et parallèle réalisant une suite de fonctions booléennes, Problemy Kibernet., 12 (1964), 46-55.
[26] KRICHEVSKII (R.E.).- Schémas minimaux de contacts fermants pour une fonction booléenne de n variables, *Diskret. Analyz.*, 5 (1965).

[27] KUNTZMANN (J.).- *Algèbre de Boole*, Dunod, Paris (1965).

[28] LUPANOV (O.B.).- Sur la comparaison des complexités des réalisations d'une fonction monotone par un schéma contenant seulement des contacts fermants et par un schéma quelconque, *Dokl. Akad. Nauk SSSR*, 144/6 (1962), 1245-1248.

[29] LUPANOV (O.B.).- Sur la synthèse de certaines classes de systèmes de commande, *Problemy Kibernet.*, 10 (1963), 63-97.

[30] LUPANOV (O.B.).- Sur une approche pour la synthèse des systèmes de commande - Principes de codage local, *Problemy Kibernet.*, 14 (1965), 31-110.

[31] NECHIPORUK (E.I.).- Sur les schémas de rectificateurs, Thèse de doctorat de la Faculté de Moscou, (1962).

[32] POVAROV (G.N.).- Sur la synthèse de schémas de contacts multipolaires, *Dokl. Akad. Nauk SSSR*, 94/6 (1954), 1075-78.

[33] POVAROV (G.N.).- Théorie mathématique de la synthèse de schémas de contacts (1 - K) polaires, *Dokl. Akad. Nauk SSSR*, 100/5 (1955), 909-912.

[34] REZNIK (B.).- Sur la réalisation des fonctions monotones par des schémas d'éléments fonctionnels, *Dokl. Akad. Nauk SSSR*, 139/3 (1961), 566-569.

[35] RIORDAN (J.) & SHANNON (C.).- On the number of series-parallel two terminal switching circuits, *J. Math. Phys.*, 21 (1942), 83-93.

[36] SESHU (S.) & REED (M.B.).- *Linear graphs and electrical networks*, Addison Wesley, London (1961).

[37] SHANNON (C.).- A symbolic analysis of relay and switching circuits, *Trans. ASMA Ser. B. J. Engrg. Indust.*, 57 (1938), 713-723.

[37 bis] SHANNON (C.).- The synthesis of two terminal switching circuits, *Bell System Tech. J.*, 28 (1949), 59-98.

[38] WHITNEY (H.).- Non separable and planar graphs, *Trans. Amer. Math. Soc.*, 34 (1932), 339-362.

[39] YAMAMOTO (K.).- Logarithmic order of free distributive lattice, *J. Math. Soc. Japan*, 6/3-4 (1954).
[40] KRUSKAL (J.). - *The number of simplices in a complex*, Mathematical Optimization Technics, Bellmann, (1963), 251-278.

[41] LUPANOV (O.B.). - Sur le problème de la réalisation des fonctions de l'algèbre logique par des schémas de contact, *Problemy Kibernet.*, **15** (1965), 86-99.
Table des matières

Pages

INTRODUCTION .................................... 163

1. RÉSULTATS CONCERNANT LE DÉNOMBREMENT DU TREILLIS DISTRIBUTIF LIBRE .................... 167

1.1. Notations, rappels .......................... 168

1.2. Partition de $B^n$ en chaines connexes ...... 178

1.3. Etude du nombre $|I_n|$ ...................... 182

2. IDENTIFICATION D'UNE FONCTION BOOLÉENNE CROISSANTE ........................................ 187

3. UNE INÉGALITÉ .................................. 193

4. LES SCHÉMAS DE CONTACTS - ÉTUDE GÉNÉRALE. 201

4.1. Rappels de théorie des graphes ............ 201

4.2. Schémas de contacts ........................ 203

4.3. Les schémas disjonctifs .................... 205

4.4. Opérations sur les schémas ($p_1, p_2$) polaires 209

4.5. Schémas de type série-parallèle ............ 211

4.6. Construction d'un arbre de décodage ........ 212

5. SCHÉMAS DE CONTACTSET FONCTIONS BOOLÉENNES CROISSANTES .................................... 219

5.1. Décompositions des fonctions booléennes ...... 220

5.2. Construction d'un schéma bipolaire pour une fonction $f \in I_n$ ......................... 223

5.3. Borne inférieure pour $E^+(n)$ .............. 230

6. SCHÉMAS DE CONTACTS DE TYPE SÉRIE-PARALLÈLE ........................................ 233

7. ÉTUDE DE LA FONCTION $F_n^2$ .................... 239

7.1. Réduction d'un schéma de la fonction $F_n^2$ .. 240

7.2. Recherche d'une borne inférieure pour $E_n^2$ .. 240
Pages

<table><tbody><tr><td>7.3. Recherche d'une borne supérieure pour E<sub>n</sub><sup>2</sup></td><td>250</td></tr><tr><td>7.4. Recherche de la valeur exacte de E<sub>n</sub><sup>2</sup></td><td>252</td></tr><tr><td>7.5. Extensions des résultats précédents</td><td>253</td></tr><tr><td>7.6. Caractérisation des schémas minimaux de F<sub>n</sub><sup>2</sup></td><td>254</td></tr><tr><td>8. ÉTUDE DE LA FONCTION S<sub>n</sub><sup>1</sup></td><td>259</td></tr><tr><td>8.1. La dualité dans les multigraphes et les schémas de contacts</td><td>259</td></tr><tr><td>8.2. Etude des fonctions S<sub>n</sub><sup>2</sup> et S<sub>n</sub><sup>2</sup></td><td>261</td></tr><tr><td>9. SCHÉMAS FONCTIONNELS ET FONCTIONS BOOLÉENNES CROISSANTES</td><td>267</td></tr><tr><td>9.1. Graphes fonctionnels</td><td>268</td></tr><tr><td>9.2. Schémas fonctionnels</td><td>270</td></tr><tr><td>9.3. Résultats auxiliaires</td><td>272</td></tr><tr><td>9.4. Construction d'un schéma fonctionnel par codage local</td><td>272</td></tr><tr><td>9.5. Construction d'un schéma fonctionnel réalisant une fonction croissante donnée f ∈ I<sub>n</sub> (borne supérieure de L<sup>*</sup>(n))</td><td>279</td></tr><tr><td>10. RÉSULTATS DE KRUSKAL ET LUPANOV</td><td>285</td></tr><tr><td>10.1. Résultats de KRUSKAL</td><td>285</td></tr><tr><td>10.2. Résultats de LUPANOV</td><td>290</td></tr><tr><td>RÉFÉRENCES</td><td>295</td></tr></tbody></table>