BURHAN.

Notions de logique : Résumé de cours de Mathématiques 1BAC Sciences Expérimentales

Notions de logique : résumé de maths 1BAC Sciences Expérimentales, avec les points essentiels, les formules et les méthodes à retenir pour réviser avant un contrôle. Pour les élèves de 1BAC Sciences Expérimentales et Sciences et Technologies (STE, STM), option française (BIOF).

Propositions et connecteurs

À retenirLe réflexe : chercher la valeur de vérité

Chaque proposition reçoit V ou F, et une seule de ces deux valeurs. Un énoncé qui contient une lettre libre n'en est pas une, car sa valeur change avec la lettre. Pour trancher, remplace les mots par un calcul. Puis conclus par V ou par F.

DéfinitionProposition ; négation

Une proposition est un énoncé mathématique qui est soit vrai, soit faux, et jamais les deux à la fois. On dit que sa valeur de vérité est « vrai » (notée V) ou « faux » (notée F).

Soit PP une proposition. La négation de PP est la proposition notée P‾\overline{P}, qui se lit « non PP » : elle est vraie lorsque PP est fausse, et fausse lorsque PP est vraie.

DéfinitionConjonction ; disjonction

Soit PP et QQ deux propositions.

  • La conjonction de PP et QQ est la proposition « PP et QQ ». Elle est vraie lorsque PP et QQ sont vraies toutes les deux, et fausse dans les trois autres cas.
  • La disjonction de PP et QQ est la proposition « PP ou QQ ». Elle est vraie lorsque l'une au moins des propositions PP et QQ est vraie, et fausse seulement lorsque PP et QQ sont fausses toutes les deux.

Le « ou » mathématique est inclusif : « PP ou QQ » est vraie aussi lorsque PP et QQ sont vraies en même temps.

DéfinitionImplication ; équivalence ; loi logique

Soit PP et QQ deux propositions.

  • L'implication P⇒QP \Rightarrow Q se lit « PP implique QQ » ou « si PP, alors QQ ». Elle est fausse lorsque PP est vraie et QQ fausse, et vraie dans les trois autres cas. L'implication Q⇒PQ \Rightarrow P est la réciproque de P⇒QP \Rightarrow Q.
  • Lorsque P⇒QP \Rightarrow Q est vraie, on dit que QQ est une condition nécessaire pour que PP soit vraie, et que PP est une condition suffisante pour que QQ soit vraie.
  • L'équivalence P⇔QP \Leftrightarrow Q se lit « PP équivaut à QQ » ou « PP si et seulement si QQ ». Elle est vraie lorsque PP et QQ ont la même valeur de vérité, et fausse sinon.

Une proposition construite à partir de propositions PP, QQ, … et qui est vraie quelles que soient leurs valeurs de vérité est une loi logique.

À retenirLes tables de vérité à connaître

Les définitions des connecteurs tiennent dans un seul tableau. Chaque ligne est une façon de choisir les valeurs de PP et de QQ.

Cas PP QQ P‾\overline{P} P et QP \text{ et } Q P ou QP \text{ ou } Q P⇒QP \Rightarrow Q P⇔QP \Leftrightarrow Q
11 V V F V V V V
22 V F F F V F F
33 F V V F V V F
44 F F V F F V V

Retiens deux colonnes : « ou » n'est faux qu'à la dernière ligne, l'implication n'est fausse qu'à la deuxième.

Exemple

Énoncé. Soit PP : « 8787 est un nombre premier » et QQ : « 8787 est impair ».

Valeurs. PP est fausse, car 87=3×2987 = 3 \times 29. QQ est vraie. Donc « PP et QQ » est fausse, « PP ou QQ » est vraie, et P‾\overline{P} est vraie.

Implications. P⇒QP \Rightarrow Q est vraie, car son hypothèse PP est fausse. Q⇒PQ \Rightarrow P est fausse : QQ est vraie et PP est fausse.

Exemple

Énoncé. Pour un entier naturel nn : « si nn se termine par 00, alors nn est multiple de 55 ». Cette implication est vraie, car n=10k=5×2kn = 10k = 5 \times 2k.

