Killian REINE

MPI TD 01 - Relation binaire

Jan 29, 202613 min read

TD1
RELATION BINAIRE
1 Notions préliminaires
Théorie des ensembles
1 Définitions et généralités
  1. Donner la définition rigoureuse d'un ensemble.
  2. Quelles sont les manières de définir un ensemble ?
  3. Rappeler les opérations sur les ensembles et les définir rigoureusement.
  4. Si A est une partie de B que peut-on dire de A par rapport à B hormis que c'est une partie...
  5. Qu'appelle-t-on ensembles disjoints ?
  6. Donner la définition d'un n-uplet.
  7. Discutez des différences entre ensembles et n-uplets.
2 Inclusion v/s appartenance

Soit \( A = \{0, 1, 7, 5, 6, 9\} \) et \( B = \{1, 8, 4, 2\} \).
Déterminer si les expressions mathématiques suivantes sont vraies ou fausses.

  1. \( \{1, 2\} \in A \)
  2. \( 0 \in A \)
  3. \( A \subset B \)
  4. \( \{1\} \in A \)
  5. \( \{1\} \subset A \) et \( B \subset \{1\} \)
  6. \( 14 \subset A \)
  7. \( \{14\} \in B \)
  8. \( A \subset A \cup B \)
3 Démontrer une propriété

Soient E un ensemble et \( A, B \subseteq E \). On considère la relation \( R_e \) suivante :
$$ A R_e B \Leftrightarrow A \subset B $$

  1. Montrer que \( R_e \) est une relation d'ordre.
4 Propriétés ∩, ∪, ∁
  1. Déterminer les propriétés des opérations d'union, d'intersection et de complémentaire.
  2. Comparez avec vos résultats avec vos voisins...
5 Égalité des ensembles
  1. Soit l'ensemble \( C = \{(x, y) \in \mathbb{R}^2 | y = x^2\} \) et l'ensemble \( D = \{(t, t^2) | t \in \mathbb{R}\} \).
    Démontrer que \( C = D \).
  2. Soit l'ensemble \( E = \{(x, y) \in \mathbb{R}^2 | y^2 = 4x\} \) et l'ensemble \( F = \{(t^2, 2t) | t \in \mathbb{R}\} \).
    Démontrer que \( E = F \).
Applications
6 Bien définie ou non
  1. Rappeler les définitions d'une fonction et d'une Application.
  2. Déterminer si les applications suivantes sont bien définies. Justifier le cas échéant.
    1. $$ \begin{align*} \mathcal{E}_1 : \mathbb{R} &\to \mathbb{R} \\ x &\mapsto \sqrt{x} \end{align*} $$
    2. $$ \begin{align*} \mathcal{E}_2 : \mathbb{Q} &\to \mathbb{Z} \\ \frac{p}{q}& \mapsto p \end{align*} $$
    3. $$ \begin{align*} \mathcal{E}_3 : \mathbb{R} &\to \{-1, 0, 1\} \\ x &\mapsto \begin{cases} -1 & \text{si } x < 0, \\ 0 & \text{si } x = 0, \\ 1 & \text{si } x > 0. \end{cases} \end{align*} $$
    4. $$ \begin{align*}\\ \mathcal{E}_4 : \{x \in \mathbb{Z} | x \bmod 2 = 0\} &\to \mathbb{Z} \\ n &\mapsto \frac{n}{2} \\ \end{align*} $$
7 Sérieux, de la bijectivité...

On considère l'objet mathématique suivant :

\[f : \mathbb{R} \setminus \{1\} \to \mathbb{R} \] \[x \mapsto \frac{x + 1}{x - 1}\]
  1. f est-elle bijective ?
    Vous utiliserez un raisonnement approprié muni d'une rédaction pour répondre à la question posée.
2 Relations binaires
Graphes
8 Définitions et généralités

Les relations données par les graphes ci-dessous sont-elles réflexives, symétriques, antisymétriques, transitives ?
Sont-elles d'ordre ou d'équivalence ?

Propriété des relations
9 Propriétés de relations

Pour chacune des relations binaires R suivantes, déterminer si elles sont réflexives, symétriques ou transitives. De plus pour les relations qui définissent une relation d'équivalence, décrire leurs classes d'équivalences et leur ensemble quotient.

  1. \( \forall a, b \in \mathbb{N}, \; aRb \Leftrightarrow |a - b| \leq 2 \)
  2. \( \forall a, b \in \mathbb{Q}^*, \; aRb \Leftrightarrow a \cdot b > 0 \)
  3. \( \forall a, b \in \mathbb{Q}^*, \; aRb \Leftrightarrow \frac{a}{b} \in \mathbb{N}^* \)
  4. \( \forall a, b \in \mathbb{Q}, \; aRb \Leftrightarrow (a - b) \in \mathbb{N} \)
  5. \( \forall a, b \in \mathbb{R}, \; aRb \Leftrightarrow a - b = a^2 - b^2 \)
