fonction booléenne

Imaginez deux interrupteurs, chacun réglé sur 0 ou 1. Une fonction booléenne regarde leur position et répond elle aussi par 0 ou 1. La règle peut, par exemple, répondre 1 seulement lorsque le premier interrupteur vaut 1 et le second vaut 0.

En essayant toutes les positions possibles, on obtient une table de vérité. Elle donne une réponse sans ambiguïté pour chaque combinaison d’entrées.

On note B l’ensemble {0, 1}, dont les deux éléments représentent aussi faux et vrai. Pour un entier naturel n, une fonction booléenne à n variables est une application $f:B^n\to Bf:B^n\backslash to\; B$. Elle reçoit donc une combinaison ordonnée de n valeurs booléennes et lui associe une unique valeur booléenne. On l’appelle aussi fonction de Boole, fonction logique ou fonction binaire.

Sa table de vérité énumère les 2ⁿ combinaisons d’entrée et indique la sortie de chacune. Une colonne de 2ⁿ sorties détermine entièrement la fonction. Comme chaque ligne peut recevoir indépendamment 0 ou 1, le nombre de fonctions possibles est $2^{2^n}2^\{2^n\}$. Par exemple, deux variables donnent quatre lignes et 2⁴ = 16 fonctions distinctes.

Pour n ≥ 1, toute fonction booléenne peut aussi s’écrire en combinant ET, OU et NON. Cette expression et la table de vérité sont deux représentations d’une même règle : la table est exhaustive, tandis que l’expression expose les opérations employées.

Une fonction booléenne réunit quatre éléments nécessaires. Le domaine Bⁿ fournit toutes les entrées possibles ; les n variables repèrent les positions dans chaque entrée ; la règle associe une sortie à chaque combinaison ; le codomaine B impose que cette sortie soit 0 ou 1. Une table de vérité consigne enfin la règle ligne par ligne, sans ajouter de donnée nouvelle.

Le nombre de variables fixe le nombre de lignes de la table : n variables produisent 2ⁿ entrées. Les sorties inscrites sur ces lignes fixent ensuite la fonction entière. Le nom des variables ou l’ordre choisi pour afficher les lignes ne change pas l’objet, à condition de conserver la correspondance entre chaque entrée et sa sortie. Ces données suffisent à évaluer la fonction sur toute entrée admise.

Prenons deux variables booléennes, x et y, et la règle « x ET NON y ». Les données sont x ∈ {0, 1}, y ∈ {0, 1}, avec 1 pour vrai et 0 pour faux. La fonction vaut donc $f(x,y)=x\wedge \mathrm{\neg }yf(x,y)=x\backslash land\backslash neg\; y$.

1. Pour l’entrée (0, 0), NON y vaut 1, puis 0 ET 1 vaut 0.

2. Pour l’entrée (0, 1), NON y vaut 0, puis 0 ET 0 vaut 0.

3. Pour l’entrée (1, 0), NON y vaut 1, puis 1 ET 1 vaut 1.

4. Pour l’entrée (1, 1), NON y vaut 0, puis 1 ET 0 vaut 0. La sortie vaut donc 1 dans un seul des quatre cas. Pour contrôler le résultat, relisez les lignes où x vaut 1 : la sortie reproduit alors NON y.

En logique formelle, on évalue une proposition composée en remplaçant chaque affirmation élémentaire par 0 ou 1. Une table de vérité convient lorsque l’on veut contrôler tous les cas ; une expression en ET, OU et NON convient mieux pour suivre la construction de la proposition.

Dans un circuit numérique, les entrées et la sortie sont des valeurs binaires. La fonction booléenne spécifie la réponse attendue du circuit pour chaque combinaison d’entrées, avant de traduire la règle en opérateurs logiques.

En cryptologie, des fonctions booléennes participent à la construction de fonctions de chiffrement. Leur table exhaustive devient vite volumineuse quand n augmente ; une expression par opérateurs est alors plus compacte pour décrire la règle, tandis que la table reste le contrôle direct des petits cas.

Une valeur booléenne est seulement 0 ou 1 ; une fonction booléenne est la règle qui produit une telle valeur à partir d’une ou plusieurs entrées. Dans l’exemple, 1 est une valeur, tandis que « x ET NON y » est une fonction de deux variables.

Un opérateur logique comme ET, OU ou NON est une fonction booléenne particulière. Une fonction booléenne générale peut combiner plusieurs de ces opérateurs. Le critère est la règle complète : « ET » est un opérateur, alors que « x ET NON y » est une composition.

La table de vérité n’est pas une autre fonction. C’est une représentation exhaustive de la même correspondance. Deux expressions qui donnent la même sortie sur chaque ligne décrivent donc la même fonction booléenne.

Le nombre de lignes double à chaque variable ajoutée. Avec n variables, une table possède exactement 2ⁿ lignes : l’énumération reste complète, mais devient rapidement peu commode à lire. Il faut alors conserver une expression logique pour décrire la règle et réserver la table aux vérifications ciblées.

Une table n’est correcte que si chaque combinaison de Bⁿ apparaît une fois. Une ligne manquante laisse la fonction indéterminée sur une entrée ; une ligne répétée avec deux sorties différentes contredit l’exigence d’une sortie unique. Il faut compléter ou corriger la correspondance avant de parler de fonction.

Une écriture par ET, OU et NON n’est pas unique. Des expressions différentes peuvent produire exactement la même colonne de sorties. Le bon test n’est donc pas leur ressemblance visuelle, mais l’égalité de leurs résultats pour toutes les combinaisons d’entrées.

L’algèbre de Boole donne le cadre de calcul dans lequel les opérateurs logiques se combinent et se simplifient.

La table de vérité approfondit la représentation exhaustive employée pour évaluer et comparer les fonctions.

La cryptologie situe le rôle de ces fonctions dans la construction de mécanismes de chiffrement résistants aux attaques.