Vocabulaire. Se terminer par 00 est une condition suffisante pour être multiple de 55. Être multiple de 55 est une condition nécessaire pour se terminer par 00.

Réciproque. « Si nn est multiple de 55, alors nn se termine par 00 » est fausse : 1515 la met en défaut. Les deux propositions ne sont pas équivalentes.

Lois logiques

PropriétéDouble négation ; lois de Morgan

Soit PP et QQ deux propositions. Les trois propositions suivantes sont des lois logiques :

  • P‾‾⇔P\overline{\overline{P}} \Leftrightarrow P ;
  • (P et Q)‾⇔(P‾ ou Q‾)\overline{(P \text{ et } Q)} \Leftrightarrow \left(\overline{P} \text{ ou } \overline{Q}\right) ;
  • (P ou Q)‾⇔(P‾ et Q‾)\overline{(P \text{ ou } Q)} \Leftrightarrow \left(\overline{P} \text{ et } \overline{Q}\right).

PropriétéContraposée d'une implication

Soit PP et QQ deux propositions. L'implication Q‾⇒P‾\overline{Q} \Rightarrow \overline{P} est appelée la contraposée de l'implication P⇒QP \Rightarrow Q, et (P⇒Q)⇔(Q‾⇒P‾)(P \Rightarrow Q) \Leftrightarrow \left(\overline{Q} \Rightarrow \overline{P}\right) est une loi logique : une implication et sa contraposée ont toujours la même valeur de vérité.

PropriétéNégation d'une implication ; double implication

Soit PP et QQ deux propositions. Les deux propositions suivantes sont des lois logiques :

  • (P⇒Q)‾⇔(P et Q‾)\overline{(P \Rightarrow Q)} \Leftrightarrow \left(P \text{ et } \overline{Q}\right) ;
  • (P⇔Q)⇔((P⇒Q) et (Q⇒P))(P \Leftrightarrow Q) \Leftrightarrow \big((P \Rightarrow Q) \text{ et } (Q \Rightarrow P)\big).

Méthodevérifier une loi logique

  1. Liste les cas : deux propositions donnent 44 lignes, trois en donnent 88.
  2. Calcule chaque membre, colonne après colonne, avec les tables des connecteurs.
  3. Compare les deux colonnes finales. Égales sur toutes les lignes : l'équivalence est une loi logique.
  4. Une seule ligne où elles diffèrent prouve que ce n'est pas une loi logique.

Exemple

Énoncé. Vérifions que (P⇒Q)⇔(P‾ ou Q)(P \Rightarrow Q) \Leftrightarrow \left(\overline{P} \text{ ou } Q\right) est une loi logique.

Cas PP QQ P⇒QP \Rightarrow Q P‾\overline{P} P‾ ou Q\overline{P} \text{ ou } Q
11 V V V F V
22 V F F F F
33 F V V V V
44 F F V V V

Conclusion. Les colonnes de P⇒QP \Rightarrow Q et de P‾ ou Q\overline{P} \text{ ou } Q coïncident sur les quatre lignes : c'est une loi logique. Elle donne une autre lecture d'une implication.

Exemple

Énoncé. Soit nn un entier. Nie « nn est pair et nn est multiple de 33 ».

Négation. D'après les lois de Morgan, on obtient « nn est impair ou nn n'est pas multiple de 33 ».

Contrôle. Pour n=12n = 12, la proposition est vraie et sa négation fausse. Pour n=10n = 10, c'est l'inverse.

AttentionNier un « et », nier un « ou »

Pour n=9n = 9, « nn est impair et nn n'est pas multiple de 33 » est fausse. Or « nn est pair et nn est multiple de 33 » est fausse aussi. Ces deux phrases ne sont donc pas la négation l'une de l'autre. Pour nier, remplace chaque morceau par son contraire et change « et » en « ou ».

AttentionContraposée ou réciproque ?

