Dualité de l'algèbre de Boole
La dualité de l'algèbre de Boole est un principe fondamental selon lequel toute identité booléenne valide possède une seconde identité, appelée son duale, qui est également valide. Cette identité duale est obtenue en échangeant simultanément les opérations ET et OU, ainsi que les constantes 0 et 1.
Ainsi, à partir de l'identité :
| A OU 0 = A |
on obtient sa duale :
| A ET 1 = A |
Les deux expressions appartiennent à une même paire de lois booléennes. Il n'est donc pas nécessaire de démontrer séparément chacune d'elles : lorsqu'une loi est établie à partir des axiomes de l'algèbre de Boole, sa forme duale est automatiquement valide.
La dualité révèle la symétrie interne de l'algèbre de Boole. Les opérations ET et OU ne sont pas identiques, mais elles jouent des rôles complémentaires. De la même manière, les constantes 0 et 1 représentent deux éléments opposés qui peuvent être échangés lorsque les opérateurs correspondants sont également permutés.
En programmation et en logique numérique, ce principe facilite la transformation des expressions, la mémorisation des lois, la conception de circuits complémentaires et le passage entre des représentations fondées sur des conjonctions et des représentations fondées sur des disjonctions.
Définition de la dualité
Le dual d'une expression booléenne est obtenu en appliquant les substitutions suivantes :
| ET ↔ OU |
et :
| 0 ↔ 1 |
Les variables et leurs compléments ne sont pas remplacés.
Par exemple, le dual de :
| A ET 1 |
est :
| A OU 0 |
Le dual de :
| A OU B |
est :
| A ET B |
Principe de dualité
Le principe de dualité peut être formulé ainsi :
- Si une identité est valide dans une algèbre de Boole, alors l'identité obtenue en échangeant ET avec OU et 0 avec 1 est également valide.
Sous une forme symbolique, si :
| E1 = E2 |
est une identité booléenne, alors :
| Dual(E1) = Dual(E2) |
est aussi une identité booléenne.
Transformations fondamentales
Pour produire le dual d'une expression, il faut effectuer simultanément les transformations suivantes :
| Élément original | Élément dual |
|---|---|
| ET | OU |
| OU | ET |
| 0 | 1 |
| 1 | 0 |
| Variable A | Variable A |
| Complément NON A | Complément NON A |
| Égalité = | Égalité = |
La négation n'est donc pas remplacée par une autre opération.
Les variables sont conservées
Lorsqu'on construit une expression duale, les variables demeurent inchangées.
Le dual de :
| A ET B |
est :
| A OU B |
Les variables :
|
A B |
restent les mêmes.
Seul l'opérateur placé entre elles est échangé.
La négation est conservée
Le complément d'une variable demeure également inchangé.
Le dual de :
| NON A ET B |
est :
| NON A OU B |
On ne remplace pas :
| NON A |
par :
| A |
La dualité et la complémentation sont deux transformations distinctes.
Dual d'une constante
Les constantes booléennes sont échangées :
| Dual(0) = 1 |
et :
| Dual(1) = 0 |
Cette substitution doit accompagner l'échange des opérateurs ET et OU.
Changer seulement les constantes ou seulement les opérateurs ne produit généralement pas le dual correct.
Exemple élémentaire
Considérons l'expression :
| A ET 0 |
Pour obtenir son dual :
| ET devient OU |
et :
| 0 devient 1 |
On obtient donc :
| A OU 1 |
Les deux expressions sont liées par le principe de dualité.
Identités duales
L'identité :
| A ET 0 = 0 |
possède pour duale :
| A OU 1 = 1 |
La première affirme qu'une conjonction avec faux est toujours fausse.
La seconde affirme qu'une disjonction avec vrai est toujours vraie.
Dualité des éléments neutres
L'identité de l'opérateur OU est :
| A OU 0 = A |
Sa duale est l'identité de l'opérateur ET :
| A ET 1 = A |
Ainsi :
- 0 est l'élément neutre du OU ;
- 1 est l'élément neutre du ET.
Dualité des éléments absorbants
L'identité :
| A OU 1 = 1 |
possède pour duale :
| A ET 0 = 0 |
Ainsi :
- 1 est absorbant pour le OU ;
- 0 est absorbant pour le ET.
Tableau des identités et de leurs duales
| Identité | Identité duale |
|---|---|
| A OU 0 = A | A ET 1 = A |
| A OU 1 = 1 | A ET 0 = 0 |
| A OU A = A | A ET A = A |
| A OU NON A = 1 | A ET NON A = 0 |
| A OU (A ET B) = A | A ET (A OU B) = A |
| A OU (B ET C) = (A OU B) ET (A OU C) | A ET (B OU C) = (A ET B) OU (A ET C) |
Ce tableau montre que les lois booléennes apparaissent naturellement par paires.
Dualité de l'idempotence
La loi d'idempotence du OU est :
| A OU A = A |
Sa duale est :
| A ET A = A |
Dans les deux cas, répéter une même valeur ne modifie pas le résultat.
Dualité de la complémentarité
La loi :
| A OU NON A = 1 |
possède pour duale :
| A ET NON A = 0 |
La première représente le tiers exclu ou une tautologie.
La seconde représente une contradiction.
Dualité de l'absorption
La loi d'absorption :
| A OU (A ET B) = A |
possède pour duale :
| A ET (A OU B) = A |
Ces deux lois permettent de supprimer une sous-expression rendue inutile par la présence de `A`.
Exemple d'absorption
Considérons :
|
EstAdministrateur OU ( EstAdministrateur ET PossèdePermission ) |
Cette expression se simplifie en :
| EstAdministrateur |
Sa forme duale serait :
|
EstAdministrateur ET ( EstAdministrateur OU PossèdePermission ) |
Elle se simplifie également en :
| EstAdministrateur |
Dualité de la distributivité
L'algèbre de Boole possède deux lois distributives.
La première est :
|
A ET (B OU C) = (A ET B) OU (A ET C) |
Sa duale est :
|
A OU (B ET C) = (A OU B) ET (A OU C) |
Contrairement à l'algèbre arithmétique ordinaire, les deux opérations booléennes sont distributives l'une par rapport à l'autre.
Vérification du dual distributif
Partons de :
|
A ET (B OU C) = (A ET B) OU (A ET C) |
Effectuons les remplacements :
| ET ↔ OU |
On obtient :
|
A OU (B ET C) = (A OU B) ET (A OU C) |
Aucune constante n'étant présente, aucun remplacement entre 0 et 1 n'est nécessaire.
Dualité de la commutativité
La loi de commutativité du ET est :
| A ET B = B ET A |
Sa duale est :
| A OU B = B OU A |
L'ordre des opérandes n'influence donc ni la conjonction ni la disjonction.
Dualité de l'associativité
La loi d'associativité du ET est :
|
(A ET B) ET C = A ET (B ET C) |
Sa duale est :
|
(A OU B) OU C = A OU (B OU C) |
Ces identités permettent de regrouper plusieurs opérations identiques sans modifier le résultat.
Dualité des lois de De Morgan
Les deux lois de De Morgan forment également une paire duale :
|
NON(A ET B) = NON A OU NON B |
et :
|
NON(A OU B) = NON A ET NON B |
Pour passer de l'une à l'autre, on échange :
| ET |
avec :
| OU |
La négation est conservée.
Dualité et complémentation
La dualité ne doit pas être confondue avec le complément d'une expression.
Le complément de :
| A ET B |
est :
| NON(A ET B) |
qui peut être transformé par De Morgan en :
| NON A OU NON B |
Le dual de :
| A ET B |
est simplement :
| A OU B |
Ces résultats sont différents.
Tableau comparatif
| Transformation | Résultat appliqué à A ET B |
|---|---|
| Dualité | A OU B |
| Complémentation | NON(A ET B) |
| De Morgan | NON A OU NON B |
| Commutativité | B ET A |
Chaque transformation poursuit un objectif différent.
Dual d'une expression composée
Considérons :
| A ET (B OU 0) |
Pour produire son dual :
| ET devient OU |
| OU devient ET |
| 0 devient 1 |
Le résultat est :
| A OU (B ET 1) |
Simplification du dual
L'expression duale :
| A OU (B ET 1) |
peut être simplifiée, car :
| B ET 1 = B |
On obtient alors :
| A OU B |
L'expression initiale se simplifiait également :
|
A ET (B OU 0) = A ET B |
Les formes simplifiées restent duales :
| A ET B |
et :
| A OU B |
Exemple avec plusieurs opérations
Considérons :
| (A OU 0) ET (B OU 1) |
Le dual est obtenu ainsi :
| (A ET 1) OU (B ET 0) |
La simplification donne :
| A OU 0 |
puis :
| A |
L'expression initiale donne également :
|
A ET 1 = A |
Dans ce cas particulier, l'expression et son dual se simplifient vers la même variable.
Méthode systématique
Pour construire le dual d'une expression :
- Copier entièrement l'expression
- Remplacer chaque ET par OU
- Remplacer chaque OU par ET
- Remplacer chaque 0 par 1
- Remplacer chaque 1 par 0
- Conserver les variables
- Conserver les négations
- Conserver les parenthèses
- Simplifier seulement après la transformation
Il est important de ne pas simplifier trop tôt si cela risque de masquer la structure originale.
Algorithme de dualisation
|
MODULE Dual(Expression) SI Expression = 0 ALORS RETOURNER 1 FIN SI SI Expression = 1 ALORS RETOURNER 0 FIN SI SI Expression est une variable ALORS RETOURNER Expression FIN SI SI Expression = NON SousExpression ALORS RETOURNER NON Dual(SousExpression) FIN SI SI Expression = Gauche ET Droite ALORS RETOURNER Dual(Gauche) OU Dual(Droite) FIN SI SI Expression = Gauche OU Droite ALORS RETOURNER Dual(Gauche) ET Dual(Droite) FIN SI |
Cet algorithme parcourt récursivement l'arbre syntaxique.
Dualisation d'un arbre syntaxique
Considérons :
| A ET (B OU 0) |
Son arbre syntaxique est :
|
ET / \ A OU / \ B 0 |
La dualisation remplace les nouds et les constantes :
|
OU / \ A ET / \ B 1 |
Le résultat correspond à :
| A OU (B ET 1) |
Dual du dual
Appliquer deux fois la transformation duale restitue l'expression initiale.
| Dual(Dual(E)) = E |
En effet :
| ET → OU → ET |
| OU → ET → OU |
| 0 → 1 → 0 |
| 1 → 0 → 1 |
La dualité est donc une transformation involutive.
Exemple de double dual
Partons de :
| A ET (B OU 0) |
Son dual est :
| A OU (B ET 1) |
Le dual de cette nouvelle expression est :
| A ET (B OU 0) |
On retrouve exactement l'expression de départ.
Expression auto-duale
Une fonction booléenne est dite auto-duale lorsque son dual, en tenant compte du complément approprié des entrées et de la sortie selon la définition fonctionnelle, représente la même fonction.
Dans le contexte élémentaire des expressions, on peut aussi rencontrer des structures dont le dual se simplifie vers une forme équivalente à l'expression initiale.
L'auto-dualité est une notion plus avancée que la simple production du dual syntaxique.
Définition fonctionnelle de l'auto-dualité
Une fonction booléenne :
| f(x1,x2,...,xn) |
est auto-duale lorsqu'elle vérifie :
|
f(NON x1, NON x2, ..., NON xn) = NON f(x1,x2,...,xn) |
pour toutes les affectations possibles.
Cette propriété signifie que le complément de toutes les entrées entraîne le complément de la sortie.
Exemple d'une fonction auto-duale
La fonction identité :
| f(A) = A |
est auto-duale, car :
|
f(NON A) = NON A |
et :
|
NON f(A) = NON A |
Les deux expressions sont identiques.
Fonction non auto-duale
La fonction :
| f(A,B) = A ET B |
n'est pas auto-duale.
En effet :
|
f(NON A,NON B) = NON A ET NON B |
tandis que :
|
NON f(A,B) = NON(A ET B) = NON A OU NON B |
Les deux résultats ne sont pas généralement équivalents.
Dualité des fonctions booléennes
Pour une fonction booléenne :
| f(x1,...,xn) |
sa fonction duale peut être définie par :
|
fd(x1,...,xn) = NON f( NON x1, ..., NON xn ) |
Cette définition fonctionnelle correspond à l'échange systématique des opérations ET et OU ainsi que des constantes 0 et 1 dans une expression représentant `f`.
Exemple avec la fonction ET
Soit :
| f(A,B) = A ET B |
La fonction duale est :
|
fd(A,B) = NON f(NON A,NON B) |
Donc :
|
fd(A,B) = NON( NON A ET NON B ) |
Par De Morgan :
|
fd(A,B) = A OU B |
La fonction duale du ET est donc le OU.
Exemple avec une constante
Soit la fonction constante :
| f(A) = 0 |
Sa fonction duale est :
|
fd(A) = NON f(NON A) |
Comme :
| f(NON A) = 0 |
on obtient :
| fd(A) = 1 |
La fonction constante fausse a pour duale la fonction constante vraie.
Démonstration par dualité
Le principe de dualité réduit le nombre de démonstrations nécessaires.
Si l'on démontre :
| A OU 0 = A |
il n'est pas nécessaire de redémontrer séparément :
| A ET 1 = A |
Cette seconde identité est la duale de la première.
Pourquoi le principe fonctionne
Les axiomes définissant une algèbre de Boole sont eux-mêmes symétriques par rapport aux transformations :
| ET ↔ OU |
et :
| 0 ↔ 1 |
Lorsqu'une démonstration utilise uniquement des axiomes et des règles préservés par cette transformation, sa version duale constitue automatiquement une démonstration valide.
Démonstration duale étape par étape
Supposons qu'une démonstration établisse :
|
A OU (A ET B) = A |
En remplaçant chaque opération par sa duale, chaque étape de la démonstration devient une étape valide pour :
|
A ET (A OU B) = A |
La dualisation s'applique donc à l'ensemble du raisonnement, et pas seulement au résultat final.
Dualité des axiomes
Une présentation axiomatique de l'algèbre de Boole comporte fréquemment des lois apparaissant par paires.
Par exemple :
| A OU 0 = A |
et :
| A ET 1 = A |
ou :
|
A OU (B ET C) = (A OU B) ET (A OU C) |
et :
|
A ET (B OU C) = (A ET B) OU (A ET C) |
Chaque membre d'une paire est le dual de l'autre.
Dualité et théorie des ensembles
L'algèbre des ensembles fournit une interprétation concrète de la dualité.
Les correspondances sont :
| Algèbre de Boole | Théorie des ensembles |
|---|---|
| ET | Intersection ∩ |
| OU | Union ∪ |
| 0 | Ensemble vide ∅ |
| 1 | Ensemble universel U |
| NON | Complément |
Le principe de dualité devient alors :
| ∩ ↔ ∪ |
et :
| ∅ ↔ U |
Exemple ensembliste
L'identité :
| A ∪ ∅ = A |
possède pour duale :
| A ∩ U = A |
La première affirme que l'union avec l'ensemble vide ne modifie pas un ensemble.
La seconde affirme que l'intersection avec l'ensemble universel ne le modifie pas non plus.
Dualité en théorie des ensembles
L'identité :
| A ∪ U = U |
possède pour duale :
| A ∩ ∅ = ∅ |
De même :
| A ∪ Ac = U |
a pour duale :
| A ∩ Ac = ∅ |
Les lois ensemblistes reproduisent donc exactement les paires duales booléennes.
Dualité et intervalles logiques
Dans l'interprétation ordonnée d'une algèbre de Boole :
| 0 |
représente le plus petit élément, tandis que :
| 1 |
représente le plus grand.
L'opération ET correspond à une forme de borne inférieure, tandis que l'opération OU correspond à une forme de borne supérieure.
La dualité échange donc les notions de minimum et de maximum.
Ordre booléen
On peut définir :
| A ≤ B |
lorsque :
| A ET B = A |
De manière duale, cette relation équivaut à :
| A OU B = B |
Les deux formulations décrivent la même relation d'ordre sous deux perspectives duales.
Dualité dans les treillis
Une algèbre de Boole est un type particulier de treillis complémenté et distributif.
Dans un treillis :
- le ET correspond à l'infimum ;
- le OU correspond au supremum ;
- 0 correspond à l'élément minimal ;
- 1 correspond à l'élément maximal.
Le treillis dual échange l'infimum avec le supremum et l'élément minimal avec l'élément maximal.
Dualité et circuits logiques
Dans les circuits numériques, une expression construite avec des portes ET et OU peut être transformée en une structure duale en échangeant :
| portes ET ↔ portes OU |
ainsi que les niveaux logiques constants :
| 0 ↔ 1 |
Les inverseurs demeurent des inverseurs.
Exemple de circuit dual
Considérons la fonction :
|
S = A ET (B OU C) |
Son circuit contient :
- une porte OU combinant `B` et `C` ;
- une porte ET combinant ce résultat avec `A`.
Le circuit dual réalise :
|
Sd = A OU (B ET C) |
Il contient :
- une porte ET combinant `B` et `C` ;
- une porte OU combinant ce résultat avec `A`.
Dualité entre NAND et NOR
Les opérations NAND et NOR sont liées par dualité.
Le NAND est défini par :
|
A NAND B = NON(A ET B) |
En échangeant ET et OU, on obtient :
| NON(A OU B) |
qui correspond au NOR.
Ainsi :
| NAND ↔ NOR |
dans une transformation duale.
Dualité des portes universelles
Les portes NAND et NOR sont toutes deux fonctionnellement complètes.
Toute fonction booléenne peut être construite :
- uniquement avec des portes NAND ;
- ou uniquement avec des portes NOR.
La dualité explique la symétrie entre ces deux familles de réalisations.
Réseau de portes NAND
Une réalisation fondée sur NAND utilise généralement des transformations issues de De Morgan pour remplacer les opérations ET et OU.
Sa structure duale conduit souvent à une réalisation correspondante utilisant uniquement des portes NOR.
Les deux réseaux ne sont pas nécessairement identiques en coût ou en délai, mais ils réalisent des transformations logiques duales.
Dualité et formes normales
La forme normale disjonctive et la forme normale conjonctive sont duales.
Une forme normale disjonctive est une disjonction de conjonctions :
|
(A ET B) OU (C ET D) |
Sa structure duale est une conjonction de disjonctions :
|
(A OU B) ET (C OU D) |
Somme de produits
Une expression sous forme de somme de produits utilise :
- des produits logiques construits par ET ;
- une somme logique construite par OU.
Exemple :
|
(A ET B) OU (NON A ET C) |
Sa forme structurellement duale est un produit de sommes.
Produit de sommes
Le dual structurel de l'expression précédente est :
|
(A OU B) ET (NON A OU C) |
Cette expression est constituée :
- de sommes logiques utilisant OU ;
- réunies par un produit logique utilisant ET.
Mintermes et maxtermes
Les mintermes et les maxtermes sont liés par dualité.
Un minterme est une conjonction de littéraux.
Exemple :
| A ET NON B ET C |
Un maxterme est une disjonction de littéraux.
Exemple dual :
| A OU NON B OU C |
Attention aux formes canoniques
Construire le dual syntaxique d'un minterme donne une disjonction contenant les mêmes littéraux.
Cependant, la correspondance précise entre les lignes d'une table de vérité et les maxtermes exige également de tenir compte des conventions de complémentation utilisées.
Il faut donc distinguer :
- la dualisation syntaxique ;
- la construction canonique depuis une table de vérité.
Dualité et programmation
Les langages de programmation n'offrent généralement pas un opérateur permettant de calculer automatiquement le dual d'une expression.
Le principe demeure toutefois utile pour :
- reformuler les conditions ;
- dériver une règle complémentaire ;
- construire des prédicats symétriques ;
- vérifier des simplifications ;
- concevoir des filtres ;
- transformer des circuits ou des expressions symboliques.
Exemple de règle métier duale
Considérons la condition :
|
CompteActif ET PossèdePermission |
Sa duale syntaxique est :
|
CompteActif OU PossèdePermission |
Il faut toutefois éviter de supposer que cette duale représente automatiquement la négation ou l'opposé métier de la première condition.
La dualité est une transformation algébrique, et non une interprétation sémantique de la règle.
Dualité et négation d'une condition
La négation de :
|
CompteActif ET PossèdePermission |
est :
|
NON CompteActif OU NON PossèdePermission |
Sa duale est seulement :
|
CompteActif OU PossèdePermission |
Ces deux résultats ne doivent pas être confondus.
Utilisation dans un système symbolique
Un système de calcul symbolique peut représenter une expression sous la forme d'un arbre et appliquer automatiquement la transformation duale.
Par exemple :
|
ET( A, OU(B,0) ) |
devient :
|
OU( A, ET(B,1) ) |
La transformation est purement structurelle.
Représentation d'une expression
Une représentation possible est :
|
Variable("A") Constante(0) Non(Expression) Et(Gauche,Droite) Ou(Gauche,Droite) |
Une fonction de dualisation peut alors parcourir récursivement ces types de nouds.
Exemple en pseudocode
|
TYPE NoeudBooléen Type Gauche Droite Valeur FIN TYPE |
Puis :
|
MODULE ConstruireDual(Noeud) SELON Noeud.Type CAS CONSTANTE_FAUX RETOURNER CONSTANTE_VRAI CAS CONSTANTE_VRAI RETOURNER CONSTANTE_FAUX CAS VARIABLE RETOURNER COPIE(Noeud) CAS NON RETOURNER NON( ConstruireDual( Noeud.Gauche ) ) CAS ET RETOURNER OU( ConstruireDual(Noeud.Gauche), ConstruireDual(Noeud.Droite) ) CAS OU RETOURNER ET( ConstruireDual(Noeud.Gauche), ConstruireDual(Noeud.Droite) ) FIN SELON |
Complexité de la dualisation
Si une expression contient :
| n |
noeuds, chaque noud doit être examiné une fois.
La complexité temporelle est donc :
| O(n) |
Si une nouvelle expression est créée, la mémoire nécessaire est également :
| O(n) |
Une transformation en place peut parfois réduire l'utilisation mémoire.
Exemple en Java
- sealed interface Expression
- permits Variable, Constante, Non, Et, Ou {
- }
-
- record Variable(String nom)
- implements Expression {
- }
-
- record Constante(boolean valeur)
- implements Expression {
- }
-
- record Non(Expression operande)
- implements Expression {
- }
-
- record Et(Expression gauche, Expression droite)
- implements Expression {
- }
-
- record Ou(Expression gauche, Expression droite)
- implements Expression {
- }
-
- public final class DualiteBooleenne {
-
- private DualiteBooleenne() {
- }
-
- public static Expression dual(
- Expression expression
- ) {
- if (expression instanceof Variable variable) {
- return variable;
- }
-
- if (expression instanceof Constante constante) {
- return new Constante(
- !constante.valeur()
- );
- }
-
- if (expression instanceof Non non) {
- return new Non(
- dual(non.operande())
- );
- }
-
- if (expression instanceof Et et) {
- return new Ou(
- dual(et.gauche()),
- dual(et.droite())
- );
- }
-
- if (expression instanceof Ou ou) {
- return new Et(
- dual(ou.gauche()),
- dual(ou.droite())
- );
- }
-
- throw new IllegalArgumentException(
- "Type d'expression inconnu."
- );
- }
- }
Analyse de l'exemple Java
La méthode :
- dual
applique les règles suivantes :
- une variable est conservée ;
- une constante est inversée ;
- une négation est conservée, mais son opérande est dualisé ;
- un noeud ET devient un noeud OU ;
- un noeud OU devient un noeud ET.
L'algorithme reproduit directement la définition du dual syntaxique.
Vérification automatique
Un programme peut vérifier le principe :
| Dual(Dual(E)) = E |
en construisant le dual d'une expression, puis le dual du résultat.
Il faut comparer les structures produites, éventuellement après une normalisation des parenthèses et des opérations associatives.
Normalisation
Deux expressions peuvent être logiquement équivalentes sans posséder exactement le même arbre syntaxique.
Par exemple :
| (A ET B) ET C |
et :
| A ET (B ET C) |
sont équivalentes par associativité.
Une vérification structurelle stricte les considérerait pourtant comme différentes.
Une normalisation peut être nécessaire avant la comparaison.
Vérification par table de vérité
Pour une expression comportant peu de variables, il est possible de vérifier sa relation avec sa fonction duale par une table de vérité.
La définition fonctionnelle impose :
|
fd(x1,...,xn) = NON f( NON x1, ..., NON xn ) |
Chaque ligne de la table peut être testée directement.
Exemple de table avec ET et OU
| A | B | A ET B | A OU B | NON((NON A) ET (NON B)) |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 |
La dernière colonne est identique à celle de `A OU B`.
Cela confirme que le OU est la fonction duale du ET.
Dualité et simplification
Lorsqu'une règle de simplification est connue, sa duale fournit immédiatement une seconde règle.
Par exemple :
| A OU (A ET B) = A |
permet de déduire :
| A ET (A OU B) = A |
Un moteur de simplification peut donc générer automatiquement les règles duales.
Base de règles de réécriture
Une règle peut être représentée ainsi :
|
Motif : A OU (A ET B) Remplacement : A |
Sa duale devient :
|
Motif : A ET (A OU B) Remplacement : A |
Cela réduit le travail nécessaire pour construire une bibliothèque complète de transformations.
Dualité dans les démonstrations automatiques
Les systèmes de démonstration automatique peuvent exploiter la dualité pour :
- produire des théorèmes supplémentaires ;
- réduire le nombre de règles primitives ;
- vérifier la symétrie d'une base axiomatique ;
- générer des cas de test ;
- construire des transformations complémentaires.
Le principe agit alors comme un mécanisme de génération de connaissances.
Dualité et tests logiciels
Une fonction transformant des expressions booléennes peut être testée à l'aide de propriétés générales.
Par exemple :
| Dual(Dual(E)) = E |
est une propriété fondamentale.
On peut également vérifier :
| Dual(0) = 1 |
| Dual(1) = 0 |
|
Dual(A ET B) = Dual(A) OU Dual(B) |
Tests fondés sur les propriétés
Un générateur peut créer aléatoirement des arbres booléens, puis vérifier :
| Dual(Dual(Expression)) |
contre l'expression initiale.
Cette approche est appelée test fondé sur les propriétés.
Elle permet de détecter des erreurs dans les transformations récursives.
Erreur : remplacer les variables
Une erreur fréquente consiste à remplacer :
| A |
par :
| NON A |
pendant la dualisation.
Cette opération correspond à une complémentation des entrées, et non à la dualisation syntaxique directe.
Les variables et leurs négations doivent rester telles quelles.
Erreur : oublier les constantes
Considérons :
| A ET 0 |
Remplacer seulement ET par OU donnerait :
| A OU 0 |
Cette expression n'est pas le dual correct.
Il faut également remplacer :
| 0 |
par :
| 1 |
Le dual correct est :
| A OU 1 |
Erreur : échanger uniquement 0 et 1
De même, remplacer uniquement les constantes dans :
| A ET 0 |
donnerait :
| A ET 1 |
Cette expression n'est pas le dual complet.
Il faut également transformer ET en OU :
| A OU 1 |
Erreur : transformer NON
La négation ne possède pas une opération duale différente.
Le dual de :
| NON A |
reste :
| NON A |
Dans une expression plus complexe :
| NON(A ET B) |
le dual est :
| NON(A OU B) |
Erreur : confondre dual et équivalent
Une expression et son dual ne sont pas nécessairement équivalents.
Par exemple :
| A ET B |
et :
| A OU B |
produisent des résultats différents pour plusieurs affectations.
Le principe de dualité affirme que le dual d'une identité valide est également une identité valide. Il n'affirme pas qu'une expression isolée est égale à son dual.
Exemple important
L'identité :
| A ET 1 = A |
est valide.
Sa duale :
| A OU 0 = A |
est également valide.
Cependant, les expressions :
| A ET 1 |
et :
| A OU 0 |
sont ici équivalentes seulement parce qu'elles se simplifient toutes deux en `A`.
Dans le cas général :
| A ET B |
n'est pas équivalent à :
| A OU B |
Erreur : confondre dual et réciproque
Dans une implication :
| A → B |
la réciproque est :
| B → A |
La contraposée est :
| NON B → NON A |
Ces transformations ne correspondent pas au principe de dualité ET-OU.
La logique des implications doit donc être distinguée de la dualité booléenne structurelle.
Dualité dans les conditions de programme
Une condition métier ne doit pas être remplacée par sa duale sans analyser son sens.
Par exemple :
|
UtilisateurAuthentifié ET CompteActif |
exige les deux conditions.
Sa duale :
|
UtilisateurAuthentifié OU CompteActif |
n'exige plus qu'une seule condition et peut être beaucoup moins sécuritaire.
La validité algébrique du principe ne signifie pas que les deux règles répondent au même besoin.
Utilisation correcte en programmation
La dualité est surtout utile pour :
- dériver des identités ;
- transformer des représentations symboliques ;
- générer des règles de simplification ;
- concevoir des circuits duals ;
- comprendre les formes normales ;
- vérifier la symétrie des lois.
Elle ne doit pas servir à modifier arbitrairement une condition fonctionnelle.
Exemple de dérivation
Supposons que l'on connaisse :
| A OU (A ET B) = A |
Pour dériver une nouvelle simplification :
|
1. Remplacer OU par ET 2. Remplacer ET par OU 3. Conserver A et B |
On obtient :
| A ET (A OU B) = A |
Cette nouvelle loi peut alors être appliquée à une expression de programme.
Exemple de simplification de programme
Expression :
|
CompteActif ET ( CompteActif OU AutorisationSpéciale ) |
Par absorption duale :
| A ET (A OU B) = A |
on obtient :
| CompteActif |
La sous-condition d'autorisation spéciale était inutile dans cette structure précise.
Dualité et documentation
Présenter les lois booléennes par paires duales facilite leur apprentissage.
Par exemple :
|
Identité du OU : A OU 0 = A Identité du ET : A ET 1 = A |
La relation entre les deux lois devient immédiatement visible.
Organisation des lois par paires
Une documentation peut utiliser la structure suivante :
| Catégorie | Loi | Duale |
|---|---|---|
| Identité | A OU 0 = A | A ET 1 = A |
| Absorption | A OU 1 = 1 | A ET 0 = 0 |
| Idempotence | A OU A = A | A ET A = A |
| Complément | A OU NON A = 1 | A ET NON A = 0 |
| Distributivité | A OU (B ET C) | A ET (B OU C) |
Cette présentation évite de traiter chaque formule comme une règle isolée.
Exemple complet de dualisation
Considérons l'identité :
|
A OU ( B ET ( C OU 0 ) ) = ( A OU B ) ET ( A OU C ) |
Cette identité n'est pas correctement équilibrée telle quelle pour toutes les valeurs sans tenir compte de la simplification du terme interne. Prenons plutôt la distributivité valide :
|
A OU (B ET C) = (A OU B) ET (A OU C) |
Son dual est :
|
A ET (B OU C) = (A ET B) OU (A ET C) |
Chaque OU est remplacé par ET et chaque ET par OU.
Exemple avec constantes
Partons de :
|
A OU ( B ET 0 ) = A |
Cette identité est valide, car :
| B ET 0 = 0 |
puis :
| A OU 0 = A |
Son dual est :
|
A ET ( B OU 1 ) = A |
Cette identité est valide, car :
| B OU 1 = 1 |
puis :
| A ET 1 = A |
Tableau de vérification
| A | B | A OU (B ET 0) | A ET (B OU 1) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 |
Dans ce cas, les deux expressions donnent toutes deux `A`.
Cette égalité particulière ne doit pas être généralisée à toute paire d'expressions duales.
Dualité dans la logique positive
Une expression booléenne est dite positive lorsqu'elle est construite sans négation explicite des variables, à partir de :
|
ET OU 0 1 |
Dans ce contexte, la dualisation est particulièrement directe, car seuls les opérateurs et les constantes doivent être échangés.
Dualité avec négations imbriquées
Considérons :
|
NON( A ET ( NON B OU 0 ) ) |
Son dual est :
|
NON( A OU ( NON B ET 1 ) ) |
Les deux négations sont conservées à leur position.
Simplification après dualisation
L'expression duale précédente contient :
| NON B ET 1 |
qui se simplifie en :
| NON B |
On obtient donc :
|
NON( A OU NON B ) |
La simplification doit utiliser les lois booléennes habituelles.
Dualité et programmation fonctionnelle
Une expression booléenne peut être représentée par une structure de données immuable.
Une fonction récursive peut ensuite produire son dual sans modifier l'expression initiale.
Cette approche facilite :
- les tests ;
- la composition ;
- l'annulation des transformations ;
- la conservation de l'historique ;
- la comparaison des arbres.
Exemple fonctionnel conceptuel
|
Dual(Variable A) = Variable A |
|
Dual(Constante Faux) = Constante Vrai |
|
Dual(Et X Y) = Ou(Dual X, Dual Y) |
|
Dual(Ou X Y) = Et(Dual X, Dual Y) |
Cette définition correspond à un parcours structurel.
Applications
La dualité de l'algèbre de Boole est utilisée dans :
- la démonstration d'identités ;
- la simplification des expressions ;
- la conception de circuits numériques ;
- la transformation NAND-NOR ;
- la théorie des ensembles ;
- les treillis et structures ordonnées ;
- les formes normales ;
- les systèmes de calcul symbolique ;
- les compilateurs ;
- les solveurs logiques ;
- la génération automatique de règles ;
- les tests fondés sur les propriétés ;
- la documentation mathématique.
Avantages
Le principe de dualité présente plusieurs avantages :
- il réduit le nombre de lois à mémoriser séparément ;
- il permet de dériver immédiatement une identité à partir d'une autre ;
- il révèle la symétrie entre ET et OU ;
- il met en relation les constantes 0 et 1 ;
- il simplifie les démonstrations ;
- il facilite la conception de circuits complémentaires ;
- il explique la relation entre NAND et NOR ;
- il relie les formes disjonctives et conjonctives ;
- il s'applique naturellement à la théorie des ensembles ;
- il permet de générer des règles de réécriture ;
- il offre des propriétés utiles pour tester les logiciels symboliques.
Limites et précautions
Le principe de dualité exige plusieurs précautions :
- ET et OU doivent être échangés simultanément ;
- 0 et 1 doivent également être échangés simultanément ;
- les variables ne doivent pas être complémentées ;
- les négations doivent être conservées ;
- le dual d'une expression n'est pas nécessairement équivalent à l'expression ;
- la dualité ne correspond pas à la négation ;
- la dualité ne correspond pas à la réciproque d'une implication ;
- une condition métier ne doit pas être remplacée arbitrairement par sa duale ;
- la simplification doit être effectuée après une transformation correcte ;
- les formes canoniques demandent des conventions supplémentaires ;
- l'auto-dualité fonctionnelle est plus subtile que la dualité syntaxique ;
- la documentation du contexte doit préciser la notation utilisée.
Erreurs fréquentes
Les erreurs courantes comprennent :
- remplacer ET par OU sans échanger 0 et 1 ;
- échanger 0 et 1 sans transformer les opérateurs ;
- remplacer une variable par son complément ;
- supprimer les négations ;
- appliquer les lois de De Morgan à la place de la dualité ;
- croire que l'expression et son dual ont toujours la même valeur ;
- confondre dualité et complémentation ;
- modifier le sens d'une règle de sécurité ;
- oublier de conserver les parenthèses ;
- simplifier partiellement avant d'avoir terminé la transformation ;
- confondre un dual syntaxique avec une fonction auto-duale.
Tableau récapitulatif
| Notion | Description |
|---|---|
| Dualité | Symétrie entre deux formulations booléennes |
| Dual d'une expression | Expression obtenue par échanges systématiques |
| Échange des opérations | ET ↔ OU |
| Échange des constantes | 0 ↔ 1 |
| Variables | Conservées |
| Négations | Conservées |
| Principe de dualité | Le dual d'une identité valide est valide |
| Double dual | Restitue l'expression initiale |
| Expression auto-duale | Fonction égale à sa duale fonctionnelle |
| Dualité ensembliste | ∩ ↔ ∪ et ∅ ↔ U |
| Dualité des circuits | Portes ET et OU échangées |
| NAND et NOR | Opérations duales |
| Formes normales | Disjonctive et conjonctive duales |
Formules essentielles
| Dual(ET) = OU |
| Dual(OU) = ET |
| Dual(0) = 1 |
| Dual(1) = 0 |
|
Dual(NON A) = NON Dual(A) |
|
Dual(Dual(A)) = A |
Pour une fonction booléenne :
|
fd(x1,...,xn) = NON f( NON x1, ..., NON xn ) |
Exemple général en pseudocode
|
MODULE DémontrerParDualité(Identité) Vérifier que l'identité initiale est valide Copier les deux membres Remplacer ET par OU Remplacer OU par ET Remplacer 0 par 1 Remplacer 1 par 0 Conserver les variables Conserver les négations RETOURNER l'identité duale valide |
Exemple final
Identité initiale :
| A OU (A ET B) = A |
Étape 1 - échange des opérateurs :
| A ET (A OU B) = A |
Étape 2 - échange des constantes :
| Aucune constante à remplacer |
Identité duale finale :
| A ET (A OU B) = A |
Les deux identités sont les deux formes de la loi d'absorption.
Remarque
La dualité de l'algèbre de Boole met en évidence une symétrie fondamentale entre les opérations ET et OU, ainsi qu'entre les constantes 0 et 1. Grâce à cette symétrie, les lois booléennes ne sont pas des formules isolées : elles appartiennent généralement à des paires dont chaque membre peut être dérivé de l'autre.
Le principe de dualité permet de réduire le nombre de démonstrations nécessaires, de mieux organiser les règles de simplification et de comprendre les relations entre plusieurs structures logiques. Il explique notamment les correspondances entre l'intersection et l'union, entre l'ensemble vide et l'ensemble universel, entre les portes NAND et NOR, ainsi qu'entre les formes normales disjonctives et conjonctives.
En programmation, la dualité doit principalement être utilisée comme outil mathématique et symbolique. Une expression et son dual ne décrivent pas nécessairement la même règle fonctionnelle. La transformation doit donc être appliquée avec rigueur, en distinguant clairement la dualité, la négation, la complémentation et l'équivalence logique.