Résumé : Écrivez une formule booléenne de manière aléatoire, construite avec des ensembles fixés de connecteurs et de littéraux. Quelle est la fonction booléenne « typique » qu’elle représente ? Quelle est la probabilité que la formule 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 formule aléatoire (i.e. la taille de la plus petite formule 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 ? Les premiers articles se posant ce genre de questions ont mis en avant deux modèles de formules 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 formules 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 formules représentant des tautologies (formule calculant toujours Vrai) en logique classique ne sont pas des tautologies en logique intuitionniste. Dans un premier temps, j’exposerai les résultats concernant l’ensemble des fonctions booléennes construites sur l’Implication, puis j’aborderai en détail les tautologies. Dans un troisième temps, j’enrichirai le modèle de formules en utilisant plusieurs connecteurs logiques aléatoires. Enfin, je conclurai l’exposé en abordant différentes perspectives relatives à ces problèmes et sur lesquelles je travaille actuellement.

 [Slides.pdf]

Dernière modification : Monday 27 May 2024

Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr