Les seize opérateurs binaires

Au lieu de partir de l’usage et de s’interroger sur la façon de représenter au mieux un opérateur comme et, ou, etc, il est possible de procéder de façon formelle. Un opérateur binaire quelconque, disons $\circ$ est tel que, appliqué à deux propositions $p$ et $q$ , il engendre une proposition $p\circ q$ . Si l’on adopte l’ordre canonique pour les valeurs de $p$ et de $q$ , l’évaluation de $p\circ q$ est fournie par un quadruple (a b c d) où a, b, c et $d$ ont soit la valeur 1 soit la valeur 0 et ce quadruple détermine entièrement l’opérateur $\circ$ .

Laissons pour l’instant la question de l’interprétation possible des opérateurs et cherchons simplement à les dénombrer exhaustivement.
On aura cinq cas à étudier.

I. (a b c d) ne contient que des 0 ;
1 façon : (0000)

II. (a b c d) contient un 1 et trois 0 ;
4 façons : (1 0 0 0) (0 1 0 0) (0 0 1 0) (0 0 0 1)

III. (a b c d) contient deux 1 et deux 0 ;
6 façons : (1 1 0 0) (1 0 1 0) (0 1 1 0) (1 0 0 1) (0 1 0 1) (0 0 1 1)

IV. (a b c d) contient trois 1 et un 0 ;
4 façons : (1 1 1 0) (1 1 0 1) (1 0 1 1) (0 1 1 1)

V. (a b c d) ne contient que des 1.
1 façon : (1111).

Il existe donc 16 et seulement 16 opérateurs binaires possibles.

Remarque

On aurait pu trouver ce résultat d’une autre façon encore. Un opérateur binaire peut se concevoir comme une application dont l’ensemble de départ est l’ensemble des couples (ordonnés) :

$\lbrace (1, 1), (1, 0), (0, 1), (0, 0)\rbrace$ et dont l’ensemble d’arrivée est l’ensemble $\lbrace 1, 0\rbrace$ . Si $V = \lbrace 1, 0\rbrace$ , un opérateur binaire est donc une application $f : V\times V\rightarrow V$ où $V\times V$ représente l’ensemble produit $V$ par $V$ . Il suffit de dénombrer les applications $f,$ ce que fait le tableau suivant, pour retrouver (cette fois-ci en colonne) les 16 quadruples.
$\begin{tabular}{|cc|c|cccc|ccc|ccc|cccc|c|} \hline {\small $p$} & {\small $q$} & {\tiny $f_{1}$} & {\tiny $f_{2}$} & {\tiny $f_{3}$} & {\tiny $f_{4}$} & {\tiny $f_{5}$} & {\tiny $f_{6}$} & {\tiny $f_{7}$} & {\tiny $f_{8}$} & {\tiny $f_{9}$} & {\tiny $f_{10}$} & {\tiny ${\normalcolor }f_{11}$} & {\tiny $f_{12}$} & {\tiny $f_{13}$} & {\tiny ${\normalcolor }f_{14}$} & {\tiny $f_{15}$} & {\tiny $f_{16}$}\tabularnewline \hline {\small 0} & {\small 0} & {\small 0} & {\small 0} & {\small 0} & {\small 0} & {\small 1} & {\small 0} & {\small 0} & {\small 0} & {\small 1} & {\small 1} & {\small 1} & {\small 0} & {\small 1} & {\small 1} & {\small 1} & {\small 1}\tabularnewline {\small 0} & {\small 1} & {\small 0} & {\small 0} & {\small 0} & {\small 1} & {\small 0} & {\small 0} & {\small 1} & {\small 1} & {\small 0} & {\small 0} & {\small 1} & {\small 1} & {\small 0} & {\small 1} & {\small 1} & {\small 1}\tabularnewline {\small 1} & {\small 0} & {\small 0} & {\small 0} & {\small 1} & {\small 0} & {\small 0} & {\small 1} & {\small 0} & {\small 1} & {\small 0} & {\small 1} & {\small 0} & {\small 1} & {\small 1} & {\small 0} & {\small 1} & {\small 1}\tabularnewline {\small 1} & {\small 1} & {\small 0} & {\small 1} & {\small 0} & {\small 0} & {\small 0} & {\small 1} & {\small 1} & {\small 0} & {\small 1} & {\small 0} & {\small 0} & {\small 1} & {\small 1} & {\small 1} & {\small 0} & {\small 1}\tabularnewline \hline \end{tabular}$

