Théorie > Fondements > Logique

Lien avec la théorie des ensembles

Les ensembles peuvent être définis à l'aide d'une proposition. Par exemple,
$$A = \{n \in \mathbb{Z} \mid (n \geq -1) \land (n < 4)\} = \{-1, 0, 1, 2, 3\}.$$ Cette similitude rend la logique et la théorie des ensembles assez proches.

Similitudes

La relation d'inclusion s'apparente par exemple à une implication. En effet, $A \subseteq B$ est équivalent à $x \in A \Rightarrow x \in B$.

Aussi, les opérations $\lor$ et $\cup$ n'ont pas que leurs symboles qui se ressemblent puisqu'on a
$$A \cup B = \{x \mid (x \in A) \lor (x \in B)\}$$ et similairement pour $\land$ et $\cap$,
$$A \cap B = \{x \mid (x \in A) \land (x \in B)\}.$$ Le complémentaire est quant à lui lié à la négation logique $\lnot$ :
$$A^c = \{x \in U \mid \lnot (x \in A)\}$$ où $U$ est l'univers.

L'ensemble vide $\emptyset$ s'apparente enfin à $0$ et l'univers $U$ à $1$.

Toutes les relations que nous avons vues dans le cadre de la logique peuvent alors être réécrites dans le cadre de la théorie des ensembles.

Commutativité et associativité, neutre et absorbant

Les opérations $\cup$ et $\cap$ sont associatives et commutatives.
Le neutre de $\cup$ est $\emptyset$ et celui de $\cap$ est $U$ :
$$\begin{align*}
\emptyset \cup A & = A, & U \cap A & = A.
\end{align*}$$ L'absorbant de $\cup$ est $U$ et celui de $\cap$ est $\emptyset$ :
$$\begin{align*}
U \cup A & = U, & \emptyset \cap A & = \emptyset.
\end{align*}$$

Lois de De Morgan

Les lois de De Morgan pour les ensembles sont
$$\begin{align*}
(A \cup B)^c & = A^c \cap B^c,\\
(A \cap B)^c & = A^c \cup B^c.
\end{align*}$$

Distributivité

Comme pour $\lor$ et $\land$, on a la distributivité
$$\begin{align*}
(A \cup B) \cap C & = (A \cap C) \cup (B \cap C),\\
(A \cap B) \cup C & = (A \cup C) \cap (B \cup C).
\end{align*}$$

Contraposition

La contraposition devient finalement
$$(A \subseteq B) \Leftrightarrow (B^c \subseteq A^c).$$