Quelques résultats sur l’application de l’algèbre de Boole a la synthèse des circuits a relais

QUELQUES R]~SULTATS SUR L'APPLICATION DE L'ALGI~BRE DE BOOLE A LA SYNTHI~SE DES CIRCUITS A RELAIS

par Claude CARDOT Ingdn ieu r des P. T. T. *

SOMMAIItE. - - Utilisant l'alg~bre de BOOLE appliqude 5 la thgorle des dip$les constitu~s par les contacts de travail et de repos d'un certain nombre de relais, l'auteur expose un th6or~me original relati/ d la synth~se de dip61es patti- cullers appelgs r de parit6 : il est ainsi gtabli qu'une structure particulidrement simple de compteur de paritd est la plus gconomique possible ; une configuration plus gconomique que le moddle ggngral n'exlste que dans le cas particulier de trois relais. A~ant d'gtablir cette proposition, traitge dans la section I V de l'article, l'auteur a successivement, dans les sections prgcgdentes, rgsum~ les principes de l'alg~bre de BooLE, d'abord comme bases de la logistique puis comme procddd de calcul applicable 5 l'dtude des circuits de commutation glectrique ; puis rgsumd les rgsultats publids pat" C. E. SnAr~ON dans ce domaine, ll signale que les progr~s qui restent d accomplir d@endent dans une large mesure d'une orientation approprige des progris de la topologie. II exprime, pour terminer, le r qtte .r uni/ormisgs les notations et symboles ainsi que la terminologie dt utiliser en la maEire.

~ . - - L ' A L G E B R E DE B O O L E .

L'alg~bre de BOOLE fut d6velopp6e voici plus d 'un si~cle [1], pour fournir les bases d 'une analyse math6matique des op6rations logiques. Les t ravaux de BOOLE oat effectivement permis le d6ve- toppement de la logistique moderne. Nous rappe- Ions bri6vement ci-dessous les ~16ments de ,:e! outil math6matique :

1.~. - - [hm proposition quelconque, A, ~[ant donn6e, il lui correspond un symbole littgral, a, qui repr6sente tousles cas og la proposition consid6r6e est vraie. Ce symbole peut ~tre consid6r6 comme un op6rateur capable de s61ectionner, dans Fen- semble de tous les cas possibles dit ,r univers logique )), et dont le symbo/e est '1, les seuls ,'as oft A est v~rifi6e.

Le symbole d'addition plat6 eulre ceux de deux propositions distinctes t radui t la conjonetion ott (au sens inclusi[ de (( tout aussi bien que ,, (( tout au tant que )~, ct non pas au sens de l 'alternative), c'est-h-dire que l 'op6rateur (a F b) pr6lb~vera dans l'univers logique los cas oh l'une ou l'autre des propositions A, R (c'est-h-dirc au rnoins l 'une d'elh,s) sera v~rifi6e.

De m~me, le symbole de multiplication t radui t ]a conjonction el, c'est-~-dire que (a X b) repr6sentc l'ensemble des cas oh les deux propositions sont l'une et l'autre v6rifi6es.

La nggation d'une proposition peut se repr6senter par diff'.rents symboles : soil par ( l - x), soil par x', st)it par ~. Nons adoptcrons eeth'~ dcrni?~.re m)t:J- I ion.

Appliqu6e au syml)ole ], la n6gation conduit au symbole 0 (z6ro) ; ce symbole repr6sente naturellement la (( classe vide )), c'est-~-dire qu'il s'applique �9 ~ une proposition qui n'est jamais v~rifi6e.

Avec ces notations, le (( principe du tiers exclu ))

se t radui t symboliquement par ]es 6quations (qui se correspondent par dualit6) :

( i - l l ) a + a = t ( t o u t e s t " a " o u " n o n - a " ) .

