# Éléments de l'algèbre de Boole

M. J. Ville

► To cite this version:

M. J. Ville. Éléments de l'algèbre de Boole. Annales de l'ISUP, 1955, IV (2-3), pp.107-140. hal-04095236

HAL Id: hal-04095236

https://hal.science/hal-04095236

Submitted on 11 May 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
# ÉLÉMENTS DE L'ALGÈBRE DE BOOLE

par

M. J. VILLE
Professeur

## 1.- ALGÈBRE DES CLASSES

### 1.1.- INVERSES ET RECIPROQUES

Il est d'usage, au début des cours de Mathématiques, de donner quelques définitions concernant la structure des théorèmes. Il est entendu par exemple qu'un axiome est une vérité si évidente qu'on ne la démontre pas, qu'un postulat est une vérité indémontrable mais que l'on admet, qu'un théorème comporte une hypothèse et une conclusion. Ces quelques définitions suffisent à donner de la nature du raisonnement mathématique une idée suffisante pour que les élèves puissent faire les premiers pas; par la suite, ils apprennent à raisonner en raisonnant sur de nombreux cas particuliers. Il arrive cependant un moment de l'étude où il est nécessaire de se pencher de plus près sur la structure des raisonnements; il est impossible, sans ce faire, de comprendre le sens et la portée de la phrase : le Postulatum d'Euclide est indémontrable, qui ne signifie pas : Personne n'a réussi, faute d'habileté, à en trouver la démonstration, mais bien : On peut démontrer qu'il est indémontrable. Sans nous attacher à une question aussi délicate que celle du Postulatum d'Euclide, revenons à des questions élémentaires, telles que celles qui se posent lorsque l'on explique en quoi consiste une condition nécessaire et suffisante, ou encore, ce qui revient au même mais dans un autre langage, lorsque l'on parle de la réciproque d'un théorème. Rappelons qu'un théorème comporte une hypothèse, que nous pouvons représenter par la lettre H et une conclusion que nous pouvons représenter par la lettre C. L'énoncé du théorème consiste à dire : *si H est vraie, alors C l'est également. Cette relation entre H et C est appelée une implication* ; on peut l'exprimer encore en disant que H (hypothèse) implique C (conclusion).

Si on représente cette implication par le signe $H \rightarrow C$, on obtient le schéma suivant :

Hypothèse : H
Conclusion : C
Théorème : H $ightarrow$ C

Par exemple, le théorème : Toute fonction dérivable est continue, a pour hypothèse :

H : $f(x)$ admet une dérivée $f'(x)$

et pour conclusion :

C : $f(x)$ est continue
Si le théorème $H \rightarrow C$ est vrai, $H$ constitue une condition suffisante de $C$, et $C$ constitue une condition nécessaire de $H$. Dans l'exemple ci-dessus, le théorème indique que pour démontrer la continuité d'une fonction, il suffit de démontrer sa dérivabilité; de même, si on veut montrer qu'une fonction est dérivable, il est bon de s'assurer qu'elle est continue, parce que si elle ne l'est pas, elle ne peut être dérivable. Portons notre attention sur la dernière phrase, qui peut se dire également :

Toute fonction non continue est non dérivable.

On peut la considérer comme un théorème, ayant pour hypothèse la négation de la conclusion du théorème primitif; nous noterons cette négation par $\bar{C}$. Quant à la conclusion, c'est la négation, que nous noterons $\bar{H}$, de l'hypothèse primitive. Nous sommes en présence de deux théorèmes que nous notons :

$$ \begin{array}{rcl} H & \rightarrow & C \\ \bar{C} & \rightarrow & \bar{H} \end{array} $$

Ces deux théorèmes n'en font en réalité qu'un seul. C'est ce qu'on exprime lorsque l'on dit qu'un théorème quelconque et l'inverse de sa réciproque sont équivalents. Ouvrons ici une parenthèse pour rappeler les significations des expressions "inversement" et "réciproquement", qui sont tout à fait distinctes. L'inverse du théorème $H \rightarrow C$ est le théorème $\bar{H} \rightarrow \bar{C}$ qui s'obtient en substituant à l'hypothèse et à la conclusion leurs négations. Le réciproque du théorème $H \rightarrow C$ est le théorème $\bar{C} \rightarrow \bar{H}$ obtenu en échangeant les rôles de l'hypothèse et de la conclusion. On peut donc associer à chaque théorème trois autres théorèmes, par les opérations d'inversion et de réciprocation, ce qui fournit le tableau :

<table><tr><td>1.</td><td>Théorème direct</td><td>: H &rarr; C</td></tr><tr><td>2.</td><td>" inverse</td><td>: H &rarr; C</td></tr><tr><td>3.</td><td>" réciproque</td><td>: C &rarr; H</td></tr><tr><td>4.</td><td>" inverse de la réciproque</td><td>: C &rarr; H</td></tr></table>

L'examen de ce tableau montre qu'il ne contient en réalité que deux théorèmes distincts. Nous avons vu en effet que les théorèmes figurant dans le tableau sous les numéros 1 et 4 ne sont pas distincts. On remarque alors que le théorème n° 2 se déduit du théorème n° 3 exactement comme le théorème n° 4 se déduit du théorème n° 1. Donc 2 et 3 bien que d'énoncés distincts, ont la même signification. Le théorème inverse et le théorème réciproque sont donc ensemble tous deux vrais ou tous deux faux. Cette concordance, que le lecteur pourra vérifier sur les exemples simples qu'il imaginera lui-même, explique pourquoi la distinction entre "inversement" qui concerne le théorème inverse, et "réciproquement" qui concerne le théorème réciproque, est si souvent méconnue. On peut se demander alors s'il y a lieu de maintenir cette distinction puisqu'on vérifie qu'elle n'a pas d'importance quand on en vient à la signification du théorème; nous allons voir que la distinction a une portée qui va plus loin qu'une simple nuance de construction grammaticale. Quand nous disons qu'il revient au même de considérer le théorème direct

$$ \begin{array}{rcl} H & \rightarrow & C \\ \bar{C} & \rightarrow & \bar{H} \end{array} $$

ou l'inverse de la réciproque

nous ne faisons autre chose que légitimer la démonstration par l'absurde. En effet, démontrer directement le théorème $\bar{C} \rightarrow \bar{H}$ n'est autre que démontrer par l'absurde $H \rightarrow C$. Si donc, on ne s'intéresse pas à la forme des démonstrations, "inversement" et "réciproquement" peuvent être considérés comme synonymes; si au contraire on étudie la manière dont on conduit
la démonstration, la distinction devient importante; elle devient naturellement capitale aux yeux des mathématiciens qui n'admettent pas la légitimité de la démonstration par l'absurde*, pour lesquels par conséquent les présentes considérations sont entachées de suspicion. Ces restrictions faites, revenons aux deux expressions :

$$H \to C \qquad \bar{C} \to \bar{H}$$

que nous considérons comme équivalentes. La seconde se déduit en soulignant les lettres, et les échangeant. Cette opération nous rappelle celle par laquelle on passe en algèbre de l'inégalité

$$a > b$$

$$\text{à l'inégalité} \qquad -b > -a$$

ce qui nous donne à penser que l'on peut définir des règles d'opération sur des symboles tels que H, C, représentant des propositions, et les signes `→`, `-`, représentant l'implication et la négation, permettant de passer d'un énoncé à un autre sans avoir à s'occuper de la signification des lettres, de même que dans la suite des transformations algébriques intervenant dans la solution d'un problème, on n'a pas besoin d'avoir constamment présente à l'esprit la signification des lettres sur lesquelles on opère. L'algèbre qui opère sur des symboles tels que H, C, existe effectivement; elle consiste à mettre en signes les règles de raisonnement d'Aristote. La création de cette algèbre est dûe aux efforts successifs de Leibnitz, Morgan, Boole; ce dernier l'ayant portée à la perfection convenant aux applications, cette algèbre est maintenant universellement désignée du nom de Boole.

## 1.2. - INTERPRETATION, A L'AIDE DE CLASSES, D'UN ENONCE DE THEOREME.

Suivant les règles d'Aristote, un énoncé tel que "toute fonction dérivable est continue" n'a de sens que si on la considère comme liant les éléments suivants :

1. La classe des fonctions

2. La classe des fonctions continues

3. La classe des fonctions dérivables

On peut donner une représentation graphique de ces trois classes et de leurs relations respectives de la manière suivante : on représente une fonction par un point appartenant à un carré T, lequel représente la classe des fonctions. Parmi les points du carré T, il en existe qui représentent des fonctions continues. Le domaine contenant ces points est représenté sous forme d'un cercle C; parmi les points de C, il en est qui représentent des fonctions dérivables; le domaine contenant ces points est représenté sous forme d'un cercle H, intérieur au cercle C.

La relation

$$H \to C$$

est représentée graphiquement par le fait que H est intérieur à C.

Considérons maintenant les domaines $\bar{H}$ et $\bar{C}_{\text{extérieurs}}$ aux cercles H et C. Nous voyons que $\bar{C}$ est contenu dans $\bar{H}$, ce qui concorde avec l'expression : $\bar{C} \to \bar{H}$

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

<footnote>* Il s'agit des mathématiciens appartenant à l'école dite Intuitioniste, dont le chef de file est le mathématicien hollandais BROUWER, de l'Université d'Amsterdam.</footnote>
D'une manière générale, soit dans une totalité $T$ d'éléments quelconques une classe $A$ comprenant certains de ces éléments, conformément à la figure 2. Cette classe $A$ est constituée par les éléments de $T$ qui possèdent une certaine propriété caractéristique. Ceux des éléments de $T$ qui ne possèdent pas cette propriété forment une classe $\bar{A}$.

Si $A$ comprend tous les éléments de $T$, $\bar{A}$ est vide. Nous écrivons alors :

$$A = T$$

$$\bar{A} = N$$

Si $A$ était vide, ce serait $\bar{A}$ qui serait identique à $T$. Nous écririons alors :

$$\bar{A} = T$$

$$A = N$$

$N$ est une classe fictive, le néant, à laquelle on égale une classe lorsqu'on veut exprimer qu'elle est vide.

<figure><img src="image_3.png" /><figcaption>fig.2</figcaption></figure>

Considérons maintenant deux classes $A$ et $B$, dont les éléments appartiennent à $T$. En général les éléments de $T$ se partagent en quatre classes, à savoir ceux qui appartiennent :

1) - à $A$ et $B$

2) - à $A$ et $\bar{B}$

3) - à $\bar{A}$ et $B$

4) - à $\bar{A}$ et $\bar{B}$

Ces quatre classes sont disjointes, c'est à dire qu'un élément quelconque de $T$ ne peut pas appartenir à la fois à deux d'entre elles. Les quatre classes considérées sont représentées sur la figure 3.

### 1. 3. - OPERATIONS ELEMENTAIRES SUR LES CLASSES.

Convenons de représenter par $A.B$ les éléments qui appartiennent à la fois à $A$ et $B$. les quatre classes considérées peuvent alors se noter, dans l'ordre :

$A.B, A.\bar{B}, \bar{A}.B, \bar{A}.\bar{B}$.

Le point (.) représente l'opération d'*intersection*. Si on considère 3 classes $A,B,C$, on peut former leur intersection.

On remarque que l'on peut écrire cette expression :

$(A. B) . C$ ou encore

$(A. C) . B$

<figure><img src="image_4.png" /><figcaption>fig.3</figcaption></figure>

