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 \land Q$ (« $P$ et $Q$ ») : vraie si et seulement si $P$ et $Q$ sont toutes deux vraies.

$P \lor 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 \Leftrightarrow 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 \R,\; x^2 \geq 0) = \exists x \in \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 \Leftrightarrow P_1 \Leftrightarrow P_2 \Leftrightarrow \dots \Leftrightarrow 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 \Z, (n \text{ pair}) \Rightarrow (4 \mid n)$.

Négation : $\exists n \in \Z, (n \text{ pair}) \land (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 \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 \lor 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) \land \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 \R, \exists y, x < y$ est vrai, mais $\exists y, \forall x, x < y$ est faux.

Je sais écrire la négation de $P \land Q$, $P \lor 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.