Fonction logique OU exclusif

Équivalence, introduction et élimination

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

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

La disjonction exclusive ${\displaystyle p\oplus q}$ peut aussi être formulée de la façon suivante^[3] :

${\displaystyle {\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 ${\displaystyle \lnot }$ et un nombre réduit d'opérations ${\displaystyle \wedge }$ et ${\displaystyle \lor }$. Une preuve de cette identité est donnée ci-dessous:

${\displaystyle {\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 ${\displaystyle p\oplus q}$ de la manière suivante:

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

ou:

${\displaystyle {\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 :

${\displaystyle {\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

• ${\displaystyle A\oplus A=0}$^[1] (on le vérifie facilement sur la table pour les 2 valeurs possibles de A)
• ${\displaystyle A\oplus 0=A}$^[1]
• ${\displaystyle A\oplus 1={\bar {A}}}$^[1]
• ${\displaystyle A\oplus {\bar {A}}=1}$^[1]
• Commutativité ${\displaystyle A\oplus B=B\oplus A}$
• Associativité ${\displaystyle A\oplus (B\oplus C)=(A\oplus B)\oplus C=A\oplus B\oplus C}$
• ${\displaystyle A\oplus B={\overline {A\odot B}}}$ et ${\displaystyle A\oplus B\oplus C=A\odot B\odot C}$ où ${\displaystyle \odot }$ est la fonction coïncidence.
• ${\displaystyle A\oplus B=(A+B)\oplus A\cdot B}$
• ${\displaystyle A\oplus B=0}$ si et seulement si ${\displaystyle A=B}$ (dans un sens, c'est immédiat, dans l'autre, utilisation de la propriété d'associativité et de la propriété : ${\displaystyle A\oplus 0=A}$)
• ${\displaystyle A\oplus B={\bar {A}}\cdot B+A\cdot {\bar {B}}}$ On déduit de cette propriété : ${\displaystyle {\overline {A\oplus B}}=A\cdot B+{\bar {A}}\cdot {\bar {B}}}$ ou même encore : ${\displaystyle {\overline {A\oplus B}}={\overline {A}}\oplus B=A\oplus {\overline {B}}}$ et même encore : ${\displaystyle A\oplus B={\overline {A}}\oplus {\overline {B}}}$
• ${\displaystyle A\oplus B=C}$ alors ${\displaystyle C\oplus B=A}$ et ${\displaystyle A\oplus C=B}$
• ${\displaystyle (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.

Symbole européen

^[1]

Symbole ANSI

^[1]

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^[4].

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^[5].

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 »^[1].

Exemple d'utilisation en cryptographie