Déduction : introduction

Résumé

Cette leçon ouvre la deuxième unité du cours, consacrée à la déduction. Elle présente ses cinq leçons et le fil qui les relie, depuis la définition d’un système déductif formel jusqu’aux lois de De Morgan et de distributivité ; elle situe l’unité sur le chemin du cours, entre le langage, déjà construit, et la sémantique et la métathéorie, qui viendront, et annonce ce que celles-ci diront d’elle ; elle justifie le choix d’un système axiomatique, qui se construit en deux étapes (le système de Łukasiewicz, avec trois schémas d’axiomes et le modus ponens, et le système du cours, qui lui ajoute la règle du remplacement de la double négation), et explique pourquoi cette seconde règle est nécessaire et pourquoi on la postule au lieu de la démontrer ; elle montre par une déduction brève combien de travail cache un raisonnement élémentaire ; elle précise ce qui est repris de l’unité précédente, à savoir la lecture unique, l’induction (la récurrence forte sur les entiers naturels et l’induction structurelle) et le dépliage des abréviations, et donne des conseils pour l’étudier.

Objectifs d’apprentissage

Décrire la suite des cinq leçons de l’unité et expliquer quels résultats de chacune la suivante utilise.
Situer la déduction dans le parcours du cours, distinguer la déductibilité $\Gamma \vdash \varphi$ de la conséquence sémantique $\Gamma \models \varphi$ et expliquer ce qu’affirmeront la correction et la complétude.
Expliquer pourquoi le système du cours ajoute à celui de Łukasiewicz une seconde règle primitive, le remplacement de la double négation, à partir de ce que les trois schémas peuvent et ne peuvent pas voir dans une négation conjointe.
Lire une déduction brève par lignes numérotées, distinguer la déduction de formules de la déduction sur les déductions, reconnaître ce que l’unité reprend de la précédente et organiser son étude à partir de l’évaluation d’entrée.

Évaluation d’entrée

Avant de parcourir l’unité, il convient de mesurer le point de départ. Cette évaluation est une autoévaluation : elle n’est pas notée, et son seul but est d’orienter l’étude. Ses treize questions sont de deux sortes. Les trois premières portent sur ce que l’unité tient pour acquis de la précédente : la lecture unique, la récurrence forte et le dépliage des abréviations ; qui en manque une doit revoir, avant de poursuivre, la leçon que la question nomme. Les dix autres portent, dans l’ordre, sur les cinq leçons de cette unité : trois sur la première, trois sur la deuxième, deux sur la troisième, une sur la quatrième et une sur la cinquième. Qui n’a jamais étudié un système déductif ne doit pas s’attendre à les réussir, et cela n’a pas d’importance : chaque réponse, juste ou non, explique le point et nomme la leçon qui le traite. Les mêmes compétences sont mesurées de nouveau à la fin, dans la leçon de synthèse.

Évaluation d’entrée

Avant de commencer l’unité, mesurez votre point de départ. C’est une autoévaluation brève : elle n’est pas notée et son résultat n’est conservé que dans votre navigateur.

