\documentclass[a4paper]{article}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{textcomp}
\usepackage[french]{babel}
\usepackage{amsmath, amssymb}
\usepackage{amsthm}
\usepackage[svgnames]{xcolor}
\usepackage{thmtools}
\usepackage{lipsum}
\usepackage{framed}
\usepackage{parskip}

\renewcommand{\familydefault}{\sfdefault}

\newenvironment{AQT}{{\fontfamily{qbk}\selectfont AQT}}

\usepackage{titlesec}
\usepackage{LobsterTwo}
\titleformat{\section}{\newpage\LobsterTwo \huge\bfseries}{\thesection.}{1em}{}
\titleformat{\subsection}{\vspace{2em}\LobsterTwo \Large\bfseries}{\thesubsection.}{1em}{}
\titleformat{\subsubsection}{\vspace{1em}\LobsterTwo \large\bfseries}{\thesubsubsection.}{1em}{}

\title{TD Maths discrètes}
\author{William Hergès\thanks{Sorbonne Université}}

\begin{document}
	\maketitle
    \section*{Exercice 1}
    \begin{enumerate}
        \item $S_1\times S_1 = \{(0,0),(0,1),(0,2),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2)\}$
        \item Pour $S=S_1$, on a~:
            $$ \mathcal{P}(S) = \{\varnothing, \{0\}, \{1\}, \{2\}, \{0,1\},\{0,2\},\{1,2\},S\} $$
            Pour $S=S_2$, on a~:
            $$ \mathcal{P}(S) = \{\varnothing, \{1\}, \{\{1,4\}\}, S\} $$
            Pour $S=S_3$, on a~:
            $$ \mathcal{P}(S) = \{\varnothing, \{\varnothing\},\{1\}, S\} $$
        \item Les partitions possibles de $\{1,2,3\}$ sont~:
            $$ \{\{1\},\{2\},\{3\}\} $$
            $$ \{\{1\},\{2, 3\}\} $$
            $$ \{\{2\},\{1, 3\}\} $$
            $$ \{\{1\},\{1, 2\}\} $$
            $$ \{\{1, 2, 3\}\} $$
    \end{enumerate}
    \section*{Exercice 2}
    \subsection*{Question 1}
    Montrons que $x\in A\cap\overline{A \cap B}$ est dans $A\cap\bar B$.

    Soit $x$ dans $A\cap\overline{A\cap B}$, alors $x$ est dans $A$ et $\overline{A\cap B}$. 
    Comme $x$ n'est pas dans $\bar A$ (il est dans $A$), il est forcément dans $\bar B$, ainsi on obtient que $x$
    est bien dans $A$ et $\bar B$.
    Alors, $x\in A\cap\bar B$.

    Montrons que $x\in A\cap\bar B$ est dans $A\cap\overline{A\cap B}$.

    Soit $x$ dans $A\cap\bar B$, alors $x$ est dans $A$ et $\bar B$.
    D'après la loi de De Morgan, on a~:
    $$ A\cap\overline{A\cap B} = A\cap(\bar A\cup \bar B) $$
    Or, comme $x$ est dans $A$, il ne peut pas être dans $\bar A$ par définition. 
    Donc $x$ est forcément dans $\bar B$.
    Ainsi, $x\in A\cap\bar B$.

    Par conséquent, $$A\cap\bar B = A\cap\overline{A\cap B}$$
    \subsection*{Question 4}
    $$ A\cup B\subseteq A\cup C\quad\land\quad A\cap B\subseteq A\cap C $$
    Soit $x$ dans $B$.

    Si $x$ n'est pas dans $A$, il est dans $C$ (car $A\cup B\subseteq A\cup C$).

    Si $x$ est dans $A$, il est dans $A\cap C$, donc il est aussi dans $C$.

    Alors, $x$ est toujours dans $C$.
    Ainsi $B\subseteq C$.

    Pour avoir $B=C$, on a besoin d'avoir $A\cup C\subseteq A\cup B$ en plus.
    \subsection*{Question 6}
    Si $A=\{0, 1, 3\}$ et $B=\{1, 2\}$, alors
    $$ \{3,2\}\in\mathcal{P}(A\cup B) $$
    Pourtant, $$\{3,2\}\not\in \mathcal{P}(A)\cup\mathcal{P}(B)$$
    Donc, $\mathcal{P}(A\cup B)=\mathcal{P}(A)\cup\mathcal{P}(B)$ est faux.

    \begin{align*}
        & E\subseteq \mathcal{P}(A\cup B) \\
        \iff & E\subseteq A\cup B \\
        \iff & E\subseteq A\cup B \\
        \iff & E\subseteq A \land E\subseteq B \\
        \iff & E\subseteq \mathcal{P}(A) \land E\subseteq \mathcal{P}(B) \\
        \iff & E\subseteq \mathcal{P}(A)\cup\mathcal{P}(B)
    \end{align*}
    \section*{Exercice 3}
    $$ S = \{(a,b,c)\in D^3|c=a+b\} $$
    \section*{Exercice 4}
    \subsection*{Question 1}
    $R$ n'est pas réflexive, car $R(2,2)$ est faux.

    $R$ est symétrique, car on a $R(1,1)$, $R(2,3)$ et $R(3,2)$.
    Elle ne peut donc pas être antisymétrique.

    Elle n'est pas transitive, car on a $R(2,3) \land R(3,2)$ qui n'implique pas $R(2,2)$.
    \subsection*{Question 4}
    On a~:
    $$ (x_1,x_2) \preceq (y_1,y_2) $$
    si, et seulement si, $x_1\leqslant y_1$ et $x_2\leqslant y_2$.

    Une relation d'ordre est une relation réflexive, antisymétrique et transitive.

    $$ (x,y)\preceq (x,y) \iff x\leqslant x \land y \leqslant y  $$
    est vraie, donc $\preceq$ est réflexive.

    \begin{align*}
        & (x_1,x_2) \preceq (y_1,y_2) \land (y_1,y_2) \preceq (x_1,x_2)\\
        \iff & (x_1 \leqslant y_1 \land x_2\leqslant y_2) \land (y_2 \leqslant x_2 \land y_1\leqslant x_1)
    \end{align*}
    Alors, on a que $x_1=y_1$ et que $x_2=y_2$, i.e. $(x_1,x_2)=(y_1,y_2)$ dans ce cas.
    $\preceq$ est donc antisymétrique.

    \begin{align*}
        & (x_1,x_2) \preceq (y_1,y_2) \land (y_1,y_2) \preceq (z_1,z_2)\\
        \iff & (x_1 \leqslant y_1 \land x_2\leqslant y_2) \land (y_2 \leqslant z_2 \land y_1\leqslant z_1) \\
        \iff & (x_1 \leqslant z_1 \land x_2\leqslant z_2) \\
        \iff & (x_1,x_2)\preceq (z_1,z_2) 
    \end{align*}
    Alors, elle est transitive.
    Ainsi, il s'agit d'une relation d'ordre.

    Elle n'est pas totale car $(0,1)$ et $(1,0)$ ne sont pas comparables.
    \subsection*{Question 5}
    Une relation est dite d'ordre si elle est réflexive, symétrique et transitive.

    Soit $\varepsilon$ dans $\mathbb{R}$.
    On pose $x = 0$ et $z = 2\varepsilon$.

    On a que $R(x,\varepsilon)$ est vraie (trivial).
    On a que $R(\varepsilon, 2\varepsilon$ est vraie (trivial).
    On a que $R(x,2\varepsilon)$ est faux, car~:
    $$ |0-2\varepsilon| > \varepsilon $$

    Ainsi, $R$ n'est pas une relation d'ordre.
    \section*{Exercice 5}
    \subsection*{Question 1}
    $$ R = \{
        (1, 3), (1, 5),
        (2, 3), (2, 5),
        (3, 5),
        (4, 5)
    \} $$
    $$ R^{-1} = \{
        (3, 1), (5, 1),
        (3, 2), (5, 2),
        (5, 3),
        (5, 4)
    \}$$
    $$ R^{-1}.R = \{(3,3), (3, 5), (5,5), (5,3)\} $$
    $$ R.R^{-1} = \{(1,1), (1,2), (1,3), (1,4), (1,5), (2,2), (2,3), (2,4), (3,3), (3,4), (4,4)\} $$
    \subsection*{Question 2}
    On a~:
    $$ R.S = \{(x,z)\in X\times Z | \exists y\in Y, R(x,y)\land S(y,z)\} $$
    Donc~:
    $$ (R.S)^{-1} = \{(z,x)\in Z\times X | \exists y\in Y, R(x,y)\land S(y,z)\} $$
    Or~:
    \begin{align*}
        S^{-1}.R^{-1} &= \{(z,x)\in Z\times X | \exists y\in Y, R(x,y)\land S(y,z)\} \\
        &= (R.S)^{-1} \\
    \end{align*}
    (Ici il y a juste une étape cachée qui transforme $R^{-1}(y,x)$ en $R(x,y)$, mais elle est triviale. Idem pour $S$)
\end{document}