Pass Matu 2027 Tout MatuMath jusqu’à la matu : 89.– une seule fois Tout jusqu’à la matu : 89.– une fois Voir le Pass →

Fiches › Fondements & logique

Fondements & logique · niveau commun

Logique mathématique

Fiche de niveau commun · Fondements & logique · chapitre 1 · 3 notions : Proposition, Négation, Conjonction

Définition

▾

Proposition

énoncé mathématique qui est soit vrai (V), soit faux (F). Exemple : « 2+2=42+2=4 » est vraie ; « tout nombre premier est impair » est fausse.

Négation

de PP, notée ¬P\neg P (ou P‾\overline{P}) : proposition qui est vraie exactement quand PP est fausse.

Conjonction

P∧QP \land Q (« PP et QQ ») : vraie si et seulement si PP et QQ sont toutes deux vraies.

Disjonction

P∨QP \lor Q (« PP ou QQ ») : vraie si au moins l'une des deux est vraie (ou inclusif).

Implication

P⇒QP \Rightarrow Q (« si PP alors QQ ») : fausse uniquement quand PP est vraie et QQ fausse ; vraie dans tous les autres cas.

Équivalence

P⇔QP \Leftrightarrow Q (« PP équivaut à QQ ») : vraie si PP et QQ ont la même valeur de vérité.

Réciproque

de P⇒QP \Rightarrow Q : c'est Q⇒PQ \Rightarrow P. Attention : une implication et sa réciproque ne sont pas équivalentes en général.

Contraposée

de P⇒QP \Rightarrow Q : c'est ¬Q⇒¬P\neg Q \Rightarrow \neg P. Elle est toujours équivalente à l'implication de départ.

Quantificateur universel

∀\forall (« pour tout »). ∀x∈E,P(x)\forall x \in E, P(x) signifie que P(x)P(x) est vraie pour chaque élément xx de EE.

Quantificateur existentiel

∃\exists (« il existe »). ∃x∈E,P(x)\exists x \in E, P(x) signifie qu'il existe au moins un xx dans EE tel que P(x)P(x) est vraie.

Contre-exemple

un élément particulier qui prouve qu'une proposition du type ∀x,P(x)\forall x, P(x) est fausse.

Formules essentielles

▾

Lois de De Morgan

¬(P∧Q)⇔(¬P)∨(¬Q),¬(P∨Q)⇔(¬P)∧(¬Q).\neg(P \land Q) \Leftrightarrow (\neg P) \lor (\neg Q), \qquad \neg(P \lor Q) \Leftrightarrow (\neg P) \land (\neg Q).

Négation d'une implication

¬(P⇒Q)⇔P∧¬Q.\neg(P \Rightarrow Q) \Leftrightarrow P \land \neg Q.

Contraposition

(P⇒Q)⇔(¬Q⇒¬P).(P \Rightarrow Q) \Leftrightarrow (\neg Q \Rightarrow \neg P).

Équivalence et double implication

(P⇔Q)⇔((P⇒Q)∧(Q⇒P)).(P \Leftrightarrow Q) \Leftrightarrow \big((P \Rightarrow Q) \land (Q \Rightarrow P)\big).

Négation des quantificateurs

¬(∀x∈E,  P(x))⇔(∃x∈E,  ¬P(x)),\neg\big(\forall x \in E,\; P(x)\big) \Leftrightarrow \big(\exists x \in E,\; \neg P(x)\big),

¬(∃x∈E,  P(x))⇔(∀x∈E,  ¬P(x)).\neg\big(\exists x \in E,\; P(x)\big) \Leftrightarrow \big(\forall x \in E,\; \neg P(x)\big).

Table de vérité de l'implication

P⇒QP \Rightarrow Q est vraie sauf si PP est vraie et QQ fausse. En particulier, « faux implique n'importe quoi » est toujours vraie.

Méthodes

▾

Pour nier une proposition avec quantificateurs :

  • Remplacer ∀\forall par ∃\exists et inversement.
  • Nier la proposition interne.
  • Exemple : ¬(∀x∈R,  x2≥0)=∃x∈R,  x2<0\neg(\forall x \in \R,\; x^2 \geq 0) = \exists x \in \R,\; x^2 < 0 (ici faux, car la proposition initiale est vraie).

