La parité : les DEUX formes normales explosent

Exercice · niveau 2 · informatique (MP2I/MPI), chapitre 20 — Logique propositionnelle

Énoncé

On note $π_{n}$ la formule qui vaut $V$ exactement quand un nombre pair de variables parmi $p_{1}, \dots, p_{n}$ vaut $F$ ; elle s'écrit $π_{n} = \neg (\dots \neg (p_{1} \leftrightarrow p_{2}) \leftrightarrow \dots \leftrightarrow p_{n})$ et sa taille est $3 n - 2$ .

Combien $π_{n}$ a-t-elle de modèles ? Combien de termes compte sa fnd complète, de clauses sa fnc complète ?
Montrer qu'aucune fnd de $π_{n}$ ne peut avoir moins de $2^{n - 1}$ termes.
Comparer avec l'exemple $φ_{n}$ du cours.

Corrigé

1. Exactement la moitié des valuations, soit $2^{n - 1}$ . Mesuré :

$n$	taille de $π_{n}$	modèles	termes de la fnd	clauses de la fnc
$2$	$4$	$2$	$2$	$2$
$3$	$7$	$4$	$4$	$4$
$4$	$10$	$8$	$8$	$8$
$5$	$13$	$16$	$16$	$16$
$6$	$16$	$32$	$32$	$32$

Une taille linéaire ( $3 n - 2$ ), et les deux formes normales complètes en $2^{n - 1}$ .

2. La preuve tient en deux lignes, et c'est le cœur de l'exercice.

Soit $T$ un terme (une conjonction de littéraux) qui implique $π_{n}$ , et supposons qu'une variable $p_{k}$ n'y figure pas. Prenons une valuation $v$ satisfaisant $T$ ; en changeant la seule valeur de $p_{k}$ , on obtient $v^{'}$ qui satisfait encore $T$ — puisque $T$ ne parle pas de $p_{k}$ . Mais $v$ et $v^{'}$ diffèrent d'exactement une variable, donc leurs parités diffèrent : l'une des deux ne satisfait pas $π_{n}$ . Contradiction avec $T ⊨ π_{n}$ .

Donc tout terme qui implique $π_{n}$ mentionne les $n$ variables, et un tel terme n'est satisfait que par une valuation. Comme une fnd de $π_{n}$ doit couvrir ses $2^{n - 1}$ modèles, et que chaque terme en couvre exactement un, il en faut au moins $2^{n - 1}$ . C.q.f.d.

Vérification par ordinateur, pour $n = 2, \dots, 5$ : sur tous les termes portant sur un sous-ensemble strict des variables, avec tous les signes possibles, il y en a exactement zéro qui implique $π_{n}$ . La preuve est confirmée à la mesure.

Le même argument, appliqué aux clauses et aux contre-modèles, donne $2^{n - 1}$ clauses au minimum pour la fnc.

3. La comparaison. L'exemple $φ_{n} = (p_{1} \land q_{1}) \lor \dots \lor (p_{n} \land q_{n})$ du cours est de taille linéaire et n'explose que d'un côté : sa fnd est immédiate (elle est déjà écrite), sa fnc demande $2^{n}$ clauses (mesuré : $2, 4, 8, \dots, 128$ pour $n = 1, \dots, 7$ ).

	fnd	fnc
$φ_{n}$ (le cours)	linéaire	$2^{n}$
$π_{n}$ (ici)	$2^{n - 1}$	$2^{n - 1}$

Ce que $π_{n}$ ajoute : il ne suffit pas de « choisir la bonne forme normale ». Il existe des formules courtes dont aucune forme normale n'est courte, et la parité en est l'exemple canonique. La seule issue est de renoncer à l'équivalence pour l'équisatisfiabilité — c'est le problème 20.3.

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.