(1-12) a. a = 0(rienn e s tg l a fo i s "a" et " n o n - a ' ) .

1.2. - - On ~tablit ais6ment, sur ces bases, que l 'additiou et la nmhiplication ainsi d6finies louis- sent des m~mes propri6t6s qu'en alg~bre ordinaire en ce qui concerne la commutativitd, l'associativitg (.t la distributivit&

Mais un certain nombre de r~gles partieulibres apparaissent ~galement, qui n 'existent pas en alg~bre ordinaire :

(l-t3) x = x + x = x + x + x + . . . , quel que soit le nombre n de termes 6gaux.

(1-14) x = x . x = x.x.x. . . , quel que soit le nombre n de facteurs 6gaux.

(Ces deux identit6s d' (( idempotence ,, qui se correspondent par" dualitY, expriment que la v6ra- eit6 d 'une proposition n'est, d 'aucune mani~re, modili6e par r6p6tition. Notons qu'il en r6sulte l 'absence de tout coefficient ou exposant num6rique dans les formules de l'alg6bre boolienne).

(t-15) i + .~ = 1.

(Cette identite, qui correspond par dualit6 ~ l'iden- tit6 famili~re 0.x = 0, exprime que rien ne peut ~tre ajout6 ~ l 'univers logique, celui-ci embrassant tousles cas possibles. Notons qu'il en r6sulte qu'en alg6bre boolienne il n 'y a pas plus de soustraction que de division.)

(1-]6) ( x + y ) ( x + z ) = x + y z .

(C'est une importante relation de distributi~,itd qui correspond par dualit6 'h la relation famili~re xy + x z - ~ x(y A-z). Elle s'6tablit en appliquant d 'abord celle-ci & deux reprises pour d6velopper le premier membre en quatre termes, puis en l'appliquant "h nouveatr en sens inverse, apr~s avoir rem-

* A la DtnE(:'r]oN DES SEav~cr:~ PtADIOI":LE(:TR1Q1;ES. [ ] P o u r t o u t renvoi entre crochets se r epo r t e r in fine h la b ib l iographle .

- - 7 5

2 / 1 0

plac6 x ~ par x en vertu de (1-16), pour mettre x en faeteur de i + y + z qui, en vertu de (1-15), est ~gal ~ i . )

Enfin, l 'op6rateur de n@ation (encore appel6 d'inversion), d6jh reneontr6 dans les formules (1-11), et (t-t2), jouit encore des propri6t6s suivantes qui permettent respectivement d'effectuer l'inversion d'une somme et eelle d 'un produit :

(t-t7) ( f - ~ ) = ~. -y (eequin 'es tn i"x"n i"y"es t la fois " n o n -x" e t " non -y ").

(1-t8) x.--y = x + y (ce qui n'est pas ~ la lois" x " et " y " est "non-x" ou " n o n - y " , c'est-~- dire au moins l'un des deux).

t.2. - - Interpretation g~om~trique. Ces symboles et leurs r~gles de caleul se pr~tent une interpr6tation g6om6trique tr~s simple dans

le langage de la th6orie des ensembles de points. I~tant donn6 un ensemble O~ de points (d'un espace absolument quelconque), nous pouvons d6finir sur les sous-ensembles de O~ les trois op6rateurs suivants :

l 'op6rateur d'union, exprim6 par le symbole U. Deux sous-ensembles A et B 6rant donn6s, le sous- ensemble AUB est l 'ensemble des points compris dans Fun ou l'autre des sous-ensembles A, B ;

l 'op6rateur d'intersection, exprlm6 par le symbole fl . Dans les mgmes conditions le sous-ensemble A [1 B e s t l'ensemble des points contenus h la fois darts A e t dans B ;

le compl~ment, exprim6, par le symbole ( 0 ~ - [...]). Le compl6ment d 'un sous-ensemble A, soit (P~ - - [A], est l 'ensemble des points de ~ qui n'appar- t iennent pas h A.

Si nous faisons jouer h ~ le r61e d'univers et si nous d6signons par | l 'ensemble vide, nous voyons

que les symboles 1, 0, + , x , (...), d6finis pr6c~- demment en (t . t) , sont rigoureusement soumis aux mgmes r6gles de calcul que les symboles ~R, @, U, f~, (O r - - [ . . .3 ) .

2 . - - A P P L I C A T I O N S A U X C I R C U I T S A R E L A I B .

2.1 . - - D f i f i n i t i o n s . - - N o u s appelons dipole tout circuit tell6 h deux bornes ext6rieures a et b e t comprenant des contacts actionn6s par un nombre quelconque de relais. Dans ce qui suit, nous supposerons que ces relais sont d deux positions : trauail et repos, et que les contacts sont soit de travail soit de repos.

Nous appellerons ~l~ment de transfert l 'association d 'un contact travail et d 'un contact repos du m~me relais, r6unis par une connexion ; il est bien connu qu 'un tel 616ment peut gtre r6alis6 en faisant l'6co- nomie d 'une lame mobile.

La propri6t6 pour le circuit ab d'gtre soit ouvert soit ferm6, selon la situation des relais qui interviennent dans le dipole, permet de traduire alg6- briquement la structure du dip61e par une fonction ~boolienne~ (c'est-~-dire susceptible de prendre les seutes valeurs 0 et t) d 'un nombre de variables 6gal

celui des reims qui interviennent dans le circuit.

C. C A R D O T [ANNALES DES TI~LI~COMMUNICATION$

Cette traduction alg6brique est possible de deux mani~res que nous estimons 6quivalentes, car, ainsi que nous le montrerons h la fin de ce chapitre, elles se prgtent h la mgme interpr6tation g6om6- trique.

2.2. - - La ~, Ionct ion de s tructure ,,.

Dans cet algorithme, on caract6rise l '6tat du circuit ab par la fonction, dite r162 fonction de structure ~,, qui est 6gale a I s i a b est ferm6 et h 0 si ab est ouvert. Cette fonction pr6sente donc une certaine parent6 logique avec une admittance, quan- tifi6e par tout ou rich.

]1 s 'ensuit que l'on doit repr6senter la mise en sdrie de deux contacts par l 'op6rateur produit, puisque, dans ces conditions, pour que ab soit ouvert, il faut et il suffit qu 'un des contacts mis en s6rie le soit. Inversement la raise en parall~le de deux contacts correspond h l 'op6rateur somme. L'inversion ou n@ation, correspond 6videmment au passage de travail h repos, de telle sorte qu 'un contact travail d'un relais A 6rant repr6sent6 par a, un contact repos du mgme relais sera repr6sent6 par 5.

C'est cette repr6sentation qui est adopt6e dans ]es t ravaux publi6s par les auteurs anglais [3], [4] ; russes [7] [8], ainsi que dans rart icle de M. SCHWAB publi6 dans ces colonnes [9].

2.3. - - La <~ I o n c t i o n - o b s t a c l e ~.

Le present expos6, provoqu6 par un travail de SHANNON [2], fait usage, comme les t ravaux am6- ricains, de la fonction-obstacle (hindrance function ou, simplement, hindrance), qui est inverse (au sens donn6 ci-dessus au terme ~ inversion ,~) de la pr6c6- dente.

La fonction-obstacle, analogue h une impddance, quantifi6e par tout ou rien, est par d6finition 6gale

t pour un circuit ab ouvert et h 0 pour un circuit ab ferm6. II s 'ensuit que la mise en sdrie de deux contacts correspond h l 'op6rateur somme, et leur mise en paraUble h l 'op6rateur produit.

La fonetion obstacle 6rant connue, pour con- naltre l '6tat du circuit dans une si tuation quelconque de l 'ensemble des relais composants, on remplacera :

- - pour tout relais X au travail, la variable x par z6ro et ~ par I ;

- - pour tout reims X au repos, ]a variable x par I et ~ par 0.

Ayant ensuite effectu6 le calcul de la valeur num6- rique de la fonction, eompte tenu de l 'application des rbgles (1.11) h (1.18), qui sont toujours valables, le circuit sera :

ouvert si le r6.~ultat final est I ; ferm~ si ce r6sultat est z6ro.

2.31. ~ Mode op6ratolre pour le calcul des fonctionsfobstacles.

Dans le tableau I, on trouvera les fonctions- obstacles de quelques dip61es simples.

- - 7 6 - -

t . 7, n o 2, 1952]

Les exemples (1) b (7) r6sultent, d 'une mani6re 6vidente, des r6gles donn6es ci-dessus. En ce qui concerne les exemples (8) h (10), on peut faire les remarques et formuler les r6gles suivantes.

]ABLEAU I

0ipo_!.t~ Fonct ion obstac le

0 (ferm~ en pema~cnce) (t) ae o b

(~) ao o b t (ouve r t en permanence)

(3) ao---z,---ob ~ ( t r a v a i l du r e l a i s x)

(a) ao-- -~-- -ob ~ ( repos du r e l a i s x)

(5~ a o - - X - - y - . - o b x + y (mise en s~r ie)

(6) ao -~__ j~ - -ob ,y (raise en p a r a l l , , e )

(7) X - - ~ : r = ~y + ~.~ ( d i s t r i b u t i v i t ~ )

=

a b

(IO)

t ( z , y ) = Ix+ flO, y ) ] [ ~ * f ( ~ , y ~ tD~veloppement en produit de fae teurs

ou "dgve loppe~ent -dgr iva t ion ' )

f ~ , y ) = ~ f ( 1 , y ) § ~f (O.y ) (D6veloppement en somme de termes ou d~veloppement-s~rie")

A P P L I C A T I O N D E L ~ A L G E B R E D E B O O L E 3/10

appeler (c d6veloppement-s6rie )) de la fonction-obstacle) a des propri6t6s qul correspondent par dualit6 h eelles du pr6e6dent ; il suffit de permuter, dans l'6nonc6 pr6e6dent, les mots produit et somme, [aeteur et terme, ainsi que les symboles I e t 0.

Ces deux d6veloppements permetteirt de bfitir des dipSles h structure sdrie-parallkle 6quivalents h bout dipSlc dont la fonetion-obstacle est eonnffe.

2.32. - - lnterprStation gdomStriqur

i~tant donn6 un dip61e h n relais, nous pouvons assoeier ~ ehaque relais une eoordonn6e susceptible d'avoir les valeurs 0 et I seulement. L'ensemble des situations possibles pour les n relais correspond ainsi aux N = 2- sommets d 'un cube ~ n dimen- sions. Cet ensemble de points peut ~tre appel6 avec les m~mes notations qu'en (t.2) ei-dessus. Dans ces conditions la [onction-obstacle apparalt comme un opdrateur de partition sur (~. Elle vaut t pour l'ensemble A des points de 0~ correspondant aux situations des n relais dans lesquelles le circuit

wont) ab est ouvert et 0 pour ]e sous-ensemble compl6- mentaire B de (P~ (la ]onction de structure a 6vi- demment les valeurs compl6mentaires h l'unit6).

Le hombre de partitions possibles dans un ensemble de N objets 6tant 2 z~', il en r6sulte que le nombre de [onctions-obstacles diff6rentes possibles, pour t o u s l e s circuits ~ n relais au plus est : 2 2"

I1 est h remarquer, en outre, que eette interpr6- ration demeurerait valable si, au lieu de relais 2 positions, nous consid6rions des (( r o t a t i f s , ou , unis6leeteurs, h u n nombre quelconque p d'6tats. Dans ce cas, l'ensemble ~ ne serait plus r6duit aux sommets du (( n-cube ~) mais eomporterait p- points r6guli6rement r6partis h l'int6rieur de eelui-ci.

Le nombre de fonctions de partit ion possibles sur un tel ensemble serait 6videmment 6gal ~ 2v ~.

La croissance extrgmement rapide de ces hombres en fonction de n montre la difficult6 de l 'analyse exacte des circuits poss6dant plus de trois relais.

Si nous adoptons le langage de la topologie (cf. [5]), nous pouvons 6noncer que le sous- ensemble A de ~ . est un invariant topologique particulier du r6seau D consti tuant le dipSle. C'est mgme le seul invarlant topologique dont la considbration soit utile si l 'on s'int6resse au comportement r6el du dip61e "~ relais.

Ce dip61e est topologiquement un ~( graphique ~>, c'est-h-dire un ensemble de sommets et d'arcs h une dimension. A notre connaissance aucune th6o- tie topologique actuellement existante ne permet de relier les caract6res topologiques classiques de ce t( graphique )), consid6r6 comme un poly6dre, avec l ' invariant ci-dessus d6fini.

En effet, les th6ories actuelles, 61abor6es princi- palement en vue de l'6tude des vari6t6s alg6- briques, reposent sur l'association aux figures g6om6triques (sommets, arcs dans le cas pr6sent), des 616ments d 'un groupe additi] tel que celui des nombres entiers, ou des entiers r6duits avec un

( 8 ) - - Circuit en pont. La fonction-obstaele s'obtient en faisant le produit des fonctions-obstaeles de tousles trajets possibles, sans point double, entre a et b. Cette r6gle est g6n6rale et s'applique ~ tous ]es dipbles.

(9) et (t0) - - Dd~,eloppements en produit de [ac- teurs et en somme de termes. Ces d6veloppements, dont la validit6 peut se v6rifier ais6ment, ont 6t6 sugg6r6s h BOOLE par la eonsid6ration du d6velop- pement en s6rie de TAYLOR qui, en analyse classique, permet d'exprimer une fonetion quelconque.

Le premier type de d6veloppement (que l'on peut appeler r d6veloppement-d6rivation )) de la fonc- Lion-obstacle) permet, par it6ration suecessivcment par rapport h ehaeune des n variables, d 'exprimer route fonction boolienne sous forme d 'un produit de 2" faeteurs : ehacun des facteurs est la somme de n termes 616mentaires pris ehacun dans les n paires (x, ~), (y, ~), ... et d 'un (n -F 1) i ~ terme eonstitu6 par la valeur que prend la fonction lorsque ces n termes 6]6mentaires sont tous 6gaux ~ 0 ; tous ceux des facteurs pour lesquels ce (n § 1) ~m~ terme est 6gal h t sont naturellement 6gaux eux-nl6mes ~ l , ce qui entralne la r6duction du d6veloppement au seul produit des autres facteurs (dans lesquels le (n -4- l) i~me terme est nul).

Le second type de d6veloppement (que l'on peut

- - 7 7 - -

4/10

nombre premier pour module, ou des nombres rationnels, etc. ; mais aucune th6orie n'est basi:e sur l 'ensemble des nombres 0 et t avec la r~gle boolienne I + I = t.

Par exemple, les deux dipSles de la tigure I sont Squivalents du point de vue de la pr6sente 6tude,

" , - . L J y- ' ' Fro. I. - - Seh6ma en pont et seh6ma ~quivalent en

s6rie-d6rivation.

alors que la topologie classique les consid~re comme tr~s diff6rents (le premier poss~de deux cycles, le second en poss~de trois).

Nous pensons que le d6veloppement d'une base topologique appropri6e permettrai t de s 'a t taquer aux probl~mes signal6s ci-dessus et notamment :

a) 6tant donn6 un dipble, t rouver sa fonction- obstacle par une op6ration autre que l'6num6- ration exhaustive des trajets possibles (op6ration mat6riellement tr6s difficile pour les r6seaux d'une certaine complexit6) ;

b) 6tant donn6 une fonction-obstacle, trouver le type de structure ~ le plus 6conomique ~ pour sa r6alisation.

3 . - P R O B L ~ M E S DE SYNTHIs DE DIPOLES.

3 . 0 - La synth~se d 'un dipSle dont la fonction- obstacle est donn6e est possible d 'une infinit6 de mani~res. Le technicien se trouvera prat iquement devant l 'un des probl6mes de minimum suivants :

a) t~conomie maximum de contacts. - - On devra chercher le sch6ma comportant le plus petit nombre total d'616ments (contacts de travail ou de repos).

b) I~conomie maximum d'armatures mobiles. - - Ce probl~me est distinct du pr6c6dent en raison du fait qu'une armature mobile peut fournir un contact de travail et un contact de repos reli6s ensemble (616ment de transfert). On cherchera donc dans ce c a s h juxtaposer les contacts de naturc oppos6e du mgme relais.

c) Charge minimum, soit du relais le plus charg6, soit d 'un sous-groupe de l'ensemble de relais consi- d6r6 (cas oh il y a, par exemple, un ou plusieurs relais rapides dont le nombre d 'armatures est limit6).

Pour un t rai tement syst6matique de ce genre de probl~mes, il est d 'un int6rgt primordial de con- naltre le comportement, au moins approximatif, des fonctions non d6croissantes suivantes :

L (n ) : plus petit entier tel que tottte fonction- obstacle h n variables puisse etre r6alis6e avec L(n) ~16ments.

M(n) : plus petit entier tel que toute fonction- obstacle de n variables puisse gtre r6alis6e avec M(n) 616merits sur le relais le plus charg6.

C. CARDOT [ANNALES DES TI~L~COMMUNICATIONS

II est ais~ de d6terminer les valeurs de L(n) et M(n) lorsque n e s t 6gal h I ou h 2 :

L(I) M ( t ) = l ;

L(~)= 4; M(~) = ~.

Pour n quelconque, l '6tude complete pr6sente de grandes difficutt6s. Nous donnons ci-apr~s en (3.1) ct (3.2) ]es r6sultats acquis par C. E. SHANNON [2] pour 6tablir : soit une limite sup6rieure de L(n) si n e s t faible (n = 3, n = 4) ; soit le comportement asymptotique de L(n).

3 . I . - ..... L i m i t e s s u p 6 r i e u r e s d e L(n). 3.10. ,-- Par u n e mgthode particuli6re de syn-

th6se, utilisant le (( d6veloppement-d@ivation )) et fond6e sur le th6or~me 6nonc6 ci-apr~s en (3.11), on peut 6tablir les r6sultats suivants dans les cas off n = 3 e t n ~ 4 .

Thdor~me. - - Dans le cas de 3 variables, toute fonction-obstacle peut ~tre r6alis6e avec les charges respeetives de 2, 2, 4 616ments par relais, dans n'im- porte quel ordre d6sir6. De plus, ces 616ments peuvent ~tre group,s par deux en l , t , 2 616ments de transfert.

Ce th6or~me fournit la limite L(3) ~ 8 ; on peut montrer facilement que l'dgalitd est rdalisde. Quant h la quantit6 M(3), on d6duit de ce r6sultat qu'elle est inf6rieure h 4 ; en fait, sa valeur est 3 (ce qui prouve que le r6seau le plus 6conomlque, quant au nombre total d 'armatures pour une fonction donn6e, n'est pas n6cessairement celui qui fournit la moindre charge du relais le plus eharg6).

Dans le cas de 4 variables : on 6tablit de m~me que L(4) ~< i4.

3. i] . - - Tous ces r6sultats reposent sur l'appll- cation de la propri6t6 suivante :

Thdor~me. - - Soient deux r6seaux M ct N de la forme indiqu6e (fig. 2), M ayant les fonctions-obs-

I I

I

FIG. 2,

tacles Uj entre la borne a et la borne j, N ayan t de mgme les fonctions-obstacles Vi entre j et b. Suppo- sons de plus que Fun de ces deux r6seaux, M par exemple, soit dis]oncti/, c'est-h-dire ait une fonction- obstacle identiquement 6gale h l 'unit6 pour tout t rajet entre deux bornes autres que a. Si l 'on r6unit borne h borne ces deux r6seaux, alors la fonction- obstacle du dipSle obtenu est :

k = n

/~b = II (u~ + v~). k = l

Ce th6orbme r6sulte de la consid6ration de tousles trajets possibles entre a et b, ceux qui traversent

- - 7 8

t. 7, n ~ 2, 19521

plus d 'une lois la ligne de jonction ayant une fonction-obstacle unit6.

D~s lors, pour faire la synth6se de toul es les fonctions possibles d 'un certain hombre de variables, on construit deux r6seaux tels que l~I et N, dont Fun soit disjonctif, et tels que l 'on pnisse r6aliser toutes les fonctions possibles, simplemenl en modifiant l 'ordre des connexions, mais non les r6seaux.

3.2 --- • asymptot ique de L(n). 3.20. --- Thgor~me. - - Un r6seau N,,, (nou-dis-

jonctif) donnant entrc a et ses b~,rnes de droitc (fig. 3) toutes les fonctions-obstacles de ~t variables

au plus (soit 22" fonctions) est r6alisable avec

22~ "~" 2 616ments. Raisonnant par r6currence, la propri6t6 ~tant

vraie pour N~, supposons que le r6seau N~ dc la figure 3, comportant n relais, jouisse de cette pro-

pri6t6 entre la borne a et les 22~ bornes marqu6es /

o~,

o~ ---r

l:m. 3.

APPLICATION DE L 'ALGEBRE DE BOOLE 5 / 1 0

suivants, relatifs ~ l'ordre d'infinitg de L(n) pour n grand :

a) Le proc6d6 de <~d6veloppement-d6rivation, (tableau I, cas 9) nous donne le moyen de faire la synth~se de toute fonction / par un arbre compor- rant 2 n+~ -o 2 616ments et dont toutes les bornes de droite sont r6unles ~ b. Cet arbre est disjonctlf. L(n) est done born6 par 2 n+~. S HAt, NON donne la limite meilleure L(n) ~< 2~-~ . 3- t8, d6duite de la consid6ration des arbres donnant toutes ]es fonetions de 2 variab]es.

