Preuves par induction : Règles généralisées de De Morgan et Distribution
RÉSUMÉ
Dans ce cours, nous abordons le sujet des preuves par induction en mathématiques et en logique propositionnelle. Nous expliquons les deux types de preuves existants : les preuves internes ou déductives, qui reposent sur les règles de la logique, et les preuves externes ou métamathématiques, qui sont nécessaires pour prouver des affirmations concernant la logique elle-même. Nous introduisons l’induction mathématique comme méthode de démonstration permettant de prouver que certaines affirmations sont valables pour tous les nombres naturels. Nous présentons un exemple avec la démonstration correspondante et expliquons les formes généralisées des lois de De Morgan et des lois distributives en logique propositionnelle, ainsi que leurs démonstrations par induction respectives. Ce cours est d’une grande importance pour comprendre les fondements des mathématiques et de la logique, et pour les appliquer dans divers domaines du savoir.
OBJECTIFS D’APPRENTISSAGE :
À la fin de ce cours, l’étudiant sera capable de :
- Reconnaître les deux types de preuves à distinguer : preuves internes ou déductives et preuves externes ou métamathématiques.
- Appliquer l’induction mathématique pour faire des démonstrations sur les nombres naturels et en logique propositionnelle.
- Utiliser les notations de conjonctions et de disjonctions pour écrire des expressions de la logique propositionnelle.
- Comprendre la forme généralisée des lois de De Morgan et des lois distributives en logique propositionnelle.
- Comprendre le concept d’hypothèse d’induction et son rôle dans la démonstration par induction.
INDEX
PREUVES INTERNES ET EXTERNES
PREUVES PAR INDUCTION MATHÉMATIQUE
PREUVES PAR INDUCTION EN LOGIQUE PROPOSITIONNELLE
FORME GÉNÉRALISÉE DES LOIS DE DE MORGAN
FORME GÉNÉRALISÉE DES LOIS DISTRIBUTIVES
Preuves internes et externes
Il existe deux types de preuves qu’il faut distinguer. Jusqu’à présent, nous avons vu de nombreux exemples de preuves formelles. Ce type de preuves émerge des règles de la logique. De telles preuves sont dites avoir lieu « à l’intérieur de la logique », et nous nous y référons donc également sous le nom de « preuves internes » ou déductives. Ce type de preuves formelles a une portée limitée, car elles ne servent qu’à prouver des affirmations qui peuvent être écrites dans le langage de la logique. Cependant, nous pourrions vouloir prouver certaines choses concernant la logique elle-même. Nous pourrions vouloir prouver que toutes les affirmations de la logique propositionnelle satisfont à une certaine propriété. De telles affirmations qui se réfèrent à la logique elle-même ne peuvent être établies ni prouvées à l’intérieur de la logique. Pour prouver de telles affirmations, nous utilisons une preuve externe. Les preuves externes sont parfois appelées « métamathématiques », et nous avons déjà rencontré ce type de choses, comme lorsque nous avons vu le (méta)théorème de déduction. C’est ici que nous contextualisons les preuves inductives.
Preuves par Induction Mathématique
L’induction mathématique est une méthode de démonstration qui nous permet de prouver que certaines choses sont valables pour tous les nombres naturels.
EXEMPLE :
Il est possible de prouver que tout nombre de la forme 11^n - 4^n, où n est un nombre naturel quelconque, est toujours divisible par 7.
DÉMONSTRATION : Si nous observons ce qui se passe avec n=1, nous verrons que :
11^1 - 4^1 = 7
ce qui, évidemment, est divisible par 7.
Supposons maintenant que 11^n - 4^n soit divisible pour un n=k. À partir de cela, nous prouverons en conséquence que cette expression sera également vraie pour n=k+1. Nous pouvons le faire de la manière suivante :
Par conséquent, si 11^k - 4^k est divisible par 7, en conséquence 11 ( 11^{k} - 4^{k} ) + 7\cdot 4^{k} le sera aussi, ce qui revient à dire que 11^{k+1} - 4^{k+1} est divisible par 7. De là, nous avons que si 11^k - 4^k est divisible pour k=1, alors il le sera pour k=2, k=3, k=4,\cdots et ainsi de suite, et donc divisible pour tout n\in\mathbb{N}. Lorsque cela se produit, on dit que l’induction est complète. ■
Preuves par Induction en Logique Propositionnelle
Pour les preuves par induction que nous allons réaliser ci-dessous, il sera d’abord nécessaire d’introduire la convention de notation suivante
NOTATION : Soient F_1,\cdots, F_n un ensemble fini d’expressions quelconques de la logique propositionnelle. Les conjonctions et les disjonctions de ces expressions sont introduites par :
\displaystyle \bigwedge_{i=1}^n F_i := F_1\wedge \cdots \wedge F_n
\displaystyle \bigvee_{i=1}^n F_i := F_1\vee \cdots \vee F_n
Avec cela, nous pourrons maintenant traiter les deux formes généralisées suivantes.
Forme Généralisée des Lois de De Morgan
Étant donné un ensemble fini d’expressions de la logique propositionnelle F_1,\cdots, F_n, les deux propriétés suivantes seront toujours vérifiées :
\displaystyle\neg\left(\bigwedge_{i=1}^n F_i \right) \equiv \left( \bigvee_{i=1}^n \neg F_i \right)
\displaystyle\neg\left(\bigvee_{i=1}^n F_i \right) \equiv \left( \bigwedge_{i=1}^n \neg F_i \right)
DÉMONSTRATION : Nous prouverons d’abord par induction sur n que \neg\left(\bigwedge_{i=1}^n F_i \right) \equiv \left( \bigvee_{i=1}^n \neg F_i \right)
Nous devons d’abord examiner ce qui se passe avec le cas initial n=1. Dans ce cas, il est clair que \neg F_1 \equiv \neg\left(\bigwedge_{i=1}^1F_i\right)\equiv \left(\bigvee_{i=1}^n \neg F_i \right) \equiv\neg F_1
Supposons maintenant que la propriété fonctionne pour un certain n=k; c’est-à-dire qu’étant donné une collection finie d’expressions F_1, F_2, \cdots, F_k il est vérifié que :
\displaystyle \neg\left(\bigwedge_{i=1}^k F_i\right) \equiv \left(\bigvee_{i=1}^k \neg F_i\right)
Alors nous prouverons en conséquence qu’il est valable
\displaystyle \neg\left(\bigwedge_{i=1}^{k+1} F_i\right) \equiv \left(\bigvee_{i=1}^{k+1} \neg F_i\right)
En utilisant la définition de la conjonction, nous avons que :
\displaystyle \neg\left(\bigwedge_{i=1}^{k+1} F_i\right) := \neg\left[\left(\bigwedge_{i=1}^{k} F_i\right) \wedge F_{k+1}\right]
Sur cette expression, nous pouvons appliquer les lois de De Morgan (la loi usuelle sur deux termes) pour obtenir :
\displaystyle \neg\left(\bigwedge_{i=1}^{k+1} F_i\right)\equiv \left[\neg\left(\bigwedge_{i=1}^{k} F_i\right) \vee \neg F_{k+1}\right]
Maintenant, si nous appliquons l’hypothèse d’induction, nous obtiendrons :
\displaystyle \neg\left(\bigwedge_{i=1}^{k+1} F_i\right)\equiv \left[ \left(\bigvee_{i=1}^k \neg F_i\right) \vee \neg F_{k+1}\right] := \left(\bigvee_{i=1}^{k+1}\neg F_i \right)
Et pour cette raison, l’induction est complète et la propriété est valable pour tout n en général. La deuxième relation peut être obtenue de manière complètement analogue, je la laisse donc comme exercice au lecteur, haha!
Forme Généralisée des Lois Distributives
De manière similaire aux lois de De Morgan, les lois de distribution peuvent être généralisées de la manière suivante. Soient \{F_1, \cdots, F_n\} et \{G_1,\cdots, G_m\} deux ensembles finis d’expressions quelconques, alors les équivalences suivantes sont valables :
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^m G_j \right) \right] \equiv \left[\bigwedge_{i=1}^n\left(\bigwedge_{j=1}^m(F_i\vee G_j) \right) \right]
\displaystyle \left[ \left(\bigvee_{i=1}^n F_i \right) \wedge \left(\bigvee_{j=1}^m G_j \right) \right] \equiv \left[\bigvee_{i=1}^n\left(\bigvee_{j=1}^m(F_i\wedge G_j) \right) \right]
DÉMONSTRATION : Pour construire cette démonstration, nous devons faire une double induction sur n et m. Ensuite, je ferai d’abord l’induction sur n puis sur m pour l’expression \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^m G_j \right) \right] \equiv \left[\bigwedge_{i=1}^n\left(\bigwedge_{j=1}^m(F_i\vee G_j) \right) \right]
Si nous prenons m=1, alors cette expression se réduit à :
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^1 G_j \right) \right] \equiv \left[\bigwedge_{i=1}^n\left(\bigwedge_{j=1}^1(F_i\vee G_j) \right) \right].
Ce qui est équivalent à dire :
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee G_1 \right] \equiv \left[\bigwedge_{i=1}^n\left( F_i\vee G_1 \right) \right].
Nous allons maintenant prouver cette expression par induction sur n.
Si nous prenons n=1, alors l’expression se réduit à :
F_1 \vee G_1 \equiv F_1 \vee G_1.
Ce qui, nous le savons déjà, est vrai. Supposons maintenant qu’elle soit vraie pour un n=k quelconque; c’est-à-dire que l’hypothèse d’induction sera :
\displaystyle \left[ \left(\bigwedge_{i=1}^k F_i \right) \vee G_1 \right] \equiv \left[\bigwedge_{i=1}^k\left( F_i\vee G_1 \right) \right].
Ensuite, nous montrerons en conséquence qu’elle est vraie pour un n=k+1.
Par la définition de la conjonction, on a :
\displaystyle \left[\left(\bigwedge_{i=1}^{k+1}F_i \right) \vee G_1 \right] := \left[\left(\left(\bigwedge_{i=1}^{k}F_i \right)\wedge F_{k+1} \right) \vee G_1 \right]
Maintenant, en utilisant la \vee-distribution, on aura :
\displaystyle \left[\left(\bigwedge_{i=1}^{k+1}F_i \right) \vee G_1 \right] \equiv \left[\left(\left(\bigwedge_{i=1}^{k}F_i \right)\vee G_{1} \right) \wedge \left(F_{k+1} \vee G_1 \right) \right]
Et juste à ce stade, nous pouvons utiliser l’hypothèse d’induction pour obtenir :
\displaystyle \left[\left(\bigwedge_{i=1}^{k+1}F_i \right) \vee G_1 \right] \equiv \left[\left(\bigwedge_{i=1}^k\left( F_i\vee G_1 \right) \right) \wedge \left(F_{k+1} \vee G_1 \right) \right] := \left[\bigwedge_{i=1}^{k+1}(F_{i}\vee G_1 \right]
Par conséquent, nous avons prouvé par induction que pour tout n\in\mathbb{N} il est vrai que :
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right)\vee G_1\right] \equiv \left[\bigwedge_{i=1}^n(F_i\vee G_1)\right]
En complétant l’induction sur n, nous avons confirmé que cela fonctionne pour le cas initial où m=1, maintenant il ne reste plus qu’à compléter l’induction sur m. Pour ce faire, établissons l’hypothèse d’induction pour un m=l, c’est-à-dire qu’elle fonctionne pour :
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^l G_j \right) \right] \equiv \left[\bigwedge_{i=1}^n\left(\bigwedge_{j=1}^l(F_i\vee G_j) \right) \right]
et à partir de cela, nous prouverons qu’elle fonctionne aussi pour m=l+1.
En partant, comme toujours, de la définition de la conjonction, on a :
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{l+1} G_j \right) \right] := \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\left(\bigwedge_{j=1}^{l} G_j \right) \wedge G_{l+1}\right) \right]
Maintenant, en utilisant la \vee-distribution, on aura :
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{l+1} G_j \right) \right] \equiv \left[ \left( \left(\bigwedge_{i=1}^n F_i \right) \vee \left( \bigwedge_{j=1}^l G_j \right) \right) \wedge \left( \left( \bigwedge_{i=1}^n F_i \right)\vee G_{l+1} \right) \right]
Par conséquent, en utilisant l’hypothèse d’induction, vous pourrez écrire :
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{l+1} G_j \right) \right] \equiv \left[ \bigwedge_{i=1}^n\left(\bigwedge_{j=1}^l(F_i\vee G_j) \right) \wedge \left( \left( \bigwedge_{i=1}^n F_i \right)\vee G_{l+1} \right) \right]
Et maintenant, en prenant le résultat de l’induction sur n
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{l+1} G_j \right) \right] \equiv \left[ \bigwedge_{i=1}^n\left(\bigwedge_{j=1}^l(F_i\vee G_j) \right) \wedge \left( \bigwedge_{i=1}^n (F_i \vee G_{l+1} )\right) \right]
Ce qui, finalement, par la définition de la conjonction, nous donne :
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{l+1} G_j \right) \right] \equiv \left[ \bigwedge_{i=1}^n\left(\bigwedge_{j=1}^{l+1}(F_i\vee G_j) \right) \right]
Et par conséquent, l’induction sur m est complète et l’expression :
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{m} G_j \right) \right] \equiv \left[ \bigwedge_{i=1}^n\left(\bigwedge_{j=1}^{m}(F_i\vee G_j) \right) \right]
est valable pour tout n,m\in\mathbb{N}.
Ce parcours à travers les preuves par induction a montré comment des techniques rigoureuses de démonstration mathématique peuvent être appliquées non seulement dans le domaine des nombres naturels, mais aussi en logique propositionnelle. Grâce à l’induction, nous avons pu établir la validité des formes généralisées des lois de De Morgan et des lois distributives, renforçant ainsi la compréhension des fondements logiques qui sous-tendent diverses disciplines mathématiques. Cette approche est essentielle non seulement pour développer des compétences en raisonnement abstrait, mais aussi comme un outil puissant pour aborder des problèmes complexes en mathématiques et au-delà.