3.4 Modélisations par des structures arborescentes
97
La loi P n dépend de la taille de l’arbre, et il est assez naturel de se demander
ce qui se passe lorsque l’arbre devient de grande taille : la suite des distributions
(P n ) n≥1 admet-elle une limite lorsque n tend vers l’infini ? Sous les conditions
d’uniformité que nous avons présentées plus haut, la réponse est positive, et permet
de définir une loi de probabilité P sur l’ensemble des fonctions booléennes à k
variables par
P(f ) = lim
n→+∞
|A n (f )|
|A n |
.
De plus, il est possible de relier la probabilité P(f ) d’une fonction booléenne
à sa complexité, définie comme la taille des plus petits arbres la représentant. 20
Revenons à l’exemple de la fonction booléenne x ∨ (y ∧ (z ∨ t)) : elle dépend
des quatre variables x, y, z et t, donc toute représentation arborescente a au moins
quatre feuilles, une pour chaque variable : la fonction est de complexité 4. L’arbre de
la figure 3.22 est de taille 5 et n’est pas minimal, par contre celui de la figure 3.23
est de taille 4, donc minimal (ce n’est pas le seul). En approximant un arbre ETOU par un arbre infini biaisé et en étudiant le processus de croissance de cet arbre
biaisé, Lefmann et Savický [164] ont obtenu un encadrement de la probabilité d’une
fonction booléenne en fonction de sa complexité, encadrement ensuite amélioré
dans [38].
Plusieurs travaux se sont ensuite intéressés à la caractérisation des lois de
probabilités ainsi obtenues, non plus dans le cas des arbres ET-OU, mais en étendant
l’approche précédente à d’autres connecteurs tels que l’implication, ou en prenant
des connecteurs associatifs ou commutatifs (cf. par exemple Genitrini, Gittenberger,
Mailler, Kozik, Kraus [108, 117, 119]). Enfin l’hypothèse initiale d’un nombre fini
de variables est levée dans un article récent de Genitrini et Mailler [118].
Tout ce que nous venons de dire s’applique à la logique propositionnelle
« classique » ; mais il est aussi possible de sortir de ce cadre et de considérer
d’autres logiques, telle la logique intuitionniste propositionnelle. Comme la logique
propositionnelle classique, celle-ci fait appel à des opérateurs logiques (par exemple, →, ∧, ∨ et ¬). Mais, à la différence de la logique classique pour laquelle les
tautologies sont définies comme les expressions vraies pour toute assignation de
VRAI ou FAUX aux variables booléennes, la logique intuitionniste (aussi appelée
pour cette raison constructiviste) ne retient comme tautologies que les expressions
pouvant être démontrées à partir de la règle d’inférence Modus Ponens (de x et
x → y, on peut déduire y) et d’un ensemble donné d’axiomes. L’expression x ∨ ¬x
(« tiers exclu ») ne fait pas partie de cet ensemble d’axiomes, et ne peut pas en être
déduit. C’est un exemple de tautologie « classique » qui n’est pas « intuitionniste »,
alors que les tautologies intuitionnistes sont aussi des tautologies classiques. Nous
renvoyons la lectrice et le lecteur curieux d’en savoir plus au livre de Sorensen
20 Attention : cette notion de complexité d’une fonction booléenne n’est pas intrinsèque, mais
dépend de la représentation arborescente choisie.
97
La loi P n dépend de la taille de l’arbre, et il est assez naturel de se demander
ce qui se passe lorsque l’arbre devient de grande taille : la suite des distributions
(P n ) n≥1 admet-elle une limite lorsque n tend vers l’infini ? Sous les conditions
d’uniformité que nous avons présentées plus haut, la réponse est positive, et permet
de définir une loi de probabilité P sur l’ensemble des fonctions booléennes à k
variables par
P(f ) = lim
n→+∞
|A n (f )|
|A n |
.
De plus, il est possible de relier la probabilité P(f ) d’une fonction booléenne
à sa complexité, définie comme la taille des plus petits arbres la représentant. 20
Revenons à l’exemple de la fonction booléenne x ∨ (y ∧ (z ∨ t)) : elle dépend
des quatre variables x, y, z et t, donc toute représentation arborescente a au moins
quatre feuilles, une pour chaque variable : la fonction est de complexité 4. L’arbre de
la figure 3.22 est de taille 5 et n’est pas minimal, par contre celui de la figure 3.23
est de taille 4, donc minimal (ce n’est pas le seul). En approximant un arbre ETOU par un arbre infini biaisé et en étudiant le processus de croissance de cet arbre
biaisé, Lefmann et Savický [164] ont obtenu un encadrement de la probabilité d’une
fonction booléenne en fonction de sa complexité, encadrement ensuite amélioré
dans [38].
Plusieurs travaux se sont ensuite intéressés à la caractérisation des lois de
probabilités ainsi obtenues, non plus dans le cas des arbres ET-OU, mais en étendant
l’approche précédente à d’autres connecteurs tels que l’implication, ou en prenant
des connecteurs associatifs ou commutatifs (cf. par exemple Genitrini, Gittenberger,
Mailler, Kozik, Kraus [108, 117, 119]). Enfin l’hypothèse initiale d’un nombre fini
de variables est levée dans un article récent de Genitrini et Mailler [118].
Tout ce que nous venons de dire s’applique à la logique propositionnelle
« classique » ; mais il est aussi possible de sortir de ce cadre et de considérer
d’autres logiques, telle la logique intuitionniste propositionnelle. Comme la logique
propositionnelle classique, celle-ci fait appel à des opérateurs logiques (par exemple, →, ∧, ∨ et ¬). Mais, à la différence de la logique classique pour laquelle les
tautologies sont définies comme les expressions vraies pour toute assignation de
VRAI ou FAUX aux variables booléennes, la logique intuitionniste (aussi appelée
pour cette raison constructiviste) ne retient comme tautologies que les expressions
pouvant être démontrées à partir de la règle d’inférence Modus Ponens (de x et
x → y, on peut déduire y) et d’un ensemble donné d’axiomes. L’expression x ∨ ¬x
(« tiers exclu ») ne fait pas partie de cet ensemble d’axiomes, et ne peut pas en être
déduit. C’est un exemple de tautologie « classique » qui n’est pas « intuitionniste »,
alors que les tautologies intuitionnistes sont aussi des tautologies classiques. Nous
renvoyons la lectrice et le lecteur curieux d’en savoir plus au livre de Sorensen
20 Attention : cette notion de complexité d’une fonction booléenne n’est pas intrinsèque, mais
dépend de la représentation arborescente choisie.