Fonction logique OU exclusif

Diagramme de Venn de $\scriptstyle A\oplus B$ sans donne

Diagramme de Venn de $\scriptstyle A\oplus B\oplus C$ $~\oplus ~$ $~\Leftrightarrow ~$

La fonction logique OU exclusif (en anglais, XOR, pour eXclusive OR) est un opérateur logique, à deux opérandes booléens, de l'algèbre de Boole. Elle est utilisée couramment en électronique, en informatique et en cryptographie.

Cette fonction donne en retour la disjonction exclusive (le OU exclusif) des états logiques des deux entrés. Cette fonction peut être aussi nommée "est différent".

Description

La fonction logique OU exclusif est aussi appelée disjonction exclusive, dans l'algèbre de Boole. Elle peut être représentée par le sigle : « ⊻ » ou par le signe d'addition dans un cercle : « ⊕ ».

C'est un opérateur booléen, à deux opérandes. Cette fonction retourne la valeur VRAI si, et seulement si, un seul des deux opérandes a la valeur VRAI. Il associe un résultat qui a lui-même la valeur VRAI seulement si les deux opérandes ont des valeurs distinctes. Sinon, elle retourne la valeur FAUX. Les valeurs VRAI et FAUX peuvent être représenté par les valeurs binaires 1 et 0 (en anglais BIT pour Binary digit).

Table de vérité de la fonction OU exclusif

Opérande 1	Opérande 2	Résultat		Opérande 1	Opérande 2	Résultat
a	b	a ⊻ b		a	b	a ⊕ b
FAUX	FAUX	FAUX		0	0	0
FAUX	VRAI	VRAI		0	1	1
VRAI	FAUX	VRAI		1	0	1
VRAI	VRAI	FAUX		1	1	0

