Fiche de révision : Logique et raisonnements mathématiques

📋 Plan du Cours

1. Propositions et prédicats
2. Opérateurs logiques élémentaires
3. Implication et équivalence
4. Règles du et et du ou
5. Appartenance et quantificateurs
6. Déduction et disjonction de cas
7. Contraposée, absurde et analyse-synthèse
8. Récurrences simples et généralisées

📖 1. Propositions et prédicats

🔑 Notions clés & Définitions

• Proposition : Énoncé mathématique non paradoxal qui est vrai ou faux, mais pas les deux simultanément.
• Prédicat : Proposition dont la valeur de vérité dépend d’une variable.

★ À maîtriser

📌 Une conjecture est un énoncé mathématique non prouvé que l’on pense vrai, tandis qu’un théorème est une conjecture importante démontrée.

Compléments

• La conjecture de Goldbach affirme que tout entier pair supérieur à 3 peut s’écrire comme la somme de deux nombres premiers.

• Le grand théorème de Fermat affirme que, pour tout entier naturel n ≥ 3, il n’existe pas d’entiers strictement positifs non nuls x, y et z tels que xⁿ + yⁿ = zⁿ.

• Le grand théorème de Fermat a été démontré en 1995 par Andrew Wiles et est devenu le théorème de Fermat-Wiles.

💡 Astuce mémo

Une proposition est vraie ou fausse ; un prédicat dépend d’une variable.

📖 2. Opérateurs logiques élémentaires

🔑 Notions clés & Définitions

• Négation : La négation ¬P est fausse lorsque P est vraie et vraie lorsque P est fausse.
• Conjonction : Proposition vraie lorsque P et Q sont toutes deux vraies, et fausse dès que l’une d’elles est fausse.
• Disjonction : Proposition fausse lorsque P et Q sont toutes deux fausses, et vraie lorsqu’au moins l’une des deux est vraie.

📝 Points essentiels

• Dans un paquet de 52 cartes, l’assertion « la carte est un as ou un pique » est vraie pour 16 cartes : les 13 piques et les 3 as qui ne sont pas des piques.

📖 3. Implication et équivalence

🔑 Notions clés & Définitions

• Implication : Proposition définie par ¬P ∨ Q et vraie si P est fausse ou si P et Q sont toutes deux vraies.
• Équivalence : L’équivalence P ⇔ Q signifie que P ⇒ Q et Q ⇒ P sont vraies, donc que P et Q ont la même valeur de vérité.

★ À maîtriser

📌 La réciproque de P ⇒ Q est Q ⇒ P, tandis que sa contraposée est ¬Q ⇒ ¬P.

📌 Si P ⇒ Q est vraie, P est une condition suffisante pour Q et Q est une condition nécessaire pour P.

Compléments

📌 La transitivité de l’implication affirme que si P ⇒ Q et Q ⇒ R, alors P ⇒ R.

💡 Astuce mémo

P ⇒ Q va de P vers Q ; sa réciproque inverse le sens, sa contraposée nie les deux termes.

📖 4. Règles du et et du ou

★ À maîtriser

• La double négation vérifie ¬(¬P) ⇔ P.

• La conjonction et la disjonction sont associatives et commutatives : on peut regrouper ou permuter leurs termes sans changer la proposition.

• La distributivité logique vérifie P ∧ (Q ∨ R) ⇔ (P ∧ Q) ∨ (P ∧ R) et P ∨ (Q ∧ R) ⇔ (P ∨ Q) ∧ (P ∨ R).

• Les lois de De Morgan donnent ¬(P ∧ Q) ⇔ ¬P ∨ ¬Q et ¬(P ∨ Q) ⇔ ¬P ∧ ¬Q.

Compléments

📌 La négation d’une implication vérifie ¬(P ⇒ Q) ⇔ P ∧ ¬Q.

💡 Astuce mémo

La négation retourne les connecteurs : le et devient ou, et le ou devient et.

📖 5. Appartenance et quantificateurs

🔑 Notions clés & Définitions

