Opérations Booléennes

Opérations booléennes

Combien y a-t-il d’opérations booléennes binaires ?

Il y a 4 combinaisons possibles de couples qu’on peut former avec 1 et 2. Comme il y a 2 choix possibles (0 ou 1) à assigner pour chacun des 4 couples (positions) possibles $(0, 0)$, $(0, 1)$, $(1, 0)$, et $(1, 1)$, le nombre total de combinaisons possibles est : $2^4 = 16$.

En effet, pour déterminer toutes les configurations possibles d’association des entrées à leurs sorties, on peut calculer le nombre de chaînes de longueur 4 où chaque position correspond à l’issue d’une entrée.

Nombre de fonctions booléennes Nombre de fonctions booléennes

(Ici, les niveaux correspondent aux configurations possibles d’attributions successives des issues aux entrées et chaque chemin correspond à une configuration possible d’une fonction.)

Suffisance des connecteurs ∧, ∨, et ¬

La logique booléenne introduite par George Boole dans les années 1850, dans son ouvrage “An Investigation of the Laws of Thought” stipule que tout énoncé logique pouvait être représenté par des combinaisons des opérations booléennes. C’est cette idée qui a conduit à la notion de forme normale pour exprimer des fonctions booléennes, dont la forme normale disjonctive (DNF).

Émile Post a publié en 1921 le “théorème de la Forme Normale Disjonctive”. Ce théorème affirme que toute formule logique $X$ dans un langage propositionnel $\mathcal{L}$, contenant $n$ variables propositionnelles ($A_1, \ldots, A_n$), peut être réécrite sous forme de disjonction (OU) de conjonctions (ET) de littéraux (des variables ou leurs négations).

Une des conséquences de ce théorème est la complétude fonctionnelle de $\{\land, \lor, \neg\}$ (i.e $\{\land, \neg\}$ ou $\{\lor, \neg\}$). Autrement dit, toute opération booléenne binaire peut être construite en combinant ces trois connecteurs de base.

Pour une fonction $f(x, y)$ sur deux variables booléennes $x$ et $y$, la DNF se construit comme suit :

  1. Pour chaque couple d’entrée $(x, y)$ tel que $f(x, y) = 1$, on écrit une conjonction (minterme) qui décrit cette combinaison précise des valeurs de $x$ et $y$.
  2. On relie toutes ces conjonctions à l’aide de l’opérateur $\lor$ (OU) pour obtenir l’expression complète de $f$.

Preuve de la suffisance des connecteurs ∧, ∨, et ¬

Soit $f : \mathbf{B}^2 \rightarrow \mathbf{B}$ une fonction booléenne binaire quelconque. La fonction $f(x, y)$ peut assigner $0$ ou $1$ à chaque combinaison d’entrées possible : $(0,0)$, $(0,1)$, $(1,0)$, et $(1,1)$.

Pour chaque couple d’entrée où $f(x, y) = 1$, on écrit une conjonction (ET) qui correspond à cette combinaison particulière de valeurs:

  • Si $f(0,0) = 1$ : $\neg x \land \neg y$.
  • Si $f(0,1) = 1$, : $\neg x \land y$.
  • Si $f(1,0) = 1$: $x \land \neg y$.
  • Si $f(1,1) = 1$ : $x \land y$.

L’expression finale pour $f(x, y)$ est obtenue en prenant la disjonction (OU) de toutes les conjonctions écrites précédemment, c’est-à-dire, en combinant toutes les conjonctions où $f(x, y) = 1$.

En utilisant la forme normale disjonctive, on a que toute fonction booléenne binaire $f : \mathbf{B}^2 \rightarrow \mathbf{B}$ peut être exprimée uniquement en utilisant les connecteurs $\land$, $\lor$, et $\neg$.

Fonction $(0,0)$ $(0,1)$ $(1,0)$ $(1,1)$ Expression avec ∧, ∨, et ¬ Description
$f_1$ $0$ $0$ $0$ $0$ $a \land \neg a$ Fonction constante $0$ (toujours $0$)
$f_2$ $0$ $0$ $0$ $1$ $a \land b$ ET (AND)
$f_3$ $0$ $0$ $1$ $0$ $a \land \neg b$ Projection inversée sur $a$
$f_4$ $0$ $1$ $0$ $1$ $b$ Projection sur $b$
$f_5$ $0$ $1$ $0$ $0$ $\neg a \land b$ Projection inversée sur $b$
$f_6$ $0$ $0$ $1$ $1$ $a$ Projection sur $a$
$f_7$ $0$ $1$ $1$ $0$ $(a \lor b) \land \neg (a \land b)$ XOR (OU exclusif)
$f_8$ $0$ $1$ $1$ $1$ $a \lor b$ OU (OR)
$f_9$ $1$ $0$ $0$ $0$ $\neg (a \lor b)$ NOR (NON-OU)
$f_{10}$ $1$ $0$ $0$ $1$ $(a \land b) \lor \neg (a \lor b)$ Égalité (XNOR)
$f_{11}$ $1$ $1$ $0$ $0$ $\neg a$ NON $a$
$f_{12}$ $1$ $1$ $0$ $1$ $\neg a \lor b$ Implication (non strict)
$f_{13}$ $1$ $1$ $0$ $0$ $\neg b$ NON $b$
$f_{14}$ $1$ $0$ $1$ $1$ $a \lor \neg b$ Implication strict
$f_{15}$ $1$ $1$ $1$ $0$ $\neg (a \land b)$ NAND (NON-ET)
$f_{16}$ $1$ $1$ $1$ $1$ $a \lor \neg a$ Fonction constante $1$ (toujours $1$)

Opérations commutatives

Il existe 8 opérations booléennes binaires commutatives. Une opération binaire est commutative si l’ordre des opérandes n’affecte pas le résultat, ce qui impose la contrainte $f(0,1) = f(1,0)$, et réduit les 16 fonctions binaires possibles à $2^3 = 8$ puisque la deuxième et troisième position dans notre calcul précédent font une position désormais.

Dans une fonction booléenne commutative exprimée en forme normale disjonctive (DNF), les mintermes correspondant aux entrées symétriques $(\neg x \land y)$ (pour $(0,1)$) et $(x \land \neg y)$ (pour $(1,0)$) doivent avoir des contributions égales. Ce qui impose que les mintermes $(\neg x \land y)$ et $(x \land \neg y)$ doivent toujours être présents ou absents ensemble pour garantir la commutativité.

Les mintermes possibles pour une fonction booléenne binaire sont :

  • $(\neg x \land \neg y)$, pour $(0,0)$,
  • $(\neg x \land y)$ et $(x \land \neg y)$, pour $(0,1)$ et $(1,0)$ (symétriques),
  • $(x \land y)$, pour $(1,1)$.

On obtient alors 8 fonctions commutatives distinctes:

Fonction constante toujours nulle (absurdité ⊥) :

DNF : aucun minterme.

$f(0,0) = 0$, $f(0,1) = 0$, $f(1,0) = 0$, $f(1,1) = 0$.

Fonction constante toujours vraie (tautologie ⊤) :

DNF : $(\neg x \land \neg y) \lor (\neg x \land y) \lor (x \land \neg y) \lor (x \land y)$

$$= \left[ \neg x \land (\neg y \lor y) \right] \lor \left[ x \land (\neg y \lor y) \right] = (\neg x \land 1) \lor (x \land 1) = \neg x \lor x = 1.$$

$f(0,0) = 1$, $f(0,1) = 1$, $f(1,0) = 1$, $f(1,1) = 1$.

Conjonction (et) :

DNF : $(x \land y)$.

$f(0,0) = 0$, $f(0,1) = 0$, $f(1,0) = 0$, $f(1,1) = 1$.

Disjonction (ou) :

DNF : $(\neg x \land y) \lor (x \land \neg y) \lor (x \land y)$

$$= \left[ (\neg x \lor x) \land y \right] \lor \left[ x \land (\neg y \lor y) \right] = (1 \land y) \lor (x \land 1) = y \lor x = x \lor y.$$

$f(0,0) = 0$, $f(0,1) = 1$, $f(1,0) = 1$, $f(1,1) = 1$.

