Revision sheet: Introduction aux principes fondamentaux de la logique formelle

📋 Plan du Cours

1. Propositions et vérité
2. Connecteurs logiques
3. Négation et opérations
4. Implication et équivalence
5. Quantificateurs
6. Variables liées et libres
7. Ensembles et sous-ensembles
8. Opérations sur ensembles
9. Raisonnement par cas
10. Raisonnement par l’absurde
11. Raisonnement par récurrence

📖 1. Propositions et vérité

🔑 Notions clés & Définitions

• Proposition : LAILLET (2025-2026) : phrase ayant un sens précis et une valeur de vérité, qui peut être vraie ou fausse, mais pas les deux simultanément.
• Valeur de vérité d’une proposition : LAILLET (2025-2026) : attribut bivalent d’une proposition, qui indique si celle-ci est vraie (V) ou fausse (F), conformément au principe du tiers exclus.
• Équivalence de propositions : LAILLET (2025-2026) : relation entre deux propositions qui ont la même valeur de vérité dans toutes les interprétations possibles.
• Principe de preuve par équivalence : LAILLET (2025-2026) : méthode de démonstration consistant à prouver qu’une proposition est équivalente à une autre proposition dont la vérité est connue ou plus simple à établir.
• Définition de proposition (notion fondamentale) : LAILLET (2025-2026) : phrase qui possède un sens clair et dont on peut déterminer la valeur de vérité, essentielle en logique pour distinguer les énoncés vérifiables.

📝 Points essentiels

• La proposition doit avoir un sens précis pour pouvoir lui associer une valeur de vérité (principe du tiers exclus).
• Deux propositions sont équivalentes si elles ont la même valeur de vérité dans tous les cas d’interprétation, ce qui permet de simplifier ou transformer des démonstrations en utilisant des équivalences.
• La preuve par équivalence est une technique clé en logique, permettant de prouver la validité d’une proposition en la remplaçant par une proposition équivalente dont la vérité est plus évidente ou connue.
• La valeur de vérité d’une proposition est bivalente, ce qui signifie qu’elle ne peut être qu’une de deux valeurs : vrai ou faux, sans ambiguïté.
• La distinction entre proposition et autres types d’énoncés est fondamentale pour structurer un raisonnement logique rigoureux.

💡 À retenir

Une proposition est une phrase ayant un sens et une valeur de vérité, et l’utilisation d’équivalences permet de simplifier ou de prouver des assertions en logique. La preuve par équivalence repose sur la démonstration que deux propositions ont la même valeur de vérité dans tous les cas.

📖 2. Connecteurs logiques

🔑 Notions clés & Définitions

• Connecteur logique : mot de liaison permettant de combiner plusieurs propositions en une nouvelle proposition, dont la valeur de vérité dépend uniquement des propositions connectées (voir définition de connecteur logique).
• Connecteurs vérifonctionnels : connecteurs dont la valeur de vérité ne dépend que des propositions qu'ils relient, comme « et » (∧), « ou » (∨), « non » (¬) (voir remarque 6).
• Table de vérité des connecteurs : tableau qui indique la valeur de vérité de la proposition résultante en fonction des valeurs de vérité des propositions initiales, illustrant la comportement logique de chaque connecteur.
• Lois de Morgan : règles fondamentales du calcul propositionnel qui relient la négation d'une conjonction ou disjonction à une autre forme, par exemple ¬(P ∧ Q) ≡ ¬P ∨ ¬Q (voir lois de Morgan).
• Involutivité : propriété du connecteur « non » (¬) stipulant que la négation de la négation d'une proposition revient à la proposition initiale, soit ¬(¬P) ≡ P (voir involutivité).

📝 Points essentiels

Les connecteurs logiques sont des mots de liaison qui permettent d'établir des relations entre propositions, formant de nouvelles propositions. Parmi eux, les connecteurs vérifonctionnels sont privilégiés en logique formelle, car leur valeur de vérité dépend uniquement des propositions qu'ils relient, ce qui facilite leur manipulation à l'aide de tables de vérité. La table de vérité est un outil clé pour analyser le comportement de ces connecteurs, notamment pour établir des équivalences ou démontrer des lois. Les lois de Morgan jouent un rôle central dans la transformation et la simplification des expressions logiques, notamment pour la négation de conjonctions ou disjonctions. La propriété d'involutivité, propre au connecteur « non » (¬), garantit que la double négation d'une proposition revient à la proposition elle-même, ce qui est fondamental dans la logique propositionnelle.