sans changer de signification. Il revient en effet au même, soit de considérer les points communs à $A$ et $B$, lesquels forment une classe $D$, et de chercher ensuite les points communs à $D$ et à $C$, ou de commencer par chercher les points communs à $A$ et $C$, et de prendre ensuite l'intersection avec $B$ de la classe ainsi formée. Il est donc inutile, lorsque l'on forme l'intersection de plusieurs classes, de préciser l'ordre dans lequel on forme l'intersection; s'il s'agit de trois classes, les 6 expressions

$A.B.C., A.C.B, B.C.A, B.A.C, C.A.B, C.B.A$

ont exactement la même signification. On peut également grouper deux ou plusieurs classes et les remplacer par leur intersection, ce qui s'exprime
par exemple par :

$$A.B.C.D = A.(B.C).D$$

On résume les considérations ci-dessus en disant que l'intersection est *commutative* et *associative*.

A côté de l'intersection, il est naturel de considérer la réunion de plusieurs classes. Représentons par $A + B$ la classe formée par les éléments qui appartiennent à $A$ ou $B$; cette classe $A + B$ sera appelée *réunion* de $A$ et de $B$. On peut définir la réunion de plusieurs classes, soit, pour trois classes

$$A + B + C$$

La réunion jouit des mêmes propriétés d'associativité et de commutativité que l'intersection.

## 1. 4. - RELATION D'INCLUSION ENTRE DEUX CLASSES.

Revenons maintenant à la relation entre classes A et B qui exprime que la propriété caractérisant les éléments de A implique que tout élément de A appartient à B, ce que nous pouvons écrire :

$$(1) \quad A \to B$$

Cette relation entre classes peut s'exprimer d'une autre façon. On voit que si $A$ est contenu dans $B$, $AB$ se confond avec $A$, d'où l'égalité :

$$(2) \quad A.B = A$$

Réciproquement (2) entraine (1). Donc (1) et (2) sont deux façons d'écrire la même chose, ce qui nous montre que le signe $\to$ n'est pas indispensable si on admet l'usage des signes $\cdot$ et $=$.

On peut exprimer (1) encore d'une autre manière. Si $A$ est contenu dans $B$, la réunion de $B$ et $A$ est encore $B$, d'où :

$$(3) \quad A + B = B$$

On voit facilement que (1), (2), (3) sont équivalentes, ce qui montre que le signe $\to$ n'est pas indispensable si on admet l'usage des signes $\cdot$ et $=$.

Il existe encore d'autres manières d'exprimer (1), en exprimant que certaine classe est égale à $T$ ou à $N$. Si en effet $A$ est contenu dans $B$, tout point de $T$ appartient soit à $B$, soit à $\bar{A}$. D'où :

$$(4) \quad B + \bar{A} = T$$

Enfin, si $A$ est contenu dans $B$, il n'existe aucun point qui soit contenu à la fois dans $A$ et dans $\bar{B}$, d'où :

$$(5) \quad A.B = N$$

## 1. 5. - RELATIONS ENTRE OPERATIONS ELEMENTAIRES.

Nous avons été en présence de 5 manières différentes d'exprimer la même situation. Nous allons chercher s'il est possible de passer de l'une à l'autre des expressions 2, 3, 4, 5; l'expression (1) restant à part parce que ne contenant pas de signe d'égalité. Nous allons pour ce faire étudier les propriétés des opérations d'union et d'intersection, combinées entre elles et avec l'opération de négation qui consiste à substituer $\bar{A}$ à $A$.

En ce qui concerne la négation, nous voyons tout de suite que la double
négation de $A$ ramène à $A$ :

$$ (6) \quad \overline{A} = A $$

Si nous cherchons à combiner l'union et la négation, nous voyons qu'en général :

$$ \overline{A + B} \neq \overline{A} + \overline{B} $$

On peut même donner pour $\overline{A + B}$ une expression qui montre que la négation n'est pas distributive par rapport à l'addition. Un point qui n'est pas dans $A + B$ n'est ni dans $A$ ni dans $B$. Il se trouve donc à la fois dans $\overline{A}$ et $\overline{B}$, d'où :

$$ (7) \quad \overline{A + B} = \overline{A} \cdot \overline{B} $$

Si nous remarquons que les égalités

$$ A = B $$

$$ \overline{A} = \overline{B} $$

sont équivalentes, ce qui revient à dire que l'on peut nier les deux membres d'une égalité sans que cette égalité cesse d'être vraie, nous déduisons, en niant les deux membres de (7) et tenant compte de (6) :

$$ A + B = \overline{A} \cdot \overline{B} $$

ou encore, en remplaçant $A$ par $\overline{A}$ et $B$ par $\overline{B}$ :

$$ (8) \quad \overline{A} \cdot \overline{B} = \overline{A} + \overline{B} $$

La comparaison de (7) et (8) montre la dualité entre l'union et l'intersection.

La négation d'une union est l'intersection des négations des termes de l'union.

La négation d'une intersection est l'union des négations des termes de l'intersection.

Ces règles sont connues sous le nom de règle de Morgan.

Si on remarque :

$$ N = \overline{T} $$

$$ T = \overline{N} $$

nous voyons que (4) et (5) se déduisent l'une de l'autre en niant les deux termes. Par exemple, à partir de (4), nous obtenons successivement :

$$ B + \overline{A} = T \quad \overline{B} + \overline{A} = \overline{T} \quad A \cdot \overline{B} = N $$

En combinant les opérations d'union et d'intersection, on obtient l'égalité :

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

facile à vérifier, exprimant que l'intersection est distributive par rapport à l'union. La relation (9) est tout à fait identique à celle utilisée en algèbre ordinaire. Dans le symbolisme que nous sommes en train d'étudier, on peut dans (9) échanger le rôle de l'union et de l'intersection, ce qui conduit à :

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

qui exprime que l'union est distributive par rapport à l'intersection. L'égalité (10) peut se vérifier directement; on peut également la déduire de (9). Ecrivons (9) en remplaçant chaque classe par sa négation, ce qui conduit à :

$$ (11) \quad (\overline{A} + \overline{B}) \cdot \overline{C} = (\overline{A} \cdot \overline{C}) + (\overline{B} \cdot \overline{C}) $$

Cela est légitime, puisque l'égalité (9) est supposée vraie quelles que soient les classes, $A, B, C$. Nions les deux membres de (11). Nous obtenons :

$$ \overline{A} + \overline{B} + C = (\overline{A} \cdot \overline{C}) \cdot (\overline{B} \cdot \overline{C}) $$
ou encore

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

ce qui est bien la relation (10).

## 1. 6 - RESUME DES REGLES D'OPERATIONS SUR CLASSES.

Résumons les relations que nous avons obtenues :

Nous avons défini des opérations + (union) et · (intersection) entre des classes. Ces opérations satisfont à :

$$ A + B = B + A \qquad A \cdot B = B \cdot A $$

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

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

Il existe deux classes particulières, T (totalité) et N (néant) telles que :

$$ (13) \quad A + T = T \qquad A + N = A $$

$$ A \cdot T = A \qquad A \cdot N = N $$

Il existe une opération, dite négation, qui associe à chaque classe A une classe $\bar{A}$ telle que :

$$ (14) \quad A + \bar{A} = T $$

$$ A \cdot \bar{A} = N $$

La négation d'une union et la négation d'une intersection satisfont à

$$ (15) \quad \overline{A+B} = \overline{A} \cdot \overline{B} \qquad A \cdot B = \overline{A+B} $$

Enfin les deux égalités

$$ (16) \quad A = B \qquad A = \bar{B} $$

sont équivalentes.

Les règles (12), (13), (14), (15), (16), que l'on peut vérifier sur des exemples, d'après la définition intuitive des opérations +, ·, -, ne sont pas indépendantes. L'application de la règle (16) permet, comme nous l'avons vu, de passer de l'une à l'autre des égalités (14) voir [7] et (8). Elle permet également de passer de l'une à l'autre des colonnes dans lesquelles sont rangées les relations (12). Elle permet enfin de passer de l'une à l'autre des lignes (13). Enfin, appliquée à (14), elle montre que $\overline{T} = N$.

## 1. 7. - QUELQUES PROBLEMES SUR L'ALGÈBRE DES CLASSES.

Nous ne chercherons pas ici à savoir quel est le nombre minimum des règles (12-16) suffisantes pour en déduire les autres, renvoyant pour cela aux ouvrages spécialisés. Nous les utiliserons de la manière qui semblera la plus commode, et commencerons par quelques problèmes simples.

**Problème I.** - Démontrer l'inégalité : $\overline{\overline{A}} = A$

Nous commencerons par résoudre le système :

$$ (17) \quad A + X = T $$

$$ A \cdot X = N $$

Ce système admet une solution unique. S'il admettait deux solutions
X et Y, nous aurions :

$$ (18) \quad A + Y = T $$

$$ A \cdot Y = N $$

Multiplions la première équation (17) par Y. Nous obtenons :

$$ A \cdot Y + X \cdot Y = T \cdot Y $$

d'où, d'après (18) et (13)

$$ N + X \cdot Y = Y $$

$$ (19) \quad X \cdot Y = Y $$

Si nous multiplions la première équation (18) par X, nous sommes
amenés de même à :

$$ (20) \quad X \cdot Y = X $$

d'où l'égalité de X et Y.

Nous savions, d'après (14), que (17) admet la solution $\overline{A}$. Nous savons maintenant qu'elle est unique. Considérons maintenant $\overline{A}$, qui est par définition la solution en Z de :

$$ \overline{A} + Z = T $$

$$ \overline{A} \cdot Z = N $$

Cette solution est unique. Or A est solution. Donc $\overline{A} = A$.

**Problème II.** - Démontrer que $A + A = A$.

Comme dans le problème I, nous allons procéder par le calcul. Nous allons chercher à montrer que la négation de $A + A$ est $\overline{A}$; comme une classe n'admet qu'une seule négation, d'après ce qui a été vu dans la solution du problème I, il en résultera bien que $A + A = A$.

Pour que $A + A$ ait pour négation $\overline{A}$, il faudrait que

$$ A + A + \overline{A} = T $$

$$ (A + A) \cdot \overline{A} = N $$

Calculons donc les membres de gauche. Nous avons, par application de (14), puis de (13) :

$$ A + A + \overline{A} = A + (A + \overline{A}) = A + T = T $$

En ce qui concerne $(A + A) \cdot \overline{A}$, nous développons le produit, ce qui nous donne

$$ (A + A) \cdot \overline{A} = A \cdot \overline{A} + A \cdot \overline{A} = N + N $$

et enfin, par application de (13) (où nous faisons $A = N$)

$$ N + N = N $$

Il est bien montré que $\overline{A}$ est la négation de $A + A$, d'où :

$$ \overline{A} + \overline{A} = \overline{A} $$

$$ (21) \quad A + A \leq A $$

On remarquera qu'en niant les deux membres de :

$$ \overline{A} + \overline{A} = \overline{A} $$

on obtient une relation, analogue à celle que l'on demandait de démontrer, à savoir :

$$ (22) \quad A \cdot A = A $$

**Problème III.** - On a vu que les deux égalités

$$ (23) \quad A = A \cdot B $$

$$ B = A + B $$
étaient équivalentes. Peut-on le montrer par le calcul ? Ajoutons B aux deux membres de la première. Nous obtenons :

$$A + B = A \cdot B + B$$

Nous pouvons remplacer, dans le second membre, B par

$$B \cdot T = B \cdot (A + \bar{A}) = A \cdot B + \bar{A} \cdot B$$

ce qui nous conduit à

$$A+B = A \cdot B + A \cdot B + \bar{A} \cdot B = A \cdot B + \bar{A} \cdot B = (A+\bar{A}) \cdot B = B \cdot T = B$$

