Logique Mathématique et Raisonnements

Qu’est-ce qu’une Proposition Logique ?

Une proposition (ou assertion) est une phrase ou un énoncé mathématique qui est soit vrai, soit faux, mais jamais les deux en même temps.

Les Opérations Logiques de Base

En logique, on combine des propositions à l’aide d’opérateurs, un peu comme on combine des nombres avec ( + ) ou \( \times \).

L’opérateur « et » (Conjonction)

La proposition « P et Q » (notée \( P \land Q \)) est vraie uniquement si P est vraie et Q est vraie. Elle est fausse dans tous les autres cas.

Table de vérité de la conjonction :

L’opérateur « ou » (Disjonction)

La proposition « P ou Q » (notée \( P \lor Q \)) est vraie si au moins l’une des deux propositions P ou Q est vraie. Elle n’est fausse que si P et Q sont toutes les deux fausses.

Table de vérité de la disjonction :

La Négation « non »

La proposition « non P » (notée \( \overline{P} \) ou \( \neg P \)) est l’inverse de P. Elle est vraie si P est fausse, et fausse si P est vraie.

Table de vérité de la négation :

L’Implication « ⇒ »

L’implication \( P \Rightarrow Q \) se lit « P implique Q » ou « Si P alors Q ». Elle est définie comme la proposition « (non P) ou Q ».

Une implication est fausse uniquement lorsque l’hypothèse (P) est vraie et la conclusion (Q) est fausse. Elle est vraie dans tous les autres cas.

Table de vérité de l’implication :

L’Équivalence « ⇔ »

L’équivalence \( P \Leftrightarrow Q \) se lit « P équivaut à Q » ou « P si et seulement si Q ». Elle est définie par l’implication mutuelle : \( (P \Rightarrow Q) \text{ et } (Q \Rightarrow P) \).

Elle est vraie lorsque P et Q ont la même valeur de vérité (soit toutes les deux vraies, soit toutes les deux fausses).

Table de vérité de l’équivalence :

Lois Logiques (Tautologies)

Une loi logique, ou tautologie, est une proposition complexe qui est toujours vraie, quelles que soient les valeurs de vérité des propositions qui la composent.

Principales équivalences logiques

Soient P, Q, et R des propositions. Les équivalences suivantes sont des lois logiques :

• Double négation : \( P \Leftrightarrow \text{non}(\text{non}(P)) \)
• Commutativité : \( (P \text{ et } Q) \Leftrightarrow (Q \text{ et } P) \) et \( (P \text{ ou } Q) \Leftrightarrow (Q \text{ ou } P) \)
• Lois de Morgan :
  • \( \text{non}(P \text{ et } Q) \Leftrightarrow (\text{non } P) \text{ ou } (\text{non } Q) \)
  • \( \text{non}(P \text{ ou } Q) \Leftrightarrow (\text{non } P) \text{ et } (\text{non } Q) \)
• Distributivité :
  • \( P \text{ et } (Q \text{ ou } R) \Leftrightarrow (P \text{ et } Q) \text{ ou } (P \text{ et } R) \)
  • \( P \text{ ou } (Q \text{ et } R) \Leftrightarrow (P \text{ ou } Q) \text{ et } (P \text{ ou } R) \)
• Contraposition : \( (P \Rightarrow Q) \Leftrightarrow (\text{non}(Q) \Rightarrow \text{non}(P)) \)

Fonctions Propositionnelles et Quantificateurs

Une fonction propositionnelle P(x) est une expression dépendant d’une variable x (d’un ensemble E) qui devient une proposition (vraie ou fausse) lorsqu’on attribue une valeur à x.

Le Quantificateur Universel \( \forall \) (Pour tout)

La proposition \( \forall x \in E, P(x) \) se lit « Pour tout x appartenant à E, P(x) est vraie ». Elle est vraie si P(x) est vraie pour chaque élément x de E.

Exemple