💡 À retenir

Les connecteurs logiques vérifonctionnels, illustrés par leur table de vérité, permettent de manipuler et simplifier les propositions en utilisant des lois fondamentales comme celles de Morgan, avec la propriété d'involutivité pour la négation.

📖 3. Négation et opérations

🔑 Notions clés & Définitions

• Négation d’une proposition (¬P) : La proposition ¬P est vraie si P est fausse, et fausse si P est vraie. (Définition)
• Table de vérité de la négation : La valeur de vérité de ¬P est l’opposée de celle de P. Si P = Vrai (V), alors ¬P = Faux (F), et vice versa. (Définition)
• Lois de Morgan appliquées à la négation :
  • ¬(P ∧ Q) ≡ ¬P ∨ ¬Q
  • ¬(P ∨ Q) ≡ ¬P ∧ ¬Q
    Ces lois permettent de transformer la négation d’opérations composées en opérations simples, en inversant les connecteurs. (Source : lois de Morgan, voir section 2)
• Opérations sur propositions incluant la négation :
  • La conjonction P ∧ Q devient ¬(¬P ∨ ¬Q) (via lois de Morgan)
  • La disjonction P ∨ Q devient ¬(¬P ∧ ¬Q) (via lois de Morgan)
  • La négation de la négation, ¬(¬P), est équivalente à P (involutivité). (Définition)

📝 Points essentiels

• La négation permet d’inverser la valeur de vérité d’une proposition : si P est vraie, ¬P est fausse, et vice versa. La table de vérité est fondamentale pour visualiser cette opération.
• Les lois de Morgan sont essentielles pour simplifier ou transformer des propositions négatives complexes, notamment dans la démonstration ou la simplification logique. Elles s’appliquent directement à la négation combinée avec les connecteurs ∧ et ∨.
• La propriété d’involutivité de la négation, ¬(¬P) ≡ P, indique que nier deux fois revient à la proposition initiale.
• La négation d’une implication P ⇒ Q est ¬(P ⇒ Q) ≡ P ∧ ¬Q, ce qui montre que pour que la négation soit vraie, P doit être vraie et Q fausse.

💡 À retenir

La négation d’une proposition inverse sa valeur de vérité, et les lois de Morgan permettent de transformer efficacement la négation d’opérations composées en opérations simples, facilitant ainsi la manipulation logique.

📖 4. Implication et équivalence

🔑 Notions clés & Définitions

• Implication (P ⇒ Q) : Proposition vraie si P est fausse ou si P et Q sont toutes deux vraies. Elle est représentée par la table de vérité où la seule situation fausse est lorsque P est vraie et Q est fausse. (Source : Point de méthode 20)

• Équivalence logique (P ⇔ Q) : Proposition vraie si P et Q ont la même valeur de vérité. Elle est définie comme la conjonction de deux implications : (P ⇒ Q) et (Q ⇒ P). (Source : Point de méthode 26)

• Contraposée (¬Q ⇒ ¬P) : Proposition qui, étant la négation de la conclusion et de l'hypothèse, est logiquement équivalente à l'implication initiale P ⇒ Q. La preuve de cette équivalence peut se faire par la table de vérité ou par calcul propositionnel. (Source : Point de méthode 20)

• Équivalence entre implication et disjonction (¬P ∨ Q) : La proposition P ⇒ Q est logiquement équivalente à la disjonction ¬P ∨ Q. La négation de cette implication est équivalente à P ∧ ¬Q. (Source : Point de méthode 18)

• Méthodes de démonstration : Pour prouver P ⇒ Q, on suppose P vraie et on montre Q vraie. Pour prouver P ⇔ Q, on démontre à la fois P ⇒ Q et Q ⇒ P, ou on utilise la double implication. (Source : Point de méthode 21, 26)