Pour déduire la première égalité de la seconde, il suffit de multiplier les deux membres de la seconde par A, ce qui donne :

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

Les problèmes résolus ci-dessus montrent le parti que l'on peut tirer du calcul des classes. Nous n'avons pas encore étudié complètement la relation

$$A \to B$$

Nous mettons cette étude à part, parce que, étant données A et B, les expressions $\bar{A}$, $A+B$, $A \cdot B$ représentent des classes, mais l'expression $A \to B$ ne représente pas une classe, mais bien une relation entre classes, ou si l'on veut, une équation à laquelle satisfait A et B. Nous avons vu que l'on pouvait mettre cette relation sous l'une des formes

$$A = A \cdot B$$

$$B = A + B$$

Deux autres formes intéressantes sont :

$$ (24) \quad \bar{A} + B = T $$

$$ (25) \quad A \cdot \bar{B} = N $$

la plus intéressante des deux étant la seconde, qui se présente d'une façon analogue aux équations de l'algèbre, $f(x, y) = 0$, puisque $A \cdot \bar{B}$ est une fonction de A et B, et que N joue un rôle tout à fait comparable à celui du zéro. Pour montrer que (24) et (25) sont équivalentes à $A \to B$, remarquons tout d'abord qu'elles sont équivalentes entre elles; en effet, la seconde s'obtient en niant les deux membres de la première, et réciproquement. Si maintenant nous multiplions les deux membres de (24) par A, nous obtenons :

$$N + A \cdot B = A \cdot T$$

c'est à dire $A \cdot B = A$

ou encore $A \to B$

Supposons maintenant que $A \cdot B = A$. Nous en déduisons :

$$\bar{A} + B = \bar{A} + B \cdot T = \bar{A} + B(A + \bar{A}) = \bar{A} + A + \bar{A} \cdot B = T + \bar{A} \cdot B = T$$

c'est à dire (24). Nous constatons bien l'équivalence de (24), ou (25) avec

$$A \to B$$

Si nous réservons le signe $\neq$ à des égalités entre classes et si nous employons le signe $\equiv$ pour lier des relations entre classes, qui ont même signification, nous obtenons par exemple :

$$ (A \to B) \equiv (\bar{A} + B = T) \equiv (A \cdot \bar{B} = N) $$

A côté des opérations fondamentales -, ., +, on introduit souvent l'opération
représentée par C, définie par

$$ (26) \quad A \subset B = \bar{A} + \bar{B} $$

A ⊂ B est une classe, au contraire de A—→ B qui est une relation entre classes. On voit que par définition on a l'équivalence :

$$ (27) \quad \{ (A \subset . B) = T \} \equiv A \rightarrow B $$

Nous allons établir, à titre d'exercice, une proposition importante concernant cette opération $\subset$.

**Problème IV.** - On considère trois classes quelconques A, B, C. Quelle est la classe définie par la formule :

$$ (28) \quad [(A \subset B) \cdot (B \subset C)] \subset (A \subset C) $$

Nous nous reporterons à la définition (26); nous obtenons

$$ (A \subset B) \cdot (B \subset C) = (\bar{A} + \bar{B}) \cdot (\bar{B} + \bar{C}) = \bar{A} \cdot \bar{B} + \bar{A} \cdot C + B \cdot C $$
en négligeant d'écrire le terme en B. $\bar{B}$, qui est égal à N.

L'expression à calculer s'écrit alors :

$$ \begin{aligned} \bar{A} \cdot \bar{B} + \bar{A} \cdot C + B \cdot \bar{C} + \bar{A} + C &= (\bar{A} \cdot \bar{B}) \cdot (\bar{A} \cdot \bar{C}) \cdot (\bar{B} \cdot \bar{C}) + \bar{A} + C \\ &= (A + B) \cdot (A + \bar{C}) (\bar{B} + \bar{C}) + A + C \end{aligned} $$

Nous développons les deux premières parenthèses :

$$ (A + B) (A + \bar{C}) = A + A \cdot \bar{C} + A \cdot B + B \cdot \bar{C} = A + B \cdot \bar{C} $$

Nous avons utilisé, pour simplifier le résultat, le fait que, quel que soit X

$$ A + A \cdot X = A \cdot T + A \cdot X = A \cdot (T + X) = A \cdot T = A $$

Multiplions par la troisième parenthèse. Il nous revient :

$$ A \cdot \bar{B} + B \cdot \bar{C} \cdot \bar{B} + A \cdot \bar{C} + B \cdot \bar{C} = A \cdot \bar{B} + A \cdot \bar{C} + B \cdot \bar{C} $$

L'expression à calculer devient ainsi :

$$ (29) \quad A \cdot \bar{B} + A \cdot \bar{C} + B \cdot \bar{C} + \bar{A} + C $$

Sous cette forme, cette expression est assez difficile à interpréter. Calculons sa négation. Nous obtenons :

$$ (\bar{A} + B) (\bar{A} + C) (\bar{B} + C) A \cdot \bar{C} $$

Le produit par A de la première parenthèse est A B. Le produit de AB par la deuxième parenthèse est ABC. Le produit de ABC par C est N.

Donc l'expression (29) est égale à T. Nous obtenons ainsi :

$$ (30) \quad \{ [(A \subset B) \cdot (B \subset C)] (A \subset C) \} = T $$

et cela, **quelles que soient** les classes A, B, C.

Pour calculer (29), nous sommes passés à la négation, parce que les simplifications y sont presque automatiques; nous aurions pu opérer directement, en observant que puisque :

$$ \bar{A} = \bar{A} + \bar{A} \cdot \bar{C} $$

nous pouvons ajouter $\bar{A} \cdot \bar{C}$ à (29). Nous observons alors l'existence dans (29) des termes

$$ A \cdot \bar{C} + \bar{A} \cdot \bar{C} + C = (A + \bar{A}) \cdot \bar{C} + C = \bar{C} + C = T $$

ce qui suffit pour montrer que (29) a pour valeur T.

Le résultat obtenu est intéressant, parce qu'il montre que certaines
expressions en A, B, C, ... ne dépendent pas en réalité des classes A, B, C, ... bien que cela ne soit pas évident à première vue. Il est également intéressant si on revient à l'équivalence

$$ (A \rightarrow B) \equiv \{ (A \subset B) = T \} $$

Nous allons montrer que l'égalité (30) est en relation étroite avec la proposition

$$ \text{Si } A \rightarrow B \text{ et } B \rightarrow C, \text{ alors } A \rightarrow C $$

ce qui signifie simplement que si A est contenu dans B et B dans C, alors A est contenu dans C. Ceci peut s'écrire, en utilisant le signe $\Rightarrow$ pour lier par "et" deux relations entre classes, et le signe $\Rightarrow$ pour indiquer qu'une relation entre classes entraine une autre relation :

$$ (31) \quad (A \rightarrow B) \& (B \rightarrow C) \Rightarrow (A \rightarrow C) $$

On remarquera l'analogie formelle entre (28) et (31), bien que la signification soit différente, puisque dans (31) il s'agit de relations entre "relations entre classes", tandis qu'en (28) il s'agit seulement d'une classe formée à partir de A, B, C par des opérations $+$, $-$, $\langle$ opération $\rangle$ étant une opération auxiliaire). Cette analogie formelle explique pourquoi on peut déduire (31) de (30). (30) est une égalité vraie quelles que soient A, B, C. Supposons maintenant que $A \rightarrow B$ et $B \rightarrow C$. Puisque $A \rightarrow B$, nous avons $(A \subset C) = T$.

Puisque $B \rightarrow C$, nous avons $(B \subset C) = T$. Donc, le crochet qui figure au premier membre de $(30)$ est $T$. $T = T$. Nous obtenons ainsi

$$ \{ T \subset (A \subset C) \} = T $$

ce qui signifie que

$$ T \rightarrow (A \subset C) $$

La classe $A \subset C$ ne peut contenir $T$ que si elle est elle-même égale à $T$. Donc

$$ (A \subset C) = T $$

ce qui signifie que $A \rightarrow C$. Nous constatons que (31) est bien une conséquence de (30). Comme nous n'avons pas pour but principal de faire de la logique formelle, nous nous en tiendrons là pour la comparaison entre (30) et (31). nous allons plutôt maintenant nous occuper de techniques de calcul. Le passage de (28) à (29) est assez aisé; mais le calcul de (29) peut sembler artificiel. Il serait regrettable que pour montrer que deux expressions en A, B, C, ..., $\bar{A}$, $\bar{B}$, $\bar{C}$, ..., écrites sous des aspects différents, sont en réalité identiques, on ne puisse sefier qu'à la plus ou moins grande habileté avec laquelle on fait des groupements de termes. Nous allons voir qu'il n'en est pas ainsi, et que l'on peut donner pour les expressions en A, B, C, ... de 3 formes canoniques, telles que si deux expressions, quoique de formes primitives différentes, sont équivalentes, elles se ramènent toujours à des formes canoniques identiques. Nous expliquerons la formation de ces formes sur le cas de 3 classes A, B, C, la généralisation étant évidente.

## 1.8. FORMES CANONIQUES D'UNE EXPRESSION DEPENDANT DE PLUSIEURS CLASSES.

Considérons le cas où les classes figurant dans une expression sont au nombre de trois, soient les classes A, B, C. Les classes A, B, C partagent la classe T en $2^3 = 8$ classes

A.B.C. A.B.Č A.B.C. A.B.Č. A.B.C. A.B.Č A.B.C A.B.Č
que nous appellerons $K_1, K_2, ..., K_8$. Considérons les classes de la forme

$$ (1) \quad \sum_{i=1}^{8} \varepsilon_i K_i \qquad (\varepsilon_i = 0,1) $$

le signe `=` représentant l'union des classes sous le signe `Σ`, étant entendu que l'on ne conserve que les classes pour lesquelles $\varepsilon_i = 1$. Si par exemple la suite des $\varepsilon_i$ est

1 0 0 1 0 1 1 0

nous obtenons la classe :

A.B.C + A.Б.С + А.В.С + А.Б.С

Les expressions de la forme (1) sont dites formes canoniques disjunctives, comme se présentant sous la forme d'une union de classes disjointes (sans points communs). Il nous faut montrer que toute expression F (A, B, C) formée à partir des classes A, B, C par l'utilisation des signes `+`, `.`, `-` peut se mettre sous la forme (1).

Remarquons que si $F_1$ et $F_2$ sont deux expressions que l'on sait mettre sous forme canonique

$$ F_1 = \Sigma \varepsilon_i K_i $$

$$ F_2 = \Sigma \varepsilon_i' K_i $$

$F_1 + F_2$ se mettra sous forme canonique

$$ (2) \quad F_1 + F_2 = \Sigma (\varepsilon_i + \varepsilon_i' - \varepsilon_i \varepsilon_i') K_i = \Sigma \varepsilon_i'' K_i $$

En effet, $F_1 + F_2$ s'obtient en faisant l'union de tous les $K_i$ figurant dans l'une `ou` l'autre des formes $F_1, F_2$, c'est à dire que $\varepsilon_i''$ ne doit être nul que si $\varepsilon_i \notin \varepsilon_i'$ sont tous deux nuls; si l'un `ou` l'autre des termes $\varepsilon_i, \varepsilon_i'$ est égal à un, $\varepsilon_i''$ doit être égal à un; c'est bien le cas pour la forme

$$ \varepsilon_i'' = \varepsilon_i + \varepsilon_i' - \varepsilon_i \varepsilon_i' $$

Nous aurions de même

$$ (3) \quad F_1 F_2 = \Sigma \varepsilon_i \varepsilon_i' K_i $$