Reprends « si nn se termine par 00, alors nn est multiple de 55 ». Sa contraposée, « si nn n'est pas multiple de 55, alors nn ne se termine pas par 00 », est vraie comme elle. Sa réciproque est fausse. Pour obtenir la contraposée, il faut échanger hypothèse et conclusion, et les nier toutes les deux.

Quantificateurs

DéfinitionFonction propositionnelle ; quantificateurs

Soit EE un ensemble, par exemple N\mathbb{N}, Z\mathbb{Z}, R\mathbb{R} ou un intervalle. Un énoncé P(x)P(x) qui contient une variable xx et qui devient une proposition chaque fois que l'on remplace xx par un élément de EE est une fonction propositionnelle définie sur EE.

  • La proposition (∀x∈E):P(x)(\forall x \in E) : P(x) se lit « pour tout xx de EE, P(x)P(x) ». Elle est vraie lorsque P(x)P(x) est vraie pour tous les éléments xx de EE. Le symbole ∀\forall est le quantificateur universel.
  • La proposition (∃x∈E):P(x)(\exists x \in E) : P(x) se lit « il existe au moins un xx de EE tel que P(x)P(x) ». Elle est vraie lorsque P(x)P(x) est vraie pour au moins un élément xx de EE. Le symbole ∃\exists est le quantificateur existentiel.
  • La proposition (∃!x∈E):P(x)(\exists! x \in E) : P(x) se lit « il existe un unique xx de EE tel que P(x)P(x) ». Elle est vraie lorsque P(x)P(x) est vraie pour exactement un élément xx de EE.

À retenirLire et écrire un quantificateur

Lis ∀\forall « pour tout » et ∃\exists « il existe au moins un ». La lettre placée après un quantificateur est muette : (∀t∈R):P(t)(\forall t \in \mathbb{R}) : P(t) dit la même chose que (∀x∈R):P(x)(\forall x \in \mathbb{R}) : P(x). L'ensemble compte : (∃x∈N):2x=3(\exists x \in \mathbb{N}) : 2x = 3 est fausse, alors que (∃x∈R):2x=3(\exists x \in \mathbb{R}) : 2x = 3 est vraie.

Exemple

Pour tout. (∀x∈R):x2+1>0(\forall x \in \mathbb{R}) : x^{2} + 1 > 0 est vraie : un carré n'est jamais négatif, donc x2+1≥1x^{2} + 1 \geq 1.

Il existe. (∃n∈N):n2=10(\exists n \in \mathbb{N}) : n^{2} = 10 est fausse. En effet, si n≤3n \leq 3, alors n2≤9n^{2} \leq 9 ; si n≥4n \geq 4, alors n2≥16n^{2} \geq 16.

Un seul. (∃!x∈R):3x−6=0(\exists! x \in \mathbb{R}) : 3x - 6 = 0 est vraie : l'équation équivaut à x=2x = 2.

AttentionL'ordre des quantificateurs

(∀x∈R)(∃y∈R):x+y=0(\forall x \in \mathbb{R})(\exists y \in \mathbb{R}) : x + y = 0 est vraie : pour chaque xx, le réel y=−xy = -x convient, et il change avec xx. Mais (∃y∈R)(∀x∈R):x+y=0(\exists y \in \mathbb{R})(\forall x \in \mathbb{R}) : x + y = 0 est fausse. Un même yy devrait convenir pour tous les xx, or pour x=1−yx = 1 - y la somme vaut 11.

Négation d'une proposition quantifiée, contre-exemple

PropriétéNégation d'une proposition quantifiée

Soit EE un ensemble et P(x)P(x) une fonction propositionnelle définie sur EE.

  • La négation de la proposition « (∀x∈E):P(x)(\forall x \in E) : P(x) » est la proposition « (∃x∈E):P(x)‾(\exists x \in E) : \overline{P(x)} ».
  • La négation de la proposition « (∃x∈E):P(x)(\exists x \in E) : P(x) » est la proposition « (∀x∈E):P(x)‾(\forall x \in E) : \overline{P(x)} ».

En particulier, pour montrer qu'une proposition « (∀x∈E):P(x)(\forall x \in E) : P(x) » est fausse, il suffit de trouver un élément x0x_0 de EE tel que P(x0)P(x_0) soit fausse : un tel élément est un contre-exemple.

