Leçon 1 sur 5
Logique propositionnelle et raisonnements
Je sais écrire et évaluer des propositions logiques avec des tables de vérité, nier une phrase quantifiée et choisir le bon type de raisonnement pour démontrer.
- 1 h 10
- 4 exercices corrigés
- QCM de 5 questions
À la fin de la leçon, vous saurez :
- Utiliser les connecteurs logiques et dresser une table de vérité
- Reconnaître tautologies et équivalences usuelles (De Morgan, contraposée)
- Manipuler et nier les quantificateurs
- Rédiger un raisonnement direct, par contraposée, par l'absurde ou par contre-exemple
Avant de commencer : Mathématiques du lycée.
1Je découvre
En TP de programmation, Fanta écrit une condition pour accorder une bourse : « si la moyenne est supérieure ou égale à 12 et que l'étudiant n'a pas redoublé, ou s'il est boursier sur critères sociaux ». Son programme accepte des étudiants qui ne devraient pas l'être. En relisant, elle s'aperçoit que l'ordinateur n'a pas regroupé les conditions comme elle l'imaginait.
Le lendemain, en cours de mathématiques, l'enseignant affirme : « Tout entier dont le carré est pair est lui-même pair », puis le démontre en trois lignes par une méthode que personne ne connaissait.
Comment écrire des énoncés logiques sans ambiguïté, vérifier leur valeur de vérité, et utiliser les règles de la logique pour raisonner et démontrer ?
2Je comprends
1. Propositions et connecteurs
Une proposition est un énoncé qui est soit vrai (V, ou 1), soit faux (F, ou 0). « 7 est premier » est une proposition vraie ; « x > 3 » n'en est pas une tant que x n'est pas fixé.
À partir de propositions p et q, on en construit d'autres avec les connecteurs :
| Connecteur | Notation | Se lit | Vrai quand… |
|---|---|---|---|
| Négation | ¬ p | non p | p est faux |
| Conjonction | p ∧ q | p et q | les deux sont vrais |
| Disjonction | p ∨ q | p ou q | au moins un est vrai (« ou » inclusif) |
| Implication | p ⇒ q | si p alors q | sauf quand p est vrai et q faux |
| Équivalence | p ⇔ q | p si et seulement si q | p et q ont la même valeur |
Table de vérité de ces connecteurs :
| p | q | ¬ p | p ∧ q | p ∨ q | p ⇒ q | p ⇔ q |
|---|---|---|---|---|---|---|
| V | V | F | V | V | V | V |
| V | F | F | F | V | F | F |
| F | V | V | F | V | V | F |
| F | F | V | F | F | V | V |
L'implication surprend souvent : « si p alors q » est vraie quand p est faux, quelle que soit q. Une promesse « s'il pleut, je prends un parapluie » n'est pas trahie les jours sans pluie.
En programmation, on retrouve ces connecteurs : not, and, or en Python (!, &&, || en C ou Java). Les parenthèses décident de l'ordre : la condition de Fanta s'écrit sans ambiguïté (moyenne >= 12 and not redouble) or boursier.
2. Tautologies et équivalences usuelles
Une tautologie est une proposition composée toujours vraie, quelles que soient les valeurs de ses variables (par exemple p ∨ ¬ p). Deux propositions sont logiquement équivalentes (on note ≡) si elles ont la même table de vérité.
Équivalences à connaître :
- double négation : ¬(¬ p) ≡ p ;
- lois de De Morgan : ¬(p ∧ q) ≡ ¬ p ∨ ¬ q et ¬(p ∨ q) ≡ ¬ p ∧ ¬ q ;
- implication : p ⇒ q ≡ ¬ p ∨ q ;
- négation de l'implication : ¬(p ⇒ q) ≡ p ∧ ¬ q ;
- contraposée : p ⇒ q ≡ ¬ q ⇒ ¬ p ;
- équivalence : p ⇔ q ≡ (p ⇒ q) ∧ (q ⇒ p) ;
- distributivité : p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r).
Attention : la réciproque q ⇒ p n'est pas équivalente à p ⇒ q. « Si un nombre est divisible par 4, il est pair » est vrai ; sa réciproque est fausse (6 est pair).
Exemple résolu. Montrons que p ⇒ q et ¬ q ⇒ ¬ p sont équivalentes.
| p | q | p ⇒ q | ¬ q | ¬ p | ¬ q ⇒ ¬ p |
|---|---|---|---|---|---|
| V | V | V | F | F | V |
| V | F | F | V | F | F |
| F | V | V | F | V | V |
| F | F | V | V | V | V |
Les colonnes 3 et 6 sont identiques : les deux propositions sont équivalentes.
3. Les quantificateurs
Un prédicat est un énoncé qui dépend d'une variable, comme P(x) : « x2 ≥ x ». On en fait une proposition avec un quantificateur :
- universel ∀ (« pour tout ») : ∀ x ∈ ℝ, P(x) est vraie si P(x) est vraie pour chaque x ;
- existentiel ∃ (« il existe au moins un ») : ∃ x ∈ ℝ, P(x) est vraie s'il y a au moins un x qui convient.
Négation : on échange les quantificateurs et on nie le prédicat.
- ¬(∀ x, P(x)) ≡ ∃ x, ¬ P(x) ;
- ¬(∃ x, P(x)) ≡ ∀ x, ¬ P(x).
Exemple résolu. « Tous les étudiants du groupe ont validé l'UE » a pour négation « Il existe au moins un étudiant du groupe qui n'a pas validé l'UE » (et non « aucun n'a validé »).
L'ordre des quantificateurs compte : ∀ x ∈ ℕ, ∃ y ∈ ℕ, y > x (pour chaque entier, il existe un entier plus grand) est vrai ; ∃ y ∈ ℕ, ∀ x ∈ ℕ, y > x (un entier plus grand que tous) est faux.
4. Les types de raisonnement
Raisonnement direct. On suppose p vraie et on en déduit q par des étapes valides.
Exemple : si n est pair, n = 2k, alors n2 = 4k2 = 2(2k2) est pair.
Raisonnement par contraposée. Pour montrer p ⇒ q, on montre ¬ q ⇒ ¬ p.
Exemple : montrons « si n2 est pair, alors n est pair ». Contraposée : « si n est impair, alors n2 est impair ». Si n = 2k+1, n2 = 4k2 + 4k + 1 = 2(2k2 + 2k) + 1, impair. La contraposée est vraie, donc la proposition aussi. C'est la démonstration du professeur.
Raisonnement par l'absurde. On suppose que la conclusion est fausse et on aboutit à une contradiction.
Exemple classique : √2 est irrationnel. Supposons √2 = ab avec une fraction irréductible. Alors a2 = 2b2, donc a2 est pair, donc a est pair (résultat ci-dessus) : a = 2c. Alors 4c2 = 2b2, donc b2 = 2c2 et b est pair. a et b sont tous deux pairs : la fraction n'était pas irréductible. Contradiction.
Contre-exemple. Pour montrer qu'un énoncé universel ∀ x, P(x) est faux, il suffit d'un x tel que P(x) soit faux.
Exemple : « pour tout entier n, n2 + n + 41 est premier » est faux : pour n = 40, 402 + 40 + 41 = 1 681 = 412.
Disjonction de cas. On sépare en cas qui couvrent toutes les possibilités.
Exemple : n(n+1) est toujours pair : si n est pair, n l'est ; si n est impair, n+1 est pair.
3Je retiens
Je retiens
Une proposition est vraie ou fausse ; les connecteurs sont ¬, ∧, ∨, ⇒, ⇔.
p ⇒ q n'est fausse que si p est vraie et q fausse ; elle équivaut à ¬p ∨ q.
De Morgan : ¬(p ∧ q) ≡ ¬p ∨ ¬q et ¬(p ∨ q) ≡ ¬p ∧ ¬q.
La contraposée ¬q ⇒ ¬p équivaut à p ⇒ q ; la réciproque q ⇒ p, non.
Nier une phrase quantifiée : échanger ∀ et ∃ et nier le prédicat ; l'ordre des quantificateurs compte.
Raisonnements : direct, contraposée, absurde, contre-exemple, disjonction de cas.
Un seul contre-exemple suffit à réfuter un énoncé universel ; des exemples ne suffisent jamais à le prouver.
4Erreurs fréquentes
- Confondre contraposée et réciproque : seule la contraposée est équivalente à l'implication.
- Nier « p et q » par « non p et non q » : la négation est « non p ou non q ».
- Nier « tous les… » par « aucun… » : la négation est « il existe au moins un… qui ne… pas ».
- Croire qu'une implication dont l'hypothèse est fausse est fausse : elle est vraie.
- Prouver un énoncé universel en vérifiant quelques exemples.
5Je m’exerce
1Exercice 1
(Questions de cours) a) Donnez la table de vérité de p ⇒ q. b) Énoncez les lois de De Morgan. c) Quelle est la différence entre la contraposée et la réciproque de p ⇒ q ?
Voir le corrigéCacher le corrigé
a) p ⇒ q vaut V, F, V, V pour (p,q) = (V,V), (V,F), (F,V), (F,F). b) ¬(p ∧ q) ≡ ¬ p ∨ ¬ q ; ¬(p ∨ q) ≡ ¬ p ∧ ¬ q. c) La contraposée ¬ q ⇒ ¬ p est équivalente à p ⇒ q ; la réciproque q ⇒ p ne l'est pas en général.
2Exercice 2
a) Dressez la table de vérité de (p ⇒ q) ∧ (q ⇒ p) et comparez-la à celle de p ⇔ q. b) Montrez par une table que (p ∧ (p ⇒ q)) ⇒ q est une tautologie.
Voir le corrigéCacher le corrigé
a) Pour (V,V), (V,F), (F,V), (F,F) : p ⇒ q = V, F, V, V ; q ⇒ p = V, V, F, V ; conjonction = V, F, F, V, ce qui est exactement la table de p ⇔ q. b) p ⇒ q = V, F, V, V ; p ∧ (p ⇒ q) = V, F, F, F ; l'implication finale vers q (= V, F, V, F) donne : V⇒V = V ; F⇒F = V ; F⇒V = V ; F⇒F = V. Toujours vraie : c'est une tautologie (le raisonnement appelé modus ponens).
3Exercice 3
Écrivez la négation de chaque phrase, en langage courant puis avec des quantificateurs : a) « Tous les étudiants de L1 ont un téléphone. » b) « Il existe un réel x tel que x2 = -1. » c) ∀ ε > 0, ∃ n ∈ ℕ, 1n+1 < ε.
Voir le corrigéCacher le corrigé
a) « Au moins un étudiant de L1 n'a pas de téléphone. » Avec E l'ensemble des étudiants et T(x) « x a un téléphone » : ∃ x ∈ E, ¬ T(x). b) « Pour tout réel x, x2 ≠ -1 » : ∀ x ∈ ℝ, x2 ≠ -1. c) ∃ ε > 0, ∀ n ∈ ℕ, 1n+1 ≥ ε.
4Exercice 4
(Type examen) a) Démontrez par contraposée : « pour tout entier n, si n2 est impair, alors n est impair ». b) Démontrez par l'absurde qu'il n'existe pas de plus grand entier naturel. c) L'énoncé « pour tout entier naturel n, 2n > n2 » est-il vrai ? Justifiez. d) Simplifiez la condition de programme not (a and not b) en une condition sans not devant une parenthèse.
Voir le corrigéCacher le corrigé
a) Contraposée : « si n est pair, alors n2 est pair ». Si n = 2k, n2 = 2(2k2) est pair. La contraposée étant vraie, l'énoncé l'est aussi. b) Supposons qu'il existe un plus grand entier naturel N. Alors N + 1 est un entier naturel et N + 1 > N : contradiction avec la définition de N. Donc il n'existe pas de plus grand entier naturel. c) Faux : contre-exemple n = 2 : 2n = 4 et n2 = 4, donc 2n > n2 est faux (autre contre-exemple : n = 3, 8 < 9). d) Par De Morgan : ¬(a ∧ ¬ b) ≡ ¬ a ∨ b, soit (not a) or b.
Cherchez d’abord seul, sur votre cahier, puis ouvrez le corrigé pour comparer.
6Je vérifie
Choisissez une réponse pour chaque question : la correction s’affiche aussitôt.
Karamö, votre enseignant
Il a lu cette leçon. Posez-lui votre question : il vous répond ici.
Connectez-vous pour poser vos questions à Karamö.
Avec un compte Kharandi gratuit, vous cochez les leçons terminées et vous suivez votre progression, cours par cours.