Taille d'une formule

Exercice · OCaml (option informatique), chapitre 17 — Logique propositionnelle

Énoncé

Écrire taille f : le nombre de nœuds (variables et connecteurs) de la formule.

Corrigé

let rec taille f =
  match f with
  | Var _ -> 1
  | Non g -> 1 + taille g
  | Et (g, h) | Ou (g, h) -> 1 + taille g + taille h

Récursion sur l'arbre : une feuille compte 1, un connecteur unaire 1 + sa sous-formule, un binaire 1 + les deux. C'est la fonction taille des arbres du chapitre 3, adaptée.

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.