b) Si nous arr~tons le processus precedent apr~s avoir utilis6 n---m variables, nous pourrons remplacer la partie non d6velopp6e de l 'arbre par un r6seau N du type pr~c6dent donnant toutes Its fonctions des m, variables restantes, l 'arbre disjonctif initial jouant le r61e de r6seau M (fig. 2). Dans ces conditions, nous voyons que le nombre d'616ments sera :

2n-~+ 1 -- 2 + 2.2 s~ < 2~-~+ 1 + 21+ v~.

sa droite. Dessinons, h droite de ces derni6res, une

rang6e de 22~+~ bornes g auxquelles nous assi-

gnerons les 22n+1 fonctions de (n - t - 1 ) variables au plus. Chacune de celles-ci, soit gl 'une d'elles, peut se d6velopper sous la forme :

g = (X'n+l -~- /)" (Xn+l ~- [ ' ) ,

/ e t / ' 6tant deux fonctions de n variables au plus. Nous pouvons donc construire le r6seau l~l~+x par t i r du r6seau 1~1~ en reliant chacune des bornes

rajout6es ~ deux homes du r6seau primitif, par deux 616ments au total comme le montre la figure.

Ce faisant, nous avons ajout6 2 x 22n+1 616- ments suppl6mentaires ~ ceux de Nn.

