La logique, depuis le tout débutPour comprendre l'implication, et tout ce qui est construit dessus.

0Mode d'emploi

Dans tes notes, tu as écrit : « partiel = 50 % de démonstration ». Garde cette phrase en tête pendant tout ce cours. Une démonstration, c'est une chaîne d'implications : « ceci est vrai, donc cela est vrai, donc cela aussi… ». La logique est la grammaire de cette chaîne. Si le mot « implique » reste flou, toutes les démonstrations du semestre le seront aussi. À l'inverse, une fois l'implication vraiment comprise, une grosse partie du cours de suites devient lisible.

Les symboles, et comment les lire à voix haute

Où trouver quoi

• •Qu'est-ce qu'une proposition ?
• •Non, et, ou, tables de vérité
• •L'implication (là où tu as décroché)
• •Condition nécessaire, suffisante
• •Réciproque et contraposée
• •Nier une implication
• •L'équivalence
• •Le labo : vérifie tes tables
• •Règles de calcul, exercices 3 et 4
• •Quantificateurs ∀ et ∃
• •Méthodes de démonstration
• •La récurrence
• •Relecture de tes notes
• •Ta feuille d'exercices

1Les rappels indispensables : ensembles et nombres

La logique parle sans arrêt d'ensembles et de nombres. Avant de commencer, on remet à plat le vocabulaire du collège et du lycée qu'elle utilise. Si tout ça te paraît connu, lis quand même en diagonale : il y a deux ou trois pièges qu'on retrouvera plus loin.

1.1 Un ensemble, c'est un sac

Un ensemble est une collection d'objets, qu'on appelle ses éléments. Pense à un sac : on regarde seulement ce qu'il y a dedans. On écrit un ensemble entre accolades : {1, 2, 3}. L'ordre ne compte pas ({1, 2, 3} et {3, 1, 2} sont le même sac), et un objet est dedans ou pas dedans, il n'y est pas « deux fois ».

• 2 ∈ {1, 2, 3} se lit « 2 appartient à l'ensemble {1, 2, 3} ».
• 5 ∉ {1, 2, 3} se lit « 5 n'appartient pas à… ».
• ∅ est l'ensemble vide : le sac sans rien dedans.

1.2 Les ensembles de nombres

Trois décorations reviennent souvent : une étoile enlève le zéro (ℝ* = les réels sauf 0, ℤ* = les entiers sauf 0), un petit + garde les positifs (ℝ⁺), un petit − garde les négatifs (ℝ⁻). Ton polycopié écrit « q ∈ ℤ* » pour dire « q est un entier non nul », parce qu'on ne divise jamais par 0.

1.3 Inclusion, intersection, réunion

Prenons A = {1, 2, 3, 4} et B = {3, 4, 5}.

• Intersection A ∩ B : ce qui est dans A et dans B. Ici {3, 4}.
• Réunion A ∪ B : ce qui est dans A ou dans B (ou dans les deux). Ici {1, 2, 3, 4, 5}.
• Privé de A ∖ B : ce qui est dans A mais pas dans B. Ici {1, 2}. Ton polycopié écrit ℝ ∖ ℚ pour « les réels qui ne sont pas rationnels », c'est-à-dire les irrationnels.
• Inclusion A ⊂ B : « A est inclus dans B », ce qui veut dire que tout élément de A est aussi un élément de B. Par exemple {3, 4} ⊂ B, mais A n'est pas inclus dans B, puisque 1 est dans A et pas dans B.

1.4 Un ensemble décrit par une propriété

Au lieu de lister les éléments, on peut décrire un ensemble par une règle :

{ n ∈ ℕ | n < 4 } = {0, 1, 2, 3}

Ça se lit : « l'ensemble des n appartenant à ℕ tels que n < 4 ». La barre | (ou le point-virgule ; dans ton polycopié) veut dire « tels que ». Toi qui programmes, c'est exactement une liste en compréhension en Python : [n for n in N if n < 4]. On parcourt l'ensemble de départ, et on garde ceux qui passent le test.

Les intervalles sont des ensembles de ce type : [0, 1] = {x ∈ ℝ | 0 ≤ x ≤ 1}. Un crochet tourné vers le nombre l'inclut, un crochet tourné vers l'extérieur l'exclut : [0, 1[ contient 0 mais pas 1.

1.5 Les inégalités, et un premier piège

a < b : « a est strictement inférieur à b ». a ≤ b : « a est inférieur ou égal à b ».

Question qui surprend souvent : 3 ≤ 3 est-il vrai ? Oui. « Inférieur ou égal » est vrai dès que l'un des deux est vrai, et ici « égal » est vrai. C'est ton premier « ou » mathématique, on y reviendra.

Et a ≤ x ≤ b est un raccourci pour « a ≤ x et x ≤ b ».

1.6 Pair, impair, premier, valeur absolue

• Un entier n est pair s'il existe un entier k tel que n = 2k (exemples : 0, 6, −4). Il est impair s'il existe un entier k tel que n = 2k + 1 (exemples : 7 = 2×3 + 1, −1 = 2×(−1) + 1). Ces deux écritures sont les outils de base de beaucoup de démonstrations.
• Un entier p ≥ 2 est premier s'il a exactement deux diviseurs positifs : 1 et lui-même. 2, 3, 5, 7, 11, 13… 1 n'est pas premier (un seul diviseur), et 2 est le seul nombre premier pair.
• La valeur absolue |x| est la distance entre x et 0 : |−3| = 3, |5| = 5. Dire |x| ≤ M, c'est dire que x est à distance au plus M de zéro, donc que −M ≤ x ≤ M. Ça servira pour l'exercice 9.

