Aller au contenu
Mathématiques discrètes · L1

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 :

ConnecteurNotationSe litVrai quand…
Négation¬ pnon pp est faux
Conjonctionp ∧ qp et qles deux sont vrais
Disjonctionp ∨ qp ou qau moins un est vrai (« ou » inclusif)
Implicationp ⇒ qsi p alors qsauf quand p est vrai et q faux
Équivalencep ⇔ qp si et seulement si qp et q ont la même valeur

Table de vérité de ces connecteurs :

pq¬ pp ∧ qp ∨ qp ⇒ qp ⇔ q
VVFVVVV
VFFFVFF
FVVFVVF
FFVFFVV

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.

pqp ⇒ q¬ q¬ p¬ q ⇒ ¬ p
VVVFFV
VFFVFF
FVVFVV
FFVVVV

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.

1Si p est faux et q est faux, p ⇒ q est :
Voir la réponse

Réponse A : vraie. Une implication dont l'hypothèse est fausse est vraie.

2La négation de « p ou q » est :
Voir la réponse

Réponse B : « non p et non q ». C'est une loi de De Morgan.

3La contraposée de « s'il pleut, la route est mouillée » est :
Voir la réponse

Réponse B : « si la route n'est pas mouillée, il ne pleut pas ». On nie et on inverse : ¬q ⇒ ¬p.

4La négation de ∀ x ∈ ℝ, x2 ≥ 0 est :
Voir la réponse

Réponse B : ∃ x ∈ ℝ, x2 < 0. On échange le quantificateur et on nie le prédicat.

5Pour montrer qu'un énoncé « pour tout n… » est faux, il suffit :
Voir la réponse

Réponse B : de trouver un contre-exemple. Un seul cas où l'énoncé échoue suffit.

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ö.

Vous avez fini la leçon ?

Avec un compte Kharandi gratuit, vous cochez les leçons terminées et vous suivez votre progression, cours par cours.

Karamö
Un point pas clair ? Dites à Karamö ce qui vous bloque dans cette leçon : il vous l’explique autrement, pas à pas, sans faire le travail à votre place. Demander à Karamö
Signaler une erreur dans cette leçon

Toutes les leçons de Mathématiques discrètes

Pose ta question à Karamö