Chapter 1 - Logic and Reasoning PDF

d pl ai re Ex em ———————————————————————– R C IA N O Chapitre 1 – Logique et raisonnements Ly am M U ———————————————————————– de Ly am Table des matières M U R C IA N O Ex em pl ai re de ECG1 - Antoine Lagarde 2 re 1 Logique Vocabulaire et notations . . . . . . . . . . ....

d pl ai re Ex em ———————————————————————– R C IA N O Chapitre 1 – Logique et raisonnements Ly am M U ———————————————————————– de Ly am Table des matières M U R C IA N O Ex em pl ai re de ECG1 - Antoine Lagarde 2 re 1 Logique Vocabulaire et notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Opérations logiques élémentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Implications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 3 5 IA N O Ex em pl ai 1.1 7 R C 2 Différents types de raisonnements Le raisonnement direct . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 Le raisonnement par disjonction de cas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.3 Le raisonnement par contre-exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.4 Le raisonnement par contraposée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.5 Le raisonnement par l’absurde . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6 Le raisonnement par double implication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.7 Le raisonnement par analyse-synthèse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 8 N O Ex em pl ai re de Ly am M U 2.1 10 11 Ly am 4 Méthodes M U R C IA 3 En Python 12 R C IA N O Ex em pl ai re de 5 Blind-test « La logique est l’hygiène du mathématicien. » 1 André Weil Logique 1.1 Vocabulaire et notations pl ai re d Définition (Vocabulaire) Ex em • Une proposition mathématique est une affirmation ayant du sens, elle peut être vraie ou fausse. IA N O • Une propriété est une proposition démontrée propre à un objet mathématique. U R C • Un théorème est une proposition importante qui a été démontrée. Ly am M • Un lemme est un théorème servant à établir un théorème plus important. • Un corollaire est un théorème qui est une conséquence d’un autre théorème. de • Un axiome est une proposition que l’on tient pour vraie sans démonstration, afin de Ex em pl ai re construire une théorie. N O Remarque. Il ne faut pas confondre une proposition logique, notée P, Q ou R dans tout ce chapitre, qui C IA peut être vraie ou fausse, et l’appellation Proposition dans les cours de maths, qui est toujours vraie – M U R que le cours la démontre ou l’admette. Ly am Définition (Quantificateurs) re de • ∃ signifie «il existe». em pl ai • ∃! signifie «il existe un unique». Ex • ∀ signifie «pour tout». U R C IA N O • ∈ signifie «appartient à». am M Proposition (admis) pl ai re de Ly Lorsque les quantificateurs sont du même type, alors ils commutent. Ex em Exemple 1. «∀x ∈ R, ∀m ∈ R+ , f (x) ⩽ m» équivaut à «∀m ∈ R+ , ∀x ∈ R, f (x) ⩽ m». N O «∃x ∈ R, ∃m ∈ R+ , f (x) ⩽ m» équivaut à «∃m ∈ R+ , ∃x ∈ R, f (x) ⩽ m». C IA Remarque. Sinon, il faut faire attention à l’ordre. Par exemple, la proposition : M U R P1 : «∀x ∈ R, ∃m ∈ R+ , f (x) ⩽ m» n’a pas la même signification que P2 : «∃m ∈ R+ , ∀x ∈ R, f (x) ⩽ m». Ly am Exercice 1. Trouvons une fonction f qui vérifie P1 mais pas P2 . de N’importe quelle fonction réelle f vérifie la première proposition. En effet, soit x ∈ R. En choisissant pl ai re m = |f (x)|, on a bien m ∈ R+ et ∀x ∈ R, f (x) ⩽ m. La fonction f : x 7→ x ne vérifie pas la deuxième Exercice 2. Écrivons avec des quantificateurs les énoncés suivants : N O Ex em proposition. IA C R 1 • Pour tout nombre strictement positif x, il existe un nombre non nul dont le carré est strictement inférieur à x. ∀x ∈ R∗+ , ∃y ∈ R∗ , y 2 < x 2 • Il existe unique réel x tel que f (x) soit égal à zéro. d ∃! x ∈ R, f (x) = 0 pl ai re • Le produit de deux réels est commutatif. Ex em ∀x ∈ R, ∀y ∈ R, xy = yx C IA N O Définition U R Deux propositions P et Q sont identiques ou équivalentes si elles sont soit toutes les deux pl ai re Exemple 2. «x2 < y 2 » et «|x| < |y|» sont équivalentes, puisque soit elles sont toutes les deux vraies (si de Ly am M vraies, soit toutes les deux fausses. On note cette relation d’équivalence ≡. em |x| < |y|), soit elles sont toutes les deux fausses (si |x| ⩾ |y|). En revanche, «x2 < y 2 » et «x < y» ne sont IA Opérations logiques élémentaires R C 1.2 N O Ex pas équivalentes puisque pour x = −3 et y = 2, seule la seconde proposition est vraie. am M U Définition (Opérations logiques élémentaires) Ly Soient P et Q deux propositions. re de • Négation : La négation (non P) de la proposition P est la proposition contraire à P, pl ai c’est à dire la proposition qui est vraie lorsque P est fausse, et inversement. em • Et : La proposition (P et Q) est la proposition qui est vraie lorsque à la fois P et Q sont O Ex vraies. IA N • Ou : La proposition (P ou Q) est la proposition qui est vraie lorsqu’au moins une des Ly am M U R C propositions entre P et Q est vraie. Exemple 3. de • La négation de «x2 > 1» est «x2 ⩽ 1». pl ai re • «(x > 3) et (x < 5)» est la même proposition que «3 < x < 5». Ex em • «(x < −2) ou (x ⩾ 1)» est la même proposition que « x ∈] − ∞, −2[∪[1, +∞[». O Remarque. Il existe également une autre opération logique très utile mais hors-programme : ou exclusif, C IA N souvent noté XOR. La proposition (P XOR Q) est vraie dès lors que P est vraie ou Q est vraie, mais pas Ly am l’un ou l’autre». M U R les deux. Dans le langage courant, «ou» signifie généralement ou exclusif, comme dans la phrase «C’est de Axiome (Principe du tiers exclu) R C IA N O Ex em pl ai re Pour toute proposition P, (P ou non P) est toujours vraie. 3 2. (Associativité de ET) P et (Q et R) ≡ (P et Q) et R P ou Q ≡ Q ou P 4. (Commutativité de ET) P et Q ≡ Q et P C R P et (Q ou R) ≡ (P et Q) ou (P et R) U 6. (Distributivité de ET sur OU) M P ou (Q et R) ≡ (P ou Q) et (P ou R) de Ly am 5. (Distributivité de OU sur ET) IA N O 3. (Commutativité de OU) pl ai re P ou (Q ou R) ≡ (P ou Q) ou R Ex em 1. (Associativité de OU) d Soient P, Q et R trois propositions. pl ai re Exemple 4. Illustrons les points 5. et 6. : em • 5 : «Pendant mes vacances, je peux confier mon chat à ma tante, ou appeler un professionnel et Ex le lui confier» est équivalent à «Pendant mes vacances, je peux confier mon chat à ma tante ou N O appeler un professionnel, et confier mon chat à ma tante ou le confier à un professionnel». En effet, M U R à ma tante (redondant si ce choix est déjà fait) soit de le confier à un professionnel. C IA je choisis soit de le confier à ma tante soit d’appeler un professionnel, puis je choisis soit de le confier am • 6 : «Mon secret pour être riche ? Toujours croire en moi, et travailler beaucoup ou jouer au loto» Ly est équivalent à «Mon secret pour être riche ? Toujours croire en moi et travailler beaucoup, ou ai re de toujours croire en moi et jouer au loto». em pl Astuce. On peut également retenir quelques règles simples et très utiles sur les opérateurs logiques: Ex 1. P et VRAI ≡ P IA N O 2. P ou VRAI ≡ VRAI U R C 3. P et FAUX ≡ FAUX am M 4. P ou FAUX ≡ P de Ly Notation. On note P(x) une proposition dépendant d’un paramètre x. pl ai re Proposition (Opérations de négation – admis) N O 1. non(non(P)) ≡ P Ex em Pour passer à la négation on remplace les quantificateurs ∀ par ∃, et inversement. C IA 2. non(∀x ∈ E, P(x)) ≡ ∃x ∈ E, non(P(x)). M U R 3. non(∃x ∈ E, P(x)) ≡ ∀x ∈ E, non(P(x)). Ly am 4. non(∀x ∈ E, ∃y ∈ F, P(x, y)) ≡ ∃x ∈ E, ∀y ∈ F , non(P(x, y)). de 5. non(P ou Q) ≡ non(P) et non(Q). Exemple 5. Illustrons les points 4, 5 et 6 : N O Ex em pl ai re 6. non(P et Q) ≡ non(P) ou non(Q). IA C R Proposition (Opérations avec ET et OU) • 4 : le contraire de «Pour toute serrure, il y a toujours une clé qui lui correspond» est «Il existe une serrure pour laquelle toute clé ne lui correspond pas». • 5 : le contraire de «J’ai perdu mes clés ou on me les a volées» est «Je n’ai pas perdu mes clés, et on ne me les a pas volées». 4 drôle». pl ai re d Exercice 3. Donnons les négations des propositions suivantes : Ex em • 0<x<1 O x ⩽ 0 ou x ⩾ 1, c’est-à-dire x ∈] − ∞, 0] ∪ [1, +∞[ R C IA N • ∀x ∈ [0, 1], f (x) > 0. Ly am M U ∃x ∈ [0, 1], f (x) ⩽ 0 de • ∃M ∈ R, ∀n ∈ N, un ⩽ M . pl ai re ∀M ∈ R, ∃n ∈ N, un > M Ex em Remarque. Le cadre dans lequel se place la négation d’une proposition est important. Par exemple, O considérons n ∈ N. Nier que n est un entier pair implique que n est impair. En revanche, si x ∈ R, nier U Implications M 1.3 R C IA N que x est un entier pair n’implique pas que x est un entier impair : il peut également ne pas être un entier. de Ly am Définition re • Implication : La proposition (P ⇒ Q) est vraie dès lors que non P est vraie ou Q est pl ai vraie. On dit alors que P est une condition suffisante de Q, et Q est une condition Ex em nécessaire de P. U R C IA N O • Équivalence : La proposition (P ⇔ Q) signifie ((P ⇒ Q) et (Q ⇒ P)). M Remarque. Par définition, on a donc (P ⇒ Q) ≡ (non P ou Q). Si P est vraie, alors nécessairement Q doit être vraie. de quoi d’une proposition fausse. Ly am Cela se justifie ainsi: si P est fausse, on peut déduire que Q est vraie car on peut déduire n’importe On a donc ai re (non P ou (P et Q)), c’est-à-dire ((non P ou P) et (non P ou Q)). Ex em pl Puisque (non P ou P) est toujours vraie (principe du tiers exclu), cela revient à (non P ou Q). Exemple 6. • «x > 5 ⇒ x2 > 1» est vraie. «x > 5» est une condition suffisante de «x2 > 1». IA N O «x2 > 1» est une condition nécessaire pour «x > 5». M U R C • «x2 = 4 ⇔ x = 2 ou x = −2» est vraie. Ly am Proposition Ex em pl ai re de La proposition (P ⇔ Q) est vraie si et seulement si P ≡ Q. est utilisée pour relier deux propositions, la seconde pour former une seule proposition. N O Remarque. La relation d’équivalence logique ≡ correspond donc à l’opération logique ⇔. La première IA C R • 6 : le contraire de «Jean est sympathique et drôle» est «Jean n’est pas sympathique, ou il n’est pas Exercice 4. Déterminons si les implications suivantes sont vraies, et le cas échéant quelle proposition est une condition nécessaire ou suffisante pour qui. 5 C’est vrai. Avoir plus de 12 au bac et une condition suffisante pour avoir son bac. Avoir son pl ai re d bac est une condition nécessaire pour avoir plus de 12 au bac. Ex em • x = 3 ⇒ x2 = 9 C’est vrai. Si x = 3 alors x2 = 32 = 9. x2 = 9 est une condition nécessaire pour avoir x = 3. C IA N O x = 3 est une condition suffisante pour avoir x2 = 9. M U R • x2 = 9 ⇒ x = 3. Ly am C’est faux. x = 3 n’est pas nécessaire pour avoir x2 = 9 puisque si x = −3, alors x2 = 9. pl ai re P⇔Q ≡ Q⇔P em 1. (Commutativité de ⇔) de Proposition (Opérations) Ex 2. non(P ⇒ Q) ≡ P et non(Q). M U R C IA N O 3. non(P ⇔ Q) ≡ (P et non(Q)) ou (non(P) et Q). am Exemple 7. Nier la proposition «Si c’est un schtroumpf, il est forcément bleu» revient à affirmer «Cela de Ly peut être un schtroumpf et pourtant n’être pas bleu». ai pl Ex em Définition re Attention. Le contraire de P ⇒ Q n’est pas non(P) ⇒ non(Q). N O • On appelle réciproque de l’implication P ⇒ Q l’implication Q ⇒ P, notée également R C IA P ⇐ Q. Ly am M U • On appelle contraposée de l’implication P ⇒ Q l’implication non Q ⇒ non P. ai re de Proposition (Contraposée) N O Ex em pl L’implication (P ⇒ Q) est équivalente à sa contraposée (non Q ⇒ non P). C IA Exemple 8. La contraposée de «Avoir plus de 12 au Bac» ⇒ «Avoir son bac» est «Ne pas avoir son Bac» M U R ⇒ «Avoir strictement moins de 12 au Bac». Ly am Exercice 5. Écrivons la contraposée des affirmations suivantes. 2. x ⩾ 1 ⇒ f (x) > 0. de 1. x ̸= 1 ⇒ f (x) ̸= 0. f (x) ⩽ 0 ⇒ x < 1 Ex em pl ai re f (x) = 0 ⇒ x = 1 N O Rédaction. Il faut être rigoureux dans les mots que l’on emploie: IA C R • «Avoir plus de 12 au bac» ⇒ «Avoir son bac» • les mots «donc», «d’où», «ainsi», «alors», «ce qui implique», «seulement si» et «par conséquent» correspondent à l’implication ⇒. • les mots «si», «car», «puisque», «parce que», «étant donné que» correspondent à l’implication ⇐. • les mots «c’est-à-dire», «i.e» (du latin id est, c’est-à-dire), «si et seulement si», «ssi», «ce qui équivaut à», «autrement dit», «ce qui revient à» correspondent à l’équivalence ⇔. 6 Différents types de raisonnements 2.1 Le raisonnement direct pl ai re d Méthode Ex em Une manière de démontrer l’implication P ⇒ Q est de commencer par l’hypothèse «Supposons C IA N O que P est vraie», et au terme d’un raisonnement déductif, obtenir alors «Q est vraie». M U R Rédaction. Pour prouver une proposition du type «∀x ∈ E, P(x)», on commencera systématiquement Ly am par «Soit x ∈ E» pour arriver à la conclusion que P(x) est vraie. Ceci signifie que l’on prend x un élément quelconque de E. Si on arrive à prouver P(x) en n’utilisant que pl ai re de les propriétés communes à tous les éléments de E, alors on a bien prouvé ∀x ∈ E, P(x). em Exemple 9. Si on part de «Soit n ∈ N» et que pour prouver P(n) on suppose que n est pair, alors il y Ex a un problème : certains éléments de N sont bien pairs, mais pas tous. Nous sommes donc en train de IA −→ R R C est croissante sur R. 7−→ 3x + 1 Ly am On doit montrer que ∀(x, y) ∈ R2 , x ⩽ y ⇒ f (x) ⩽ f (y). U x M Exercice 6. Sans dérivation, montrons que la fonction f :  R N O prouver ∀n ∈ {2k, k ∈ N}, P(n) au lieu de ∀n ∈ N, P(n). de Soit (x, y) ∈ R2 , x ⩽ y. On a alors 3x ⩽ 3y, donc 3x + 1 ⩽ 3y + 1, donc f (x) ⩽ f (y). Ex Le raisonnement par disjonction de cas O 2.2 em pl ai re Ainsi f est croissante sur R. C IA N Méthode Ly am M U R Pour prouver un résultat, on peut étudier séparément tous les cas possibles. Exercice 7. ai re de • Montrons que ∀x ∈ R, |x| = | − x|. Ex em pl Soit x ∈ R. O – Si x ⩾ 0, |x| = x. −x ⩽ 0 donc | − x| = −(−x) = x. Ainsi |x| = | − x|. C IA N – Si x ⩽ 0, |x| = −x. − x ⩾ 0 donc | − x| = −x. Ainsi |x| = | − x|. Ly am M U R Dans tous les cas |x| = | − x|. N O Ex em pl ai re de • Montrons que ∀n ∈ N, n et n2 ont la même parité. IA C R 2 Soit n ∈ N. – Si n et pair, ∃p ∈ N, n = 2p. n2 = (2p)2 = 4p2 = 2 × 2p2 , donc n2 est pair. |{z} ∈N – Si n est impair, ∃p ∈ N, n = 2p + 1. m = (2p + 1) = 4p2 + 4p + 1 = 2 × 2p2 + 2p ) + 1. | {z } 2 2 ∈N Donc n2 est impair. Dans tous les cas n et n2 ont la même parité. 7 2.3 Le raisonnement par contre-exemple Méthode pl ai re d La négation de «∀x ∈ E, P(x)» est la proposition «∃x ∈ E, non(P(x))». Ainsi il suffit de trouver un exemple de x ∈ E telle que P(x) est fausse pour prouver que «∀x ∈ E, P(x)» est R n’est pas croissante sur R. U   x C −→ R M 7−→ x2 Ly am Exercice 8. Montrons que la fonction f :    R IA N O Ex em fausse. On appelle cela un contre-exemple de la proposition P. f n’est pas croissante signifie : ∃(x, y) ∈ R2 , x ⩽ y et f (x) > f (y). pl ai re em Le raisonnement par contraposée Ex 2.4 de f (−2) = (−2)2 = 4 or f (1) = 12 = 1, donc f (−2) > f (1), donc f n’est pas croissante sur R. IA N O Méthode am M U R C Pour montrer que P ⇒ Q on montre non Q ⇒ non P. de Ly Rédaction. Lorsqu’on utilise un raisonnement par contraposée, on rédige de la manière suivante : «On ai Exercice 9. re suppose non Q . . . . donc non P. Ainsi, par contraposition, P ⇒ Q.». Ex em pl • Soit n ∈ N. Montrons que si n2 est impair alors n est impair. O On suppose n pair. Alors ∃p ∈ N, n = 2p, donc n2 = 4p2 = 2 × 2p2 . Donc n2 est pair. Par R C IA N contraposée, on a le résultat. M U • Soit x ∈ R. Montrer que x ∈ / Q⇒1+x∈ / Q. Ly am Soit x ∈ R. Supposons 1 + x ∈ Q. ∃(p, q) ∈ Z × N∗ , 1 + x = p . q p−q p −1= . Or p − q ∈ Z et q ∈ N∗ , donc x ∈ Q. q q Ainsi. par contraposition, x ∈ / Q⇒1+x∈ / Q. Ex em pl ai re de Donc x = O • Montrons que si x et y sont des réels distincts de 1, alors x ̸= y ⇒ 1 1 ̸= . x−1 y−1 N 1 1 = . Alors x − 1 = y − 1 donc x = y. x−1 y−1 1 1 Ainsi, par contraposition, x ̸= y ⇒ ̸= x−1 y−1 Ly am M U R C IA Soit (x, y) ∈ (R\{1})2 . Supposons Le raisonnement par l’absurde de 2.5 Ex em pl ai re Méthode Pour prouver P, on peut faire l’hypothèse que P est fausse (i.e. non P est vraie). Si avec cette non P est fausse et donc que P est vraie. R C IA N O hypothèse on tombe sur une absurdité, c’est que notre hypothèse était fausse, c’est à dire que Rédaction. Pour montrer par l’absurde que P est vraie, on rédige ainsi : «Supposons par l’absurde que non P est vraie .... ce qui est absurde, donc P est vraie». 8 • Soit (un ) la suite définie par u0 = 1, et ∀n ∈ N, un+1 = 2u2n + 3. Montrons que (un ) ne converge pas. d Supposons par l’absurde que (un ) converge. On note ℓ sa limite. n→+∞ pl ai re On a alors un+1 −→ ℓ et 2u2n + 3 −→ 2ℓ2 + 3. n→+∞ Ex em Ainsi par passage à la limite, ℓ = 2ℓ2 + 3. D’où 2ℓ2 − ℓ + 3 = 0. Or on a ∆ = (−1)2 − 4 × 2 × 3 = −23 < 0. Il n’existe donc pas de ℓ ∈ R vérifiant ℓ = 2ℓ2 + 3 : IA N O absurde. U R C Donc (un ) ne converge pas. Ly am M • Soit a ∈ R+ tel que ∀ε > 0, a < ε. Montrons que a = 0. Soit a ∈ R+ tel que ∀ε > 0, a < ε. Supposons par l’absurde que a ̸= 0. a , 2 i.e a 2 < 0 i.e a < 0. de > 0, on obtient a < a 2 pl ai re Dans ce cas, a > 0. En choisissant ε = em Absurde. Donc a = 0. Ex Remarque. De nombreux raisonnements par l’absurde sont en fait des contraposées cachées. Montrons IA C R re Le raisonnement par double implication ai 2.6 de Ly am M U a a Soit a ∈ R+ tel que a ̸= 0. Alors a > 0 donc a > > 0. Ainsi ∃ ε = > 0, a > ε. 2 2
On a montré a ̸= 0 ⇒ ∃ε > 0, a > ε .
Par contraposée, ∀ε > 0, a < ε ⇒ a = 0. N O par exemple l’exercice précédent par contraposée: Ex em pl Méthode R C IA N O Pour démontrer que P ⇔ Q, on peut démontrer P ⇒ Q et Q ⇒ P. am M U
Exercice 11. Soient a, b ∈ R, montrons que : ∀x ∈ R, ax + bex = 0 ⇐⇒ a = b = 0. de re a × 1 = 0 donc a = 0 pl Pour x = 1, a × 0 + be0 = 0 donc b = 0 ai Pour x = 0, Ly (⇒) Supposons ∀x ∈ R, ax + bex = 0 Ex em Donc ∀x ∈ R, ax + bex = 0 ⇒ a = 0 et b = 0. O (⇐) Réciproquement, supposons a = 0 et b = 0. Soit x ∈ R.. Alors ax + bex = 0x + 0ex = 0. IA N Donc a = b = 0 ⇒ ∀x ∈ R, ax + bex = 0. Ly am M U R C On a bien ∀x ∈ 0, ax + bex = 0 ⇔ a = b = 0. 2.7 Le raisonnement par analyse-synthèse ai re de Méthode • L’analyse : on raisonne sur une hypothétique solution du problème et on accumule des déductions de propriétés qu’elle doit vérifier, du seul fait qu’elle est solution. N O Ex em pl Un raisonnement par analyse-synthèse se déroule en deux étapes : IA C R Exercice 10. • La synthèse : on examine tous les objets vérifiant les conditions nécessaires précédemment accumulées (ce sont les seuls candidats possibles à être des solutions) et on détermine, parmi eux, lesquels sont réellement des solutions. 9 ne reste plus qu’un seul candidat qui les vérifie. Dans ce cas, cette première phase prouve l’unicité de la solution (sous réserve d’existence). La phase de synthèse permet alors ou bien de montrer l’existence d’une pl ai re d solution (si le candidat répond au problème), ou bien de constater qu’il n’y a aucune solution. Ex em L’analyse-synthèse est donc particulièrement adaptée pour démontrer des propriétés d’existence et d’unicité du type «∃! x ∈ E, P(x)». Dans ce cas, l’analyse prouve l’unicité sous réserve d’existence et fournit une O expression de la solution recherchée. La synthèse (qui se contente de reprendre le candidat déterminé par C R U 6 + x = x. ∆ = (−1)2 − 4 × 1 × (−6) = 25 = 52 . On a alors x1 = 1−5 2 et = −2 x2 = 1+5 = 3. 2 IA N O On vient de prouver que x solution ⇒ x = −2 ou x = 3. p √ Réciproquement : si x = −2, 6 + (−2) = 4 = 2 ̸= −2. Ainsi −2 n’est pas solution. √ √ Si x = 3, 6 + 3 = 9 = 3. Ainsi 3 est solution. pl ai re Donc 6 + x = x , d’où x − x − 6 = 0. de 2 em 2 √ 6 + x = x. Ly am Soit x une solution de √ M • Déterminons les solutions réelles de l’équation Ex Exercice 12. IA N l’analyse) justifie l’existence. M U R C Donc x solution ⇔ x = 3. Ly am • Déterminons l’ensemble des entiers naturels n multiples de 3 dont le carré est impair. de Analyse : soit n ∈ N vérifiant ces conditions. ai re Donc ∃p ∈ N, n = 3p et ∃q ∈ N, n2 = 2q + 1. em pl Ainsi 9p2 = 2q + 1 donc 9p2 est impaire. Puisque 9 est impaire, nécessairement p2 doit être Ex impaire. En effet impaire × paire = paire et impaire × impaire = impaire. IA N O Donc p est impaire (cf exercice 9). R C Synthèse : soit p un entier impair et n = 3p. Donc n est multiple de 3, et n2 = 9p2 . Puisque M U p2 est impaire, n2 est bien impair (impaire × impaire = impaire). pl ai En Python Ex em 3 re de Ly am On a bien montré que l’ensemble recherché est {3p, p ∈ N impaire}. O Définition (Booléen) IA N Un booléen (en Python : bool) est un type d’objet informatique pouvant prendre seulement Ly am M U R C deux valeurs : True (vrai) ou False (faux). de Exemple 10. • b = True déclare un objet booléen qui s’appelle b et dont la valeur est True. Ex em pl ai re • condition = False déclare un objet booléen qui s’appelle condition et dont la valeur est False. N O Remarque. IA C R Remarque. Il arrive souvent que la phase d’analyse produise des conditions nécessaires si restrictives qu’il • Les booléens ne sont pas des nombres, donc ni de type int (integer, i.e entier), ni de type float (flottant, i.e décimal). Néanmoins, si on les force à se comporter comme des nombres, True se convertit en 1 et False se convertit en 0. Par exemple si on écrit b = True puis print(b + 1), cela affiche 2. • Les conditions logiques sont des booléens. Par exemple (a == 2) est True si a vaut 2, False sinon. On peut enregistrer cette valeur de vérité dans une variable : b = (a==2). 10 Les commandes if et elif requièrent une condition if b: print("Hello") logique ou un booléen. Le programme ci-contre af- pl ai re d elif c: print("Hola") fiche Hello si b est vrai, Hola si b est faux et c est else: print("Bonjour") IA N O Ex em vrai, Bonjour sinon. Ly am affiche Hello si a vaut 3. de Attention. Les égalités dans les conditions logiques prennent un double égal, tandis que les affectations pl ai re d’une valeur à une variable en prennent un. Ainsi : em • a == 3 est True si a vaut 3, False sinon. O Ex • a = 3 affecte 3 à la variable a. C IA N Commandes Ly am M U R Les opérateurs pour manipuler les booléens sont and (et), or (ou), not (non), xor (ou exclusif) ai em • (u > 0) or (v > 0) est True si u ou v est strictement positif. re de • b and c est True si b est True et c aussi, False sinon. pl Exemple 11. N O Ex • if (a >= 0) and not b: s’exécute si a est strictement positif et si le booléen b est False. C IA Méthodes M U R 4 −→ Soit .. ∈ .. . Alors ... Mq ∃.. ∈ .., ... = ... −→ Trouver un exemple. Mq ∃.. ∈ .., ... ̸= ... −→ Ly de re ai pl Ex em Trouver un exemple OU Par l’absurde : supposons que pour tout .. ∈ .., on a ... = ... . Alors ..., absurde, d’où le résultat. Soient .. ∈ .. et .. ∈ .. . Alors ... −→ Soit .. ∈ .. . Alors en posant .. = ..., on a bien ... Mq ∃.. ∈ .., ∀.. ∈ .., on a ... −→ On pose .. = ... . Soit .. ∈ .., alors on a bien ... −→ Existence : on pose x = ... . On a bien ... N Ly am M U R C Mq ∀.. ∈ .., ∃.. ∈ .., tq ... O −→ IA Mq ∀.. ∈ .., ∀.. ∈ .., on a ... re de Mq ∃! x ∈ .., ... Ex em pl ai Mq ∀.. ∈ .., ∃! x ∈ .., tq ... −→ Unicité : soit y vérifiant également ... . Alors ... donc x = y. Soit .. ∈ .. . Alors en posant x = ..., on a bien ... De plus, si y ∈ .. vérifie aussi ..., alors x = y. Mq ∃! x ∈ .., ∀.. ∈ .., on a ... −→ Montrer que x ∈ A ⇒ x ∈ B −→ Soit x ∈ A. Alors par définition ... d’où x ∈ B. La proposition «x ∈ A ⇒ x ∈ −→ Contre-exemple : prenons x = ... . x ∈ A et pourtant ... donc x ∈ / B. N O am Mq ∀.. ∈ .. on a ... B» est-elle vraie ? U M préalable. Une condition logique fonctionne également: par exemple, si a est un entier, if (a == 3): print("Hello") R C Remarque. Pour faire fonctionner le script ci-dessus, il faut bien évidemment définir les booléens b et c au IA C R Méthode (if et elif) On pose x = ... . Soit .. ∈ .., alors on a bien ... De plus, si y ∈ .. vérifie également ∀.. ∈ .., ... alors ... donc x = y. Donc la proposition est fausse. 11 −→ Ou bien x ∈ A, ou bien x ∈ / A. Si x ∈ / A, alors ... donc x ∈ B. Mq .. ∈ / .. ⇒ .. ̸= .. −→ Contraposée : mq .. = .. ⇒ .. ∈ .. Mq x ∈ /A −→ Supposons x ∈ A, alors ..., absurde, donc x ∈ / A. Mq si x ∈ A, alors x ∈ /B −→ Mq si n2 ... alors n ... −→ Par contraposée : si n ... alors en passant au carré, n2 ... Mq ... n’est pas ... −→ Par l’absurde : supposons qu’elle le soit. Alors ... Mq P si et seulement si Q −→ O IA N C R U M Ly am P ⇔ ... ⇔ Q OU (⇒) puis (⇐) de pl ai re Supposons non P. Alors ... donc non Q. em Analyse-synthèse : −→ - Soit x une solution de l’équation. Alors ... donc x vérifie ... Ex tions de ... = ... Ex em Soit x ∈ A tq x ∈ B. Alors ..., mais par ailleurs ..., absurde. Donc x∈A⇒x∈ / B. OU Supposons P. Alors ... donc Q. Déterminer l’ensemble des solu- pl ai re d Mq on a x ∈ A ou x ∈ B N O - Réciproquement, si x vérifie ..., alors ... donc x est solution de U Synthèse : on pose y = ... et z = x − y. Alors ... donc y ∈ .., de plus am somme de ... Analyse : soit x = y + z où y ∈ .. et z ∈ .. . Alors on a ... donc y = ... −→ M Mq tout ... peut s’écrire comme R C IA l’équation. re ai vérifiant ... = ... Analyse : soit x vérifiant ... = ... . Alors nécessairement ... donc −→ x = .. pl Montrer qu’il existe un unique x de Ly ... donc z ∈ .. . Enfin on a bien x = y + z. O contradictoire, d’où le résultat. C IA fiant ... Si x ∈ .. vérifie ..., alors d’une part ..., d’autre part ... . C’est −→ N Mq il n’existe aucun x ∈ .. véri- Ex em Synthèse : si x = .., il vérifie bien ... = ... U R OU Si x ∈ .. vérifie ..., alors ... donc x vérifie aussi P . M Réciproquement, si x vérifie P, il ne peut pas vérifier ... pl ai Blind-test Ex em 5 re de Ly am Donc il n’existe aucun x ∈ .. vérifiant ... Dfnt : proposition = ... N IA R M U lemme = ... C théorème = ... O propriété = ... Axm : principe du tiers exclu Mtd : raisonnement direct Ppst : opérations avec ET et OU (6) Mtd : raisonnement par disjonction de cas Ppst : opérations de négations (6) Mtd : raisonnement par contre-exemple Dfnt : implication = ... Mtd : raisonnement par contraposée équivalence = ... Ly am corollaire = ... axiome = ... de Dfnt : quantificateurs (4) re Ppst : lorsque ..., commutent Mtd : raisonnement par double impl. Dfnt : réciproque = ... Dfnt : bool est ... Ppst : opérations avec ⇒ et ⇔ (3) Dfnt : propositions équivalentes = ... Ex em pl ai contraposée = ... Ppst : P ⇔ Q est équivalente à ... R C IA N O Dfnt : opérations logiques élémentaires (3) Mtd : raisonnement par l’absurde Ppst : P ⇔ Q vraie ssi ... 12 Mtd : raisonnement par analyse-synthèse Mtd : if et booléens Cmd : opérateurs de booléens (4)