.

Définitions

.

Les fonctions booléennes, qui associent un booléen, 0 ou 1, à un ou plusieurs booléen(s).

L’expression des fonctions booléennes

Comme les fonctions d’une variable réelle, les fonctions booléennes peuvent s’exprimer de manière symbolique : l’expression\(\left( {non\left( x \right)\ et\ y} \right)\ ou\ \left( {x\ et\ z} \right)\) est bâtie sur le même modèle que l’expression\((sin\left( x \right) \times y) + (x \times z)\) , sauf que les variables\(x,y\,\, et\,\, z\,,\, y\) représentent des booléens et non des nombres réels.

En revanche, contrairement aux fonctions d’une variable réelle, ces fonctions ne peuvent pas s’exprimer par des courbes. Néanmoins, elles peuvent s’exprimer d’une nouvelle manière : par des tables car, à la différence des nombres réels, les booléens sont en nombre fini.

.

Les fonctions non et, ou

Les fonctions non, et et ou sont définies par les tables suivantes.

 \(\mathbf{non}\left( \mathbf{x} \right)\)

.

x non(x)
0 1
1 0

.

 \(\mathbf{et}~\left( {\mathbf{x},\mathbf{y}} \right)\)

x y et(x,y)
0 0 0
0 1 0
1 0 0
1 1 1

.

 \(\mathbf{ou}~\left( {\mathbf{x},\mathbf{y}} \right)\)

x y ou(x,y)
0 0 0
0 1 1
1 0 1
1 1 1

T Notation

De même que l’on écrit \(x + y\) le nombre que l’on devrait, en toute rigueur, écrire \(+ \left( {x,y} \right)\) , on écrit souvent x et \(y\) le booléen que l’on devrait écrire et \(\left( {x,y} \right)\)  .

Le nom de ces fonctions vient de la convention de lire 0 comme « faux » et 1 comme « vrai ».

•          Ainsi, la fonction non transforme faux en vrai et vrai en faux : le booléen \(non\left( x \right)\) est donc égal à 1 si et seulement si \(x\) n’est pas égal à 1.

•          De même, le booléen \(x\) et y est égal à 1 si et seulement si \(x\)est égal à 1 et \(y\) est égal à 1.

•          Le booléen \(x\) ou \(y\) est égal à 1 si et seulement si au moins \(x\)ou \(y\) est égal à 1.

On remarquera que, quand \(x\) et \(y\) sont tous les deux égaux à 1, \(x\) ou \(y\) est égal à 1. Ce ou est donc inclusif ; c’est le ou qui apparaît dans la phrase « Je viendrai s’il y a un bus ou un métro. » et non le ou exclusif qui apparaît dans la phrase « Tu dois choisir : aller à la mer ou aller à la montagne. » Pour le distinguer du précédent, ce ou exclusif sera noté oux.

L’expression des fonctions booléennes avec les fonctionsnon,et,ou

On peut exprimer de manière symbolique toutes les fonctions booléennes avec les seules fonctions non, et et ou.

Avant de voir comment le faire dans le cas général, on commence par exprimer cinq fonctions particulières, qui seront utilisées dans la suite.

La première est la fonction\(multiplexeur,\ mux\) . Cette fonction de\(\left\{ 0,1 \right\}^{3}\) dans\(\left\{ 0,1 \right.\) } est telle que si x vaut 0, alors mux(x,y,z) vaut y et si x vaut 1, alors mux(x,y,z) vaut z. Elle est définie par la table ci-après. Elle s’exprime avec les fonctions non, et et ou, par l’expression symbolique\(mux\left( {x,y,z} \right) = \left( {non\left( x \right)et\ y} \right)ou\left( {x\ et\ z} \right)\) .

mux(x,y,z)

Pour le montrer, on calcule ligne à ligne la table de la fonction qui à x, y et z associe (non(x) et y) ou (x et z) en ajoutant des colonnes correspondant aux calculs intermédiaires et on vérifie, ligne à ligne, que cette table est celle de la fonction mux :

.

x y z non(x ) non(x ) et y x et z (non( x) et y) ou (x et z)
0 0 0 1 0 0 0
0 0 1 1 0 0 0
0 1 0 1 1 0 1
0 1 1 1 1 0 1
1 0 0 0 0 0 0
1 0 1 0 0 1 1
1 1 0 0 0 0 0
1 1 1 0 0 1 1

