Corrigé Centrale 2026 Informatique MPI — Partie C, III et IV (Q26 à Q34) : Formules réduites, univers arborescents, décidabilité

Sujet officiel du concours Centrale, session 2026, épreuve Informatique MPI. Corrigé rédigé par Ibrahim Alame.

Énoncé

Mêmes notations que Q16 à Q25. Une formule est réduite si elle est engendrée par : $P$ et $\neg P$ pour une variable $P$ ; $(φ \land ψ)$ et $(φ \lor ψ)$ ; $□ φ$ et $◊ φ$ (pour $φ$ , $ψ$ réduites) : pas d'implication, négations devant les variables seulement. Deux formules sont logiquement équivalentes si elles ont les mêmes modèles ; $\neg □ \neg φ$ est équivalente à $◊ φ$ .
Q26. Rappeler les règles de De Morgan.
Q27. Toute formule déontique est équivalente à une formule réduite.
Q28. bool est_reduite(formule *f).


struct univers_s {
  int nb_mondes;
  bool **matrice;
  monde *mondes;
};

typedef struct univers_s univers;

u.matrice[i][j] vaut true si et seulement si le monde $j$ est idéal pour le monde $i$ .
Q29. bool satisfaction2(univers *u, int i, formule *f) pour une formule réduite f.

IV. Un univers arborescent de profondeur $0$ est un monde muni d'une boucle ; de profondeur $n + 1$ , c'est une racine $r$ reliée aux racines $r_{1}, \dots, r_{k}$ d'univers arborescents disjoints de profondeur $n$ . L'algorithme arborescent(U, N, i) crée une copie $r$ de $i$ ; si $N = 0$ il ajoute l'arc $(r, r)$ ; sinon, pour chaque arc $(i, j)$ , il construit $A_{j} =$ arborescent(U, N-1, j), fait l'union des $A_{j}$ , ajoute $r$ et les arcs $(r, r_{j})$ .
Q30. int taille(univers *u, int i, int N) : nombre de mondes de l'univers construit.
Q31. univers *arborescent(univers *u, int i, int N), de racine le monde $0$ .
Q32. $φ$ réduite, $N$ son nombre de symboles $□$ et $◊$ , $A =$ arborescent $(U, N, i)$ de racine $r$ : si $U ⊨_{i} φ$ , alors $A ⊨_{r} φ$ .
Q33. Le résultat subsiste si l'on ne garde pas deux sous-univers identiques lors de la construction.
Q34. La satisfiabilité d'une formule déontique est décidable.

Corrigé

Les fonctions C ont été compilées et exécutées sur l'univers $E$ de Q21 (codé avec $P = X_{0}$ , $Q = X_{1}$ ) ; les énoncés de Q27, Q32 et Q33 ont été testés par un programme Python sur des milliers de formules et d'univers tirés au hasard, sans aucun désaccord.

Q26. Pour toutes formules $φ$ , $ψ$ :

$\neg (φ \land ψ) \equiv \neg φ \lor \neg ψ, \neg (φ \lor ψ) \equiv \neg φ \land \neg ψ .$