Question 1Des unités précédentesLa chaîne $\sigI\sigI\sigO\sigI\sigO\sigO\sigI\sigO\sigI$ est une formule composée, de la forme $\sigI\varphi\psi$ . Quelles sont ses composantes $\varphi$ et $\psi$ ?
$\varphi = \sigI\sigO\sigI\sigO\sigO\sigI$ et $\psi = \sigO\sigI$ .
$\varphi = \sigI\sigO\sigI$ et $\psi = \sigO\sigO\sigI\sigO\sigI$ .
Elle admet deux décompositions, selon l’endroit où l’on coupe la chaîne après le disque initial.
$\varphi$ est toute la chaîne qui suit le disque initial, et $\psi$ est la chaîne vide.
Question 2Des unités précédentesDans une démonstration par récurrence forte que tout entier naturel $n$ vérifie une propriété $P(n)$ , que peut-on supposer pour démontrer $P(n)$ ?
Que $P(m)$ est vraie pour tout entier naturel $m$ inférieur à $n$ .
Seulement que $P(n - 1)$ est vraie.
Que $P(m)$ est vraie pour tout entier naturel $m$ inférieur ou égal à $n$ .
Rien, tant qu’on n’a pas démontré séparément $P(1)$ et $P(2)$ .
Question 3Des unités précédentesAvec les abréviations officielles du cours, quelle formule $(\varphi \rightarrow \psi)$ désigne-t-elle, écrite avec la négation conjointe et la négation ?
$\neg(\neg\varphi \downarrow \psi)$ .
$(\neg\varphi \downarrow \psi)$ .
$\neg(\varphi \downarrow \neg\psi)$ .
Aucune en particulier : cela dépend de la façon dont on décide de la lire.
Question 4Le schéma A1 est $(\varphi \rightarrow (\psi \rightarrow \varphi))$ . La formule $(v_{1} \rightarrow (v_{2} \rightarrow v_{3}))$ est-elle une instance de A1 ?
Non : il faudrait substituer la même formule à la première et à la dernière occurrence de $\varphi$ , et ici ce sont $v_{1}$ et $v_{3}$ .
Oui, avec $\varphi := v_{1}$ et $\psi := v_{2}$ .
Oui, car toute implication dont le conséquent est une autre implication est une instance de A1.
Non, car les instances d’un schéma ne peuvent pas contenir de variables.
Question 5Une déduction contient déjà les lignes $\psi$ et $(\varphi \rightarrow \psi)$ , où $\varphi$ et $\psi$ sont des formules distinctes. Quelle formule le modus ponens appliqué à ces deux lignes permet-il d’écrire ?
Aucune : le modus ponens exige l’antécédent $\varphi$ , et ce que l’on a, c’est le conséquent.
$\varphi$ .
$(\psi \rightarrow \varphi)$ .
$\neg\varphi$ .
Question 6On sait que $\{\varphi\} \vdash \psi$ , c’est-à-dire qu’il existe une déduction de $\psi$ dont l’unique prémisse est $\varphi$ . Qu’affirme alors le théorème de déduction ?
Que $\vdash (\varphi \rightarrow \psi)$ : l’implication est un théorème.
Que $\vdash \psi$ : on peut supprimer la prémisse sans plus.
Que $\vdash (\psi \rightarrow \varphi)$ .
Que $\{\psi\} \vdash \varphi$ .
Question 7Que déduit-on, sans autres prémisses, de l’ensemble $\{(\varphi \rightarrow \psi), (\psi \rightarrow \chi)\}$ ?
$(\varphi \rightarrow \chi)$ .
$\chi$ , en appliquant deux fois le modus ponens.
$(\chi \rightarrow \varphi)$ .
$(\varphi \wedge \chi)$ .
Question 8La règle du remplacement de la double négation (RDN) change, dans une ligne, une seule occurrence d’une sous-formule, et agit sur la chaîne de la langue de base. Combien d’occurrences de la sous-formule $\neg v_{1}$ contient la chaîne que désigne $(v_{1} \rightarrow v_{2})$ ?
Deux.
Une, celle qui correspond à l’antécédent.
Aucune : la formule ne contient pas de négations.
Quatre.
Question 9Quelle formule obtient-on de $(\neg\varphi \rightarrow \psi)$ par contraposition, sans ajouter de doubles négations ?
$(\neg\psi \rightarrow \varphi)$ .
$(\psi \rightarrow \neg\varphi)$ .
$(\varphi \rightarrow \neg\psi)$ .
$(\neg\psi \rightarrow \neg\varphi)$ .
Question 10 $(\varphi \vee \psi)$ et $(\neg\varphi \rightarrow \psi)$ désignent-elles la même formule ?
Non : la première est $\neg(\varphi \downarrow \psi)$ et la seconde, $\neg(\neg\neg\varphi \downarrow \psi)$ ; ce sont des formules distinctes, équivalentes par déduction.
Oui, par la définition de l’implication.
Oui, car toutes deux se lisent « $\varphi$ ou $\psi$ ».
Non, et aucune ne se déduit de l’autre.
Question 11On sait que $\varphi \dashv\vdash \varphi'$ , c’est-à-dire que chacune se déduit de l’autre. Qu’est-ce qui justifie qu’on ait aussi $\neg\varphi \dashv\vdash \neg\varphi'$ ?
Un théorème, le remplacement des équivalents, que l’on démontre avec le théorème de déduction et la contraposition.
Aucune justification particulière : il suffit de « nier les deux membres » de l’équivalence.
La définition de la négation, car $\neg\varphi$ est $(\varphi \downarrow \varphi)$ .
Rien, car ce n’est pas vrai : la négation peut séparer des formules équivalentes.
Question 12À partir de l’ensemble de prémisses $\Gamma \cup \{\neg\varphi\}$ on déduit une formule $\chi$ et sa négation $\neg\chi$ . Que peut-on conclure ?
Que $\Gamma \vdash \varphi$ .
Que $\Gamma \vdash \neg\varphi$ .
Que de $\Gamma$ se déduit n’importe quelle formule.
Rien : une déduction qui aboutit à une contradiction ne prouve rien.
Question 13À quelle formule la négation d’une implication, $\neg(\varphi \rightarrow \psi)$ , est-elle équivalente ?
À $(\varphi \wedge \neg\psi)$ .
À $(\neg\varphi \rightarrow \neg\psi)$ .
À $(\varphi \rightarrow \neg\psi)$ .
À $(\neg\varphi \wedge \psi)$ .