Propositions et connecteurs

⏱ ~10 min·+30 XP

🚀

Pourquoi cette leçon est importante

Cette leçon te servira directement pour 1 module plus avancé :

🔗

Ensembles & Relations

Maths Discrètes — Ensembles & Relations

💡

Pourquoi apprendre ça ?

La logique propositionnelle est le langage des mathématiques. Avant de démontrer quoi que ce soit — que ce soit en algèbre, en analyse ou en informatique — tu dois maîtriser les règles qui permettent de raisonner correctement. C'est la grammaire du raisonnement mathématique.

🎯

Analogie

Imagine un tribunal : le juge doit décider si un accusé est coupable ou innocent. Pour cela, il combine des faits (propositions) avec des connecteurs logiques : "il était sur les lieux ET il avait un mobile" → alors il est suspect. La logique propositionnelle formalise exactement ce type de raisonnement.

Propositions et valeurs de vérité

📐

Théorie

Une proposition (ou énoncé) est une affirmation qui est soit vraie (V ou 1), soit fausse (F ou 0). Il ne peut pas y avoir de valeur intermédiaire.

Exemples de propositions :

"2 + 2 = 4" → Vraie
"7 est pair" → Fausse
" $\sqrt{2}$ est rationnel" → Fausse

Non-exemples (pas des propositions) :

