Classification des fonctions booléennes pour la corrélation d’ordre 1

Dans cet exposé nous verrons commment classifier les fonctions booléennes à n variables, pour n fixé, en fonction de leur “distance” aux fonctions sans corrélation d’ordre 1. Ces dernières forment les classes (à n variables) les plus grandes, et les cardinalités respectives des autres classes diminuent plus elles s’en éloignent. Nous disposons d’un opérateur binaire qui construit une classe à n variables en composant deux classes à n-1 variables. Un opérateur “inverse” (basé sur une méthode récursive) permet d’énumérer l’ensemble des fonctions booléennes d’une classe à n variables, pour n peu élevé. Nous verrons que cette méthode permet d’obtenir la première borne inférieure non triviale du nombre de fonctions sans corrélation d’ordre 1. D’autre part, elle fournit un algorithme pour générer aléatoirement une fonction booléenne parmi une fraction importante des fonctions sans- corrélation d’ordre 1.

(Travail en collaboration avec Thomas Leduc, CERMA)