Elles restent vraies ici, monde par monde, puisque $\land$ , $\lor$ et $\neg$ s'interprètent en un monde fixé. Elles ont des analogues modaux : $\neg □ φ \equiv ◊ \neg φ$ et $\neg ◊ φ \equiv □ \neg φ$ . En effet, $U ⊨_{i} \neg □ φ$ signifie qu'il est faux que tout successeur $j$ de $i$ satisfasse $φ$ , c'est-à-dire qu'un successeur au moins satisfait $\neg φ$ : c'est $U ⊨_{i} ◊ \neg φ$ . La seconde s'obtient de même (ou de la première et de la remarque de l'énoncé).

Q27. On définit simultanément, par induction sur $φ$ , deux formules $φ^{+}$ et $φ^{-}$ (la forme réduite de $φ$ et celle de $\neg φ$ ) :

$P^{+} = P, (\neg φ)^{+} = φ^{-}, (φ \land ψ)^{+} = φ^{+} \land ψ^{+}, (φ \lor ψ)^{+} = φ^{+} \lor ψ^{+}, (φ \to ψ)^{+} = φ^{-} \lor ψ^{+}, (□ φ)^{+} = □ φ^{+}, (◊ φ)^{+} = ◊ φ^{+}, P^{-} = \neg P, (\neg φ)^{-} = φ^{+}, (φ \land ψ)^{-} = φ^{-} \lor ψ^{-}, (φ \lor ψ)^{-} = φ^{-} \land ψ^{-}, (φ \to ψ)^{-} = φ^{+} \land ψ^{-}, (□ φ)^{-} = ◊ φ^{-}, (◊ φ)^{-} = □ φ^{-} .$

Ces formules sont réduites : par induction, chaque clause n'introduit que $\land$ , $\lor$ , $□$ , $◊$ au-dessus de formules réduites, ou une négation devant une variable.

Elles conviennent : montrons par induction structurelle sur $φ$ la propriété $P (φ)$ : « pour tout univers $U$ et tout monde $i$ , $U ⊨_{i} φ^{+} ⟺ U ⊨_{i} φ$ et $U ⊨_{i} φ^{-} ⟺ U ⊨_{i} \neg φ$ ».

Variable : immédiat.
$\neg φ$ : $(\neg φ)^{+} = φ^{-}$ est vraie en $i$ si et seulement si $\neg φ$ l'est, par $P (φ)$ ; $(\neg φ)^{-} = φ^{+}$ l'est si et seulement si $φ$ , donc $\neg\neg φ$ , l'est.
$\land$ , $\lor$ : la partie $+$ découle de l'hypothèse de récurrence, la partie $-$ de De Morgan (Q26). Pour $\to$ : par définition $φ \to ψ$ se lit $\neg φ \lor ψ$ , et $\neg (φ \to ψ)$ se lit $φ \land \neg ψ$ .
$□ φ$ : $U ⊨_{i} □ φ^{+}$ si et seulement si $U ⊨_{j} φ^{+}$ pour tout successeur $j$ , si et seulement si (hypothèse $P (φ)$ appliquée au monde $j$ ) $U ⊨_{j} φ$ pour tout successeur $j$ , c'est-à-dire $U ⊨_{i} □ φ$ . De même, $◊ φ^{-}$ est vraie en $i$ si et seulement si un successeur satisfait $\neg φ$ , soit (Q26) $U ⊨_{i} \neg □ φ$ . Le cas $◊$ est symétrique.

C'est pour ce cas modal que l'hypothèse de récurrence porte sur tous les mondes. Ainsi $φ$ et $φ^{+}$ ont les mêmes modèles. De plus $∣ φ^{\pm} ∣ ⩽ 2∣ φ ∣$ (chaque nœud en donne au plus un, plus une négation par variable), et le calcul est linéaire : on s'en servira en Q34 et Q39.

Q28. Traduction directe de la définition inductive :


bool est_reduite(formule *f) {
  if (f->op == VARIABLE) return true;
  if (f->op == NON) return f->gauche->op == VARIABLE;
  if (f->op == ET || f->op == OU)
    return est_reduite(f->gauche) && est_reduite(f->droite);
  if (f->op == DOIT || f->op == PEUT) return est_reduite(f->gauche);
  return false;                          /* IMPLIQUE */
}

Une négation n'est acceptée que devant une variable, une implication jamais, et les autres constructeurs demandent des sous-formules réduites : c'est la définition. Un appel par nœud au plus, coût $O (∣ f ∣)$ . Exécuté : $\neg X_{0} \lor □◊ \neg X_{1}$ est réduite ; $□ \neg ◊ X_{1}$ , $\neg\neg X_{1}$ et toute formule contenant une implication ne le sont pas.

100 % gratuit

La suite du corrigé est sur Adloun

Le corrigé rédigé en entier, question par question, et le tuteur pour poser des questions sur ce sujet.

Voir le corrigé complet, gratuitement

Inscription gratuite en 30 secondes (e-mail, nom d'utilisateur, mot de passe, classe ou profil), sans carte bancaire : arrivée directe sur le corrigé.

Toutes les parties de l'épreuve

Corrigé complet gratuit →