loadingPage en cours de chargement
    ACCUEIL | TÉLÉCHARGER | QCM | DON | ANNONCES | CHAT | FORUM | LIVRE D'OR | PARTENAIRES | CONTACT | BLOG
 
  Rechercher
  separation
  Introduction
  Arithmétique
  Algèbre
  Analyse
  Géométrie
  Mécanique
  Électrodynamique
  Atomistique
  Cosmologie
  Chimie
  Informatique Théorique
  Maths. Sociales
  Ingénierie
  separation
  Biographies
  Références
  Liens
  separation
  Humour
  Serveur d'exercices
  separation
  Parrains
9 connectés
News News :: Erreur Erreur :: Statistiques Visiteurs :: ClearType ClearType :: Imprimer Imprimer :: Bookmark and Share

Informatique Théorique

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

59. SYSTÈMES LOGIQUES FORMELS

Dernière mise à jour de ce chapitre: 2017-08-06 17:23:41 | {oUUID 1.794}
Version: 2.2 Révision 4 | Avancement: ~80%
viewsvues depuis le 2012-01-01: 5'104

Table des matières 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" (couramment 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 de "modèle logique combinatoire" lorsque les sorties d'un système dépendent uniquement de la combinaison des variables d'entrées.

Remarque: Nous différencions la "logique stricte" de la "logique floue" qui seront toutes deux définies dans les détails plus loin.

LOGIQUE STRICTE

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

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 equation dans B. Elle associe à un n-uplet de variables logiques equation une valeur equation.

D3. Il existe différentes 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:

equation   (59.1)

Cet énoncé prend généralement la forme d'un tableau à n+1 colonnes et au plus equation lignes, chaque ligne exposant une combinaison 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:

A

B

C

F(A,B,C)

0

0

0

F(0,0,0)

0

0

1

F(0,0,1)

0

1

0

F(0,1,0)

0

1

1

F(0,1,1)

1

0

0

F(1,0,0)

1

0

1

F(1,0,1)

1

1

0

F(1,1,0)

1

1

1

F(1,1,1)

Tableau: 59.1  - Table de vérité générique

Les éléments d'entrées des systèmes seront considérés comme des variables booléennes sur lesquelles nous pouvons construire une structure de base en anneau que, par ajout d'un axiome particulier, nous pouvons munir 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. À 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 George 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érations arithmétiques é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).

Remarque: Il serait préférable avant de commencer la lecture de ce chapitre, de parcourir la partie traitant de la logique au chapitre de la Théorie De La Démonstration et des structures algébriques dans le chapitre de Théorie Des Ensembles.

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 equation contenant deux éléments particuliers, equation, (formes abstraites du 0 et du 1) muni de deux lois de composition internes, equation (ET et OU logiques) et qui vérifie les axiomes suivants pour former une structure d'anneau telle que equation:

A1. equation et equation (associativité)

A2. equation et equation (commutativité)

A3. equation et equation (absorption)

A4. equation et equation (distributivité)

A5. equation et equation (idempotence)

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

Remarque: Les quatre premiers axiomes établissent une structure d'anneau. Le cinquième axiome (idempotence) ajouté aux quatre premiers définit le concept "d'algèbre de Boole".

Rigoureusement, pour former une 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 equation. C'est la raison pour laquelle les vrais opérateurs d'une algèbre de Boole sont normalement le equation (ET) et la equation(différence symétrique) donnée par l'opération logique:

equation   (59.2)

mais pour simplifier, dans les petites 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 equation constitue donc bien par rapport aux lois equation un "groupe abélien". Dès lors, equation étant un groupe abélien, la loi equation étant associative et distributive par rapport à equation, equation est un "anneau commutatif unitaire" (vu que B possède un élément neutre pour la loi equation).

Remarques:

R1. Ainsi, les opérations equation et equationadmettent chacune un élément neutre tel que le chiffre 1 est l'élément neutre de equation et le chiffre 0 l'élément neutre de equation

R2. Les deux opérations que nous utilisons habituellement pour former une algèbre de Boole sont le "ou inclusif" noté rigoureusement equation mais plus fréquemment par le signe d'addition "+", et le et "et inclusif" noté rigoureusement equation  mais plus fréquemment par le signe de multiplication "equation".

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