.

Les quatre autres cas particuliers sont les quatre fonctions de\(\left\{ 0,1 \right\}\) dans\(\left\{ 0,1 \right\}\)  :

•          la fonction constante égale à\(0\ ()\) exprimée, de manière symbolique, par\(h\left( x \right)\ = x\ et\ non(x),\) h(x) = x et non(x),

•          la fonction constante égale à\(1\ ()\)  exprimée par  \(k\left( x \right)\ = x\ ou\ non(x),\)

•          l’ « identité »\(~()\)  exprimée par  \(i\left( x \right)\ = x\) , sans utiliser aucune fonction,

•          et la fonction non,

.

x h(x)
0 0
1 0

.

x k(x)
0 1
1 1

.

x i(x)
0 0
1 1

.

qui peuvent donc toutes les quatre être exprimées avec des fonctions non, et et ou.

On peut maintenant voir comment exprimer toutes les fonctions de\(\left\{ 0,1 \right\}^{n}\) dans\(\left\{ 0,1 \right\}\)  avec les fonctions non, et et ou. On procède par récurrence sur n.

Dans le cas\(n = \ 1\) , la fonction à exprimer est l’une des fonctions h, k, i et non, qui peuvent toutes s’exprimer avec les fonctions non, et et ou.

On suppose maintenant que l’on sait exprimer toutes les fonctions de\(\left\{ 0,1 \right\}^{n}\) dans\(\left\{ 0,1 \right\}\)  avec les fonctions non, et et ou et on se donne une fonction\(f\) de\(\left\{ 0,1 \right\}^{n}{}^{+ 1}\) dans\(\left\{ 0,1 \right\}\) . On définit les fonctions\(getg’de\ \left\{ 0,1 \right\}^{n}dans\ \left\{ 0,1 \right\}\) par :

\(g(x_{1},\ \ldots,x_{n})\ = f(x_{1},\ldots,\ x_{n},0)g’(x_{1},\ldots,x_{n})\ = f(x_{1},\ldots,\ x_{n},1)\) et on remarque que la fonction f peut s’exprimer de manière symbolique avec les fonctions g, g’ et mux :

\(~f(x_{1},\ldots,x_{n},x_{n} + 1)\ = mux(x_{n} + 1,g(x_{1},\ldots,x_{n}),g’(x_{1},\ldots,x_{n}))\) car, quand\(x_{n}{}_{+ 1}\) vaut 0, le membre de gauche et le membre de droite sont tous les deux égaux à\(g\left( {x_{1},\ldots,x_{n}} \right)\) et, quand\(x_{n} + 1\) vaut 1, les deux membres sont égaux à\(g’\left( {x_{1},\ldots,x_{n}} \right)\) .

Par hypothèse de récurrence, on sait exprimer les deux fonctions g et g’ de manière symbolique avec les fonctions non, et et ou, et comme on sait aussi exprimer la fonction mux, on peut exprimer la fonction f en remplaçant les fonctions mux, g et g’ par leur expression en termes de non, et et ou.

SAVOIR-FAIRE Trouver une expression symbolique exprimant une fonction à partir de sa table

On identifie le nombre d’arguments de la fonctionf. On extrait de la table de la fonctionfles tables des fonctionsget\(g’\)  définies par :

\(g(x_{1},\ \ldots,x_{n})\ = f(x_{1},\ldots,\ x_{n},0)\ g’(x_{1},\ldots,\ x_{n})\ = \ f(x_{1},\ldots,\ x_{n},1)\) On trouve les expressions symboliques de ces deux fonctions et on construit celle de la fonctionfà partir de ces deux expressions symboliques et de celle de la fonction multiplexeur.

Exercice.1

Trouver une expression symbolique exprimant une fonction ou exclusif (oux) définie par la table ci-dessous.

.

x y sx oux y
0 0 0
0 1 1
1 0 1
1 1 0

.

Le booléen \(oux:\ \ x\ oux\ y\ \)est égal à 1 si et seulement six est égal à 1 ou y est égal à 1, mais pas les deux.

