Taille, hauteur, et le compte des sous-formules

1. L'arbre.

La taille est le nombre de nœuds : quatre feuilles ($p$, $q$, $r$, $p$) et six nœuds internes ($\to$, $\vee$, $\wedge$, et trois $\neg$), soit $10$. La hauteur est la longueur du plus long chemin de la racine à une feuille : $\to$, $\vee$, $\neg$, $\wedge$, $p$ donne quatre arêtes, soit $4$.

2. Les sous-formules distinctes. Il y en a neuf :

$$p,q,r,\neg p,(p\wedge q),\neg \neg p,\neg (p\wedge q),(\neg (p\wedge q)\vee r),\phi .$$

L'écart avec la taille est le point de l'exercice. À chaque nœud de l'arbre correspond une occurrence de sous-formule : il y en a donc exactement $10$, autant que la taille. Mais deux occurrences peuvent porter la même formule : ici, $p$ apparaît à deux endroits — une fois sous le $\wedge$, une fois sous les deux négations.

On retiendra la distinction, car elle revient partout : la taille compte les occurrences, l'ensemble des sous-formules compte les formules. En mémoire, on peut d'ailleurs partager les sous-formules communes : l'arbre devient un graphe sans circuit, souvent bien plus petit, et c'est le principe des diagrammes de décision binaires. Le chapitre chap:arbres donne le vocabulaire, le chapitre chap:graphes la structure.