Propositions et fonctions propositionnelles
Proposition
Définition
Une proposition est un énoncé mathématique qui est soit vrai (V), soit faux (F), mais jamais les deux à la fois.
On dit que V ou F est la valeur de vérité de la proposition.
Exemple
- « $\sqrt{9}=3$ » est une proposition vraie.
- « $2>5$ » est une proposition fausse.
- « $7$ est un nombre premier » est une proposition vraie.
- « $x+1=3$ » n’est pas une proposition : sa vérité dépend de $x$.
Fonction propositionnelle
Définition
Une fonction propositionnelle $P(x)$ est un énoncé qui contient une variable $x$ d’un ensemble $E$ et qui devient une proposition quand on remplace $x$ par un élément de $E$.
Exemple
Soit $P(x)$ : « $x^2\geq4$ » avec $x\in\mathbb{R}$.
- $P(3)$ : « $9\geq4$ » est vraie ;
- $P(1)$ : « $1\geq4$ » est fausse.
Les quantificateurs
Définition
Soit $P(x)$ une fonction propositionnelle, $x\in E$.
- Quantificateur universel : « $(\forall x\in E)\ P(x)$ » se lit « pour tout $x$ de $E$, $P(x)$ ».
- Quantificateur existentiel : « $(\exists x\in E)\ P(x)$ » se lit « il existe au moins un $x$ de $E$ tel que $P(x)$ ».
- « $(\exists!x\in E)\ P(x)$ » se lit « il existe un unique $x$ de $E$ tel que $P(x)$ ».
Méthode Déterminer la valeur de vérité
- Pour montrer que « $(\forall x\in E)\ P(x)$ » est vraie : on fait une démonstration pour un $x$ quelconque.
- Pour montrer qu’elle est fausse : il suffit d’un contre-exemple.
- Pour montrer que « $(\exists x\in E)\ P(x)$ » est vraie : il suffit de donner un $x$ qui convient.
Exemple
- « $(\forall x\in\mathbb{R})\ x^2+1>0$ » est vraie : $x^2\geq0$, donc $x^2+1\geq1>0$.
- « $(\forall x\in\mathbb{R})\ x^2>x$ » est fausse : pour $x=\dfrac{1}{2}$, $x^2=\dfrac{1}{4}<\dfrac{1}{2}$.
- « $(\exists x\in\mathbb{R})\ x^2=2$ » est vraie : $x=\sqrt{2}$ convient.
- « $(\exists!x\in\mathbb{R})\ 2x+1=0$ » est vraie : la seule solution est $x=-\dfrac{1}{2}$.
Erreur fréquente L’ordre des quantificateurs compte
- « $(\forall x\in\mathbb{R})(\exists y\in\mathbb{R})\ x+y=0$ » est vraie : pour chaque $x$, on prend $y=-x$.
- « $(\exists y\in\mathbb{R})(\forall x\in\mathbb{R})\ x+y=0$ » est fausse : aucun $y$ ne convient pour tous les $x$.
[!] On ne permute pas $\forall$ et $\exists$
Application
Donner la valeur de vérité de : a) $(\forall n\in\mathbb{N})\ n^2\geq n$ ; b) $(\exists x\in\mathbb{R})\ x^2+4=0$.
Réponse
a) Vraie : $n^2-n=n(n-1)$ et $n\geq0$, $n-1\geq0$ si $n\geq1$ ; et pour $n=0$ : $0\geq0$.
b) Fausse : pour tout $x$, $x^2+4\geq4>0$.
Les connecteurs logiques
Définition
À partir de propositions $P$ et $Q$, les connecteurs logiques permettent de construire de nouvelles propositions : la négation, la conjonction, la disjonction, l’implication et l’équivalence.
La négation
Définition
Soit $P$ une proposition. La négation de $P$ est la proposition qui est vraie quand $P$ est fausse, et fausse quand $P$ est vraie.
La négation de $P$ a deux notations : $\overline{P}$ (barre au-dessus de $P$) ou $\neg P$. Elle se lit « non $P$ ».
>> Dans ce cours, on utilise la notation $\overline{P}$.
Propriété Table de vérité
| $P$ | $\overline{P}$ |
| V | F |
| F | V |
Exemple
- $P$ : « $\sqrt{4}=2$ » (vraie) ; $\overline{P}$ : « $\sqrt{4}\neq2$ » (fausse).
- $P$ : « $x>3$ » ; $\overline{P}$ : « $x\leq3$ ».
- $P$ : « $n$ est pair » ; $\overline{P}$ : « $n$ est impair ».
La conjonction « et »
Définition
Soient $P$ et $Q$ deux propositions. La conjonction de $P$ et $Q$, notée $P\wedge Q$ (« $P$ et $Q$ »), est vraie seulement quand $P$ et $Q$ sont toutes les deux vraies.
Propriété Table de vérité
| $P$ | $Q$ | $P\wedge Q$ |
| V | V | V |
| V | F | F |
| F | V | F |
| F | F | F |
Exemple
- « $2<3$ et $5$ est premier » est vraie (les deux sont vraies).
- « $2<3$ et $4$ est impair » est fausse (la deuxième est fausse).
La disjonction « ou »
Définition
Soient $P$ et $Q$ deux propositions. La disjonction de $P$ et $Q$, notée $P\vee Q$ (« $P$ ou $Q$ »), est vraie quand au moins une des deux est vraie ; elle est fausse seulement si les deux sont fausses.
Propriété Table de vérité
| $P$ | $Q$ | $P\vee Q$ |
| V | V | V |
| V | F | V |
| F | V | V |
| F | F | F |
Exemple
- « $2<3$ ou $4$ est impair » est vraie (la première est vraie).
- « $2>3$ ou $4$ est impair » est fausse (les deux sont fausses).
Remarque
Le « ou » mathématique est inclusif : « $P\vee Q$ » est vraie aussi quand $P$ et $Q$ sont vraies toutes les deux.
L’implication
Définition
Soient $P$ et $Q$ deux propositions. L’implication « $P\Rightarrow Q$ » est la proposition « $\overline{P}\vee Q$ ». Elle se lit « $P$ implique $Q$ » ou « si $P$ alors $Q$ ».
Propriété Table de vérité
| $P$ | $Q$ | $\overline{P}$ | $P\Rightarrow Q$ |
| V | V | F | V |
| V | F | F | F |
| F | V | V | V |
| F | F | V | V |
[!] « $P\Rightarrow Q$ » est fausse uniquement quand $P$ est vraie et $Q$ est fausse
Exemple
- « $x=2\Rightarrow x^2=4$ » est vraie.
- « $1>2\Rightarrow3=0$ » est vraie : la prémisse « $1>2$ » est fausse.
- La réciproque « $x^2=4\Rightarrow x=2$ » est fausse : pour $x=-2$, $x^2=4$ mais $x\neq2$.
Remarque
- « $Q\Rightarrow P$ » s’appelle l’implication réciproque de « $P\Rightarrow Q$ ».
- Si « $P\Rightarrow Q$ » est vraie : $P$ est une condition suffisante pour $Q$, et $Q$ est une condition nécessaire pour $P$.
L’équivalence
Définition
Soient $P$ et $Q$ deux propositions. L’équivalence « $P\iff Q$ » est la proposition « $(P\Rightarrow Q)\wedge(Q\Rightarrow P)$ ». Elle se lit « $P$ équivaut à $Q$ » ou « $P$ si et seulement si $Q$ ».
Propriété Table de vérité
| $P$ | $Q$ | $P\Rightarrow Q$ | $Q\Rightarrow P$ | $P\iff Q$ |
| V | V | V | V | V |
| V | F | F | V | F |
| F | V | V | F | F |
| F | F | V | V | V |
« $P\iff Q$ » est vraie quand $P$ et $Q$ ont la même valeur de vérité
Exemple
- Pour $x\in\mathbb{R}$ : « $2x-6=0\iff x=3$ » est vraie.
- « $x^2=4\iff x=2$ » est fausse : la réciproque « $x^2=4\Rightarrow x=2$ » est fausse.
Application
Donner la valeur de vérité de : a) « $\sqrt{4}=2$ et $\pi<3$ » ; b) « $5$ est pair ou $5>1$ » ; c) « $1>2\Rightarrow 3=0$ » ; d) « $2+2=5\iff 3>4$ ».
Réponse
a) Fausse : « $\pi<3$ » est fausse ($\pi\approx3{,}14$).
b) Vraie : « $5>1$ » est vraie.
c) Vraie : la prémisse « $1>2$ » est fausse.
d) Vraie : les deux propositions sont fausses, elles ont la même valeur de vérité.
Remarque Récapitulatif
| $P$ | $Q$ | $\overline{P}$ | $P\wedge Q$ | $P\vee Q$ | $P\Rightarrow Q$ | $P\iff 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 |
Lois logiques
Définition
Une loi logique est une proposition composée qui est toujours vraie, quelles que soient les valeurs de vérité des propositions qui la composent.
Propriété Lois usuelles
- Double négation : $\overline{\overline{P}}\iff P$ ;
- Lois de Morgan : $\overline{P\wedge Q}\iff(\overline{P}\vee\overline{Q})$ ;
$\overline{P\vee Q}\iff(\overline{P}\wedge\overline{Q})$
- Négation d’une implication : $\overline{P\Rightarrow Q}\iff(P\wedge\overline{Q})$ ;
- Contraposée : $(P\Rightarrow Q)\iff(\overline{Q}\Rightarrow\overline{P})$ ;
- Transitivité : $\left[(P\Rightarrow Q)\wedge(Q\Rightarrow R)\right]\Rightarrow(P\Rightarrow R)$ ;
- Distributivité : $P\wedge(Q\vee R)\iff(P\wedge Q)\vee(P\wedge R)$ ;
$P\vee(Q\wedge R)\iff(P\vee Q)\wedge(P\vee R)$
Méthode Démontrer une loi logique
On dresse la table de vérité et on vérifie que les deux membres ont la même colonne (ou que la proposition est toujours V).
Exemple Loi de Morgan
| $P$ | $Q$ | $P\wedge Q$ | $\overline{P\wedge Q}$ | $\overline{P}$ | $\overline{Q}$ | $\overline{P}\vee\overline{Q}$ |
| V | V | V | F | F | F | F |
| V | F | F | V | F | V | V |
| F | V | F | V | V | F | V |
| F | F | F | V | V | V | V |
Les colonnes de $\overline{P\wedge Q}$ et de $\overline{P}\vee\overline{Q}$ sont identiques : la loi est démontrée
Négation d’une proposition quantifiée
Propriété
$\overline{(\forall x\in E)\ P(x)}\iff(\exists x\in E)\ \overline{P(x)}$
$\overline{(\exists x\in E)\ P(x)}\iff(\forall x\in E)\ \overline{P(x)}$
Méthode Écrire une négation
- on remplace $\forall$ par $\exists$ et $\exists$ par $\forall$ ;
- on garde l’ensemble $E$ ;
- on nie la propriété : $<$ devient $\geq$, $=$ devient $\neq$, « et » devient « ou », « $P\Rightarrow Q$ » devient « $P\wedge\overline{Q}$ ».
Exemple
- La négation de « $(\forall x\in\mathbb{R})\ x^2+x+1>0$ » est :
$(\exists x\in\mathbb{R})\ x^2+x+1\leq0$
- La négation de « $(\exists n\in\mathbb{N})\ n^2=10$ » est :
$(\forall n\in\mathbb{N})\ n^2\neq10$
- La négation de « $(\forall x\in\mathbb{R})\ (x>1\Rightarrow x^2>1)$ » est :
$(\exists x\in\mathbb{R})\ (x>1\wedge x^2\leq1)$
Erreur fréquente
La négation de « $x>0$ » est « $x\leq0$ » et non « $x<0$ » : on n’oublie pas le cas d’égalité.
Les types de raisonnement
Raisonnement par équivalences successives
Méthode
Pour montrer $P$, on la transforme équivalence après équivalence jusqu’à une proposition vraie évidente.
Exemple
Montrer que $(\forall(a,b)\in\mathbb{R}^2)\ a^2+b^2\geq2ab$.
$a^2+b^2\geq2ab\iff a^2-2ab+b^2\geq0$
$\iff(a-b)^2\geq0$
La dernière proposition est vraie (un carré est positif) :
$(\forall(a,b)\in\mathbb{R}^2)\ a^2+b^2\geq2ab$
Raisonnement par contre-exemple
Méthode
Pour montrer que « $(\forall x\in E)\ P(x)$ » est fausse, on montre sa négation : on trouve un $x_0\in E$ tel que $P(x_0)$ soit fausse.
Exemple
« $(\forall n\in\mathbb{N})\ n^2+n+41$ est premier » est-elle vraie ?
Pour $n=40$ :
$40^2+40+41=40\times41+41$
$=41\times41$
$41^2$ n’est pas premier : la proposition est fausse
Raisonnement par contraposée
Méthode
On utilise la loi : $(P\Rightarrow Q)\iff(\overline{Q}\Rightarrow\overline{P})$.
Pour montrer « $P\Rightarrow Q$ », on montre « **si $Q$ est fausse, alors $P$ est fausse** ».
Exemple
Soit $n\in\mathbb{N}$. Montrer : si $n^2$ est pair, alors $n$ est pair.
Contraposée : si $n$ est impair, alors $n^2$ est impair.
Si $n$ est impair, il existe $k\in\mathbb{N}$ tel que $n=2k+1$ :
$n^2=(2k+1)^2$
$=4k^2+4k+1$
$=2\left(2k^2+2k\right)+1$
$n^2$ est impair ; la contraposée est vraie, donc :
Si $n^2$ est pair, alors $n$ est pair
Raisonnement par l’absurde
Méthode
Pour montrer $P$, on suppose que $\overline{P}$ (la négation de $P$) est vraie et on arrive à une contradiction (une proposition fausse) : donc $P$ est vraie.
Exemple
Montrer que $\sqrt{2}\notin\mathbb{Q}$.
Supposons que $\sqrt{2}=\dfrac{p}{q}$ avec $p,q\in\mathbb{N}^*$ et la fraction irréductible.
$\sqrt{2}=\dfrac{p}{q}\iff p^2=2q^2$
Donc $p^2$ est pair, et (paragraphe précédent) $p$ est pair : $p=2k$.
$4k^2=2q^2\iff q^2=2k^2$
Donc $q^2$ est pair, et $q$ est pair : $p$ et $q$ sont pairs, la fraction n’est pas irréductible. Contradiction.
$\sqrt{2}\notin\mathbb{Q}$
Raisonnement par disjonction des cas
Méthode
Pour montrer $P$, on sépare en cas qui couvrent toutes les possibilités, et on montre $P$ dans chaque cas (loi : $\left[(Q\Rightarrow P)\wedge(\overline{Q}\Rightarrow P)\right]\Rightarrow P$).
Exemple
Montrer que pour tout $n\in\mathbb{N}$, $n(n+1)$ est pair.
- Cas 1 : $n$ pair, $n=2k$ : $n(n+1)=2k(n+1)$ est pair ;
- Cas 2 : $n$ impair, $n=2k+1$ : $n+1=2(k+1)$, donc $n(n+1)=2n(k+1)$ est pair.
Dans les deux cas, $n(n+1)$ est pair
Raisonnement par récurrence
Méthode
Pour montrer $(\forall n\geq n_0)\ P(n)$ :
1. Initialisation : on vérifie que $P(n_0)$ est vraie ;
2. Hérédité : on suppose $P(n)$ vraie pour un $n\geq n_0$ et on montre $P(n+1)$ ;
3. Conclusion : $P(n)$ est vraie pour tout $n\geq n_0$.
Exemple
Montrer que $(\forall n\in\mathbb{N}^*)\ 1+2+\cdots+n=\dfrac{n(n+1)}{2}$.
Initialisation : pour $n=1$, $1=\dfrac{1\times2}{2}$ ✔.
Hérédité : on suppose $1+2+\cdots+n=\dfrac{n(n+1)}{2}$ et on montre la formule pour $n+1$ :
$1+2+\cdots+n+(n+1)=\dfrac{n(n+1)}{2}+(n+1)$
$=\dfrac{n(n+1)+2(n+1)}{2}$
$=\dfrac{(n+1)(n+2)}{2}$
C’est la formule au rang $n+1$ ✔.
Par récurrence : $(\forall n\in\mathbb{N}^*)\ 1+2+\cdots+n=\dfrac{n(n+1)}{2}$
Erreur fréquente
- Oublier l’initialisation : l’hérédité seule ne prouve rien.
- Dans l’hérédité, il faut utiliser l’hypothèse $P(n)$.
À retenir
- $P\Rightarrow Q$ est fausse seulement si $P$ est vraie et $Q$ fausse.
- Négation : $\forall\leftrightarrow\exists$, « et » $\leftrightarrow$ « ou », $\overline{P\Rightarrow Q}\iff P\wedge\overline{Q}$.
- Faux pour tout ⇒ un contre-exemple ; vrai pour tout ⇒ démonstration générale.
- Contraposée, absurde, cas, récurrence : on annonce le raisonnement avant de l’écrire.