Preuve directe : Supposer la prémisse vraie et démontrer la conclusion par une suite d'arguments logiques.
- Supposer que la prémisse est vraie
- Développer des arguments logiques
- Arriver à la conclusion
- Conclure que l'implication est vraie
Supposons que n est un entier pair
Par définition, cela signifie qu'il existe un entier k tel que n = 2k
n² = (2k)² = 4k² = 2(2k²)
n² = 2(2k²)
Donc n² est de la forme 2 fois un entier
Puisque n² = 2(2k²) et que 2k² est un entier, n² est pair par définition
On a montré que si n est pair, alors n² est pair
Donc la proposition est démontrée
On a démontré par preuve directe que si n est pair, alors n² est pair.
• Définition : Un entier est pair s'il est de la forme 2k pour un entier k
• Substitution : Remplacer n par son expression en fonction de k
• Structure : Montrer que le résultat est de la forme 2m pour un entier m
Contraposée : L'implication \(P \Rightarrow Q\) est logiquement équivalente à \(\neg Q \Rightarrow \neg P\).
On veut prouver : "Si n² est impair, alors n est impair"
Soit P : "n² est impair" et Q : "n est impair"
On veut prouver P ⇒ Q
La contraposée est : \(\neg Q \Rightarrow \neg P\)
C'est-à-dire : "Si n n'est pas impair, alors n² n'est pas impair"
Ou encore : "Si n est pair, alors n² est pair"
Supposons que n n'est pas impair, c'est-à-dire que n est pair
Donc il existe un entier k tel que n = 2k
n² = (2k)² = 4k² = 2(2k²)
n² = 2(2k²), donc n² est pair
Donc n² n'est pas impair
On a prouvé que si n est pair, alors n² est pair
Donc la contraposée est vraie
Par conséquent, la proposition originale est vraie
On a démontré par contraposée que si n² est impair, alors n est impair.
• Contraposée : \(P \Rightarrow Q\) équivaut à \(\neg Q \Rightarrow \neg P\)
• Équivalence : Prouver la contraposée équivaut à prouver l'original
• Logique : La contraposée est souvent plus facile à prouver que l'original
Disjonction des cas : Diviser la preuve en cas exclusifs couvrant toutes les possibilités.
On veut prouver : "Pour tout entier n, n² + n est pair"
Pour tout entier n, il est soit pair, soit impair
On va examiner les deux cas
Si n est pair, alors n = 2k pour un certain entier k
n² + n = (2k)² + 2k = 4k² + 2k = 2(2k² + k)
Donc n² + n est pair
Si n est impair, alors n = 2k + 1 pour un certain entier k
n² + n = (2k + 1)² + (2k + 1)
= 4k² + 4k + 1 + 2k + 1
= 4k² + 6k + 2
= 2(2k² + 3k + 1)
Donc n² + n est pair
Dans tous les cas (n pair ou impair), n² + n est pair
Donc la proposition est vraie pour tout entier n
On peut vérifier avec quelques exemples :
Pour n = 0 : n² + n = 0 + 0 = 0 (pair)
Pour n = 1 : n² + n = 1 + 1 = 2 (pair)
Pour n = 2 : n² + n = 4 + 2 = 6 (pair)
On a démontré par disjonction des cas que pour tout entier n, n² + n est pair.
• Exhaustivité : Les cas doivent couvrir toutes les possibilités
• Exclusivité : Les cas doivent être mutuellement exclusifs
• Conclusion : La propriété doit être vraie dans chaque cas
Récurrence : Méthode de preuve pour les propriétés portant sur les entiers naturels.
Pour tout entier n ≥ 1, notons P(n) la propriété :
P(n) : 1 + 2 + ... + n = n(n+1)/2
Vérifions P(1) : 1 = 1(1+1)/2 = 1×2/2 = 1 ✓
Donc P(1) est vraie
Supposons que P(k) est vraie pour un certain entier k ≥ 1
Cela signifie : 1 + 2 + ... + k = k(k+1)/2
On veut montrer que P(k+1) est vraie, c'est-à-dire :
1 + 2 + ... + k + (k+1) = (k+1)(k+2)/2
1 + 2 + ... + k + (k+1) = [1 + 2 + ... + k] + (k+1)
= k(k+1)/2 + (k+1) (par hypothèse de récurrence)
= k(k+1)/2 + 2(k+1)/2
= (k(k+1) + 2(k+1))/2
= ((k+1)(k + 2))/2
= (k+1)(k+2)/2
On a prouvé l'initialisation et l'hérédité
Par le principe de récurrence, P(n) est vraie pour tout entier n ≥ 1
On a démontré par récurrence que pour tout entier n ≥ 1, 1 + 2 + ... + n = n(n+1)/2.
• Initialisation : Vérifier la propriété pour la valeur de départ
• Hypothèse : Supposer la propriété vraie au rang k
• Hérédité : Démontrer qu'elle est vraie au rang k+1
Disjonction des cas : Méthode de preuve en examinant toutes les situations possibles.
On veut prouver : "Pour tout entier n, n(n+1) est pair"
Pour tout entier n, il est soit pair, soit impair
On examine les deux cas
Si n est pair, alors n = 2k pour un certain entier k
n(n+1) = 2k(2k+1) = 2k × (2k+1)
Donc n(n+1) est pair (multiple de 2)
Si n est impair, alors n = 2k+1 pour un certain entier k
n(n+1) = (2k+1)((2k+1)+1) = (2k+1)(2k+2)
= (2k+1) × 2(k+1) = 2(2k+1)(k+1)
Donc n(n+1) est pair (multiple de 2)
On peut aussi observer que parmi deux entiers consécutifs n et n+1, l'un est nécessairement pair
Donc leur produit est pair
Dans tous les cas, n(n+1) est pair
Donc la proposition est vraie pour tout entier n
Exemples : n = 0 : 0×1 = 0 (pair), n = 1 : 1×2 = 2 (pair), n = 2 : 2×3 = 6 (pair)
On a démontré par disjonction des cas que pour tout entier n, n(n+1) est pair.
• Alternatives : Parmi deux entiers consécutifs, l'un est pair
• Produit : Si un facteur est pair, le produit est pair
• Complétude : Les cas examinés couvrent toutes les possibilités
- Preuve directe : Supposer la prémisse et arriver à la conclusion
- Contraposée : Supposer la négation de la conclusion et arriver à la négation de la prémisse
- Raisonnement par l'absurde : Supposer la négation de la conclusion et arriver à une contradiction
- Disjonction des cas : Examiner toutes les situations possibles
- Récurrence : Initialisation et hérédité pour les propriétés des entiers
- Une preuve doit être rigoureuse et suivre une logique inattaquable
- Chaque étape d'une preuve doit être justifiée
- La contraposée est logiquement équivalente à l'implication originale
- La récurrence ne s'applique qu'aux propriétés des entiers naturels
