Logique mathématique

Une proposition est un énoncé dont on peut dire, sans ambiguïté, qu'il est vrai (V) ou qu'il est faux (F). Sa valeur de vérité est V ou F, jamais les deux, jamais « un peu vrai ».

• « $5$ est un entier naturel » est une proposition vraie.
• « Tout entier pair est divisible par $4$ » est une proposition fausse (contre-exemple : $6$).
• « $x+1=3$ » n'est pas une proposition tant que $x$ n'est pas fixé : c'est une fonction propositionnelle $P(x)$, vraie pour $x=2$ et fausse sinon.
• « Que la paix soit avec toi » n'est pas une proposition.

• Négation « non $P$ », notée $\neg P$ : vraie lorsque $P$ est fausse, et réciproquement.
• Conjonction « $P$ et $Q$ », notée $P\wedge Q$ : vraie lorsque $P$ et $Q$ sont simultanément vraies.
• Disjonction « $P$ ou $Q$ », notée $P\vee Q$ : vraie dès que l'une au moins des deux est vraie (le « ou » mathématique est inclusif).
• Implication « $P\Rightarrow Q$ » : fausse uniquement lorsque $P$ est vraie et $Q$ fausse.
• Équivalence « $P\iff Q$ » : vraie lorsque $P$ et $Q$ ont la même valeur de vérité.

