Une identité sur les formules

Exercice · niveau 2 · informatique (MP2I/MPI), chapitre 9 — Ordres bien fondés et induction structurelle

Énoncé

Soit $F$ l'ensemble inductif des formules propositionnelles engendré par les variables et les règles $\neg$ , $\land$ , $\lor$ . Notons $v (φ)$ le nombre d'occurrences de variables et $b (φ)$ le nombre de connecteurs binaires. Montrer que $v (φ) = b (φ) + 1$ .

Corrigé

Les deux fonctions, écrites sur les quatre constructeurs :


type formule = Var of string | Non of formule
             | Et of formule * formule | Ou of formule * formule

let rec occ_var = function
  | Var _ -> 1 | Non f -> occ_var f
  | Et (a,b) | Ou (a,b) -> occ_var a + occ_var b

let rec binaires = function
  | Var _ -> 0 | Non f -> binaires f
  | Et (a,b) | Ou (a,b) -> 1 + binaires a + binaires b

<details class="group my-6 border border-gray-300 rounded-2xl bg-black/[0.03] overflow-hidden transition-all duration-300"><summary style="color:#1e3a8a" class="flex items-center justify-between p-4 cursor-pointer text-xs font-bold select-none"><div class="flex items-center"><i class="fa-solid fa-graduation-cap mr-2"></i>Démonstration</div><span class="transition-transform group-open:rotate-180"><i class="fa-solid fa-chevron-down"></i></span></summary><div style="color:#1d4ed8" class="force-blue p-4 pt-0 border-t border-gray-200 bg-black/[0.02] leading-relaxed font-sans text-xs select-text"> Par induction structurelle sur $φ$ . Quatre constructeurs, donc quatre cas — et le match du code les énumère déjà.

Cas $φ = Var (p)$ (assertion). $v = 1$ , $b = 0$ , et $1 = 0 + 1$ .

Cas $φ = \neg ψ$ . La négation n'est pas binaire et n'apporte aucune variable : $v (φ) = v (ψ)$ et $b (φ) = b (ψ)$ . L'hypothèse d'induction sur $ψ$ donne le résultat, inchangé.

Cas $φ = ψ_{1} \land ψ_{2}$ . Alors $v (φ) = v (ψ_{1}) + v (ψ_{2})$ et $b (φ) = 1 + b (ψ_{1}) + b (ψ_{2})$ . Par hypothèse d'induction sur chacun des deux arguments :

$v (φ) = (b (ψ_{1}) + 1) + (b (ψ_{2}) + 1) = (1 + b (ψ_{1}) + b (ψ_{2})) + 1 = b (φ) + 1.$

Cas $φ = ψ_{1} \lor ψ_{2}$ . Identique au précédent : seul le nom du constructeur change.

Vérification. Identité testée sur $20000$ formules tirées au hasard jusqu'à la profondeur $5$ : vraie sur toutes. Sur l'exemple $(p \lor \neg q) \land \neg (q \land r)$ , on mesure $v = 4$ et $b = 3$ .

Ce que l'identité dit vraiment. Une formule est un arbre binaire déguisé (chapitre chap:arbres) : ses feuilles sont les occurrences de variables, ses nœuds à deux fils les connecteurs binaires. L'identité $v = b + 1$ est donc exactement celle du cours, $f (a) = d (a) + 1$ , transportée sur un autre type inductif. On ne l'a pas redémontrée : on a redémontré la même chose. C'est ce qu'annonçait le chapitre — un principe, et des objets qui changent.

Une conséquence pratique. Elle donne une vérification à coût nul pour tout analyseur syntaxique : si l'arbre construit à partir d'un texte ne satisfait pas $v = b + 1$ , l'analyseur est fautif. Un invariant qui se teste en $Θ (n)$ et qui ne peut pas mentir vaut mieux qu'une relecture.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.