Corrigé X-ENS 2025 Informatique A MP — Partie V (Q21 à Q26) : Formules logiques sur les caractères : clauses et forme normale disjonctive

Sujet officiel du concours X-ENS, session 2025, épreuve Informatique A MP. Corrigé rédigé par Ibrahim Alame.

Énoncé

Les formules sont définies par $φ ::= c_{i} \in V ∣ φ_{1} \land \dots \land φ_{m} ∣ φ_{1} \lor \dots \lor φ_{m}$ , avec $0 \leq i < N$ , $V \subseteq V_{i}$ et $m \geq 0$ ; $⊥$ est la disjonction vide, $⊤$ la conjonction vide. Taille : $∣ c_{i} \in V ∣ = 1 + ∣ V ∣$ , et une conjonction ou une disjonction de $m$ formules a pour taille $1 + m + \sum_{k} ∣ φ_{k} ∣$ .

Un modèle déterministe est un $v = (v_{0}, \dots, v_{N - 1}) \in V = V_{0} \times \dots \times V_{N - 1}$ : $v ⊨ c_{i} \in V$ si $v_{i} \in V$ , une conjonction est satisfaite si toutes ses composantes le sont, une disjonction si l'une d'elles l'est. Un modèle probabiliste est un $d = (d_{0}, \dots, d_{N - 1}) \in D (V_{0}) \times \dots \times D (V_{N - 1})$ , et

$P (d ⊨ φ) = v \in V, v ⊨ φ \sum 0 \leq i < N \prod d_{i} (v_{i}) .$

Une clause est une conjonction de formules atomiques portant sur des caractères deux à deux distincts ; $K = max_{i} ∣ V_{i} ∣$ . Les modèles sont codés par des tableaux de $N$ valeurs ou distributions (mesures de la partie I), et les formules par le type suivant, les listes de valeurs étant sans doublons :


type formule =
  | Feuille of caractere * valeur list
  | Conjonction of formule list
  | Disjonction of formule list

Q21. Montrer que « pour tout $v$ , $v ⊨ φ ⟺ v ⊨ ψ$ » équivaut à « pour tout $d$ , $P (d ⊨ φ) = P (d ⊨ ψ)$ » ; on note alors $φ \equiv ψ$ .
Q22. Complexité, en fonction de $N$ , $K$ et $∣ φ ∣$ , du calcul naïf de $P (d ⊨ φ)$ selon la définition (décrire l'algorithme assez pour justifier l'analyse).
Q23. Pour une clause $φ$ , décrire un calcul de $P (d ⊨ φ)$ de complexité ne dépendant que de $K$ et $∣ φ ∣$ ; correction et complexité.
Q24. Pour deux clauses $φ$ et $ψ$ , montrer que $φ \land ψ$ est équivalente à une clause, notée $φ ⊼ ψ$ .
Q25. Montrer que toute formule est équivalente à une disjonction $φ_{1} \lor \dots \lor φ_{m}$ de clauses ( $m \geq 0$ ).
Q26. Pour une formule quelconque, décrire un calcul de $P (d ⊨ φ)$ de complexité (éventuellement non polynomiale) ne dépendant que de $K$ et $∣ φ ∣$ .

Corrigé

Notons $Mod (φ) = {v \in V ∣ v ⊨ φ}$ et $Q_{d}$ la mesure sur $V$ définie par $Q_{d} ({v}) = \prod_{i} d_{i} (v_{i})$ . C'est une loi de probabilité (la loi produit) : sa masse $\prod_{i} \sum_{w \in V_{i}} d_{i} (w)$ vaut $1$ . Par définition, $P (d ⊨ φ) = Q_{d} (Mod (φ))$ . Dans le code, le type formule masque le constructeur Feuille des arbres : Feuille désigne ici une formule atomique.

Q21. ( $\Rightarrow$ ) Si $φ$ et $ψ$ ont les mêmes modèles déterministes, $Mod (φ) = Mod (ψ)$ , et les deux sommes portent sur le même ensemble avec les mêmes termes : $P (d ⊨ φ) = P (d ⊨ ψ)$ pour tout $d$ .

( $\Leftarrow$ ) Par contraposée, supposons qu'un $v$ satisfasse l'une des formules et pas l'autre, disons $v ⊨ φ$ et $v \neq ⊨ ψ$ . Prenons le modèle probabiliste des diracs $d = (δ_{v_{0}}, \dots, δ_{v_{N - 1}})$ : $\prod_{i} d_{i} (w_{i})$ vaut $1$ si $w = v$ et $0$ sinon. Donc $P (d ⊨ φ) = 1$ (car $v \in Mod (φ)$ ) et $P (d ⊨ ψ) = 0$ (car $v \in / Mod (ψ)$ ) : les probabilités diffèrent. En somme, un modèle déterministe est un modèle probabiliste fait de diracs, ce qui rend la seconde propriété au moins aussi forte que la première.

Q22. L'algorithme naïf énumère tous les $v \in V$ (récursion qui remplit un tableau v case par case, ou compteur « odomètre »), teste $v ⊨ φ$ par une fonction récursive, et, si le test réussit, ajoute $\prod_{i} d_{i} (v_{i})$ au total :


let rec satisfait (v : valeur array) (f : formule) : bool =
  match f with
  | Feuille (i, vs) -> List.mem v.(i) vs
  | Conjonction fs -> List.for_all (satisfait v) fs
  | Disjonction fs -> List.exists (satisfait v) fs

Nombre de modèles : $\prod_{i} ∣ V_{i} ∣ \leq K^{N}$ (avec égalité si tous les $V_{i}$ ont $K$ éléments). Leur énumération récursive visite au plus $(N + 1) \prod_{i} ∣ V_{i} ∣$ appels, en $O (1)$ chacun hors des feuilles.
Test : par récurrence sur $φ$ , satisfait coûte $O (∣ φ ∣)$ : un atome $c_{i} \in V$ coûte $O (1 + ∣ V ∣) = O (∣ c_{i} \in V ∣)$ (List.mem), et une conjonction ou disjonction de $m$ formules coûte $O (1 + m)$ plus la somme des coûts des $φ_{k}$ , soit $O (1 + m + \sum_{k} ∣ φ_{k} ∣) = O (∣ φ ∣)$ .
Produit : $N$ multiplications, chaque $d_{i} (v_{i})$ étant lu par proba_de dans une liste d'au plus $∣ V_{i} ∣ \leq K$ couples : $O (N K)$ (ou $O (N)$ si l'on a d'abord converti les $d_{i}$ en tableaux, pour $O (N K)$ une fois pour toutes).

Total : $O (K^{N} (∣ φ ∣ + N K))$ , borne atteinte quand tous les $V_{i}$ ont $K$ éléments, que chaque $d_{i}$ est uniforme et que $φ$ est satisfaite partout après évaluation complète (par exemple une conjonction d'atomes $c_{0} \in V_{0}$ ). La complexité est exponentielle en $N$ , même pour une formule minuscule : c'est ce que la suite évite. (Programme exécuté : il sert de référence aux tests de Q26.)

Q23. Soit $φ = (c_{i_{1}} \in A_{1}) \land \dots \land (c_{i_{m}} \in A_{m})$ , les $i_{k}$ deux à deux distincts, et $I = {i_{1}, \dots, i_{m}}$ . Alors $Mod (φ) = {v ∣ v_{i_{k}} \in A_{k} pour tout k}$ est le produit cartésien $\prod_{i} B_{i}$ avec $B_{i_{k}} = A_{k}$ et $B_{i} = V_{i}$ pour $i \in / I$ : c'est ici que sert l'hypothèse de caractères distincts. La somme d'un produit sur un produit cartésien se factorise :

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 →