Fiche de révision : Logique et méthodes de démonstration

📋 Plan du Cours

1. Algèbre et structures mathématiques
2. Propositions et prédicats
3. Tables de vérité et connecteurs
4. Équivalence et lois logiques
5. Conditions nécessaires et suffisantes
6. Quantificateurs et négations
7. Traduction des énoncés mathématiques
8. Méthodes de démonstration
9. Structure et rédaction des preuves

📖 1. Algèbre et structures mathématiques

🔑 Notions clés & Définitions

• Loi de composition interne : Une loi de composition interne sur un ensemble E est une application de E × E vers E qui associe à deux éléments de E un élément de E.

★ À maîtriser

• Une structure algébrique est obtenue lorsqu’une loi possède des propriétés telles que l’associativité, un élément neutre ou l’existence d’inverses.

• L’algèbre étudie les objets mathématiques, leurs opérations et les propriétés qui découlent des règles satisfaites par ces opérations.

Compléments

📌 L’addition est une loi interne sur ℤ, tandis que la division ne l’est pas, car 1 ÷ 2 = 1/2 n’appartient pas à ℤ.

• L’addition est interne sur ℕ, mais 3 n’y possède pas d’opposé, alors que son opposé −3 appartient à ℤ.

📖 2. Propositions et prédicats

🔑 Notions clés & Définitions

• Proposition : Une proposition est un énoncé auquel on peut attribuer sans ambiguïté exactement une valeur de vérité, vraie ou fausse.
• Prédicat : Un prédicat P(x) devient une proposition lorsque sa variable est fixée ou quantifiée.

★ À maîtriser

📌 L’énoncé « x + 1 = 4 » est un prédicat et non une proposition tant que x n’est ni fixé ni quantifié.

Compléments

• La vérité d’un prédicat peut dépendre du domaine : « x possède un inverse multiplicatif » est faux pour x = 0 dans ℝ, mais vrai pour tout x de ℝ∗.

📖 3. Tables de vérité et connecteurs

🔑 Notions clés & Définitions

• Négation : La négation ¬P est vraie exactement lorsque P est fausse.
• Conjonction : La conjonction P ∧ Q est vraie seulement lorsque P et Q sont toutes deux vraies.
• Disjonction : La disjonction inclusive P ∨ Q est vraie lorsqu’au moins l’une des propositions est vraie, y compris si les deux le sont.
• Implication : L’implication P ⇒ Q est fausse uniquement lorsque P est vraie et Q est fausse.
• Ou exclusif : Le ou exclusif P ⊕ Q est vrai lorsque exactement une des deux propositions est vraie.

★ À maîtriser

• Pour établir une implication universelle ∀x ∈ E, P(x) ⇒ Q(x), on prend un élément arbitraire x vérifiant P(x), puis on démontre Q(x).

📌 Pour réfuter une implication universelle ∀x ∈ E, P(x) ⇒ Q(x), il suffit de trouver x₀ ∈ E tel que P(x₀) soit vraie et Q(x₀) fausse.

Compléments

• Pour construire une table de vérité d’une formule composée, on évalue les connecteurs pour toutes les combinaisons de valeurs de vérité des propositions élémentaires.

• Deux propositions élémentaires donnent quatre combinaisons de valeurs de vérité et trois propositions en donnent huit.

• La négation exacte de « x > 2 » est « x ≤ 2 ».

📐 Formule - Le ou exclusif vérifie $P \oplus Q \equiv (P \lor Q) \land \neg(P \land Q)$.

• Une implication P ⇒ Q promet seulement que Q est vraie lorsque l’hypothèse P est réalisée.

• L’implication « si un entier est multiple de 4, alors il est pair » est vraie ; le cas n = 6 ne la contredit pas, car l’hypothèse « 6 est multiple de 4 » est fausse.

📖 4. Équivalence et lois logiques

🔑 Notions clés & Définitions

• Équivalence logique : Deux formules qui ont la même valeur de vérité pour toute attribution des variables propositionnelles.

★ À maîtriser

• L’équivalence P ⇔ Q signifie que P et Q ont la même valeur de vérité et est équivalente à $(P \Rightarrow Q) \land (Q \Rightarrow P).$

• Les lois de De Morgan sont $\neg(P \land Q) \Leftrightarrow (\neg P \lor \neg Q)$ et $\neg(P \lor Q) \Leftrightarrow (\neg P \land \neg Q).$

• La contraposée de P ⇒ Q est ¬Q ⇒ ¬P, et elle lui est logiquement équivalente : $P \Rightarrow Q \Leftrightarrow \neg Q \Rightarrow \neg P.$

📌 Pour P ⇒ Q, la réciproque est Q ⇒ P, tandis que la contraposée est ¬Q ⇒ ¬P ; l’implication est toujours équivalente à sa contraposée, mais pas nécessairement à sa réciproque.

Compléments

• L’implication P ⇒ Q est logiquement équivalente à $\neg P \lor Q.$

• Si P signifie « n est multiple de 4 » et Q « n est pair », P ⇒ Q est vraie, Q ⇒ P est fausse pour n = 6, et la contraposée « si n n’est pas pair, alors n n’est pas multiple de 4 » est vraie.

💡 Astuce mémo

La réciproque inverse les flèches ; la contraposée nie les deux termes.

📖 5. Conditions nécessaires et suffisantes

★ À maîtriser

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

Compléments

• Être divisible par 4 est une condition suffisante pour être pair, et être pair est une condition nécessaire pour être divisible par 4.

• Si P ⇔ Q, P est à la fois une condition nécessaire et suffisante pour Q, et Q l’est pour P.

📖 6. Quantificateurs et négations