10 Relations avancées
  1. Soit R la relation binaire définie sur \( \mathbb{Z} \) par : $$ \forall (a, b) \in \mathbb{Z}^2, \; aRb \Leftrightarrow a - b \text{ est pair} $$ Montrer que R est une relation d'équivalence et déterminer ses différentes classes d'équivalences.
  2. Soit \( n \in \mathbb{N}^* \). Soit \( R_n \) une relation binaire définie sur \( \mathbb{Z} \) par : $$ \forall (a, b) \in \mathbb{Z}^2, \; aRb \Leftrightarrow n \text{ divise } a - b $$ Montrer que \( R_n \) est une relation d'équivalence et déterminer ses différentes classes d'équivalences.
11 Utiliser la circularité

Soit R une relation binaire sur un ensemble E. La relation R est dite circulaire sur E si :
$$ \forall a, b, c \in E, \; (aRb \land bRc) \Rightarrow cRa $$

  1. Montrer que si R est réflexive et circulaire sur E, alors la relation R est une relation d'équivalence sur E.
Matrices booléennes et algorithmes
12 Matrice booléenne et graphes

On considère l'ensemble \( A = \{1, 2, 3\} \) et la relation \( R \subseteq A \times A \) définie par :
$$ R = \{(1, 1), (1, 2), (2, 3)\}$$

  1. Représentation de la relation
    1. Représenter R par son graphe orienté.
    2. Construire la matrice booléenne \( M_R \) de la relation.
  2. Déterminer si R vérifie la réflexivité, symétrie, antisymétrique et la transitivité à partir du graphe, puis de la matrice.
  3. Modifier la relation
    1. Modifier la relation pour la rendre réflexive.
    2. Ajouter les couples manquant pour rendre la relation symétrique.
    3. Faire de même pour rendre R transitive.
13 Plus difficile !
  1. Soient A et B deux ensembles finis et R une relation définie dans \( A \times B \).
    $$ A = \{a_i, a_{i+1}, \ldots, a_n\} \quad B = \{b_j, b_{j+1}, \ldots, b_m\} $$ On rappelle la définition de \( M_R \) la matrice booléenne d'ordre \( (n, m) \) associée à R.
    \[ (M_R)_{ij} = \begin{cases} 1 & \text{si } a_i R b_j \\ 0 & \text{sinon} \end{cases} \]
    1. Écrire des algorithmes qui ont, en entrée une matrice booléenne associée à une relation binaire sur un ensemble fini et qui précisent si cette relation est réflexive, symétrique ou transitive.

      Soient deux relations R et S de \( A \times B \), on rappelle que, \( \forall x, y \in A \times B \) :
      $$ x(R + S)y \Leftrightarrow x(R \cup S)y $$ $$ x(RS)y \Leftrightarrow x(R \cap S)y $$ On définit les deux opérations suivantes sur les matrices booléennes P et Q :
      $$ P \lor Q : (P \lor Q)_{ij} = P_{ij} \lor Q_{ij} $$ $$P \land Q : (P \land Q)_{ij} = P_{ij} \land Q_{ij} $$
    2. Montrer que \( M_{R+S} = M_R \lor M_S \)
    3. Montrer que \( M_{RS} = M_R \land M_S \)
    4. Donner les algorithmes qui calculent \( P \land Q \) et \( P \lor Q \) avec P et Q comme paramètres.
  2. On définit maintenant la composition \( R \circ S \) de deux relations \( R \subset A \times B \) et \( S \subset B \times C \) telle que :
    $$\forall (x, y) \in A \times C, \; x(R \circ S)y \Leftrightarrow \exists z \in B \; | \; xRz \land zSy$$ On définit aussi le produit booléen \( A \otimes B \) de deux matrices booléennes A d'ordre \( (n, p) \) et B d'ordre \( (p, m) \) par :
    $$(A \otimes B)_{ij} = \bigvee_{k=1}^p a_{ik} \land b_{kj} $$
    1. Vérifier que \( R \circ (S \circ T) = (R \circ S) \circ T \)
    2. Montrer que \( M_{R \circ S} = M_R \otimes M_S \)
    3. Soit \( A = \{a, b, c, d\} \) et \( R \subset A^2 \) une relation sur A définie par \( R = \{(a, b), (b, c), (c, d)\} \).
      1. Écrire la matrice booléenne associée à R et construire son graphe.
      2. Construire le graphe de \( R^2 \), donner sa matrice associée et vérifier que la formule du b) permet de la retrouver.
    4. Écrire un algorithme permettant d'effectuer le produit booléen de deux matrices booléennes.
Les clôtures
14 Introduction aux clôtures

On considère l'ensemble \( A = \{a, b, c\} \) et la relation R définie sur A par :
$$R = \{(a, b), (b, c)\} $$