puisque seules figurent dans $F_1, F_2$ les $K_i$ pour lesquels on a à la fois $\varepsilon_i = \varepsilon_i' = 1$. Enfin nous aurons :

$$ F_1 = (1 - \varepsilon_i) K_i $$

Nous voyons donc que si des expressions quelconques sont données sous forme canonique, nous pouvons mettre sous forme canonique les expressions qui s'en déduisent par les opérations `+`, `.` `-`. Il reste à montrer simplement que A, B, C elles-mêmes peuvent se mettre sous forme canonique. Cela est immédiat, puisque

$$ A = A.B.C + A.B.C + A.B.C + A.B.C + A.B.C $$

$$ B = A.B.C + A.B.C + A.B.C + A.B.C + A.B.C $$

$$ C = A.B.C + A.B.C + A.B.C + A.B.C + A.B.C $$

Une remarque est cependant nécessaire. dans le cas où la suite des $\varepsilon_i$ serait :

O O O O O O O O

comme nous convenons de ne pas écrire les classes $K_i$ pour lesquelles $\varepsilon_i = 0$, il ne nous reste rien à écrire. Donc à proprement parler, une expression de la forme F (A, B, C) qui toutes réductions faites se ramène à N, ne peut
pas se mettre sous forme canonique disjonctive. Au contraire, une expression qui se réduit à T peut se mettre sous forme canonique, à savoir la somme des huit classes A, B, C, ..., $\overline{A}$, $\overline{B}$, $\overline{C}$.

Il est évident que la forme canonique disjonctive est unique, nous avons
donc un moyen sûr pour savoir si deux expressions F (A, B, C), G (A, B, C)
sont ou non identiques bien que primitivement d'aspect différent.

Il existe une autre forme canonique, dite conjonctive, d'un usage moins
courant. Considérons les classes :

$$
(4) \quad A+B+C \qquad A+B+\overline{C} \qquad A+\overline{B}+C \qquad A+\overline{B}+\overline{C} \\
\phantom{(4) \quad} A+\overline{B}+C \qquad A+B+\overline{C} \qquad A+B+\overline{B}+C \qquad A+\overline{B}+\overline{C}
$$

Toute expression en A, B, C peut se mettre sous la forme d'une intersection
de classes de la forme ci-dessus. Soit en effet F une pareille expression.
Mettons $\overline{F}$ sous forme disjonctive, soit

$$
\overline{F} = K_1 + K_2 + K_3
$$

nous en déduisons

$$
F = K_1 . K_2 . K_3
$$

$\overline{K_1}$, $\overline{K_2}$, $\overline{K_3}$ étant de la forme (3). En effet, les termes de la suite (4) ne sont autres que les négations des termes employés dans la forme disjonctive. On marquera qu'en ce qui concerne la forme conjonctive, c'est T qui représente le cas d'exception, tandis que N peut s'exprimer :

$$
N = \overline{K_1} \cdot \overline{K_2} \cdot \overline{K_3} \dots \overline{K_8}
$$

1. 9. - NOMBRE DE FONCTIONS DISTINCTES DEPENDANT DE n CLASSES.

Une expression telle que F (A₁, A₂, ..., Aₙ) formée à partir des classes
A₁, A₂, Aₙ par les opérations +, -, s'appelle une fonction booléienne des
classes A₁, A₂, Aₙ. La considération des formes canoniques permet d'évaluer
le nombre de fonctions booléennes distinctes que l'on peut former, fonctions
de n classes. Considérons le cas simple où n = 2, et soient A et B les deux
classes dont on cherche à former une fonction. Les termes de la forme
canonique sont ici au nombre de 4 :

$$
A \cdot B \quad A \cdot \overline{B} \quad \overline{A} \cdot B \quad \overline{A} \cdot \overline{B}
$$

Dans la forme canonique, chacun de ces termes peut figurer ou non, ce
qui nous donne $2^4 = 16$ possibilités. Il y a donc 16 fonctions distinctes de A
et B. Mais nous notons que parmi ces fonctions, il y en a 2, à savoir T et
N, obtenues en prenant 4 ou 0 termes, qui ne dépendent pas de A et B. Il y
en a 4 qui ne dépendent que de A ou de B, à savoir A, $\overline{A}$, B, $\overline{B}$. Par exemple
A s'obtient par le choix

$$
A = A \cdot B + A \cdot \overline{B}
$$

Il nous reste donc 10 fonctions seulement dépendant de A et B ; ce sont
les fonctions

$$
A.B \quad A.\bar{B} \quad \bar{A}.B \quad \bar{A}.\bar{B} \quad A.B + \bar{A}.\bar{B}
$$

et les fonctions qui s'en déduisent par négation, ce qui fait bien 10 fonctions
en tout.

Pour mettre une expression sous forme canonique disjonctive, on
applique les règles :

$$
\overline{a + \mathcal{B}} = \overline{a} \cdot \overline{\mathcal{B}}
$$

$$
\overline{a} \cdot \overline{\mathcal{B}} = \overline{a} + \overline{\mathcal{B}}
$$
jusqu'à ce que les signes - ne s'appliquent plus qu'à des classes A, B, C, ...
On a alors une expression ressemblant à une expression algébrique, dans
laquelle les lettres A, B, C, ..., $\bar{A}$, $\bar{B}$, $\bar{C}$, ... sont combinées uniquement
avec les signes + et . On développe cette expression d'après les règles de
l'algèbre ordinaire (puisque l'intersection est distributive par rapport à
l'union) comme si l'union était une somme et l'intersection un produit. On
réduit les termes semblables d'après la règle :

$$A + A = A$$

$$A \cdot \bar{A} = N$$

et on obtient ainsi une somme de termes. On met ces termes sous forme
canonique en écrivant par exemple :

$$A \cdot B = A \cdot B \cdot C + A \cdot B \cdot \bar{C}$$

et on réduit à nouveau les termes semblables. On est alors parvenu à la
forme canonique.

Soit, par exemple, à étudier si l'opération $\bar{C}$ est associative, c'est à
dire s'il y a identité entre les expressions

$$(A \cdot B) \cdot \bar{C}$$

$$A \cdot \bar{C} \cdot \bar{C}$$

Nous mettons la première sous forme canonique, ce qui donne :

$$ \begin{aligned} (A \cdot B) \cdot \bar{C} &= (\bar{A} + B) \cdot \bar{C} = \bar{A} + \bar{B} + C = A \bar{B} + C \\ &= A \bar{B} C + A \bar{B} \bar{C} + A B C + \bar{A} B C + \bar{A} \bar{B} C \end{aligned} $$

La seconde peut s'écrire :

$$\bar{A} + (B \cdot \bar{C}) = \bar{A} + \bar{B} + C = \bar{A} B C + \bar{A} B \bar{C} + \bar{A} \bar{B} C + \bar{A} \bar{B} \bar{C} + A \bar{B} C + A \bar{B} \bar{C} + A B C$$

Nous voyons que les deux expressions ne sont pas identiques, et que l'on a :

$$ \begin{aligned} A \cdot \bar{C} \cdot \bar{C}) &= [ (A \cdot \bar{B}) \cdot \bar{C} ] + \bar{A} \cdot B \cdot \bar{C} + \bar{A} \cdot \bar{B} \cdot \bar{C} \\ &= \{ [ (A \cdot \bar{B}) \cdot \bar{C} ] + \bar{A} + \bar{B} \} \end{aligned} $$

On peut vérifier que :

$$ \{ [ (A \cdot \bar{B}) \cdot \bar{C} ] \cdot \bar{C} \{ A \cdot \bar{C} (B \cdot \bar{C}) \} \} = \bar{T} $$

En effet, le premier membre de l'équation s'écrit :

$$ \begin{aligned} \overline{A \bar{B} + \bar{C}} + \bar{A} + \bar{B} + C &= A \bar{B} \cdot \bar{C} + \bar{A} + \bar{B} + C = (\bar{A} + B) \bar{C} + \bar{A} + \bar{B} + C \\ &= \bar{A} + \bar{B} + C + B \bar{C} \end{aligned} $$

Comme A ne figure qu'une fois, mettons :

$$\bar{B} + C + B \bar{C}$$

sous forme canonique par rapport aux variables B et C. Nous obtenons :

$$ \bar{B}C + \bar{B}\bar{C} + B\bar{C} + \bar{B}C + B\bar{C} = B\bar{C} + B\bar{C} + \bar{B}C + \bar{B}\bar{C} = \bar{T} $$

On arrive plus vite au résultat en niant l'expression, ce qui conduit à

$$ \overline{\bar{B} + C + B \bar{C}} = B \cdot \bar{C} (\bar{B} + C) = \bar{N} $$

Le fait que l'opération $\bar{C}$ n'est pas associative oblige à utiliser des parenthèses lorsque plusieurs de ces opérations se succèdent, pour qu'il n'y ait pas d'ambiguïté.

Le lecteur doit maintenant être en mesure de traiter un problème tel que le suivant :
**Problème V.** - Etant données deux classes A et B, on définit l'opération $\sim$ par l'égalité :

$$A \sim B = A \cdot B + \bar{A} \cdot \bar{B}$$

Calculer l'expression :

$$ (5) \quad [(A \sim B) \cdot (B \sim C)] \bar{C} \cdot (A \sim C), $$

comparer ce problème au problème IV, et essayer de tirer des conclusions analogues. Chercher en particulier la règle qui joue par rapport à l'expression (5) le rôle joué par la règle (31) relativement à l'expression (28).

**Problème VI.** - Montrer que le nombre de fonctions booléennes distinctes, de n classes $A_1, A_2, \dots, A_n$, dépendant effectivement de chacune des n classes est :

$$ N(n) - \frac{n}{1} N(n-1) + \frac{n(n-1)}{1 \cdot 2} N(n-2) + \dots $$

formule où l'on a posé pour abréger l'écriture

$$ N(n) = 2^{2^n} $$

## 1.10. - NOMBRE MAXIMUM DE SIGNES D'OPERATIONS NECESSAIRES POUR EXPRIMER UNE FONCTION DE n CLASSES.

Il est intéressant pour les applications, de savoir quel est le nombre maximum de signes d'opération qui interviennent dans la formation d'une fonction booléienne à n variables. Pour les comptes, remarquons qu'il y a $2^n$ termes possibles dans la forme canonique disjonctive, et que chacun de ces termes contient n - 1 signes. On prend un certain nombre de ces termes. Toutes réductions faites, il en reste au plus $2^{n-1}$. Soient en effet A, B, C, ..., L les n classes, et $K_1, K_2, \dots$, les termes en nombre $2^{n-1}$, correspondant à toutes les classes considérées sauf L. Nous aurons alors, pour les termes correspondant à A, B, C, ... L, les termes des deux lignes.

$$ K_1 L, K_2 L, K_3 L, \dots $$

$$ K_1 \bar{L}, K_2 \bar{L}, K_3 \bar{L}, \dots $$

Chacune de ces lignes contient $2^{n-1}$ termes. Si la fonction booléienne considérée contient plus de $2^{n-1}$ termes il y aura forcément, dans les termes qui y figurent, des termes dans une même colonne, qui se simplifieront d'après le schéma

$$ K_1 L + K_1 \bar{L} = K_1 $$

