Langage de programmation - Mathématiques appliquées

Principe de complémentarité

Le principe de complémentarité est une notion fondamentale de l'algèbre de Boole. Il exprime la relation existant entre une variable booléenne et sa négation, appelée son complément. Puisqu'une variable booléenne ne peut prendre que les valeurs vrai ou faux, son complément possède toujours la valeur opposée.

Si une variable :

vaut vrai, son complément :

NON A

vaut faux. Inversement, si `A` vaut faux, `NON A` vaut vrai. Une variable et son complément ne peuvent donc jamais être vrais simultanément dans la logique booléenne classique. Ils ne peuvent pas non plus être faux simultanément.

Cette opposition conduit aux deux lois essentielles de complémentarité :

A ET NON A = FAUX

et :

A OU NON A = VRAI

La première formule représente une contradiction, car une proposition ne peut pas être vraie et fausse en même temps. La seconde représente une tautologie, car une proposition est nécessairement vraie ou fausse.

Le principe de complémentarité intervient dans la simplification des expressions, les démonstrations logiques, les conditions de programmation, les circuits numériques, les opérations sur les bits, la théorie des ensembles, les bases de données et la vérification formelle des logiciels.

Définition du complément

Le complément d'une valeur booléenne est la valeur opposée obtenue en appliquant l'opérateur de négation.

Pour une variable :

son complément peut être noté :

NON A

¬A

Ā

ou, dans plusieurs langages de programmation :

La notation employée dépend du contexte mathématique ou du langage utilisé.

Table de vérité du complément

A	NON A
0	1
1	0

Cette table montre que le complément inverse toujours la valeur de son opérande.

Ainsi :

NON 0 = 1

et :

NON 1 = 0

Valeur vraie et valeur fausse

Dans l'algèbre de Boole classique :

0 = FAUX

et :

1 = VRAI

La complémentation échange donc ces deux constantes :

NON FAUX = VRAI

NON VRAI = FAUX

Les deux valeurs sont complémentaires l'une de l'autre.

Complément d'une variable

Si :

A = 1

alors :

NON A = 0

Si :

A = 0

alors :

NON A = 1

Une variable et son complément possèdent toujours des valeurs différentes.

On peut écrire :

A ≠ NON A

dans la logique booléenne classique à deux valeurs.

Première loi de complémentarité

La première loi est :

A ET NON A = 0

ou :

A ET NON A = FAUX

Elle affirme qu'une variable et son complément ne peuvent jamais être vrais simultanément.

Cette expression représente une contradiction.

Vérification par table de vérité

A	NON A	A ET NON A
0	1	0
1	0	0

Quelle que soit la valeur de `A`, la colonne finale vaut toujours :

L'expression est donc toujours fausse.

Interprétation logique

Considérons la proposition :

Le fichier existe.

Son complément est :

Le fichier n'existe pas.

Les deux propositions ne peuvent pas être vraies simultanément dans un même contexte parfaitement déterminé.

L'expression :

FichierExiste
ET
NON FichierExiste

est donc nécessairement fausse.

Principe de non-contradiction

La formule :

A ET NON A = FAUX

correspond au principe de non-contradiction.

Ce principe affirme qu'une proposition ne peut pas être simultanément vraie et fausse dans le même contexte et au même moment.

Il joue un rôle fondamental dans :

la logique classique ;
les démonstrations mathématiques ;
la vérification des programmes ;
la validation des modèles de données ;
la conception des systèmes de règles.

Deuxième loi de complémentarité

La seconde loi est :

A OU NON A = 1

ou :

A OU NON A = VRAI

Elle affirme qu'une variable ou son complément est nécessairement vrai.

Cette expression représente une tautologie.

Vérification par table de vérité

A	NON A	A OU NON A
0	1	1
1	0	1

Quelle que soit la valeur de `A`, la colonne finale vaut toujours :

L'expression est donc toujours vraie.

Principe du tiers exclu

La formule :

A OU NON A = VRAI

correspond au principe du tiers exclu.

Ce principe affirme qu'une proposition est vraie ou que sa négation est vraie. Dans la logique booléenne classique, aucune troisième possibilité n'existe entre vrai et faux.

Ainsi, une variable booléenne satisfait nécessairement l'une des deux conditions :

ou :

NON A

Tableau des lois fondamentales

Loi	Formule	Résultat
Non-contradiction	A ET NON A	FAUX
Tiers exclu	A OU NON A	VRAI
Complément de faux	NON FAUX	VRAI
Complément de vrai	NON VRAI	FAUX
Double complément	NON NON A	A

Ces identités constituent les principales formes du principe de complémentarité.

Double complément

Appliquer deux fois la négation restitue la valeur initiale.

NON NON A = A

Cette identité est également appelée :

loi de double négation ;
loi d'involution ;
involutivité du complément.

Vérification de la double négation

A	NON A	NON NON A
0	1	0
1	0	1

La dernière colonne est identique à la première.

Ainsi :

NON(NON A) = A

Exemple de double négation

Considérons :

NON NON CompteActif

Cette expression signifie :

Il n'est pas vrai que le compte n'est pas actif.

Elle se simplifie en :

CompteActif

La forme simplifiée est généralement beaucoup plus lisible.

Complément d'une constante

Les constantes booléennes sont complémentaires :

NON 0 = 1

NON 1 = 0

On peut également écrire :

0̅ = 1

et :

1̅ = 0

Cette relation joue un rôle important dans les transformations duales et les circuits logiques.

Unicité du complément

Dans une algèbre de Boole, chaque élément possède un complément unique.

Si B est le complément de A, il doit satisfaire :

