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
|
\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 6}
\begin{enumerate}
\item Supposons que $R$ soit réflexive.
On a que pour tout $x$ dans $R$, $(x,x)\in R$, ce qui est la définition de l'identité.
Supposons que $\mathrm{Id}_E\subseteq R$.
On a que pour tout $x$ dans $R$, $(x,x)\in R$ car $(x,x)\in\mathrm{Id}_E$.
\item \begin{align*}
\text{$R$ symétrique} \iff& \forall (x,y)\in E^2, (x,y)\in R \implies (y,x)\in R \\
\iff& R = \{(x,y) \in R | (y,x)\in R \} \\
\iff& R = R^{-1}
\end{align*}
\item À faire par équivalence classiquement.
\end{enumerate}
\section*{Exercice 8}
Si $R$ est relation d'équivalence sur $E$, alors la classe d'équivalence de $a\in R$ est l'ensemble~:
$$ \{(a,x)\in R\} $$
\begin{enumerate}
\item $R$ est réflexive, donc $a\in [a]$ car $(a,a)\in R$
\item Si $[a] = [b]$, alors pour tout $x$ dans $A$, on a $(a,x)\in R$ et $(b,x)\in R$, donc $(a,b)\in R$ par
symétrie et transitivité.
Pareil dans l'autre sens.
\item Supposons que $[a]\cap[b]\neq\varnothing$.
Alors, $\exists x\in [a]\cap[b]$ tel que $(a,x)\in R$ et $(b,x)\in R$.
Par symétrie et transitivité, on a $(b,x)\in R \iff (x,b)\in R \iff (a,b)\in R$.
Absurde car si $(a,b)\in R$, on a que $[a] = [b]$, ce qui est faux par hypothèse.
\item $\{[a]|a\in A\}$ est une partition de $A$ car
\begin{itemize}
\item tous les éléments de $[a]$ pour tout $a\in A$ sont dans $A$ par définition;
\item toutes les classes d'équivalence sont disjointes (3);
\item tous les éléments de $A$ sont présents dans cet ensemble car $a\in [a]$ (1).
\end{itemize}
\end{enumerate}
\textbf{Ceci est un résultat important~!}
\section*{Exercice 9}
L'application $\{(a,b), (b,b)\}$ dans $\{a,b\}$ n'est ni injective, ni surjective.
\begin{enumerate}
\item $f_1$ est injective, mais pas surjective, car il n'existe pas d'inverse sur $\mathbb{N}$.
$f_2$ est bijective, car il existe un inverse sur $\mathbb{Q}$.
\item $f$ est surjective, car $f(0) = 0$, $f(1) = 1$, $f(2) = 2$ et $f(3) = 0$.
\item $f$ est surjective, car $\forall x\in\mathbb{N}, f(x, 0) = x$ et $f(1,0) = f(0,1)$.
\item $f$ est bijective, car~:
\begin{itemize}
\item si $f(n)$ est pair, alors son antécédent est $n+1$
\item si $f(n)$ est impair, alors son antécédent est $n-1$
\item si $f(n_1) = f(n_2)$, alors $n_1 + 1 = n_2 + 1$ ou $n_1 - 1 = n_2 - 1$, i.e. $n_1=n_2$
\end{itemize}
\item $f$ n'est pas surjective, car les mots ne finissant par par $b$ ne sont jamais atteint.
$f$ est injective, car $f(u_1) = f(u_2) \implies u_1.b = u_2.b\implies u_1 = u_2$.
\end{enumerate}
Il existe $2^3 = 9$ applications différentes de $\{a,b,c\}$ vers $\{1,2\}$ (pour chaque élément de $\{a,b,c\}$, on
possède deux choix), dont aucune injective, $3\times 2 = 6$ surjectives (on choisit quel élément est le premier et
quel élément est le deuxième, le troisième est libre) et aucune bijective (car aucune n'est injective).
\section*{Exercice 19}
Soit $n\in\mathbb{N}$.
Si $n$ est pair, alors $n+1$ est impair.
Donc, $$ \exists !p\in\mathbb{N},\quad n+1=2p+1 $$
On pose $x=0$ et $y=p$, alors $$ n = 2^0 (2p+1) - 1 = 2^x(2y+1) $$
Par conséquent, les nombres pairs s'écrivent comme~:
$$ g(0,p) $$
Si $n$ est impair, il existe un unique $p$ dans $\mathbb{N}$ tel que $n = 2p+1$.
Donc, $$ n+1 = 2p+2 = 2(p+1) $$
Or, un nombre pair s'écrit d'une manière unique avec $(q,r)\in\mathbb{N}^2$ avec $q$ non nul comme~:
$$ 2^q(2r+1) $$
On pose $x=q$ et $p=r$, alors $$ n = 2^q(2r+1) - 1 = 2^x(2y+1) - 1 $$
Par conséquent, les nombres pairs s'écrivent comme~:
$$ g(q,r) $$
\end{document}
endsnippet
|