Comme il y a $2^{n-1}$ colonnes, il reste $2^{n-1}$ termes au plus. Nous avons donc au plus $(n-1) 2^{n-1}$ signes, et au plus $2^{n-1}$ signes +, d'où $n2^{n-1} - 1$ signes + et -; il nous reste maintenant à nous occuper des signes de négation. Soit F la fonction considérée, dans laquelle figurent au plus $n2^{n-1}$ lettres, et soient $\mu, \mu'$ les nombres de négations figurant dans F et $\bar{F}$. La fonction $F + \bar{F} = T$, mise sous forme canonique disjonctive non simplifiée, contient $n2^n$ lettres, c'est à dire $n 2^{n-1}$ signes de négation. Les simplifications amenant à F et $\bar{F}$ ne peuvent que faire disparaître un certain nombre de signes de négation, d'où $\mu + \mu' \le n 2^{n-1}$. Il en résulte que l'on a :

$$ \mu \le n 2^{n-2} \quad \text{ou} \quad \mu' \le n 2^{n-2} $$

les deux inégalités pouvant avoir lieu simultanément. Si $\mu \le n 2^{n-2}$, nous voyons que F peut s'écrire avec au plus :

$$ n 2^{n-1} - 1 + n 2^{n-2} = 3 n 2^{n-2} - 1 $$
signes d'opération. Si $\mu > n 2^{n-2}$, nous aurons

$$ \mu' \le n 2^{n-2} - 1 $$

et par conséquent $\overline{F}$ pourra s'écrire avec

$$ 3 n 2^{n-2} - 2 $$

signes d'opération, ce qui permet, avec une négation supplémentaire, d'écrire $\overline{F}$ avec au plus $3m2^{n-2} - 1$ signes d'opérations.

Nous obtenons ainsi le résultat : une fonction booléienne à n variables peut toujours être écrite de manière à faire intervenir au plus des signes d'opérations en nombre égal à

$$ 3 n \cdot 2^{n-2} - 1 $$

étant entendu que les signes d'opération sont les signes d'union, d'intersec- tion et de négation. Pour n = 3, ce nombre est de 17. Il se trouve effective- ment dans la fonction

$$ F = \overline{A} \overline{B} \overline{C} + \overline{A} \overline{B} \overline{C} + \overline{A} \overline{B} \overline{C} + \overline{A} \overline{B} \overline{C} $$

et également dans la fonction $\overline{F}$

$$ \overline{F} = \overline{A} \overline{B} \overline{C} + \overline{A} \overline{B} \overline{C} + \overline{A} \overline{B} \overline{C} + \overline{A} \overline{B} \overline{C} $$

Toute autre fonction de A, B, C peut s'écrire avec moins de 17 signes d'opérations. Naturellement, le décompte est fait sur la formule développée, mais on peut s'arranger pour que le nombre des opérations soit moindre. Nous pouvons par exemple écrire :

$$ F = (A \overline{B} + \overline{A} \overline{B}) C + (\overline{A} B + \overline{A} \overline{B}) \overline{C} $$

Il n'intervient dans cette expression que 10 opérations, comme le montre le schéma ci-dessous :

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

chaque opération est représentée par un petit carré contenant le signe de l'opération. On voit qu'il ne figure que 10 petits carrés dans le schéma.

## 2.- ALGÈBRE BINAIRE DE BOOLE

### 2.1. - PROPRIETES DES FONCTIONS CARACTERISTIQUES DE CLASSES

A toute classe A, contenue dans une totalité T, on peut associer une fonction dite "caractéristique", de la forme

$$ a(x) = K(A; x) $$
où x désigne un élément quelconque de T, et jouissant de la propriété que si x appartient à A, a (x) = 1 et si x appartient à A, a (x) = 0. a (x) est ainsi une fonction numérique, qui ne peut prendre que les valeurs 0 et 1.

Considérons maintenant deux classes A et B. Nous avons évidemment

$$K(A \cdot B ; x) = K(A ; x) ; K(B ; x)$$

La fonction caractéristique attachée à A. B peut donc être sans inconvénient représentée par a (x), b (x), a (x) et b (x) étant les fonctions caractéristiques attachées à A et B, et le signe . représentant le produit au sens ordinaire.

Appelons maintenant a (x) ÷ b (x) la fonction caractéristique attachée à A + B. Nous avons par définition a (x) ÷ b (x) = K (A + B ; x).

On vérifie sans peine que :

$$K(A + B ; x) = K(A ; x) + K(B ; x) - K(A \cdot B ; x)$$

d'où

$$a(x) \div b(x) = a(x) + b(x) - a(x) \cdot b(x)$$

Nous voyons ainsi la relation entre l'algèbre de Boole et l'algèbre ordinaire : l'algèbre de Boole concerne l'ensemble des propriétés des expressions que l'on peut former à partir des nombres a, b, c, ... par les opérations de produit et d'union, le produit étant le produit classique, et l'union étant définie par

$$(1) \quad a + b = a + b - ab$$

A ces deux opérations, il faut ajouter la négation, définie par :

$$(2) \quad \bar{a} = 1 - a$$

Il est essentiel de remarquer que le produit et les opérations (1) et (2), appliquées à des nombres égaux à 0 ou 1, donne encore des nombres égaux à 0 ou 1. Il suffit pour le montrer de partir du fait qu'être égal à 0 ou 1, pour un nombre t, se traduit par :

$$t^2 = t$$

Supposons donc :

$$a^2 = a$$

$$b^2 = b$$

Nous en déduisons :

$$\begin{align*} (a \div b)^2 &= a^2 + b^2 + a^2 b^2 + 2 ab - 2 a^2 b - 2 ab^2 \\ &= a + b - ab = a \div b \end{align*}$$

$$(ab)^2 = a^2 b^2 = ab$$

$$(1 - a)^2 = 1 + a^2 - 2a = 1 - a$$

L'algèbre de Boole, opérant sur des nombres égaux à 0 ou 1, c'est à dire dans le système de numérotation binaire, sera dite algèbre de Boole binaire.

Il peut être utile, en certaines circonstances, de ramener l'algèbre binaire de Boole à l'algèbre ordinaire, c'est à dire aux relations mod (x² - x); mais on suivra en général le chemin inverse, parce que l'algèbre mod (x² - x) n'est pas très commode à manipuler. Supposons par exemple que nous soyons en face du problème suivant :

**Problème VII.** - Quels sont les polynomes z en x et y tels que si :

$$x^2 = x$$

$$y^2 = y$$

ils satisfont à $z^2 = z$ ?
La solution algébrique est la suivante :

Puisque $x^2 = x$, $y^2 = y$, z peut toujours, quel que soit son degré, se ramener à :

$$z = A + Bx + Cy + Dxy$$

d'où

$$z^2 = A^2 + B^2 x^2 + C^2 y^2 + D^2 x^2 y^2 + 2 AB x + 2 Acy + 2 AD x^2 y + 2 BCxy + 2 BD x^2 y + 2 CD xy^2$$

$$= A^2 + (B^2 + 2 A B) x + (C^2 + 2 A C) y + (D^2 + 2 AD + 2 BC + 2 BD + 2 CD) xy$$

Les coefficients A, B, C, D doivent ainsi satisfaire à :

$$A = A^2$$

$$B = B (B + 2 A)$$

$$C = C (C + 2 A)$$

$$D = D (D + 2 A + 2 B + 2 C) + 2 BC$$

Ce système ne se résout simplement que si on pose :

$$B = \lambda - A$$

$$C = \mu - A$$

$$D = \nu + A - \lambda - \mu$$

ce qui conduit à :

$$A^2 = A$$

$$\lambda^2 = \lambda$$

$$\mu^2 = \mu$$

$$\nu^2 = \nu$$

Si on ordonne z en A, $\lambda, \mu, \nu$, on voit que l'on obtient :

$$z = A(1-x) (1-y) + \lambda x (1-y) + \mu y (1-x) + \nu xy$$

ce qui montre que nous avons en fait écrit la forme canonique disjonctive :

$$z = A \overline{x}\overline{y} + \lambda x\overline{y} + \mu y\overline{x} + \nu xy$$

Si on prend comme point de départ l'algèbre de Boole, on obtient tout de suite l'expression générale de z dépendant de quatre paramètres tous égaux à 0 ou à 1.

Posons maintenant un autre problème.

**Problème VIII.** - z ayant la forme générale établie à propos du problème précédent, quelle doit être sa forme pour que z = 1, si x = y et dans ce cas seulement ?

Ici le calcul direct peut se faire directement. Si $x \neq y$, on a :

$$(x - y)^2 = 1$$

Nous essayons donc :

$$z = 1 - (x - y)^2$$

qui convient effectivement. On obtient en développant :

$$z = 1 - x - y + 2 xy$$

Si nous voulons utiliser les résultats que nous connaissons déja en algèbre de Boole, nous pouvons partir des équivalences :

$$\begin{cases} A = B \end{cases} \equiv \begin{cases} (A \rightarrow B) \cdot (B \rightarrow A) \end{cases}$$

$$\begin{cases} A \rightarrow B \end{cases} \equiv (A + B = T)$$

ce qui nous permet d'écrire l'égalité $A = B$ sous la forme :

$$(A + B) \cdot (A + \bar{B}) = T \quad \text{ou encore} \quad AB + A\bar{B} = T$$
En appelant $x$ et $y$ les fonctions caractéristiques de $A$ et $B$, nous obtenons bien :

$$z = xy + (1-x)(1-y) = 1 - x - y + 2xy$$

## 2.2. - EQUATIONS BOOLEIENNES.

Considérons l'équation en $x$ et $y$

$$x + y = 2xy$$

qui d'après ce que nous avons vu, est équivalente à :

$$x = y$$

On peut chercher à résoudre cette équation en $y$. Nous tirons effectivement :

$$y = (2y - 1)x$$

Elevons cette expression au carré, nous obtenons :

$$y^2 = (4y^2 - 4y + 1)x^2$$

d'où

$$y = x$$

Parallèlement à cette résolution, nous pouvons chercher à résoudre en $B$ l'équation :

$$A.B + \overline{A}.\overline{B} = T$$

Il suffit pour cela de multiplier par $A$ et par $B$, ce qui donne :

$$A.B = A$$

$$A.B = B$$

d'où $A = B$. Inversement, $A = B$ satisfait à l'équation, qui se réduit, si $A = B$, à $A + \overline{A} = T$.

Il se pose donc le problème général de résoudre une équation de la forme :

$$F(X, Y, Z, ...) = N$$

où $F$ est une fonction booléienne des classes $X, Y, Z, ...$

Une telle équation sera appelée équation booléienne.

Si $F$ est mise sous forme canonique disjonctive, nous pouvons en grouper les termes qui contiennent $A$ et ceux qui contiennent $\overline{A}$, mettre $F$ sous la forme :

$$F = AX + \overline{B}X$$

$\overline{A}$ et $B$ étant deux fonctions booléiennes de $Y, Z, ...$

Raisonnons en algèbre binaire de Boole, ce qui nous conduit à l'équation :

$$(1) \quad ax + b\overline{x} = 0$$

dans laquelle $a, b, x$ sont des variables booléiennes. Les quatre variables :

$ab, a\overline{b}, \overline{ab}, \overline{a\overline{b}}$,

sont telles que l'une d'entre elles, et une seule, est nécessairement égale à 1. Nous avons pour les quatre cas possibles :

$$\begin{array}{lcl} \text{Si } ab & = & 1 \\ \text{Si } a\overline{b} & = & 1 \\ \text{Si } \overline{a}b & = & 1 \\ \text{Si } \overline{a\overline{b}} & = & 1 \end{array}$$

$$\begin{array}{lcl} ax + b\overline{x} & = & 1 \\ ax + b\overline{x} & = & x \\ ax + b\overline{x} & = & \overline{x} \\ ax + b\overline{x} & = & 0 \end{array}$$
x doit donc être égale à 0 dans le deuxième cas, à 1 dans le troisième; dans le premier et quatrième cas, x est indéterminée, puisque ax + b = x a alors une valeur indépendante de x. Ceci nous donne ainsi la valeur de x :