La proposition \( \forall x \in [1, +\infty[, x^2 \ge 1 \) est vraie.

Le Quantificateur Existentiel \( \exists \) (Il existe)

La proposition \( \exists x \in E / P(x) \) se lit « Il existe (au moins) un x appartenant à E tel que P(x) soit vraie ». Il suffit de trouver un seul x qui vérifie P(x) pour que la proposition soit vraie.

Exemples

• \( \exists n \in \mathbb{N} : n^2 – n \ge n \) est vraie (par exemple, n=3 convient, car \( 9-3 \ge 3 \)).
• \( \exists x \in \mathbb{R} : x^2 = -1 \) est fausse (aucun réel au carré n’est négatif).

Remarque sur l’unicité

Pour préciser qu’un élément est unique, on utilise le quantificateur \( \exists ! \). Par exemple, \( \exists ! x \in \mathbb{R} : f(x) = 0 \) signifie que f s’annule en une unique valeur.

La Négation des Quantificateurs

Pour nier une proposition avec quantificateurs, on change le quantificateur ( \( \forall \) devient \( \exists \) et vice-versa) et on nie la proposition P(x).

• La négation de \( \forall x \in E, P(x) \) est \( \exists x \in E / \overline{P(x)} \).
• La négation de \( \exists x \in E / P(x) \) est \( \forall x \in E, \overline{P(x)} \).

Attention : L’ordre des quantificateurs est très important. \( \forall x \exists y … \) est très différent de \( \exists y \forall x … \).

Les Types de Raisonnements Mathématiques

Voici les méthodes classiques pour construire une démonstration.

Raisonnement direct

Pour montrer que \( P \Rightarrow Q \) est vraie, on suppose que P est vraie et on montre, par une série de déductions logiques, que Q est alors nécessairement vraie.

Raisonnement par disjonction des cas

Pour vérifier une proposition P(x) sur un ensemble E, on peut diviser E en plusieurs sous-ensembles (cas) et montrer que la proposition est vraie dans chaque cas.

Exemple : Montrer que \( \forall n \in \mathbb{N}, n(n+1)(n+2) \) est un multiple de 3.

Tout entier \( n \) a un reste de 0, 1 ou 2 dans la division par 3. On distingue 3 cas :

• Cas 1 : Si \( n = 3k \). Alors \( n(n+1)(n+2) = 3k(3k+1)(3k+2) = 3k’ \). C’est un multiple de 3.
• Cas 2 : Si \( n = 3k+1 \). Alors \( n+2 = (3k+1)+2 = 3k+3 = 3(k+1) \). Le produit contient un facteur 3, il est donc multiple de 3.
• Cas 3 : Si \( n = 3k+2 \). Alors \( n+1 = (3k+2)+1 = 3k+3 = 3(k+1) \). Le produit contient un facteur 3, il est donc multiple de 3.

Conclusion : Dans tous les cas, la proposition est vraie.

Raisonnement par contraposition

Ce raisonnement utilise la loi logique \( (P \Rightarrow Q) \Leftrightarrow (\text{non}(Q) \Rightarrow \text{non}(P)) \).

Au lieu de prouver \( P \Rightarrow Q \) directement, on prouve sa contraposée : on suppose que non(Q) est vraie, et on montre que non(P) est vraie.

Exemple : Montrer que \( x \ne -8 \Rightarrow \frac{x+2}{x+5} \ne 2 \) (pour \( x \ne -5 \)).

Par contraposition, montrons que : \( \frac{x+2}{x+5} = 2 \Rightarrow x = -8 \).

La contraposée est vraie, donc l’implication initiale est vraie.

Raisonnement par l’absurde

Pour montrer qu’une proposition est vraie, on suppose le contraire (sa négation) et on cherche à aboutir à une contradiction (une affirmation qui est logiquement impossible, comme \( 1=0 \) ou une affirmation contraire aux hypothèses).

Exemple : Montrer que si \( a > 0, b > 0 \) et \( \frac{a}{1+b} = \frac{b}{1+a} \), alors \( a = b \).

Supposons par l’absurde que \( \frac{a}{1+b} = \frac{b}{1+a} \) et que \( a \ne b \).

De l’égalité, on tire : \( a(1+a) = b(1+b) \Rightarrow a+a^2 = b+b^2 \Rightarrow a^2-b^2 = b-a \).

Cela donne \( (a-b)(a+b) = -(a-b) \).

Puisque nous avons supposé \( a \ne b \), alors \( a-b \ne 0 \), et on peut diviser par \( (a-b) \). On obtient \( a+b = -1 \).

Ceci est une contradiction, car a et b sont positifs (\( a > 0, b > 0 \)), donc leur somme ne peut pas être négative. Notre hypothèse (\( a \ne b \)) est donc fausse. Par conséquent, \( a = b \).

Raisonnement par Contre-exemple

Pour prouver qu’une proposition universelle \( \forall x \in E, P(x) \) est fausse, il suffit de trouver un seul élément \( x_0 \in E \) pour lequel P(x) est fausse. Cet élément \( x_0 \) est appelé un contre-exemple.

Exemple : Montrer que \( P: (\forall x \in [0, 1]), x^2 \ge x \) est fausse.

Il suffit de trouver un contre-exemple. Prenons \( x = \frac{1}{2} \). On a bien \( x \in [0, 1] \).

Calculons : \( x^2 = (\frac{1}{2})^2 = \frac{1}{4} \). On voit que \( \frac{1}{4} < \frac{1}{2} \), donc \( x^2 < x \).

Nous avons trouvé un x qui ne vérifie pas la propriété, donc la proposition P est fausse.

Raisonnement par équivalence

Pour montrer qu’une proposition P est vraie, on peut la transformer en une proposition Q équivalente (\( P \Leftrightarrow Q \)) dont on sait déjà qu’elle est vraie. On utilise souvent une chaîne d’équivalences.

Exemple : Montrer que \( \forall x > 0, x + \frac{1}{x} \ge 2 \).

On procède par équivalences successives (puisque \( x > 0 \), on peut multiplier sans changer le sens de l’inégalité) :

La dernière proposition \( (x-1)^2 \ge 0 \) est vraie pour tout réel x (un carré est toujours positif ou nul). Puisque nous avons procédé par équivalence, la proposition de départ est également vraie.

Raisonnement par récurrence

Ce raisonnement est utilisé pour montrer qu’une proposition \( P(n) \) est vraie pour tous les entiers \( n \) à partir d’un certain rang (par exemple, pour tout \( n \in \mathbb{N} \)). Il se déroule en trois étapes :

1. Initialisation : On prouve que la proposition est vraie au premier rang (ex: \( P(0) \)).
2. Hérédité : On suppose que \( P(n) \) est vraie pour un certain rang \( n \) (c’est l’hypothèse de récurrence), et on démontre que \( P(n+1) \) est alors vraie.
3. Conclusion : Par le principe de récurrence, on conclut que \( P(n) \) est vraie pour tout \( n \).

L’analogie classique est celle de la file de dominos : si on pousse le premier (Initialisation) et si chaque domino fait tomber le suivant (Hérédité), alors tous les dominos tombent (Conclusion).

Exemple : Montrer que \( \forall n \in \mathbb{N}, n^3 + 2n \) est divisible par 3.

• Initialisation : Pour \( n = 0 \), on a \( 0^3 + 2(0) = 0 \). 0 est divisible par 3 (car 0 = 3*0). Donc P(0) est vraie.
• Hérédité : Supposons que P(n) est vraie pour un certain \( n \in \mathbb{N} \). C’est-à-dire, \( \exists k \in \mathbb{N} / n^3 + 2n = 3k \).
• Montrons P(n+1) : On veut montrer que \( (n+1)^3 + 2(n+1) \) est divisible par 3.
  

  \[ (n+1)^3 + 2(n+1) = (n^3 + 3n^2 + 3n + 1) + (2n + 2) \]
  \[ = (n^3 + 2n) + 3n^2 + 3n + 3 \]
  \[ = (3k) + 3n^2 + 3n + 3 \quad (\text{par hypothèse de récurrence}) \]
  \[ = 3(k + n^2 + n + 1) \]

  En posant \( k’ = k + n^2 + n + 1 \), on a \( (n+1)^3 + 2(n+1) = 3k’ \), ce qui est un multiple de 3. Donc P(n+1) est vraie.

• Conclusion : Par le principe de récurrence, \( n^3 + 2n \) est divisible par 3 pour tout \( n \in \mathbb{N} \).

En résumé (Logique et Raisonnements)

• La logique mathématique utilise des propositions (énoncés vrais ou faux).
• Les opérateurs (et, ou, non, implication, équivalence) permettent de combiner ces propositions. Leurs tables de vérité définissent leur comportement.
• Les quantificateurs (\( \forall \) « pour tout », \( \exists \) « il existe ») permettent de généraliser des propositions à des ensembles.
• Un raisonnement est une structure permettant de prouver une proposition.
• Les méthodes clés incluent le raisonnement direct, par contraposition, par l’absurde, par disjonction de cas, et par récurrence.

Questions Fréquentes (FAQ) sur le Raisonnement Logique