From 5a08a4e1e055a0a702a54cfa867d7fdebf2c1ad7 Mon Sep 17 00:00:00 2001 From: Anhgelus Morhtuuzh Date: Fri, 19 Sep 2025 12:16:41 +0200 Subject: Cours du 15 au 19 septembre --- .../td/25-09-19.tex" | 167 +++++++++++++++++++++ 1 file changed, 167 insertions(+) create mode 100755 "semestre 3/math\303\251matiques discr\303\250tes/td/25-09-19.tex" (limited to 'semestre 3/mathématiques discrètes/td/25-09-19.tex') diff --git "a/semestre 3/math\303\251matiques discr\303\250tes/td/25-09-19.tex" "b/semestre 3/math\303\251matiques discr\303\250tes/td/25-09-19.tex" new file mode 100755 index 0000000..d256e24 --- /dev/null +++ "b/semestre 3/math\303\251matiques discr\303\250tes/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} -- cgit v1.2.3