Équivalence logique $x \Leftrightarrow y$ :

DNF : $(\neg x \land \neg y) \lor (x \land y) = x \Leftrightarrow y$.

$f(0,0) = 1$, $f(0,1) = 0$, $f(1,0) = 0$, $f(1,1) = 1$.

OU exclusif (XOR) :

DNF : $(\neg x \land y) \lor (x \land \neg y) = x \oplus y$.

$f(0,0) = 0$, $f(0,1) = 1$, $f(1,0) = 1$, $f(1,1) = 0$.

Négation de l’ET (NAND) :

DNF : $(\neg x \land \neg y) \lor (\neg x \land y) \lor (x \land \neg y)$

$$= \neg x \lor \neg y.$$

$f(0,0) = 1$, $f(0,1) = 1$, $f(1,0) = 1$, $f(1,1) = 0$.

Négation de l’OU (NOR) :

  • DNF : $(\neg x \land \neg y)$.

    $f(0,0) = 1$, $f(0,1) = 0$, $f(1,0) = 0$, $f(1,1) = 0$.

Les seules opérations booléennes binaires commutatives et associatives sont les fonctions constantes, et les quatre opérations $\wedge, \vee, \Leftrightarrow$ et $\oplus$

$f$ est associative si :

$$ f(f(x, y), z) = f(x, f(y, z)), \quad \forall x, y, z \in \{0, 1\}. $$

Parmi les fonctions commutatives précédemment identifiées, identifions celles qui sont également associatives.

  1. Fonctions constantes : sont trivialement associatives et commutatives.

  2. Fonction $\land$ :
    $f(x, y) = x \land y$

    $$ (x \land y) \land z = x \land (y \land z). $$

  3. Fonction $\lor$ :
    $f(x, y) = x \lor y$ est aussi commutative et associative, car :

    $$ (x \lor y) \lor z = x \lor (y \lor z). $$

  4. Fonction $\Leftrightarrow$ (Équivalence) :
    $f(x, y) = x \Leftrightarrow y$ (biconditionnel ou “IFF”) est commutative et associative. Cela peut être vérifié avec sa table de vérité et la propriété suivante :

    $$ (x \Leftrightarrow y) \Leftrightarrow z = x \Leftrightarrow (y \Leftrightarrow z). $$

  5. Fonction $\oplus$ (XOR) :
    $f(x, y) = x \oplus y$ (OU exclusif) est également associative et commutative :

    $$ (x \oplus y) \oplus z = x \oplus (y \oplus z). $$

  6. Autres fonctions :

    • $f(x, y) = \neg(x \lor y)$ (NOR)

      Un contre-exemple simple montre que cette fonction échoue à être associative :

      Prenons $x = 1$, $y = 0$, $z = 0$ :

      $$ f(f(x, y), z) = f(0, 0) = 1,\\f(x, f(y, z)) = f(1, 1) = 0. $$

      Donc la fonction n’est pas associative.

    • $f(x,y) = \neg(x \land y) $ (NAND)

      Prenons $x = 1$, $y = 1$, $z = 0$.

      $$ f(f(1, 1), 0) = f(0, 0) = \neg(0 \land 0) = 1. $$$$ f(1, f(1, 0)) = f(1, 1) = \neg(1 \land 1) = 0. $$

      D’où la fonction $f(x, y) = \neg(x \land y)$ n’est pas associative.

Eléments neutres

Un opérateur $f(x, y)$ possède un élément neutre $e$ si $f(x, e) = x$ pour tout $x$. Vérifions ça pour les quatre opérations non constantes :

  1. Pour $\land$ (ET) :
    $1$ est l’élément neutre car $x \land 1 = x$.

  2. Pour $\lor$ (OU) :
    $0$ est l’élément neutre car $x \lor 0 = x$.

  3. Pour $\Leftrightarrow$ (Équivalence) :
    $1$ est l’élément neutre car $x \Leftrightarrow 1 = x$.

  4. Pour $\oplus$ (XOR) :
    $0$ est l’élément neutre car $x \oplus 0 = x$.