📝 Points essentiels

• La table de vérité de P ⇒ Q montre que l'implication est fausse uniquement lorsque P est vraie et Q est fausse. Elle est toujours vraie dans le cas où P est fausse, indépendamment de Q. (Source : Point de méthode 20)

• La contraposée (¬Q ⇒ ¬P) est logiquement équivalente à P ⇒ Q, ce qui permet souvent de prouver une implication en prouvant sa contraposée. La preuve peut se faire par la table de vérité ou par calcul propositionnel, en utilisant notamment la distributivité et la commutativité. (Source : Point de méthode 20)

• L'équivalence P ⇔ Q est définie comme la conjonction de deux implications : P ⇒ Q et Q ⇒ P. Elle indique que P et Q sont nécessairement vrais ou faux simultanément. La démonstration peut utiliser la méthode par double implication ou par raisonnement par équivalences successives. (Source : Point de méthode 26)

• La négation de P ⇒ Q est ¬P ∨ Q, et la négation de cette implication est P ∧ ¬Q. Ces relations sont une généralisation des lois de Morgan appliquées aux implications. (Source : Point de méthode 18, 41)

• La preuve d'une implication ou d'une équivalence repose sur la supposition de P ou Q, selon le cas, et la déduction logique de Q ou P. La rédaction doit respecter la méthode en supposant P pour montrer Q, ou en utilisant la preuve par contraposée. (Source : Point de méthode 21, 22)

💡 À retenir

L'implication P ⇒ Q est équivalente à la disjonction ¬P ∨ Q, et sa contraposée ¬Q ⇒ ¬P est logiquement équivalente à P ⇒ Q. La démonstration d'une implication repose sur la supposition de P pour déduire Q, ou sur la preuve de sa contraposée.

📖 5. Quantificateurs

🔑 Notions clés & Définitions

• PREDICAT (voir section 6) : Proposition dépendant d’un paramètre x, notée P(x), qui peut prendre différentes valeurs de vérité selon x.
• QUANTIFICATEUR UNIVERSEL (∀x ∈ E, P(x)) : Proposition affirmant que pour tout x dans l’ensemble E, P(x) est vraie. Elle est vraie si tous les éléments de E possèdent la propriété P.
• QUANTIFICATEUR EXISTENTIEL (∃x ∈ E, P(x)) : Proposition affirmant qu’il existe au moins un x dans E tel que P(x) est vraie. Elle est vraie si au moins un élément de E possède la propriété P.
• INTERPRÉTATION (voir section 6) : Les quantificateurs se traduisent en propriétés sur ensembles, par exemple, ∀x ∈ E, P(x) signifie que tous les éléments de E vérifient P, et ∃x ∈ E, P(x) que l’on trouve au moins un.
• RÈGLES D’INTERVERSION (voir section 6) : Les propositions (∀x ∈ E, ∀y ∈ F, P(x, y)) et (∀y ∈ F, ∀x ∈ E, P(x, y)) sont équivalentes ; de même pour les quantificateurs existentiel.

📝 Points essentiels

• La proposition (∀x ∈ E, P(x)) est vraie si tous les x de E vérifient P(x). Elle peut s’écrire aussi comme (∀x, x ∈ E ⇒ P(x)).
• La proposition (∃x ∈ E, P(x)) est vraie si un x dans E vérifie P(x), équivalente à (∃x, x ∈ E ∧ P(x)).
• La négation de (∀x ∈ E, P(x)) est (∃x ∈ E, ¬P(x)), et celle de (∃x ∈ E, P(x)) est (∀x ∈ E, ¬P(x)) (voir section 6).
• Les règles d’interversion permettent d’échanger l’ordre des quantificateurs sans changer la valeur de vérité, sous certaines conditions (voir section 6).
• La distributivité s’applique notamment pour décomposer (∀x ∈ E, Q(x) ∧ R(x)) en (∀x ∈ E, Q(x)) ∧ (∀x ∈ E, R(x)), et pour les disjonctions (∃x ∈ E, Q(x) ∨ R(x)) en (∃x ∈ E, Q(x)) ∨ (∃x ∈ E, R(x)).

💡 À retenir