A ET B = 0

et :

A OU B = 1

Ces deux conditions permettent de caractériser le complément.

Démonstration conceptuelle de l'unicité

Supposons que `B` et `C` soient deux compléments de `A`.

Ils satisfont :

A OU B = 1

A ET B = 0

et :

A OU C = 1

A ET C = 0

On peut alors montrer, à l'aide des lois distributives et des identités booléennes, que :

B = C

Le complément de `A` est donc unique.

Démonstration algébrique de l'unicité

Partons de :

B = B ET 1

Comme :

A OU C = 1

on obtient :

B = B ET (A OU C)

Par distributivité :

B = (B ET A) OU (B ET C)

Puisque :

B ET A = 0

il reste :

B = B ET C

De manière symétrique :

C = B ET C

Donc :

B = C

Complément d'une expression

La complémentation ne s'applique pas uniquement à une variable.

Elle peut s'appliquer à une expression complète :

NON(A ET B)

NON(A OU B)

NON(
CompteActif
ET PossèdePermission
)

Le complément représente alors la négation du résultat de toute l'expression.

Parenthèses et complément

Les parenthèses déterminent la portée de la négation.

NON A ET B

signifie généralement :

(NON A) ET B

En revanche :

NON(A ET B)

nie le résultat de la conjonction complète.

Ces deux expressions ne sont pas équivalentes.

Exemple de différence

Considérons :

A = 1
B = 0

Alors :

(NON A) ET B
=
0 ET 0
=
0

Tandis que :

NON(A ET B)
=
NON(1 ET 0)
=
NON 0
=
1

La portée du complément modifie donc le résultat.

Lois de De Morgan

Le complément d'une conjonction ou d'une disjonction peut être distribué à l'aide des lois de De Morgan.

NON(A ET B)
=
NON A OU NON B

et :

NON(A OU B)
=
NON A ET NON B

Lorsque la négation traverse les parenthèses, l'opérateur ET devient OU et l'opérateur OU devient ET.

Complément d'une conjonction

L'expression :

NON(A ET B)

est vraie lorsque la conjonction `A ET B` est fausse.

Cela se produit lorsque :

A est faux ;
ou B est faux ;
ou les deux sont faux.

On obtient donc :

NON A OU NON B

Table de vérité de De Morgan

A	B	NON(A ET B)	NON A OU NON B
0	0	1	1
0	1	1	1
1	0	1	1
1	1	0	0

Les deux dernières colonnes sont identiques.

Complément d'une disjonction

L'expression :

NON(A OU B)

est vraie uniquement lorsque :

A = FAUX

et :

B = FAUX

Elle est donc équivalente à :

NON A ET NON B

Table de vérité correspondante

A	B	NON(A OU B)	NON A ET NON B
0	0	1	1
0	1	0	0
1	0	0	0
1	1	0	0

Les résultats sont identiques pour toutes les affectations.

Complément et dualité

Le principe de complémentarité est lié à la dualité, mais les deux notions sont différentes.

La dualité échange :

ET ↔ OU

et :

0 ↔ 1

La complémentation inverse la valeur d'une expression :

A ↔ NON A

Les deux lois fondamentales de complémentarité sont toutefois duales :

A ET NON A = 0

et :

A OU NON A = 1

Expression et expression complémentaire

Pour une expression :

son complément est :

NON F

Les deux expressions vérifient :

F ET NON F = 0

et :

F OU NON F = 1

Ces propriétés sont vraies même lorsque `F` est une expression complexe.

Exemple avec une expression complexe

Soit :

F =
CompteActif
ET
PossèdePermission

Son complément est :

NON F

c'est-à-dire :

NON(
   CompteActif
   ET
   PossèdePermission
)

Par De Morgan :

NON CompteActif
OU
NON PossèdePermission

Vérification de complémentarité

Les expressions :

et :

NON F

satisfont :

F ET NON F = FAUX

et :

F OU NON F = VRAI

Cela reste vrai indépendamment de la structure interne de `F`.

Contradiction

Une contradiction est une expression toujours fausse.

La forme classique est :

A ET NON A

Toute expression contenant une conjonction obligatoire entre une condition et son complément peut souvent être simplifiée en :

FAUX

Exemple de contradiction dans un programme

SI
   CompteActif
   ET NON CompteActif
ALORS

   AutoriserAccès

FIN SI

Le bloc ne pourra jamais être exécuté dans une logique booléenne classique.

La condition est contradictoire.

Code inaccessible

Lorsqu'une condition se simplifie en faux :

SI FAUX ALORS
Instruction
FIN SI

le bloc correspondant est inaccessible.

Un compilateur ou un outil d'analyse statique peut signaler ou supprimer ce code.

Tautologie

Une tautologie est une expression toujours vraie.

La forme classique est :

A OU NON A

Toute expression contenant une disjonction complète entre une condition et son complément peut souvent être simplifiée en :

VRAI

Exemple de tautologie dans un programme

SI
   CompteActif
   OU NON CompteActif
ALORS

   ExécuterInstruction

FIN SI

Le bloc est toujours exécuté.

La condition est donc inutile dans la logique classique.

Simplification d'une expression

Le principe de complémentarité permet de réduire des expressions complexes.

Considérons :

(A ET NON A)
OU B

Comme :

A ET NON A = 0

l'expression devient :

0 OU B

Puis :

Autre exemple de simplification

Considérons :

(A OU NON A)
ET B

Comme :

A OU NON A = 1

l'expression devient :

1 ET B

Puis :

Exemple avec plusieurs variables

(
A ET NON A
)
OU
(
B ET C
)