Mais dans les fonctions de n § ~ variables au plus, figurent les fonctions de n variables au plus,

qui sont au nombre de 22n. Pour chacune de celles- ci les fonctions / e t / ' qui interviennent dans la for- mule pr6c6dente sont 6gales, ce qui permet de supprimer une paire d'616ments x,+i, ~+~ en parall~le et de la remplacer par une connexion directe pour relier la borne g h la borne correspon-

dante f. Nous avons ainsi supprim6 2 X 22n 616- ments suppl6mentaires, c'est-h-dire au tan t qu 'en contient lVI., de sorte que le nombre total d'616-

ments de N~+~ est bien 2 x 2 2=+~.

3.21. - - De ce th6or~me on d6duit les r6sultats

Ce nombre passe par un minimum pour m 6gal au plus grand entier v6rifiant : n >~ m A- 2"~.

m est born6 par log2n et il en r6sulte que le nombre L(n) est bornd par (2"+3/n), c'est-h- dire qu'il est infini comme (2 ~/n), cette limite 6tant 6videmment meilleure que la pr6c6dente pour les grandes valeurs de n.

3.22. - - Si l 'on appelle cornplexitg d'une fouction (de n variables) le rapport du nombre minimum d'616- ments n6cessaires pour sa r6alisation la plus 6co- nomique, au nombre L(n) qui correspond h la r6ali- sation la plus 6conomique de la fonction (de u variables) la plus cofiteuse, il est int6ressant de se demander si la plupart des fonctions sont simples ou complexes. Se basant sur le d6nombrement des r6seaux que l 'on peut construire avec un certain nombre d'616ments donn6s, SHANNON 6tablit que presque toutes les fonctions exigent au morns 2"/n 616ments, et il estime que, en fait, la complexit6 d 'une fonction prise au hasard doit ~tre de l'unit6.

Les fonctions (( simples )) sont donc une tr~s peti te fraction du total des fonctions possibles ; cependant , de m~me que les nombres transcendants, qui sont math6mat iquement la presque totalit6 (au sens du calcul des probabilit6s) de tous les nombres, se ren- contrent rarement en pratique, de m6me les /onctions-obstacles des circuits r@ondant ~ un but pratique peuvent g6n6ralement ~tre construites avec un nombre d'616ments bien moindre que les maxima d6finis ci-dessus. I1 est donc int6ressant 6galement de d6terminer des bornes inf6rieures pour les quantit6s L(n), M(n) et d '6tudier les dip61es correspondants.

~. - - ~ T U D E DES COMPTEURS DE PARITI~.

Pour t rouver une borne inf6rieure des quantit6s L(n) et M(n), nous allons construire une famille r6currente de dip61es 0~ ~ n relais n6cessitant au

I 7 9 - -

6/10

moins ( 4n - - 4 ) 616ments, dont 4 sur le relais le plus charg6, pour n sup6rieur h 3.

Ces circuits ou compteurs de paritd ne sont autres que les cireuits (( va-et-vlent )) ou (( permutateurs ,, bien connus des 61ectriciens.

4.1. - - D~flnitions. - - Le compteur de paritd est un dipble dont l '6tat t radu i t la parit6 du nombre de relais excit6s (il est utilis6 dans les installations d'6clairage en raison du fait que l 'on peut agir sur l '6tat du dip61e h par t i r d 'un relais quelconque, quel que soit l '6tat des autres relais).

D6finissons la fonction

c~ : xl @ x2 ~ �9 .. @ x~

par les relations de r6currence :

C 1 = X 1

C 2 : X l ( ~ X 2 = X 2 . X , "-~ X 2 . X I ~___ (X 1 -~ X 2 ) ( X 1 --~ X 2 ) ,

c3= x, | x2 | xs= x3. c2 + x3.c2

= X 1 X 2 X;~ 2[_ Xl X2 X3 "t- X 1 X2 X3 -t- Xl X 2 X 3.

On+ 1 = Xn+ 1 �9 Cn -J- X n + 1 . Cn.

Le d6veloppement de c, en polyn6me se compose de 2 "-1 termes, c'est-h-dire de la moiti6 des 2" termes dont la somme constitue le d6velop- pement de l 'unit6 par rappor t aux n variables : ce sont ceux dans lesquels celles de ces variables qui in tervicnnent sous leur forme naturelle (c'est-h-dire sans le signe de l 'inversion) sont en nombre impair.

La fonetion ~,~, inverse de c,~, d6velopp6e 6ga- lcment en polyn6me, se compose de l 'autre moiti6 des termes, c'est-h-dire de ceux dans lesquels celles des variables qui in terviennent sous leur forme naturelle sont en nombre pair.

Tout dip61e dont la fonction-obstacle est l 'une des fonctions du type c,~ ou ~ est un compteur de paritd. Nous supposerons dans ce qui suit, que les quantit6s L(n), M(n) sont les minima d6finis comme ci-dessus (w 3.0) mais seulement sur les fonctions du type en question, et non plus sur l 'ensemble des fonctions de n variables. Cette restriction est 16gi- t ime puisque nous cherchons des bornes inf6rieures de ees quantit6s. De plus, un compteur de parit6 C,~ 6tant donn6, nous utiliserons les /onctionnelles suivantes de ce dip61e :

G~, ou G (C,,) : nombre total d'616ments de contact dans C~ ;

K~, ou K(Cn) : n o m b r e d'616ments sur lc relais le plus eharg6 de Cn.

On a 6videmment :

G,,>~L(n), K,~>~M(n),

puisquc L et M sont les minima de G et K pour tous |es compteurs de parit6.

4.2. - - Proprifit~!s d e s e o m p t e u r s de par i t& - - Tout compteur h n relais pr6sente les propri6t6s suivantes :

4.20 - - En immobilisant un relais, on obtient un des compteurs possibles h n - - I relais. On passe

C. C A B D O T [ANNALES DES TI~LI~COMMUNICATIONS

de ce compteur au compteur inverse en changeant la position du relais immobilis6.

4.21. - - Tout circuit reliant les borncs terminales passe par un contact au moins de chaque relais (h moins qu'il ne soit ident iquement ouvert) .

Supposons, en effct, qu 'un t ra je t relic a h b sans passer par un contact du relais Xi (et sans gtre ident iquement ouvert .) Cela revient h dire qu'il y a au moins une position des relais autres que X~ pour laquelle il est ferm6. Pour cette position, X, n'a plus d' influence sur l '6tat du dipble, ce qui contredit la d6finition.

4.22. - - Dans un compteur de parit6, tout relais poss~de au moins un contact de repos et un contact de travail.

Supposons, en effet, que X, par exemple n 'ai t pas de contact de travail . I1 existe au moins une posi- t ion des autres relais pour laquelle X, 6tant au travail, ab dolt gtre ferm6. Mais pour cette position, lc chemin ab ne saurait exister puisqu'en ver tu de (4.21) il doit emprunter un contact de X~ et qu'au- cun d 'eux n'est 6tabli.

4.23. - - On a l'in6galit6 :

L(n) >~ L(n-- 1) + M(n).

Consid6rons, en effet le compteur C* pour lequel le nombre G, est :

G(C~*) - G* = L(n).

Le relais (ou l 'un des re]ais, s'il en existe plusicurs) lc plus charg6 poss6de un nombre Kn d'6i6ments 6gal h :

K(C*) = K~* ~> M(n).

Bloquons ce relais. Nous obtenons un C*~-1 dont le nombre d'616ments est :

* = * * L ( n ) * d'ofl : G,,_ 1 G~,- K~ = -- K,, >~ L(n -- 1);

L(n) >~ L(n-- l) + K* >~ L(n-- l) + M(n).

4.3. - - C o m p t e u r s ~ tro i s re la i s a u p lus .

La figure 4 indique les deux configurations possibles d 'un compteur h deux relais ; une configu- rat ion plus 6conomique est impossible, puisque tou t compteur de parit6 doit avoir deux contacts par relais au moins (4.22).

La figure 5 indique les deux types possibles de

F: '1 E:S a o ab ao ob

7 y | |

F I G . /t. - - lab = X (~ y .

compteurs h trois relais ; on pcut en d6duire un grand nombre de circuits 6quivalents.

I1 est tr~s facilement d6montrable que la cons- t ruct ion d 'un C3 est impossible avec 7 616ments. I1 en r6sulte que chacune des configurations de la figure 5 est une configuration minimum :

- - le sch6ma 5-1 est un compteur h 8 616ments

- - 80 - - -

t. 7, n ~ 2, 1952]

au total (6 616ments de transfert), dont 4 (2 616ments de transfert) sur le relais le plus charg6.

C'est pour cette configuration que G3 assume sa valeur minimum, L(3) = 8.

- - Le sch6ma 5-2 est uu compleur h 11 616ments au total (3 616merits tic t ransfer t L 3 616ments

�9

1:~. 5. -- i,,, - .v @ !t t4~ :.

simples), off la charge du relais le plus charg6 n'cst que de 3 616merits (1 616ment de t ransfer t + I 616- ment simple).

C'est pour ce type de configuration que K 3 assume sa valeur minimmn, M(3) = 3.

I1 y a lieu de remarquer que la contiguration 5-1 est imm6diatement g6n6ralisable et fournit le sch6ma (fig. 6~ d 'un compteur de parit6 ~ u n nombre

FIs. 6. -- [d, ..... J : l @ .c., (# .... ~ . % .

queleonque de relais (va-et-vient classique, h permutateurs) . Cette derni~re configuration est applicable sur la sur[ace d 'un tore, a et b 6rant suppos6s r6unis.

Quant au type 5-2 ; on remarque qu'/I l 'oppos6 du pr6c6dent, il est applicable sur un plan, dans les m~mes condit ions. Notre d6nlonstration 6tablit pr6cis6ment qu'il n 'est pas g6n6ralisable pour un nombre sup6rieur de reims.

4.4. - - Compteurs A plus de trois relais. - Le r6sultat que nous nous proposons d'6tablir peut s '6noncer ainsi :

4 . 4 0 . - T h ~ o r ~ m e . - Un compteur de parit~ it n relais est irrgalisable avec moins de (6n - - 4 ) ~lgments si n e s t au moins @al /t 6. Aut rement dit : L(n) > / 4 n - - 4.

I1 r6sulte de l'in6galit6 (6.23) que, si la proposit ion cst 6tabiie pour une valeur de n et qu 'en outre M ( n ) / > 4 pour cette valeur, le th6or~me est vrai pour toutes les valeurs plus 61ev6es de n, en raison du caract~re non d6eroissant de L(n) et M(n) .

Pour n = 4 , 4 n - - 4 = 12. Comme nous avons 6tabli (en 4.3) que L ( 3 ) = 8 et M ( 3 ) = 3, nous savons d~j~ que L(4) >~ L(3) + M(4) est au moins 6 g a l h 8 + 3 = l l , pu i squeM(4)>~ M(3). I1 nous

APPLICATION DE L'ALGEBRE DE BOOLE 7/10

sutfira done de d6montrer que M(4)>~ 6, ce qui 6quivaut h l'6none6 suivant :

6.61l. - - II est impossible de construire un compteur de paritg ayant 3 ~lgments pat" relais au plus, pour n supgrieur it 3.

D&nonstration. - - Supposons que, contrairernent h notre proposition, puisse ~tre construi t un compleur de parit6 jouissant de la propri6t6 6nonc6e. I1 a au moins 11 616ments, r6partis h raison de 3 pour chacun des trois premiers relais et de 2 ou 3 pour le dernier. Bloquons d 'abord celui-ci sur travait : nous obtenons IIIt C~ "~l 3 relais et 3 616ments par relais. Bloquons maintenant le m6me relais sur repos. Nous obtenons alors, avec les mgmes relais restants que pr6c6demment, un compteur C* inverse du pr6- c6dent ; nous allons 6tablir que c'est lh que r6side l'impossibilit6 ; au t rement dit que si, avec 3 relais ayan t chacun 3 616ments, on peut construire un C3,

on ne peut pas, avec les m~mes reims, construire 0 3 inverse du pr6c6dent.

Supposons donc que nous soient donn6s les 3 reims repr6sent6s sur la figure 5-2. Ce cas est le plus g6n6ral possible, puisque nous savons que t o u s l e s relais ont forc6ment des contacts des deux esp6ces, donc ici, par exemple, un contact de repos et 2 contacts de travail chacun. Avec ces trois relais on peut construire le compteur de la figure ; on ne peut pas construire le compteur inverse c'est-h-dire le dipSle qui entre a et b offrirait les seuls trajets : ~ c - ? y + z , ~r + . ~ + 2., s . v + y + L En cffet cette construction implique contradict ion dans tous les cas possibles :

(a) Supposons d 'abord qu'aucune des borrtes terminales a et b ne soft relide gt un contact de repos : Dans ce cas, la possibilit6 des trois derniers trajets, x + ~ + z , .v + ~ + z , Y : + g + ~ , implique que chacune d'elles soft reli6e h u n contact de travail de chaque relais. Mais alors, les 6 contacts de travail disponibles 6tant directement connect6s ~ a et b, le t ra je t x + V + zes t devenu impossible h r6al[ser.

(b) Supposons nlaintenant qu'une des bornes terminales a, pat. exemple, ne soft relige it aacun contact de repos : Le ralsonnement pr6c6dent montre que a est alors reli6e '~ 3 contacts de travail diff6- rents (fig. 7). La borne b, qui est reli6e h un contact

' T " - ' - b

ok:_-: ~-~3 |

l:l~. 7.

de repos par hypoth~se, soft x, dolt 6galement 6tre reli6e h un contact de travail au moins, pour permet t re le t ra je t x -4- y + z.

(b.1) Envisageons d 'abord le cas (fig. 7-1), off b n'est pas r6unie h u n travail et h u n repos du m~me relais. Soft y le contact de travail auquel est reli6e b. Le trajet ~ + y -F k impose que le contact ~, qui est unique, soft situ6 entre les points marqu6s

8/10 Bet 4, et non ailleurs. D~s lors, le trajet x W ff q- impose que b, qui n'est pas reli6e h l 'unique contact ~', soit reli6e soit h ~ soit h x, ee qui, dans un cas comme dans l 'autre, nous ram~ne au cas, exctu par hypoth~se, oO b e s t reli6e h deux contacts diff6rents du m~me relais.

Remarquons, en outre, que lc premier des deux cas envisag6s ci-dessus, h savoir que b, d6j~ reli6e

~, soit 6galement reli6e ~ ~, est impossible : aucune des bornes a ou b ne peut ~tre reli6e ~ dcux contacts de repos, ~ et y, sous peine d'interdire la r6alisation du tra.jet ~ q- y -~ z comportant ces deux contacts uniques en s6rie.

(b.2) La borne b est reli6e h u n COiltact de travail et h un contact de repos du m~me relais, soit x (fig. 7-2). Le contact x est le seul contact de repos auquel puisse gtre reli6e b, en vertu de la remarque qui pr6c~de. Le trajet x -4- .~ q- z implique que ~) et

soient en s6rie entre les points 1 et 4 de la figure 7-2, dans un ordre que nous pouvons supposer gtre celui de cette figure.

Consid6rons alors le t rajet ~ + y q- ~. I1 se termine n6cessairement en a sur y, c'est-h-dire au point 2. Ce point dolt gtre reli6, soit directement, soit encore par un autre contact y en s6rie, h l 'une des extr6mit6s 4 ou 6 du contact unique L Dans les deux cas cette connexion est interdite, car elle viole la condition (4.21) ou cr6e un trajet exclu x -}- y A- z.

(c) Supposons enfin que les deux bornes a et b soient relides chacune & un contact de repos (fig. 8) : Le trajet x - t - y A-z se termine n6cessairement

Fro. 8.

en b sur y, puisque cette borne ne peut ~tre reli6e h 2 contacts de repos. Le contact unique ~ est donc reli6 au point tb comme figur6. De m~me le trajet x q- y q- z se termine n6cessairement en a sur x. D~s lors l 'extr6mit6 2 de ee dernier contact doit gtre reli6e, pour permettre ee dernier trajet , soit diree- tement, soit encore par un autre contact x en s6rie, h l 'une des extr6mit6s 4 ou 5, de l 'unique contact ~. Dans les deux cas cette connexion est interdite, ear elle viole la condition (4.21) ou er6e un trajet exclu x -}- y -t- ~. c . q . f . d .

4.5 - - C o n c l u s i o n s de c e t t e 6 tude . - - Les r6sul- tats pr6c6dents nous permettent de circonscrire le comportement de la fonction L(n), pour l 'ensemble des dipbles h n relais, entre :

- - u n e borne supdrieure, r6sultant des valeurs donn6es en (3.2) ; en particulier, cette limite est la plus petite des deux quantit6s : (2~-1 + 18) et 2~+3/n ;

- - une borne in[6rieure, 6gale "h (4n - - 4) et r6sul- t an t de la constitution d'une famille de circuits d6finis dans le pr6sent paragraphe et n6cessitant effectivement ce nombre minimum de contacts.

C.. C A R D O T [ANNALR$ DES TI~LI~CO}tn~rUNI.CATION$

On volt que, dans l '6tat actuel de nos connais- sances, le comportement exact de L(n) est encore tr~s largement ind6termin6, et cela d 'au tant plus que n e s t plus grand.

Mgme pour n - 4, nous ne savons pas actuel leinent laquelle des trois valeurs possibles 12, 13, t4 est effectivemeut le nombre minimum d'616ments permet tant ]a r6alisatiou de routes les fonctions de 4 variables. En particulier personne n'a, h notre connaissance, fourni d'exemple de fonctions de 4 variables qui soient irr6alisables avec moins de 13 contacts.

~). P R O B L E M E S D E D I S T R I B U T I O N

D E C H A R G E D E S R E L A I S .

5.t. - - Ce probl~me comprend, cn particulier, l '6tude du comportement de la fonction M(n). Les r6sultats 6tablis aux paragraphes pr6c6dents nous fournissent la valeur sfire M ( 3 ) = 3, et la limite inf6rieure M(n) >~ 4 pour n au moins 6gal ~ 4.

5.2. - - SUANNON 6tablit que, parmi routes les r6alisations possibles d 'une m~me fonction avec un nombre total donn6 d'616ments, il est possible, dans presque t o u s l e s cas, de trouver une r6alisation particuli~re conduisant h une rdpartition presque uni- [orme de ces 616ments entre tousles relais qui apparaissent dans la fonction consid6r6e.

En particulier, consid6rons (fig. 9), non pas un dipSle, mais l 'arbre disjonctif de la figure 9-I,

FIG. 9.

donnant entre ae t les bornes 1 h $ toutes les sommes telles que x + y -t- z (avec un nombre quelconque de barres d'inversion). La charge respective des relais X, Y, Z e s t 2,4, 8 616ments.

En 6changeant le rble des relais Y et Z dans la partie inf6rieure de l'arbre, nous obtenons celui de la figure 9-2 qui lui est rigoureusement 6quivalent et dont ]a distribution est (2, 6, 6). A partir de la distribution initiale (2, 4, 8), nous avons donc fait passer deux unit6s du plus grand nombrc au nombre voisin. La t ransformation inverse 6tant impossible en g6n6ral, il y a lh un principe d'unifor- misation que SHANNON compare au flux irr6ver- sible de chaleur d 'un corps chaud sur un corps froid, et auquel il applique la th6orie des nombres additi/s, qui n'est autre, dans le cas particulier pr6sent, que l '6tude de l'ensemble des distributions 6quivalentes h la distribution donn6e. Les arbres disjonctifs du module 9-1 ayant d6jh 6t6 utilis6s pour effectuer

- - 8 2 - -

7, n o 2, 1952]

la synth~se d'cnscmbles de fonctions quelconques (ef. w 3.1), on peut ais6ment d6duirc de cette th6oric le r6sultat suivant :

M(n) est inf6rieur h 2~+'~/n~. Si l 'on rapproche ce r6sullat de la limile obtenue

(w 3.21) pour L(n), soil : 2"~'~/n, on volt que ee r6sultat signifie que, s'il existe une fonction de n variables n6cessitant pour sa r6alisation ce nombre total d'616ments, alors il y a une r~alisation de cetle fonction pour laquelle la charge peul 6tre unifor- n~6ment r6partie entre tous les relais.

(~) . F O N C I I O N S PARY1CI LI I~RE5 .

Nous avons signal6 ci-dessus lw 3.22) que les fonctions que l 'on r6alisait prat iquement , sur tout pour un nombre 61ev6 de relais, dans les 6qui- pements de t616eommunications ou de t616eom- mande, n6cessitaient beaueoup moins d'616ments que les fonetions les plus g6n6rales possibles, la raison en 6tant qu'elles n '6taient pas des fonetions queleonques, mais qu'elles pr6sentaicnt quelques particularit6s de nature h simplifier leur r6alisation, partieularit6s r6sultant d'ailleurs du fait qu'elles sont destin6es h satisfaire h un besoin logiquement exprimable ((~ programme )) du constructeur). Les prineipales partieularit6s de cette nature son t :

(a) La ddcomposabilit& C'est le eas d 'une fonetion [(Xl, x2, ... x,,) pouvant 6tre raise sous la forme :

t - g Lt,(:,:,, :~:~,... :~0 ;:~'~ ~, .... :,,,i.

Il est bien 6videnl, dans ce cas, quc le problSme de synth~se de ]a fonction [ se scinde en deux pro- blSmcs : 6tablir un dipble h s relais de fonction-obstacle h, et effectuer la synth&se de la fonction g dans laquelle h apparMt comme une seule variable ; c'est-h-dire que la fonction g cst "h (n - - s ~- 1) variables.

(b) L'invarianee vis-h-vis de t ransformat ions appar tenant h certains groupes op6rant sur l'ensemble des variables.

Un eas typique est l ' invariance de la fonction vis-h-vis de la sym6trie op6r6c sur un certain nombre des variables o u des inverses de ces variables. Pour la quasi-totalit6 des fonetions possibles, le groupe d ' invarianee n'existe pas, mais eu fait, pour un grand nombre des fonctions r6ellement utilis6es, on se t rouvera cn pr6sence d 'un tel groupe : on pourra alors appliquer le th6or~me suivant, dfi h SHANNON :

Toute [onction de m ~- n variables, symgtrique par rapport it m d'entre eUes, peut ~tre rgalisde avec un uombre maximum du qui est le plus petit des deux nombres :

(m + l ) . [L (n) + m] et ( m + l ) . ( 2 ~ + m - - 2 ) + 2 .

En particulier toute [onction de n variables, symJ- trique par rapport it n - - 2 aa moths d'entre elles, peut ~tre r~alis~e avec (n ~ - - n + 2) dldments au maximum.

A P P L I C A T I O N D E L ~ A L G E B R E D E B O O L E 9 3 0

7 . " ..... ( ' ,ON CLU SIO N GI~NI~RALE.

Lc lecteur n'aura pas 6t6 sans remarquer d 'une part la difficult6 el lc caract~re compliqu6 de cer- talus des raisonnements n6cessaires pour 6tablir des d6monstrations rigoureuses darts ce domaine, de l 'autre le fait que tous les circuits que nous savons manipuler commod6ment, ou peu s'en faut, sont du type (( s6rie-parall61e )). Dans les t ravaux jusqu'ici publi6s, on trouve bien quelques tenta- lives d 'analyse de circuits qui ne sont pas de ce type (voir, par exemple, SCHWA, [91 , w 6,/ : circuits d6riv6s du pont), mats nous ne poss6dons pas actuellement de m6thode g6n6rale d 'approche des circuits cornportant un hombre quelconque de liaisons internes arbi t ra i rement dispos6es. Cela nous paralt pouvoir 6tre reli6 h l 'absence (signal6e ci-dessus, w 2.32 in fine) d'une th6orie topologique appropri6e.

Les r6sultats d6jh acquis sufl]sent pour tan t montrer l'intgr~t pratique des perspectives ouvertes h ce proc6d6 d'alg6brisation de l '6tude des circuits. Les divers exemples d 'applications que l 'on peut t rouver dans les articles cit6s en bibliographie (voir no tamment les deux cas 6tudi6s en d6tail h la fin de [9]) suffisent h montrer que l 'outil a prise sur les probl~mes concrets qui se poseur aux ing6- nieurs et techniciens de la commutat ion. C'est dire l'int6r~t qu'il y a h am61iorer cet outil, et c'est pour- quoi notre conclusion sera que les math6ma- ticiens ont, en cette mati~re, l 'occasion de rendre aux ing6nieurs 61ectrotechniciens un service dont l ' importance pourrai t ~tre comparable ~ celle qu'a acquise actuellement l 'application prat ique des r~gles du calcul dit (( symbolique ~)ou (( op6ra- t ionnel )).

Pour terminer, nous exprimerons le weu que soit r6alis6e le plus t6t possible une normalisation des notations et symb01es et de la terminologie h utiliser dans ce domaine. Selon les auteurs, la m~me op6ration qui fait correspondre h la variable x la variable y telle que x.y = 0, x - t - y = t, s'appelle c( inversion ,, (( r6ciprocation ,, (( n6gation ,... (y est aussi appel6 c( compl6ment )), ou encore (( d u a l , de x), et s 'exprime par les symboles [ 1 - - x ] , x ' , x,... D 'autre part , nous avons vu qu 'un dip61e form6 de contacts peut se caract6riser par une (( fonction de structure )~ ou une (( fonction-obstacle )~ ((( hindrance function ))) : certains auteurs n'util isent que la pre- miere h l 'exclusion de la seconde, d 'autres font le choix contrairc ; leurs r6sultats sont certes 6qui- valents, puisqu'ils se ram~nent les uns aux autres par simple dualit6, mats il est assez g6nant, en pratique, que les m~mes sch6mas aleut ainsi deux formulations algbbriques diff6rentes selon les auteurs. A vrai dire, la dualit6 en question existe dans les structures m@aes des sch6mas, ce qui justifie la coexistence des deux fonctions caract6- ristiques : suivant les cas c'est l 'une ou l 'autre qui est la plus commode d'emploi ; c'est ce crit~re qui

- - 83 - -

C. CARDOT [ANNALES DES T]~LJ~COMMUNICATION$

devrait jouer plutSt qu'un parti-pris syst6matique, variable suivant les auteurs. I1 en r6sulterait trbs probablement que l'une des deux caract6ristiques prendrait le rSle de caract6ristique principale, l'autre intervcnant en eas de besoin en qualit6 de caract6ristique auxiliaire susceptible d'abr6gcr cer- rains raisonnements (de m6me qu'en g6om6trie, dans la dualit6 des propri6t6s ponctuelles et tangen- tielles, on raisonne beaucoup plus commun6ment sur les premibres, les secondes n'6tant trait6es - - dans la majorit6 des cas - - que comme corollaires d6duits par dualit6, sauf dans la minorit6 des cas off elles s'6tablissent directement de manibre plus exp6- ditive ou plus concrbte). L'uniformit6 ici souhait6e par l'auteur semble d6sirable pour tout le monde - - y compris les chercheurs, h qui elle procurerait un gain de temps et d'attention lorsqu'ils out h prendre connaissance de leurs travaux respectifs - - mais surtout pour les usagers : pour que ce~ proc6d6 de calcul trouve parmi eux tout le succ~s qu'il m6rite, le mieux est que les divers auteurs parlent le m~me langage.

Manuscrit regu le 27 [dvrier 1951.

B I B L I O G R A P H I E

[1] BOOLE (G.), L'analyse nla th6mat ique de la logique. (The mathemat ica l analysis of logic.) R66dit6 par Philosophical Library, New-York (1847).

[2] SHANNON (C. E.), La synthbse des circuits h in ter rupteurs compor tan t deux terminaisons. (The synthesis of two-terminal switching circuits.) Bell System Techn., U. S. A. (jan. 1949), pp. 59-99.

[3] MONTGOMERIE (G. A.), Algbbre des circuits des contacteurs et des relais. (Sketch for an algebra of relay and contactor circuits.) J. Inst. Electr. Engrs., Par t I I I , G.-B. (juil. 1948), 95, n ~ 36, pp. 303-312.

[4] BUFFERY (G. l-L), Une contr ibut ion fi l 'algbbre des relais et des in ter rupteurs h contacts. (A contr ibut ion to the algebra of relay and switch contacts. Proc. Inst. Electr. Eagrs, Par t l, G.-B. (nov. 1950), 97, n ~ t08, pp. 357-363.

[5! LEFSCHETZ (S.), In t roduct ion h la topologic. ( In t roduct ion to topology.) Princeton Univer- sity Press, Princeton, N. J. , U. S. A. (1949), 218 p.

[6] MAc CULLOCH (W. S.), PITTS (W.), Calcul logique des id6es iminanentes dans l 'act ivi t6 nerveuse. (A logical calculus of the ideas immanent in ner- vous activit ies.) Bull. Math. Biophysics, U. S. A. (1943), v. 5, pp. 115-133.

[7] GAV~ILOV (M. A.), Analyse des circuits compor- rant des relais et des contacts. Elektritchestvo, 15. B. S. S. (f6v. 1946), n ~ 2, pp. 54-58; (avril 1947), n ~ 4, p.p. 5-13.

[S] VOLOTZKO~ (A. N.), E16ments de la tb.dorie des sch6mas compor tan t des contacts de relais. Vest. Swiyazi, U. R. S. S. (juil. 1947), n ~ 7. pp. J6-18.

[9] SCHWAB (H.), L'alg6bre des chalnes de contacts. Ann. Tdlr (jan. 1952), 7, n ~ 1, pp. 2-16.

NOTES, INFORMATIONS, ACTUALIT#__.S

R E V U E D E S P . T . T . D E F R A N C E . - - Publi- cat ion de l 'Adminis t ra t ion des P. T. T. (Direction du Budget e t de la Comptabil l t6 , 6 e Bureau). En vente: soit par num6ro s~par6 (t00 francs) ; solt par abonne- ment annuel de 6 fascicules, scrvi h par t i r du num~ro su ivant la date de souscript ion (500 francs ; pour les membres de l 'Admin i s t ra t ion fran~aise des P. T. T. : 250 francs). Souscrire (en sp~cifiant le moti[ du versement: ct Abonnemen t h la Revue des P. T. T. ~)) au cr~- di t du Receveur principal de la Seine, 52, rue du Louvre, Paris (ler) :

soit, de prg/drence, par versement ou vi rement son c /c postal (9040-00/Paris) ; ~ soit par manda t -pos te 6mis ~ son adresse ; ~ soit cnfin par versement en numdraire h u n bureau de pos'te.

Sommaire du n ~ 6 (vol. 6) Novembre-D~cembre 1951

Pages Organisation g6n6ra|e de l 'Administration franqaise

des P. T. T. (suite). - - Los Centres d'amplification, par M. MAILL~Y . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

Un proc~s criminel au xvm e si6cle pour spoliation de correspondance et vol d'argent. L'affaire Lc Prince, par M. VAILL~ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

Les radiocommunications et le probl6me de l'assignation des fr6quences radio61ectriques, par M. LAFFAY... 9

En Alg6rie, quand le bStiment va..., par M. YACONO. 12 Les progr6s et le d6veloppement du r6seau des liaisons

radio61ectriques h grande distance de l'Adminis- tration des P. T. T., par M. VEAUX . . . . . . . . . . . . . 16

L'extension du r6seau souterrain t616phonique et les acquisitions de terrains qu'elle implique, par M. BolssiEn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2~

Nos bureaux modernes, par M. LAFON . . . . . . . . . . . . 29 Nouveau calcu[ des 6moluments, par M. GEMPTEL... 32 L'eeuvre du Postier qui, h l'aube de la R6volution fran-

~aise, a lanc6 et personnifi6 lc (c P6re Duchdne )~ dans le journalisme, par M. RICAnD . . . . . . . . . . . . . . . . . 60

Chroniques : m6dicale-- (( Les anxieux dans la vie courantc ~, par le Docteur BUREAU (p. tt6) ; juridique - - ~( L'obli- gation alimentaire ~), par M e DEBRAY (p. ~5} ; - - Statis- tiqucs (p. 66) ; - - Philat61ie (p. ~8) ; - - L6gistation et jurisprudence (p. 50) ; - - Bibliographic (p. 56) ; - - Table des mati6res 1951 (p. 62).

- - 8 4 - -

Documents

Quelques résultats sur l’application de l’algèbre de Boole a la synthèse des circuits a relais