Méthodeécrire une négation

  1. Lis la proposition de gauche à droite : d'abord les quantificateurs, puis la phrase qui les suit.
  2. Retourne chaque quantificateur : « pour tout » devient « il existe », et inversement. Garde les mêmes ensembles, dans le même ordre.
  3. Nie la phrase finale : « et » et « ou » s'échangent, == devient ≠\neq, << devient ≥\geq, et « si AA, alors BB » devient « AA et B‾\overline{B} ».
  4. Contrôle : une proposition et sa négation n'ont jamais la même valeur de vérité.

Exemple

Énoncé. Nie (∃x∈R)(∀y∈R):x≤y2(\exists x \in \mathbb{R})(\forall y \in \mathbb{R}) : x \leq y^{2}.

Négation. On retourne les deux quantificateurs, puis on nie l'inégalité : (∀x∈R)(∃y∈R):x>y2(\forall x \in \mathbb{R})(\exists y \in \mathbb{R}) : x > y^{2}.

Valeurs. La proposition est vraie : x=−1x = -1 convient, car un carré n'est jamais négatif. Sa négation est donc fausse.

Méthoderéfuter par un contre-exemple

  1. Repère le « pour tout » et l'ensemble EE dans lequel varie la lettre.
  2. Teste des valeurs variées : petites, nulles, négatives, non entières, selon EE.
  3. Écris l'élément trouvé, vérifie qu'il appartient à EE, et montre par un calcul que la propriété est fausse pour lui.
  4. Conclus : la proposition universelle est fausse. Un seul élément suffit.

Exemple

Énoncé. La proposition « (∀n∈N):2n+1(\forall n \in \mathbb{N}) : 2^{n} + 1 est premier » est-elle vraie ?

Essais. Pour n=0n = 0, 11 et 22, on obtient 22, 33 et 55, qui sont premiers.

Contre-exemple. Pour n=3n = 3, 23+1=9=3×32^{3} + 1 = 9 = 3 \times 3 n'est pas premier. La proposition est fausse.

AttentionTrois essais ne font pas une démonstration

Dans l'exemple précédent, trois essais réussis ne prouvaient rien : la quatrième valeur met la proposition en défaut. Pour établir un « pour tout », il faut un raisonnement valable pour chaque élément de l'ensemble. Pour le réfuter, un seul élément suffit.

Contraposée, équivalences successives

Méthoderaisonner par contraposée

  1. Écris l'implication à démontrer, P⇒QP \Rightarrow Q.
  2. Forme sa contraposée Q‾⇒P‾\overline{Q} \Rightarrow \overline{P}, en niant avec soin chaque morceau.
  3. Annonce : « Raisonnons par contraposée. » Écris « Supposons Q‾\overline{Q} », puis déduis P‾\overline{P}.
  4. Termine en citant la contraposée : l'implication de départ est démontrée.

Exemple

Énoncé. Soit aa et bb deux entiers. Si abab est impair, alors aa et bb sont impairs.

Contraposée. Avec les lois de Morgan : si aa est pair ou bb est pair, alors abab est pair.

Rédaction. Raisonnons par contraposée. Supposons aa pair : a=2ka = 2k avec kk entier, donc ab=2(kb)ab = 2(kb) est pair. Si bb est pair, on conclut de la même façon. L'implication est démontrée.

Méthodeenchaîner des équivalences

  1. Transforme la proposition pas à pas, et écris ⇔\Leftrightarrow entre deux lignes.
  2. Justifie chaque pas : on peut ajouter le même réel des deux côtés, factoriser, ou multiplier par un réel différent de zéro.
  3. Surveille le signe : multiplier une inégalité par un nombre négatif change son sens.
  4. Si un pas ne se renverse pas, écris ⇒\Rightarrow et contrôle ensuite les solutions trouvées.

Exemple

Énoncé. Résous dans R\mathbb{R} l'inéquation −2x+1>7-2x + 1 > 7.