🔑 Notions clés & Définitions

• Quantificateur universel : Le quantificateur universel ∀x ∈ E, P(x) signifie que la propriété P(x) est vraie pour tout élément x de E.
• Quantificateur existentiel : Le quantificateur existentiel ∃x ∈ E, P(x) signifie qu’il existe au moins un élément x de E tel que P(x) soit vraie.
• Existence et unicité : La formule ∃!x ∈ E, P(x) signifie qu’il existe exactement un élément de E satisfaisant P(x).

★ À maîtriser

• La négation d’une affirmation universelle est une affirmation existentielle avec la propriété niée : $\neg(\forall x \in E, P(x)) \Leftrightarrow \exists x \in E, \neg P(x).$

📌 L’ordre des quantificateurs change le sens : ∀x ∈ ℝ, ∃y ∈ ℝ, y > x est vraie, tandis que ∃y ∈ ℝ, ∀x ∈ ℝ, y > x est fausse.

Compléments

• La négation de ∀x ∈ ℝ, x² + x + 1 > 0 est ∃x ∈ ℝ, x² + x + 1 ≤ 0.

• Dans ∀x ∈ ℝ, ∃y ∈ ℝ, y > x, le choix de y peut dépendre de x, alors que dans ∃y ∈ ℝ, ∀x ∈ ℝ, y > x, un même y devrait convenir à tous les réels.

💡 Astuce mémo

« Tous » se nie par « il existe » ; « il existe » se nie par « tous ».

📖 7. Traduction des énoncés mathématiques

🔑 Notions clés & Définitions

• Injectivité : Une fonction f est telle que, pour tous x et y de E, f(x) = f(y) implique x = y.
• Surjectivité : Une fonction f : E → F est telle que, pour tout y ∈ F, il existe x ∈ E tel que f(x) = y.

📝 Points essentiels

• « Tout entier pair est le double d’un entier » se traduit par ∀n ∈ ℤ, n pair ⇒ ∃k ∈ ℤ, n = 2k.

📐 Formule - La négation de l’injectivité de f s’écrit $\exists x,y \in E,\ x \ne y \land f(x)=f(y).$

📖 8. Méthodes de démonstration

★ À maîtriser

• Pour démontrer directement P ⇒ Q, on suppose P vraie et on en déduit Q.

• Pour démontrer P ⇒ Q par contraposée, on démontre l’implication équivalente ¬Q ⇒ ¬P.

• Le raisonnement par l’absurde consiste à supposer la négation du résultat à démontrer, puis à en déduire une contradiction.

• Pour démontrer P ⇔ Q, on prouve généralement séparément P ⇒ Q et Q ⇒ P.

📌 Pour réfuter une affirmation universelle ∀x ∈ E, P(x), il suffit de donner un x₀ ∈ E pour lequel P(x₀) est fausse.

• La récurrence sur P(n), définie pour n ∈ ℕ à partir de n₀, exige de démontrer P(n₀), puis P(n) ⇒ P(n + 1) pour tout n ≥ n₀ ; on en conclut que P(n) est vraie pour tout n ≥ n₀.

Compléments

• Si a = 2k et b = 2ℓ pour k, ℓ ∈ ℤ, alors a + b = 2(k + ℓ) et a + b est pair.

• Pour démontrer que si n² est pair alors n est pair, on prouve la contraposée : si n est impair, n = 2k + 1 et n² = 2(2k² + 2k) + 1 est impair.

• Pour établir l’irrationalité de √2, supposer √2 = p/q avec p et q premiers entre eux conduit à montrer que p et q sont tous deux pairs, en contradiction avec leur coprimalité.

• Dans une démonstration par disjonction de cas, on traite séparément chaque situation d’une partition naturelle des possibilités.

• Pour tout n ∈ ℤ, n(n + 1) est pair : si n est pair, n fournit un facteur pair, et si n est impair, n + 1 est pair.

• L’affirmation « tout nombre premier est impair » est réfutée par 2, qui est premier et pair.

📐 Formule - La somme des entiers de 1 à n vérifie $1+2+\cdots+n=\frac{n(n+1)}{2}$ pour tout n ≥ 1.

📖 9. Structure et rédaction des preuves

★ À maîtriser

• Un théorème peut se lire sous la forme « hypothèses ⇒ conclusion », et sa démonstration relie les hypothèses à la conclusion par une chaîne d’implications justifiées.

• 🔄 La préparation d’une preuve suit ces étapes :

  1. Identifier précisément l’énoncé à prouver.
  2. Repérer les quantificateurs et l’implication principale.
  3. Écrire les hypothèses utilisables.
  4. Reconnaître la forme de la conclusion.
  5. Choisir une stratégie de preuve.
  6. Justifier chaque transition.
  7. Terminer par une phrase répondant exactement à la question.

Compléments

• Pour démontrer que si n est multiple de 6 alors n est pair, on écrit n = 6k avec k ∈ ℤ, puis n = 2(3k) avec 3k ∈ ℤ, d’où 2 | n.

• Dans une preuve, chaque passage doit être justifié et la conclusion doit répondre exactement à la propriété annoncée.

• Les stratégies de preuve à envisager sont :

  • la démonstration directe
  • la contraposée
  • l’absurde
  • la disjonction de cas
  • la récurrence
  • la double implication

• Vérifier quelques exemples ne démontre pas une proposition universelle, et il faut préciser le domaine des variables.

• Une preuve d’implication ne doit pas supposer la conclusion, une équivalence exige les deux sens, et « il existe pour tout » ne signifie pas qu’un même élément existe pour tous.

💡 Astuce mémo

Des hypothèses, une chaîne justifiée, puis la conclusion.