Soit $P$ : « $5\ge 3$ » (V) et $Q$ : « $5$ est pair » (F). $P\wedge Q$ est F ; $P\vee Q$ est V ; $P\Rightarrow Q$ est F (le seul cas faux : V implique F) ; $Q\Rightarrow P$ est V (une prémisse fausse rend l'implication vraie, quelle que soit la conclusion).

Soit l'implication $P\Rightarrow Q$.

• Sa réciproque est $Q\Rightarrow P$. Elle n'a en général pas la même valeur de vérité.
• Sa contraposée est $(\neg Q)\Rightarrow (\neg P)$. Elle a toujours la même valeur de vérité que $P\Rightarrow Q$.

Pour toutes propositions $P$, $Q$, $R$ :

1. $\neg (\neg P)\iff P$ ;
2. $(P\Rightarrow Q)\iff ((\neg P)\vee Q)$ ;
3. $\neg (P\Rightarrow Q)\iff (P\wedge (\neg Q))$ ;
4. $(P\Rightarrow Q)\iff ((\neg Q)\Rightarrow (\neg P))$ (contraposée) ;
5. $(P\iff Q)\iff ((P\Rightarrow Q)\wedge (Q\Rightarrow P))$ ;
6. transitivité : $((P\Rightarrow Q)\wedge (Q\Rightarrow R))\Rightarrow (P\Rightarrow R)$.

La négation de « $x>0$ et $x<5$ » est « $x\le 0$ ou $x\ge 5$ ». La négation de « $n$ est pair ou $n$ est multiple de $3$ » est « $n$ est impair et $n$ n'est pas multiple de $3$ ».

« $\forall x\in E,P(x)$ » (pour tout $x$ de $E$, $P(x)$) est vraie lorsque tout élément de $E$ vérifie $P$.

« $\exists x\in E,P(x)$ » (il existe $x$ dans $E$ tel que $P(x)$) est vraie lorsque l'on peut trouver au moins un élément de $E$ vérifiant $P$. La notation $\exists !$ signifie « il existe un unique ».

• $\forall n\in \mathbb{N},n^2\ge 0$ : vrai.
• $\exists x\in \mathbb{R},x^2=2$ : vrai ($x=\sqrt{2}$).
• $\forall x\in \mathbb{R},x^2>0$ : faux ($x=0$).
• $\exists !x\in \mathbb{R},2x+1=0$ : vrai ($x=-\frac{1}{2}$).

Pour nier un « pour tout », on exhibe un contre-exemple ; pour nier un « il existe », on montre que la propriété échoue partout.

• « $\forall x\in \mathbb{R},\exists y\in \mathbb{R},y>x$ » est vraie : pour chaque $x$, $y=x+1$ convient. Le $y$ dépend de $x$.
• « $\exists y\in \mathbb{R},\forall x\in \mathbb{R},y>x$ » est fausse : il n'existe pas de réel plus grand que tous les réels. Ici le même $y$ devrait convenir pour tous les $x$.

Inverser $\forall$ et $\exists$ change le sens de l'énoncé. En revanche deux quantificateurs de même nature commutent : $\forall x,\forall y$ est identique à $\forall y,\forall x$.

Si $n$ est pair alors $n^2$ est pair. Démonstration. Si $n=2k$ ($k\in \mathbb{Z}$), alors $n^2=4k^2=2(2k^2)$ est pair.

« Si $n^2$ est pair alors $n$ est pair. » Par contraposée : si $n$ est impair, $n=2k+1$ et $n^2=4k^2+4k+1=2(2k^2+2k)+1$ est impair.

$\sqrt{2}$ est irrationnel. Supposons $\sqrt{2}=\frac{p}{q}$ avec $p,q$ entiers premiers entre eux. Alors $p^2=2q^2$ : $p^2$ est pair, donc $p$ est pair (contraposée ci-dessus), $p=2k$, puis $q^2=2k^2$ et $q$ est pair. $p$ et $q$ seraient tous deux pairs : contradiction avec « premiers entre eux ».

« Tout entier impair est premier » est faux : $9=3\times 3$. « $\forall n\in \mathbb{N},n^2+n+41$ est premier » est faux : pour $n=41$, $41^2+41+41=41\times 43$.

Pour tout entier $n$, $n(n+1)$ est pair : si $n$ est pair, le produit l'est ; si $n$ est impair, $n+1$ est pair et le produit l'est aussi.

$\sqrt{x+3}=x+1$. L'élévation au carré n'est pas une équivalence : $x+3=(x+1{)}^2$ donne $x^2+x-2=0$, soit $x=1$ ou $x=-2$. Or $x=-2$ rend $x+1<0$ : on ne garde que $x=1$ (vérification : $\sqrt{4}=2$).

Soit $P(n)$ une propriété dépendant d'un entier $n$ et $n_0\in \mathbb{N}$. Si

1. $P(n_0)$ est vraie (initialisation) ;
2. pour tout entier $n\ge n_0$, $P(n)\Rightarrow P(n+1)$ (hérédité), alors $P(n)$ est vraie pour tout entier $n\ge n_0$.

Démontrer que pour tout $n\ge 1$ : $1+2+\dots +n=\frac{n(n+1)}{2}$.

Initialisation. Pour $n=1$ : $1=\frac{1\times 2}{2}$. Vraie.

Hérédité. Soit $n\ge 1$ tel que $1+\dots +n=\frac{n(n+1)}{2}$. Alors $1+\dots +n+(n+1)=\frac{n(n+1)}{2}+(n+1)=(n+1)(\frac{n}{2}+1)=\frac{(n+1)(n+2)}{2}$, qui est bien la formule au rang $n+1$.

Conclusion. La formule est vraie pour tout $n\ge 1$.

(Inégalité de Bernoulli) Pour tout réel $a\ge 0$ et tout $n\in \mathbb{N}$ : $(1+a{)}^n\ge 1+na$.

Initialisation. $n=0$ : $(1+a{)}^0=1\ge 1+0$.

Hérédité. Supposons $(1+a{)}^n\ge 1+na$. En multipliant par $1+a>0$ : $(1+a{)}^{n+1}\ge (1+na)(1+a)=1+(n+1)a+n{a}^2\ge 1+(n+1)a$ car $n{a}^2\ge 0$.

Conclusion. L'inégalité est vraie pour tout $n\in \mathbb{N}$.

(Divisibilité) Pour tout $n\in \mathbb{N}$, $4^n-1$ est divisible par $3$.

Initialisation. $4^0-1=0=3\times 0$.

Hérédité. Supposons $4^n-1=3k$ avec $k\in \mathbb{N}$. Alors $4^{n+1}-1=4\times 4^n-1=4(3k+1)-1=12k+3=3(4k+1)$.

Conclusion. $3$ divise $4^n-1$ pour tout $n$.

(Suite définie par récurrence) Soit $(u_n)$ définie par $u_0=2$ et $u_{n+1}=2u_n-1$. Montrer que $u_n=2^n+1$ pour tout $n$.

Initialisation. $u_0=2=2^0+1$.

Hérédité. Si $u_n=2^n+1$, alors $u_{n+1}=2(2^n+1)-1=2^{n+1}+1$.

Conclusion. $u_n=2^n+1$ pour tout $n\in \mathbb{N}$.

Si $P(n_0)$ et $P(n_0+1)$ sont vraies, et si pour tout $n\ge n_0$, $(P(n)\wedge P(n+1))\Rightarrow P(n+2)$, alors $P(n)$ est vraie pour tout $n\ge n_0$. On l'utilise pour les suites dont chaque terme dépend des deux précédents.

Soit $(F_n)$ la suite de Fibonacci : $F_0=0$, $F_1=1$, $F_{n+2}=F_{n+1}+F_n$. Montrons que $F_n\le 2^n$ pour tout $n$. Initialisation : $F_0=0\le 1$ et $F_1=1\le 2$. Hérédité : si $F_n\le 2^n$ et $F_{n+1}\le 2^{n+1}$, alors $F_{n+2}\le 2^n+2^{n+1}=3\times 2^n\le 4\times 2^n=2^{n+2}$.

Si $P(n_0)$ est vraie et si, pour tout $n\ge n_0$, le fait que $P(k)$ soit vraie pour tous les $k$ de $n_0$ à $n$ entraîne $P(n+1)$, alors $P(n)$ est vraie pour tout $n\ge n_0$.

Tout entier $n\ge 2$ admet un diviseur premier. Récurrence forte : $2$ est premier. Soit $n\ge 2$ ; si $n$ est premier, c'est fini ; sinon $n=ab$ avec $2\le a<n$, et par hypothèse (appliquée à $a$) $a$ admet un diviseur premier, qui divise aussi $n$.