Les quantificateurs permettent d’étendre la logique à des propriétés sur des ensembles, en exprimant des affirmations universelles ou existentielles, avec des règles précises pour leur interchangeabilité et leur distribution.

📖 6. Variables liées et libres

🔑 Notions clés & Définitions

• Variable liée : Variable apparaissant dans une formule sous l’emprise d’un quantificateur (∀ ou ∃). Elle est « liée » par ce quantificateur, ce qui signifie que sa valeur est déterminée par la portée du quantificateur. (Laillet, 2025) : « Une variable est dite liée si elle est introduite par un quantificateur dans une formule, et sa portée est limitée à cette formule. »

• Variable libre : Variable apparaissant dans une formule sans être sous l’emprise d’un quantificateur. Elle peut être remplacée par une valeur concrète sans changer le sens global de l’expression. (Laillet, 2025) : « Une variable est libre si elle n’est pas liée par un quantificateur dans la formule, et peut être remplacée par une valeur sans affecter la validité de la formule. »

• Notations P(x) : Représente un prédicat dépendant d’une variable x. La formule P(x) peut contenir x comme variable liée ou libre selon le contexte. (Laillet, 2025) : « P(x) désigne un prédicat dépendant de la variable x, dont la valeur de vérité peut varier selon x. »

• Importance de la distinction : La différence entre variables liées et libres est cruciale pour la validité des démonstrations et la compréhension des formules logiques. La variable liée est « quantifiée » par ∀ ou ∃, tandis que la variable libre ne l’est pas, ce qui influence la portée et la signification de la formule. (Laillet, 2025) : « La distinction permet d’éviter des ambiguïtés et de garantir la validité des démonstrations en logique formelle. »

📝 Points essentiels

• La variable liée apparaît uniquement dans le contexte d’un quantificateur (∀x ou ∃x). Sa portée est limitée à la formule ou sous-formule où elle est quantifiée. La variable liée est essentielle pour exprimer des propriétés universelles ou existentielles. (Laillet, 2025)

• La variable libre, en revanche, n’est pas quantifiée dans la formule. Elle peut représenter un paramètre ou une donnée extérieure à la formule, et son remplacement par une valeur concrète ne modifie pas la structure logique de l’expression. (Laillet, 2025)

• Lorsqu’on écrit une formule avec une variable x sans quantificateur, x est considéré comme libre. Pour que la formule soit bien formée en logique, il faut préciser si x est lié ou libre selon le contexte. (Laillet, 2025)

• La portée d’un quantificateur s’étend à toute la formule ou sous-formule qu’il précède. La variable liée ne doit pas apparaître libre dans la partie de la formule où elle est quantifiée. (Laillet, 2025)

• La substitution d’une variable libre par une valeur concrète est toujours permise sans changer la validité de la formule, contrairement à une variable liée dont la portée est limitée. (Laillet, 2025)

💡 À retenir

Une variable liée est introduite par un quantificateur et sa portée est limitée, tandis qu’une variable libre n’est pas quantifiée et peut être remplacée par une valeur concrète sans affecter la formule. La distinction est fondamentale pour la validité des démonstrations en logique mathématique.

📖 7. Ensembles et sous-ensembles

🔑 Notions clés & Définitions

• Ensemble : Collection d’éléments distincts considérés comme un tout. Noté généralement par des lettres majuscules (ex : E, F).
• Appartenance (x ∈ E) : Notation indiquant que l’élément x appartient à l’ensemble E.
• Sous-ensemble (F ⊂ E) : Ensemble F dont tous les éléments sont aussi dans E, c’est-à-dire ∀x, (x ∈ F) ⇒ (x ∈ E).
• Ensemble vide (∅) : Ensemble ne contenant aucun élément.
• Partie décrite en extension : Ensemble défini en énumérant ses éléments (ex : E = {1, 2, 3}).
• Partie décrite en compréhension : Ensemble défini par une propriété ou un prédicat (ex : F = {x ∈ E | P(x)}).

📝 Points essentiels

