Université L1 / enseignement supérieur

Logique mathématique et démonstrations : exercices corrigés L1

Une grande partie des difficultés en L1 vient du passage d’une intuition à une preuve. On révise ici la négation avec quantificateurs, la récurrence et deux méthodes incontournables : contraposée et raisonnement par l’absurde.

L'essentiel à retenir

  • Une implication P⇒QP\Rightarrow Q est fausse exactement quand PP est vraie et QQ fausse ; sa négation est P∧¬QP\land\neg Q.
  • La contraposée de P⇒QP\Rightarrow Q est ¬Q⇒¬P\neg Q\Rightarrow\neg P ; les deux propositions sont logiquement équivalentes.
  • Les quantificateurs s’échangent dans la négation : ¬(∀x P(x))  ⟺  ∃x ¬P(x)\neg(\forall x\,P(x))\iff\exists x\,\neg P(x) et ¬(∃x P(x))  ⟺  ∀x ¬P(x)\neg(\exists x\,P(x))\iff\forall x\,\neg P(x).
  • Une preuve par récurrence comporte initialisation, hérédité et conclusion.
  • Une preuve par l’absurde suppose la négation de la propriété cherchée et aboutit à une contradiction.

Exercice 1 — Négation de quantificateurs

Considérer la proposition PP : « Pour tout réel xx, il existe un réel yy tel que y>xy>x. »
  1. Écrire PP avec les quantificateurs.
  2. Écrire rigoureusement sa négation.
  3. Dire si PP est vraie ou fausse.
Corrigé détaillé
1. P: ∀x∈R, ∃y∈R, y>xP:\ \forall x\in\mathbb R,\ \exists y\in\mathbb R,\ y>x. 2. Pour nier PP, on inverse ∀\forall et ∃\exists, puis on nie y>xy>x. Ainsi ¬P: ∃x∈R, ∀y∈R, y≤x.\boxed{\neg P:\ \exists x\in\mathbb R,\ \forall y\in\mathbb R,\ y\le x}. 3. PP est vraie : pour tout xx, le nombre y=x+1y=x+1 est réel et satisfait y>xy>x. Sa négation est donc fausse.

Exercice 2 — Récurrence sur une somme

Montrer par récurrence que, pour tout entier n≥1n\ge1, 13+23+⋯+n3=(n(n+1)2)2.1^3+2^3+\cdots+n^3=\left(\frac{n(n+1)}2\right)^2.
Corrigé détaillé
1. Initialisation. Pour n=1n=1, le membre de gauche vaut 11 et celui de droite (1⋅2/2)2=1(1\cdot2/2)^2=1. 2. Hérédité. Supposons la formule vraie au rang nn. Alors ∑k=1n+1k3=(n(n+1)2)2+(n+1)3.\sum_{k=1}^{n+1}k^3=\left(\frac{n(n+1)}2\right)^2+(n+1)^3. Factorisons (n+1)2(n+1)^2 : (n+1)2(n24+n+1)=(n+1)2(n+2)24=((n+1)(n+2)2)2.(n+1)^2\left(\frac{n^2}{4}+n+1\right)=(n+1)^2\frac{(n+2)^2}{4}=\left(\frac{(n+1)(n+2)}2\right)^2. La formule est donc vraie au rang n+1n+1. 3. Conclusion. Par récurrence, elle est vraie pour tout n≥1n\ge1.

Exercice 3 — Contraposée et raisonnement par l’absurde

  1. Prouver par contraposée que pour tout n∈Zn\in\mathbb Z, si n2n^2 est pair, alors nn est pair.
  2. En déduire, par l’absurde, que 2\sqrt2 est irrationnel.
Corrigé détaillé
1. Contraposée. La contraposée est : si nn est impair, alors n2n^2 est impair. Écrivons n=2k+1n=2k+1. Alors n2=4k(k+1)+1=2(2k(k+1))+1n^2=4k(k+1)+1=2(2k(k+1))+1, impair. L’implication initiale est donc démontrée. 2. Supposons 2=p/q\sqrt2=p/q avec p∈Zp\in\mathbb Z, q∈N∗q\in\mathbb N^* et la fraction irréductible. L’égalité p2=2q2p^2=2q^2 montre que p2p^2 est pair. D’après la question 1, pp est pair : p=2kp=2k. Alors 4k2=2q24k^2=2q^2, donc q2=2k2q^2=2k^2, ce qui impose que qq est pair. La fraction p/qp/q aurait un facteur commun 22, contradiction. Ainsi 2∉Q\boxed{\sqrt2\notin\mathbb Q}.

Exercice 4 — Table de vérité de l'implication