2La proposition : la brique de base

Une proposition (on dit aussi une assertion) est une phrase qui est soit vraie, soit fausse. Jamais les deux à la fois, jamais « un peu vraie ».

Une proposition a donc une valeur de vérité : V ou F. Tu connais déjà ça sous un autre nom : c'est un booléen. V correspond à True (ou 1), F à False (ou 0). Toute la logique de ce chapitre, c'est de l'algèbre de booléens, celle que tu manipules dans tes if.

« Soient P et Q deux propositions »

C'est la première ligne de ton polycopié, et elle mérite d'être décortiquée. « Soient » veut dire « prenons ». P et Q sont des lettres qui remplacent des propositions quelconques, exactement comme en algèbre la lettre x remplace un nombre quelconque. Quand on écrit (a + b)² = a² + 2ab + b², ça marche pour tous les nombres a et b. De la même façon, quand on écrit une règle de logique avec P et Q, elle marche quelles que soient les propositions qu'on met à leur place.

En programmation, c'est comme déclarer deux variables de type booléen, P: bool et Q: bool, sans savoir encore ce qu'elles vaudront. Et comme chacune ne peut valoir que V ou F, il n'y a que 4 situations possibles pour le couple (P, Q). C'est pour ça que les tables de vérité existent : on peut tester tous les cas.

3Non, et, ou : les connecteurs

Les connecteurs fabriquent de nouvelles propositions à partir d'anciennes, comme les opérations +, × fabriquent de nouveaux nombres. La valeur de vérité du résultat dépend seulement de celles de P et de Q. On décrit chaque connecteur par sa table de vérité : la liste de tous les cas possibles, avec le résultat.

3.1 La négation : non P, noté ¬P

¬P est vraie quand P est fausse, et fausse quand P est vraie. C'est l'interrupteur qui inverse. En Python : not P.

Exemple : P = « il pleut ». ¬P = « il ne pleut pas ». Et ¬(¬P) = P : nier deux fois revient au départ (« il n'est pas vrai qu'il ne pleut pas » = « il pleut »).

3.2 La conjonction : P et Q, noté P ∧ Q

P ∧ Q est vraie seulement quand P et Q sont vraies toutes les deux. Il suffit qu'une seule soit fausse pour que tout soit faux. En Python : P and Q.

3.3 La disjonction : P ou Q, noté P ∨ Q

P ∨ Q est vraie dès qu'au moins une des deux est vraie. Elle n'est fausse que si les deux sont fausses. En Python : P or Q.

3.4 Construire une table de vérité, méthodiquement

Pour une formule plus compliquée, on procède comme pour un calcul avec des parenthèses : de l'intérieur vers l'extérieur, une colonne par étape. C'est exactement ce que tu as fait dans tes exercices 1 et 2, et tes tables sont justes.

1. Compte les lignes : avec n lettres, il y a 2ⁿ lignes (2 lettres → 4 lignes, 3 lettres → 8 lignes).
2. Remplis les colonnes des lettres sans rien oublier. Avec P, Q, R : la colonne P alterne par blocs de 4 (VVVVFFFF), Q par blocs de 2 (VVFFVVFF), R une fois sur deux (VFVFVFVF). Tu reconnais le principe : c'est comme compter en binaire, la dernière colonne change le plus vite.
3. Ajoute une colonne par morceau de la formule, en commençant par les plus petits.

Exemple, qu'on va retrouver très bientôt : la table de (¬P) ∨ Q.

Retiens la dernière colonne : V, F, V, V. Un seul F, à la deuxième ligne. Garde-la dans un coin de ta tête.

3.5 Tautologie, contradiction, formules équivalentes

• Une tautologie est une formule toujours vraie, quelles que soient les valeurs des lettres. Tu l'as noté : « tautologie = tout le temps vrai ». Exemple : P ∨ ¬P (« il pleut ou il ne pleut pas ») : vraie dans les deux cas. C'est le tiers exclu.
• Une contradiction est une formule toujours fausse. Exemple : P ∧ ¬P (« il pleut et il ne pleut pas »).
• Deux formules sont équivalentes si elles ont la même dernière colonne dans leur table de vérité : elles disent la même chose, avec d'autres mots. On l'écrit avec le symbole ⇔. Par exemple ¬(¬P) ⇔ P.

4L'implication, pas à pas

On y est. C'est la partie la plus importante de tout le cours : prends ton temps, relis-la deux fois si besoin, et fais les exercices. Je vais te montrer l'implication sous cinq angles différents : une promesse, un argument mathématique, un dessin, un jeu de cartes, et une formule. Si un angle ne te parle pas, un autre te parlera.

4.1 L'implication, c'est une promesse

Je te fais cette promesse : « Si tu as la moyenne au partiel, alors je t'offre un kebab. »

Appelons P = « tu as la moyenne » et Q = « je t'offre un kebab ». Ma promesse, c'est P ⇒ Q. La question de la logique est : dans quels cas ai-je menti ? Il y a 4 scénarios possibles.