• La notation x ∈ E signifie que x est un élément de l’ensemble E, tandis que x ∉ E indique que x n’appartient pas à E.
• L’ensemble vide ∅ est un sous-ensemble de tout ensemble, et il est décrit en extension par l’absence d’éléments.
• Un ensemble F est un sous-ensemble de E (F ⊂ E) si et seulement si ∀x, (x ∈ F) ⇒ (x ∈ E).
• La puissance de l’ensemble P(E) est l’ensemble de toutes les parties de E, c’est-à-dire tous les sous-ensembles possibles.
• La description en compréhension d’un ensemble F consiste à définir F = {x ∈ E | P(x)}, où P(x) est une propriété ou un prédicat vérifié par les éléments de F.
• La relation d’inclusion F ⊂ E est équivalente à l’appartenance de F dans P(E), c’est-à-dire F ∈ P(E).
• La cardinalité de P(E) est 2^n si E possède n éléments, car chaque élément peut appartenir ou non à une partie.

💡 À retenir

Un ensemble est une collection d’éléments distincts, et un sous-ensemble est une partie de cet ensemble, défini soit par énumération en extension, soit par propriété en compréhension. La relation d’appartenance (x ∈ E) et la notion d’inclusion (F ⊂ E) sont fondamentales pour manipuler et comparer des ensembles.

📖 8. Opérations sur ensembles

🔑 Notions clés & Définitions

• Union (∪) : Opération qui rassemble tous les éléments appartenant à au moins un des deux ensembles.
  AUTEUR (source) : « L’union de deux ensembles E et F, notée E ∪ F, est l’ensemble des éléments qui appartiennent à E ou à F ou aux deux. »

• Intersection (∩) : Opération qui donne l’ensemble des éléments communs à deux ensembles.
  AUTEUR (source) : « L’intersection de deux ensembles E et F, notée E ∩ F, est l’ensemble des éléments qui appartiennent à la fois à E et à F. »

• Différence (−) : Opération qui consiste à retirer de l’ensemble E tous les éléments appartenant à F.
  AUTEUR (source) : « La différence de deux ensembles E et F, notée E \ F, est l’ensemble des éléments qui appartiennent à E mais pas à F. »

• Relation entre opérations et connecteurs logiques :
  AUTEUR (source) : « L’union correspond à la disjonction (∨), l’intersection à la conjonction (∧), et la différence à la négation et à la différence logique. »
  Point essentiel : Ces opérations sur ensembles sont liées aux connecteurs logiques par des correspondances : union avec « ou » (∨), intersection avec « et » (∧), différence avec la négation (¬) combinée à l’appartenance.

• Propriétés des opérations (commutativité, associativité, distributivité) :
  AUTEUR (source) : « Les opérations sur ensembles vérifient des propriétés fondamentales : »

  • Commutativité : E ∪ F = F ∪ E, E ∩ F = F ∩ E
  • Associativité : (E ∪ F) ∪ G = E ∪ (F ∪ G), (E ∩ F) ∩ G = E ∩ (F ∩ G)
  • Distributivité : E ∩ (F ∪ G) = (E ∩ F) ∪ (E ∩ G), E ∪ (F ∩ G) = (E ∪ F) ∩ (E ∪ G)

📝 Points essentiels

• L’union (∪) rassemble tous les éléments de deux ensembles, correspondant à la disjonction logique. La propriété de commutativité (A ∪ B = B ∪ A) et d’associativité (A ∪ (B ∪ C) = (A ∪ B) ∪ C) facilite la manipulation des unions.
• L’intersection (∩) ne conserve que les éléments communs, avec des propriétés similaires : commutativité et associativité.
• La différence (−) est non commutative, mais distributive par rapport à l’union et à l’intersection selon des lois précises :
  • E \ (F ∪ G) = (E \ F) ∩ (E \ G)
  • E \ (F ∩ G) = (E \ F) ∪ (E \ G)
• La relation entre opérations sur ensembles et connecteurs logiques permet de traduire des expressions en logique propositionnelle en opérations sur ensembles, notamment par l’utilisation de la complémentarité et de l’appartenance.

💡 À retenir

Les opérations sur ensembles (union, intersection, différence) sont fondamentales en logique et en mathématiques, car elles traduisent des connecteurs logiques et possèdent des propriétés essentielles (commutativité, associativité, distributivité) qui facilitent leur manipulation et leur compréhension.