La première partie est toujours fausse :

A ET NON A = 0

On obtient :

0 OU (B ET C)

Puis :

B ET C

Exemple avec une tautologie

(
A OU NON A
)
ET
(
B OU C
)

La première partie est toujours vraie :

A OU NON A = 1

On obtient :

1 ET (B OU C)

Puis :

B OU C

Complément et absorption

Le principe de complémentarité intervient souvent avec la distributivité et l'absorption.

Considérons :

A OU
(
NON A ET B
)

Par distributivité :

(
A OU NON A
)
ET
(
A OU B
)

Puis :

1 ET (A OU B)

On obtient :

A OU B

Identité utile

On peut donc établir :

A OU (NON A ET B)
=
A OU B

Sa forme duale est :

A ET (NON A OU B)
=
A ET B

Ces identités utilisent directement le principe de complémentarité.

Démonstration de la première identité

Partons de :

A OU (NON A ET B)

Par distributivité :

(A OU NON A)
ET
(A OU B)

Par complémentarité :

1 ET (A OU B)

Par identité du ET :

A OU B

Démonstration de la forme duale

Partons de :

A ET (NON A OU B)

Par distributivité :

(A ET NON A)
OU
(A ET B)

Par complémentarité :

0 OU (A ET B)

Par identité du OU :

A ET B

Complément et implication

L'implication :

A → B

peut être exprimée par :

NON A OU B

Sa négation est :

NON(NON A OU B)

Par De Morgan :

A ET NON B

Ainsi, une implication est fausse uniquement lorsque `A` est vrai et `B` est faux.

Complément d'une implication

NON(A → B)
=
A ET NON B

Cette identité est utile pour :

démontrer qu'une implication est fausse ;
chercher un contre-exemple ;
construire des conditions d'erreur ;
transformer des règles logiques.

Complément de l'équivalence

L'équivalence logique :

A ↔ B

est vraie lorsque `A` et `B` possèdent la même valeur.

Son complément est le OU exclusif :

NON(A ↔ B)
=
A XOR B

Inversement :

NON(A XOR B)
=
A ↔ B

Le XOR et le XNOR sont donc complémentaires.

Complément du XOR

Le XOR peut être écrit :

A XOR B
=
(A ET NON B)
OU
(NON A ET B)

Son complément est vrai lorsque les deux variables sont égales :

(A ET B)
OU
(NON A ET NON B)

Cette opération correspond à l'équivalence ou au XNOR.

Complément et opérateurs NAND et NOR

Le NAND est le complément du ET :

A NAND B
=
NON(A ET B)

Le NOR est le complément du OU :

A NOR B
=
NON(A OU B)

Ces opérations sont directement construites par complémentation.

Table du NAND

A	B	A ET B	A NAND B
0	0	0	1
0	1	0	1
1	0	0	1
1	1	1	0

La colonne NAND est le complément exact de la colonne ET.

Table du NOR

A	B	A OU B	A NOR B
0	0	0	1
0	1	1	0
1	0	1	0
1	1	1	0

La colonne NOR est le complément exact de la colonne OU.

Complément dans les circuits logiques

Dans un circuit numérique, le complément est produit par une porte NON, aussi appelée :

inverseur ;
porte NOT ;
porte de négation.

Cette porte possède une seule entrée et une seule sortie.

La sortie prend toujours l'état logique opposé à l'entrée.

Exemple d'inverseur

Entrée A ──[NON]── Sortie S

La relation est :

S = NON A

Si l'entrée vaut 1, la sortie vaut 0.

Si l'entrée vaut `0`, la sortie vaut `1`.

Bulle d'inversion

Dans les schémas logiques, une petite bulle placée sur une entrée ou une sortie indique généralement une inversion.

Une porte ET suivie d'une bulle de sortie représente une porte NAND.

Une porte OU suivie d'une bulle de sortie représente une porte NOR.

Signaux actifs à l'état bas

Dans certains circuits, un signal est considéré comme actif lorsqu'il vaut :

On parle alors de signal actif à l'état bas.

Son nom peut être représenté par :

RESET_N

/RESET

ou par une barre au-dessus du nom.

La complémentarité aide à comprendre la relation entre signal actif haut et actif bas.

Exemple de signal actif bas

Si :

RESET_N = 0

la remise à zéro est active.

La condition positive :

ResetActif

peut être calculée par :

ResetActif = NON RESET_N

Ainsi :

RESET_N = 0

produit :

ResetActif = 1

Complément dans les opérations sur les bits

Dans les opérations bit à bit, le complément inverse chaque bit d'une valeur.

Par exemple :

A = 10110010

Son complément bit à bit est :

NON A = 01001101

Chaque `0` devient `1` et chaque `1` devient `0`.

Largeur de représentation

Le résultat du complément bit à bit dépend du nombre de bits utilisés.

Par exemple, sur 8 bits :

00000101

devient :

11111010

Sur 16 bits, la même valeur numérique serait représentée par :

0000000000000101

et son complément serait :

1111111111111010

Complément logique et complément bit à bit

Le complément logique traite une valeur comme une condition globale :

NON VRAI = FAUX

Le complément bit à bit inverse chaque bit individuellement.

Ces deux opérations doivent être distinguées.

Type	Exemple
Complément logique	NON true = false
Complément bit à bit	NON 1010 = 0101

Complément à un

L'inversion de tous les bits d'un nombre est parfois appelée complément à un.

Pour une valeur binaire :

00101100

le complément à un est :

11010011

Cette opération ne doit pas être confondue avec le complément à deux utilisé pour représenter les entiers négatifs.

