Logique mathématique

énoncé mathématique qui est soit vrai (V), soit faux (F). Exemple : « $2+2=4$ » est vraie ; « tout nombre premier est impair » est fausse.

de $P$, notée $\neg P$ (ou $\overline{P}$) : proposition qui est vraie exactement quand $P$ est fausse.

$P\wedge Q$ (« $P$ et $Q$ ») : vraie si et seulement si $P$ et $Q$ sont toutes deux vraies.

$P\vee Q$ (« $P$ ou $Q$ ») : vraie si au moins l'une des deux est vraie (ou inclusif).

$P\Rightarrow Q$ (« si $P$ alors $Q$ ») : fausse uniquement quand $P$ est vraie et $Q$ fausse ; vraie dans tous les autres cas.

$P\iff Q$ (« $P$ équivaut à $Q$ ») : vraie si $P$ et $Q$ ont la même valeur de vérité.

de $P\Rightarrow Q$ : c'est $Q\Rightarrow P$. Attention : une implication et sa réciproque ne sont pas équivalentes en général.

de $P\Rightarrow Q$ : c'est $\neg Q\Rightarrow \neg P$. Elle est toujours équivalente à l'implication de départ.

$\forall$ (« pour tout »). $\forall x\in E,P(x)$ signifie que $P(x)$ est vraie pour chaque élément $x$ de $E$.

$\exists$ (« il existe »). $\exists x\in E,P(x)$ signifie qu'il existe au moins un $x$ dans $E$ tel que $P(x)$ est vraie.

un élément particulier qui prouve qu'une proposition du type $\forall x,P(x)$ est fausse.

$P\Rightarrow Q$ est vraie sauf si $P$ est vraie et $Q$ fausse. En particulier, « faux implique n'importe quoi » est toujours vraie.

• Remplacer $\forall$ par $\exists$ et inversement.
• Nier la proposition interne.
• Exemple : $\neg (\forall x\in \mathbb{R},x^2\ge 0)=\exists x\in \mathbb{R},x^2<0$ (ici faux, car la proposition initiale est vraie).

• Méthode directe : prouver les deux implications $P\Rightarrow Q$ et $Q\Rightarrow P$.
• Méthode par chaîne d'équivalences : $P\iff P_1\iff P_2\iff \cdots \iff Q$ (vérifier que chaque étape est bien une équivalence).

• Trouver un contre-exemple : un $x_0$ tel que $P(x_0)$ est fausse.
• Un seul contre-exemple suffit.

• Exhiber explicitement un élément $x_0$ et vérifier que $P(x_0)$ est vraie.
• Ou faire une preuve d'existence non constructive (plus rare au lycée).

Énoncé : $\forall n\in \mathbb{Z},(n\text{ pair})\Rightarrow (4\mid n)$.

Négation : $\exists n\in \mathbb{Z},(n\text{ pair})\wedge (4\nmid n)$.

Contre-exemple : $n=6$ est pair mais pas divisible par $4$. Donc l'énoncé est faux.

Prouver : « si $n^2$ est pair, alors $n$ est pair » ($n\in \mathbb{Z}$).

La contraposée est plus simple : « si $n$ est impair, alors $n^2$ est impair ». Si $n=2k+1$, alors $n^2=4k^2+4k+1=2(2k^2+2k)+1$ est impair. La contraposée étant vraie, l'implication initiale l'est aussi.

$P$ : « $x=2$ ». $Q$ : « $x^2=4$ ».

$P\Rightarrow Q$ est vraie. Mais la réciproque $Q\Rightarrow P$ est fausse : $x=-2$ vérifie $Q$ mais pas $P$. Donc $P$ et $Q$ ne sont pas équivalentes.

en mathématiques, « ou » est toujours inclusif : $P\vee Q$ est vraie si au moins l'une des deux est vraie, y compris quand les deux sont vraies.

$P\Rightarrow Q$ ne veut pas dire $Q\Rightarrow P$. Toujours vérifier dans quel sens l'énoncé est écrit.

la contraposée est logiquement équivalente à l'implication de départ ; la réciproque, non.

dans $\neg (\forall x,P(x)\Rightarrow Q(x))$, on obtient $\exists x,P(x)\wedge \neg Q(x)$. Attention à bien nier aussi l'implication intérieure.

$\forall x,\exists y$ et $\exists y,\forall x$ ne signifient pas la même chose. Exemple : $\forall x\in \mathbb{R},\exists y,x<y$ est vrai, mais $\exists y,\forall x,x<y$ est faux.

Je sais écrire la négation de $P\wedge Q$, $P\vee Q$, $P\Rightarrow Q$.

Je sais former la contraposée et la réciproque d'une implication.

Je sais nier une proposition avec quantificateurs $\forall$ et $\exists$.

Je sais trouver un contre-exemple pour réfuter une proposition universelle.

Je sais prouver une équivalence en séparant les deux implications.

Je sais que la contraposée est équivalente à l'implication, mais pas la réciproque.