A1. equation

A2. equation

A3. equation (double complémentation)

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

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

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

Remarque: Le théorème de De Morgan se démontre à l'aide d'une simple table de vérité ou algébriquement comme nous le verrons juste un peu plus loin.

Il s'ensuit donc le tableau suivant:

equation   (59.3)

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

Voyons maintenant ce que nous appelons le "théorème des constantes" qui consiste à prouver que:

equation   (59.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 equation et à son élément neutre (0) par rapport au equation .

Démontrons maintenant la relation suivante:

equation   (59.5)

Démonstration:

La distributivité nous amène à écrire:

equation   (59.6)

et en appliquant la complémentation:

equation   (59.7)

en appliquant la commutativité:

equation   (59.8)

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

equation   (59.9)

equationC.Q.F.D.

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

equation   (59.10)

Démonstration:

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

equation   (59.11)

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

equation
Figure: 59.1 - Diagramme de Venn du théorème du consensus

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

equation   (59.12)

equationC.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!):

equation   (59.13)

Démonstrations:

equation

et:

equation   (59.14)

equationC.Q.F.D.

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

equation   (59.15)

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 equation juste. Alors en vertu des relations equation et equation (axiome de complémentation) nous devons avoir:

equation   (59.16)

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

equation   (59.17)

et:

equation   (59.18)

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

equationC.Q.F.D.

Remarque: Ces deux théorèmes peuvent s'étendre à un nombre quelconque de variables.

Corollaires:

equation   (59.19)

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 equation aussi donc):

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

equation   (59.20)

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

Remarque: Si chacun (tous) des produits contient toutes les variables d'entrée sous une forme directe ou complémentée, alors la forme est appelée "première forme canonique" ou "forme canonique disjonctive". Chacun des produits est alors appelé "minterme".

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

equation   (59.21)

Remarque: Si chacune des sommes contient toutes les variables d'entrée sous une forme directe ou complémentée, alors la forme est appelée "deuxième forme canonique" ou "forme canonique conjonctive". Chacune des sommes est alors appelée "maxterme".

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 simplification 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.

Remarque: La simplification algébrique d'une expression consiste à la transformer de manière à réduire au maximum le nombre de ses lettres en lui appliquant les théorèmes vus précédemment.

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 aux trois opérations booléennes élémentaires (ET, OU, NON) et quelques autres fonctions logiques qui en découlent dont voici les symboles tels que définis en théorie des circuits (norme MIL sauf erreur...):

equation
Figure: 59.2 - Portes logiques

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


Table de vérité ET (equation)

ET

0

1

0

0

0

1

0

1

Tableau: 59.2  - Table de vérité ET

Table de vérité OU (equation)

OU

0

1

0

0

1

1

1

1

Tableau: 59.3  - Table de vérité OU

Table de vérité NON (equation)

NON

-

0

1

1

0

Tableau: 59.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)

equation
NON-ET (NAND): NON (a ET b)
NAND
0
1
0
1
1
1
1
0
Tableau: 59.5  - Table de vérité NON-ET

equation
NON-OU (NOR): NON (a OU b)
NOR
0
1
0
1
0
1
0
0
Tableau: 59.6  - Table de vérité NON-OU

equation
OU EXCLUSIF (XOR): [a OU b] ET [ NON (a ET b) ]
XOR
0
1
0
0
1
1
1
0
Tableau: 59.7  - Table de vérité OU EXCLUSIF

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 equation 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

À 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:

equation   (59.22)

(sous forme F.N.D) et sa table de vérité respective:

b

a

F

0

0

1

0

1

0

1

0

1

1

1

1

Tableau: 59.8  - Exemple de base pour la table de Karnaugh

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

equation
Figure: 59.3 - Représentation traditionnelle de la table de Karnaugh

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 equation cases pour une fonction à n variables. Chaque case, qui se trouve à l'intersection d'une ligne et d'une 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ères:

equation   (59.23)

ou encore:

equation   (59.24)

Cette simplification possible ce fait toujours avec deux mintermes adjacents dans la table de Karnaugh tels que:

equation
Figure: 59.4 - Table de Karnaugh associée