• Tu as la moyenne, je t'offre le kebab (V, V). J'ai tenu parole. La promesse est vraie.
• Tu as la moyenne, je ne t'offre rien (V, F). Là, j'ai menti. La promesse est fausse. C'est le seul cas de mensonge.
• Tu n'as pas la moyenne, je t'offre quand même le kebab, pour te consoler (F, V). Ai-je menti ? Non : ma promesse ne disait rien sur ce qui se passe si tu rates. Elle est vraie.
• Tu n'as pas la moyenne, je ne t'offre rien (F, F). Ai-je menti ? Non plus : la condition n'était pas remplie, ma promesse n'a jamais été mise à l'épreuve. Elle est vraie.

Les deux derniers cas gênent souvent. Pense à un tribunal : on est innocent tant qu'on n'a pas été pris en flagrant délit. Une implication est considérée comme vraie tant qu'on ne l'a pas prise en défaut, et la seule façon de la prendre en défaut, c'est le cas « P vrai et Q faux ». Et comme en logique il n'existe que deux valeurs, « pas fausse » veut dire « vraie ».

4.2 Pourquoi cette convention n'est pas un caprice

Tu te demandes peut-être : « D'accord pour les promesses, mais pourquoi les mathématiciens ont-ils choisi ça ? ». Voici la vraie raison. Prends cette phrase, que tout le monde trouve vraie :

Pour tout réel x, si x > 2, alors x² > 4.

« Pour tout réel x » veut dire que l'implication doit être vraie pour chaque nombre, sans exception. Testons-la sur trois nombres :

Si on décidait que « F ⇒ V » est faux, alors la phrase serait fausse à cause de x = −5. Si on décidait que « F ⇒ F » est faux, elle serait fausse à cause de x = 0. Absurde : −5 et 0 ne sont pas concernés par la phrase, puisqu'ils ne sont pas plus grands que 2. Ils ne doivent pas pouvoir la faire tomber.

Le seul nombre qui pourrait faire tomber cette phrase serait un x qui vérifie x > 2 et x² ≤ 4. Il n'en existe aucun. Et c'est exactement ce que la phrase affirme.

4.3 L'image des cercles : qui implique qui ?

Dans tes notes, il y a un dessin avec un petit cercle P à l'intérieur d'un grand cercle Q, et tu as écrit dans une marge « dans le cas du cercle, qui implique qui ». Voici la réponse, avec P = « habiter à Paris » et Q = « habiter en France ».

C'est aussi la définition de l'inclusion vue en 1.3 : « A ⊂ B » veut dire « pour tout x, si x ∈ A, alors x ∈ B ». Une inclusion d'ensembles et une implication, c'est la même idée, dessinée ou écrite.

4.4 Ce que l'implication ne dit pas

• Elle ne dit pas que P est vraie. « Si je gagne au loto, je m'achète une villa » ne dit pas que je vais gagner. Écrire P ⇒ Q dans une démonstration, ce n'est pas affirmer P.
• Elle ne dit pas que Q est vraie. Pour obtenir Q, il faut deux ingrédients : savoir que P ⇒ Q, et savoir que P est vraie. Alors seulement, Q est vraie (regarde la table : la seule ligne où P et P ⇒ Q sont vraies toutes les deux est la première, où Q est vraie). C'est ça, le « donc » des démonstrations.
• Elle n'exprime pas une cause, ni un ordre dans le temps. Sa valeur ne dépend que des valeurs V ou F de P et Q. « Si 2 + 2 = 4, alors Paris est en France » est vraie (V ⇒ V), même s'il n'y a aucun lien. « Si 2 + 2 = 5, alors je suis le pape » est vraie aussi (F ⇒ F). On raconte d'ailleurs que le philosophe Bertrand Russell, mis au défi, l'aurait « démontré » : si 2 + 2 = 5, en retirant 3 on obtient 1 = 2 ; le pape et moi sommes deux, donc nous sommes un. D'une hypothèse fausse, on peut tout tirer.

Rassure-toi : en mathématiques, on n'écrit jamais d'implications absurdes comme celles-là. Mais c'est la table de vérité, et elle seule, qui décide si une implication est vraie.

4.5 Toutes les façons de dire P ⇒ Q

Ton polycopié donne plusieurs traductions en français. Les voici toutes, avec l'exemple P = « habiter à Paris » et Q = « habiter en France ». Toutes ces phrases disent exactement la même chose.

Suffisant veut dire « si tu as P, c'est assez : Q est garanti ». Habiter à Paris suffit pour habiter en France. Mais ce n'est pas nécessaire : on peut habiter en France sans habiter à Paris.

Nécessaire veut dire « obligatoire : sans Q, pas de P ». Habiter en France est nécessaire pour habiter à Paris : si tu n'habites pas en France, tu ne peux pas habiter à Paris. Mais ce n'est pas suffisant.

Deux exemples de la vie courante, pour t'entraîner à placer la flèche :

• « Il faut avoir le code pour avoir le permis. » Le code est nécessaire. Donc : avoir le permis ⇒ avoir le code. Tous ceux qui ont le permis ont le code ; l'inverse est faux.
• « Pour voter en France, il faut avoir au moins 18 ans. » Donc : voter ⇒ avoir au moins 18 ans. Avoir 18 ans est nécessaire, pas suffisant (il faut aussi être inscrit sur les listes, par exemple).

4.6 Réciproque et contraposée

Ce petit test, inventé par le psychologue Peter Wason, est raté par la grande majorité des gens, étudiants en maths compris. Si tu as choisi le 4, tu es tombé dans le piège de la réciproque. Si tu n'as pas pensé au 7, il te manquait la contraposée. Voyons les deux.

La réciproque : Q ⇒ P