Il est possible de tirer davantage encore de ce qui précède. Soit $P$ une proposition quelconque qui contient les deux atomes $p$ et $q$ . Ceux-ci peuvent figurer un nombre quelconque de fois dans $P$ et les compositions peuvent se faire à l’aide d’un ou de plusieurs des seize opérateurs.

Exemple

$P$ =df $\sim p\supset\left(p\vee q\right)$

Dans tous les cas, l’évaluation de $P$ conduira à l’un des seize quadruples ci-dessus. Ce sera (1 1 1 0) pour cet exemple (V, p. 8), qui est aussi l’évaluation de $p\vee q$ .

Cela signifie que $\sim p\supset\left(p\vee q\right)$ est équivalente à $p\vee q$ , donc que

$\vdash\sim p\supset\left(p\vee q\right)\equiv p\vee q$ ou encore

$\sim p\supset\left(p\vee q\right)\leftrightarrow p\vee q$

L’ensemble $\Pi_{2}$ de toutes les propositions qui contiennent deux atomes est infini, puisque chaque atome peut être répété un nombre quelconque de fois et la relation d’équivalence $\leftrightarrow$ engendre une partition de $\Pi_{2}$ en 16 classes d’équivalence. Nous noterons $\left[ a b c d \right]$ la classe de toutes les propositions dont l’évaluation est $(a b c d)$ .

Exemples

1) Comme nous venons de le voir $\sim p\supset\left(p\vee q\right)\in\left[1\:1\:1\:0\right]$ , $p\vee q\in\left[1\:1\:1\:0\right]$ ;
2) on s’assurera que $p\supset q\in\left[1\:0\:1\:1\right]$ , $\sim p\vee q\in\left[1\:0\:1\:1\right]$ , et que $\sim\left(p\wedge\sim q\right)\in\left[1\:0\:1\:1\right]$ .

Il est aussi possible de désigner la classe $\left[ a b c d \right]$ en choisissant l’un quelconque de ses éléments et en le plaçant entre crochets. Ainsi, par exemple, $\left[p\vee q \right]$ désignera la classe $\left[1\:1\:1\:0\right]$ , {[} $p\supset q$ {]} désignera $\left[1\:0\:1\:1\right]$ , etc.

Ordonnons maintenant les 16 classes. Nous dirons que la classe $\left[a_{1}\: b_{1}\: c_{1}\: d_{1}\right]$ précède la classe $\left[a_{2}\: b_{2}\: c_{2}\: d_{2}\right]$ , et nous noterons $\left[a_{1}\: b_{1}\: c_{1}\: d_{1}\right]\leq\left[a_{2}\: b_{2}\: c_{2}\: d_{2}\right]$ , si un représentant quelconque de $\left[a_{1}\: b_{1}\: c_{1}\: d_{1}\right]$ implique, au sens de la relation $\rightarrow$ , un représentant quelconque de la classe $\left[a_{2}\: b_{2}\: c_{2}\: d_{2}\right]$ .

Exemple
Soit les trois classes $\left[1\:0\:0\:0\right]$ , $\left[1\:0\:1\:0\right]$ et $\left[1\:1\:1\:0\right]$ . On s’assure sans peine que : $p\wedge q\in\left[1\:0\:0\:0\right]$ , $q\wedge\left(p\vee\sim p\right)\in\left[1\:0\:1\:0\right]$ et $p\vee q\in\left[1\:1\:1\:0\right]$ .
D’autre part, le calcul montre que :
$\vdash\left(p\wedge q\right)\supset\left(q\wedge\left(p\vee\sim p\right)\right)$ ,
$\vdash\left(q\wedge\left(p\vee\right)\right)\supset\left(p\vee q\right)$ ,
$\vdash\left(p\wedge q\right)\supset\left(p\vee q\right)$ .

On aura donc les implications :
$p\wedge q\rightarrow q\wedge\left(p\vee\sim p\right)$ , $q\wedge\left(p\vee\sim p\right)\rightarrow p\vee q$ ,
$p\wedge q\rightarrow p\vee q$ .

Et il s’ensuit que :

$\left[1000\right]\leq\left[1010\right]$ , $\left[1010\right]\leq\left[1110\right]$ et $\left[1000\right]\leq\left[1110\right]$ . La troisième relation découle des deux premières par la transitivité de la relation « précède », qui est une relation d’ordre.

Remarques

1) $q\leftrightarrow q\wedge\left(p\vee\sim p\right)$ . En effet, cela revient à dire que $q\equiv\left(q\wedge\left(p\vee\sim p\right)\right)$ est une tautologie, ce que montre le calcul suivant :
$\begin{tabular}{r|cccc} $p$ & 1 & 1 & 0 & 0\tabularnewline $q$ & 1 & 0 & 1 & 0\tabularnewline \hline $\sim p$ & 0 & 0 & 1 & 1\tabularnewline $p\vee\sim p$ & 1 & 1 & 1 & 1\tabularnewline $q\wedge\left(p\vee\sim p\right)$ & 1 & 0 & 1 & 0\tabularnewline \hline Proposition & 1 & 1 & 1 & 1\tabularnewline \end{tabular}$