• Quantificateur universel : Notation signifiant que la propriété P(x) est vraie pour tous les éléments x de E.
• Quantificateur existentiel : La notation ∃x ∈ E, P(x) signifie qu’au moins un élément de E vérifie P(x), et ∃!x ∈ E indique qu’un unique élément la vérifie.
• Appartenance : La notation x ∈ E signifie que x appartient à l’ensemble E, et x ∉ E signifie que x n’y appartient pas.

★ À maîtriser

📌 La négation de ∀x ∈ E, P(x) est ∃x ∈ E, ¬P(x), et la négation de ∃x ∈ E, P(x) est ∀x ∈ E, ¬P(x).

Compléments

📌 L’ordre des quantificateurs de natures différentes change le sens de l’assertion et ne peut pas être inversé en général.

💡 Astuce mémo

∀ exige tous les éléments ; ∃ en exige au moins un.

📖 6. Déduction et disjonction de cas

🔑 Notions clés & Définitions

• Déduction : Raisonnement qui part d’hypothèses et atteint une conclusion par une suite d’implications.
• Raisonnement par équivalences : Raisonnement établissant une proposition par une succession d’équivalences vers une proposition plus simple dont on connaît les cas de vérité.

★ À maîtriser

• Le raisonnement par disjonction de cas démontre une propriété en séparant les situations possibles, en établissant le résultat dans chaque cas, puis en concluant que les cas couvrent toutes les possibilités.

Compléments

• Pour tout entier naturel n, n(n + 1) est pair, ce qui se démontre en distinguant les cas où n est pair et où n est impair.

💡 Astuce mémo

Déduction : hypothèses → implications → conclusion ; cas : couvrir chaque situation → conclure.

📖 7. Contraposée, absurde et analyse-synthèse

🔑 Notions clés & Définitions

• Raisonnement par contraposée : Pour démontrer P ⇒ Q, le raisonnement par contraposée démontre l’implication équivalente ¬Q ⇒ ¬P.
• Raisonnement par l’absurde : Méthode qui suppose P vraie et Q fausse, puis établit qu’elles entraînent une contradiction.

★ À maîtriser

• L’analyse-synthèse recherche une solution en déduisant d’abord des conditions nécessaires à partir de son existence supposée, puis en vérifiant que les objets satisfaisant ces conditions sont effectivement solutions.

Compléments

• Pour toute fonction f : ℝ → ℝ, la décomposition en une fonction paire p et une fonction impaire i est unique, avec p(x) = (f(x) + f(−x))/2 et i(x) = (f(x) − f(−x))/2.

• Par l’absurde, si n + 1 paires de chaussettes sont rangées dans n tiroirs, au moins un tiroir contient au moins deux paires : supposer au plus une paire par tiroir limiterait leur nombre total à n.

💡 Astuce mémo

Contraposée : nier conclusion et hypothèse ; absurde : supposer la conclusion fausse et obtenir une contradiction.

📖 8. Récurrences simples et généralisées

🔑 Notions clés & Définitions

• Récurrence double : Si P(n₀) et P(n₀ + 1) sont vraies et si, pour tout n ≥ n₀, P(n) et P(n + 1) impliquent P(n + 2), alors P(n) est vraie pour tout n ≥ n₀.
• Récurrence forte : Si P(n₀) est vraie et si, pour tout n ≥ n₀, la vérité de P(k) pour chaque k de n₀ à n implique P(n + 1), alors P(n) est vraie pour tout n ≥ n₀.

★ À maîtriser

• La rédaction d’une récurrence simple comporte l’annonce de P(n), l’initialisation au rang n₀, l’hérédité de n à n + 1 et la conclusion.

Compléments

• La somme 1 + 2 + … + n vaut n(n + 1)/2 pour tout entier n ≥ 1.

• Le paradoxe des crayons de couleurs vient d’une hérédité défectueuse au passage de n = 1 à n = 2 : les deux groupes de crayons successifs n’ont alors aucun crayon commun.

💡 Astuce mémo

L’escalier de Peano : atteindre la première marche, puis savoir passer à la suivante.

📊 Tableaux de synthèse

Comparaison des récurrences