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:
2015-09-06 16:36:16 | {oUUID 1.794}
Version: 2.2 Révision 4 | Rédacteur: Vincent ISOZ | Avancement:
~80%
vues
depuis
le 2012-01-01:
4'098
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
(plus formellement notés ).
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é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:
(59.1)
Cet énoncé
prend généralement la forme d'un tableau à
n+1 colonnes et au plus
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
contenant deux éléments particuliers, ,
(formes abstraites 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 telle 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")
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 .
C'est la raison pour laquelle les vrais opérateurs d'une
algèbre
de Boole sont normalement le
(ET) et la (différence
symétrique) donnée par l'opération logique:
(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 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 ).
Remarques:
R1.
Ainsi, les opérations et
admettent
chacune un élément neutre tel que le chiffre 1 est l'élément neutre
de et
le chiffre 0 l'élément neutre de
R2. Les deux opérations que nous utilisons habituellement pour
former une algèbre de Boole sont le "ou inclusif" noté
rigoureusement mais
plus fréquemment par le signe d'addition "+", et le et
"et inclusif" noté rigoureusement
mais plus fréquemment par le signe de multiplication " ".
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).
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:
(59.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.
Voyons maintenant ce que nous appelons le "théorème
des constantes" qui consiste à prouver que:
(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
et à son élément neutre (0) par rapport au
.
Démontrons maintenant la relation suivante:
(59.5)
Démonstration:
La distributivité nous amène
à écrire:
(59.6)
et en appliquant la complémentation:
(59.7)
en appliquant la commutativité:
(59.8)
et enfin en appliquant le théorème des constantes:
(59.9)
C.Q.F.D.
Cette démonstration va nous permettre de démontrer
le fameux "théorème
du consensus":
(59.10)
Démonstration:
Pour vérifier le théorème
du consensus relatif au produit logique:
(59.11)
nous pouvons faire usage
d'un diagramme de Venn où nous voyons bien que le terme
est contenu dans les deux autres:
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:
(59.12)
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!):
(59.13)
Démonstrations:

et:
(59.14)
C.Q.F.D.
Revenons maintenant sur les
théorèmes de De Morgan précédemment
présentés
comme des axiomes:
(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
juste. Alors en vertu des relations
et (axiome
de complémentation) nous devons avoir:
(59.16)
Donc il nous faut prouver
que ces deux relations sont exactes:
(59.17)
et:
(59.18)
Le deuxième théorème de De Morgan se démontre
de la même façon.
C.Q.F.D.
Remarque: Ces deux théorèmes peuvent s'étendre à un
nombre quelconque de variables.
Corollaires:
(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
aussi donc):
F1. Sous la
forme d'une somme de produits logiques, appelée "forme
normale disjonctive F.N.D.", tel que (exemple):
(59.20)
Les termes
constitutifs de ce polynôme sont les monômes .
Les variables ou complémentaires de ces monômes sont
les "lettres" .
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):
(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...):
Figure: 59.2 - Portes logiques
et leurs "tables de vérité" respectives:
Tableau: 59.2
- Table de vérité ET
Tableau: 59.3
- Table de vérité OU
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)
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
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
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
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
À 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:
(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:
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
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:
(59.23)
ou
encore:
(59.24)
Cette
simplification possible ce fait toujours avec deux mintermes
adjacents dans la table de Karnaugh tels que:
Figure: 59.4 - Table de Karnaugh associée
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 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:
Figure: 59.5 - Table de Karnaugh à trois variables
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 adjacentes sont là
où b vaut partout 1.
Une autre manière
de simplifier:

Figure: 59.6 - Table de Karnaugh à trois variables avec autre méthode de simplification
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 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.
Exemple:
Soit 1=01 correspondant à et
2 = 11 correspondant à ba, la somme (forme disjonctive)
nous donnerait donc
ce qui se réduit à l'aide de la règle de complémentation
directement à .
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:
Figure: 59.7 - Premier type de réduction possible
R2. Quand deux 1 sont aux
extrémités du tableau:
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:

Figure: 59.9 - Troisième type de réduction possible
R4. Une colonne pleine fait
disparaître deux variables DC dans ce cas:

Figure: 59.10 - Quatrième type de réduction possible
R5. Quatre cases font
disparaître deux variables A et C dans ce cas:

Figure: 59.11 - Cinquième type de réduction possible
R6. La même case peut
servir à deux réductions:
Figure: 59.12 - Septième type de réduction possible
R7. La même case peut
servir à deux réductions:
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
(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 toutes les valeurs possibles sur 3 bits (trois lettres)
soit 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:
(59.25)
ligne
par ligne (sans penser à la retenue sortante 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 (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 |
|
0 |
0 |
1 |
1 |
0 |

|
0 |
1 |
0 |
1 |
0 |
|
0 |
1 |
1 |
0 |
1 |
|
1 |
0 |
0 |
1 |
0 |

|
1 |
0 |
1 |
0 |
1 |
|
1 |
1 |
0 |
0 |
1 |

|
1 |
1 |
1 |
1 |
1 |
|
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:
(59.26)
Une simplification possible
est:
(59.27)
Il vient également
pour la retenue sortante les mintermes suivants:
(59.28)
Donc finalement nous avons:
(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 (emprunt
sortant) et l'emprunt reporté (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 ()
prennent toutes les valeurs possibles sur 3 bits (trois lettres)
soit
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 ,
nous allons calculer
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
ligne par ligne (sans penser à l'emprunt )
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 qui
écrite ainsi, devient donc une somme S:
ee |
a |
b |
S (D) |
es |
mintermes |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
1 |
1 |
1 |
|
0 |
1 |
0 |
1 |
0 |

|
0 |
1 |
1 |
0 |
0 |
|
1 |
0 |
0 |
1 |
1 |
|
1 |
0 |
1 |
0 |
1 |

|
1 |
1 |
0 |
0 |
0 |

|
1 |
1 |
1 |
1 |
1 |
|
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:
(59.30)
Une simplification triviale
possible est:
(59.31)
Il vient également
pour l'emprunt sortant les mintermes suivants:
(59.32)
Donc finalement:
(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:
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:
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:
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:
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:

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

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:
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
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
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
(59.34)
Les fonctions indicatrices
sont souvent des intermédiaires techniques très pratiques!
Exemple:
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:
Figure: 59.22 - Fonction floue centrée
Les notions suivantes sont
caractéristiques de A:
Définitions:
D1. Support de A:
D2. Hauteur de A:
D3. A est dit normalisée
si
Remarque: Les sous-ensembles flous considérés seront
tous supposés normalisés, in extenso de hauteur égale
à 1.
D4. Noyau de A:
D5. Cardinalité de
A:
Exemple:
Avec l'exemple de la figure précédente:
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:
et
(59.35)
2. A est "plus précis"
que B si:
,
et
(59.36)
D7. Il y a égalité
entre deux sous-ensembles flous si et seulement si:
(59.37)
D8. Il y a inclusion si et
seulement si:
(59.38)
D9. L'intersection
est définie par:
(59.39)
D10. L'union
est définie par:
(59.40)
Exemple:
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!):

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

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