Chapitre 7: Rudiments de logique et opérations élémentaires ensemblistes.

Projection, conjonction, négation.

Soient $p$ et $q$ deux énoncés mathématiques :

• L’énoncé $p \text{ ET } q$ est l’énoncé qui est vrai dans le seul cas où $p$ est vrai et $q$ est vrai.

• L’énoncé $p \text{ OU } q$ est l’énoncé qui est vrai dès que l’un des deux est vrai.

Remarque importante : le OU en mathématiques n’est pas exclusif : il n’existe pas de cas où $p$ et $q$ sont simultanément faux.

Par exemple : un triangle isocèle possède deux côtés de même longueur ou deux angles de même mesure.

• L’énoncé $\text{NON } p$ (négation de $p$) est l’énoncé qui est vrai dans le seul cas où $p$ est faux.

Soient $p, q, r$ trois énoncés mathématiques.

1. $(p \text{ ET } q) \text{ ET } r$

2. $(p \text{ OU } q) \text{ ET } r = (p \text{ OU } r) \text{ ET } (q \text{ OU } r)$

Lois de De Morgan :

Autres lois :

• $\text{NON}(\text{NON } p) = p$

• $(\text{NON } p) \text{ OU } p$ est toujours vrai (principe d’identité)

• $(\text{NON } p) \text{ ET } p$ est toujours faux (principe de non-contradiction)

Implication :¶

L’implication de $q$ par $p$ est l’énoncé $(\text{NON } p) \text{ OU } q$. Cet énoncé est faux dans le seul cas où $p$ est vrai et $q$ est faux.

$p$ : la prémisse $q$ : la conclusion Quand l’implication de $p$ par $q$ est vraie, on dit : si $p$ alors $q$ $p$ implique $q$ il suffit que $p$ pour avoir $q$ $p$ est une condition suffisante pour $q$ $q$ est une condition nécessaire pour $p$ On note $p \Rightarrow q$

1.) $\Rightarrow$ ne veut pas dire “Donc”¶

Équivalence :¶

L’équivalence entre $p$ et $q$ est l’énoncé $(p \Rightarrow q) \text{ ET } (q \Rightarrow p)$ $(\text{NON } p \text{ OU } q) \text{ ET } (\text{NON } q \text{ OU } p)$ Cette énoncé est notée $p \leftrightarrow q$

Lorsque $p \leftrightarrow q$ est vrai, on note $p \Leftrightarrow q$ et on dit : $p$ équivalent à $q$ $p$ si et seulement si $q$ $r$ est une condition nécessaire et suffisante de $p$ Il faut et il suffit d’avoir $p$ pour avoir $q$

Principe de contraposition :¶

L’implication $\text{NON } p \Rightarrow \text{NON } q$ s’appelle contraposée de $p \Rightarrow q$. On admet d’équivalence :

Exemple : Soit $n \in \mathbb{Z}$ Si $n^2$ est pair alors $n$ est pair. Supposons $n$ impair. Il existe $k \in \mathbb{Z}$ tel que $n = 2k + 1$. Alors $n^2 = 1 + 2(2k^2 + 2k)$. Donc $n^2$ est impair. Par contraposition : si $n^2$ n’est pas pair, alors $n$ n’est pas pair.

Attention : La négation d’une implication n’est pas une implication :

Ensembles, relations, E, C¶

Un ensemble peut être défini par extension ou par compréhension !

Dans le cas contraire, on dit qu’il n’appartient pas à $E$ et on note $x \notin E$.

Un ensemble à un seul élément s’appelle un singleton.

Un ensemble de deux éléments s’appelle une paire.

Il existe un ensemble sans aucun élément, on l’appelle ensemble vide. On le note $\varnothing$.

Soit $A, B$ deux ensembles. Lorsque tout élément de $A$ est aussi élément de $B$, on dit que $A$ est inclus dans $B$.

On note alors $A \subset B$. $\mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R} \subset \mathbb{C}$ $A \subset B \Leftrightarrow (\forall x)(x \in A \Rightarrow x \in B)$

Deux ensembles $A$ et $B$ ont exactement les mêmes éléments, $A = B \Leftrightarrow (A \subset B \text{ et } B \subset A)$

On note $\varnothing \subset E$.

Quantification :¶

n’est pas un énoncé mathématique car la variable $x$ n’est pas quantifiée.

Soit $E$ un ensemble : $P(x)$ : une propriété définissant $E$ $A = \{x \in E \mid P(x)\}$

Cela se lit aussi : pour tout $x \in E$, $P(x)$ est vrai.

Quantificateurs et connecteurs logiques¶

Soient $P, Q$ deux propriétés définies sur un ensemble $E$.

1. $(\forall x \in E)(P(x) \text{ ET } Q(x))$ a le même sens que $(\forall x \in E, P(x)) \text{ ET } (\forall x \in E, Q(x))$

2. $(\forall x \in E)(P(x) \text{ OU } Q(x))$ a le même sens que $(\forall x \in E, P(x)) \text{ OU } (\forall x \in E, Q(x))$

