4 files changed, 515 insertions, 0 deletions
diff --git a/semestre 3/mathématiques discrètes/td/.gitignore b/semestre 3/mathématiques discrètes/td/.gitignore
new file mode 100644
index 0000000..c5d2f98
--- /dev/null
+++ b/semestre 3/mathématiques discrètes/td/.gitignore
@@ -0,0 +1,316 @@
+# Created by https://www.toptal.com/developers/gitignore/api/latex
+# Edit at https://www.toptal.com/developers/gitignore?templates=latex
+
+### LaTeX ###
+## Core latex/pdflatex auxiliary files:
+*.aux
+*.lof
+*.log
+*.lot
+*.fls
+*.out
+*.toc
+*.fmt
+*.fot
+*.cb
+*.cb2
+.*.lb
+
+## Intermediate documents:
+*.dvi
+*.xdv
+*-converted-to.*
+# these rules might exclude image files for figures etc.
+# *.ps
+# *.eps
+# *.pdf
+
+## Generated if empty string is given at "Please type another file name for output:"
+.pdf
+
+## Bibliography auxiliary files (bibtex/biblatex/biber):
+*.bbl
+*.bcf
+*.blg
+*-blx.aux
+*-blx.bib
+*.run.xml
+
+## Build tool auxiliary files:
+*.fdb_latexmk
+*.synctex
+*.synctex(busy)
+*.synctex.gz
+*.synctex.gz(busy)
+*.pdfsync
+
+## Build tool directories for auxiliary files
+# latexrun
+latex.out/
+
+## Auxiliary and intermediate files from other packages:
+# algorithms
+*.alg
+*.loa
+
+# achemso
+acs-*.bib
+
+# amsthm
+*.thm
+
+# beamer
+*.nav
+*.pre
+*.snm
+*.vrb
+
+# changes
+*.soc
+
+# comment
+*.cut
+
+# cprotect
+*.cpt
+
+# elsarticle (documentclass of Elsevier journals)
+*.spl
+
+# endnotes
+*.ent
+
+# fixme
+*.lox
+
+# feynmf/feynmp
+*.mf
+*.mp
+*.t[1-9]
+*.t[1-9][0-9]
+*.tfm
+
+#(r)(e)ledmac/(r)(e)ledpar
+*.end
+*.?end
+*.[1-9]
+*.[1-9][0-9]
+*.[1-9][0-9][0-9]
+*.[1-9]R
+*.[1-9][0-9]R
+*.[1-9][0-9][0-9]R
+*.eledsec[1-9]
+*.eledsec[1-9]R
+*.eledsec[1-9][0-9]
+*.eledsec[1-9][0-9]R
+*.eledsec[1-9][0-9][0-9]
+*.eledsec[1-9][0-9][0-9]R
+
+# glossaries
+*.acn
+*.acr
+*.glg
+*.glo
+*.gls
+*.glsdefs
+*.lzo
+*.lzs
+*.slg
+*.slo
+*.sls
+
+# uncomment this for glossaries-extra (will ignore makeindex's style files!)
+# *.ist
+
+# gnuplot
+*.gnuplot
+*.table
+
+# gnuplottex
+*-gnuplottex-*
+
+# gregoriotex
+*.gaux
+*.glog
+*.gtex
+
+# htlatex
+*.4ct
+*.4tc
+*.idv
+*.lg
+*.trc
+*.xref
+
+# hyperref
+*.brf
+
+# knitr
+*-concordance.tex
+# TODO Uncomment the next line if you use knitr and want to ignore its generated tikz files
+# *.tikz
+*-tikzDictionary
+
+# listings
+*.lol
+
+# luatexja-ruby
+*.ltjruby
+
+# makeidx
+*.idx
+*.ilg
+*.ind
+
+# minitoc
+*.maf
+*.mlf
+*.mlt
+*.mtc[0-9]*
+*.slf[0-9]*
+*.slt[0-9]*
+*.stc[0-9]*
+
+# minted
+_minted*
+*.pyg
+
+# morewrites
+*.mw
+
+# newpax
+*.newpax
+
+# nomencl
+*.nlg
+*.nlo
+*.nls
+
+# pax
+*.pax
+
+# pdfpcnotes
+*.pdfpc
+
+# sagetex
+*.sagetex.sage
+*.sagetex.py
+*.sagetex.scmd
+
+# scrwfile
+*.wrt
+
+# svg
+svg-inkscape/
+
+# sympy
+*.sout
+*.sympy
+sympy-plots-for-*.tex/
+
+# pdfcomment
+*.upa
+*.upb
+
+# pythontex
+*.pytxcode
+pythontex-files-*/
+
+# tcolorbox
+*.listing
+
+# thmtools
+*.loe
+
+# TikZ & PGF
+*.dpth
+*.md5
+*.auxlock
+
+# titletoc
+*.ptc
+
+# todonotes
+*.tdo
+
+# vhistory
+*.hst
+*.ver
+
+# easy-todo
+*.lod
+
+# xcolor
+*.xcp
+
+# xmpincl
+*.xmpi
+
+# xindy
+*.xdy
+
+# xypic precompiled matrices and outlines
+*.xyc
+*.xyd
+
+# endfloat
+*.ttt
+*.fff
+
+# Latexian
+TSWLatexianTemp*
+
+## Editors:
+# WinEdt
+*.bak
+*.sav
+
+# Texpad
+.texpadtmp
+
+# LyX
+*.lyx~
+
+# Kile
+*.backup
+
+# gummi
+.*.swp
+
+# KBibTeX
+*~[0-9]*
+
+# TeXnicCenter
+*.tps
+
+# auto folder when using emacs and auctex
+./auto/*
+*.el
+
+# expex forward references with \gathertags
+*-tags.tex
+
+# standalone packages
+*.sta
+
+# Makeindex log files
+*.lpz
+
+# xwatermark package
+*.xwm
+
+# REVTeX puts footnotes in the bibliography by default, unless the nofootinbib
+# option is specified. Footnotes are the stored in a file with suffix Notes.bib.
+# Uncomment the next line to have this generated file ignored.
+#*Notes.bib
+
+### LaTeX Patch ###
+# LIPIcs / OASIcs
+*.vtc
+
+# glossaries
+*.glstex
+
+# End of https://www.toptal.com/developers/gitignore/api/latex
+
+TD*.pdf
diff --git a/semestre 3/mathématiques discrètes/td/25-09-19.pdf b/semestre 3/mathématiques discrètes/td/25-09-19.pdf
new file mode 100644
index 0000000..0e744c5
--- /dev/null
+++ b/semestre 3/mathématiques discrètes/td/25-09-19.pdf
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}
diff --git a/semestre 3/mathématiques discrètes/td/template.tex b/semestre 3/mathématiques discrètes/td/template.tex
new file mode 100755
index 0000000..23ee891
--- /dev/null
+++ b/semestre 3/mathématiques discrètes/td/template.tex
@@ -0,0 +1,32 @@
+\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{Titre}
+\author{William Hergès\thanks{CPES Science Henri-IV / PSL}}
+
+\begin{document}
+	\maketitle
+	$0	
+\end{document}
+endsnippet