Nous voyons que le premier regroupement/simplification (horizontal) se fait sur la ligne equation et le second regroupement/simplification (vertical) se fait sur la colonne b tous 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:

equation
Figure: 59.5 - Table de Karnaugh à trois variables

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

Une autre manière de simplifier:

equation
Figure: 59.6 - Table de Karnaugh à trois variables avec autre méthode de simplification

Donne equation.

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 de 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 de Gray nous pouvons créer des tables de Karnaugh optimales. La raison en est simple, le code de 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 variables sera le contraire.

exempleExemple:

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

Tout cela pour dire que quand deux formules se retrouvent côte à côte dans le tableau de Karnaugh, nous conservons des éléments 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:

 equation
Figure: 59.7 - Premier type de réduction possible

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

equation
Figure: 59.8 - Deuxième type de réduction possible

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

equation
Figure: 59.9 - Troisième type de réduction possible

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

equation
Figure: 59.10 - Quatrième type de réduction possible

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

equation
Figure: 59.11 - Cinquième type de réduction possible

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

equation
Figure: 59.12 - Septième type de réduction possible

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

equation
Figure: 59.13 - Huitième type de réduction possible

et sauf erreur... c'est tout mais c'est déjà pas mal.

OPÉRATIONS ARITHMÉTIQUES BOOLÉENNES

À 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érenciation. 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.

