Antoine Genitrini (Versailles)

Écrivez une expression booléenne de manière aléatoire, construite avec des ensembles fixes de connecteurs et de littéraux. Quelle est la fonction booléenne “typique” qu’elle représente ? Quelle est la probabilité que l’expression calcule la fonction Vrai ? Un littéral ? Ou une autre fonction donnée ? D’autres questions de nature un peu différente peuvent se poser : quelle est la complexité de la fonction booléenne représentée par cette expression aléatoire (i.e. la taille de la plus petite expression la représentant) ? Quelle est la complexité moyenne d’une fonction booléenne définie sur k variables ?

Ces questions mettent en avant le problème suivant : comment définir une distribution de probabilité sur les fonctions booléennes à partir d’expressions aléatoires ? Les premiers articles se posant ce genre de questions ont mis en avant deux modèles de expressions booléennes aléatoires, basées sur les connecteurs binaires Et/Ou , et qui engendrent une distribution (non uniforme) sur les fonctions booléennes. Ces articles n’ont répondu que très partiellement aux premières questions que j’ai évoquées. On adapte aisément ces distributions au cas de expressions construites à l’aide de l’unique connecteur Implication , un des connecteurs de base d’un point de vue logique. Ce modèle de base suscite de l’intérêt car certaines expressions représentant des tautologies (expression calculant toujours Vrai ) en logique classique ne sont pas des tautologies en logique intuitionniste.

Dans un premier temps, j’exposerai les résultats concernant les tautologies construites sur l’ Implication , puis j’aborderai la distribution de probabilité sur l’ensemble des fonctions booléennes construites avec ce connecteur logique. Dans un troisième temps, j’enrichirai le modèle de expressions en utilisant plusieurs connecteurs logiques aléatoires. Enfin, je conclurai l’expose en abordant différentes perspectives relatives à ces problèmes et sur lesquelles je travaille actuellement.