$$x = ab + 0 \cdot \bar{a}b + \bar{a}b + \bar{a} \cdot \overline{b} \cdot v = ab + \bar{a}b + \bar{a} \overline{b}v$$

u et v étant arbitraires; x étant ainsi définie, on voit que :

$$abx + \bar{a}b + \bar{a} \overline{b}x = x$$

ce qui permet de mettre la solution, en x, de l'équation (1) sous la forme :

$$(2) \quad x = \bar{a}b + (ab + \bar{a}\overline{b})x$$

En portant cette valeur dans (1), il reste la condition

$$(3) \quad ab = 0$$

Nous vérifions que si $ab = 1$ ou $\bar{a} \cdot \overline{b} = 1$, l'équation (2) laisse x indéterminée. Si $ab = 1$ l'équation n'est pas vérifiée, si $\bar{a} \cdot \overline{b} = 1$, elle l'est. Si $\bar{a}b + \overline{ab} = 1$, x est en tièrement déterminée, puisque l'on a $x = \bar{a}b$, et l'équation est satisfaite.

Si nous avons maintenant une équation à plusieurs inconnues, soit :

$$f(x, y, z) = 0$$

on peut la résoudre en posant :

$$f(1, y, z) = a(y, z)$$

$$f(0, y, z) = b(y, z)$$

ce qui nous ramène à :

$$x = \bar{a}(y,z)b(y,z) + a(y,z)b(y,z) + \bar{a}(y,z)\overline{b}(y,z)$$

$$a(y,z)b(y,z) = g(y,z) = 0$$

On opérerait ensuite sur g comme sur f.

D'une manière générale, une équation de la forme

$$f(x_1, x_2, \dots, x_n) = 0$$

se résoudra sous la forme :

$$x_1 = f_1(x_1, x_2, \dots, x_n)$$

$$x_2 = f_2(x_2, \dots, x_n)$$

$$x_{n-1} = f_{n-1}(x_{n-1}, x_n)$$

$$x_n = f_n(x_n)$$

Si la dernière équation est de la forme $x_n = 0$, $x_n = 1$ ou $x_n = x_n$, l'équation admet une ou plusieurs solutions. Si elle est de la forme $x_n = \bar{x}_n$, l'équation est impossible.

Toute équation de la forme $f = 1$, se ramène immédiatement au cas étudié en posant $g = 1 - f$. Tout système de la forme

$$F_1 = F_2 = \dots = F_m = 0$$

se ramène à l'équation unique :

$$F_1 + F_2 + \dots + F_m = 0$$

**Problème IX.** - Montrer que le système

$$x < y < z$$

est impossible.
Commençons par exprimer que $x \prec y$. Si $y = 1$, $x$ est indéterminée;
Si $y = 0$, $x = 0$, d'où

$$x = u \cdot y + 0 (1 - y) = u \cdot y$$

Nous en déduisons par multiplication par $y$ que

$$x = xy$$

ou encore

$$x (1 - y) = 0$$

Nous savons par ailleurs qu' $x = y$ s'exprime par

$$xy + (1-x) (1-y) = 1$$

La condition $x \neq y$ s'exprimera donc par

$$xy + (1-x) (1-y) = 0$$

La condition $x < y$, qui comprend à la fois $x < y$ et $x \neq y$, devient
ainsi :

$$x (1 - y) + xy + (1 - x) (1 - y) = 0$$

De même $y < z$ donne

$$y (1 - z) + yz + (1 - y) (1 - z) = 0$$

Le système proposé se ramène à l'équation unique :

$$f(x, y, z) = x (1-y) + xy + (1-x) (1-y) + y (1-z) + yz + (1-y) (1-z) = 0$$

Nous obtenons, après des simplifications évidentes :

$$ 
\begin{aligned}
f(x, y, z) &= x + y (1 - y) [(1 - x) + (1 - z)] \\
&= x + y + \bar{y} (\bar{x} + \bar{z})
\end{aligned}
$$

Pour $x = 0$, cette expression est égale à 1. Pour $x = 1$, elle est encore égale à 1. Donc le système est impossible.

Nous pouvons remarquer que $x < y$ équivaut à $x = 0, y = 1$.

En effet, $x < y$ s'exprime par

$$x \bar{y} + xy + \bar{x} \cdot \bar{y} = 0$$

La méthode générale nous conduit à écrire :

$$x + \bar{x} \cdot \bar{y} = 0$$

d'où

$$a = 1$$

$$b = \bar{y}$$

$$\bar{y} = 0$$

$$x = \bar{y} x$$

ce qui donne bien $x = 0, y = 1$.

Après ces exercices sur les variables booléennes numériques, nous allons revenir aux classes. Nous obtenons des résultats tout à fait comparables; si par exemple nous avons

$$A X + B \bar{X} = N$$

nous en déduisons que :

$$A B = N$$

$$X = \bar{A} B + X (AB + \bar{A} \cdot \bar{B}).$$
De même, nous pouvons résoudre des équations de la forme $f(X, Y, Z) = N$. Il nous faut cependant faire une restriction quant aux inégalités telles que $X < Y$, quand il n'est pas vrai que $X = Y$. En effet, dire que l'on n'a pas $X = Y$, ou encore que l'on n'a pas

$$XY + \overline{XY} = T$$

ne signifie pas ici que l'on a

$$XY + \overline{XY} = N$$

### 2. 3. - OPERATION DE SCHAEFFER.

On peut exprimer toutes les opérations sur variables booléennes à partir des opérations $+$, $-$, Schaeffer a montré qu'une seule opération suffirait, à savoir la contradiction, définie par

$$A | B = \overline{A}B$$

On voit facilement en effet que

$$\overline{A} = A | \overline{A}$$

et que

$$AB = \overline{A} | \overline{B} = (A | B) | (\overline{A} | \overline{B}).$$

Comme l'union s'exprime à partir de l'intersection et de la négation, elle peut donc s'exprimer en fonction de la contradiction seule. Examinons les opérations possédant les mêmes propriétés que la fonction de Schaeffer, ce qui nous conduit au problème suivant, que nous traitons en algèbre de Boole binaire.

**Problème X.** - Quelles sont les fonctions booléennes de deux variables telles que l'on puisse, en utilisant uniquement *une* de ces fonctions, exprimer toutes les autres ?

Nous savons déja que la fonction de Schaeffer

$$f(x, y) = 1 - xy$$

permet d'exprimer toutes les fonctions booléennes. Considérons maintenant la fonction la plus générale de deux variables

$$(1) \quad F(x, y) = \alpha xy + \beta x (1-y) + \gamma (1-x) y + \delta (1-x) (1-y).$$

La négation de x ne peut se définir que par $F(x, x)$; nous devons donc avoir :

$$F(x, x) = 1 - x$$

d'où

$$\alpha = 0$$

$$\delta = 1$$

La fonction prend donc la forme

$$(2) \quad F(x, y) = \beta x (1-y) + \gamma (1-x) y + (1-x) (1-y)$$

Si $\beta = 0, \gamma$ est forcément égal à 0, sinon nous aurions

$$F(x, y) = (1-x)y + (1-x)(1-y) = 1-x$$

et F ne dépendrait que de x. De même si $\beta = 1$, on a nécessairement $\gamma = 1$. Nous n'avons donc en définitive qu'à choisir entre

$$f(x, y) = (1-x)y + (1-x) y + (1-x) (1-y) = 1 - xy$$

$$g(x, y) = (1-x)(1-y)$$
c'est-à-dire entre la fonction de Schaeffer et la fonction :

$$g(x,y) = \overline{x+y} = 1 - f(1-x, 1-y)$$

Les deux seules solutions au problème proposé sont donc les fonctions :

$$f(x, y) = \overline{xy}$$

$$g(x, y) = \overline{x+y}$$

### 3.- TREILLIS

#### 3.1.- DEFINITION IMPLICITE DE L'UNION A PARTIR DE L'INCLUSION.

Nous allons, relativement aux classes, étudier un problème qui trouve son prolongement dans l'algèbre générale. Nous allons voir si on peut définir la somme $X + Y$ à partir du produit et de l'implication. Partons de $X$ et $Y$. Nous pouvons former les trois classes :

$XY$

$X + Y$

$X + \bar{Y}$

Combinons encore ces classes par produit et implication. Nous obtenons :

$$XY (\bar{X} + Y) = XY \quad XY (X + \bar{Y}) = XY (\bar{X} + Y) (X + \bar{Y}) = XY + \bar{X}\bar{Y}$$

$$\bar{X}\bar{Y} + \bar{X} + Y = T \quad \bar{X}\bar{Y} + X + \bar{Y} = T \quad \bar{X}\bar{Y} + X + \bar{Y} = X + \bar{Y}$$

$$X\bar{Y} + XY = X \quad X\bar{Y} + XY = Y \quad X\bar{Y} + X + Y = X + Y$$

Sinous poursuivons les combinaisons, nous voyons que nous ne sortons pas du système de classes :

$$T, XY, XY + \bar{X}\bar{Y}, X, Y, X + \bar{Y}, \bar{X} + Y$$

Donc, nous ne pouvons obtenir $X + Y$ par une opération explicite; cherchons une définition implicite.

Il est bien évident que $X + Y$ est une classe $Z$ contenant $X + Y$, et que toute classe contenant $X$ et $Y$ contient $Z$. $Z$ est ainsi définie par :

$$\begin{cases} X \to Z & Y \to Z \\ \text{Si } X \to U \text{ et } Y \to U, \text{ alors } Z \to U. \end{cases}$$

Ceci nous donne les équations :

$$\bar{X} + Z = T$$

$$\bar{Y} + Z = T$$

$$[ (\bar{X} + U) \cdot (\bar{Y} + U) \subset (\bar{Z} + U) ] = T$$

lesquelles s'expriment uniquement en utilisant $\subset$. et $\cup$ puisqu'on peut les écrire :

$$(X \subset Z) = T$$

$$(Y \subset Z) = T$$

$$\{ [ (X \subset U) \cdot (Y \subset U) ] \subset (Z \subset U) \} = T$$

Voyons ce que donne le développement de ces équations : nous obtenons :

$$\bar{X} + Z = T$$

$$\frac{\bar{Y} + Z = T}{(\bar{X} + U)(\bar{Y} + U) + (\bar{Z} + U) = T}$$
ou encore

$$X\bar{Z} = N$$

$$Y\bar{Z} = N$$

$$(X + U)(Y + U)Z\bar{U} = N$$

La dernière équation donne

$$\overline{X\bar{Y}Z\bar{U}} = N$$

Cette équation doit avoir lieu *quel que soit* U. D'où, en rassemblant toutes les conditions en une seule :

$$X\bar{Z} + Y\bar{Z} + \overline{X\bar{Y}Z} = N$$

c'est à dire

$$\overline{X\bar{Y}Z} + (X + Z)\bar{Z} = N$$

Nous obtenons ainsi :

$$(X + \overline{Y}) Z = N$$

$$(X + Y) \bar{Z} = N$$

d'où

$$Z = Z(X + Y)$$

$$\bar{Z} = \bar{Z}(\overline{X + Y})$$

La négation de la deuxième relation nous donne

$$Z = Z + X + Y$$

En combinant les deux équations

$$Z = Z(X + Y)$$

$$Z = Z + X + Y$$

nous obtenons la valeur cherchée de Z. Il suffit pour cela, dans le second membre de la seconde, de remplacer Z par Z(X + Y), ce qui donne

