Équivalence logique
L'équivalence logique permet de déterminer si deux expressions booléennes représentent exactement la même fonction logique. Deux expressions sont logiquement équivalentes lorsqu'elles retournent toujours la même valeur, quelles que soient les valeurs attribuées à leurs variables.
Par exemple, les expressions :
| NON(A ET B) |
et :
| NON A OU NON B |
semblent différentes par leur forme, mais elles produisent la même valeur pour toutes les combinaisons possibles de `A` et de `B`. Elles sont donc logiquement équivalentes en vertu d'une loi de De Morgan.
L'équivalence logique joue un rôle essentiel dans la simplification des conditions, la transformation des programmes, l'optimisation des circuits numériques, la vérification formelle, la conception des compilateurs et la démonstration de propriétés mathématiques. Elle permet de remplacer une expression par une autre sans modifier le comportement observable du système.
En programmation, une expression plus courte n'est pas toujours préférable à une expression plus explicite. L'équivalence logique garantit uniquement que les résultats booléens sont identiques dans le modèle considéré. Il faut également tenir compte du court-circuit, des effets secondaires, des valeurs nulles et des règles propres au langage avant de remplacer effectivement une expression dans un programme.
Définition
Deux expressions booléennes :
| F |
et :
| G |
sont logiquement équivalentes lorsqu'elles possèdent la même valeur de vérité pour toutes les affectations possibles de leurs variables.
On écrit généralement :
| F ≡ G |
ou :
| F ↔ G |
Cette notation signifie que :
| F |
et :
| G |
définissent la même fonction booléenne.
Définition formelle
Soient deux fonctions booléennes :
| F : {0,1}n → {0,1} |
et :
| G : {0,1}n → {0,1} |
Elles sont équivalentes si, pour toute affectation :
| x ∈ {0,1}n |
on obtient :
| F(x) = G(x) |
Autrement dit, aucune combinaison de valeurs ne permet de distinguer les deux fonctions.
Exemple élémentaire
Considérons :
| F(A) = NON NON A |
et :
| G(A) = A |
Pour :
| A = FAUX |
on obtient :
| NON NON FAUX = NON VRAI = FAUX |
Pour :
| A = VRAI |
on obtient :
| NON NON VRAI = NON FAUX = VRAI |
Dans les deux cas :
| F(A) = G(A) |
On peut donc écrire :
| NON NON A ≡ A |
Équivalence et égalité
L'équivalence logique ne doit pas être confondue avec une égalité arithmétique ordinaire.
L'écriture :
| F ≡ G |
indique que les deux expressions possèdent le même comportement logique pour toutes les affectations.
L'écriture :
| F = G |
peut, selon le contexte, représenter :
- une égalité mathématique ;
- une comparaison dans un programme ;
- une affectation ;
- une définition ;
- une équation à résoudre.
Le symbole d'équivalence rend la relation logique plus explicite.
Équivalence et biconditionnelle
Le biconditionnel :
| F ↔ G |
est une expression booléenne.
Il retourne vrai lorsque `F` et `G` possèdent la même valeur.
L'équivalence logique :
| F ≡ G |
est une relation entre deux expressions.
On peut toutefois caractériser l'équivalence en disant :
| F ≡ G |
si et seulement si :
| F ↔ G |
est une tautologie.
Table de vérité du biconditionnel
| F | G | F ↔ G |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Le biconditionnel est vrai lorsque les deux opérandes sont identiques.
Critère par tautologie
Deux expressions sont équivalentes lorsque :
| F ↔ G |
est toujours vraie.
On peut donc vérifier :
| F ≡ G |
en démontrant :
| F ↔ G ≡ VRAI |
Cette méthode transforme un problème d'équivalence en un problème de validité logique.
Critère par OU exclusif
Le OU exclusif est vrai lorsque ses opérandes sont différents.
Ainsi, `F` et `G` sont équivalentes lorsque :
| F XOR G |
est toujours faux.
On peut écrire :
| F ≡ G |
si et seulement si :
| F XOR G ≡ FAUX |
Cette propriété est particulièrement utile dans les circuits numériques et les outils de vérification.
Méthodes de vérification
Plusieurs méthodes permettent de démontrer une équivalence logique :
- construire une table de vérité ;
- appliquer les lois de l'algèbre de Boole ;
- transformer les expressions en formes normales ;
- comparer leurs diagrammes de décision binaires ;
- utiliser un solveur SAT ;
- démontrer que leur XOR est insatisfaisable ;
- comparer les circuits obtenus ;
- tester exhaustivement les affectations lorsque leur nombre est faible.
Vérification par table de vérité
La table de vérité constitue la méthode la plus directe.
Elle consiste à :
- Identifier toutes les variables
- Énumérer leurs affectations
- Évaluer la première expression
- Évaluer la seconde expression
- Comparer les colonnes finales
Si les colonnes sont identiques, les expressions sont équivalentes.
Exemple avec les lois de De Morgan
Considérons :
| F = NON(A ET B) |
et :
| G = NON A OU NON B |
La table de vérité est :
| A | B | A ET B | NON(A ET B) | NON A | NON B | NON A OU NON B |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 |
Les deux dernières colonnes comparées sont identiques.
On conclut :
| NON(A ET B) ≡ NON A OU NON B |
Contre-exemple
Pour montrer que deux expressions ne sont pas équivalentes, il suffit de trouver une seule affectation produisant des résultats différents.
Considérons :
| F = A OU B |
et :
| G = A XOR B |
Pour :
|
A = 1 B = 1 |
on obtient :
| A OU B = 1 |
mais :
| A XOR B = 0 |
Les expressions ne sont donc pas équivalentes.
Principe du contre-exemple
Une équivalence exige l'égalité des résultats pour toutes les affectations.
Sa réfutation ne nécessite qu'un seul cas différent.
Ainsi :
|
Pour démontrer une équivalence : toutes les affectations doivent convenir. |
|
Pour réfuter une équivalence : une seule affectation différente suffit. |
Vérification algébrique
Une équivalence peut être démontrée en transformant progressivement une expression à l'aide des lois booléennes.
Par exemple :
| A ET (A OU B) |
Appliquons la distributivité :
| A ET (A OU B) ≡ (A ET A) OU (A ET B) |
Puis l'idempotence :
| (A ET A) OU (A ET B) ≡ A OU (A ET B) |
Enfin l'absorption :
| A OU (A ET B) ≡ A |
On obtient donc :
| A ET (A OU B) ≡ A |
Chaîne d'équivalences
Une démonstration algébrique peut être présentée sous la forme d'une chaîne :
|
Expression initiale ≡ Expression intermédiaire ≡ Expression intermédiaire ≡ Expression finale |
Chaque transformation doit être justifiée par une loi valide.
Par exemple :
|
NON(A OU B) ≡ NON A ET NON B |
La transformation est justifiée par la deuxième loi de De Morgan.
Réflexivité
Toute expression est équivalente à elle-même :
| F ≡ F |
Cette propriété est appelée réflexivité.
Elle découle du fait que chaque expression possède nécessairement le même résultat qu'elle-même pour toutes les affectations.
Symétrie
Si :
| F ≡ G |
alors :
| G ≡ F |
Cette propriété est appelée symétrie.
L'ordre dans lequel les expressions sont comparées ne modifie pas leur équivalence.
Transitivité
Si :
| F ≡ G |
et :
| G ≡ H |
alors :
| F ≡ H |
Cette propriété est appelée transitivité.
Elle permet d'enchaîner plusieurs transformations logiques.
Relation d'équivalence
Puisque l'équivalence logique est :
- réflexive ;
- symétrique ;
- transitive ;
elle constitue une véritable relation d'équivalence sur l'ensemble des expressions booléennes.
Elle divise les expressions en classes regroupant toutes les formes syntaxiques possédant le même comportement logique.
Classes d'équivalence
Les expressions suivantes appartiennent à la même classe :
| A |
| A ET VRAI |
| A OU FAUX |
| A ET A |
| NON NON A |
Elles représentent toutes exactement la fonction identité :
| F(A) = A |
Remplacement d'une sous-expression
Si :
| F ≡ G |
alors une occurrence de `F` peut généralement être remplacée par `G` dans une expression logique pure.
Par exemple, puisque :
|
NON(A ET B) ≡ NON A OU NON B |
l'expression :
| C OU NON(A ET B) |
peut être remplacée par :
| C OU NON A OU NON B |
sans changer sa fonction booléenne.
Principe de substitution
Le principe de substitution permet d'utiliser une équivalence à l'intérieur d'une expression plus grande.
Si :
| F ≡ G |
alors, pour un contexte logique pur `C`, on obtient :
| C[F] ≡ C[G] |
où `C[F]` représente le contexte contenant `F`.
Cette propriété rend possible la simplification locale des expressions.
Identité logique
Une identité logique est une équivalence vraie pour toutes les valeurs possibles de ses variables.
Par exemple :
| A OU FAUX ≡ A |
est une identité.
Les lois fondamentales de l'algèbre de Boole sont donc des familles d'équivalences logiques.
Lois d'identité
Les lois d'identité sont :
| A ET VRAI ≡ A |
| A OU FAUX ≡ A |
La constante vraie est l'élément neutre du ET.
La constante fausse est l'élément neutre du OU.
Lois de domination
Les lois de domination sont :
| A ET FAUX ≡ FAUX |
| A OU VRAI ≡ VRAI |
La constante fausse absorbe une conjonction.
La constante vraie absorbe une disjonction.
Lois d'idempotence
Les lois d'idempotence sont :
| A ET A ≡ A |
| A OU A ≡ A |
Répéter la même condition ne modifie pas son résultat logique.
Loi de double négation
La double négation restitue la valeur initiale :
| NON NON A ≡ A |
Cette loi est également appelée loi d'involution.
Lois de complémentarité
Une variable et son complément vérifient :
| A ET NON A ≡ FAUX |
| A OU NON A ≡ VRAI |
La première expression est une contradiction.
La seconde est une tautologie.
Lois commutatives
L'ordre des opérandes peut être inversé :
| A ET B ≡ B ET A |
| A OU B ≡ B OU A |
Cette propriété ne s'applique pas nécessairement aux opérations contenant des effets secondaires dans un programme.
Lois associatives
Le regroupement d'opérations identiques peut être modifié :
|
(A ET B) ET C ≡ A ET (B ET C) |
|
(A OU B) OU C ≡ A OU (B OU C) |
Les parenthèses peuvent donc être déplacées sans modifier la fonction logique.
Lois distributives
Le ET se distribue sur le OU :
|
A ET (B OU C) ≡ (A ET B) OU (A ET C) |
Le OU se distribue également sur le ET :
|
A OU (B ET C) ≡ (A OU B) ET (A OU C) |
Cette seconde distributivité distingue l'algèbre de Boole de plusieurs structures algébriques ordinaires.
Lois d'absorption
Les lois d'absorption sont :
|
A OU (A ET B) ≡ A |
|
A ET (A OU B) ≡ A |
La présence du terme plus restrictif ne change pas le résultat déjà déterminé par `A`.
Première loi de De Morgan
La négation d'une conjonction est équivalente à la disjonction des négations :
|
NON(A ET B) ≡ NON A OU NON B |
En langage naturel :
| Il n'est pas vrai que A et B |
équivaut à :
| A est faux ou B est faux |
Deuxième loi de De Morgan
La négation d'une disjonction est équivalente à la conjonction des négations :
|
NON(A OU B) ≡ NON A ET NON B |
En langage naturel :
| Ni A ni B |
signifie que les deux propositions sont fausses.
Généralisation de De Morgan
Pour plusieurs variables :
|
NON(A1 ET A2 ET ... ET An) ≡ NON A1 OU NON A2 OU ... OU NON An |
et :
|
NON(A1 OU A2 OU ... OU An) ≡ NON A1 ET NON A2 ET ... ET NON An |
La négation inverse l'opérateur et nie chaque opérande.
Implication
L'implication logique :
| A → B |
est équivalente à :
| NON A OU B |
Cette équivalence permet d'éliminer l'opérateur d'implication d'une expression.
Démonstration de l'implication
| A | B | A → B | NON A | NON A OU B |
|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 1 |
Les deux colonnes finales sont identiques.
Donc :
|
A → B ≡ NON A OU B |
Contraposée
Une implication est équivalente à sa contraposée :
|
A → B ≡ NON B → NON A |
Cette propriété est très utilisée dans les démonstrations mathématiques.
Elle ne doit pas être confondue avec la réciproque.
Réciproque
La réciproque de :
| A → B |
est :
| B → A |
Ces deux expressions ne sont généralement pas équivalentes.
Par exemple :
|
Être divisible par 4 implique être pair. |
Mais :
| Être pair |
n'implique pas nécessairement :
| Être divisible par 4. |
Inverse
L'inverse d'une implication :
| A → B |
est :
| NON A → NON B |
L'inverse n'est généralement pas équivalent à l'implication initiale.
En revanche, l'inverse est équivalent à la réciproque.
Biconditionnelle
Le biconditionnel :
| A ↔ B |
est équivalent à la conjonction de deux implications :
|
(A → B) ET (B → A) |
On peut donc écrire :
|
A ↔ B ≡ (A → B) ET (B → A) |
Autres formes de l'équivalence
Le biconditionnel peut également s'écrire :
|
A ↔ B ≡ (A ET B) OU (NON A ET NON B) |
Cette expression indique que les deux variables sont toutes les deux vraies ou toutes les deux fausses.
Équivalence et XNOR
L'opérateur XNOR retourne vrai lorsque ses deux opérandes sont identiques.
Ainsi :
|
A XNOR B ≡ A ↔ B |
Il correspond au complément du XOR :
|
A XNOR B ≡ NON(A XOR B) |
XOR
Le OU exclusif peut être exprimé par :
|
A XOR B ≡ (A OU B) ET NON(A ET B) |
Une autre forme est :
|
A XOR B ≡ (A ET NON B) OU (NON A ET B) |
Ces deux expressions décrivent le cas où exactement une variable est vraie.
Négation du XOR
La négation du XOR est l'équivalence :
|
NON(A XOR B) ≡ A ↔ B |
Le XOR détecte une différence.
Le XNOR ou biconditionnel détecte une égalité logique.
Équivalence par formes normales
Deux expressions peuvent être transformées dans une même forme normale.
Si leurs formes normales canoniques sont identiques, elles représentent la même fonction.
Les principales formes sont :
- la forme normale disjonctive ;
- la forme normale conjonctive ;
- la forme canonique disjonctive ;
- la forme canonique conjonctive.
Forme canonique disjonctive
La forme canonique disjonctive est construite à partir des lignes où la fonction vaut vrai.
Chaque ligne vraie produit un minterme.
La fonction est ensuite la disjonction de tous ces mintermes.
Deux expressions possédant les mêmes lignes vraies auront la même forme canonique disjonctive.
Exemple de forme canonique
Considérons le XOR :
| A | B | A XOR B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Les lignes vraies donnent :
| NON A ET B |
et :
| A ET NON B |
Donc :
|
A XOR B ≡ (NON A ET B) OU (A ET NON B) |
Forme canonique conjonctive
La forme canonique conjonctive est construite à partir des lignes où la fonction vaut faux.
Chaque ligne fausse produit un maxterme.
La fonction est ensuite la conjonction de tous ces maxtermes.
Cette forme fournit une autre représentation unique à l'ordre des termes près.
Équivalence par diagramme de décision
Un diagramme de décision binaire représente une fonction booléenne sous forme de graphe.
Deux expressions possédant le même diagramme de décision binaire réduit et ordonné représentent la même fonction, à condition d'utiliser le même ordre de variables.
Cette méthode est utilisée dans :
- la vérification de circuits ;
- la vérification de logiciels ;
- les systèmes symboliques ;
- les outils de synthèse logique.
Équivalence par solveur SAT
Pour vérifier :
| F ≡ G |
on peut construire :
| F XOR G |
Puis demander à un solveur SAT s'il existe une affectation rendant cette expression vraie.
Si le solveur trouve une affectation, celle-ci constitue un contre-exemple.
S'il démontre que l'expression est insatisfaisable, `F` et `G` sont équivalentes.
Mitre d'équivalence
Une structure fréquemment utilisée en vérification de circuits est appelée mitre d'équivalence.
Elle combine les sorties de deux circuits à l'aide d'un XOR :
|
Différence = SortieCircuit1 XOR SortieCircuit2 |
Si Différence ne peut jamais devenir vraie, les deux circuits sont équivalents.
Équivalence de circuits
Deux circuits logiques sont fonctionnellement équivalents lorsqu'ils produisent les mêmes sorties pour toutes les entrées possibles.
Ils peuvent pourtant avoir :
- un nombre différent de portes ;
- une profondeur différente ;
- une disposition différente ;
- des portes de types différents ;
- des délais de propagation différents.
L'équivalence fonctionnelle ne signifie donc pas une identité physique.
Exemple de circuit équivalent
Le circuit réalisant :
| NON(A ET B) |
peut utiliser une seule porte NAND.
Un autre circuit peut utiliser :
- une porte ET ;
- suivie d'une porte NON.
Les deux circuits sont logiquement équivalents, même si leur construction matérielle diffère.
Équivalence et simplification
Une expression simplifiée doit rester équivalente à l'expression initiale.
Par exemple :
|
A ET B OU A ET NON B |
Factorisons `A` :
| A ET (B OU NON B) |
Puis :
|
B OU NON B ≡ VRAI |
Donc :
|
A ET VRAI ≡ A |
Finalement :
|
(A ET B) OU (A ET NON B) ≡ A |
Vérification de la simplification
Chaque étape doit conserver l'équivalence.
| (A ET B) OU (A ET NON B) |
| ≡ A ET (B OU NON B) |
| ≡ A ET VRAI |
| ≡ A |
La chaîne complète constitue une démonstration algébrique.
Simplification d'une condition
Considérons :
| CompteActif ET ( EstAdministrateur OU NON EstAdministrateur ) |
La parenthèse est une tautologie :
| EstAdministrateur OU NON EstAdministrateur ≡ VRAI |
L'expression devient :
| CompteActif ET VRAI |
puis :
| CompteActif |
Factorisation
La distributivité permet également de factoriser une expression.
|
(A ET B) OU (A ET C) |
est équivalente à :
| A ET (B OU C) |
La forme factorisée utilise généralement moins d'occurrences de `A`.
Développement
L'opération inverse consiste à développer :
| A ET (B OU C) |
en :
|
(A ET B) OU (A ET C) |
Les deux formes sont équivalentes, mais elles ne possèdent pas nécessairement le même coût dans un programme ou un circuit.
Équivalence logique et coût
Deux expressions équivalentes peuvent avoir des coûts différents.
Elles peuvent différer par :
- le nombre d'opérations ;
- le nombre d'appels de fonctions ;
- la profondeur logique ;
- le nombre de portes ;
- la consommation mémoire ;
- le délai d'exécution ;
- les possibilités de court-circuit.
L'équivalence fonctionnelle ne garantit donc pas une performance identique.
Équivalence mathématique et programme
Dans l'algèbre de Boole pure :
|
A ET B ≡ B ET A |
Cependant, dans un programme, les expressions :
| FonctionA() ET FonctionB() |
et :
| FonctionB() ET FonctionA() |
peuvent ne pas avoir le même comportement observable si les fonctions produisent des effets secondaires.
Effets secondaires
Un effet secondaire peut être :
- la modification d'une variable ;
- l'écriture dans un fichier ;
- l'affichage d'un message ;
- la modification d'une base de données ;
- l'envoi d'une requête ;
- le lancement d'une exception.
Dans ce cas, la commutativité logique ne garantit pas l'équivalence opérationnelle du programme.
Exemple d'effet secondaire
Considérons :
|
IncrémenterCompteur() ET VérifierLimite() |
et :
|
VérifierLimite() ET IncrémenterCompteur() |
Les résultats logiques pourraient être identiques dans certains cas, mais la vérification ne porte pas sur la même valeur du compteur.
Les deux programmes ne sont donc pas nécessairement équivalents.
Court-circuit et équivalence
Dans l'algèbre de Boole :
| A ET B ≡ B ET A |
Avec le court-circuit, l'ordre détermine quelle expression peut être ignorée.
Si `A` est faux dans :
| A ET B |
`B` n'est pas évaluée.
Dans :
| B ET A |
`B` est évaluée en premier.
Les expressions restent équivalentes sur leur résultat booléen si les opérandes sont purs, mais pas nécessairement sur leurs effets.
Expression pure
Une expression pure :
- ne modifie aucun état ;
- ne dépend pas d'un ordre d'exécution caché ;
- retourne le même résultat pour les mêmes entrées ;
- ne produit pas d'effet observable autre que sa valeur.
Les lois d'équivalence peuvent être appliquées plus directement aux expressions pures.
Exceptions
Deux expressions logiquement équivalentes peuvent ne pas être opérationnellement équivalentes si l'une provoque une exception évitée par l'autre.
Par exemple :
|
Objet ≠ NUL ET Objet.EstValide() |
est sécuritaire avec le court-circuit.
La forme commutée :
|
Objet.EstValide() ET Objet ≠ NUL |
peut tenter d'accéder à un objet nul avant la vérification.
Valeurs nulles
L'algèbre de Boole classique utilise uniquement :
|
VRAI FAUX |
Un langage ou une base de données peut ajouter :
|
NUL INCONNU INDÉTERMINÉ |
Les équivalences classiques doivent alors être vérifiées dans la logique réellement utilisée.
Logique ternaire de SQL
SQL utilise généralement les valeurs :
|
TRUE FALSE UNKNOWN |
en présence de `NULL`.
Certaines équivalences booléennes classiques demeurent valides, tandis que d'autres transformations impliquant des comparaisons ou des valeurs nulles peuvent produire des résultats inattendus.
Il faut employer les règles de la logique ternaire SQL.
Exemple avec NULL
L'expression SQL :
- Valeur = NULL
ne retourne généralement pas `TRUE`, même si `Valeur` est nulle.
Elle retourne plutôt :
| UNKNOWN |
Il faut utiliser :
- Valeur IS NULL
Les deux expressions ne sont donc pas équivalentes.
Équivalence contextuelle
Deux expressions peuvent être équivalentes dans un contexte précis sans l'être dans tous les contextes.
Par exemple, si l'on sait que :
| A implique toujours B |
alors :
| A ET B |
peut se simplifier en :
| A |
dans ce domaine particulier.
Sans cette hypothèse, l'équivalence n'est pas générale.
Hypothèses
Une équivalence conditionnelle peut être écrite sous la forme :
|
Sous l'hypothèse H, F ≡ G |
Les contraintes du domaine doivent être mentionnées explicitement.
Une simplification reposant sur une hypothèse non documentée peut devenir incorrecte si les données changent.
Équivalence sémantique
L'équivalence sémantique signifie que les expressions possèdent le même sens ou le même comportement pour toutes les interprétations considérées.
Dans l'algèbre de Boole, elle correspond à l'identité des tables de vérité.
Elle s'oppose à la simple ressemblance syntaxique.
Équivalence syntaxique
Deux expressions sont syntaxiquement identiques lorsqu'elles utilisent exactement la même structure et les mêmes symboles.
Par exemple :
| A ET B |
et :
| A ET B |
sont syntaxiquement identiques.
En revanche :
| A ET B |
et :
| B ET A |
sont syntaxiquement différentes, mais logiquement équivalentes.
Équivalence structurelle
Dans certains outils, une comparaison structurelle vérifie si deux arbres syntaxiques possèdent la même forme.
Une comparaison fonctionnelle vérifie plutôt si les expressions produisent les mêmes résultats.
Une équivalence structurelle implique généralement une équivalence fonctionnelle, mais l'inverse n'est pas vrai.
Équivalence forte et faible
Dans les programmes, plusieurs niveaux d'équivalence peuvent être distingués :
- même résultat booléen ;
- mêmes effets secondaires ;
- même ordre d'effets ;
- mêmes exceptions ;
- mêmes performances asymptotiques ;
- même utilisation mémoire ;
- même comportement concurrent.
L'équivalence logique ne concerne principalement que le résultat logique.
Équivalence dans un compilateur
Un compilateur peut remplacer une expression par une forme équivalente afin de :
- supprimer des calculs inutiles ;
- réduire le nombre de branches ;
- propager des constantes ;
- simplifier les conditions ;
- produire un meilleur code machine ;
- diminuer le nombre d'instructions.
Ces transformations doivent préserver le comportement défini par le langage.
Repliement de constantes
Considérons :
| A ET VRAI |
Le compilateur peut la remplacer par :
| A |
De même :
| A OU FAUX |
peut devenir :
| A |
Ces transformations sont des applications directes des identités booléennes.
Propagation de constantes
Si le compilateur sait que :
| ModeDiagnostic = FAUX |
alors :
|
ModeDiagnostic ET ExécuterDiagnostic |
peut être simplifié en :
| FAUX |
Le code dépendant uniquement de cette condition peut ensuite être supprimé.
Élimination de branche
Considérons :
|
SI A OU VRAI ALORS Bloc1 SINON Bloc2 FIN SI |
La condition est équivalente à :
| VRAI |
Le compilateur peut conserver directement `Bloc1` et supprimer `Bloc2` s'il n'existe aucun effet nécessaire dans la condition.
Vérification formelle
La vérification formelle utilise l'équivalence pour démontrer qu'une transformation conserve le comportement d'un système.
Elle peut comparer :
- deux versions d'un circuit ;
- un programme source et une version optimisée ;
- une spécification et une implémentation ;
- deux règles d'autorisation ;
- deux expressions de contraintes.
Refactorisation
Lors d'une refactorisation, une condition peut être réécrite pour améliorer sa lisibilité.
Avant :
|
NON( NON CompteActif OU CompteSuspendu ) |
Après application de De Morgan :
|
CompteActif ET NON CompteSuspendu |
Les deux expressions sont logiquement équivalentes, mais la seconde exprime plus directement l'état d'un compte utilisable.
Équivalence de règles métier
Une règle métier écrite en langage naturel peut posséder plusieurs traductions logiques.
Règle :
|
L'accès est refusé si le compte est inactif ou suspendu. |
Expression de refus :
|
NON CompteActif OU CompteSuspendu |
Expression d'autorisation équivalente :
|
CompteActif ET NON CompteSuspendu |
La seconde est la négation de la condition de refus.
Vérification d'une règle de médiation
Supposons qu'un dossier soit admissible lorsque les deux parties ont demandé la médiation.
L'expression directe est :
|
DemandeDemandeur ET DemandeDéfendeur |
La condition de non-admissibilité est :
|
NON( DemandeDemandeur ET DemandeDéfendeur ) |
Par De Morgan :
|
NON DemandeDemandeur OU NON DemandeDéfendeur |
Le dossier n'est donc pas admissible lorsqu'au moins une partie n'a pas demandé la médiation.
Équivalence dans les tests
Les tests peuvent confirmer qu'une transformation conserve les résultats.
Pour deux fonctions :
| F |
et :
| G |
on peut tester toutes les affectations lorsque le nombre de variables est faible.
|
POUR CHAQUE affectation ASSERTION( F(affectation) = G(affectation) ) FIN POUR |
Limite des tests
Tester plusieurs cas ne démontre pas toujours une équivalence générale lorsque l'espace d'entrée est très grand ou infini.
Pour `n` variables booléennes, un test exhaustif nécessite :
| 2n |
affectations.
Lorsque `n` est élevé, une démonstration symbolique ou un solveur devient préférable.
Complexité de la vérification exhaustive
Si les expressions possèdent :
| n |
variables, la table de vérité comporte :
| 2n |
lignes.
Si l'évaluation d'une expression demande `m` opérations, le coût total est approximativement :
| O(m × 2n) |
Cette croissance exponentielle limite la méthode exhaustive.
Algorithme de vérification exhaustive
|
MODULE SontÉquivalentes(F,G,Variables) n ← NOMBRE(Variables) POUR Affectation ← 0 JUSQU'À 2n-1 ValeurF ← Évaluer(F,Affectation) ValeurG ← Évaluer(G,Affectation) SI ValeurF ≠ ValeurG ALORS RETOURNER FAUX FIN SI FIN POUR RETOURNER VRAI |
L'algorithme peut s'arrêter dès qu'un contre-exemple est trouvé.
Retour du contre-exemple
Une version plus utile peut retourner l'affectation fautive.
|
MODULE TrouverDifférence(F,G) POUR CHAQUE Affectation SI F(Affectation) ≠ G(Affectation) ALORS RETOURNER Affectation FIN SI FIN POUR RETOURNER AUCUNE_DIFFÉRENCE |
Le contre-exemple facilite le diagnostic de l'erreur.
Exemple en Java
- public final class EquivalenceLogique {
-
- private EquivalenceLogique() {
- }
-
- public static boolean expressionF(
- boolean a,
- boolean b
- ) {
- return !(a && b);
- }
-
- public static boolean expressionG(
- boolean a,
- boolean b
- ) {
- return !a || !b;
- }
-
- public static boolean sontEquivalentes() {
- boolean[] valeurs = {
- false,
- true
- };
-
- for (boolean a : valeurs) {
- for (boolean b : valeurs) {
- if (
- expressionF(a, b)
- != expressionG(a, b)
- ) {
- return false;
- }
- }
- }
-
- return true;
- }
-
- public static void main(String[] args) {
- System.out.println(
- "Expressions équivalentes : "
- + sontEquivalentes()
- );
- }
- }
Résultat du programme Java
Le programme évalue les quatre affectations possibles :
|
A = FAUX, B = FAUX A = FAUX, B = VRAI A = VRAI, B = FAUX A = VRAI, B = VRAI |
Les deux fonctions produisent toujours la même valeur.
Le programme affiche :
| Expressions équivalentes : true |
Exemple en Pascal
- Program EquivalenceLogique;
-
- function ExpressionF(
- A: Boolean;
- B: Boolean
- ): Boolean;
- begin
- ExpressionF := not (A and B);
- end;
-
- function ExpressionG(
- A: Boolean;
- B: Boolean
- ): Boolean;
- begin
- ExpressionG := (not A) or (not B);
- end;
-
- var
- A: Boolean;
- B: Boolean;
- Equivalentes: Boolean;
- I: Integer;
- J: Integer;
-
- BEGIN
- Equivalentes := True;
-
- for I := 0 to 1 do
- begin
- A := I = 1;
-
- for J := 0 to 1 do
- begin
- B := J = 1;
-
- if ExpressionF(A, B)
- <> ExpressionG(A, B) then
- begin
- Equivalentes := False;
- end;
- end;
- end;
-
- WriteLn(
- 'Expressions équivalentes : ',
- Equivalentes
- );
- END.
Exemple en Python
- def expression_f(a, b):
- return not (a and b)
-
-
- def expression_g(a, b):
- return (not a) or (not b)
-
-
- def sont_equivalentes():
- valeurs = (False, True)
-
- for a in valeurs:
- for b in valeurs:
- if expression_f(a, b) != expression_g(a, b):
- return False, (a, b)
-
- return True, None
-
-
- equivalentes, contre_exemple = (
- sont_equivalentes()
- )
-
- print(
- "Expressions équivalentes :",
- equivalentes,
- )
-
- if contre_exemple is not None:
- print(
- "Contre-exemple :",
- contre_exemple,
- )
Exemple en C#
- static bool ExpressionF(
- bool a,
- bool b)
- {
- return !(a && b);
- }
-
- static bool ExpressionG(
- bool a,
- bool b)
- {
- return !a || !b;
- }
-
- static bool SontEquivalentes()
- {
- bool[] valeurs = { false, true };
-
- foreach (bool a in valeurs)
- {
- foreach (bool b in valeurs)
- {
- if (
- ExpressionF(a, b)
- != ExpressionG(a, b)
- )
- {
- return false;
- }
- }
- }
-
- return true;
- }
Table des équivalences principales
| Expression | Expression équivalente |
|---|---|
| NON NON A | A |
| A ET VRAI | A |
| A OU FAUX | A |
| A ET FAUX | FAUX |
| A OU VRAI | VRAI |
| A ET A | A |
| A OU A | A |
| A ET NON A | FAUX |
| A OU NON A | VRAI |
| NON(A ET B) | NON A OU NON B |
| NON(A OU B) | NON A ET NON B |
| A → B | NON A OU B |
| A ↔ B | (A ET B) OU (NON A ET NON B) |
| A XOR B | (A ET NON B) OU (NON A ET B) |
| A OU (A ET B) | A |
| A ET (A OU B) | A |
| (A ET B) OU (A ET C) | A ET (B OU C) |
| (A OU B) ET (A OU C) | A OU (B ET C) |
Stratégie de simplification
Une stratégie générale de simplification peut être :
- Éliminer les implications
- Éliminer les biconditionnelles
- Appliquer les lois de De Morgan
- Supprimer les doubles négations
- Appliquer les identités
- Appliquer l'idempotence
- Rechercher les compléments
- Utiliser l'absorption
- Factoriser ou développer
- Vérifier l'équivalence finale
L'ordre exact dépend de l'expression et du résultat recherché.
Exemple complet de simplification
Simplifions :
|
NON( NON A OU ( A ET B ) ) |
Appliquons De Morgan :
|
NON NON A ET NON(A ET B) |
Supprimons la double négation :
|
A ET NON(A ET B) |
Appliquons De Morgan :
|
A ET ( NON A OU NON B ) |
Distribuons :
|
(A ET NON A) OU (A ET NON B) |
Appliquons la complémentarité :
|
FAUX OU (A ET NON B) |
Puis l'identité :
| A ET NON B |
Ainsi :
|
NON( NON A OU ( A ET B ) ) ≡ A ET NON B |
Vérification par table
| A | B | Expression initiale | A ET NON B |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
Les colonnes finales sont identiques.
La transformation est confirmée.
Équivalence et lisibilité
La forme la plus courte n'est pas toujours la plus lisible.
Par exemple :
|
NON( CompteInactif OU CompteSuspendu ) |
est équivalente à :
|
NON CompteInactif ET NON CompteSuspendu |
Mais une meilleure modélisation pourrait utiliser :
|
CompteActif ET NON CompteSuspendu |
La lisibilité dépend aussi du choix des noms.
Équivalence et intention
Deux expressions peuvent être équivalentes sans exprimer aussi clairement la même intention métier.
qPar exemple :
|
Âge < 18 OU Âge >= 18 |
est équivalente à :
| VRAI |
La première forme montre toutefois une séparation en deux cas, tandis que la seconde montre directement que la condition est universelle.
Le contexte détermine la forme la plus appropriée.
Équivalence et maintenance
Une expression bien structurée facilite :
- la compréhension ;
- la modification ;
- les tests ;
- l'identification des règles métier ;
- la détection des erreurs ;
- la réutilisation des sous-conditions.
Une simplification trop agressive peut rendre une condition mathématiquement courte, mais moins compréhensible pour les développeurs.
Bonnes pratiques
Pour utiliser correctement l'équivalence logique, il est recommandé de :
- justifier chaque transformation par une loi valide ;
- utiliser une table de vérité pour les expressions simples ;
- chercher un contre-exemple lorsqu'une équivalence semble douteuse ;
- distinguer équivalence syntaxique et équivalence sémantique ;
- tenir compte des effets secondaires ;
- préserver l'ordre nécessaire au court-circuit ;
- vérifier les valeurs nulles et inconnues ;
- utiliser des parenthèses explicites ;
- privilégier une forme lisible ;
- tester les règles de sécurité ;
- documenter les hypothèses du domaine ;
- utiliser un solveur pour les expressions importantes et complexes.
Erreurs fréquentes
Les erreurs courantes comprennent :
- considérer deux expressions semblables comme équivalentes sans preuve ;
- vérifier seulement quelques affectations ;
- confondre implication et équivalence ;
- confondre implication et réciproque ;
- oublier la priorité des opérateurs ;
- appliquer incorrectement une loi de De Morgan ;
- oublier de nier chaque opérande ;
- distribuer un opérateur de manière incorrecte ;
- appliquer une loi booléenne classique dans une logique ternaire ;
- permuter des appels de fonctions ayant des effets secondaires ;
- ignorer les exceptions et le court-circuit ;
- supposer qu'une expression plus courte est toujours meilleure ;
- utiliser une hypothèse non documentée ;
- confondre le XOR avec le OU inclusif.
Tableau récapitulatif
| Notion | Description |
|---|---|
| Équivalence logique | Même résultat pour toutes les affectations |
| Biconditionnelle | Vraie lorsque deux valeurs sont identiques |
| Tautologie d'équivalence | F ↔ G toujours vraie |
| XOR de différence | F XOR G toujours faux si F ≡ G |
| Contre-exemple | Affectation où les résultats diffèrent |
| Identité logique | Équivalence valide pour toutes les variables |
| Substitution | Remplacement d'une expression par une équivalente |
| Table de vérité | Vérification exhaustive des affectations |
| Simplification algébrique | Transformation par les lois booléennes |
| Forme canonique | Représentation déterminée par la table de vérité |
| Équivalence fonctionnelle | Même relation entre entrées et sorties |
| Équivalence opérationnelle | Même comportement observable du programme |
| Mitre d'équivalence | XOR entre les sorties de deux systèmes |
| Solveur SAT | Recherche d'une affectation différenciant les expressions |
Avantages
L'équivalence logique présente plusieurs avantages :
- elle permet de simplifier les expressions booléennes ;
- elle garantit la conservation du résultat logique ;
- elle facilite l'optimisation des circuits ;
- elle permet de vérifier les transformations des compilateurs ;
- elle aide à reformuler les règles métier ;
- elle fournit une méthode rigoureuse de comparaison ;
- elle permet de détecter les conditions redondantes ;
- elle facilite la conversion entre différentes formes normales ;
- elle soutient la vérification formelle ;
- elle permet de construire des circuits uniquement avec NAND ou NOR ;
- elle aide à réduire les expressions utilisées dans les programmes.
Limites et précautions
L'équivalence logique possède néanmoins certaines limites :
- la table de vérité croît exponentiellement avec le nombre de variables ;
- l'équivalence booléenne ne préserve pas nécessairement les effets secondaires ;
- le court-circuit peut modifier l'ordre des appels ;
- des expressions équivalentes peuvent avoir des performances différentes ;
- les exceptions peuvent rendre une transformation dangereuse ;
- les valeurs nulles peuvent introduire une logique non booléenne ;
- une équivalence peut dépendre d'hypothèses particulières ;
- une expression minimale peut être moins lisible ;
- les comparaisons de chaînes et d'objets dépendent du langage ;
- l'équivalence fonctionnelle d'un circuit ne garantit pas le même délai ;
- la concurrence peut rendre l'ordre des opérations observable.
Remarque
L'équivalence logique constitue l'un des principaux outils de l'algèbre de Boole. Elle permet d'affirmer que deux expressions, malgré des formes syntaxiques différentes, définissent exactement la même fonction logique. Cette propriété rend possibles la simplification, la factorisation, la transformation en formes normales et la vérification des circuits ou des programmes.
La table de vérité fournit une méthode simple et rigoureuse lorsque le nombre de variables est faible. Les lois booléennes permettent des démonstrations symboliques plus élégantes, tandis que les diagrammes de décision et les solveurs SAT rendent possible l'analyse de systèmes plus complexes.
Dans un programme réel, l'équivalence du résultat booléen ne suffit toutefois pas toujours. Les effets secondaires, les exceptions, le court-circuit, les valeurs nulles et l'ordre d'évaluation doivent également être pris en compte. Une transformation logiquement valide doit donc être appliquée avec prudence afin de préserver non seulement la valeur finale, mais aussi le comportement observable du programme.