Équivalences. −2x+1>7⇔−2x>6⇔x<−3-2x + 1 > 7 \Leftrightarrow -2x > 6 \Leftrightarrow x < -3. On a retranché 11, puis divisé par −2-2, qui est négatif : le sens change.

Conclusion. L'ensemble des solutions est ]−∞,−3[]-\infty, -3[.

AttentionUn pas qui ne se renverse pas

x=−3x = -3 implique x2=9x^{2} = 9. Mais x2=9x^{2} = 9 n'implique pas x=−3x = -3, car x=3x = 3 convient aussi. Passer au carré garde l'équivalence lorsque les deux membres sont positifs ou nuls : pour a≥0a \geq 0 et b≥0b \geq 0, a=b⇔a2=b2a = b \Leftrightarrow a^{2} = b^{2}. Sinon, écris ⇒\Rightarrow et contrôle les solutions. Diviser par une expression qui peut s'annuler pose le même problème.

Disjonction des cas, raisonnement par l'absurde

PropriétéRaisonnement par disjonction des cas

Soit PP, QQ et RR trois propositions. Si les implications P⇒RP \Rightarrow R et Q⇒RQ \Rightarrow R sont vraies, et si la proposition « PP ou QQ » est vraie, alors RR est vraie.

En particulier, comme « PP ou P‾\overline{P} » est toujours vraie, si P⇒RP \Rightarrow R et P‾⇒R\overline{P} \Rightarrow R sont vraies, alors RR est vraie : on démontre RR dans le cas où PP est vraie, puis dans le cas où PP est fausse.

Méthodetraiter tous les cas

  1. Découpe en cas qui ne laissent rien de côté : pair ou impair, positif ou négatif, reste d'une division.
  2. Annonce la liste des cas avant de commencer.
  3. Traite chaque cas avec ce qu'il t'apporte : une écriture n=2kn = 2k, une valeur absolue sans barres.
  4. Conclus en rappelant que les cas couvrent toutes les possibilités.

Exemple

Énoncé. Pour tout réel xx, ∣x∣+x≥0\lvert x \rvert + x \geq 0.

Deux cas, qui couvrent tous les réels. Si x≥0x \geq 0, alors ∣x∣=x\lvert x \rvert = x et ∣x∣+x=2x≥0\lvert x \rvert + x = 2x \geq 0. Si x<0x < 0, alors ∣x∣=−x\lvert x \rvert = -x et ∣x∣+x=0\lvert x \rvert + x = 0.

Conclusion. Dans les deux cas, ∣x∣+x≥0\lvert x \rvert + x \geq 0.

PropriétéRaisonnement par l'absurde

Soit PP et QQ deux propositions. Si l'implication P‾⇒(Q et Q‾)\overline{P} \Rightarrow \left(Q \text{ et } \overline{Q}\right) est vraie, alors PP est vraie.

Ainsi, pour démontrer PP, on peut supposer que PP est fausse et en déduire une contradiction, c'est-à-dire une proposition de la forme « QQ et Q‾\overline{Q} », qui est toujours fausse.

Méthoderaisonner par l'absurde

  1. Annonce : « Supposons par l'absurde que PP est fausse. »
  2. Exploite cette hypothèse par des déductions justifiées.
  3. Repère la contradiction et dis contre quoi elle se heurte : une donnée, un résultat connu, l'hypothèse elle-même.
  4. Conclus que PP est vraie.

Exemple

Énoncé. Il n'existe pas de plus grand entier pair.

Rédaction. Supposons par l'absurde qu'il existe un plus grand entier pair pp. On écrit p=2kp = 2k, avec kk entier. Alors p+2=2(k+1)p + 2 = 2(k + 1) est pair. Or p+2>pp + 2 > p : cela contredit le choix de pp.

Conclusion. Aucun entier pair n'est le plus grand.

Raisonnement par récurrence

ThéorèmePrincipe de récurrence

Soit n0n_0 un entier naturel et P(n)P(n) une fonction propositionnelle définie pour tout entier naturel n≥n0n \geq n_0. Si :

  • P(n0)P(n_0) est vraie (initialisation) ;
  • pour tout entier naturel n≥n0n \geq n_0, l'implication P(n)⇒P(n+1)P(n) \Rightarrow P(n+1) est vraie (hérédité) ;