Il aurait donc été possible de choisir $q$ comme représentant de la classe $[1010]$ . Cela exige toutefois de se souvenir que $q$ n’est pas ici une proposition isolée, mais bien la seconde de deux atomes. Pour garder la chose en mémoire, nous écrirons $[q(p)]$ pour représenter la classe qui contient, en particulier la proposition $q$ , mais qui contient aussi des propositions où l’atome $p$ figure explicitement.

2) D’une façon toute semblable, nous écrirons $[p(q)]$ pour la classe $[1100]$ , $[\sim p(q)]$ pour la classe $[0011]$ et $[\sim q(p)]$ pour la classe~ $[0101]$ .

Cela dit, il est possible d’ordonner les 16 classes d’équivalence comme le montre le diagramme précédent. On s’assurera par le calcul que les propositions choisies appartiennent bien aux classes correspondantes. Enfin nous avons écrit $\top$ pour désigner l’opérateur tel que $p\top q\in[1111]$ et $\bot$ pour représenter celui tel que $p.\bot q\in[0000]$ .

Ce schéma a cinq niveaux et il est disposé de telle façon que si une classe de niveau $n$ est reliée à une classe de niveau $n+k$ , elle la précède. Ainsi $[0100]\leq[0111]$ . Toutefois deux classes quelconques ne sont pas toujours reliées : on a affaire à un ordre partiel. Les
classes d’un même niveau ne sont pas ordonnées entre elles, et il n’est pas non plus possible de comparer $[1001]$ par exemple à $[0111]$ .

Si l’on revient à la définition que nous avons donnée de la relation $\leq$ , le même schéma permet de lire les implications entre les propositions, donc les tautologies.

Exemples

$\vdash\left(p\wedge q\right)\supset p$ ; $\vdash p\supset\left(p\vee q\right)$ ; $\vdash\left(p\wedge q\right)\supset\left(p\supset q\right)$ .

Enfin la proposition notée $p\bot q$ implique toutes les autres. Elle correspond à la contradiction et ce fait traduit partiellement l’adage ex falso quodlibet sequitur. Réciproquement, toute proposition implique celle notée $p\top q$ . La chose se comprend facilement puisque $p\top q$ correspond à la notion de tautologie. Soit $P$ une proposition dont l’évaluation est (\emph{a b c d}). Formons la conditionnelle $P\supset(p\top q)$ . On aura :
$\begin{tabular}{l>{\raggedleft}m{0.15\textwidth}} \begin{tabular}{>{\raggedleft}m{0.15\textwidth}|cccc} P & \emph{a} & \emph{b} & \emph{c} & \emph{d}\tabularnewline $p\top q$ & 1 & 1 & 1 & 1\tabularnewline \hline \hline $P\supset(p\top q)$ & 1 & 1 & 1 & 1\tabularnewline \end{tabular} & % \parbox[t]{0.65\columnwidth}{% En effet, si $a$ est 1, on a bien $val(1\supset1)=1$ \\ et si $a$ est 0 on a aussi $val(0\supset1)=1.$\\ De même avec b, c et d.% }\tabularnewline \end{tabular}$

Remarques

1) Soit $P,$ $Q$ et $M$ trois propositions qui ont entre elles les relations de la figure 2. Alors $M$ est $P\wedge Q$ . De même si $P$ , $Q$ et $M$ ont entre elles les relations de la figure 3, $M$ est $P\vee Q$ .\smallskip{}

Exemples

$\left(p\equiv q\right)\wedge\left(\sim p\left(q\right)\right)\leftrightarrow\sim p\wedge\sim q$ ; $\left(p\wedge q\right)\vee\left(\sim p\wedge q\right)\leftrightarrow q\left(p\right)$ \\
$\left(q\supset p\right)\wedge\left(p\equiv q\right)\leftrightarrow p\equiv q$ ; $\left(p\vee\negthickspace\negthickspace\vee q\right)\vee\left(\sim p\wedge q\right)\leftrightarrow p\vee\negthickspace\negthickspace\vee q$

2) La structure représentée à la figure 1 est isomorphe à celle de l’ensemble des parties d’un ensemble $E$ à 4 éléments. Elle constitue de plus un exemple d’algèbre de Boole (V. Fascicule III).