Résumé CM 5 : Logique (L1 Maths-info)

Bonjour à tou·te·s ! Aujourd'hui, nous allons revenir sur le CM sur la logique qui a eu lieu jeudi dernier – et oui, on fait le chapitre 3 après le chapitre 4, c'est parfaitement logique.

Chapitre 3. Logique. 

1. Prédicats et assertions.

Une assertion, c'est un énoncé mathématique qui est soit vrai, soit faux. On d'une assertion valide que sa valeur de vérité est "Vrai" et d'une assertion erronée que sa valeur de vérité est "Faux". Par exemple, $$\forall\;n\in\mathbb N,\;n^2<n$$ est une assertion qui a pour valeur de vérité "Faux". Un prédicat, c'est simplement un bout d'assertion qui peut par exemple dépendre d'une variable dont on n'a pas défini la nature préalablement. Par exemple : $$n^2<n$$ est un prédicat. On ne sait pas qui est $n$, et selon le quantificateur ($\forall$, $\exists$ ou encore $\exists!$) ainsi que le domaine de définition de $n$ que l'on choisit pour rendre ce prédicat moins ambiguë, il se peut que l'on obtienne un résultat juste ou complètement à côté de la plaque. Par exemple, $\forall\;n\in\mathbb Z,\;n^2<n$ est faux mais $\forall\;x\in[1/3,2/3],\;n^2<n$ est vrai. On ne peut donc forcément assigner une valeur de vérité à un prédicat.

Opérations sur les prédicats.

Soient deux prédicats A et B. Voici les opérations que l'on peut avoir sur les prédicats en logique classique :

• et ($\wedge$) : (A et B) vrai si et seulement si A vrai, B vrai.
• ou ($\vee$) : (A ou B) vrai si et seulement si soit A vrai, soit B vrai, soit (A et B) vrai.
• non- ($\neg$) : non-A vrai si et seulement si A faux.
• implique ($\implies$) : (A implique B) est vrai si et seulement si (non-A ou B).

  
2. Quelques schémas de démonstrations.

2.1. Disjonction de cas.
Prenons l'exemple du cours, qui demandait de trouver l'ensemble $\{x\in\mathbb R:|x-3|+|x+4|\le7\}$. Pour cela, on se munit de la définit de la valeur absolue, càd
$$|x|:=\left\{\begin{array}cx&x\ge0\\-x&x\le0\end{array}\right.$$
On trouve déjà que $x-3\ge0\iff x\ge3$ et que $x+4\ge0\iff x\ge-4$, donc
$$\begin{array}{|c|ccccccc|} \hline x&-\infty&&-4&&3&&+\infty\\ \hline|x-3|&&3-x&:&&|&x-3\\ \hdashline|x-4|&&-4-x&|&&:&x+4\\ \hline|x-3|+|x-4|&&-1-2x&|&7&|&2x+1\\ \hline\end{array}$$
Pour $x\le-4$ on a donc $-1-2x\le7\iff x\ge-4$ donc seulement lorsque $x=-4$, pour $-4\le x\le3$ c'est plutôt trivial car on a $7\le7$, et pour $x\ge3$ on a $2x+1\le7\iff x\le3$ donc seulement lorsque $x=3$. Au final, on se retrouve avec $\{x\in\mathbb R:|x-3|+|x+4|\le7\}=[-4,\;3]$.

2.2. Démonstrations ensemblistes.

• $A\subset B$ : Soit $x\in A$. Montrons que $x\in B$. [...] donc $x\in B$. Ainsi, $A\subset B$.
• On peut également partir de $E\setminus B\subset E\setminus A$ : Soit $x\not\in B$. Montrons que $x\not\in A$. [...] donc $x\not\in A$. Ainsi, $A\subset B$.
• $x\in A\cap B$ : $x\in A$ et $x\in B$.
• $x\in A\cup B$ : Soit $x\not\in A$. Montrons que $x\in B$. [...] donc $x\in B$. Ainsi, $x\in A\cup B$.

2.3. Preuves par récurrence (simple).
Imaginons que l'on veuille montrer un assertion du type $\forall\;n\in\mathbb N,\;H_n$. On montre ainsi $H_0$ (initialisation) puis on montre que $H_n\implies H_{n+1}$ (hérédité), ce qui prouve notre assertion par récurrence.