"Quel âge as-tu ?" (question, pas d'évaluation vrai/faux)
" $x + 1 = 5$ " (dépend de $x$ , c'est un prédicat)

On note généralement les propositions par des lettres : $p$ , $q$ , $r$ , ...

Connecteurs logiques et tables de vérité

📐

Théorie

Les connecteurs logiques permettent de combiner des propositions pour en former de nouvelles.

Négation $\neg p$ (NON $p$ ) : vrai si $p$ est faux, faux si $p$ est vrai.

| $p$ | $\neg p$ | |-----|----------| | V | F | | F | V |

Conjonction $p \land q$ ( $p$ ET $q$ ) : vrai seulement si les deux sont vrais.

| $p$ | $q$ | $p \land q$ | |-----|-----|-------------| | V | V | V | | V | F | F | | F | V | F | | F | F | F |

Disjonction $p \lor q$ ( $p$ OU $q$ ) : vrai si au moins l'un est vrai.

| $p$ | $q$ | $p \lor q$ | |-----|-----|------------| | V | V | V | | V | F | V | | F | V | V | | F | F | F |

Implication $p \Rightarrow q$ : faux seulement si $p$ est vrai et $q$ est faux.

| $p$ | $q$ | $p \Rightarrow q$ | |-----|-----|-------------------| | V | V | V | | V | F | F | | F | V | V | | F | F | V |

Équivalence $p \Leftrightarrow q$ : vrai si $p$ et $q$ ont la même valeur de vérité.

| $p$ | $q$ | $p \Leftrightarrow q$ | |-----|-----|-----------------------| | V | V | V | | V | F | F | | F | V | F | | F | F | V |

📝

Table de vérité d'une formule composée

Construisons la table de vérité de $(p \Rightarrow q) \land \neg p$ .

On calcule colonne par colonne :

| $p$ | $q$ | $\neg p$ | $p \Rightarrow q$ | $(p \Rightarrow q) \land \neg p$ | |-----|-----|----------|-------------------|----------------------------------| | V | V | F | V | F | | V | F | F | F | F | | F | V | V | V | V | | F | F | V | V | V |

La formule est vraie exactement quand $p$ est faux. Elle n'est ni une tautologie ni une contradiction.

🧩

Checkpoint

Quelle est la valeur de vérité de l'implication quand est FAUX et est FAUX ?

Tautologies, contradictions et lois logiques

📐

Théorie

Une tautologie est une formule toujours vraie, quelle que soit la valeur de ses variables. Une contradiction est une formule toujours fausse.

Tautologies importantes :

Loi du tiers exclu : $p \lor \neg p$
Double négation : $\neg(\neg p) \Leftrightarrow p$
Modus ponens : $(p \land (p \Rightarrow q)) \Rightarrow q$
Contraposée : $(p \Rightarrow q) \Leftrightarrow (\neg q \Rightarrow \neg p)$

Lois de De Morgan : $\neg(p \land q) \Leftrightarrow (\neg p \lor \neg q)$ $\neg(p \lor q) \Leftrightarrow (\neg p \land \neg q)$

Contradiction classique : $p \land \neg p$ (toujours fausse).

📝

Vérifier que la contraposée est une tautologie

Montrons que $(p \Rightarrow q) \Leftrightarrow (\neg q \Rightarrow \neg p)$ est une tautologie.

| $p$ | $q$ | $p \Rightarrow q$ | $\neg q \Rightarrow \neg p$ | Équivalence | |-----|-----|-------------------|-----------------------------|-------------| | V | V | V | V | V | | V | F | F | F | V | | F | V | V | V | V | | F | F | V | V | V |

La dernière colonne est toujours V : c'est bien une tautologie. Cela justifie la méthode de démonstration par contraposée.

🧩

Checkpoint

Laquelle de ces formules est une tautologie ?

Méthodes de démonstration

📐

Théorie

Démonstration directe : On suppose $p$ vrai et on dérive $q$ par une chaîne d'implications logiques.

Démonstration par contraposée : Pour prouver $p \Rightarrow q$ , on prouve l'équivalent $\neg q \Rightarrow \neg p$ .

Démonstration par l'absurde : Pour prouver $p$ , on suppose $\neg p$ et on en déduit une contradiction $r \land \neg r$ .

Récurrence simple : Pour prouver $\forall n \in \mathbb{N},\; P(n)$ :

Initialisation : Vérifier $P(0)$ (ou $P(1)$ ).
Hérédité : Supposer $P(n)$ vrai (hypothèse de récurrence) et montrer $P(n+1)$ .

📝

Démonstration par récurrence — somme des entiers

Théorème : Pour tout $n \geq 1$ , $\displaystyle\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$ .

Initialisation : Pour $n = 1$ : $\sum_{k=1}^{1} k = 1$ et $\frac{1 \times 2}{2} = 1$ . Vrai.

Hérédité : Supposons $\displaystyle\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$ .

$\sum_{k=1}^{n+1} k = \left(\sum_{k=1}^{n} k\right) + (n+1) = \frac{n(n+1)}{2} + (n+1) = (n+1)\cdot\frac{n+2}{2} = \frac{(n+1)(n+2)}{2}$

C'est la formule au rang $n+1$ . Par récurrence, le résultat est établi pour tout $n \geq 1$ .

📝

Démonstration par l'absurde — irrationalité de √2

Théorème : $\sqrt{2}$ est irrationnel.

Preuve : Supposons par l'absurde que $\sqrt{2} = \frac{p}{q}$ avec $\pgcd(p,q) = 1$ .

En élevant au carré : $p^2 = 2q^2$ , donc $p^2$ est pair, donc $p$ est pair. Écrivons $p = 2k$ .

Alors $4k^2 = 2q^2$ , soit $q^2 = 2k^2$ , donc $q$ est pair.

Mais alors $2 \mid p$ et $2 \mid q$ , ce qui contredit $\pgcd(p,q) = 1$ . Contradiction.

Donc $\sqrt{2}$ est irrationnel.

⚠️

L'implication n'est pas symétrique

$p \Rightarrow q$ ne signifie PAS $q \Rightarrow p$ . Par exemple : "Il pleut $\Rightarrow$ le sol est mouillé" est vrai, mais "le sol est mouillé $\Rightarrow$ il pleut" est faux. La contraposée $\neg q \Rightarrow \neg p$ est équivalente à $p \Rightarrow q$ , mais PAS le réciproque $q \Rightarrow p$ .

⭐

À retenir

Une proposition est un énoncé ayant exactement une valeur de vérité : vrai ou faux.
Les cinq connecteurs principaux : $\neg$ (NON), $\land$ (ET), $\lor$ (OU), $\Rightarrow$ (IMPLIQUE), $\Leftrightarrow$ (ÉQUIVAUT).
Une implication $p \Rightarrow q$ n'est fausse que lorsque $p$ est vrai et $q$ est faux.
La contraposée $(\neg q \Rightarrow \neg p)$ est logiquement équivalente à $(p \Rightarrow q)$ .
Lois de De Morgan : $\neg(p \land q) \equiv \neg p \lor \neg q$ et $\neg(p \lor q) \equiv \neg p \land \neg q$ .
Quatre grandes méthodes de preuve : directe, contraposée, absurde, récurrence.

Passer aux exercices →