Pour prouver une équivalence P⇔QP \Leftrightarrow Q :

  • Méthode directe : prouver les deux implications P⇒QP \Rightarrow Q et Q⇒PQ \Rightarrow P.
  • Méthode par chaîne d'équivalences : P⇔P1⇔P2⇔⋯⇔QP \Leftrightarrow P_1 \Leftrightarrow P_2 \Leftrightarrow \dots \Leftrightarrow Q (vérifier que chaque étape est bien une équivalence).

Pour réfuter une proposition universelle ∀x,P(x)\forall x, P(x) :

  • Trouver un contre-exemple : un x0x_0 tel que P(x0)P(x_0) est fausse.
  • Un seul contre-exemple suffit.

Pour démontrer ∃x,P(x)\exists x, P(x) :

  • Exhiber explicitement un élément x0x_0 et vérifier que P(x0)P(x_0) est vraie.
  • Ou faire une preuve d'existence non constructive (plus rare au lycée).

Exemples-types

▾

Exemple 1 — Nier « tous les nombres pairs sont divisibles par 4 »

Énoncé : ∀n∈Z,(n pair)⇒(4∣n)\forall n \in \Z, (n \text{ pair}) \Rightarrow (4 \mid n).

Négation : ∃n∈Z,(n pair)∧(4∤n)\exists n \in \Z, (n \text{ pair}) \land (4 \nmid n).

Contre-exemple : n=6n = 6 est pair mais pas divisible par 44. Donc l'énoncé est faux.

Exemple 2 — Contraposée pour simplifier une démonstration

Prouver : « si n2n^2 est pair, alors nn est pair » (n∈Zn \in \Z).

La contraposée est plus simple : « si nn est impair, alors n2n^2 est impair ». Si n=2k+1n = 2k+1, alors n2=4k2+4k+1=2(2k2+2k)+1n^2 = 4k^2+4k+1 = 2(2k^2+2k)+1 est impair. La contraposée étant vraie, l'implication initiale l'est aussi.

Exemple 3 — Distinguer implication et réciproque

PP : « x=2x = 2 ». QQ : « x2=4x^2 = 4 ».

P⇒QP \Rightarrow Q est vraie. Mais la réciproque Q⇒PQ \Rightarrow P est fausse : x=−2x = -2 vérifie QQ mais pas PP. Donc PP et QQ ne sont pas équivalentes.

Pièges et cas particuliers

▾

Confondre « ou » exclusif et inclusif

en mathématiques, « ou » est toujours inclusif : P∨QP \lor Q est vraie si au moins l'une des deux est vraie, y compris quand les deux sont vraies.

Confondre implication et équivalence

P⇒QP \Rightarrow Q ne veut pas dire Q⇒PQ \Rightarrow P. Toujours vérifier dans quel sens l'énoncé est écrit.

Confondre réciproque et contraposée

la contraposée est logiquement équivalente à l'implication de départ ; la réciproque, non.

Nier partiellement une proposition complexe

dans ¬(∀x,P(x)⇒Q(x))\neg(\forall x, P(x) \Rightarrow Q(x)), on obtient ∃x,P(x)∧¬Q(x)\exists x, P(x) \land \neg Q(x). Attention à bien nier aussi l'implication intérieure.

Ordre des quantificateurs

∀x,∃y\forall x, \exists y et ∃y,∀x\exists y, \forall x ne signifient pas la même chose. Exemple : ∀x∈R,∃y,x<y\forall x \in \R, \exists y, x < y est vrai, mais ∃y,∀x,x<y\exists y, \forall x, x < y est faux.

À retenir

▾

Je sais écrire la négation de P∧QP \land Q, P∨QP \lor Q, P⇒QP \Rightarrow Q.

Je sais former la contraposée et la réciproque d'une implication.

Je sais nier une proposition avec quantificateurs ∀\forall et ∃\exists.

Je sais trouver un contre-exemple pour réfuter une proposition universelle.

Je sais prouver une équivalence en séparant les deux implications.

Je sais que la contraposée est équivalente à l'implication, mais pas la réciproque.

Télécharger l'app · gratuit