Définition : Lorsqu'une relation R n'a pas une propriété réflexive, symétrique ou transitive, on peut lui ajouter le minimum de couples pour qu'elle le devienne.
La nouvelle relation s'appelle alors clôture de R pour la propriété ajoutée.
  1. Construire le graphe de la relation R.
  2. La relation R est-elle réflexive ? Symétrique ? Transitive ? Justifiez vos réponses.
  3. Construire la clôture réflexive de R.
  4. Construire la clôture symétrique de R.
  5. Construire la clôture transitive de R.
  6. Vérifier que la clôture transitive trouvée est bien une relation qui contient R, et qu'elle est la plus petite au sens de la transitivité.
15 Presque la fin...

Soit R une relation sur un ensemble fini A. On appelle clôture propriété de R, la plus petite relation propriété sur A contenant R.

  1. Construire les clôtures réflexives, symétriques et transitives de la relation de l'exercice 13.2.c.
  2. Montrer que la clôture réflexive de R est \( R + I_A \), où \( I_A \) est définie par :
    $$ \forall x, y \in A, \; xI_A y \Leftrightarrow x = y $$
  3. Montrer que la clôture symétrique de R est \( R + R^{-1} \) où \( R^{-1} \) est définie par :
    $$ \forall x, y \in A, \; xR^{-1}y \Leftrightarrow yRx $$
  4. Montrer que la clôture transitive de R est :
    $$ R^+ = \sum_{k=1}^{|A|} R^k $$ où \( R^k = \underbrace{R \circ R \circ R \circ \ldots \circ R}_{k \text{ fois}} \)
    où \( |A| \) représente le cardinal de A.
  5. Écrire les algorithmes de calcul des clôtures réflexives, symétriques et transitives.
Les relations d'ordre, les diagrammes de Hasse
16 Relations d'ordre
Soit \( A = \{1, 2, 3, 4, 5\} \) un ensemble fini et \(R, S\) deux relations sur \(A\) décrites par les matrices booléennes suivantes : $$ M_R=\begin{pmatrix}1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1\end{pmatrix} \hspace{1cm} M_S=\begin{pmatrix}1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 & 1\end{pmatrix} $$
  1. Vérifier que les relations \(R\) et \(S\) sont des relations d'ordre.
  2. Représentez les relations par un graphe puis donner leur diagramme de Hasse associé.
17 Relations divise \( | \)
  1. Soit \( A = \{3, 6, 12, 24, 72\} \). Représenter le diagramme de Hasse de \((A, |)\) où \( | \) est la relation divise.
  2. Même question avec \( A = \{ 1, 2, 3, 4, 5, 6, 10, 12, 15, 30, 60\} \)
  3. Soit \(A=\{2, 3, 4, 12\}\). Représenter le diagramme du produit des ensembles ordonnés \((A, |)\) et \((A, \leq)\).
18 Tri topologique
Définition :Soit \((A, \leq)\) un ensemble partiellement ordonné. On appelle tri topologique de \(A\), toute relation d'ordre total \((A, \leq')\) telle que $$ \forall (a,b) \in A \times A, \quad (a \leq b) \Longrightarrow (a \leq' b) $$
Représenter les diagrammes de Hasse de tous les tris topologiques que l'on peut construire à partir de la relation d'ordre définie par le diagramme de Hasse suivant :
19 Éléments maximaux, minimaux, maximal, minimal, majorant, minorant, supremum, infimum
  1. On considère l'ensemble \(A=\{1, 2, 3, 4, 5, 6, 7, 8, 9\}\) muni d'une relation d'ordre définie par le diagramme de Hasse suivant :
    Pour chaque partie \(B\) de \(A\) ci-après, donner : Les éléments minimaux, maximaux, maximum, minimum. Les majorants et les minorants, ainsi que le supremum et l'infimum si ils existent.
    1. \(B=\{2, 3, 4, 5, 6\}\)
    2. \(B=\{6,7\}\)
    3. \(B=\{2,4,6,9\}\)
    4. \(B=A\)
    5. \(B=\{4,5,7\}\)
    6. \(B=\{1,2,5\}\)
  2. Même question pour \(A=\mathbb{N}\) muni de la relation d'ordre \(|\).
    1. \(B=\{1,2,3\}\)
    2. \(B=\{0,2,4,8\}\)
    3. \(B=\{4,6,8\}\)
    4. \(B=\{7\}\)
    5. \(B=3\mathbb{N}\)
20 Et si on s'amusait à démontrer des propriétés ?
Soit \((A, \leq)\) un ensemble ordonné, \(B \subset A\) et \(a,b\in A\). On note \(major(B)\) l'ensemble des majorants de \(B\).
Montrer que :
  1. \(a \in major(B) \quad \text{et} \quad a \leq b \Longrightarrow b \in major(B)\)
  2. \(a \in B\cap major(B) \Longrightarrow a=max(B)\)
  3. \(a = max(B)\Longrightarrow a=sup(B)\)
  4. Si, de plus, \(A\) est fini, montrer que tout élément de \(A\) est inférieur ou égal à un élément maximal de \(A\).

Graph View

Backlinks