La réciproque de P ⇒ Q est Q ⇒ P : on retourne la flèche. Elle ne dit pas la même chose.

• « Si tu habites à Paris, tu habites en France » : vraie. Réciproque : « si tu habites en France, tu habites à Paris » : fausse.
• « Si n est un multiple de 4, alors n est pair » : vraie. Réciproque : « si n est pair, alors n est un multiple de 4 » : fausse, 6 est pair sans être multiple de 4.
• Tu as rencontré ce piège dans la discussion sur le rectangle : « carré ⇒ trois angles droits » est vraie, mais « trois angles droits ⇒ carré » est fausse.

Les colonnes diffèrent sur deux lignes : une implication et sa réciproque ne sont pas équivalentes. Parfois les deux sont vraies (on aura alors une équivalence, partie 5), parfois une seule. Utiliser la réciproque à la place de l'implication est l'erreur de raisonnement la plus fréquente, en maths comme dans la vie.

La contraposée : ¬Q ⇒ ¬P

La contraposée de P ⇒ Q est ¬Q ⇒ ¬P : on retourne la flèche et on nie les deux côtés. Et là, miracle : elle dit exactement la même chose que l'implication de départ.

« Si tu habites à Paris, tu habites en France » a pour contraposée « si tu n'habites pas en France, alors tu n'habites pas à Paris ». Les deux sont vraies, et c'est logique : sur le dessin des cercles, un point hors du grand cercle est forcément hors du petit.

Pour la colonne ¬Q ⇒ ¬P, applique la règle de 4.1 avec ¬Q à la place de P et ¬P à la place de Q : elle n'est fausse que si ¬Q est vraie et ¬P fausse, c'est-à-dire à la deuxième ligne. Les deux dernières colonnes sont identiques : c'est la ligne « contraposition » de ton polycopié, (P ⇒ Q) ⇔ (¬Q ⇒ ¬P).

La contraposée est très utile en démonstration : quand P ⇒ Q est difficile à prouver directement, ¬Q ⇒ ¬P est parfois beaucoup plus facile. On le verra en partie 9.

4.7 Nier une implication

Quand une promesse P ⇒ Q est-elle rompue ? Uniquement dans le cas « P vrai et Q faux ». Donc la négation de l'implication est vraie exactement dans ce cas-là, et c'est la définition de P ∧ ¬Q (tu l'as calculée dans la question 1 de la partie 3) :

¬(P ⇒ Q) ⇔ P ∧ ¬Q

C'est la troisième règle encadrée de ton polycopié. En français : le contraire de « s'il pleut, je prends mon parapluie », c'est « il pleut, et je ne prends pas mon parapluie ».

C'est aussi ce que montre ton exercice 1. Tu as calculé la colonne de ¬(P ⇒ Q) : F, V, F, F. Et celle de P ∨ (¬Q) : V, V, F, V. Elles diffèrent, donc P ∨ (¬Q) n'est pas la négation de P ⇒ Q. (Petit bonus : P ∨ ¬Q équivaut en fait à Q ⇒ P, la réciproque. Tu comprendras pourquoi dans la section suivante.)

Cette règle est l'origine du contre-exemple : pour montrer qu'une affirmation « pour tout x, si P(x) alors Q(x) » est fausse, il faut trouver un x qui vérifie P(x) et pas Q(x). On le reverra en parties 8 et 9.

4.8 L'implication écrite avec un « ou »

Tu te souviens de la table de (¬P) ∨ Q en 3.4 ? V, F, V, V. C'est exactement celle de P ⇒ Q. Les deux formules sont donc équivalentes :

(P ⇒ Q) ⇔ (¬P ∨ Q)

En français : « ou bien la condition P n'est pas remplie (et alors rien n'était promis), ou bien Q est vraie ». Pour la promesse : « soit tu n'as pas eu la moyenne, soit tu as ton kebab ». La seule façon de rendre cette phrase fausse, c'est que tu aies eu la moyenne sans avoir de kebab : on retrouve le même unique cas de mensonge.

En Python, c'est la façon de programmer l'implication, qui n'existe pas comme opérateur :

def implique(p, q): return (not p) or q

4.9 La phrase mystérieuse de ton polycopié

Ton polycopié dit : « Une implication est vraie si l'enchaînement logique "P implique Q" est vrai, quelles que soient les véracités de P et de Q ». Traduction : ce qui compte dans une implication, c'est le lien entre P et Q (« le cas P vrai, Q faux ne se produit pas »), pas la vérité de P ou de Q prises séparément. Une implication peut être vraie avec P fausse et Q fausse : relis 4.2, c'était le cas de x = 0.

5L'équivalence : la flèche dans les deux sens

P ⇔ Q est vraie quand P et Q ont la même valeur de vérité : toutes les deux vraies, ou toutes les deux fausses.

Les deux dernières colonnes sont identiques : c'est la règle « double implication » de ton polycopié, (P ⇔ Q) ⇔ ((P ⇒ Q) ∧ (Q ⇒ P)). Une équivalence, c'est une implication et sa réciproque, toutes les deux vraies.

Les façons de le dire

• « P équivaut à Q », « P est équivalent à Q ».
• « P si et seulement si Q » (abrégé « ssi »). Décortiquons : « P si Q », c'est Q ⇒ P ; « P seulement si Q », c'est P ⇒ Q (4.5). Les deux ensemble donnent l'équivalence.
• « P est une condition nécessaire et suffisante pour Q ».

Exemples