Complément à deux

Le complément à deux est obtenu en :

Inversant tous les bits
Ajoutant 1

Par exemple, sur 8 bits :

5 = 00000101

Complément à un :

11111010

Ajout de 1 :

11111011

Cette dernière valeur représente `-5` en complément à deux.

Différence avec la complémentarité booléenne

La complémentarité booléenne porte sur les valeurs logiques et les expressions.

Le complément à un et le complément à deux portent sur la représentation binaire des nombres.

Ces notions utilisent l'inversion des bits, mais poursuivent des objectifs différents.

Complément en théorie des ensembles

Le complément d'un ensemble `A`, relativement à un ensemble universel `U`, contient tous les éléments de `U` qui n'appartiennent pas à `A`.

Il peut être noté :

A^c

La correspondance avec l'algèbre de Boole est :

NON A ↔ A^c

Lois ensemblistes de complémentarité

Les lois booléennes deviennent :

A ∩ A^c = ∅

et :

A ∪ A^c = U

Elles correspondent respectivement à :

A ET NON A = 0

et :

A OU NON A = 1

Interprétation ensembliste

L'ensemble `A` et son complément ne possèdent aucun élément commun :

A ∩ A^c = ∅

En revanche, leur union reconstitue tout l'ensemble universel :

A ∪ A^c = U

Cette représentation illustre concrètement le principe de complémentarité.

Complément du complément d'un ensemble

(A^c)^c = A

Cette identité correspond à la double négation :

NON NON A = A

Prendre deux fois le complément restitue l'ensemble initial.

Complément de l'ensemble vide

∅^c = U

Cette identité correspond à :

NON 0 = 1

Le complément de l'ensemble vide est l'ensemble universel.

Complément de l'ensemble universel

U^c = ∅

Cette identité correspond à :

NON 1 = 0

Aucun élément extérieur à l'ensemble universel n'est considéré dans le domaine défini.

De Morgan dans les ensembles

Les lois de De Morgan en théorie des ensembles sont :

(A ∩ B)^c = A^c ∪ B^c

et :

(A ∪ B)^c = A^c ∩ B^c

Elles reproduisent exactement les lois booléennes de complémentation.

Complément dans les conditions de programmation

En programmation, le complément d'une condition est souvent exprimé à l'aide de :

NOT

not

ou :

NON

Par exemple :

SI NON FichierExiste ALORS
CréerFichier
FIN SI

La condition est satisfaite lorsque `FichierExiste` vaut faux.

Exemple de validation

SI NON DonnéeValide ALORS
AfficherErreur
FIN SI

Cette condition représente le complément du prédicat :

DonnéeValide

Elle pourrait aussi être nommée :

DonnéeInvalide

si ce prédicat est clairement défini.

Formulation positive et complément

Une condition positive est souvent plus facile à lire que sa négation.

Préférer :

SI CompteActif ALORS

à :

SI NON CompteInactif ALORS

Les doubles formulations négatives augmentent le risque d'erreur.

Double négation en programmation

Une expression comme :

NON NON Valeur

peut parfois être utilisée pour convertir une valeur en booléen dans certains langages.

Mathématiquement :

NON NON A = A

Cependant, dans un langage dynamique, la double négation peut transformer une valeur non booléenne en un booléen strict selon les règles de conversion du langage.

Exemple conceptuel de conversion

Dans certains langages :

NON NON Valeur

produit :

VRAI

si la valeur est considérée comme vraie, et :

FAUX

si elle est considérée comme fausse.

Ce comportement dépend du langage et dépasse l'algèbre de Boole stricte.

Complément et court-circuit

Considérons :

NON A ET B

Le complément de `A` est évalué avant le ET en raison de la priorité habituelle de la négation.

Si :

NON A = FAUX

et que le ET utilise le court-circuit, `B` peut ne pas être évalué.

La complémentation peut donc influencer le chemin d'exécution.

Négation d'une condition composée

Considérons :

NON(
UtilisateurAuthentifié
ET CompteActif
)

Par De Morgan :

NON UtilisateurAuthentifié
OU
NON CompteActif

L'échec survient donc lorsqu'au moins une des conditions requises est fausse.

Validation de toutes les conditions

Une validation positive peut être :

ToutesValides ←
   ConditionA
   ET ConditionB
   ET ConditionC

Son complément est :

NON ToutesValides

Par généralisation de De Morgan :

NON ConditionA
OU
NON ConditionB
OU
NON ConditionC

Au moins une condition a échoué.

Validation d'au moins une condition

Une condition positive peut être :

AuMoinsUneValide ←
   ConditionA
   OU ConditionB
   OU ConditionC

Son complément est :

NON ConditionA
ET
NON ConditionB
ET
NON ConditionC

Aucune des conditions n'est alors satisfaite.

Généralisation de De Morgan

Pour plusieurs variables :

NON(
A₁ ET A₂ ET ... ET A_n
)
=
NON A₁
OU NON A₂
OU ...
OU NON A_n

et :

NON(
A₁ OU A₂ OU ... OU A_n
)
=
NON A₁
ET NON A₂
ET ...
ET NON A_n

Ces formules sont très utiles dans les validations et les filtres.

Complément d'un quantificateur universel

L'expression :

Tous les éléments satisfont P.

a pour complément :

Il existe au moins un élément
qui ne satisfait pas P.

Symboliquement :

NON(POUR TOUT x, P(x))
=
IL EXISTE x TEL QUE NON P(x)

Complément d'un quantificateur existentiel

L'expression :

Il existe un élément satisfaisant P.

a pour complément :

Aucun élément ne satisfait P.

Symboliquement :

NON(IL EXISTE x, P(x))
=
POUR TOUT x, NON P(x)

Ces relations sont des extensions des lois de De Morgan.

Exemple avec un tableau

La condition :

TousPositifs

peut être définie par :

POUR TOUT Élément,
Élément > 0

Son complément est :

IL EXISTE un Élément
tel que Élément <= 0

Il suffit donc de trouver un contre-exemple pour invalider la propriété universelle.

Algorithme de recherche d'un complément

MODULE ContientValeurNonPositive(Tableau)

   POUR CHAQUE Valeur DANS Tableau
      SI NON(Valeur > 0) ALORS
         RETOURNER VRAI
      FIN SI
   FIN POUR

   RETOURNER FAUX

La négation de :

Valeur > 0

peut être simplifiée en :

Valeur <= 0

Complément des comparaisons

Les opérateurs de comparaison possèdent des compléments naturels.

Comparaison	Complément
A = B	A ≠ B
A ≠ B	A = B
A < B	A ≥ B
A < B	A > B
A > B	A ≤ B
A ≥ B	A < B

Ces transformations supposent un domaine ordonné classique sans valeur indéterminée particulière.

Exemple de comparaison

NON(Âge >= 18)

est équivalent à :

Âge < 18

De même :

NON(Position < Taille)

est équivalent à :

Position >= Taille

La forme simplifiée est souvent plus lisible.

Cas des nombres spéciaux

Dans certains langages et domaines numériques, la complémentation directe d'une comparaison peut être plus subtile.

Par exemple, une valeur flottante spéciale comme :

NaN

peut rendre certaines comparaisons fausses de manière inhabituelle.

Il ne faut donc pas toujours remplacer mécaniquement :

NON(x < y)

par :

x >= y

sans connaître les règles du type utilisé.

Cas des valeurs nulles

Dans une logique à trois valeurs, une expression peut prendre :

VRAI
FAUX
INCONNU

Le complément de `INCONNU` demeure généralement :

INCONNU

Le principe classique :

A OU NON A = VRAI

peut alors ne plus produire vrai lorsque `A` est inconnu.

Exemple SQL avec NULL

En SQL :

Âge > 18

peut produire :

UNKNOWN

si Âge vaut NULL.

La négation :

NOT(Âge > 18)

produit également généralement :

UNKNOWN

La logique SQL ne correspond donc pas entièrement à l'algèbre booléenne classique à deux valeurs.

Limite du tiers exclu

Dans une logique à trois valeurs :

A OU NON A

peut produire :

INCONNU

lorsque :

A = INCONNU

Le principe du tiers exclu dépend donc du système logique considéré.

Dans l'algèbre de Boole classique, il reste toujours valide.

Complément dans la logique floue

En logique floue, une valeur de vérité peut être comprise entre :

et :

Un complément courant est défini par :

NON x = 1 - x

Par exemple :

NON 0,7 = 0,3

Cependant, cette logique n'est pas l'algèbre de Boole classique.

Complément et états inconnus

Lorsqu'un programme modélise une information pouvant être inconnue, il faut distinguer :

EstActif = FAUX

de :

ÉtatActif = INCONNU

Le complément de « actif » est « inactif », mais une absence d'information ne signifie pas nécessairement que l'objet est inactif.

Modélisation avec une énumération

Au lieu d'un booléen nullable, on peut employer :

ÉtatVérification
   Inconnu
   Valide
   Invalide

Cette représentation évite d'interpréter automatiquement l'absence de valeur comme le complément d'une affirmation.

Complément et sécurité

Dans une règle de sécurité, le complément doit être formulé avec précision.

Considérons :

AccèsAutorisé

Son complément logique est :

NON AccèsAutorisé

Mais cela ne précise pas pourquoi l'accès est refusé.

Plusieurs causes peuvent être possibles :

utilisateur non authentifié ;
compte inactif ;
permission absente ;
dossier verrouillé ;
erreur système.

Refus par défaut

Une approche sécuritaire consiste à initialiser :

AccèsAutorisé ← FAUX

Puis à le rendre vrai uniquement lorsque toutes les conditions requises sont satisfaites.

SI
   UtilisateurAuthentifié
   ET CompteActif
   ET PossèdePermission
ALORS

   AccèsAutorisé ← VRAI

FIN SI

Toute situation non validée conserve le complément de l'autorisation.

Complément d'une autorisation composée

Si :

AccèsAutorisé =
UtilisateurAuthentifié
ET CompteActif
ET PossèdePermission

alors :

NON AccèsAutorisé

équivaut à :

NON UtilisateurAuthentifié
OU
NON CompteActif
OU
NON PossèdePermission

Le refus survient dès qu'au moins une exigence manque.

Tests unitaires de complémentarité

Une fonction booléenne peut être testée en vérifiant les propriétés :

F ET NON F = FAUX

et :

F OU NON F = VRAI

Pour une fonction booléenne stricte, ces identités doivent être vraies pour toutes les entrées.

Exemple de test conceptuel

MODULE TesterComplément(F)

   POUR CHAQUE Entrée possible

   Valeur ← F(Entrée)

      ASSERTION(
         Valeur ET NON Valeur
         =
         FAUX
      )

      ASSERTION(
         Valeur OU NON Valeur
         =
         VRAI
      )

   FIN POUR

Test du double complément

Une autre propriété fondamentale est :

NON NON F = F

Elle peut être utilisée dans les tests fondés sur les propriétés.

ASSERTION(
   NON NON F(Entrée)
   =
   F(Entrée)
)

Complément et analyse statique

