News :: Erreur :: Statistiques :: ClearType :: Imprimer ::

MÉTHODES NUMÉRIQUES | FRACTALES | SYSTÈMES LOGIQUES | CODES CORRECTEURS CRYPTOGRAPHIE | AUTOMATES | INFORMATIQUE QUANTIQUE

LISTE DES SUJETS TRAITÉS SUR CETTE PAGE

Le lecteur connaissant bien l'objectif de ce site ne doit pas s'attendre à voir ici de quelconques schémas de boutons poussoirs, interrupteurs, chronogrammes ou encore de schémas électriques de norme MIL ou autres. Nous resterons donc dans un cadre purement formel des systèmes logiques et de leurs outils.

Définitions:

D1. Nous parlons de "modèle logique asynchrone" (courament appelé "modèle logique séquentiel") lorsque les sorties d'un système dépendent de l'ordre chronologique dans lequel se succèdent les entrées.

D2. Nous parlons "modèle logique combinatoire" les sorties d'un système dépendent uniquement de la combinaisons des variables d'entrées.

LOGIQUE STRICTE

Considérons dans un premier temps un ensemble que nous noterons B à deux éléments (plus formellement noté ).

Définitions:

D1. Une "variable logique stricte" ou "variable booléenne" est un élément de B qui ne possède que deux états 0 et 1 (à l'opposé d'une variable logique floue dont la valeur peut-être comprise entre 0 et 1). Elle est représentée par des lettres latines majuscules ou minuscules (au choix).

D2. Une "fonction logique F" de plusieurs variables applique dans B. Elle associe à un n-uplet de variables logiques une valeur .

D3. Il existe différente manières d'exprimer une fonction logique (ou "fonction booléenne"). Une fonction de n variables est entièrement décrite par l'énoncé des valeurs de cette fonction pour l'ensemble (ou le sous-ensemble de définition) des combinaisons du n-uplet de variables :

  (1)

Cet énoncé prend généralement la forme d'un tableau à n+1 colonnes et au plus lignes, chaque ligne exposant une combinais des variables et la valeur correspondante de la fonction. Le tableau suivant donne la forme générale d'une "table de vérité" de fonctions de trois variables totalement (fonction F) définies :

Les éléments d'entrées des systèmes seront considérées comme des variables booléenes sur lesquelles nous pouvons construire une structure de base anneau et par ajout d'un axiome particulier, d'une "algèbre" (dans le sens calculatoire du terme et non ensembliste!) appelée couramment "algèbre de Boole" :

ALGÈBRE DE BOOLE

L'algèbre de Boole (ou "anneau de Boole" à un axiome près...) est donc une structure qui est le plus souvent utilisée en électronique (ou micro-électronique). Ainsi, Un processeur est composé de transistors permettant de réaliser des fonctions sur des signaux numériques. Ces transistors, assemblés entre eux forment des composants permettant de réaliser des fonctions très simples. A partir de ces composants il est possible de créer des circuits réalisant des opérations assez complexes. L'algèbre de Boole (du nom du mathématicien anglais Georges Boole 1815 - 1864) est un moyen d'arriver à créer plus ou moins facilement de tels circuits.

L'algèbre de Boole est donc une algèbre sur elle-même (avec une structure d'anneau comme nous allons le définir rigoureusement plus loin) se proposant de traduire des signaux dont la valeur est du type 0/1 (assimilé à : Vrai/Faux) en expressions mathématiques. Pour cela, nous définissons chaque signal élémentaire par des "variables logiques" et leur traitement par des "fonctions logiques". Des méthodes ("tables de vérité") permettent de définir les opérations que nous désirons réaliser, et à transcrire le résultat en une expression algébrique. Grâce à des règles que nous verrons plus loin, ces expressions peuvent être simplifiées. Cela va permettre de représenter grâce à des symboles simples un circuit logique capable d'effectuer des opération arithématique élémentaires, c'est-à-dire un circuit qui schématise l'agencement des composants de base (au niveau logique) sans se préoccuper de la réalisation au moyen de transistors (niveau physique).

Il est nécessaire pour obtenir une définition rigoureuse d'une algèbre de Boole de se la donner en des termes d'algèbre abstraite.

