Fiche de révision : Rudiments de logique et démonstration

📋 Plan du Cours

1. Histoire de la logique mathématique
2. Définitions et propositions
3. Quantificateurs et variables muettes
4. Conjonction disjonction et négation
5. Implication et équivalence
6. Traduction des propriétés mathématiques
7. Méthodes de démonstration élémentaires
8. Analyse-synthèse et unicité
9. Raisonnement par récurrence
10. Applications aux fonctions et suites

📅 Repères chronologiques

1. 1847Boole inventa l’algèbre qui porte son nom et De Morgan publia ses lois, contribuant à définir un calcul de vérité.
2. 1930Gödel démontra que toute théorie suffisamment riche, notamment l’arithmétique dans N, ne peut pas être à la fois complète et cohérente. — théorème d’incomplétude, 1930
3. 1963Cohen démontra l’indépendance de l’hypothèse du continu par rapport aux axiomes de Zermelo-Fraenkel.

📖 1. Histoire de la logique mathématique

🔑 Notions clés & Définitions

• Cohérence : l’impossibilité de démontrer simultanément une proposition et son contraire dans une théorie
• Complétude : La complétude signifie que tout énoncé est démontrable ou que son opposé est démontrable à l’intérieur de la théorie.
• Décidabilité : l’existence d’une procédure permettant de tester tout énoncé de la théorie

📝 Points essentiels

• À la fin du XIXe siècle, de nombreux mathématiciens ont cherché à donner des bases solides aux mathématiques en étudiant notamment leurs fondements logiques.

• Les axiomes de Peano définissent l’ensemble des entiers ainsi que les lois d’addition et de multiplication, et permettent d’obtenir le principe de récurrence.

• Frege énonça trois propriétés souhaitables d’une théorie mathématique:

  • la cohérence
  • la complétude
  • la décidabilité

💡 Astuce mémo

Peano → Boole et De Morgan → Frege → Gödel → Cohen

📖 2. Définitions et propositions

🔑 Notions clés & Définitions

• Définition : le fait de nommer un objet ou un type d’objets
• Proposition : un énoncé qui est exclusivement vrai ou faux
• Équivalence logique : Deux propositions P et Q sont équivalentes, noté P ⇔ Q, lorsqu’elles ont les mêmes valeurs logiques.

★ À maîtriser

📌 La phrase « n est un multiple de 4 » n’est pas une proposition lorsque n n’est pas défini, car sa valeur de vérité dépend de l’entier choisi.

Compléments

• La fonction carré est définie comme la fonction qui à tout réel x associe $x^2$.

💡 Astuce mémo

Définir un objet ne garantit pas son existence ; une proposition, elle, est vraie ou fausse

📖 3. Quantificateurs et variables muettes

🔑 Notions clés & Définitions

• Quantificateur universel : Le quantificateur universel ∀ signifie « pour tout » et permet d’affirmer qu’une propriété P(x) est vraie pour chaque x d’un ensemble E.
• Quantificateur existentiel : le symbole qui signifie qu’il existe au moins un élément x de E vérifiant P(x)
• Existence unique : le symbole qui signifie qu’il existe un unique élément x de E vérifiant P(x)

📝 Points essentiels

• Pour démontrer ∀x∈E, P(x), on fixe un élément x quelconque de E et on démontre P(x).

• Pour démontrer ∃x∈E, P(x), il suffit de fournir un élément de E qui vérifie P(x), tandis que pour utiliser cette proposition on ne peut pas choisir un élément arbitraire.

• Pour démontrer ∃!x∈E, P(x), il faut prouver séparément l’existence et l’unicité.

• Des quantificateurs de même nature peuvent être permutés, mais un quantificateur universel et un quantificateur existentiel ne peuvent généralement pas être permutés.

💡 Astuce mémo

∀ = tout, ∃ = au moins un, ∃! = un seul

📖 4. Conjonction disjonction et négation

🔑 Notions clés & Définitions

• Disjonction : une proposition vraie si et seulement si au moins l’une des propositions P ou Q est vraie
• Conjonction : une proposition vraie si et seulement si P et Q sont simultanément vraies
• Négation : La négation ¬P est vraie lorsque P est fausse et fausse lorsque P est vraie.

📝 Points essentiels

📌 La négation de P ∧ Q est équivalente à ¬P ∨ ¬Q.

📌 La négation de ∃x∈E, P(x) est équivalente à ∀x∈E, ¬P(x), tandis que la négation de ∀x∈E, P(x) est équivalente à ∃x∈E, ¬P(x).

💡 Astuce mémo

P ∧ Q exige les deux ; P ∨ Q exige au moins une

📖 5. Implication et équivalence

🔑 Notions clés & Définitions

• Implication : une proposition vraie lorsque P est fausse ou lorsque Q est vraie, et fausse seulement lorsque P est vraie et Q est fausse
• Condition suffisante : une condition suffisante pour Q
• Condition nécessaire : une condition nécessaire pour P