alors P(n)P(n) est vraie pour tout entier naturel n≥n0n \geq n_0.

Méthoderédiger une récurrence

  1. Pose la propriété P(n)P(n) et son premier rang n0n_0.
  2. Initialisation : calcule les deux membres pour n=n0n = n_0 et compare-les.
  3. Hérédité : « Soit n≥n0n \geq n_0 un entier ; supposons P(n)P(n) vraie. » C'est l'hypothèse de récurrence. Montre P(n+1)P(n + 1) et signale où tu l'utilises.
  4. Conclusion : par le principe de récurrence, P(n)P(n) est vraie pour tout entier n≥n0n \geq n_0.

Exemple

Énoncé. Pour tout entier naturel nn, 88 divise 9n−19^{n} - 1.

Initialisation. Pour n=0n = 0, 90−1=0=8×09^{0} - 1 = 0 = 8 \times 0.

Hérédité. Soit n∈Nn \in \mathbb{N} tel que 9n−1=8k9^{n} - 1 = 8k, avec kk entier : c'est l'hypothèse de récurrence. Alors 9n+1−1=9×9n−1=9(8k+1)−1=8(9k+1)9^{n+1} - 1 = 9 \times 9^{n} - 1 = 9(8k + 1) - 1 = 8(9k + 1).

Conclusion. Par le principe de récurrence, 88 divise 9n−19^{n} - 1 pour tout n∈Nn \in \mathbb{N}.

AttentionPas de récurrence sans initialisation

Soit P(n)P(n) : « 99 divise 10n+110^{n} + 1 ». Si 10n+1=9k10^{n} + 1 = 9k, alors 10n+1+1=10(10n+1)−9=9(10k−1)10^{n+1} + 1 = 10(10^{n} + 1) - 9 = 9(10k - 1) : l'hérédité est vraie. Pourtant P(0)P(0) est fausse, car 100+1=210^{0} + 1 = 2. En fait, P(n)P(n) n'est vraie pour aucun entier. Sans initialisation, l'hérédité ne prouve rien.

Choisir son raisonnement

MéthodeQuel raisonnement pour quelle forme d'énoncé ?

Lis d'abord la forme de l'énoncé : elle indique le raisonnement à tenter.

Forme de l'énoncé Raisonnement Première ligne
si AA, alors BB, avec AA facile à exploiter direct « Supposons AA. Montrons BB. »
si AA, alors BB, avec B‾\overline{B} plus simple que AA par contraposée « Raisonnons par contraposée. Supposons B‾\overline{B}. »
une équation, une inéquation, « AA si et seulement si BB » par équivalences successives, ou par deux implications « A⇔…A \Leftrightarrow \dots »
une propriété liée à la parité, au signe, à une valeur absolue par disjonction des cas « Distinguons deux cas. »
« … n'est pas … », « il n'existe aucun … » par l'absurde « Supposons par l'absurde que… »
pour tout entier n≥n0n \geq n_0 : égalité, inégalité, divisibilité par récurrence « Initialisation. »
un « pour tout » que tu crois faux contre-exemple « Pour x=…x = \dots, on obtient… »
un « il existe » exhiber un élément « Le nombre … convient, car… »

Si une voie bloque, essaie la suivante.

À retenirRédiger en devoir

En devoir, annonce le raisonnement choisi : « par contraposée », « par l'absurde », « distinguons les cas ». Introduis chaque objet par « Soit » et chaque hypothèse par « Supposons ». Justifie chaque pas par « car » ou par le nom de la règle employée. Titre les trois étapes d'une récurrence. Termine par une phrase qui reprend l'énoncé.

RemarqueContrôler et prolonger

Avant de démontrer, teste l'énoncé sur deux ou trois valeurs : un contre-exemple t'évite de chercher une preuve impossible. Après, relis chaque « donc » et demande-toi s'il se renverse. La récurrence resservira en 2BAC, et à l'examen de 2BAC SE.