Rappel : une "algèbre de Boole" est un ensemble contenant deux éléments particuliers, , (forme abstraite du 0 et du 1) muni de deux lois de composition internes, (ET et OU logiques) et qui vérifie les axiomes suivants pour former une structure d'anneau tel que :

A1. et (associativité)

A2. et (commutativité)

A3. et (absorption)

A4. et (distributivité)

A5. et (idempotence)

A6. a possède un complément noté ou (NON) tel que : et ("complémentation" ou "inversion")

Rigoureusement, pour former un algèbre de Boole il faut un élément symétrique (cf. le chapitre de Théorie Des Ensembles) ce qui n'est pas le cas de l'opération . C'est la raison pour laquelle les vrais opérateurs d'un algèbre de Boole sont normalement le (ET) et la (différence symétrique) donnée par l'opération logique :

  (2)

mais pour simplifier dans les petits classes il est fréquent que nous y fassions implicitement référence sans entrer dans les détails.

Il s'ensuit que l'ensemble binaire  constitue donc bien par rapport aux lois  un "groupe abélien". Dès lors,  étant un groupe abélien, la loi  étant associative et distributive par rapport à ,  est un "anneau commutatif unitaire" (vu que B possède un élément neutre pour la loi ).

Les axiomes précédents peuvent cependant se démontrer à partir des "axiomes de la définition" :

A1.

A2.

A3. (double complémentation)

A4. est l'élément neutre de la loi

A5. est l'élément neutre de la loi

A6. et (ces deux dernières formulations forment le théorème de De Morgan).

Il s'ensuit donc le tableau suivant :

  (3)

Nous appelons ces expressions "duales" car en remplaçant dans une même équation logique, les 0 par 1, les par des + est inversement, cette équation reste vérifiée.

Théorème des constantes :

Soit à prouver que :

  (4)

La démonstration est triviale (au besoin faire une table de vérité) car elle provient de la propriété même du concept "d'anneau" (de Boole) et de son élément neutre (1) par rapport au et à son élément neutre (0) par rapport au .

Démontrons maintenant la relation suivante:

  (5)

Démonstration:

La distributivité nous amène à écrire :

  (6)

et en appliquant la complémentation :

  (7)

en appliquant la commutativité :

  (8)

et enfin en appliquant le théorème des constantes :

  (9)

C.Q.F.D.

Cette démonstration va nous permettre de démontrer le fameux "théorèmes du consensus" :

  (10)

Démonstration:

Pour vérifier le théorème du consensus relatif au produit logique :

  (11)

nous pouvons faire usage d'un diagramme de Venn où nous voyons bien que le terme est contenu dans les deux autres :

  (12)

En procédant de même avec un diagramme de Venn, le lecteur verra sans aucun problème que :

  (13)

C.Q.F.D.

Et enfin les très fameux "théorèmes de Shannon" (à ne pas confondre avec le théorème de Shannon en théorie du signal!):

  (14)

Démonstrations:

et:

  (15)

C.Q.F.D.

Revenons maintenant sur les théorèmes de Morgan précédemment présentés comme des axiomes :

  (17)

Ces deux relations expriment donc que l'inverse (ou l'opposé) d'un produit (respectivement de la somme) de deux variables est égal à la somme (respectivement au produit) des inverses de ces variables.

Démonstration:

Supposons juste. Alors en vertu des relations et (axiome de complémentation) nous devons avoir :

  (18)

Donc il nous faut prouver que ces deux relations sont exactes :

  (19)

et :

  (20)

Le deuxième théorème de De Morgan se démontre de la même façon.

C.Q.F.D.

Corollaires :

  (21)

Les expressions logiques, nous l'avons vu à l'aide des axiomes, propriétés et particulièrement des théorèmes précédents, doivent donc toujours pouvoir se mettre sous deux formes (en jouant avec les oppositions aussi donc) :

F1. Sous la forme d'une somme de produits logiques, appelée "forme normale disjonctive F.N.C.", tel que (exemple) :

  (22)

Les termes constitutifs de ce polynôme sont les monômes : . Les variables ou complémentaire de ces monômes sont les "lettres" : .

F2. Sous la forme de produit de sommes logiques , appelée "forme normale conjonctive F.N.D.", tel que (exemple) :

  (23)

