98
3 Arbres, algorithmes et données
Fig. 3.24 À gauche, les tautologies simples ; à droite, des expressions qui ne sont jamais des
tautologies lorsque B ∈ {C 1 , . . . , C p }
Fig. 3.25 Les différents ensembles de tautologies : classiques, simples et intuitionnistes
et Urzyczyn [238] pour une présentation détaillée de la logique intuitionniste, et
explicitons maintenant l’intérêt que présentent les arbres d’expressions pour la
comparer à la logique classique.
Considérons par exemple l’ensemble E des expressions construites à partir du
seul connecteur d’implication → et des littéraux positifs, et parmi elles l’ensemble
des expressions de la forme (A 1 → (· · · → (A p → B))), où B et les A i
(i = 1, . . . , p) sont des expressions de E, et où de plus B est l’un des A i (cf. la
figure 3.24). De telles expressions sont évidemment des tautologies de la logique
classique (elles prennent la valeur VRAI pour toute assignation des variables) ;
nous les appelons tautologies simples. Il est possible de montrer que les tautologies
simples sont des tautologies intuitionnistes ; la figure 3.25 visualise ces relations
d’inclusion entre les ensembles des tautologies intuitionnistes, simples et classiques.
Il est également possible de caractériser des ensembles d’expressions qui ne sont pas
des tautologies, par exemple celles qui sont de la forme ((A 1 → C 1 ) → (· · · →
((A p → C p ) → B))) lorsque B n’est pas un des C i (cf. la figure 3.24). Tous ces
ensembles d’expressions sont en fait des familles d’arbres, dont le dénombrement
permet de calculer la probabilité qu’une expression choisie uniformément parmi
toutes les expressions de taille n appartienne à l’une de ces familles, appelons-la F ,
puis de passer à la limite lorsque n tend vers l’infini (comme auparavant lors de
l’obtention d’une loi de probabilité sur les fonctions booléennes) et de définir une
proportion limite π k (F ). Cette limite dépend du nombre k de variables booléennes,
qu’il est possible de faire à son tour tendre vers l’infini ; c’est ainsi qu’il a été montré
que les ensembles des tautologies simples et des tautologies classiques, et donc
aussi l’ensemble des tautologies intuitionnistes, représentent asymptotiquement,
3 Arbres, algorithmes et données
Fig. 3.24 À gauche, les tautologies simples ; à droite, des expressions qui ne sont jamais des
tautologies lorsque B ∈ {C 1 , . . . , C p }
Fig. 3.25 Les différents ensembles de tautologies : classiques, simples et intuitionnistes
et Urzyczyn [238] pour une présentation détaillée de la logique intuitionniste, et
explicitons maintenant l’intérêt que présentent les arbres d’expressions pour la
comparer à la logique classique.
Considérons par exemple l’ensemble E des expressions construites à partir du
seul connecteur d’implication → et des littéraux positifs, et parmi elles l’ensemble
des expressions de la forme (A 1 → (· · · → (A p → B))), où B et les A i
(i = 1, . . . , p) sont des expressions de E, et où de plus B est l’un des A i (cf. la
figure 3.24). De telles expressions sont évidemment des tautologies de la logique
classique (elles prennent la valeur VRAI pour toute assignation des variables) ;
nous les appelons tautologies simples. Il est possible de montrer que les tautologies
simples sont des tautologies intuitionnistes ; la figure 3.25 visualise ces relations
d’inclusion entre les ensembles des tautologies intuitionnistes, simples et classiques.
Il est également possible de caractériser des ensembles d’expressions qui ne sont pas
des tautologies, par exemple celles qui sont de la forme ((A 1 → C 1 ) → (· · · →
((A p → C p ) → B))) lorsque B n’est pas un des C i (cf. la figure 3.24). Tous ces
ensembles d’expressions sont en fait des familles d’arbres, dont le dénombrement
permet de calculer la probabilité qu’une expression choisie uniformément parmi
toutes les expressions de taille n appartienne à l’une de ces familles, appelons-la F ,
puis de passer à la limite lorsque n tend vers l’infini (comme auparavant lors de
l’obtention d’une loi de probabilité sur les fonctions booléennes) et de définir une
proportion limite π k (F ). Cette limite dépend du nombre k de variables booléennes,
qu’il est possible de faire à son tour tendre vers l’infini ; c’est ainsi qu’il a été montré
que les ensembles des tautologies simples et des tautologies classiques, et donc
aussi l’ensemble des tautologies intuitionnistes, représentent asymptotiquement,