En cryptographie, il est aussi appelé somme binaire, et est noté « + ». À noter que dans cette représentation 1 + 1 = 0 (il n'y a pas de retenue).^{[réf. souhaitée]}

Il se différencie de l'opérateur OU inclusif, car il donne un résultat FAUX lorsque A et B ont simultanément la valeur VRAI.

En informatique, cet opérateur peut s'utiliser pour combiner deux bits, valant chacun 0 ou 1, en appliquant les règles définies par la table précédente, le résultat étant lui-même la valeur d'un bit.

Équivalence, introduction et élimination

La disjonction exclusive $p\oplus q$, ou Jpq, peut être exprimée en termes de conjonction (« et logique », $\wedge$), disjonction (« ou logique », $\lor$), et de la négation logique ($\lnot$) comme suit :

${\begin{matrix}p\oplus q&=&(p\lor q)\land \lnot (p\land q)\end{matrix}}$

La disjonction exclusive $p\oplus q$ peut aussi être formulée de la façon suivante :

${\begin{matrix}p\oplus q&=&(p\land \lnot q)\lor (\lnot p\land q)\end{matrix}}$

Cette représentation de XOR peut être utile lors de la construction d'un circuit ou d'un réseau, car il n'a qu'une seule opération $\lnot$ et un nombre réduit d'opérations $\wedge$ et $\lor$. Une preuve de cette identité est donnée ci-dessous:

${\begin{matrix}p\oplus q&=&(p\land \lnot q)&\lor &(\lnot p\land q)\\[3pt]&=&((p\land \lnot q)\lor \lnot p)&\land &((p\land \lnot q)\lor q)\\[3pt]&=&((p\lor \lnot p)\land (\lnot q\lor \lnot p))&\land &((p\lor q)\land (\lnot q\lor q))\\[3pt]&=&(\lnot p\lor \lnot q)&\land &(p\lor q)\\[3pt]&=&\lnot (p\land q)&\land &(p\lor q)\end{matrix}}$Il est parfois utile de noter $p\oplus q$ de la manière suivante:

${\begin{matrix}p\oplus q&=&\lnot ((p\land q)\lor (\lnot p\land \lnot q))\end{matrix}}$

ou:

${\begin{matrix}p\oplus q&=&(p\lor q)\land (\lnot p\lor \lnot q)\end{matrix}}$

Cette équivalence peut être établie en appliquant les lois de De Morgan deux fois à la quatrième ligne de la démonstration ci-dessus.

Le ou exclusif est également équivalent à la négation d'une équivalence logique, par les règles de l'implication matérielle.

En résumé, nous avons :

${\begin{matrix}p\oplus q&=&(p\land \lnot q)&\lor &(\lnot p\land q)&=&p{\overline {q}}+{\overline {p}}q\\[3pt]&=&(p\lor q)&\land &(\lnot p\lor \lnot q)&=&(p+q)({\overline {p}}+{\overline {q}})\\[3pt]&=&(p\lor q)&\land &\lnot (p\land q)&=&(p+q)({\overline {pq}})\end{matrix}}$

Quelques propriétés mathématiques

• $A\oplus A=0$ (on le vérifie facilement sur la table pour les 2 valeurs possibles de A)
• $A\oplus 0=A$
• $A\oplus 1={\bar {A}}$
• $A\oplus {\bar {A}}=1$
• Commutativité $A\oplus B=B\oplus A$
• Associativité $A\oplus (B\oplus C)=(A\oplus B)\oplus C=A\oplus B\oplus C$
• $A\oplus B={\overline {A\odot B}}$ et $A\oplus B\oplus C=A\odot B\odot C$ où $\odot$ est la fonction coïncidence.
• $A\oplus B=(A+B)\oplus A\cdot B$
• $A\oplus B=0$ si et seulement si $A=B$ (dans un sens, c'est immédiat, dans l'autre, utilisation de la propriété d'associativité et de la propriété : $A\oplus 0=A$)
• $A\oplus B={\bar {A}}\cdot B+A\cdot {\bar {B}}$ On déduit de cette propriété : ${\overline {A\oplus B}}=A\cdot B+{\bar {A}}\cdot {\bar {B}}$ ou même encore : ${\overline {A\oplus B}}={\overline {A}}\oplus B=A\oplus {\overline {B}}$ et même encore : $A\oplus B={\overline {A}}\oplus {\overline {B}}$
• $A\oplus B=C$ alors $C\oplus B=A$ et $A\oplus C=B$
• $(A\oplus B)\oplus B=A$ (Conséquence des deux premières propriétés et de l'associativité — utile en cryptographie (voir ci-dessous))
• L'ensemble {0;1} muni des deux lois de composition interne OU exclusif et ET est un corps fini.

Illustration

L'illustration suivante explique la fonction logique OU exclusif.

Les deux opérandes booléens, « a » et « b » et la fonction OU exclusif, sont simulés par des doubles interrupteurs de type NO (normalement ouvert)/NF (normalement fermé). Le résultat de la fonction est simulé par une lampe.

Une lampe s'allume (résultat VRAI) si l'on appuie (ferme le circuit) sur « a » (valeur VRAI) OU sur « b » (valeurVRAI), mais pas quand on appuit sur les deux en même temps.

Simulation de la fonction logique OU exclusif (montage électrique d'interrupteurs va-et-vient)

Chronogramme de la fonction logique OU exclusif

Symbole

Symbole européen

Symbole ANSI

Exemple d'utilisation

La fonction XOR est un exemple de fonction parité.^{[réf. souhaitée]}

Application en électronique

Exemple d'utilisation : le circuit intégré 7486 TTL ou le circuit intégré CMOS 4070 intègre quatre portes logiques du type OU exclusif.

Applications en informatique

Outre les utilisations liées à la cryptographie, la fonction logique OU exclusif permet de remettre rapidement la valeur d'une variable (souvent un registre) à zéro.

Le code en assembleur qui utilise le OU exclusif pour remettre la valeur du registre eax à zéro :

xor eax, eax

Sur les processeurs de type x86, cette instruction est plus courte (en nombre d'octets) que le code intuitif suivant :

mov eax, 0

Elle permet aussi la mise à zéro d'une variable lorsque les conditions ne permettent pas l'octet 0x00 dans le binaire (shellcode)^{[réf. souhaitée]}.

On peut également utiliser le OU exclusif pour échanger deux variables sans utiliser de variable temporaire.

Application en électricité domestique

Une application utilisée de l'opérateur logique OU exclusif en électricité domestique est dans les salles où une ampoule peut être allumée ou éteinte par deux interrupteurs placés près de deux entrées. Chacun des deux interrupteurs peut soit allumer ou éteindre l'ampoule quelle que soit la position de l'autre interrupteur. Pour obtenir une telle fonctionnalité, on doit brancher les deux interrupteurs afin de former un opérateur XOR. C'est le montage dit « va-et-vient ».

Voir aussi

Articles connexes

• Fonction logique
• Fonction logique OUI
• Fonction logique NON
• Fonction logique ET
• Fonction logique OU
• Fonction logique NON-ET
• Fonction logique NON-OU
• Fonction Coïncidence

Liens externes

• Notices dans des dictionnaires ou encyclopédies généralistes :

  • Britannica
  • Enciclopedia De Agostini