Proposition & Fonction propositionnelle
Proposition : Énoncé mathématique ayant un sens, dont on peut dire sans ambiguïté qu'il est vrai ou faux.
Principe du tiers exclu : une proposition est soit vraie, soit fausse.
Principe de non-contradiction : une proposition ne peut pas être à la fois vraie et fausse.
Fonction propositionnelle (prédicat) : Énoncé contenant une ou plusieurs variables, qui se transforme en proposition suivant la valeur attribuée à ces variables.
Notation : Les propositions sont généralement notées par des symboles tels que $P, Q, R, \ldots$
Vrai : $(T)$ ou $1$ ; Faux : $(F)$ ou $0$.
Quantificateurs
Quantificateur universel $\forall$ : « Pour tout »
$\forall x \in E,\; P(x)$ est vraie ssi tous les éléments de $E$ vérifient $P(x)$.
Se lit : "Pour tout $x$ appartenant à $E$, $P(x)$ est vraie."
Quantificateur existentiel $\exists$ : « Il existe »
$\exists x \in E,\; P(x)$ est vraie ssi au moins un élément de $E$ vérifie $P(x)$.
$\exists!$ : existence et unicité. Se lit : "Il existe un unique".
Négation des quantificateurs :
$\overline{\bigl(\forall x \in E,\; P(x)\bigr)} \;\Longleftrightarrow\; \exists x \in E,\; \overline{P(x)}$
$\overline{\bigl(\exists x \in E,\; P(x)\bigr)} \;\Longleftrightarrow\; \forall x \in E,\; \overline{P(x)}$
Remarque fondamentale : L'ordre des quantificateurs de nature différente est fondamental. On ne peut pas permuter deux quantificateurs de nature différente.
Exemple : $(\forall x \in \mathbb{R}, \exists y \in \mathbb{R}, x+y=0) \neq (\exists y \in \mathbb{R}, \forall x \in \mathbb{R}, x+y=0)$.
Variable muette : Une variable quantifiée peut être remplacée par n'importe quelle autre variable (sauf celles déjà utilisées).
Connecteurs logiques
Conjonction ($\wedge$) : « et »
$P \wedge Q$ est vraie ssi $P$ et $Q$ sont toutes les deux vraies.
Fausse dans tous les autres cas.
Disjonction ($\vee$) : « ou » (inclusif)
$P \vee Q$ est vraie ssi au moins l'une des deux est vraie.
Fausse seulement si les deux sont fausses.
Implication ($\Rightarrow$)
$P \Rightarrow Q \;\Longleftrightarrow\; \overline{P} \vee Q$
Fausse uniquement si $P$ est vraie et $Q$ est fausse.
Se lit : "Si $P$ alors $Q$" ou "$P$ implique $Q$".
Équivalence ($\Leftrightarrow$)
$P \Leftrightarrow Q \;\Longleftrightarrow\; (P \Rightarrow Q) \wedge (Q \Rightarrow P)$
Vraie ssi $P$ et $Q$ ont la même valeur de vérité.
Se lit : "$P$ si et seulement si $Q$".
Table de vérité :
| $P$ | $Q$ | $P \wedge Q$ | $P \vee Q$ | $P \Rightarrow Q$ | $P \Leftrightarrow Q$ |
|---|
| V | V | V | V | V | V |
| V | F | F | V | F | F |
| F | V | F | V | V | F |
| F | F | F | F | V | V |
Principales lois logiques
Idempotence : $P \wedge P \Leftrightarrow P$ ; $P \vee P \Leftrightarrow P$
Commutativité : $P \wedge Q \Leftrightarrow Q \wedge P$ ; $P \vee Q \Leftrightarrow Q \vee P$
Associativité : $P \wedge (Q \wedge R) \Leftrightarrow (P \wedge Q) \wedge R$
Distributivité : $P \wedge (Q \vee R) \Leftrightarrow (P \wedge Q) \vee (P \wedge R)$
$P \vee (Q \wedge R) \Leftrightarrow (P \vee Q) \wedge (P \vee R)$
De Morgan : $\overline{P \wedge Q} \Leftrightarrow \overline{P} \vee \overline{Q}$
$\overline{P \vee Q} \Leftrightarrow \overline{P} \wedge \overline{Q}$
Contraposition : $(P \Rightarrow Q) \Leftrightarrow (\overline{Q} \Rightarrow \overline{P})$
Complément : $P \vee \overline{P} \Leftrightarrow \mathcal{V}$ (toujours vraie)
$P \wedge \overline{P} \Leftrightarrow \mathcal{F}$ (toujours fausse)
Double négation : $\overline{\overline{P}} \Leftrightarrow P$
Équivalence : $(P \Leftrightarrow Q) \Leftrightarrow (P \Rightarrow Q) \wedge (Q \Rightarrow P)$
Condition nécessaire et suffisante :
Si $P \Rightarrow Q$, alors $P$ est une condition suffisante pour $Q$, et $Q$ est une condition nécessaire pour $P$.
Si $P \Leftrightarrow Q$, alors $P$ est une condition nécessaire et suffisante pour $Q$.
Méthodes de raisonnement
Déduction
Si $P$ est vraie et $P \Rightarrow Q$ est vraie, alors $Q$ est vraie.
$(P \wedge (P \Rightarrow Q)) \Rightarrow Q$
Contraposée
Pour montrer $P \Rightarrow Q$, montrer $\overline{Q} \Rightarrow \overline{P}$.
Utile quand la contraposée est plus facile à démontrer.
Absurde
Pour montrer $P$, supposer $\overline{P}$ et aboutir à une contradiction.
$(\overline{P} \Rightarrow \mathcal{F}) \Rightarrow P$
Disjonction des cas
Pour montrer $R$, montrer $P \Rightarrow R$ et $\overline{P} \Rightarrow R$.
$(P \vee \overline{P})$ est toujours vraie.
Équivalences successives
$P \Leftrightarrow P_1 \Leftrightarrow P_2 \Leftrightarrow \cdots \Leftrightarrow Q$
Récurrence
Initialisation $P(n_0)$ + Hérédité $P(n) \Rightarrow P(n+1)$.
Valable pour $n \in \mathbb{N}, n \geq n_0$.
Contre-exemple : Pour montrer que $\forall x \in E,\; P(x)$ est fausse, il suffit d'exhiber un $x \in E$ tel que $\overline{P(x)}$.
La négation de $\forall x \in E, P(x)$ est $\exists x \in E, \overline{P(x)}$.
Définition d'un ensemble
Ensemble : Collection d'objets nommés éléments.
Si $x$ est un élément de l'ensemble $E$, on note $x \in E$ ; sinon $x \notin E$.
Ensemble vide : Ensemble ne contenant aucun élément, noté $\emptyset$.
Extension : On dresse la liste de tous les éléments.
Ex: $\{0,1,2,3,4,5\}$
Compréhension : On énonce la propriété caractéristique.
Ex: $\{n \in \mathbb{N} \mid 0 \leq n \leq 5\}$
Remarques : L'ordre des éléments n'a pas d'importance. La répétition d'éléments ne modifie pas l'ensemble.
Ex: $\{a,b,c\} = \{c,a,b\}$ et $\{1,2,2\} = \{1,2\}$.
Inclusion, Égalité & Ensemble des parties
Inclusion : $A \subset B \;\Longleftrightarrow\; \forall x,\; (x \in A \Rightarrow x \in B)$
On dit que $A$ est inclus dans $B$, ou que $A$ est une partie de $B$.
Égalité : $A = B \;\Longleftrightarrow\; (A \subset B) \wedge (B \subset A)$
Autrement dit : $\forall x,\; (x \in A \Leftrightarrow x \in B)$.
Partie (sous-ensemble) : Tout ensemble $A$ inclus dans $E$.
Ensemble des parties : $\mathcal{P}(E) = \{ A \mid A \subset E \}$
$A \in \mathcal{P}(E) \;\Longleftrightarrow\; A \subset E$.
Si $E$ a $n$ éléments, alors $\mathcal{P}(E)$ a $2^n$ éléments.
Propriétés :
- $\emptyset \subset E$ (l'ensemble vide est inclus dans tout ensemble)
- $A \subset A$ (réflexivité de l'inclusion)
- $(A \subset B) \wedge (B \subset C) \Rightarrow A \subset C$ (transitivité)
- $\emptyset \neq \{\emptyset\}$ et $\mathcal{P}(\emptyset) = \{\emptyset\}$
- $x \in E \;\Longleftrightarrow\; \{x\} \subset E$
Opérations sur les ensembles
Intersection ($\cap$)
$x \in A \cap B \;\Longleftrightarrow\; (x \in A) \wedge (x \in B)$
Réunion ($\cup$)
$x \in A \cup B \;\Longleftrightarrow\; (x \in A) \vee (x \in B)$
Complémentaire ($\overline{A}$)
$x \in \overline{A} \;\Longleftrightarrow\; (x \in E) \wedge (x \notin A)$
Noté aussi $C_E^A$ ou $E \setminus A$.
Différence ($A \setminus B$)
$x \in A \setminus B \;\Longleftrightarrow\; (x \in A) \wedge (x \notin B)$
Noté aussi $A - B$.
Différence symétrique ($\Delta$)
$A \Delta B = (A \setminus B) \cup (B \setminus A) = (A \cup B) \setminus (A \cap B)$
Propriétés fondamentales
Identité : $A \cup \emptyset = A$ ; $A \cap E = A$
Domination : $A \cup E = E$ ; $A \cap \emptyset = \emptyset$
Idempotence : $A \cup A = A$ ; $A \cap A = A$
Commutativité : $A \cup B = B \cup A$ ; $A \cap B = B \cap A$
Associativité : $(A \cup B) \cup C = A \cup (B \cup C)$
$(A \cap B) \cap C = A \cap (B \cap C)$
Distributivité : $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$
$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
Lois de Morgan :
$\overline{A \cup B} = \overline{A} \cap \overline{B}$
$\overline{A \cap B} = \overline{A} \cup \overline{B}$
Autres propriétés :
- $A \setminus B = A \cap \overline{B}$
- $A = (A \setminus B) \cup (A \cap B)$
- $A \subset B \;\Longleftrightarrow\; A \setminus B = \emptyset$
- $A \subset B \;\Longleftrightarrow\; \overline{B} \subset \overline{A}$
- $A \subset B \;\Longrightarrow\; (A \cup B = B) \wedge (A \cap B = A)$
- $A \Delta A = \emptyset$, $A \Delta \emptyset = A$, $A \Delta E = \overline{A}$
Produit cartésien
Définition : $E \times F = \{ (x,y) \mid (x \in E) \wedge (y \in F) \}$
$(x,y) \in E \times F \;\Longleftrightarrow\; (x \in E) \wedge (y \in F)$
Propriétés :
- $(x,y) = (x',y') \;\Longleftrightarrow\; (x = x') \wedge (y = y')$
- $E \times F = \emptyset \;\Longleftrightarrow\; (E = \emptyset) \vee (F = \emptyset)$
- En général $E \times F \neq F \times E$
- $(A \cup B) \times C = (A \times C) \cup (B \times C)$
- $(A \cap B) \times C = (A \times C) \cap (B \times C)$
- $(A \setminus B) \times C = (A \times C) \setminus (B \times C)$
Définition & Égalité
Application : Correspondance qui associe à tout élément $x$ de $E$ un unique élément de $F$, noté $f(x)$.
$f : E \to F \quad;\quad x \mapsto f(x)$
$E$ est l'ensemble de départ, $F$ l'ensemble d'arrivée.
$x$ est un antécédent de $y = f(x)$.
Le graphe de $f$ : $\Gamma_f = \{(x,f(x)) \in E \times F \mid x \in E\}$.
Égalité : $f = g \;\Longleftrightarrow\; (E = G) \wedge (F = H) \wedge \bigl(\forall x \in E,\; f(x) = g(x)\bigr)$
Identité : $Id_E : E \to E \quad;\quad Id_E(x) = x$
Restriction : $f|_{E_1}$ est la restriction de $f$ à $E_1 \subset E$.
$\forall x \in E_1, f|_{E_1}(x) = f(x)$.
Prolongement : $f$ est un prolongement de $f_1$ à $E$ si $f|_{E_1} = f_1$.
Notation : $\mathcal{A}(E,F)$ désigne l'ensemble des applications de $E$ vers $F$.
$f \in \mathcal{A}(E,F) \;\Longleftrightarrow\; \forall x \in E, \exists! y \in F, y = f(x)$.
Image directe & Image réciproque
Image directe :
$f(A) = \{ f(x) \mid x \in A \}$
$y \in f(A) \;\Longleftrightarrow\; \exists x \in A, y = f(x)$.
Image réciproque :
$f^{-1}(B) = \{ x \in E \mid f(x) \in B \}$
$x \in f^{-1}(B) \;\Longleftrightarrow\; f(x) \in B$.
Propriétés :
- $A \subset f^{-1}(f(A))$ (égalité si $f$ injective)
- $f(f^{-1}(B)) \subset B$ (égalité si $f$ surjective)
- $A \subset B \Rightarrow f(A) \subset f(B)$
- $C \subset D \Rightarrow f^{-1}(C) \subset f^{-1}(D)$
- $f(A \cup B) = f(A) \cup f(B)$
- $f^{-1}(C \cup D) = f^{-1}(C) \cup f^{-1}(D)$
- $f(A \cap B) \subset f(A) \cap f(B)$ (égalité si $f$ injective)
- $f^{-1}(C \cap D) = f^{-1}(C) \cap f^{-1}(D)$
Injection — Surjection — Bijection
Injection : $\forall (x,x') \in E^2,\; f(x) = f(x') \Rightarrow x = x'$
Tout élément de $F$ admet au plus un antécédent.
$f$ est injective $\Longleftrightarrow$ pour tout $y \in F$, $|f^{-1}(\{y\})| \leq 1$.
Surjection : $\forall y \in F,\; \exists x \in E,\; f(x) = y$
$f(E) = F$. Tout élément de $F$ admet au moins un antécédent.
$f$ est surjective $\Longleftrightarrow$ pour tout $y \in F$, $f^{-1}(\{y\}) \neq \emptyset$.
Bijection : $\forall y \in F,\; \exists! x \in E,\; f(x) = y$
$f$ est à la fois injective et surjective.
Pour tout $y \in F$, $f^{-1}(\{y\})$ a exactement un élément.
Théorème : Une application $f: E \to F$ est bijective ssi il existe $g: F \to E$ telle que
$f \circ g = Id_F$ et $g \circ f = Id_E$.
Bijection réciproque
Définition : Si $f$ est une bijection de $E$ sur $F$, l'application $f^{-1} : F \to E$ définie par
$f(x) = y \;\Longleftrightarrow\; x = f^{-1}(y)$
est appelée bijection réciproque de $f$.
Propriétés :
- $f^{-1} \circ f = Id_E$
- $f \circ f^{-1} = Id_F$
- $(f^{-1})^{-1} = f$
- La réciproque d'une bijection est une bijection.
Composition des applications
Définition : Pour $f : E \to F$ et $g : F \to G$,
$(g \circ f)(x) = g(f(x))$
$g \circ f : E \to G$
Propriétés :
- $(f \circ g) \circ h = f \circ (g \circ h)$ (associativité)
- En général, $f \circ g \neq g \circ f$ (non-commutativité)
- Si $f$ et $g$ sont injectives, $g \circ f$ est injective
- Si $f$ et $g$ sont surjectives, $g \circ f$ est surjective
- Si $f$ et $g$ sont bijectives, $g \circ f$ est bijective
- $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$
Remarque : $f \circ f$ se note $f^2$. De manière générale, $f^n = \underbrace{f \circ f \circ \cdots \circ f}_{n \text{ fois}}$.