Les analyseurs statiques peuvent détecter :

les contradictions ;
les tautologies ;
le code inaccessible ;
les comparaisons redondantes ;
les doubles négations ;
les conditions toujours vraies ;
les conditions toujours fausses.

Ces diagnostics utilisent souvent les lois de complémentarité.

Exemple de condition redondante

SI
   EstActif
   OU NON EstActif
ALORS

   ExécuterTraitement

FIN SI

L'analyseur peut remplacer la condition par :

VRAI

et signaler que le test est inutile.

Exemple de branche impossible

SI
   EstActif
   ET NON EstActif
ALORS

   TraitementImpossible

FIN SI

L'analyseur peut déterminer que la branche ne sera jamais exécutée.

Complément et solveurs SAT

Les solveurs de satisfaisabilité booléenne manipulent continuellement des littéraux positifs et négatifs.

Pour une variable :

les deux littéraux sont :

et :

NON A

Une clause contenant les deux :

A OU NON A

est toujours satisfaite.

Clause tautologique

Une clause comme :

A OU B OU NON A

contient une variable et son complément.

Elle est donc toujours vraie, quelle que soit la valeur de `B`.

Un solveur peut supprimer cette clause sans modifier la satisfaisabilité globale de la formule.

Conjonction contradictoire

Un ensemble de contraintes exigeant simultanément :

et :

NON A

est incohérent.

Sous forme conjonctive :

A ET NON A

la formule est insatisfaisable.

Complément dans les diagrammes de décision

Dans un diagramme de décision binaire, les branches d'un noeud représentent souvent :

Variable = 0

et :

Variable = 1

Ces deux branches sont complémentaires et couvrent toutes les valeurs possibles de la variable.

Complément dans une machine à états

Une variable booléenne peut représenter deux états complémentaires :

PorteOuverte

et :

NON PorteOuverte

Cependant, il est préférable de ne pas mémoriser séparément :

PorteOuverte

et :

PorteFermée

si l'un peut être calculé comme le complément exact de l'autre.

Risque d'incohérence

Si deux variables sont entreposées séparément :

PorteOuverte
PorteFermée

le programme pourrait accidentellement produire :

PorteOuverte = VRAI
PorteFermée = VRAI

ou :

PorteOuverte = FAUX
PorteFermée = FAUX

Ces états violent la complémentarité si la porte ne possède que deux états.

Valeur dérivée

Une meilleure modélisation consiste à stocker une seule valeur :

PorteOuverte

et à calculer :

PorteFermée =
NON PorteOuverte

La cohérence est alors garantie automatiquement.

Limite de la modélisation binaire

Une porte réelle peut toutefois posséder un état intermédiaire :

Ouverte
Fermée
En mouvement
Bloquée
Inconnue

Dans ce cas, `PorteFermée` n'est plus toujours le complément exact de `PorteOuverte`.

Une énumération est alors plus appropriée qu'un booléen.

Complément et invariants

Un invariant peut imposer :

EstOuvert XOR EstFermé

Cela signifie qu'exactement une des deux variables doit être vraie.

Cette condition peut également être exprimée par :

EstFermé = NON EstOuvert

si le système comporte exactement deux états.

Complément dans les bases de données

Une requête peut chercher le complément d'un ensemble de lignes.

Par exemple :



SELECT *

FROM Utilisateurs

WHERE NOT CompteActif;

Cette requête cherche les lignes où la condition `CompteActif` est fausse, sous réserve des règles concernant les valeurs nulles.

Complément d'un filtre

Si un filtre sélectionne :

Âge >= 18
ET CompteActif

son complément logique est :

Âge < 18
OU
NON CompteActif

Cette transformation provient des lois de De Morgan et du complément des comparaisons.

Exemple SQL explicite

Condition positive :



WHERE Age >= 18

  AND CompteActif = 1

Condition complémentaire, sans tenir compte des valeurs NULL :



WHERE Age < 18

   OR CompteActif <> 1

Avec des valeurs nulles, des tests supplémentaires peuvent être nécessaires.

Complément dans les moteurs de recherche

Une recherche booléenne peut exclure un critère à l'aide de NON.

Pascal ET NON Delphi

Cette expression sélectionne les documents appartenant à l'ensemble Pascal, mais pas à l'ensemble Delphi.

Elle correspond à :

Pascal ∩ Delphi^c

Complément relatif

Dans une recherche ou un ensemble, le complément dépend toujours d'un univers de référence.

Le complément de :

Documents contenant Delphi

désigne tous les documents de l'univers de recherche qui ne contiennent pas Delphi.

Il ne désigne pas tous les objets possibles de manière absolue.

Algorithme de négation d'une expression

MODULE Nier(Expression)

   SI Expression est VRAI ALORS
      RETOURNER FAUX
   FIN SI

   SI Expression est FAUX ALORS
      RETOURNER VRAI
   FIN SI

   SI Expression est NON X ALORS
      RETOURNER X
   FIN SI

   SI Expression est X ET Y ALORS
      RETOURNER
         Nier(X)
         OU
         Nier(Y)
   FIN SI

   SI Expression est X OU Y ALORS
      RETOURNER
         Nier(X)
         ET
         Nier(Y)
   FIN SI

   RETOURNER NON Expression

Cet algorithme pousse les négations vers les variables.

Forme normale négative

Une expression est en forme normale négative lorsque les opérateurs NON s'appliquent uniquement aux variables ou aux constantes.

Par exemple :

NON(A ET (B OU C))

peut être transformée en :

NON A
OU
(
   NON B
   ET
   NON C
)