📖 9. Raisonnement par cas

🔑 Notions clés & Définitions

• Principe du raisonnement par cas : méthode de démonstration consistant à prouver une proposition en la divisant en plusieurs cas exhaustifs, chacun étant traité séparément, afin de couvrir toutes les situations possibles.
• Utilisation du connecteur 'ou' (∨) : opérateur logique qui permet de couvrir plusieurs cas en affirmant qu’au moins un d’entre eux est vrai, facilitant la démonstration par cas.
• Exemple de raisonnement par cas : démonstration où l’on considère plusieurs propositions, par exemple P ou Q, et on prouve la proposition cible dans chaque cas séparément, pour conclure globalement.

📝 Points essentiels

• La démonstration par cas repose sur la partition de l’univers en plusieurs situations distinctes, chacune étant exhaustive.
• Le connecteur 'ou' (∨) est essentiel pour exprimer la disjonction entre différents cas, permettant de couvrir toutes les possibilités.
• La méthode consiste à prouver que la proposition est vraie dans chaque cas considéré, ce qui implique sa vérité globale.
• Exemple : pour démontrer une propriété P(x), on peut distinguer deux cas : x est pair ou x est impair. On prouve P(x) dans chaque cas séparément, puis on conclut que P(x) est vraie en général.
• La démonstration par cas est souvent utilisée en combinant avec d’autres techniques, comme la preuve directe ou la preuve par contradiction, pour traiter différentes situations.
• La couverture exhaustive des cas est cruciale : il faut s’assurer que tous les cas possibles sont bien pris en compte pour que la démonstration soit valable.

💡 À retenir

Le raisonnement par cas consiste à prouver une proposition en la décomposant en plusieurs situations exhaustives, en utilisant le connecteur 'ou' pour couvrir toutes les possibilités, ce qui permet de valider la proposition dans tous les cas.

📖 10. Raisonnement par l’absurde

🔑 Notions clés & Définitions

• Principe du raisonnement par l’absurde : méthode de démonstration consistant à supposer la négation d’une proposition pour en déduire une contradiction, et ainsi conclure que la proposition initiale est vraie (voir aussi la critique de la négation dans la section 3).
• Supposition de la négation : étape où l’on considère la proposition contraire à celle que l’on veut prouver, afin de tester sa cohérence ou d’en déduire une contradiction.
• Contradiction : situation où l’on obtient une proposition et sa négation simultanément, ce qui est impossible en logique classique, permettant de conclure que la supposition est fausse.
• Utilisation de la négation et implication : dans le raisonnement par l’absurde, on exploite la relation entre la négation d’une proposition et l’implication pour déduire une contradiction (voir section 4 pour l’implication).
• Exemple de démonstration par l’absurde : montrer qu’une proposition P est vraie en supposant que ¬P est vraie, puis en démontrant que cette supposition mène à une contradiction, donc P doit être vraie.

📝 Points essentiels

• Le raisonnement par l’absurde repose sur le principe que si la négation d’une proposition conduit à une contradiction, alors cette proposition est nécessairement vraie.
• La démarche consiste à supposer ¬P, puis à utiliser la négation et l’implication pour déduire une contradiction, souvent une proposition qui est à la fois vraie et fausse (voir la critique dans la section 3).
• La démonstration par l’absurde est particulièrement utile lorsque la preuve directe est complexe ou difficile à réaliser.
• La méthode s’appuie sur la propriété fondamentale de la logique classique : une proposition et sa négation ne peuvent être vraies en même temps (principe du tiers exclus).
• Exemple : pour prouver que √2 est irrationnel, on suppose le contraire, c’est-à-dire que √2 est rationnel, puis on aboutit à une contradiction avec la parité des nombres entiers (voir aussi la démonstration classique).

💡 À retenir

Le raisonnement par l’absurde consiste à supposer la négation d’une proposition pour en déduire une contradiction, permettant ainsi de conclure que cette proposition est nécessairement vraie.

📖 11. Raisonnement par récurrence

🔑 Notions clés & Définitions