$$Z = Z(X + Y) + X + Y = X + Y$$

On montrerait de même que l'intersection de X et Y peut se définir comme la classe Z telle que

$$\begin{cases} Z \to X \\ \text{Si } U \to X \text{ et } U \to Y, \text{ alors } U \to Z \end{cases} \quad Z \to Y$$

### 3.2. - ENSEMBLES PARTIELLEMENT ORDONNES.

La conception des opérations + et . à partir de l'inclusion nous amène à dire quelques mots des *treillis*. D'une façon générale, on appelle ensemble partiellement ordonné, un ensemble d'éléments tels qu'entre certains couples d'éléments, on puisse reconnaitre si existe, ou non, une relation de la forme

$$a \leq b$$

Cette relation est supposée transitive, c'est à dire que

$$a \leq b \text{ et } b \leq c$$

entraîne $a \leq c$. L'inégalité stricte

$$a < b$$
signifie que $a \leq b$ et que $a$ est distinct de $b$. L'inégalité stricte est disymétrique, de sorte que l'on ne peut pas avoir à la fois

$$a < b \text{ et } a > b$$

Lorsque l'on a $a < b$, on dit quelquefois que $b$ est un ascendant de $a$, et que $a$ est un descendant de $b$. Si on considère les humains du point de vue de la filiation, ils constituent un ensemble partiellement ordonné. En effet, étant donnés deux individus $a$ et $b$, trois cas peuvent se présenter, et trois seulement :

* $a$ est descendant de $b$

* $b$ est descendant de $a$

* $a$ et $b$ ne sont pas liés en ligne directe.

De même les entiers vus du point de vue de la divisibilité forment un ensemble partiellement ordonné : étant donné deux entiers $a$ et $b$, il n'y a qu'trois cas possibles : ou $a$ divise $b$, ou $b$ divise $a$, ou $a$ et $b$ ne se divisent ni dans un sens, ni dans l'autre. On peut dire la même chose pour les polynomes.

Examinons le cas des entiers. Nous exprimerons, pour éviter toute confusion avec les inégalités usuelles, la relation $a$ divise $b$ par $a \rightarrow b$. L'arithmétique nous apprend alors que, si on se donne $a$ et $b$, il existe parmi leurs ascendants communs (leurs multiples communs) un ascendant tel qu'il soit descendant de tous les autres ascendants communs. En signes, cela veut dire qu'il existe $c$ tel que

$$a \rightarrow c$$

$$b \rightarrow c$$

$$\text{si } (a \rightarrow d) \text{ et } (b \rightarrow d) \text{ alors } (c \rightarrow d).$$

De même, parmi leurs descendants communs, il existe un descendant qui est un ascendant de tous les autres descendants; ou encore, il existe $\gamma$ tel que

$$\gamma \rightarrow a$$

$$\gamma \rightarrow b$$

$$\text{si } (\delta \rightarrow a) \text{ et } (\delta \rightarrow b) \text{ alors } (\delta \rightarrow \gamma).$$

On reconnait là le plus petit commun multiple et le plus grand commun diviseur; nous voyons que dans l'algèbre de Boole, AB joue le rôle d'un plus grand commun diviseur, $A + B$ le rôle d'un plus petit commun multiple. Représentons pour un instant par $a+b$ le p.p.c.m. et par $ab$ le p.g.c.d. de deux entiers. Cherchons si les relations de l'algèbre de Boole ont lieu. Examinons par exemple l'égalité

$$a (b+c) = ab + ac$$

Au premier membre figure le p.g.c.d. de $a$ et du p.p.c.m. de $b$ et $c$; au second membre figure le p.p.c.m. des p.g.c.d. de $a$ et de $b$ d'une part, de $a$ et de $c$ d'autre part. Exprimons ces différents nombres. En appelant $\Delta$ le p.g.c.d. de $a, b, c$, nous avons (en écrivant des égalités ordinaires)

$$a = \Delta \alpha$$

$$b = \Delta \beta$$

$$c = \Delta \gamma$$
α, β, γ étant premiers entre eux dans leur ensemble. Appelons $δ_1, δ_2$ les p.g.c.d. de α et β, de α et γ. Nous aurons alors

$$a = \Delta \delta_1 \alpha' = \Delta \delta_2 \alpha''$$

$$b = \Delta \delta_1 \beta'$$

$$c = \Delta \delta_2 \gamma''$$

α' et β' sont premiers entre eux, ainsi que α'' et γ''δ₁ et δ₂ sont premiers entre eux, puisque α, β, γ n'ont aucun diviseur commun; puisque $δ_1 \alpha' = δ_2 \alpha''$, $δ_1$ divise $α''$.

Si nous faisons intervenir maintenant le p.g.c.d. $δ_3$ de $β'$ et $γ''$, nous obtenons

$$a = \Delta \delta_1 \delta_2 \lambda$$

$$b = \Delta \delta_1 \delta_3 \mu$$

$$c = \Delta \delta_2 \delta_3 \nu$$

Dans ces conditions nous avons

$$ab = \Delta \delta_1$$

$$ac = \Delta \delta_2$$

$$ab + ac = \Delta \delta_1 \delta_2$$

$$b + c = \Delta \delta_1 \delta_2 \delta_3 \mu \nu$$

$$a = \Delta \delta_1 \delta_2 \lambda$$

$$a (b + c) = \Delta \delta_1 \delta_2 = ab + ac$$

Examinons également l'égalité

$$a + bc = (a + b) (a + c)$$

Nous aurons

$$bc = \Delta \delta_3$$

$$a + bc = \Delta \delta_1 \delta_2 \delta_3 \lambda$$

$$a + b = \Delta \delta_1 \delta_2 \delta_3 \lambda \mu$$

$$a + c = \Delta \delta_1 \delta_2 \delta_3 \lambda \nu$$

$$(a + b) (a + c) = a + bc$$

Nous voyons que les relations de l'algèbre de Boole sont valables pour les opérations + (p.p.c.m.) et. (p.g.c.d.). On peut en donner une justification élémentaire en remarquant qu'étant donnés a, b, c, si on calcule leur p.p.c.m., et qu'on décompose ce p.p.c.m. en facteurs premiers, et qu'on marque sur un jeton chacun de ces facteurs, on peut disposer ces jetons sur une table de manière que chaque nombre soit représenté par l'ensemble des jetons disposés dans un cercle, les opérations de p.g.c.d. et p.p.c.m. étant alors exactement des intersections et des unions. Par exemple, le produit des nombres contenus dans le petit triangle du milieu n'est autre que le p.g.c.d. de a, b, c.

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

### 3.3. - DEFINITION D'UN TREILLIS.

On conçoit l'intérêt qu'il y a à savoir si un ensemble partiellement
ordonné se prête ou non à des calculs semblables à ceux que nous avons étudiés à propos de l'algèbre de Boole.

La première question est de savoir si $a + b$ et $ab$ existent. Pour un ensemble dont on suppose seulement qu'il est partiellement ordonné, $a + b$ et $ab$ n'existent pas nécessairement, ce qui veut dire que parmi les ascendants communs à $a$ et $b$, il n'en existe pas forcément un qui est descendant de tous les autres. Par exemple dans l'ensemble des quatre éléments $a, b, c, d$ tels que l'on ait seulement

$$a \to c$$

$$b \to c$$

$$a \to d$$

$$b \to d$$

$a + b$ n'existe pas; ab défini comme le descendant commun de $a$ et de $b$ tels que tous les autres descendants communs soient ses descendants, n'existe pas davantage pour l'ensemble considéré.

Les ensembles partiellement ordonnés tels que pour tout couple $a, b$ les éléments $a + b$ et $ab$ existent sont appelés des treillis.

Allons plus loin. Soit un treillis. L'égalité

$$a (b + c) = ab + ac$$

peut, ou non, avoir lieu. Dans le premier cas, le treillis est dit distributif. Lorsque le treillis n'est pas distributif, on peut montrer que l'on a une relation moins stricte, à savoir :

$$ab + ac \to a (b + c)$$

et que l'on a également

$$a + bc \to (a + b) (a + c)$$

On remarque tout d'abord que

$$ab \to b \to b + c$$

$$ac \to c \to b + c$$

$$ab \to a$$

$$ac \to a$$

$ab$ et $ac$ sont donc deux descendants communs à $a$ et à $b + c$. Par définition $a (b + c)$ admet pour ascendants tous les descendants communs. Donc

$$ab + ac \to a (b + c)$$

En général, dans un treillis, seules sont vérifiées les lois de "semi distributivité"

$$ab + ac \to a (b + c)$$

$$a + bc \to (a + b) (a + c)$$

dont nous avons démontré la première; la seconde se démontre d'une manière analogue.

De toutes manières, les opérations $+ $ et $-$ sont associatives et commutatives. Si enfin une des lois de semi distributivité est une loi de distributivité complète, il en est de même pour l'autre. Si, par exemple

$$a (b + c) = ab + ac$$

nous aurons

$$(a + b) (a + c) = a + ab + ac + bc = a + bc$$

puisque l'on a évidemment $a + ab = a$.

Donnons, pour fixer les idées, un exemple de treillis dans lequel a simplement lieu la semi distributivité. Il suffit pour cela de considérer des
domaines convexes. Etant donnés deux domaines convexes A et B, la définition de AB, c'est à dire le plus grand des domaines convexes contenus à la fois dans A et B, se confond avec l'intersection ordinaire. Mais la définition de A + B, c'est à dire le plus petit des domaines convexes contenant à la fois A et B, est différente.

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

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

On vérifie facilement sur la figure la propriété de semi distributivité; AB + AC est cerclé d'un trait gras; sur la figure A(B+C) est confondu avec A. L'inégalité est évidente.

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

### 3.4. - TREILLIS DISTRIBUTIF.

Portons maintenant notre attention sur les treillis distributifs. Pour faire le raccordement avec l'algèbre de Boole, il ne nous manque plus que la négation. Bornons nous aux treillis contenant un nombre fini d'éléments, soient :

$a_1, a_2, \dots, a_n$

Posons

$$T = a_1 + a_2 + \dots + a_n$$

$$N = a_1 a_2 \dots a_n.$$

T et N sont deux éléments du treillis. T est ascendant d'un élément quelconque, N descendant d'un élément quelconque. Nous avons évidemment, quel que soit a

$$T + a = T$$

$$a \cdot N = N$$

$$T \cdot a = a$$

$$a + N = a$$

Nous reconnaissions là des relations fondamentales de l'algèbre des classes. Soit maintenant à définir $\bar{a}$. Nous le définirons implicitement comme racine du système

$$a + x = T$$

$$ax = N$$

En se rapportant aux raisonnements en 1-7 faits pour montrer que $\overline{A} = A$, on montre facilement que $\underline{si} x$ existe, x est unique. Mais x n'existe pas forcément. Considérons le treillis constitué par 3 éléments a b c tels que :

$$a \rightarrow b \rightarrow c$$

Ce treillis est distributif, comme on le vérifie sans peine. Nous avons évidemment

$$a = N$$

$$c = T$$
β, s'il existait, satisferait à

$$b + x = c$$

$$bx = a$$

On voit que le système n'a pas de solution.

Les treillis distributifs pour lesquels on peut associer à chaque élément a un élément $\bar{a}$ sont dits treillis à complémentation. Les règles de calcul dans de pareils treillis sont identiques à celles de l'algèbre de Boole.

## 4. COMPARAISON DE L'ALGÈBRE DE BOOLE AVEC L'ALGÈBRE ORDINAIRE