Établir la table de vérité de P⇒QP\Rightarrow Q, l'exprimer avec ¬P∨Q\neg P\lor Q, puis déterminer quand l'implication est fausse.
Corrigé détaillé
1. Pour (P,Q)=(V,V),(V,F),(F,V),(F,F)(P,Q)=(V,V),(V,F),(F,V),(F,F), les valeurs de P⇒QP\Rightarrow Q sont respectivement V,F,V,VV,F,V,V. 2. Les mêmes valeurs apparaissent pour ¬P∨Q\neg P\lor Q : les propositions sont équivalentes. 3. Une implication est fausse uniquement lorsque l'hypothèse est vraie et la conclusion fausse.

Exercice 5 — Négation des quantificateurs

Nier ∀x∈R,∃y∈R:y>x\forall x\in\mathbb R,\exists y\in\mathbb R:y>x, puis montrer que la proposition initiale est vraie.
Corrigé détaillé
1. La négation échange ∀\forall et ∃\exists, puis nie y>xy>x en y≤xy\le x. 2. Elle s'écrit ∃x∈R,∀y∈R:y≤x\exists x\in\mathbb R,\forall y\in\mathbb R:y\le x. 3. L'énoncé initial est vrai : pour tout xx, choisir y=x+1y=x+1 donne y>xy>x. Sa négation est donc fausse.

Exercice 6 — Contraposée et parité

Démontrer : si n2n^2 est pair, alors nn est pair, à l'aide d'une contraposée. Expliquer pourquoi la réciproque est aussi vraie.
Corrigé détaillé
1. La contraposée est « si nn est impair, alors n2n^2 est impair ». 2. Si n=2k+1n=2k+1, alors n2=4k(k+1)+1n^2=4k(k+1)+1 est impair. L'énoncé initial est donc démontré. 3. Si n=2kn=2k est pair, n2=4k2n^2=4k^2 est pair ; la réciproque est vraie. Les deux propriétés sont équivalentes.

Exercice 7 — Récurrence géométrique

Démontrer par récurrence que pour q≠1q\ne1, ∑k=0nqk=(1−qn+1)/(1−q)\sum_{k=0}^{n}q^k=(1-q^{n+1})/(1-q), pour tout n≥0n\ge0.
Corrigé détaillé
1. Pour n=0n=0, les deux membres valent 11. 2. Supposons la formule au rang nn. En ajoutant qn+1q^{n+1}, on obtient (1−qn+1)/(1−q)+qn+1=(1−qn+2)/(1−q)(1-q^{n+1})/(1-q)+q^{n+1}=(1-q^{n+2})/(1-q). 3. C'est la formule au rang n+1n+1 ; par récurrence elle est vraie pour tout n≥0n\ge0.

Exercice 8 — Raisonnement par l'absurde

Démontrer que 3\sqrt3 est irrationnel. Partir d'une fraction irréductible p/qp/q et utiliser la divisibilité par 3.
Corrigé détaillé
1. Supposons 3=p/q\sqrt3=p/q avec p,qp,q entiers premiers entre eux et q>0q>0. 2. Alors p2=3q2p^2=3q^2 ; un carré divisible par 3 vient d'un entier divisible par 3, donc p=3kp=3k. 3. On obtient 9k2=3q29k^2=3q^2, soit q2=3k2q^2=3k^2, donc qq est aussi divisible par 3. Cela contredit l'irréductibilité : 3\sqrt3 est irrationnel.

Exercice 9 — Double implication

Montrer que pour deux ensembles A,BA,B, A=BA=B si et seulement si A⊆BA\subseteq B et B⊆AB\subseteq A.
Corrigé détaillé
1. Si A=BA=B, chaque élément de AA appartient à BB, et inversement : les deux inclusions sont immédiates. 2. Supposons A⊆BA\subseteq B et B⊆AB\subseteq A. Pour tout xx, x∈Ax\in A implique x∈Bx\in B ; la réciproque découle de la seconde inclusion. 3. Les ensembles ont exactement les mêmes éléments, donc A=BA=B. Les deux sens établissent l'équivalence.

Exercice 10 — Négation d'une disjonction

Construire la négation de (P∨Q)(P\lor Q) puis justifier par les lois de De Morgan l'équivalence ¬(P∨Q)  ⟺  (¬P∧¬Q)\neg(P\lor Q)\iff(\neg P\land\neg Q).
Corrigé détaillé
1. Dire que « PP ou QQ » est faux signifie que ni PP ni QQ n'est vrai. 2. Cela revient à affirmer simultanément ¬P\neg P et ¬Q\neg Q. 3. Par la loi de De Morgan, ¬(P∨Q)≡¬P∧¬Q\neg(P\lor Q)\equiv\neg P\land\neg Q. On peut confirmer cette équivalence sur les quatre valeurs de vérité possibles de (P,Q)(P,Q).

Besoin d'aide sur ce chapitre ?

Réserver le bilan offert de 30 minAccompagnement individuel en maths du supérieur