• Principe du raisonnement par récurrence : méthode permettant de démontrer qu'une propriété $ P(n) $ est vraie pour tous les entiers naturels $ n $, en prouvant d'abord sa validité pour un cas initial, puis en montrant que si elle est vraie pour un entier $ n $, alors elle l'est aussi pour $ n+1 $.

• Étapes de la récurrence :

  • Initialisation : démontrer que la propriété $ P(n) $ est vraie pour le premier entier $ n_0 $ (souvent $ n_0=0 $ ou $ 1 $).
  • Hypothèse de récurrence : supposer que $ P(n) $ est vraie pour un entier $ n $ donné.
  • Étape de récurrence : démontrer que, sous cette hypothèse, $ P(n+1) $ est également vraie.

• Utilisation des quantificateurs universels dans la récurrence : dans la preuve, on formule souvent $ \forall n \in \mathbb{N}, P(n) $, en utilisant la logique du quantificateur universel pour exprimer que la propriété est valable pour tout $ n $.

📝 Points essentiels

• La démonstration par récurrence repose sur la logique suivante : si $ P(n_0) $ est vraie (initialisation) et si, pour tout $ n $, $ P(n) \Rightarrow P(n+1) $ (hypothèse de récurrence), alors $ \forall n \in \mathbb{N}, P(n) $ est vraie (point de méthode fondamental).

• La clé est de bien formuler la propriété $ P(n) $ et de prouver rigoureusement chaque étape.

• La structure de la preuve utilise souvent la formule :
  $ \text{Initialisation} : \text{montrer } P(n_0) \quad \text{et} \quad \text{Récurrence} : \forall n \in \mathbb{N}, (P(n) \Rightarrow P(n+1)) $

• La formulation en langage logique : $ \forall n \in \mathbb{N}, P(n) $, est souvent exprimée dans la preuve par $ \text{pour tout } n $, puis démontrée par induction.

• Point à retenir : La récurrence permet de prouver une propriété pour tous les entiers naturels en combinant une étape initiale et une étape de propagation, en utilisant la logique du quantificateur universel.

💡 À retenir

Le raisonnement par récurrence est une méthode puissante pour établir la validité d'une propriété pour tous les entiers naturels, en s'appuyant sur une preuve de base et une étape de transmission.

📊 Tableaux de Synthèse

⚠️ Pièges & Confusions Fréquentes

1. Confondre proposition et énoncé non vérifiable ou ambigu.
2. Oublier que la valeur de vérité d’un connecteur vérifonctionnel dépend uniquement des propositions connectées.
3. Confondre la négation ¬P avec la double négation ¬(¬P) sans se rappeler de l’involutivité.
4. Mal appliquer les lois de Morgan, notamment en inversant incorrectement les connecteurs.
5. Confusion entre implication (P ⇒ Q) et sa négation ¬(P ⇒ Q).
6. Négliger que l’implication est toujours vraie si P est fausse, indépendamment de Q.
7. Confondre la contraposée avec l’implication initiale sans vérifier leur équivalence.

✅ Checklist Examen

1. Connaître la définition d’une proposition selon LAILLET (2025-2026).
2. Maîtriser la table de vérité des connecteurs vérifonctionnels (∧, ∨, ¬).
3. Savoir appliquer les lois de Morgan pour transformer ¬(P ∧ Q) et ¬(P ∨ Q).
4. Connaître la propriété d’involutivité de la négation ¬(¬P) ≡ P.
5. Savoir démontrer qu’une proposition P ⇔ Q en utilisant leur définition par implications.
6. Maîtriser la table de vérité de l’implication P ⇒ Q.
7. Savoir démontrer que P ⇒ Q est équivalent à ¬P ∨ Q.
8. Connaître la définition et la propriété de la contraposée ¬Q ⇒ ¬P.
9. Être capable d’utiliser la preuve par équivalence pour simplifier ou établir la vérité d’une proposition.
10. Connaître la différence entre implication, équivalence, et leur négation.
11. Savoir distinguer une implication vraie dans tous les cas sauf P vrai et Q faux.
12. Connaître la référence de la définition de proposition selon LAILLET (2025-2026).