Après avoir montré les relations de l'Algèbre de Boole avec la théorie des inégalités, par l'intermédiaire des treillis, nous allons maintenant faire une comparaison avec l'Algèbre ordinaire. Nous désignerons par a, b, c, ... des éléments qui seront des nombres en algèbre, des classes en algèbre de Boole. L'union sera représentée par +, le produit par ... Les classes N et T seront représentées par 0 et 1. Les règles communes aux deux algèbres sont :

$$a + b = b + a$$

$$a \cdot b = b \cdot a$$

$$(a + b) + c = a + (b + c)$$

$$(a \cdot b) \cdot c = a (b \cdot c)$$

$$(a + b) \cdot c = a \cdot c + b \cdot c$$

$$a + 0 = a$$

$$a \cdot 1 = a$$

Dans l'algèbre de Boole, le système

$$a + x = 1$$

$$a \cdot x = 0$$

admet toujours une solution, tandis que dans l'algèbre ordinaire il n'en admet que si $a = 0$ ou $a = 1$. Cette solution est représentée par $\bar{a}$.

Les opérations suivantes sont légitimes en algèbre de Boole et ne le sont pas en algèbre ordinaire :

$$a + b \cdot c = (a + b) (a + c)$$

$$a + ab = a$$

$$a \cdot (a + b) = a$$

$$\overline{ab} = \bar{a} + \bar{b}$$

$$\overline{a + b} = \bar{a} \cdot \bar{b}$$

Il existe en Algèbre ordinaire des opérations qui ne sont pas légitimes en Algèbre de Boole. Si

$$x = y$$

on peut en déduire, dans les deux algèbres, que

$$a + x = a + y$$

$$a \cdot x = a \cdot y$$

mais tandis que le retour inverse est permis en algèbre ordinaire (sauf pour la deuxième équation si $a = 0$), il n'en est pas ainsi en algèbre de Boole. On ne peut pas, en algèbre de Boole, simplifier les deux membres d'une égalité. Cela tient à ce que, dans cette algèbre de Boole, les équations (considérées séparément)

$$a + x = 0$$

$$a \cdot x = 1$$
n'ont pas de solutions.

Les différences citées ci-dessus suffisent à mettre en évidence les précautions à prendre quand on calcule en algèbre de Boole. Le lecteur pourra s'exercer à chercher d'autres points de comparaison tels que celui-ci.

Si en algèbre ordinaire

$$a \cdot b \cdot c = 0$$

entraîne que l'un au moins des facteurs est égal à 0, en algèbre de Boole, l'égalité

$$a \cdot b \cdot c = 1$$

entraîne que tous les facteurs sont égaux à 1.

## 5.- APPLICATIONS DE L'ALGÈBRE DE BOOLE

### 5.1. - APPLICATIONS AU CALCUL BINAIRE.

Considérons deux nombres binaires $x_1$ et $y_1$, égaux chacun à 0 ou 1. Leur somme est un nombre binaire à deux chiffres au plus, de la forme $(z_2, z_1)$. $z_2$ n'est égal à 1 que si $x_1$ et $y_1$ sont égaux tous les deux à 1, auquel cas leur somme est $z = (1, 0)$.

Nous avons ainsi

$$z_2 = x_1 y_1 \\ 2 z_2 + z_1 = x_1 + y_1$$

d'où

$$z_1 = x_1 + y_1 - 2 x_1 y_1$$

En notation booléenne, ceci donne

$$z_1 = x_1 \bar{y}_1 + \bar{x}_1 y_1 \\ z_2 = x_1 y_1$$

Soit maintenant à faire la somme de 3 nombres $x_1, y_1, t_1$, égaux à 0 ou 1. Faisons d'abord la somme de $x_1, y_1$, ce qui nous donne $(z_2, z_1)$. Le résultat final de l'opération sera ainsi un nombre $(s_2, t_1)$, avec

$$s_1 = z_1 \bar{t}_1 + \bar{z}_1 t_1 \\ s_2 = t_1 z_1 + z_2$$

Dans $s_2$, nous voyons apparaître le report $t_1 z_1$ et l'ancien report $z_2$. Ils ne peuvent pas être égaux à 1 tous les deux, puisque

$$t_1 z_1 z_2 = 0$$

Nous avons ainsi sous forme canonique

$$s_1 = x_1 \bar{y}_1 \bar{t}_1 + \bar{x}_1 y_1 \bar{t}_1 + x_1 y_1 t_1 + \bar{x}_1 \bar{y}_1 t_1 \\ s_2 = x_1 \bar{y}_1 t_1 + \bar{x}_1 y_1 t_1 + x_1 y_1 t_1 + x_1 \bar{y}_1 \bar{t}_1$$

$s_2$ est égal à 1 seulement si au moins deux des variables $x_1, y_1, t_1$ sont égaux à 1 ce qui conduit à la forme

$$(1) \quad s_2 = x_1 y_1 + y_1 t_1 + x_1 t_1$$
Si $s_2 = 1$, nous avons

$$s_1 = x_1 y_1 t_1$$

Si $s_2 = 0$, nous avons

$$s_1 = x_1 + y_1 + t_1$$

d'où

$$(2) 	 s_1 = s_2 x_1 y_1 t_1 + \bar{s}_2 (x_1 + y_1 + t_1)$$

Si nous disposons d'appareils faisant la somme (‡) et le produit et la néga-
tion, nous pourrons donc faire l'opération conformément au schéma.

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

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

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

L'avantage de ce schéma est de comporter **une seule négation**, ce qui est
important dans le calcul électronique, lorsque l'est représenté par la pré-
sence d'un signal, et 0 par son absence. Nier la présence est facile (on
court circuite) mais nier l'absence (il faut amener de l'énergie) peut l'être
moins.

Une fois construite une cellule additionnant trois chiffres, il est facile
de construire un dispositif additionnant deux nombres quelconques, puisque
l'on peut faire les reports. Le schéma ci-dessous, où x, y sont les chiffres
à additionner, t les chiffres de retenue, s les chiffres de la somme, se
passe de commentaires.

L'intérêt de l'algèbre de Boole par le calcul électronique est que les réseaux à diodes fournissent tout naturellement les opérations + (ou) et . (et). Les problèmes à traiter sont alors par exemple de chercher la forme des fonctions booléennes contenant le moins de signes d'opérations, ou contenant le moindre nombre de négations.

<figure><img src="image_13.png" /></figure>
## 5.2. APPLICATIONS A LA LOGIQUE.

L'algèbre de Boole se prête particulièrement à l'étude de la logique formelle, puisque si on interprète le signe $\dot{+}$ comme "ou" et le signe $\cdot$ comme "et", on trouve une correspondance entre $T$ (vrai) et $N$ (faux), qui permet de ramener à un calcul algébrique un grand nombre de considérations sur la structure logique des raisonnements.

Si par exemple $a(x, y)$ est une fonction d'éléments quelconques, égale à 1 si les éléments satisfont à une condition $A(x, y)$, égale à 0 dans le cas contraire, une proposition telle que :

(α) "Pour tout x s'il existe un y tel que $A$"

s'écrit

$$ \dot{\pi}_x \dot{\Sigma}_y a(x, y) = 1 $$

le signe $\dot{\Sigma}$ jouant par rapport à $\dot{+}$ le rôle de $\Sigma$ par rapport à $+$.
On peut comparer à (α) la proposition (β).

(β) "Il existe un y tel que pour tout x on ait $A$" laquelle s'écrit

$$ \dot{\Sigma}_y \dot{\pi}_x a(x, y) = 1 $$

La proposition (β) entraîne forcément (α). D'où l'inégalité

$$ \dot{\pi}_x \dot{\Sigma}_y a(x, y) = \dot{\Sigma}_y \dot{\pi}_x a(x, y) $$

Cette inégalité est une règle de logique.

Pour certaines formes de $a(x, y)$, on a

$$ \dot{\pi}_x \dot{\Sigma}_y a(x, y) = \dot{\Sigma}_y \dot{\pi}_x a(x, y). $$

De tels raisonnements permettent de voir par exemple la relation logique qui existe entre continuité simple et continuité uniforme.

## 5.3. LOGIQUE INTUITIONNISTE.

Nous avons vu le rôle fondamental joué dans l'algèbre de Boole par la relation

$$ \overline{a+b} = \overline{a} \cdot \overline{b} $$

qui suppose l'existence de la négation. Si on cherche à faire une logique plus générale que la logique classique on peut, au lieu de se rattacheter à des treillis distributifs avec complémentation (qui équivalent à l'algèbre de Boole), s'en tenir à des treillis distributifs. On ne définira pas $\overline{a}$ comme la solution du système

$$ a + x = T $$

$$ a \cdot x = N $$

mais comme le plus grand $x$ satisfaisant à

$$ a \cdot x = N. $$
ā est ainsi défini par

$$ \begin{cases} a.\bar{a} = N \\ (a. x = N) \text{ implique } (x \rightarrow \bar{a}). \end{cases} $$

Cet ā existe bien; il suffit pour le former de considérer tous les $x_i$ satisfaisant à

$$ a. x = N $$

et de poser

$$ \bar{a} = \sum x_i $$

Considérons maintenant $\bar{a}$, défini par

$$ \begin{cases} \bar{a}.\bar{a} = N \\ (\bar{a}. x = N) \text{ implique } (x \rightarrow \bar{a}). \end{cases} $$

Si dans la dernière relation nous remplaçons x par a, nous obtenons, au lieu de $a = \bar{a}$, la relation

$$ a \rightarrow \bar{a} $$

Passons maintenant à $\bar{a}$. Nous avons encore

$$ \bar{a} \rightarrow \bar{a} $$

et

$$ \bar{a}.\bar{a} = N $$

Par ailleurs, puisque $a \rightarrow \bar{a}$.

$$ a.\bar{a} \rightarrow \bar{a}.\bar{a} $$

$$ \text{Donc } \bar{a}.\bar{a} = a.\bar{a} = N $$

Nous en déduisons, en remplaçant x par $\bar{a}$ dans la condition définissant $\bar{a}$, que

$$ \bar{a} \rightarrow \bar{a} $$

Rapprochée de $\bar{a} \rightarrow \bar{a}$, ceci nous conduit à

$$ \bar{a} = \bar{a}. $$

Si donc la double négation n'équivaut pas à l'affirmation, la triple négation équivaut à la négation simple. Il n'y a pas là de paradoxe. Si en effet nous interprètons ā non pas comme a est faux mais comme a est démontrable faux, nous voyons que la correspondance entre a, ā et ā est la suivante :

<table><thead><tr><th>a</th><th>ā</th><th>ā</th></tr></thead><tbody><tr><td>démontrable vrai</td><td>démontrable faux</td><td>démontrable vrai</td></tr><tr><td>démontrable faux</td><td>démontrable vrai</td><td>démontrable faux</td></tr><tr><td>impossible à démontrer</td><td>démontrable faux</td><td>démontrable vrai</td></tr><tr><td>faux ni vrai</td><td></td><td></td></tr></tbody></table>

Nous voyons que a implique $\bar{a}$, au sens que si a est démontrable vrai, ā l'est aussi, mais que ā n'implique pas a. ā de son côté se révèle, si on prolonge le tableau, identique à $\bar{a}$ parce que toute proposition de la forme ā ne peut jamais se trouver dans le cas douteux.
Ce type de logique, dite logique intuitionniste, repousse le raisonnement par l'absurde. A l'usage, la tâche de construire des démonstrations directes, sans recours à l'absurde, s'est révélée si formidable qu'aucun traité systématique sur ces bases n'a été mené à bien, ce qui n'empêche que la question de la légitimité du raisonnement par l'absurde reste toujours actuelle.