Cours, Chapitre de Mathématiques de niveau CPGE

Tpautrel

Description

Logique et raisonnements
Cours, Chapitre en Mathématiques (2011) pour CPGE 1 MPSI

Sujets

• Ressource
• ressources pédagogiques
• École
• Lycée
• exercices
• Cours
• Devoir scolaire
• Devoir surveillé
• Annales

Informations

• Publié par: ressources-pour-le-superieur
• Nombre de lectures: 76
• Langue: Français

Extrait

Ch1: Logique et raisonnements

Ce chapitre a pour but de récapituler des raisonnements, revoir certains symboles et les notions propres à la logique. Ces notions sont incontournables pour un étudiant en MPSI.

I) Logique: 1. Propositionet conjonctions:

MPSI

On appellepropositiontoute « phrase » p sur laquelle on peut poser la question: p est-elle vraie? On appelleconnecteur logiquetout moyen de construire une proposition à partir d'une ou plusieurs propositions. Ex: « ou », « et », « si... alors » sont des connecteurs logiques.

Quelques exemples:

> La négation NON: Une proposition « non p » est vraie si p est fausse, et fausse si p est vraie. Remarque: p et « non (non p » sont équivalentes.

> La conjonction ET> La disjonction OU: Soit p et q deux propositions. « p et q »est vraie si p et q sont vraies, et fausse dans les« p ou q » est vraie si p est vraie ou si q est vraie (voire autres cas.même les deux); et fausse dans l'unique cas où p et q sont fausses toutes les deux. Remarque:le OU est inclusif. Remarque: Pour démontrer que « p ou q » est vraie, on suppose que p est fausse et on montre que q est vraie. – Les propositions « non (p et q) » et « (non p) ou (non q) » sont équivalentes. – – Les propositions « non (p ou q) » et « (non p) et (non q) » sont équivalentes.

Ces deux dernières remarques correspondent auxlois de MORGAN.

Démonstration:(sous la forme d'une table de vérité)

1ère loi de MORGAN p q V V V F F V F F

2ème loi de MORGAN p q V V V F F V F F

Non pNon q F F F V V F V V

P et q V F F F

Non (p et q) F V V V

(non p) ou (non q) F V V V

Non pNon qP ou qNon (p ou q)(non p) et (non q) F FV FF F VV FF V FV FF V VF VV

2. Lesquantificateurs: > Définitions:

Les quantificateurs sont des symboles permettant d'écrire des phrases de manière plus synthétique, plus simple à lire et à écrire (avec un peu d'habitude!).

∀ ∃ > Le quantificateur universel: >Le quantificateur existentiel: Ce symbole signifie « quel que soit ».Ce symbole signifie « il existe ». ∀x∈ℝ, fx0∃x∈ℝ /fx0 Ex: setraduit en français par « quelEx: setraduit par « il existe un réel x fx0fx0 que soit le nombre réel x, on a toujours». telque ». La barre « / » n'est pas indispensable mais facilite la lecture en rappelant le « tel que ». Ex: Soit y un réel positif. Si l'on veut écrire que y a une racine carrée positive, on peut écrire: ∃x∈ℝ /y=x² avec x0 . Remarques: – ∀x∈PE ,x Beaucoup de théorèmes mathématiques se basent sur. Pour démontrer qu'un énoncé universellement quantifié est vrai, il faut démontrer. La démonstration commencera donc par écrire « Soit x un élément de E. », afin de fixer un élément x pour ensuite montrer que ce x vérifie la propriété demandée. Si on avait à démontrer qu'un énoncé universellement quantifié est faux, il faut juste trouver un contre-exemple. – ∃x∈E/Px De même, certains théorèmes se forment comme cela:. Pour montrer qu'un énoncé existentiellement quantifié est vrai, il faut juste trouver un exemple tandis que montrer qu'il est faux impose de le démontrer. Attention! Une proposition mathématique peut contenir plusieurs quantificateurs. La compréhension du premier coup devient alors plus délicate. ∀x∈ℝ,∃y∈ℝ /fyx Ex: setraduit en français par « pour tout réel x, on peut trouver un réel y tel que fyx . >Interversion: De deux quantificateurs identiques:De quantificateurs différents: On peut intervertir deux quantificateurs existentielsEn revanche, l'inversion d'un quantificateur existentiel et d'un consécutifs (resp. quantificateurs universels).quantificateur universel change le sens de la proposition. ∀x∈ℝ,∀y∈ℝ, fxfy ∀x∈ℝ,∃y∈ℝ /yx Ex: revientà direEx: (cequi est vrai) ∀y∈ℝ,∀x∈ℝ, fxfy ∃ y∈ℝ/ ∀x∈ℝ, yx . (cequi est évidemment faux) 3. Implication,équivalence, CNS: Une démonstration mathématique consiste, à partir d'hypothèses, à parvenir à la conclusion cherchée, en utilisant les règlesde déduction logique. Pour éviter d'avoir un texte lourd reproduisant littéralement ces déductions logiques (« si une telle propriété est vraie, alors... »), on utilise des symboles qui clarifient aussi bien la rédaction que le raisonnement lui-même. > Implications: Elle correspond au raisonnement logique « classique »: « si ... alors... ». Dire qu'une propositionp implique qest vraie signifie quesi la proposition p est vraie, alors la proposition q l'est p⇒q aussi. On utilise le symbole=>qui signifie «implique». Ainsi,se lit « p implique q ».

Ex: Si x et y sont deux nombres réels, alors la proposition suivante est vraie x²=y²⇒x=y est fausse.

xy0⇒x²y²

, tandis que

Remarques: Pour démontrer qu'une implication p => q est vraie, on suppose p vraie et on montrer sous cette hypothèse que – q est vraie. Les propositions «non( p => q )» et « p et (non q) » sont équivalentes, ainsi on peut démontrer qu'une – implication est fausse en montrant que « p et (non q ) » est vraie.

> Contraposée d'une implication:

Lacontraposéed'une proposition p => q est la proposition non q => non p. Si l'une des deux est vraie, alors l'autre l'est aussi. Ex: Soient p :« il pleut » et q: « la pelouse est mouillée ». La proposition p => q est vraie et non q => non p est vraie aussi. Ici la réciproque q => p est fausse (on peut avoir arrosé la pelouse)

Remarque:Montrer que p => q est vraie revient rigoureusement à montrer que non q => non p est vraie. Dans certains problèmes, il peut apparaître plus facile de démontrer la contraposée d'une implication plutôt que de montrer directement l'implication.

> Équivalence:

La proposition « p équivaut à q » est vraie quand les deux implications « p implique q » et « q implique p » sont vraies, c'est-à-dire que: - si p est vraie alors q est vraie - si q est vraie alors p est vraie. ⇔ ⇒⇐ On utilise le symbolequi signifie « équivaut à ». Il signifie bienet . x²−3x2=0⇔x=1ou x=2 Ex: La proposition suivante est vraie (x est un nombre réel). Cela signifie que x²−3x2=0⇒x=1ou x=2x=1ou x=2⇒x²−3x2=0 et réciproquement,. Au final, on dira que x = 1 ou x = 2 si et seulement si x² – 3x + 2 = 0.

Remarque:Pour montrer qu'une équivalence p <=> q est vraie, on démontrer l'implication p => q puis que q => p.

> CN, CS, CNS: Soient p et q deux propositions. Lorsque p implique q est vraie, on dit que: ➢ - q est unecondition nécessairepour que p soit vraie. Elle est nécessaire dans le sens où si elle était fausse, alors p serait également fausse. (CN) - p est unecondition suffisantepour que q soit vraie. Elle est suffisante dans le sens o* dès qu'elle est vérifiée, q l'est aussi. (CS) Lorsque p et q sont équivalentes, on dit que p est vraie à lacondition nécessaire et suffisante(CNS) que q ➢ soit vraie.

II) Raisonnements:

1. Leraisonnement par récurrence:

∀n∈ℕ, P Soient P 0 , P 1 , ... une suite infinie de propositions, et on veut démontrer que n . kn P⇒P Principe: Si P n0 est vraie et si pour tout entier 0 , k k1 , alors toutes les propositions sont vraies.  Un raisonnement par récurrence comporte donc 3 étapes: l'initialisation – l'hérédité – la conclusion –

Exemple: Démontrer que tout entier est soit pair, soit impair.

Remarque:Il faut toujours commencer l'hérédité par « supposons qu'il existe un rang n pour lequel P n est vraie ». Le fait d'écrire « On suppose que pour tout entier n, P n est vraie » montre que vous prenez la proposition vraie à tous les rangs, et donc la démonstration devient obsolète!. Il se peut que l'on ait besoin quelque fois de P n , P n-1 ,...voire de toute la suite P 0 ,P 1 , ..., P n . Dans ces cas là, on parle de récurrence forte.

=− =∀ ∈ℕ= uu1,u5n ,u  3u  −2u Exemple: On pose n la suite de termes réels définie par 0 1 et n2n1n . n u=6×2−7 Démontrer que n . (Ici on parle de double récurrence). ..........................................................................................................................................................................................

2. Leraisonnement par l'absurde: Principe: Pour montrer qu'une proposition P est vraie, on suppose qu'elle est fausse et on en déduit une contradiction. Exemple: Démontrer l'irrationalité de  2 . ..........................................................................................................................................................................................

3. Leraisonnement par contraposée:

La contraposée de l'implication P => Q est la proposition non Q => non P. Or, une implication est équivalente à sa contraposée. (voir plus haut)

Conséquence: Pour démontrer l'implication P=> Q, on peut essayer de démontrer la contraposée non Q => non P, qui est parfois plus simple.

Exemple: Démontrer que si le carré d'un entier naturel n est pair, alors n est pair. ..........................................................................................................................................................................................

4. Leraisonnement par disjonction des cas:

Pour démontrer P=> Q, on étudie tous les cas possibles pouvant se présenter afin de pouvoir conclure.

Exemple: Démontrer que, pour tout entier naturel n, n(n+1) est pair.