Les lois de De Morgan et la double négation permettent cette transformation.

Étapes de transformation

Partons de :

NON(A ET (B OU C))

Première application de De Morgan :

NON A
OU
NON(B OU C)

Deuxième application :

NON A
OU
(

NON B

ET NON C
)

La négation ne porte désormais que sur les variables.

Utilité de la forme normale négative

Cette forme est utilisée dans :

les solveurs logiques ;
les démonstrateurs automatiques ;
les compilateurs ;
les transformations en formes normales ;
la vérification de modèles ;
les systèmes de règles.

Elle facilite l'analyse structurée des compléments.

Exemple en Pascal



Program Complementarite;

 
var

  CompteActif: Boolean;

  CompteInactif: Boolean;

 
BEGIN

  CompteActif := True;

 
  CompteInactif :=

    not CompteActif;

 
  WriteLn(

    'Compte actif : ',

    CompteActif

  );

 
  WriteLn(

    'Compte inactif : ',

    CompteInactif

  );

 
  WriteLn(

    'Contradiction : ',

    CompteActif and CompteInactif

  );

 
  WriteLn(

    'Tautologie : ',

    CompteActif or CompteInactif

  );

END.

Résultat conceptuel en Pascal

Comme :

CompteActif = VRAI

on obtient :

CompteInactif = FAUX

Puis :

CompteActif ET CompteInactif
=
FAUX

et :

CompteActif OU CompteInactif
=
VRAI

Exemple en Java


public final class Complementarite {
 
    private Complementarite() {
    }
 
    public static void main(String[] args) {
        boolean compteActif = true;
        boolean compteInactif =
            !compteActif;
 
        boolean contradiction =
            compteActif
            && compteInactif;
 
        boolean tautologie =
            compteActif
            || compteInactif;
 
        System.out.println(
            "Compte actif : "
            + compteActif
        );
 
        System.out.println(
            "Compte inactif : "
            + compteInactif
        );
 
        System.out.println(
            "Contradiction : "
            + contradiction
        );
 
        System.out.println(
            "Tautologie : "
            + tautologie
        );
    }
}

Résultat du programme Java

Le programme affiche :

Compte actif : true Compte inactif : false Contradiction : false Tautologie : true

Ces résultats illustrent directement les deux lois de complémentarité.

Exemple en C



#include <stdbool.h>

#include <stdio.h>

 
int main(void)

{

    bool compte_actif = true;

    bool compte_inactif =

        !compte_actif;

 
    bool contradiction =

        compte_actif

        && compte_inactif;

 
    bool tautologie =

        compte_actif

        || compte_inactif;

 
    printf(

        "Contradiction : %d&#92;n",

        contradiction

    );

 
    printf(

        "Tautologie : %d&#92;n",

        tautologie

    );

 
    return 0;

}

Exemple en C#



bool compteActif = true;

bool compteInactif =

    !compteActif;

 
bool contradiction =

    compteActif

    && compteInactif;

 
bool tautologie =

    compteActif

    || compteInactif;

 
Console.WriteLine(

    $"Contradiction : {contradiction}"

);

 
Console.WriteLine(

    $"Tautologie : {tautologie}"

);

Exemple en Visual Basic



Dim CompteActif As Boolean = True

 
Dim CompteInactif As Boolean =

    Not CompteActif

 
Dim Contradiction As Boolean =

    CompteActif AndAlso CompteInactif

 
Dim Tautologie As Boolean =

    CompteActif OrElse CompteInactif

 
Console.WriteLine(

    "Contradiction : " &

    Contradiction

)

 
Console.WriteLine(

    "Tautologie : " &

    Tautologie

)

Exemple en Python



compte_actif = True

compte_inactif = not compte_actif

 
contradiction = (

    compte_actif

    and compte_inactif

)

 
tautologie = (

    compte_actif

    or compte_inactif

)

 
print(

    "Contradiction :",

    contradiction,

)

 
print(

    "Tautologie :",

    tautologie,

)

Exemple en JavaScript



const compteActif = true;

const compteInactif = !compteActif;

 
const contradiction =

    compteActif

    && compteInactif;

 
const tautologie =

    compteActif

    || compteInactif;

 
console.log(

    "Contradiction :",

    contradiction

);

 
console.log(

    "Tautologie :",

    tautologie

);

Fonction de complément

MODULE Complément(Valeur)

   SI Valeur = VRAI ALORS
      RETOURNER FAUX
   SINON
      RETOURNER VRAI
   FIN SI

Cette fonction peut être simplifiée en :

MODULE Complément(Valeur)

RETOURNER NON Valeur

Vérification des lois

MODULE VérifierComplémentarité(A)

   Complément ← NON A

   Contradiction ←
      A ET Complément

   Tautologie ←
      A OU Complément

   DoubleComplément ←
      NON Complément

   ASSERTION(
      Contradiction = FAUX
   )

   ASSERTION(
      Tautologie = VRAI
   )

   ASSERTION(
      DoubleComplément = A
   )

Complexité de la complémentation

Le complément d'une valeur booléenne simple demande :

O(1)

temps et :

O(1)

mémoire.

Pour une expression représentée par un arbre contenant `n` noeuds, la propagation complète du complément à l'aide des lois de De Morgan peut demander :

O(n)

temps.

Complément d'une grande expression

Si l'expression est déjà stockée sous forme d'arbre, chaque noeud doit être examiné :

les noeuds ET deviennent OU ;
les noeuds OU deviennent ET ;
les négations sont propagées ;
les constantes sont inversées ;
les variables sont éventuellement marquées comme négatives.

Le coût est proportionnel à la taille de l'expression.