Exemple : $E = \mathbb{N}$ $(\forall x \in \mathbb{N})(x \text{ est pair OU } x \text{ est impair})$ : V $(\forall x \in \mathbb{N}, x \text{ est pair}) \text{ OU } (\forall x \in \mathbb{N}, x \text{ est impair})$ : F

Cependant :

3. $(\exists x \in E)(P(x) \text{ ET } Q(x))$ a le même sens que $(\exists x \in E, P(x)) \text{ ET } (\exists x \in E, Q(x))$

Exemple : $E = \mathbb{N}$ $(\exists x \in E)(x \text{ est pair ET } x \text{ est impair})$ : F $(\exists x \in E, x \text{ est pair}) \text{ ET } (\exists x \in E, x \text{ est impair})$ : V Cependant : $(\exists x \in E)(P(x) \text{ ET } Q(x)) \neq (\exists x \in E, P(x)) \text{ ET } (\exists x \in E, Q(x))$

4. $(\exists x \in E)(P(x) \text{ OU } Q(x))$ a le même sens que $(\exists x \in E, P(x)) \text{ OU } (\exists x \in E, Q(x))$

L’ensemble constitué par les parties de $E$ est appelé ensemble des parties de $E$.

Dans l’exemple précédent : $\{\varnothing, \{a\}, \{b\}, \{c\}, \{a, b\}, \{a, c\}, \{b, c\}, \{a, b, c\}\}$ est l’ensemble noté $\mathcal{P}(E)$. $\forall x : X \in \mathcal{P}(E) \Leftrightarrow X \subset E$

Exemple : éléments de $\mathcal{P}(\mathcal{P}(\varnothing))$

Car le seul sous-ensemble de $\varnothing$ est $\varnothing$.

Opérations dans $M(E)$ :¶

Soit $E$ un ensemble et $A, B$ deux sous-ensembles de $E$.

• L’intersection de $A$ et $B$ est le sous-ensemble noté $A \cap B$, formé des éléments appartenant à la fois à $A$ et $B$.

• La réunion de $A$ et $B$ est le sous-ensemble noté $A \cup B$, formé des éléments appartenant à l’un ou l’autre des sous-ensembles.

• Le complémentaire de $A$ dans $E$ est le sous-ensemble noté $C_E A$, formé des éléments n’appartenant pas à $A$.

L’intersection de $A$ et $B$ est notée $A \cap B$.

• La réunion de $A$ et $B$ est notée $A \cup B$.

• Le complémentaire de $A$ dans $E$ est noté $C_E A$.

On note $A$ quand il n’y a pas d’égalité.

Exemple :

• $C_E \varnothing = E$

• $C_E E = \varnothing$

• $\forall x \in \mathcal{P}(E) : x \cup \varnothing = x$

• $x \cap \varnothing = \varnothing$

• $x \cup x = \varnothing$

• $x \cap x = x$

Propriétés : Soit $A, B, C$ des sous-ensembles d’un ensemble $E$ :

1. $A \cap B = B \cap A$

2. $(A \cap B) \cap C = A \cap (B \cap C)$

3. Si $A \subset B$, alors $A \cap B = A$

4. $A \cup B = B \cup A$

5. $(A \cup B) \cup C = A \cup (B \cup C)$

6. Si $A \subset B$, alors $A \cup B = B$

7. $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$

8. $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$

Lois de De Morgan :¶

9. $C_E (A \cap B) = C_E A \cup C_E B$

10. $C_E (A \cup B) = C_E A \cap C_E B$

Produit cartésien :¶

Soient $A, B$ deux ensembles. Le produit cartésien $A \times B$ (« A croix B ») est l’ensemble noté :

Exemple : $A = \{-1, 0, 1\}$, $B = \{2, 3\}$

$A \times B = \{(-1, 2), (-1, 3), (0, 2), (0, 3), (1, 2), (1, 3)\}$

$B \times A = \{(2, -1), (2, 0), (2, 1), (3, -1), (3, 0), (3, -4)$

En général, $A \times B \neq B \times A$.

Définition :¶

Soit $A_1, \ldots, A_n$ des ensembles non vides. $A_1 \times A_2 \times \ldots \times A_n = \left\{ (x_1, \ldots, x_n) \mid \forall i \in [1, n], x_i \in A_i \right\}$

$(x_1, \ldots, x_n)$ est appelé $n$-uplet.

Si $A_1 = A_2 = \ldots = A_n = A$, alors $\underbrace{A \times A \times \ldots \times A}_{n \text{ facteurs}}$ est noté $A^n$. Les éléments de $A^n$ sont appelés $n$-listes.

Exemple :¶

Ex13 : Soit $(n, p) \in \mathbb{N}^2$. Montrer que si $np$ est pair, alors $n^2 - p^2$ est multiple de 8.

Ex19 : Pour tout $n \in \mathbb{N}$, $1 + \frac{1}{2} + \frac{1}{3!} + \cdots + \frac{1}{n!} < e < 1 + \frac{1}{2!} + \cdots + \frac{1}{n!} + \frac{1}{n!!}$