Remarque: Nous travaillerons sur des nombres entiers mais le lecteur doit se rappeler que les nombres rationnels peuvent toujours être augmentés en puissance pour être représentés de manière entière (reste après à effectuer l'opération inverse au besoin).

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

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

Ce

a

b

0

0

0

0

0

1

0

1

0

0

1

1

1

0

0

1

0

1

1

1

0

1

1

1

Tableau: 59.9  - Identifications des retenues reportées pour la somme de bits

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

equation   (59.25)

ligne par ligne (sans penser à la retenue sortante equation que nous allons voir un tout petit peu plus loin):

Ce

a

b

S

0

0

0

0

0

0

1

1

0

1

0

1

0

1

1

0

1

0

0

1

1

0

1

0

1

1

0

0

1

1

1

1

Tableau: 59.10  - Retenues reportées pour la somme de bits

Maintenant, ligne par ligne, nous rajoutons la retenue sortante equation (qui n'est autre que la valeur qui est envoyée à la retenue entrante de la ligne suivante) de la somme S:

Ce

a

b

S

Cs

mintermes

0

0

0

0

0

equation

0

0

1

1

0

equation

0

1

0

1

0

equation

0

1

1

0

1

equation

1

0

0

1

0

equation

1

0

1

0

1

equation

1

1

0

0

1

equation

1

1

1

1

1

equation

Tableau: 59.11  - Identification des mintermes de la somme

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:

equation   (59.26)

Une simplification possible est:

equation   (59.27)

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

equation   (59.28)

Donc finalement nous avons:

equation   (59.29)

Remarque: La table de vérité de l'addition sans retenue entrante est appelée "demi-additionneur".

La soustraction (différence) de deux bytes sera notée D, l'emprunt equation (emprunt sortant) et l'emprunt reporté equation (emprunt entrant). 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 (equation) prennent toutes les valeurs possibles sur 3 bits (trois lettres) soit equation lignes. Ainsi:

ee

a

b

0

0

0

0

0

1

0

1

0

0

1

1

1

0

0

1

0

1

1

1

0

1

1

1

Tableau: 59.12  - Identifications des emprunts reportés pour la soustraction de bits

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

-ee

a

-b

0

0

0

0

0

1

0

1

0

0

1

1

1

0

0

1

0

1

1

1

0

1

1

1

Tableau: 59.13  - Inversion des emprunts reportés pour la soustraction de bits

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

ee

a

b

D

0

0

0

0

0

0

1

1

0

1

0

1

0

1

1

0

1

0

0

1

1

0

1

0

1

1

0

0

1

1

1

1

Tableau: 59.14  - Emprunts reportés pour la soustraction de bits

Maintenant, ligne par ligne, nous rajoutons l'emprunt sortant de la différence equation qui écrite ainsi, devient donc une somme S:

ee

a

b

S (D)

es

mintermes

0

0

0

0

0

equation

0

0

1

1

1

equation

0

1

0

1

0

equation

0

1

1

0

0

equation

1

0

0

1

1

equation

1

0

1

0

1

equation

1

1

0

0

0

equation

1

1

1

1

1

equation

Tableau: 59.15  - Identification des mintermes de la soustraction

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

equation   (59.30)

Une simplification triviale possible est:

equation   (59.31)

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

equation   (59.32)

Donc finalement:

equation   (59.33)

Remarque: La table de vérité de la soustraction sans emprunt entrant est appelée "demi-soustracteur".

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'informations 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ée à 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 classiques. 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 se 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 côté 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), la 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.

À 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:

equation
Figure: 59.14 - Application de la logique booléenne

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:

equation
Figure: 59.15 - Aspect flou de la logique... floue

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 même, la fonction "La vitesse est-elle peu élevée?" sera évaluée de la manière suivante selon:

equation
Figure: 59.16 - A l'inverse... le flou demeure...

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:

equation
Figure: 59.17 - Application pertinente de la logique floue

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), exponentielles, gaussiennes (dans le cas d'un état moyen) ou de toutes autres nature, sont utilisables telles que les méthodes que nous avons vues lors de notre étude des réseaux de neurones dans le chapitre de Méthodes Numériques:

equationequationequation
Figure: 59.18 - Exemples de transitions non linéaires

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:

equation
Figure: 59.19 - Entrée/Sortie floue

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

Un exemple consiste à prendre l'horizontale passant par le point d'ordonnée correspondant sur la courbe de départ à l'abscisse de la valeur de l'entrée et de regarder où cette horizontale coupe la courbe de sortie. L'abscisse de ce point d'intersection est une valeur de sortie possible comme représenté ci-dessous:

equation
Figure: 59.20 - Transposition entrée/sortie

Un deuxième exemple consiste à prendre comme valeur de sortie possible le centre de gravité du trapèze en grisé délimité par l'horizontale et la courbe de sortie comme représenté sur la figure ci-dessous:

equation
Figure: 59.21 - Autre transposition possible

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 equation sur X à valeurs dans l'intervalle [0,1].

Remarque: La fonction d'appartenance peut être fixée arbitrairement. Un problème des applications pratiques est pour l'ingénieur de définir ces fonctions (nous faisons généralement appel à des données statistiques ou à l'avis d'un expert).

La notion de sous-ensemble flou englobe celle de sous-ensemble classique pour laquelle equation 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 equation définie dans {0,1}, et telle que:

equation si x est dans A
equation si x n'est pas dans A
  (59.34)

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

exempleExemple:

Une fonction caractéristique possible pour définir le sous-ensemble A flou "avoir une vingtaine d'années" sur l'ensemble X des réels:

equation
Figure: 59.22 - Fonction floue centrée

Les notions suivantes sont caractéristiques de A:

Définitions:

D1. Support de A: equation

D2. Hauteur de A: equation

D3. A est dit normalisée si equation

Remarque: Les sous-ensembles flous considérés seront tous supposés normalisés, in extenso de hauteur égale à 1.

D4. Noyau de A: equation

D5. Cardinalité de A: equation

exempleExemple:

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

equation
Figure: 59.23 - Décomposition de la fonction floue centrée

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:

equation et equation   (59.35)

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

equation, et equation   (59.36)

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

equation   (59.37)

D8. Il y a inclusion si et seulement si:

equation   (59.38)

D9. L'intersection equation est définie par:

equation   (59.39)

D10. L'union equation est définie par:

equation   (59.40)

exempleExemple:

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

equation
Figure: 59.24 - Décomposition de la fonction floue centrée

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é" (figure de gauche ci-dessous) ainsi que celui des personnes "ayant une vingtaine d'années ou la majorité" (figure de droite ci-dessous):

equation
Figure: 59.25 - Résumé des résultats des différentes opérations logiques


Haut de page

FRACTALSCODES CORRECTEURS


Like4   Dislike0
66.67% sur 100%
Notée par 12 visiteur(s)
12345
Commentaires: [0] 
 
 


W3C - HTMLW3C - CSS Firefox
Ce travail est dans le domaine public
2002-2017 Sciences.ch

Haut de page