• Pythagore et sa réciproque, réunis : « le triangle ABC est rectangle en A si et seulement si BC² = AB² + AC² ».
• « n est pair ⇔ n² est pair ». On le démontrera en partie 9, en prouvant les deux sens séparément.
• « x² = 4 ⇔ (x = 2 ou x = −2) ».
• Contre-exemple : « x > 0 ⇔ x² > 0 » est fausse pour les réels. Le sens ⇒ est vrai, mais le sens ⇐ est faux : pour x = −1, x² = 1 > 0 alors que x n'est pas positif.

Attention à ⇔ et ⇒ entre deux lignes de calcul

Quand on écrit ⇔ entre deux lignes, on promet que chaque étape marche dans les deux sens. Ce n'est pas toujours le cas. « x = 2 ⇒ x² = 4 » est vrai, mais on ne peut pas écrire ⇔, car x² = 4 n'oblige pas x à valoir 2 (il pourrait valoir −2). Mettre un ⇔ là où il n'y a qu'un ⇒, c'est perdre des solutions ou en inventer. Dans tes exercices 3 et 4, par contre, chaque étape est une règle d'équivalence, donc les ⇔ sont légitimes (partie 7).

6Le labo : fais calculer les tables

Voici un outil pour vérifier tes propres tables de vérité. Tape une formule avec les lettres P, Q, R (ou d'autres majuscules), et les symboles ¬ ∧ ∨ ⇒ ⇔ (les boutons les insèrent pour toi). Tu peux aussi écrire non, et, ou, =>, <=>. L'outil affiche toutes les colonnes intermédiaires, comme dans tes exercices, et te dit si la formule est une tautologie.

Idées d'expériences : tape les deux formules de ton exercice 1 séparément et compare avec tes colonnes ; tape la formule de l'exercice 2 et vérifie tes 8 lignes ; tape P ⇒ (Q ⇒ (P ∧ Q)) (exercice 4) et regarde le verdict.

7Les règles de calcul, et tes exercices 3 et 4

Les tables de vérité marchent toujours, mais elles deviennent vite longues (16 lignes avec 4 lettres). Alors on fait comme en algèbre : on apprend quelques règles de transformation, et on calcule. Chaque règle ci-dessous est une équivalence (tu peux toutes les vérifier dans le labo).

7.1 Les règles de base

• Associativité : quand il n'y a que des ∨ (ou que des ∧), les parenthèses ne servent à rien, on peut les déplacer. Mais dès qu'on mélange ∧ et ∨, elles sont indispensables : (P ∧ Q) ∨ R et P ∧ (Q ∨ R) ne disent pas la même chose (essaie P faux et R vrai).
• Distributivité : la première ressemble à la règle de collège a × (b + c) = ab + ac. La seconde n'a pas d'équivalent en calcul ordinaire (a + b×c n'est pas égal à (a + b) × (a + c)) : en logique, les deux connecteurs se distribuent l'un sur l'autre.
• Attention : l'implication n'est pas commutative. P ⇒ Q et Q ⇒ P, c'est l'implication et sa réciproque (4.6).

7.2 Les lois de De Morgan : nier un « et », nier un « ou »

¬(P ∧ Q) ⇔ ¬P ∨ ¬Q
¬(P ∨ Q) ⇔ ¬P ∧ ¬Q

Tu as noté à côté : « on applique aussi la négation sur le signe ». C'est exactement ça : la négation entre dans la parenthèse, s'applique à chaque morceau, et retourne le signe (∧ devient ∨, ∨ devient ∧).

• « Il n'est pas vrai que je suis riche et célèbre » = « je ne suis pas riche, ou je ne suis pas célèbre » (il suffit qu'un des deux manque).
• « Il n'est pas vrai que j'ai un chat ou un chien » = « je n'ai pas de chat et je n'ai pas de chien ».
• Avec le circuit en série de la partie 3 : la lampe reste éteinte dès que P est ouvert ou que Q est ouvert.
• Avec des inégalités : nier « 0 ≤ x ≤ 1 », c'est nier « 0 ≤ x et x ≤ 1 », ce qui donne « x < 0 ou x > 1 ». Le « et » devient « ou », et chaque inégalité est niée sans oublier le cas d'égalité.

En Python, tu as peut-être déjà simplifié une condition de cette façon : not (a and b) est équivalent à (not a) or (not b).

7.3 La transitivité : les dominos

((P ⇒ Q) ∧ (Q ⇒ R)) ⇒ (P ⇒ R)

Si P entraîne Q, et que Q entraîne R, alors P entraîne R. « Si tu travailles, tu comprends ; si tu comprends, tu réussis ; donc si tu travailles, tu réussis. » C'est la règle qui permet d'enchaîner les étapes d'une démonstration : chaque ligne implique la suivante, donc la première implique la dernière.

7.4 Tes exercices 3 et 4, ligne par ligne

Dans tes notes, les calculs sont justes, mais les lignes sont posées les unes sous les autres sans symbole entre elles et sans justification. C'est pour ça qu'ils sont difficiles à relire. Voici les mêmes calculs, avec un ⇔ entre chaque ligne et la règle utilisée à chaque étape. « Montrer que A équivaut à B », c'est construire une chaîne de ⇔ qui part de A et arrive à B.

Exercice 3.1 : P ⇒ (Q ⇒ R) équivaut à (P ∧ Q) ⇒ R

En français : « s'il pleut, alors s'il fait froid, je reste chez moi » dit la même chose que « s'il pleut et qu'il fait froid, je reste chez moi ». Deux conditions emboîtées, c'est une double condition.

Exercice 3.2 : (P ∨ Q) ⇒ R équivaut à (P ⇒ R) ∧ (Q ⇒ R)

En français : « s'il pleut ou s'il neige, je prends le bus » dit la même chose que « s'il pleut, je prends le bus, et s'il neige, je prends le bus ». Garde cette règle en tête : c'est elle qui justifie le raisonnement par disjonction de cas (partie 9).

Exercice 4 : P ⇒ (Q ⇒ (P ∧ Q)) est une tautologie

Comme dans tes notes, pose S = P ∧ Q. La dernière ligne est ¬S ∨ S : « S est fausse ou S est vraie ». C'est toujours vrai (tiers exclu, 3.5). La formule de départ est donc toujours vraie : c'est une tautologie.

Deux remarques. Tu avais noté « faisable avec le tableau de vérité » : oui, et c'est une méthode tout aussi valable (4 lignes, toutes V). Et il y avait un raccourci : d'après l'exercice 3.1, la formule équivaut à (P ∧ Q) ⇒ (P ∧ Q), de la forme « S ⇒ S », évidemment toujours vraie. En français : « si P est vraie, alors si Q est vraie, P et Q sont vraies ». Une fois traduit, c'est presque évident.

8Les quantificateurs : pour tout, il existe

8.1 Le prédicat, une proposition avec un trou

« x > 3 » n'est ni vrai ni faux tant qu'on ne sait pas qui est x (partie 2). C'est une proposition avec un trou, qu'on appelle un prédicat et qu'on note P(x). Donne-lui une valeur, il te rend V ou F : P(5) est vraie, P(1) est fausse.

Pour toi, c'est une fonction qui renvoie un booléen : def P(x): return x > 3.

Il y a deux façons de « boucher le trou » pour obtenir une vraie proposition : dire que la propriété marche pour tous les x, ou dire qu'elle marche pour au moins un x.

8.2 ∀ et ∃

Des exemples, pour t'habituer à lire :

• ∀x ∈ ℝ, x² ≥ 0 : « le carré de tout réel est positif ou nul ». Vraie.
• ∀n ∈ ℕ, n est pair : fausse, 1 n'est pas pair. Un seul contre-exemple suffit à faire tomber un « pour tout ».
• ∃n ∈ ℕ, n est pair : vraie (2 convient). « Il existe » veut dire « au moins un », même s'il y en a une infinité.
• ∃x ∈ ℝ, x² = −1 : fausse, un carré de réel n'est jamais négatif.
• ∃x ∈ ℕ, x + 3 = 1 est fausse, mais ∃x ∈ ℤ, x + 3 = 1 est vraie (x = −2). L'ensemble fait partie de la phrase : changer E peut changer la réponse.
• ∃!n ∈ ℕ, n² = 4 est vraie (seul 2 convient, car −2 n'est pas dans ℕ). Dans ℤ, elle serait fausse : il y aurait deux solutions.

La lettre après ∀ ou ∃ est une variable muette : ∀x ∈ ℝ, x² ≥ 0 et ∀t ∈ ℝ, t² ≥ 0 disent exactement la même chose, comme tu peux renommer la variable d'une boucle for sans changer ce que fait ton programme.

8.3 « Pour tout » suivi d'une implication

La forme la plus fréquente d'un théorème est ∀x ∈ E, P(x) ⇒ Q(x) : « pour tout x de E, si x vérifie P, alors x vérifie Q ». C'est exactement la phrase de 4.2. Et c'est là que la convention « faux ⇒ n'importe quoi est vrai » devient indispensable : les x qui ne vérifient pas P ne comptent pas.

Conséquence amusante : « tout réel x tel que x² < 0 est égal à 42 » est une phrase vraie. Il n'existe aucun réel dont le carré est négatif, donc aucun x ne peut la prendre en défaut. De même, « tous les dragons de ma chambre sont verts » est vraie : il n'y a aucun dragon pour la contredire. On dit qu'elle est vraie par vacuité (vide). Garde cet exemple : il va servir pour l'exercice 5.

8.4 Nier une phrase avec des quantificateurs

Tu as écrit la bonne idée dans tes notes, à l'exercice 5 : la négation de « tout le monde a les yeux bleus » est « il existe au moins une personne qui n'a pas les yeux bleus ». Et surtout pas « personne n'a les yeux bleus » : pour contredire « tout le monde », il suffit d'une exception.

¬(∀x ∈ E, P(x)) ⇔ ∃x ∈ E, ¬P(x)
¬(∃x ∈ E, P(x)) ⇔ ∀x ∈ E, ¬P(x)

De même, la négation de « il existe un étudiant qui a eu 20 » est « aucun étudiant n'a eu 20 », c'est-à-dire « pour tout étudiant, il n'a pas eu 20 ».

Exemple complet, tiré de ton polycopié (page des majorants). « A est majorée » veut dire : il existe un nombre M plus grand que tous les éléments de A.

En français : « aussi grand que soit le nombre M que tu choisis, il y a un élément de A qui le dépasse ». Par exemple ℕ n'est pas majoré : pour n'importe quel M, l'entier juste au-dessus de M le dépasse.

Pourquoi ça marche ? Parce que « pour tout » est un grand « et » (P(x₁) et P(x₂) et P(x₃)…), et « il existe » un grand « ou ». Nier un « pour tout », c'est appliquer De Morgan à un « et » géant : il devient un « ou » géant de négations, c'est-à-dire « il existe un x tel que non P(x) ».

Enfin, la négation d'un théorème en « pour tout… si… alors » est une phrase en « il existe… et… » :

¬(∀x ∈ E, P(x) ⇒ Q(x)) ⇔ ∃x ∈ E, P(x) ∧ ¬Q(x)

C'est la définition exacte d'un contre-exemple. « Tout nombre premier est impair » est fausse, car il existe un nombre premier qui n'est pas impair : 2.

8.5 L'ordre des quantificateurs change tout

Avec des nombres :

• ∀x ∈ ℝ, ∃y ∈ ℝ, y > x : « pour tout réel, il existe un réel plus grand ». Vraie : prends y = x + 1. Le y dépend de x.
• ∃y ∈ ℝ, ∀x ∈ ℝ, y > x : « il existe un réel plus grand que tous les réels ». Fausse : ce y devrait être plus grand que lui-même. Ici, y doit être choisi une fois pour toutes, avant de connaître x.

C'est la remarque de ton polycopié : on peut échanger deux quantificateurs de même espèce (∀x ∀y ⇔ ∀y ∀x, et pareil pour ∃), mais échanger un ∀ et un ∃ change le sens de la phrase. En Python, la différence saute aux yeux : all(any(P(x, y) for y in E) for x in E) n'est pas any(all(P(x, y) for x in E) for y in E).

8.6 Lire les définitions de ton polycopié

Ton chapitre 1 est plein de phrases à quantificateurs. Voici comment les lire.

• Majorant : « M est un majorant de A si ∀x ∈ A, x ≤ M ». M est plus grand ou égal à tous les éléments de A. Pour A = [1, 2], les nombres 2, 3 et 100 sont des majorants, mais pas 1,5 (car 1,8 est dans A et dépasse 1,5).
• ℝ est archimédien : « ∀X ∈ ℝ, ∀ε > 0, ∃n ∈ ℕ, nε > X ». La lettre grecque ε (epsilon) désigne un nombre strictement positif, qu'on imagine tout petit. Lecture : « aussi loin que soit X, et aussi petit que soit le pas ε, il existe un nombre de pas n tel qu'en faisant n pas de longueur ε, on dépasse X ». Avec ε = 0,01 et X = 1 000, n = 100 001 convient. Remarque que n arrive après X et ε : il a le droit de dépendre d'eux.

9Les méthodes de démonstration

9.1 Qu'est-ce qu'une démonstration ?

Une démonstration est une chaîne d'étapes qui part de choses déjà sûres (les hypothèses de l'énoncé, les définitions, les théorèmes déjà démontrés) et arrive à la conclusion. Chaque étape utilise le même mécanisme : « je sais que A est vraie, je sais que A ⇒ B, donc B est vraie ». Et par transitivité (7.3), le début de la chaîne implique la fin.

Pourquoi ne pas se contenter de vérifier sur des exemples ? Regarde la formule n² + n + 41. Pour n = 0, 1, 2, 3… elle donne 41, 43, 47, 53, 61… tous des nombres premiers. Ça continue jusqu'à n = 39, soit 40 essais réussis d'affilée. Et pour n = 40 : 40² + 40 + 41 = 1681 = 41 × 41, qui n'est pas premier. C'est ce que dit ton polycopié : « un nombre fini de cas ne suffit pas ». Toi qui codes, tu connais le principe : des tests qui passent sur 40 entrées ne prouvent pas que ta fonction marche sur toutes.

9.2 La démonstration directe d'une implication

Pour démontrer P ⇒ Q, on suppose que P est vraie, et on montre que Q est vraie. C'est la phrase de ton polycopié.

Pourquoi a-t-on le droit de « supposer » P ? Parce que si P est fausse, l'implication est vraie de toute façon (4.1) : il n'y a rien à vérifier. Le seul cas dangereux est « P vraie », alors c'est le seul qu'on examine. Supposer P, ce n'est pas affirmer que P est vraie : c'est aller inspecter le seul endroit où la promesse pourrait être rompue.

9.3 Démontrer un « pour tout » : le sens de « soit »

Pour démontrer ∀x ∈ E, P(x), on écrit « Soit x ∈ E » : on prend un élément quelconque de E, sur lequel on ne sait rien d'autre que « il est dans E ». On n'a pas le droit de le choisir (« prenons x = 2 »). Si la démonstration marche pour cet x sans visage, elle marche pour tous.

C'est exactement comme écrire une fonction qui prend un paramètre : ton code doit marcher pour n'importe quelle valeur d'entrée, tu ne choisis pas ce que l'utilisateur va envoyer.

9.4 Démontrer un « il existe », et le contre-exemple

Pour démontrer ∃x ∈ E, P(x), il suffit d'en exhiber un et de vérifier qu'il marche. Exemple : ∃n ∈ ℕ, n² > 50 est vraie, car n = 8 convient (64 > 50).

Le contre-exemple est la même idée à l'envers. Pour montrer qu'un « pour tout » est faux, il suffit de trouver un élément qui ne vérifie pas la propriété, puisque ¬(∀x, P(x)) ⇔ ∃x, ¬P(x) (8.4).

• « ∀n ∈ ℕ, n² + n + 41 est premier » est fausse : contre-exemple n = 40.
• « ∀x ∈ ℝ, x² ≥ x » est fausse : contre-exemple x = 1/2, car 1/4 < 1/2.

9.5 Le raisonnement par contraposition

Comme P ⇒ Q et ¬Q ⇒ ¬P sont équivalentes (4.6), on peut démontrer la seconde à la place de la première quand elle est plus facile.

Avec 9.2, on a maintenant les deux sens : n pair ⇔ n² pair. C'était la promesse de la partie 5. Et ce résultat est exactement la clé de l'exercice 18.

9.6 Le raisonnement par l'absurde

Pour démontrer une proposition R, on suppose le contraire, ¬R, et on en déduit quelque chose d'impossible : une contradiction (une affirmation et sa négation vraies en même temps, comme « n est pair et impair », ou « 0 = 1 »). Comme ¬R mène à l'impossible, ¬R est fausse, donc R est vraie (tiers exclu, partie 2).

C'est le raisonnement du détective : « Supposons que le majordome soit coupable. Alors il était dans la cuisine à 21 h. Or à 21 h, les caméras le filment au supermarché. Contradiction : ce n'est pas lui. »

Différence avec la contraposition : la contraposition démontre une implication en démontrant une autre implication, avec un but précis (¬P). L'absurde suppose la négation de ce qu'on veut, et cherche n'importe quelle contradiction. L'exercice 18 (√2 n'est pas une fraction) est le grand classique de l'absurde.

9.7 La disjonction de cas, et ton exercice 5

Si une conclusion C est vraie dans le cas A et dans le cas ¬A, alors C est vraie tout court. Pourquoi ? D'après ton exercice 3.2, (A ⇒ C) ∧ (¬A ⇒ C) équivaut à (A ∨ ¬A) ⇒ C. Et A ∨ ¬A est toujours vraie. Donc C est vraie.

L'exercice 5, guidé

L'énoncé : « dans un groupe de personnes non vide, il existe une personne P telle que : si P a les yeux bleus, alors tout le monde a les yeux bleus ». La phrase a l'air absurde, comme si une seule personne décidait des yeux de tout le monde. Elle est pourtant vraie, et c'est uniquement une question d'implication.

La structure : il faut trouver une personne p pour laquelle l'implication « p a les yeux bleus ⇒ tout le monde a les yeux bleus » est vraie. Fais la disjonction de cas sur A = « tout le monde a les yeux bleus ».

• Indice pour le cas 1 (A vraie) : la conclusion de l'implication est vraie. Que vaut « … ⇒ V », quoi qu'il y ait avant la flèche ? Et pourquoi a-t-on besoin que le groupe soit non vide ?
• Indice pour le cas 2 (A fausse) : tu as déjà écrit la négation de A dans tes notes. Elle te donne une personne précise. Choisis-la comme p. Que vaut alors l'hypothèse « p a les yeux bleus » ? Et que vaut « F ⇒ … » ?

9.8 Le raisonnement par récurrence

On veut démontrer une propriété P(n) pour tous les entiers n à partir d'un rang n₀. On procède en deux étapes :

1. Initialisation : on vérifie que P(n₀) est vraie (souvent n₀ = 0 ou 1).
2. Hérédité : on démontre que, pour tout n ≥ n₀, P(n) ⇒ P(n + 1).

Alors P(n) est vraie pour tout n ≥ n₀ : P(n₀) est vraie, donc P(n₀ + 1) aussi, donc P(n₀ + 2) aussi, et ainsi de suite (transitivité, 7.3).

Variantes que tu croiseras sur ta feuille. Dans la récurrence double (exercices 10 et 11, où chaque terme dépend des deux précédents), on initialise deux rangs, et on suppose P(n) et P(n + 1) pour démontrer P(n + 2). Dans la récurrence forte (exercices 12 et 14), on suppose P vraie à tous les rangs de n₀ jusqu'à n pour démontrer P(n + 1). C'est d'ailleurs la formulation de ton polycopié : « supposant Pₙ vraie jusqu'au rang n ».

9.9 Le principe des tiroirs

Si tu ranges n + 1 paires de chaussettes dans n tiroirs, un tiroir en contient au moins deux. Sinon, chaque tiroir en contiendrait au plus une, et il y aurait au plus n paires : absurde. Exemple : parmi 13 personnes, deux au moins sont nées le même mois, car il n'y a que 12 mois. Ça paraît évident, et pourtant c'est un outil très puissant (exercices 15 à 17).

10Relecture de tes notes

Ce qui est juste

• Tes tables des exercices 1 et 2 sont entièrement justes. J'ai vérifié les 4 lignes de l'exercice 1 et les 8 lignes de l'exercice 2, colonne par colonne. La mécanique est donc en place : ce qui manquait, c'était le sens, et c'est l'objet de la partie 4.
• Les calculs des exercices 3 et 4 sont justes. Ce qui leur manque, ce sont les ⇔ entre les lignes et la règle utilisée à chaque étape : c'est fait en 7.4.
• « Tautologie = tout le temps vrai » : exact.
• Dans l'exercice 5, ta négation de « tout le monde a les yeux bleus » est parfaite. La fin de l'exercice est en 9.7.
• Le dessin du petit cercle p dans le grand cercle q, et ta question « qui implique qui » : le petit implique le grand (4.3).

11Ta feuille d'exercices, et ta checklist

Honnêtement : les exercices 1 à 9 sont à ta portée après ce cours. Les exercices de récurrence (10 à 14) et les exercices 16 et 17 demandent plus d'entraînement, surtout pour les calculs. S'ils résistent, ce n'est pas un signe que tu n'as pas compris la logique, c'est normal à ce stade.