1 files changed, 167 insertions, 0 deletions
diff --git a/semestre 3/mathématiques discrètes/td/25-09-19.tex b/semestre 3/mathématiques discrètes/td/25-09-19.tex
new file mode 100755
index 0000000..d256e24
--- /dev/null
+++ b/semestre 3/mathématiques discrètes/td/25-09-19.tex
@@ -0,0 +1,167 @@
+\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}