📝 Points essentiels

📌 Une implication P ⇒ Q est équivalente à sa contraposée ¬Q ⇒ ¬P.

📌 Une équivalence P ⇔ Q est équivalente à la conjonction des deux implications P ⇒ Q et Q ⇒ P.

💡 Astuce mémo

P ⇒ Q n’est pas Q ⇒ P ; P ⇔ Q exige les deux implications

📖 6. Traduction des propriétés mathématiques

🔑 Notions clés & Définitions

• Divisibilité : Pour des entiers a et b avec b≠0, b divise a s’il existe un entier k tel que a=bk.
• Fonction surjective : Une fonction est surjective lorsque tout élément de son ensemble d’arrivée possède au moins un antécédent.
• Fonction injective : Une fonction est injective lorsque tout élément de son ensemble d’arrivée possède au plus un antécédent.

📝 Points essentiels

📌 La phrase « pour tout x∈E vérifiant C(x), P(x) » se traduit par ∀x∈E, C(x) ⇒ P(x).

📌 La proposition « ∀x∈I, ∃M∈R, f(x)≤M » autorise une borne M dépendant de x, tandis que « ∃M∈R, ∀x∈I, f(x)≤M » exprime que f est majorée par une même constante.

💡 Astuce mémo

Condition vérifiée → propriété imposée ; condition non vérifiée → aucune contrainte

📖 7. Méthodes de démonstration élémentaires

📝 Points essentiels

• Pour démontrer une proposition existentielle, on peut exhiber un élément qui la vérifie.

📌 Pour réfuter une proposition universelle, il suffit de trouver un contre-exemple qui vérifie les hypothèses et contredit la conclusion.

• Un raisonnement par séparation de cas consiste à partitionner les possibilités, démontrer la propriété dans chaque cas, puis conclure.

• Pour démontrer une implication par contraposition, on démontre l’implication entre la négation de la conclusion et la négation de l’hypothèse.

• Un raisonnement par l’absurde suppose la négation de la proposition recherchée et en déduit une contradiction.

💡 Astuce mémo

Exemple, contre-exemple, cas, contraposition, absurde

📖 8. Analyse-synthèse et unicité

★ À maîtriser

• Le raisonnement par analyse-synthèse consiste à supposer une solution, en déduire les candidats, puis vérifier lesquels satisfont réellement le problème initial.

Compléments

• L’équation $6+x=x$ possède une seule solution réelle, x=3, car l’analyse fournit les candidats 3 et −2 et la synthèse élimine −2.

• Pour montrer que √2 est irrationnel par l’absurde, on suppose √2=p/q sous forme irréductible, puis on déduit que p et q sont tous deux pairs, ce qui contredit l’irréductibilité.

💡 Astuce mémo

Analyser → trouver les candidats → vérifier → conclure

📖 9. Raisonnement par récurrence

🔑 Notions clés & Définitions

• Récurrence simple : La récurrence simple prouve P(n) pour tout n≥n₀ en établissant l’initialisation P(n₀) puis la transmission ∀n≥n₀, P(n)⇒P(n+1).
• Récurrence double : La récurrence double établit P(n₀) et P(n₀+1), puis montre que P(n) et P(n+1) entraînent P(n+2).
• Récurrence forte : La récurrence forte établit P(n₀), puis montre que la véracité de tous les P(k) pour n₀≤k≤n entraîne P(n+1).

★ À maîtriser

📌 Le type de récurrence se choisit selon le nombre de termes précédents nécessaires dans l’étape de transmission.

Compléments

📐 Formule — Pour tout n∈N, $\sum_{k=0}^{n} k=\frac{n(n+1)}{2}$.

💡 Astuce mémo

Une rangée de dominos : initialisation, transmission, chute de tous les suivants

📖 10. Applications aux fonctions et suites

🔑 Notions clés & Définitions

• Fonction croissante : Une fonction f est croissante sur I si, pour tous a,b∈I, a≤b implique f(a)≤f(b).
• Fonction décroissante : Une fonction f est décroissante sur I si, pour tous a,b∈I, a≤b implique f(a)≥f(b).
• Fonction monotone : Une fonction est monotone lorsqu’elle est soit croissante, soit décroissante.

★ À maîtriser

📌 Pour une fonction strictement croissante ou strictement décroissante, l’ordre des antécédents et celui des images sont reliés par une équivalence, tandis que pour une fonction seulement monotone ils le sont seulement par une implication.

📌 Pour résoudre une inéquation, il faut tenir compte de l’ensemble de résolution et des conditions d’existence des expressions utilisées.

Compléments

• Sur [0,π], l’inégalité x≥π/3 est équivalente à cos(x)≤1/2.

💡 Astuce mémo

Monotonie simple : implication ; monotonie stricte : équivalence

📊 Tableaux de synthèse

Quantificateurs et méthodes de preuve

Types de récurrence