Soit g la fonction définie par \(g(x)= \ x\ oux\ y\)` et g’ la fonction définie par   . \(g('x)= \ x\ oux\ y\)

La table de la fonctiong est et celle de la fonction g’ est .

.

x g(x)
0 0
1 1

.

x g’(x)
0 1
1 0

.

On reconnaît les tables de la fonction identité et de la fonctionnon. Donc    :\(g(x) = x,, et,, g’(x) = non(x)\) , d’où on tire l’expression de la fonction  \(oux:\ \bullet \ x\ oux\ y\ = mux(y,x,non\left( x \right))\ = \ (non\left( y \right)\ et\ x)ou(yet\ non(x))\)

Exercice 2

Trouver l’expression symbolique de la fonction de « si et seulement si » définie par la table ci-dessous.

.

x y x ssi y
0 0 1
0 1 0
1 0 0
1 1 1

.

L’expression des fonctions booléennes avec les fonctionsnonetou

On veut maintenant montrer qu’il est possible de se passer de la fonction et et que toutes les fonctions booléennes peuvent s’exprimer avec les fonctions non et ou. Pour cela, il suffit de montrer que la fonction et elle-même peut s’exprimer ainsi. Cette fonction s’exprime de la manière suivante :

\(\bullet ~~~~~~~~~x\ et\ y = non\left( {non\left( x \right)ou\ non\left( y \right)} \right)\) En effet, la table de la fonction qui à x et y associe  \(non\left( {non\left( x \right)ou\ non\left( y \right)} \right)\) se calcule ligne à ligne (voir ci-dessous) et on reconnaît la table de la fonction et.

.

x y non (non(x) ou non(y))
0 0 0
0 1 0
1 0 0
1 1 1

.

Exercice  3

Montrer que :

\(\bullet ~~~~~~~~~x\ ou\ y = non\left( {non\left( x \right)et\ non\left( y \right)} \right)\) En déduire que toutes les fonctions booléennes peuvent s’exprimer avec les fonctions non et et.

Exercice.4

La fonction de Sheffer exprime l’incompatibilité de deux valeurs booléennes. Elle est définie par la table ci-dessous.

.

x y S (x,y)
0 0 1
0 1 1
1 0 1
1 1 0

.

Montrer que\(S\left( {x,\ y} \right)\ = \ non\left( {x\ et\ y} \right)\) .

Montrer, réciproquement, que\(non\left( x \right)\ = S\left( {x,x} \right)\ etx\ ou\ y\ = \ S\left( {S\left( {x,x} \right),S\left( {y,y} \right)} \right)\) . En déduire que toutes les fonctions booléennes peuvent s’exprimer avec la fonction de Sheffer uniquement.

Le choix d’exprimer les fonctions avec les fonctions non et ou n’est donc qu’un choix parmi d’autres.

Exercice 5

Quand deux interrupteurs sont en parallèle, la lumière s’allume quand l’un d’eux est fermé. Quand ils sont en série, la lumière s’allume quand les deux sont fermés. Quand ils sont en va-et-vient la lumière s’allume quand les deux sont fermés ou les deux sont ouverts. Donner la table de la fonction booléenne dans ces trois cas et exprimer ces trois fonctions booléennes avec les fonctions non et ou.

Exercice 6

Montrer que x et y = y et x. Est-ce la même chose pour ou ? Calculer x et 1 et x et 0. On appelle élément neutre d’une fonction binaire f, un élément n tel que pour tout\(x,f\left( {x,n} \right)\ = \ f\left( {n,x} \right)\ = \ x\) et élément absorbant un élément a tel que pour tout\(x,f\left( {x,a} \right)\ = \ f\left( {a,x} \right)\ = \ a\) . La fonction et a-t-elle un élément neutre ? Et un élément absorbant ? La fonction ou a-telle un élément neutre ? Et un élément absorbant ?

 Exercice 7

Med est content si Bob et Jon sont tous les deux là, mais sans Rut, ou si Rut est là soit avec Bob, soit avec Jon. Construire une table avec en entrée la présence de Rut, Bob et Jon et en sortie le booléen qui vaut 1 si Med est content. Exprimer le choix de Med par une phrase plus simple.

 Exercice 8

Soit f une fonction qui s’exprime de manière symbolique avec la fonction ou uniquement. Montrer que\(f\left( {0,0,\ldots,0} \right)\ = \ 0.\) Montrer que la fonction non ne peut pas s’exprimer avec la fonction ou uniquement.