1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
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}
|
