Mathematical Statements, Logic and Proofs

# Mathematical Statements, Logic and Proofs ## Objectifs et prérequis Ce chapitre vise à développer chez l'élève une compréhension rigoureuse des fondements logiques des mathématiques, essentielle pour la construction et l'analyse de preuves. À la fin de ce chapitre, l'élève sera capable de : - Identifier et formuler des propositions mathématiques correctement. - Déterminer la valeur de vérité d'une proposition et de sa négation. - Construire et analyser des propositions composées (conjonctions, disjonctions, conditionnelles). - Comprendre et utiliser la réciproque d'une conditionnelle. - Réaliser des preuves directes, par contre-exemple, par contradiction et par récurrence. - Appliquer ces méthodes à des problèmes concrets en algèbre, théorie des nombres et géométrie. **Prérequis** : Maîtrise des opérations sur les ensembles, des propriétés des nombres entiers, des notions de fonction et de relation, ainsi qu'une familiarité avec la notation mathématique de base. --- ## I. Basic concepts in logic La logique formelle fournit le langage et les règles permettant de raisonner de manière valide en mathématiques. Elle distingue les raisonnements corrects des raisonnements fallacieux, indépendamment du contenu sémantique des propositions. > **Définition** : Une **proposition** est une phrase déclarative qui est soit vraie soit fausse, mais pas les deux en même temps. ### Exemples : - "2 + 2 = 4" → vraie (V) - "Le ciel est vert" → fausse (F) - "x > 5" → pas une proposition (dépend de x) : c'est une **ouverte** - "Ferme la porte" → pas une proposition (impératif) - "Cette phrase est fausse" → paradoxe (non admise en logique classique) ### Propriétés : - Toute proposition a une **valeur de vérité** : V (vrai) ou F (faux). - La logique classique admet le **principe du tiers exclu** : une proposition est soit V soit F. - Le **principe de non-contradiction** : aucune proposition ne peut être à la fois V et F. ### Exercice 1 : Identifier les propositions Parmi les phrases suivantes, lesquelles sont des propositions ? 1. La racine carrée de 9 est 3. 2. Quel est ton nom ? 3. Tous les nombres premiers sont impairs. 4. x² ≥ 0 pour tout réel x. 5. Si il pleut, alors le sol est mouillé. 6. Peut-être que demain il fera beau. **Corrigé** : 1. Proposition (V) 2. Pas une proposition (question) 3. Proposition (F, car 2 est premier et pair) 4. Pas une proposition (contient une variable libre x) → ouverte 5. Proposition (conditionnelle, valeur de vérité dépend du contexte) 6. Pas une proposition (incertitude modale) --- ## II. Propositions Une proposition est l'unité de base de la logique propositionnelle. Elle est généralement notée par une lettre majuscule (P, Q, R, ...). > **Notation** : On note V la valeur de vérité "vrai" et F la valeur de vérité "faux". ### Exemples de propositions : - P : "Le nombre 7 est premier." → V - Q : "Le nombre 15 est pair." → F - R : "Le triangle ABC est équilatéral." → dépend de ABC (peut être V ou F) ### Exercice 2 : Attribution de valeurs de vérité Soient les propositions : - P : "12 est divisible par 3." - Q : "12 est divisible par 5." - R : "12 est un nombre carré parfait." Déterminer la valeur de vérité de chacune. **Corrigé** : - P : 12 ÷ 3 = 4 → entier → V - Q : 12 ÷ 5 = 2,4 → pas entier → F - R : √12 ≈ 3,46 → pas entier → F --- ## III. Truth value of a statement and its negation La négation d'une proposition P, notée ¬P (ou parfois ~P ou ¬P), est vraie lorsque P est fausse, et fausse lorsque P est vraie. > **Règle de négation** : > $$ > \begin{array}{c|c} > P & \neg P \\ > \hline > V & F \\ > F & V \\ > \end{array} > $$ ### Exemples : - P : "Tous les entiers pairs sont divisibles par 4." → F (exemple : 2) → ¬P : "Il existe un entier pair qui n'est pas divisible par 4." → V - Q : "√2 est un nombre rationnel." → F → ¬Q : "√2 est un nombre irrationnel." → V - R : "Le vide est un sous-ensemble de tout ensemble." → V → ¬R : "Le vide n'est pas un sous-ensemble de tout ensemble." → F ### Exercice 3 : Négation de propositions Écrire la négation de chacune des propositions suivantes : 1. Tous les étudiants de Lower Sixth aiment les mathématiques. 2. Il existe un nombre premier pair supérieur à 2. 3. Pour tout réel x, x² ≥ 0. 4. La somme de deux nombres impairs est paire. **Corrigé** : 1. Il existe au moins un étudiant de Lower Sixth qui n'aime pas les mathématiques. 2. Pour tout nombre premier pair, il est inférieur ou égal à 2. (Équivalent : Il n'existe pas de nombre premier pair supérieur à 2.) 3. Il existe un réel x tel que x² < 0. 4. Il existe deux nombres impairs dont la somme est impaire. > **À retenir** : La négation transforme un "tout" en "il existe un" et vice versa, et nie le prédicat. --- ## IV. Composite statements (Conjunctions) Une conjonction de deux propositions P et Q, notée P ∧ Q (lu "P et Q"), est vraie seulement lorsque P et Q sont toutes deux vraies. > **Table de vérité de la conjonction** : > $$ > \begin{array}{c|c|c} > P & Q & P \land Q \\ > \hline > V & V & V \\ > V & F & F \\ > F & V & F \\ > F & F & F \\ > \end{array} > $$ ### Exemples : - P : "7 est premier." → V - Q : "9 est pair." → F → P ∧ Q : "7 est premier et 9 est pair." → F - R : "Le carré d'un nombre réel est non négatif." → V - S : "La somme des angles d'un triangle est 180°." → V → R ∧ S : V ∧ V = V ### Exercice 4 : Évaluation de conjonctions Soient : - P : "15 est divisible par 3." - Q : "15 est divisible par 5." - R : "15 est un nombre carré." Déterminer la valeur de vérité de : 1. P ∧ Q 2. P ∧ R 3. Q ∧ R 4. ¬P ∧ Q **Corrigé** : - P : 15 ÷ 3 = 5 → V - Q : 15 ÷ 5 = 3 → V - R : √15 ≈ 3,87 → pas entier → F 1. P ∧ Q = V ∧ V = V 2. P ∧ R = V ∧ F = F 3. Q ∧ R = V ∧ F = F 4. ¬P ∧ Q = F ∧ V = F > **À retenir** : La conjonction est vraie seulement si les deux propositions sont vraies ; elle est fausse dès qu'au moins une est fausse. --- ## V. Composite statements (Disjunctions) Une disjonction de deux propositions P et Q, notée P ∨ Q (lu "P ou Q"), est vraie lorsque au moins une des deux propositions est vraie. C'est une disjonction **inclusive** (comme en mathématiques, sauf indication contraire). > **Table de vérité de la disjonction** : > $$ > \begin{array}{c|c|c} > P & Q & P \lor Q \\ > \hline > V & V & V \\ > V & F & V \\ > F & V & V \\ > F & F & F \\ > \end{array} > $$ ### Exemples : - P : "10 est divisible par 2." → V - Q : "10 est divisible par 3." → F → P ∨ Q : "10 est divisible par 2 ou par 3." → V - R : "Le nombre 1 est premier." → F - S : "Le nombre 1 est pair." → F → R ∨ S : F ∨ F = F ### Exercice 5 : Évaluation de disjonctions Soient : - P : "Le nombre 25 est un carré parfait." - Q : "Le nombre 25 est un cube parfait." - R : "Le nombre 25 est divisible par 5." Déterminer la valeur de vérité de : 1. P ∨ Q 2. P ∨ R 3. Q ∨ R 4. ¬P ∨ Q **Corrigé** : - P : √25 = 5 → entier → V - Q : ³√25 ≈ 2,92 → pas entier → F - R : 25 ÷ 5 = 5 → entier → V 1. P ∨ Q = V ∨ F = V 2. P ∨ R = V ∨ V = V 3. Q ∨ R = F ∨ V = V 4. ¬P ∨ Q = F ∨ F = F > **À retenir** : La disjonction est fausse seulement lorsque les deux propositions sont fausses ; elle est vraie dès qu'au moins une est vraie. --- ## VI. The converse of a Conditional statement Une conditionnelle est une proposition de la forme "Si P alors Q", notée P → Q (lu "P implique Q"). Elle est fausse seulement lorsque P est vraie et Q est fausse. > **Table de vérité de la conditionnelle** : > $$ > \begin{array}{c|c|c} > P & Q & P \rightarrow Q \\ > \hline > V & V & V \\ > V & F & F \\ > F & V & V \\ > F & F & V \\ > \end{array} > $$ La **réciproque** de P → Q est la proposition Q → P. > **Important** : La conditionnelle et sa réciproque ne sont pas logiquement équivalentes. ### Exemples : - P → Q : "Si un nombre est divisible par 4, alors il est pair." → V → Réciproque Q → P : "Si un nombre est pair, alors il est divisible par 4." → F (exemple : 2) - R → S : "Si un triangle est équilatéral, alors il est isocèle." → V → Réciproque S → R : "Si un triangle est isocèle, alors il est équilatéral." → F (exemple : triangle rectangle isocèle) ### Exercice 6 : Conditionnelle et réciproque Soient les propositions : - P : "x est un multiple de 6." - Q : "x est un multiple de 2." - R : "x est un multiple de 3." 1. Écrire la conditionnelle P → Q et déterminer sa valeur de vérité pour tout entier x. 2. Écrire la réciproque Q → P et déterminer sa valeur de vérité. 3. Faire de même pour P → R et sa réciproque R → P. **Corrigé** : 1. P → Q : "Si x est multiple de 6, alors x est multiple de 2." → Vrai : tout multiple de 6 est multiple de 2 (6k = 2×3k). 2. Q → P : "Si x est multiple de 2, alors x est multiple de 6." → Faux : contre-exemple x = 2 (multiple de 2 mais pas de 6). 3. P → R : "Si x est multiple de 6, alors x est multiple de 3." → Vrai : 6k = 3×2k. 4. R → P : "Si x est multiple de 3, alors x est multiple de 6." → Faux : contre-exemple x = 3. > **À retenir** : La réciproque d'une conditionnelle vraie n'est pas nécessairement vraie ; il faut la vérifier séparément. --- ## VII. Direct proofs and proofs by counter examples Une **preuve directe** consiste à partir d'hypothèses connues (axiomes, définitions, théorèmes préalablement démontrés) et à appliquer des raisonnements logiques valides pour arriver à la conclusion souhaitée. Une **preuve par contre-exemple** sert à montrer qu'une affirmation universelle ("pour tout x, P(x)") est fausse en exhibant un seul élément pour lequel P(x) est faux. > **À retenir** : Pour réfuter une affirmation du type "∀x, P(x)", il suffit de trouver un contre-exemple : un x tel que ¬P(x). ### Exemple de preuve directe : **Théorème** : La somme de deux nombres pairs est paire. **Preuve** : Soient a et b deux nombres pairs. Alors, par définition, il existe des entiers k et m tels que : a = 2k et b = 2m. Leur somme est : a + b = 2k + 2m = 2(k + m). Puisque k + m est un entier, a + b est de la forme 2 × entier, donc pair. ∎ ### Exemple de preuve par contre-exemple : **Affirmation** : "Tout nombre premier est impair." **Preuve par contre-exemple** : Considérons le nombre 2. 2 est premier (ses seuls diviseurs sont 1 et 2). Mais 2 est pair. Donc, 2 est un nombre premier qui n'est pas impair. L'affirmation est donc fausse. ∎ ### Exercice 7 : Preuves directes et contre-exemples 1. Prouver directement que le produit de deux nombres impairs est impair. 2. Montrer par contre-exemple que l'affirmation suivante est fausse : "Pour tout entier n, n² + n + 1 est premier." 3. Prouver directement que si n est un entier pair, alors n² est divisible par 4. **Corrigé** : 1. Soient a et b deux nombres impairs. Alors ∃ k, m ∈ ℤ tels que a = 2k + 1, b = 2m + 1. Produit : ab = (2k+1)(2m+1) = 4km + 2k + 2m + 1 = 2(2km + k + m) + 1. Donc ab est de la forme 2 × entier + 1 → impair. ∎ 2. Affirmation : ∀n ∈ ℕ, n² + n + 1 est premier. Essayer n = 1 : 1 + 1 + 1 = 3 → premier n = 2 : 4 + 2 + 1 = 7 → premier n = 3 : 9 + 3 + 1 = 13 → premier n = 4 : 16 + 4 + 1 = 21 = 3 × 7 → pas premier Donc, pour n = 4, l'expression n'est pas premier → contre-exemple. L'affirmation est fausse. ∎ 3. Soit n un entier pair. Alors ∃ k ∈ ℤ tel que n = 2k. Alors n² = (2k)² = 4k². Puisque k² est un entier, n² = 4 × entier → divisible par 4. ∎ --- ## VIII. Proof by contradiction Une **preuve par contradiction** (ou *reductio ad absurdum*) consiste à supposer la négation de ce qu'on veut prouver, puis à montrer que cette supposition mène à une contradiction (une proposition fausse qui découle de prémisses vraies). Comme les prémisses sont vraies, la supposition doit être fausse, donc l'énoncé original est vrai. > **À retenir** : Pour prouver P par contradiction, on suppose ¬P et on déduit une contradiction (F). Donc P doit être vrai. ### Exemple classique : **Théorème** : √2 est irrationnel. **Preuve par contradiction** : Supposons que √2 soit rationnel. Alors, il existe deux entiers premiers entre eux p et q (q ≠ 0) tels que : √2 = p/q. En élevant au carré : 2 = p²/q² → p² = 2q². Donc p² est pair → p est pair (si p était impair, p² serait impair). Alors, ∃ k ∈ ℤ tel que p = 2k. Substituons : (2k)² = 2q² → 4k² = 2q² → 2k² = q². Donc q² est pair → q est pair. Mais alors p et q sont tous les deux pairs → ils ont 2 comme diviseur commun → contredisent l'hypothèse que p et q sont premiers entre eux. Contradiction. Donc, notre supposition initiale est fausse : √2 n'est pas rationnel → il est irrationnel. ∎ ### Autre exemple : **Théorème** : Il existe une infinité de nombres premiers. **Preuve par contradiction** (d'Euclide) : Supposons qu'il n'y ait qu'un nombre fini de nombres premiers. Les lister : p₁, p₂, ..., pₙ. Considérons le nombre N = p₁p₂⋯pₙ + 1. N est supérieur à 1, donc il a un diviseur premier. Mais aucun des pᵢ ne divise N (car la division de N par pᵢ laisse un reste 1). Donc, N a un diviseur premier qui n'est pas dans la liste {p₁, ..., pₙ} → contradiction avec l'hypothèse que la liste contient tous les nombres premiers. Donc, il y a une infinité de nombres premiers. ∎ ### Exercice 8 : Preuves par contradiction 1. Prouver par contradiction que si n² est pair, alors n est pair. 2. Prouver par contradiction que la somme d'un nombre rationnel et d'un nombre irrationnel est irrationnelle. 3. Prouver par contradiction que le plus grand commun diviseur de deux nombres consécutifs est 1. **Corrigé** : 1. Supposons que n² soit pair et que n soit impair. Alors n = 2k + 1 pour algún k ∈ ℤ. Alors n² = (2k+1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1 → impair. Mais on a supposé n² pair → contradiction. Donc, n ne peut pas être impair → n est pair. ∎ 2. Soit r un nombre rationnel et i un nombre irrationnel. Supposons que r + i soit rationnel. Alors, il existe deux rationnels a et b tels que r + i = a. Alors i = a - r. Mais la différence de deux rationnels est rationnelle → i serait rationnel. Contredit l'hypothèse que i est irrationnel. Donc, r + i ne peut pas être rationnel → il est irrationnel. ∎ 3. Soient n et n+1 deux entiers consécutifs. Supposons que pgcd(n, n+1) = d > 1. Alors d divise n et d divise n+1. Donc d divise (n+1) - n = 1. Mais le seul diviseur positif de 1 est 1 → d = 1. Contredit l'hypothèse d > 1. Donc, pgcd(n, n+1) = 1. ∎ --- ## IX. Proof by mathematical induction La **preuve par récurrence** (ou induction mathématique) permet de démontrer qu'une propriété P(n) est vraie pour tout entier naturel n ≥ n₀ (souvent n₀ = 0 ou 1). Elle repose sur deux étapes : 1. **Initialisation** : Montrer que P(n₀) est vraie. 2. **Hérédité** : Supposer que P(k) est vraie pour un entier arbitraire k ≥ n₀ (hypothèse de récurrence), puis prouver que P(k+1) est vraie. > **À retenir** : Si l'initialisation et l'hérédité sont vraies, alors P(n) est vraie pour tout entier n ≥ n₀. ### Exemple 1 : Somme des premiers n entiers naturels **Théorème** : Pour tout entier n ≥ 1, $$ 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2} $$ **Preuve par récurrence** : - **Initialisation (n=1)** : Somme = 1. Formule : 1×(1+1)/2 = 2/2 = 1. Vrai. - **Hérédité** : Supposons que la formule soit vraie pour un certain k ≥ 1 : $$ 1 + 2 + \cdots + k = \frac{k(k+1)}{2} $$ Alors pour k+1 : $$ 1 + 2 + \cdots + k + (k+1) = \frac{k(k+1)}{2} + (k+1) $$ $$ = \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k + 2)}{2} $$ Ce qui est exactement la formule pour n = k+1. Donc, si vraie pour k, alors vraie pour k+1. Par récurrence, la formule est vraie pour tout n ≥ 1. ∎ ### Exemple 2 : Divisibilité **Théorème** : Pour tout entier n ≥ 1, 3 divise (4ⁿ - 1). **Preuve par récurrence** : - **Initialisation (n=1)** : 4¹ - 1 = 4 - 1 = 3 → divisible par 3. Vrai. - **Hérédité** : Supposons que 3 | (4ᵏ - 1) pour un certain k ≥ 1. Alors, il existe un entier m tel que 4ᵏ - 1 = 3m → 4ᵏ = 3m + 1. Maintenant, considérons 4ᵏ⁺¹ - 1 = 4·4ᵏ - 1 = 4(3m + 1) - 1 = 12m + 4 - 1 = 12m + 3 = 3(4m + 1). Donc, 4ᵏ⁺¹ - 1 est divisible par 3. Par récurrence, la propriété est vraie pour tout n ≥ 1. ∎ ### Exercice 9 : Preuves par récurrence 1. Prouver par récurrence que pour tout entier n ≥ 1, $$ 1^2 + 2^2 + 3^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6} $$ 2. Prouver par récurrence que pour tout entier n ≥ 1, $$ 2 + 4 + 6 + \cdots + 2n = n(n+1) $$ 3. Prouver par récurrence que pour tout entier n ≥ 0, $$ 2^n > n $$ **Corrigé** : 1. **Initialisation (n=1)** : Somme = 1² = 1. Formule : 1×2×3/6 = 6/6 = 1. Vrai. **Hérédité** : Supposons vraie pour k : $$ S_k = \frac{k(k+1)(2k+1)}{6} $$ Alors Sₖ₊₁ = Sₖ + (k+1)² $$ = \frac{k(k+1)(2k+1)}{6} + (k+1)^2 = \frac{k(k+1)(2k+1) + 6(k+1)^2}{6} = \frac{(k+1)[k(2k+1) + 6(k+1)]}{6} = \frac{(k+1)(2k^2 + k + 6k + 6)}{6} = \frac{(k+1)(2k^2 + 7k + 6)}{6} $$ Factoriser 2k² + 7k + 6 = (2k+3)(k+2) Donc Sₖ₊₁ = (k+1)(2k+3)(k+2)/6 Ce qui est la formule pour n = k+1 : (k+1)((k+1)+1)(2(k+1)+1)/6 = (k+1)(k+2)(2k+3)/6. ∎ 2. **Initialisation (n=1)** : Somme = 2. Formule : 1×2 = 2. Vrai. **Hérédité** : Supposons vraie pour k : 2+4+⋯+2k = k(k+1) Alors pour k+1 : Sₖ₊₁ = k(k+1) + 2(k+1) = (k+1)(k + 2) Ce qui est la formule pour n = k+1. ∎ 3. **Initialisation (n=0)** : 2⁰ = 1 > 0 → Vrai. **Hérédité** : Supposons 2ᵏ > k pour un certain k ≥ 0. Alors 2ᵏ⁺¹ = 2·2ᵏ > 2k (par hypothèse de récurrence). Maintenant, montrer que 2k ≥ k+1 pour k ≥ 1 ? Mais pour k=0 : 2⁰=1>0, 2¹=2>1 → vrai. Pour k≥1 : 2k ≥ k+1 ⇔ k ≥ 1, vrai. Donc 2ᵏ⁺¹ > 2k ≥ k+1 → 2ᵏ⁺¹ > k+1. Donc vraie pour k+1. Par récurrence, vraie pour tout n ≥ 0. ∎ --- ## ## Synthèse du chapitre Ce chapitre a permis de maîtriser les outils logiques fondamentaux pour raisonner et prouver en mathématiques : - **Propositions** : unités de base de la logique, vraies ou fausses. - **Négation** : transforme V en F et F en V ; ¬(∀x P(x)) ≡ ∃x ¬P(x), ¬(∃x P(x)) ≡ ∀x ¬P(x). - **Conjonction (∧)** : vraie seulement si les deux propositions sont vraies. - **Disjonction (∨)** : vraie si au moins une proposition est vraie. - **Conditionnelle (→)** : fausse seulement si l'antécédent est vrai et le conséquent faux. - **Réciproque** : Q → P ; pas équivalente à P → Q. - **Preuve directe** : partir des hypothèses pour déduire la conclusion. - **Preuve par contre-exemple** : réfuter une affirmation universelle par un exemple contraire. - **Preuve par contradiction** : supposer la négation et montrer qu'elle mène à l'absurde. - **Preuve par récurrence** : initialisation + hérédité → vérité pour tous les entiers naturels ≥ n₀. Ces méthodes sont complémentaires et s'appliquent à tous les domaines des mathématiques : algèbre, théorie des nombres, géométrie, analyse. --- ## ## Glossaire - **Proposition** : Phrase déclarative qui est soit vraie soit fausse. - **Valeur de vérité** : Attribut V (vrai) ou F (faux) d'une proposition. - **Négation** : Opération qui inverse la valeur de vérité d'une proposition (notée ¬P). - **Conjonction** : Opération logique "et" (P ∧ Q), vraie seulement si P et Q sont vraies. - **Disjonction** : Opération logique "ou" (P ∨ Q), vraie si au moins une des deux est vraie. - **Conditionnelle** : Proposition de la forme "Si P alors Q" (P → Q), fausse seulement si P est vraie et Q est fausse. - **Réciproque** : La proposition Q → P, issue de l'inversion de la conditionnelle P → Q. - **Preuve par récurrence** : Méthode de démonstration basée sur l'initialisation et l'hérédité pour les propriétés dépendant d'un entier naturel.