Cours du 15 au 19 septembre

5 files changed, 635 insertions, 0 deletions

diff --git a/semestre 3/mathématiques discrètes/1- Ensembles, relations, fonctions.md b/semestre 3/mathématiques discrètes/1- Ensembles, relations, fonctions.md
index b0066aa..8d7ceec 100644
--- a/semestre 3/mathématiques discrètes/1- Ensembles, relations, fonctions.md
+++ b/semestre 3/mathématiques discrètes/1- Ensembles, relations, fonctions.md
@@ -125,3 +125,123 @@ Une partition de $E$ est une famille $(A_i)_{i\in I}$ de parties de $E$ telle qu
 - $E=\bigcup_{i\in I} A_i$
 
 > [!warning] Une partition de $E$ n'est pas unique dans le cas générale !
+## Relation
+**Définition**
+Relation binaire $R$ d'un ensemble $E$ vers $F$ est un sous-ensemble de $E\times F$, i.e.
+$$ R\subseteq E\times F $$
+On peut la noter $(x,y)\in R$, $x R y$, $R(x,y)$.
+Lorsque $E=F$, on dit que $R$ est une relation binaire sur $E$.
+
+Exemple :
+- $\mathrm{Id}_E$ est la relation identité de $E$ est une relation binaire sur $E$ telle que $\{(e,e)|e\in E\}$
+- $\mathrm{Id}_{\mathbb{N}} = \{(n,n)|n\in\mathbb{N}\}$
+- $\leqslant$ sur $\mathbb{N}$ est aussi une relation binaire : $\{(n_1,n_2)\in\mathbb{N}^2|n_1\leqslant n_2\}$
+- $<$ sur $\mathbb{N}$ est aussi une relation binaire (elle est incluse dans $\leqslant$)
+
+> [!NOTE] Opérations sur les relations
+> Comme une relation est un ensemble, on peut appliquer les opérations ensemblistes dessus 🎉
+
+**Définition**
+Relation $n$-aire est un sous-ensemble du produit cartésien $E_1\times\ldots\times E_n$
+
+**Définition**
+Une relation unaire est un sous-ensemble d'un ensemble $E$.
+
+Définir par compréhension permet d'énoncer la propriété caractéristique de l'ensemble
+|> on peut avoir une même relation pour des propriétés caractéristiques différentes
+Définir par extension permet de lister les éléments
+
+**Définition**
+La relation inverse $R^{-1}$ d'une relation $R\subseteq E\times F$ est la relation de $F$ vers $E$ contenant tous les couples $(x,y)$ tels que $(y,x)\in R$, i.e.
+$$ R^{-1} = \{(x,y)\in F\times E|(y,x)\in R\} $$
+
+**Définition**
+Un produit de relation est quand on applique plusieurs relations à la suite.
+
+Le produit de $R_1\subseteq E\times F$ et de $R_2\subseteq F\times G$ est définie par :
+$$ R_1R_2 = \left\{(x,y)\in E\times G\quad|\quad\exists z, (x,z)\in R_1\quad\land\quad(z,y)\in R_2\right\} $$ -> revoir le cours pour cette expression, ça me semble chelou
+On la note $R_1\circ R_2$ ou $R_1\cdot R_2$.
+```mermaid
+flowchart LR
+	A -- R1⋅R2 ---C
+	A-- R1 ---B
+	B-- R2 ---C
+```
+
+Par exemple, on peut définir $<$ comme $S\cdot\leqslant$ où $S$ est la relation successeur (i.e. $S=\{(x,y)|x+1=y\}$)
+
+> [!warning] Commutativité
+> Le produit de relation n'est pas commutatif
+
+> [!warning] $R\cdot R^{-1}\neq\mathrm{Id}_E$
+> De même dans l'autre sens
+
+**Propriétés**
+$\varnothing$ est un élément est absorbant des relations : $R\cdot\varnothing = \varnothing\cdot R = R$
+Le produit est associatif : $R_1\cdot(R_2\cdot R_3) = (R_1\cdot R_2)\cdot R_3$
+$\mathrm{Id}$ est l'élément neutre : $R\cdot\mathrm{Id}_F = \mathrm{Id}_ER=R$ (si $R$ est dans $E\times F$)
+|> ⚠ faire bien attention à la modification de l'identité en fonction qu'on soit à droite ou à gauche
+
+**Notations**
+Si $R$ est une relation sur $E$, on note :
+$$ R^n = \underbrace{R\ldots R}_n = \left\{\begin{matrix}
+	\mathrm{Id}_E&\text{si}&n=0\\
+	R\cdot R^{n-1}&\text{sinon}
+\end{matrix}\right. $$
+
+***Revoir les diapos 23 à 29***
+
+**Définition**
+Une relation est dite d'équivalence si, et seulement si, elle est :
+- réflexive
+- symétrique
+- transitive
+
+Une relation est dite d'ordre si, et seulement si, elle est :
+- réflexive
+- anti-symétrique
+- transitive
+
+Par exemple :
+- $\equiv$ (congruence) est une relation d'équivalence
+- $\leqslant$ est une relation d'ordre
+- $<$ n'est pas une relation d'ordre car elle n'est pas anti-symétrique !
+
+**Définition**
+Soit $R$ une relation d'équivalence sur $E$.
+La classe d'équivalence d'un élément $e\in E$ pour $R$ est noté $[e]_R$ et :
+$$ [e]_R = \{e'\in E|(e,e')\in R\} $$
+Remarque : $e\in[e]_R$ car $R$ est réflexive
+
+**Définition**
+On note $E_{/R}$  l'ensemble des quotients de $E$ par $R$
+***J'AI PAS EU LE TEMPS DE NOTER (diapo 31)***
+## Fonctions
+**Définition**
+Une relation de $E$ vers $F$ est dite déterministe (ou fonctionnelle) si, et seulement si, tout élément de $E$ est en relation avec au plus un élément de $F$, i.e.
+$$ \forall e\in E,\quad\forall(e_1,e_2)\in F^2,\quad(e,e_1)\in R\quad\land\quad(e,e_2)\in R \implies e_1=e_2 $$
+
+Exemples :
+- $S$ est fonctionnelle
+- $S^{-1}$ l'est aussi
+- $\leqslant$ ne l'est pas par contre
+
+**Proposition**
+Une relation déterministe est une fonction $f$.
+
+Si $f$ n'est pas définie pour tout l'ensemble de départ, on dit qu'elle est partielle.
+
+Preuves :
+- relation déterministe ne donne qu'une unique image
+
+**Définition**
+Une relation $R$ de $E$ vers $F$ est dite totale à gauche si, et seulement si, chaque élément de $E$ est en relation avec au moins un élément de $F$ :
+$$ \forall e_1\in E,\quad\exists e_2\in F,\quad (e_1,e_2)\in R $$
+
+**Définition**
+Une application est une relation déterministe et totale à gauche, on la note :
+$$ f : E\to F $$
+i.e. tout élément de $E$ possède une (unique) image.
+On dit parfois qu'elle est une fonction totale.
+
+***Voir diapo 36 à 45 car j'ai pas le temps de noter***
\ No newline at end of file
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