Réfuter en une ligne

Exercice · niveau 2 · informatique (MP2I/MPI), chapitre 28 — Déduction naturelle

Énoncé

Peut-on démontrer $p \to q ⊢ q \to p$ ? Répondre sans chercher de preuve.

Corrigé

Non, et il suffit d'une ligne de table de vérité. Prenons la valuation $v$ telle que $v (p) = F$ et $v (q) = V$ :

$p$	$q$	$p \to q$	$q \to p$
$F$	$V$	$V$	$F$

Cette valuation satisfait l'hypothèse et pas la conclusion, donc $p \to q \neq ⊨ q \to p$ . Or la correction du système dit : si $Γ ⊢ C$ alors $Γ ⊨ C$ . Par contraposée, $Γ \neq ⊨ C$ entraîne $Γ \neq ⊢ C$ : aucune dérivation n'existe.

L'économie est le point de l'exercice. Chercher une preuve d'un séquent faux, c'est chercher indéfiniment : la recherche ne s'arrête pas d'elle-même sur un échec. Une seule ligne de table tranche. Les deux outils du chapitre ne s'opposent donc pas, ils se répartissent le travail : la table réfute en une valuation, la preuve établit en quelques nœuds. On commence toujours par chercher un contre-exemple, et l'on ne se met à démontrer qu'après avoir échoué à en trouver.

Trois autres séquents à réfuter de la même façon, chacun en une valuation :

séquent	la valuation qui le tue
$p \lor q ⊢ p$	$v (p) = F$ , $v (q) = V$
$p \to q, q ⊢ p$	$v (p) = F$ , $v (q) = V$
$\neg (p \land q) ⊢ \neg p$	$v (p) = V$ , $v (q) = F$

Le deuxième porte un nom : c'est l'affirmation du conséquent, la faute de raisonnement la plus répandue. « S'il pleut, la rue est mouillée ; la rue est mouillée ; donc il pleut. »

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.