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

📋 Plan du Cours

1. Propositions et fonctions propositionnelles
2. Quantificateurs et ordre
3. Connecteurs et valeurs de vérité
4. Lois logiques fondamentales
5. Disjonction des cas et absurde
6. Contraposée et déduction
7. Équivalences successives
8. Principe de récurrence

📖 1. Propositions et fonctions propositionnelles

🔑 Notions clés & Définitions

• Proposition : Énoncé mathématique qui est vrai ou faux, mais pas les deux à la fois.
• Fonction propositionnelle : Énoncé mathématique contenant une ou plusieurs variables d’un ensemble donné, qui devient une proposition lorsque ces variables reçoivent des valeurs.

📝 Points essentiels

• Une proposition vraie reçoit la valeur V ou 1, tandis qu’une proposition fausse reçoit la valeur F ou 0.

💡 Astuce mémo

Une proposition a déjà une valeur de vérité ; une fonction propositionnelle attend des valeurs pour ses variables.

📖 2. Quantificateurs et ordre

🔑 Notions clés & Définitions

• Quantificateur universel : Symbole qui signifie « pour tout » ou « quel que soit ».
• Quantificateur existentiel : Le quantificateur existentiel ∃ signifie « il existe ».
• Quantificateur d’unicité : Le quantificateur ∃! signifie « il existe un unique ».

📝 Points essentiels

📌 Des quantificateurs de même nature peuvent être permutés, mais des quantificateurs de nature différente ne le peuvent pas en général.

💡 Astuce mémo

Même nature : permutation possible ; nature différente : l’ordre change le sens.

📖 3. Connecteurs et valeurs de vérité

🔑 Notions clés & Définitions

• Négation : La négation ¬P est vraie lorsque P est fausse et fausse lorsque P est vraie.
• Conjonction : La conjonction P ∧ Q est vraie uniquement lorsque P et Q sont toutes deux vraies.
• Disjonction : La disjonction P ∨ Q est fausse uniquement lorsque P et Q sont toutes deux fausses.
• Implication : L’implication P ⇒ Q est équivalente à ¬P ∨ Q et est fausse uniquement lorsque P est vraie et Q est fausse.
• Équivalence logique : L’équivalence P ⇔ Q signifie que P ⇒ Q et Q ⇒ P sont toutes deux vraies ; elle est vraie lorsque P et Q ont la même valeur de vérité.

📖 4. Lois logiques fondamentales

🔑 Notions clés & Définitions

• Loi logique : Proposition composée de plusieurs propositions et connecteurs qui est toujours vraie, quelles que soient les valeurs de vérité des propositions élémentaires.

★ À maîtriser

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

• L’implication P ⇒ Q est équivalente à sa contraposée ¬Q ⇒ ¬P.

Compléments

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

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

📖 5. Disjonction des cas et absurde

★ À maîtriser

📌 Pour prouver une implication en distinguant des cas, on établit la conséquence dans chacun des cas qui partitionnent la situation.

📌 Pour démontrer P par l’absurde, on suppose que P est fausse, on en déduit des conséquences, puis on obtient une contradiction et on conclut que P est vraie.

Compléments

• Pour tout entier naturel n, le produit n(n + 1) est pair, comme le montrent les deux cas n pair et n impair.

• La preuve par l’absurde de l’irrationalité de √2 suppose √2 = p/q avec PGCD(p, q) = 1, puis établit que p et q sont tous deux pairs, en contradiction avec cette hypothèse.

💡 Astuce mémo

Par l’absurde : supposer la négation, déduire, obtenir une contradiction, conclure.

📖 6. Contraposée et déduction

★ À maîtriser

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

📌 Par déduction, si P est vraie et si P ⇒ Q est vraie, alors Q est vraie.

Compléments

• Pour démontrer que xy ≠ 1 et x ≠ y impliquent l’inégalité des deux fractions données dans le cours, on montre par contraposée que leur égalité entraîne xy = 1 ou x = y.

💡 Astuce mémo

Déduction : P mène à Q ; contraposée : non-Q mène à non-P.

📖 7. Équivalences successives

★ À maîtriser

📌 Si A ⇔ B et B ⇔ C, alors A ⇔ C.

Compléments

• Pour x ∈ ℝ⁺, le cours établit par équivalences successives que $\frac{\sqrt{x}}{x^2-x+1} \leq \frac{4}{3}\sqrt{x}$.

📖 8. Principe de récurrence

★ À maîtriser

📌 Si P(n₀) est vraie et si, pour tout n ≥ n₀, P(n) ⇒ P(n + 1) est vraie, alors P(n) est vraie pour tout n ≥ n₀.

• Une démonstration par récurrence comporte une initialisation en n₀, une hérédité de P(n) à P(n + 1), puis une conclusion pour tout n ≥ n₀.

Compléments

📐 Formule - Pour tout n ∈ ℕ*, la somme des entiers de 1 à n vérifie $1+2+\cdots+n=\frac{n(n+1)}{2}$.

💡 Astuce mémo

Initialiser, puis transmettre P(n) à P(n + 1).