Bonnes pratiques

Pour utiliser correctement le principe de complémentarité, il est recommandé de :

définir clairement l'univers logique utilisé ;
employer la négation sur la bonne sous-expression ;
utiliser des parenthèses explicites ;
simplifier les doubles négations ;
reconnaître les contradictions et les tautologies ;
utiliser les lois de De Morgan pour les expressions composées ;
préférer les formulations positives lorsque cela améliore la lisibilité ;
distinguer le complément logique du complément bit à bit ;
distinguer faux, nul et inconnu ;
éviter de mémoriser séparément deux états parfaitement complémentaires ;
utiliser une énumération lorsque plus de deux états sont possibles ;
tester les règles d'autorisation et leurs compléments.

Erreurs fréquentes

Les erreurs courantes comprennent :

croire que `NON(A ET B)` équivaut à `NON A ET NON B` ;
oublier de remplacer ET par OU selon De Morgan ;
appliquer la négation à une seule variable au lieu de toute l'expression ;
confondre complémentarité et dualité ;
confondre complément logique et complément à deux ;
interpréter une valeur inconnue comme fausse ;
créer deux variables complémentaires pouvant devenir incohérentes ;
utiliser une double négation inutile ;
oublier la priorité élevée de l'opérateur NON ;
supposer que le tiers exclu reste valable dans toutes les logiques ;
comparer incorrectement des valeurs nulles dans SQL ;
considérer qu'une chaîne `"false"` est nécessairement fausse.

Tableau récapitulatif

Notion	Description
Complément	Valeur logique opposée
Négation	Opération produisant le complément
Non-contradiction	A ET NON A = FAUX
Tiers exclu	A OU NON A = VRAI
Double négation	NON NON A = A
Complément de faux	NON FAUX = VRAI
Complément de vrai	NON VRAI = FAUX
Contradiction	Expression toujours fausse
Tautologie	Expression toujours vraie
De Morgan	Transformation du complément d'une expression composée
Complément bit à bit	Inversion individuelle de chaque bit
Complément ensembliste	Éléments extérieurs à un sous-ensemble
Forme normale négative	Négations appliquées uniquement aux littéraux
Unicité du complément	Chaque élément booléen possède un seul complément

Formules essentielles

NON 0 = 1

NON 1 = 0

A ET NON A = 0

A OU NON A = 1

NON NON A = A

NON(A ET B) = NON A OU NON B

NON(A OU B) = NON A ET NON B

F ET NON F = 0

F OU NON F = 1

Applications

Le principe de complémentarité est utilisé dans :

les conditions de programmation ;
les circuits logiques ;
les opérations sur les bits ;
la simplification booléenne ;
les tables de vérité ;
les démonstrations logiques ;
la théorie des ensembles ;
les bases de données ;
les moteurs de recherche ;
les systèmes experts ;
les solveurs SAT ;
les compilateurs ;
l'analyse statique ;
les tests logiciels ;
les contrôles d'accès ;
les automates et machines à états.

Avantages

Le principe de complémentarité présente plusieurs avantages :

il permet d'inverser précisément une condition ;
il permet de reconnaître les contradictions ;
il permet de reconnaître les tautologies ;
il simplifie de nombreuses expressions booléennes ;
il facilite la négation des règles complexes ;
il permet de dériver les lois de De Morgan ;
il aide à détecter le code inaccessible ;
il permet de représenter des signaux actifs à l'état bas ;
il établit un lien entre logique, ensembles et circuits ;
il facilite la construction de NAND et de NOR ;
il permet de vérifier la cohérence d'un modèle binaire ;
il fournit des propriétés utiles pour les tests automatiques.

Limites et précautions

Le principe de complémentarité possède certaines limites :

il suppose généralement une logique classique à deux valeurs ;
il ne s'applique pas de la même manière aux valeurs inconnues ;
le tiers exclu peut échouer dans certaines logiques non classiques ;
le complément d'une condition métier ne fournit pas nécessairement la cause précise de son échec ;
la négation d'une expression complexe peut être difficile à lire ;
les conversions implicites peuvent modifier le comportement attendu ;
les opérations flottantes particulières peuvent compliquer le complément des comparaisons ;
le complément logique ne doit pas être confondu avec le complément bit à bit ;
deux états opposés ne sont réellement complémentaires que si aucun troisième état n'existe ;
l'univers de référence doit être défini pour les compléments ensemblistes.

Remarque

Le principe de complémentarité exprime l'opposition fondamentale entre une proposition et sa négation. Dans l'algèbre de Boole classique, une variable et son complément couvrent ensemble toutes les possibilités, mais ne peuvent jamais être vrais simultanément. Cette relation produit les deux identités centrales :

A ET NON A = FAUX

et :

A OU NON A = VRAI

Ces lois correspondent respectivement au principe de non-contradiction et au principe du tiers exclu. Elles permettent de simplifier les expressions, de détecter les branches impossibles, de reconnaître les conditions toujours vraies et de transformer correctement les négations complexes.

En programmation, la complémentarité intervient chaque fois qu'une condition est inversée, qu'une règle d'échec est déduite d'une règle de réussite ou qu'un signal actif est converti en son état opposé. Son utilisation doit toutefois tenir compte des valeurs nulles, des états inconnus et des systèmes comportant plus de deux états.

La maîtrise du principe de complémentarité prépare directement à l'étude des lois de De Morgan, de l'équivalence logique, des tautologies, des contradictions, des formes normales et des méthodes avancées de simplification des fonctions booléennes.

Dernière mise à jour : Jeudi, le 16 juillet 2026