Ainsi, une forme normale disjonctive est soit un littéral (une lettre), soit une disjonction de formules écrites comme conjonctions de littéraux. Une forme normale conjonctive est soit un littéral, soit une conjonction de formules écrites comme disjonctions de littéraux.

Les méthodes de simplifications que nous verrons par la suite viseront à minimiser le nombre de lettres des expressions de manière à réduire le nombre d'entrées de notre système logique.

Pour simplifier les expressions (ou les déterminer) une technique connue consiste donc à utiliser les "tables de Karnaugh" que nous verrons plus loin dans les détails.

FONCTIONS LOGIQUES

Donc quand nous parlons d'algèbre de Boole sauf mention contraire, nous faisons référence à ces aux trois opérations booléennes élémentaires (ET, OU, NON) et quelques autres fonctions logiques qui en découlent dont voici les symboles tel que définis en théorie des circuits (norme MIL sauf erreur...) :

  (24)

et leurs "tables de vérité" respectives :

Table de vérité ET ()
ET	0	1
0	0	0
1	0	1

Tableau: 2  - Table de vérité ET

Table de vérité OU ()
OU	0	1
0	0	1
1	1	1

Tableau: 3  - Table de vérité OU

Table de vérité NON ()
NON	-
0	1
1	0

Tableau: 4  - Table de vérité NON

Toutes les autres "fonctions logiques" connues (communes) peuvent être composées de ces deux opérateurs fondamentaux. Tels que par définition (données avec leur définition standard dans la première ligne et avec leurs différentes formes algébriques sous leur table de vérité respective)

Tableau: 5  - Table de vérité NON-ET

Tableau: 6  - Table de vérité NON-OU

où a et b sont, vous l'aurez compris, des variables (ou "bit" de Binary Digit) pouvant prendre arbitrairement les valeurs binaires 0 ou 1.

Remarque: La fonction logique XOR est souvent notée dans la littérature par l'opérateur et nous considérerons comme évident que le XOR est également une loi de groupe et permet de construire ainsi un groupe commutatif abélien. Cette propriété du XOR est particulièrement utilisée en cryptographie.

TABLES DE KARNAUGH

A part la table de vérité qui simplifie en général la présentation d'un problème logique (mathématique, électronique, micro-électronique, fiabilité des systèmes), il existe d'autres formes tabulées en particulier la table de Karnaugh qui est dans de nombreux cas un outil de travail facile à manipuler.

Considérons pour exemple la fonction (sous forme F.N.D) et sa table de vérité respective :

La table de Karnaugh est définie par une représentation comme celle ci-dessous :

  (25)

La table de Karnaugh d'une fonction logique comporte donc autant de cases que de combinaisons possibles de variables qui la composent, soit quatre cases pour une fonction à deux variables, et cases pour une fonction à n variables. Chaque case, qui se trouve à l'intersection d'une ligne et d'un colonne de la table de Karnaugh porte l'état 0 ou 1 que prend la fonction pour le produit logique correspondant des variables (mintermes).

Dans l'exemple précédent nous pouvons voir cependant quelque chose d'intéressant, la fonction F, nous le voyons très bien, peut se simplifier de deux manière ou encore . Cette simplification possible ce fait toujours avec deux mintermes adjacents dans la table de Karnaugh tel que :

  (26)

Nous voyons que le premier regroupement/simplification (horizontal) se fait sur la ligne et le second regroupement/simplification (vertical) se fait sur la colonne b tout deux résultats de la simplification algébrique de la fonction.

Donc nous pourrions émettre l'hypothèse que la table de Karnaugh a pour propriété :

P1. De nous donner la forme disjonctive normale d'une fonction

P2. Que toutes cases adjacentes mises ayant pour valeur 1 peuvent se simplifier en la lettre respective de leur réunion.

C'est donc un outil extrêmement puissant pour simplifier et déterminer des fonctions logiques.

Voyons un exemple à trois variables :

  (27)

La F.N.D est donc mais elle peut se simplifier algébriquement sous la forme mais nous voyons que ceci peut encore se simplifier en où nous voyons que les quatre cases adjacents sont là où b vaut partout 1.

Une autre manière de simplifier :

  (28)

Donne .

Une difficulté subsiste cependant avec cette technique : comment choisir la meilleure construction du tableau (choix des lettres en colonnes ou en ligne) ?

Au fait, il existe une manière spécifique qui consiste à associer la règle de complémentation de l'algèbre de Boole avec ce que nous appelons le "code Gray".

Définition: Dans le code de Gray, deux termes successifs ne diffèrent que par un seul bit. Les termes ne différant que par un seul bit sont appelés "adjacents".

En utilisant le code Gray nous pouvons créer des tables de Karnaugh optimales. La raison en est simple, le code Gray ne change qu'un bit à la fois à chaque incrémentation. En pratique ceci signifie que pour deux valeurs qui se suivent, un et deux par exemple, une des deux variable sera le contraire.

Exemple:

Soit 1=01 correspondant à et 2 = 11 correspondant à ba, la somme (forme disjonctive) nous donnerait par donc ce qui se réduit à l'aide de la règle de complémentation directement à

Tout ceci pour dire que quand deux formules se retrouvent côte à côte dans le tableau de Karnaugh, nous conservons des élément semblables seulement.

Les règles sont telles que nous pouvons réduire quand (voir l'exemple concret précédant) :

R1. Deux 1 sont juxtaposés dans le tableau :

 
  (29)

R2. Quand deux 1 sont aux extrémités du tableau :

  (30)

R3. Quand une rangée pleine fait disparaître les deux variables BA dans ce cas :

  (31)

R4. Une colonne pleine fait disparaître deux variables DC dans ce cas :

  (32)

R5. Quatre cases font disparaître deux variables A et C dans ce cas :

  (33)

R6. La même case peut servir à deux réductions :

  (34)

R7. La même case peut servir à deux réductions :

  (35)

OPÉRATIONS ARITHMÉTIQUES

A l'aide de tous les éléments démontrés et donnés précédemment, nous sommes maintenant capables de déterminer rigoureusement la fonction logique permettant l'addition et la soustraction booléenne. Rappelons aussi que ceci étant fait, nous pouvons construire la multiplication et la division à l'aide respectivement de l'addition et de la soustraction.

Cependant, nous ne pouvons avec les systèmes numériques formels construire des éléments permettant l'intégration et la différentiation. Pour cela, nous renvoyons le lecteur au chapitre d'Électrocinétique où il est montré comment utiliser des inductances et des condensateurs pour effectuer de telles opérations avec des signaux.

La somme de deux bytes sera notée S, la retenue (retenue sortante) et la retenue reportée (retenue entrante).

La table de vérité sera construite avec pour astuce que les entrées du système () prennent tout les valeurs possibles sur 3 bits (trois lettres) soit lignes que nous avons représentées dans la table suivante:

et maintenant l'idée consiste à rajouter la colonne de la somme:

  (36)

ligne par ligne (sans penser à la retenue sortante ) :

Maintenant, ligne par ligne, nous rajoutons la retenue sortante de la somme S :

Il vient alors quatre mintermes (c'est-à-dire les termes pour lesquels S est non nul aux lignes 2,3,5,8) tel que la F.N.D s'écrive :

  (37)

Une simplification possible est :

  (38)

Il vient également pour la retenue sortante les mintermes suivants :

  (39)

Donc finalement nous avons :

  (40)

La soustraction (différence) de deux bytes sera notée D, l'emprunt (emprunt sortant) et la emprunt reporté (emprunt entrante). La table de vérité sera construite avec dans un premier temps comme pour l'addition. C'est-à-dire que les entrées du système () prennent tout les valeurs possibles sur 3 bits (trois lettres) soit lignes. Ainsi :

Mais nous allons rajouter une petite subtilité. Plutôt que de nous embêter à calculer , nous allons calculer de manière à travailler avec la table de vérité ci-dessous :

et maintenant l'idée consiste à rajouter la colonne de différence ligne par ligne (sans penser à l'emprunt ) qui sera strictement identique à la table de vérité de la somme :

Maintenant, ligne par ligne, nous rajoutons l'emprunt sortant de la différence :

Il vient alors quatre mintermes (c'est-à-dire les termes pour lesquels S est non nul aux lignes 2,3,5,8) tel que la F.N.D s'écrive :

  (41)

Une simplification triviale possible est :

  (42)

Il vient également pour l'emprunt sortant les mintermes suivants :

  (43)

Donc finalement :

  (44)

LOGIQUE FLOUE

La plupart des problèmes rencontrés sont modélisables mathématiquement. Mais ces modèles nécessitent des hypothèses parfois trop restrictives, rendant délicate l'application au monde réel. Les problèmes de ce monde doivent tenir compte d'information imprécises, incertaines. Prenons l'exemple d'une climatisation : si nous voulons obtenir une température fraîche, nous pouvons nous demander quelle gamme de températures conviendra (la demande est imprécise); de plus la fiabilité des capteurs entre en jeu (la mesure de la température ambiante est incertaine). Nous voyons apparaître la difficulté d'interprétation des variables linguistiques comme frais, chaud, …ainsi que du traitement de ces données entachées d'incertitude.

Une approche fut développé à partir de 1965 par Loft. A. Zadeh, professeur à l'Université de Californie à Berkeley, basée sur la théorie des sous ensembles flous ("fuzzy sets" en anglais), généralisant la théorie des ensembles classique. Dans la nouvelle théorie de Zadeh, un élément peut plus ou moins appartenir à un certain ensemble. Les imprécisions et les incertitudes peuvent ainsi être modélisées, et les raisonnements acquièrent une flexibilité que ne permet pas la logique classique : la "logique floue" était née. De nombreuses applications ce sont alors développées dans divers domaines, là où aucun modèle déterministe n'existe ou n'est pratiquement implémentable, ainsi que dans des situations pour lesquelles l'imprécision sur les données rend le contrôle par des méthodes classiques impossible.

Dans ce qui suit, nous développerons d'abord la théorie des sous-ensembles flous, puis nous préciserons le raisonnement en logique floue, nous examinerons les méthodes d'exploitation des résultats obtenus, et enfin nous verrons une application effective.

Avant de passer au coté formel de la chose (mathématiquement parlant) il peut être préférable (puisqu'il s'agit quand même d'une technique de l'ingénieur) de présenter brièvement les concepts de la logique floue de manière imagée.

La logique floue est une technique utilisée dans des domaines aussi variés que l'automatisme (freins ABS), la robotique (reconnaissance de formes), le gestion de la circulation routière (feux rouges), le contrôle aérien, l'environnement (météorologie, climatologie, sismologie), la médecine (aide au diagnostic) et bien d'autres.

A l'inverse de la logique booléenne, la logique floue permet à une condition d'être en un autre état que vrai ou faux. Il y a des degrés dans la vérification d'une condition.

Considérons par exemple la vitesse d'un véhicule sur une route nationale. La vitesse normale est de 90 [km/h]. Une vitesse peut être considérée comme élevée au-dessus de 100 [km/h], et comme plus du tout élevée en dessous de 80 [km/h]. La logique booléenne envisagerait les choses de la manière suivante :

  (45)

La vitesse est considérée à 100% comme élevée à partir de 100 km/h, et à 0% en dessous.

La logique floue, à l'inverse, permet des degrés de vérification de la condition " La vitesse est-elle élevée ? " selon :

  (46)

La vitesse est considérée comme pas du tout élevée en dessous de 80 km/h. On peut donc dire qu'en dessous de 80 km/h, la vitesse est élevée à 0%. La vitesse est considérée comme élevée au-dessus de 100 km/h. La vitesse est donc élevée à 100% au-dessus de 100 km/h. La vitesse est donc élevée à 50% à 90 km/h, et à 25% à 85 km/h.

De la même manière, la fonction " La vitesse est-elle peu élevée ? " sera évaluée de la manière suivante selon :

  (47)

La vitesse est considérée comme peu élevée en dessous de 80 km/h. Elle est donc peu élevée à 100%. La vitesse est considérée comme pas du tout peu élevée au-dessus de 100 km/h. Elle est donc peu élevée à 0%. La vitesse est donc peu élevée à 50% à 90km/h, et à 75% à 85 km/h.

Nous pouvons également définir une fonction " La vitesse est-elle moyenne ? " selon :

  (48)

La vitesse est moyenne à 90 km/h. À cette allure, la vitesse est moyenne à 100%. La vitesse n'est pas du tout moyenne en dessous de 80 km/h et au-dessus de 100 km/h. Hors de cet intervalle, la vitesse est moyenne à 0%. La vitesse est donc moyenne à 50% à 85 km/h et 95 km/h.

Il n'est pas obligatoire que la transition soit linéaire. Des transitions hyperboliques (comme une sigmoïde ou une tangente hyperbolique), exponentielle, gaussienne (dans le cas d'un état moyen) ou de toute autre nature sont utilisables tel que les méthodes que nous avons vues lors de notre étude des réseaux de neurones :

  (49)

Une fois évaluée la valeur de l'entrée (" La vitesse est-elle élevée ? "), une valeur peut être déterminée pour une fonction de sortie. Considérons la fonction " Si la fièvre est forte, alors administrer de l'aspirine ". Une telle fonction est appelée "commande floue". Elle est composée de deux parties :

1. Une entrée : " La fièvre est-elle forte ? ". Nous considérons qu'une fièvre n'est pas forte en dessous de 38°C, et qu'elle est forte au-dessus de 40°C.

2. Une sortie : " Administrer de l'aspirine "

Ces deux parties sont liées. Nous pouvons les représenter ensemble comme ci-dessous :

  (50)

Il existe plusieurs techniques pour déterminer la valeur de la sortie (dans l'exemple : la quantité d'aspirine à administrer) :

Un exemple consistant à prendre pour la droite ayant la même ordonnée que le point de la courbe de départ ayant pour abscisse la valeur de l'entrée coupe la courbe de sortie. L'abscisse de ce point d'intersection est une valeur de sortie possible comme représenté ci-dessous :

  (51)

Une deuxième exemple consiste à prendre la droite ayant la même ordonnée que le point de la courbe de départ ayant pour abscisse la valeur de l'entrée délimite un trapèze au niveau de la sortie. Le centre de gravité de ce trapèze est également une valeur de sortie possible comme représenté sur la figure ci-dessous :

  (52)

De par ces deux exemples nous voyons bien que nous sommes à la frontière science/ingénierie puisqu'il y a un choix technique ou et statistique à faire dans la méthode à choisir.

ENSEMBLE FLOU

Définition: Soit X un ensemble. Un "sous-ensemble flou" A de X est défini par une fonction d'appartenance sur X à valeurs dans l'intervalle [0,1].

La notion de sous-ensemble flou englobe celle de sous-ensemble classique pour laquelle est la fonction indicatrice :

Définition: Si A et B sont deux ensembles, tels que A est inclus dans B, nous appelons "fonction indicatrice" de A (relativement à B), la fonction définie dans {0,1}, et telle que :

si x est dans A
si x n'est pas dans A
  (53)

Les fonctions indicatrices sont souvent des intermédiaires techniques très pratiques!

Exemple:

Une fonction caractéristique possible pour définir le sous-ensemble flou "avoir une vingtaine d'années"

  (54)

Les notions suivantes sont caractéristiques de A :

Définitions:

D1. Support de A :

D2. Hauteur de A :

D3. A est dit normalisé si

D4. Noyau de A :

D5. Cardinalité de A :

Exemple:

Avec l'exemple de la figure précédente :

  (55)

D6. Si A et B sont deux sous-ensembles flous de l'ensemble X, nous disons que :

1. A est "plus spécifique" que B si :

et   (56)

2. A est "plus précis" que B si :

, et   (57)

D7. Il y a égalité entre deux sous-ensembles flous si et seulement si :

  (58)

D8. Il y a inclusion si et seulement si :

  (59)

D9. L'intersection est définie par :

  (60)

D10. L'union est définie par :

  (61)

Exemple:

Reprenons le cas déjà envisagé. Nous considérons les personnes ayant une "vingtaine d'années", et celles "ayant la majorité" (en pointillés sur la figure : nous considérons celle-ci comme un sous ensemble non-flou!) :

  (62)

Selon les définitions de l'intersection ("ET logique" ou multiplication logique selon l'algèbre de Boole) et de l'union ("OU logique" ou addition logique selon l'algèbre de Boole), nous pouvons caractériser les sous-ensembles flous correspondant aux personnes "ayant une vingtaine d'années et la majorité" (à gauche dans la figure ci-dessous) ainsi que celui des personnes "ayant une vingtaine d'années ou la majorité" (à gauche dans la figure ci-dessous) :

  (63)