Notions mathématiques

Définition intuitive d’un ensemble

Un ensemble peut être vu comme :

• collection d’objets appelés éléments, sémantiquement définie mais non-structurée

• logique booléenne d'appartenance (\(\in\)) à un ensemble (\(E\)).

  • l’élément, noté \(x\), est (\(x \in E\)) ou n’est pas (\(x \notin E\)) dans l’ensemble

• unicité : un élément n’est pas 2 fois dans le même ensemble

Ensemble vide

Représentation mathématique de l’ensemble vide :

• \(E = \{ \} = \emptyset\)

Création de l’ensemble vide en SQL :

On remarquera dans l’exécution du script ci-dessus les commandes SQL:

• CREATE TABLE : de création de TABLE qui représentera un ensemble d’éléments (de données)
• SELECT : de recherche d’informations (d’éléments) dans une table (un ensemble)
• count() : de calcul sur les résultats d’une recherche d’informations

On remarquera également que la requête SQL :

• SELECT x FROM E;

ne retourne aucun élément \(x\), l’exécution de cette requête sous SQLite ne produit aucun affichage entre les commentaires « ensemble vide » et « nombre d’éléments dans l’ensemble vide ».

Ensemble des chiffres arabes

Représentation mathématique de l’ensemble des chiffres arabes :

• \(E = \{ 0,1,2,3,4,5,6,7,8,9 \}\)

Création de l’ensemble des chiffres en SQL :

On remarquera dans l’exécution du script ci-dessus la commande SQL

• INSERT INTO ... VALUES ... : d’insertion d’élément dans un ensemble

A partir de ces commandes SQL nous pouvons créer des ensembles dont les éléments peuvent contenir plusieurs informations.

Nous invitons le lecteur à faire l’exercice ci-dessous qui a pour objectif de créer un ensemble de points de coordonnées (x,y) avant de continuer la lecture de ce chapitre.

CREATE TABLE points(x FLOAT,y FLOAT);
INSERT INTO points(x,y) VALUES (-50,-50);
INSERT INTO points(x,y) VALUES (50,-50);
INSERT INTO points(x,y) VALUES (50,50);
INSERT INTO points(x,y) VALUES (-50,50);

SELECT * from points;

Domaine d’un ensemble

On peut définir un domaine en extension (énumération des valeurs) :

• \(E= \{ 0,2,4,6,8 \}\) : ensemble des entiers naturels (\(\mathbb{N}\)) pairs inférieur à 10

Création de l’ensemble des chiffres pairs en SQL :

On peut définir, en calcul relationnel, un domaine en intension (compréhension), par une formule logique vérifiée par tous les éléments :

• \(E = \{ x \; \vert \; x \in \mathbb{N} \land x \equiv 0 \mod 2 \}\) : ensemble des entiers naturels (\(\mathbb{N}\)) pairs (congrus à 0 modulo 2)

ou de manière plus synthétique :

• \(E = \{ x \in \mathbb{N} \; \vert \; x \equiv 0 \mod 2 \}\) : ensemble des entiers naturels (\(\mathbb{N}\)) pairs

La première notation est cependant plus explicite sur la formulation en calcul relationnel, où l’on veut récupérer les éléments (\(x\)) qui vérifient la proposition logique :

• \(x \in \mathbb{N}\) : x appartient (« vrai ») ou n’appartient pas (« faux ») à l’ensemble des entiers
• \(\land\) : connecteur logique et (AND en SQL).
• \(x \equiv 0 \mod 2\) : x est (« vrai ») ou n’est pas (« faux ») un nombre pair (congru à 0 modulo 2)

Si l’élément \(x\) est un entier et \(x\) est un nombre pair alors il appartient au domaine (\(x \in E\)) des entiers pairs défini par cette formule logique.

Le lecteur intéressé trouvera quelques notions supplémentaires sur la définition mathématique de la congruence en déployant le block ci-dessous.

Fonction caractéristique

La fonction caractéristique (prédicat) d’un ensemble, notée \(P(x)\), définira en intension l’ensemble \(E\) :

• \(E = \{ x \; \vert \; P(x) \}\)

Exemple : définition de l’ensemble des entiers naturels impairs

• \(E = \{ x \mid x \in \mathbb{N} \land (x \equiv 1 \mod 2) \}\)

Fonction caractéristique \(P(x)\) :

• \(x \in \mathbb{N} \land (x \equiv 1 \mod 2)\)

Exemple : définition de l’ensemble des chiffres impairs

• \(E = \{ x \mid x \in \mathbb{N} \land (x \equiv 1 \mod 2) \land (x > 0 \land x <10) \}\)

Fonction caractéristique \(P(x)\) :

• \(x \in \mathbb{N} \land (x \equiv 1 \mod 2) \land (x > 0 \land x <10)\)

Fonction caractéristique en SQL:

En SQL, la fonction caractéristique est définie dans la clause WHERE par l’écriture d’une expression logique.

SELECT x FROM E WHERE x%2 = 0 AND x >=0 AND x < 10;

On peut également créer des vues (CREATE VIEW) sur une partie (un sous-ensemble) d’un ensemble.

Dans le code SQL ci-dessous, nous récupérons l’ensemble des chiffres pairs ou impairs en créant des vues (E_even, E_odd), représentant ces deux sous-ensembles de l’ensemble \(\mathbb{N}\) des entiers, à l’aide des fonctions caractéristiques qui définissent logiquement les chiffres pairs ou impairs.

CREATE VIEW E_even AS
SELECT x AS "even digits"
FROM E
WHERE x%2 = 0 AND x >= 0 AND x < 9 ;

CREATE VIEW E_odd AS
SELECT x AS "odd digits"
FROM E
WHERE x%2 = 1 AND x > 0 AND x <= 9 ;

On peut alors utiliser ces vues (sous-ensembles) dans une requête comme on utilise une table (ensemble).

SELECT * FROM E_odd;
SELECT * FROM E_even;

Créer une vue revient à définir un sous-ensemble d’un ensemble, ce sous-ensemble étant représenté par une requête SQL.

Une vue revient à « encapsuler » une requête SQL en la nommant (un peu comme on encapsule du code dans une fonction en programmation).

Attention, il ne faut cependant pas confondre une table avec une vue.

Si nous avions créé des tables (E_even, E_odd) nous aurions alors dû insérer les chiffres pairs et impairs dans ces tables.

Nous aurions alors obtenu trois ensembles distincts (E,E_even, E_odd). L’insertion d’un entier pair dans l’ensemble (E) n’aurait pas été répercuté dans le sous-ensemble E_even. Reciproquement l’insertion d’un entier pair dans l’ensemble (E_even) n’aurait pas non plus été répercuté dans l’ensemble E.

Par contre si E_even est défini comme une vue sur les éléments pairs de l’ensemble E, l’insertion d’un entier pair dans cet ensemble sera « visible » lors d’une requête sur la vue (qui constitue elle-même une requête sur l’ensemble E).

Cardinalité

La cardinalité d’un ensemble est le nombre d’éléments d’un ensemble, noté \(card(E)\).

En SQL on obtient la cardinalité d’un ensemble en appliquant la fonction de calcul \(count()\) sur l’ensemble généré par une requête.

Cardinalité d’un ensemble en SQL :

En utilisant les opérations ensemblistes d’union, d’intersection et de différence (\(\cup,\cap,\setminus\)), on pourra vérifier :

• \(card(E_1 \cup E_2) = card(E_1) + card(E_2) - card(E_1 \cap E_2)\)
• \(card(E_1 \setminus E_2) = card(E_1) - card(E_1 \cap E_2)\)

En SQL on pourra utiliser les opérations ensemblistes correspondantes (UNION,INTERSECT,EXCEPT) comme ilmlustré dans les exercices ci-dessous.

SELECT count(*) AS "card(E1 Union E2)"
FROM (SELECT *  FROM E1 UNION SELECT * FROM E2);

SELECT "" AS "=";

SELECT count(*) AS "card(E1)" FROM E1;

SELECT "" AS "+";

SELECT count(*) AS "card(E2)" FROM E2;

SELECT "" AS "-";

SELECT count(*) AS "card(E1 Intersect E2)"
FROM (SELECT * FROM E1 INTERSECT SELECT * FROM E2);

SELECT count(*) AS "card(E1 Minus E2)"
FROM (SELECT *  FROM E1 EXCEPT SELECT * FROM E2);

SELECT "" AS "=";

SELECT count(*) AS "card(E1)" FROM E1;

SELECT "" AS "-";

SELECT count(*) AS "card(E1 Intersect E2)"
FROM (SELECT * FROM E1 INTERSECT SELECT * FROM E2);

Egalité d’ensembles

Deux ensembles \(A,B\) sont égaux, ce qu’on note \(A = B\), si tout élément de l’un appartient à l’autre et inversement.

Autrement dit l’ensemble \(A\) est inclus (\(\subseteq\)) dans l’ensemble \(B\) et réciproquement.

• \(A = B \Leftrightarrow A \subseteq B \land B \subseteq A\)

Dire qu’un ensemble \(A\) dans un ensemble \(E\) revient à vérifier :

• \(A \setminus E = 0\)

Autrement dit, si la différence entre l’ensemble \(A\) et l’ensemble \(E\) est vide alors tous les éléments de l’ensemble \(A\) sont dans l’ensemble \(E\).

L’inclusion d’un ensemble dans un autre peut également être définie par les fonctions caractéristiques d’ensemble.

Si \(P_A, P_E\) sont les fonctions caractéristiques des ensembles \(A,E\), alors \(A \subseteq E\) si et seulement si :

• \(\forall a \in A, P_A(a) \Rightarrow P_E(a)\)

Si le prédicat est vérifié pour les éléments du sous-ensemble \(A\) alors il est vérifié pour le prédicat de l’ensemble \(E\).

Exemples :

• un chiffre pair est un chiffre mais l’inverse n’est pas nécessairement vrai.
• l’humain est un mammifère mais tous les mammifères ne sont pas des humains.
• …

Vérification, en SQL, de l’inclusion d’un ensemble dans un autre et de l’égalité de deux ensembles :

On peut définir l’égalité de deux ensembles (\(A = B\)) par la propriété suivante :

• \(A \cup B = A \cap B\)

ou

• \((A \cup B) \setminus (A \cap B)= \emptyset\)

CREATE VIEW B AS
SELECT * FROM A ORDER BY x DESC;

SELECT * FROM A;
SELECT * FROM B;

SELECT COUNT(*)
FROM
(
 SELECT x FROM A  UNION SELECT x FROM B
 EXCEPT
 SELECT x FROM A  INTERSECT SELECT x FROM B
)

Parties d’un ensemble

L’ensemble \(A\) est un sous-ensemble, une partie, d’un ensemble \(E\) s’il est inclus dans \(E\) :

• \(\forall x \in A, x\in E\)

Autrement dit tous les éléments de l’ensemble \(A\) sont des éléments de l’ensemble \(E\).

Notation :

• \(A \subseteq E\) : l’ensemble \(A\) est inclus ou égal à l’ensemble \(E\)
• \(\mathscr{P}(E)\) : ensemble des sous-ensembles (ensemble des parties)

SELECT * FROM E;

-- create view E1 (even digits) --
CREATE VIEW E1 AS
SELECT x FROM E WHERE x%2=0 AND x>=0 AND x<10;

SELECT x AS "even digits" FROM E1;

-- create view E2 (odd digits) --
CREATE VIEW E2 AS
SELECT x FROM E WHERE x>0 AND x<10 AND x NOT IN (SELECT x FROM E1);

SELECT x AS "odd digits"  FROM E2;

-- card(E1\E) = 0 => E1 inclus dans E  --
SELECT count(*) AS "card(E1\E)" FROM E1 EXCEPT SELECT x FROM E;
-- card(E\E1)  --
SELECT count(*) AS "card(E\E1)"  FROM E EXCEPT SELECT x FROM E1;
-- card(E2\E) = 0 => E2 inclus dans E ---
SELECT count(*) AS "card(E2\E)" FROM E2 EXCEPT SELECT x FROM E;
-- card(E\E2)  --
SELECT count(*) AS "card(E\E2)" FROM E EXCEPT SELECT x FROM E2;

 SELECT * FROM E;

  -- create view E1 : chiffres pairs  --
 CREATE VIEW E1 AS
 SELECT x FROM E WHERE x%2=0 AND x>=0 AND x<10;


 -- create view E2  : chiffres impairs --
 CREATE VIEW E2 AS
 SELECT x FROM E WHERE  x>0 AND x<10 AND x NOT IN (SELECT x FROM E1);

 SELECT x AS "even digits"  FROM E1;
 SELECT x AS "odd digits" FROM E2;

-- create view E_numbers  --
 CREATE VIEW E_numbers  AS
 SELECT x FROM E WHERE x NOT IN (SELECT x FROM  E1) AND  x NOT IN (SELECT x FROM E2);

 SELECT x AS "numbers"  FROM E_numbers;

 -- create view E_union = E_numbers + E1 + E2  --
 CREATE VIEW E_union AS
 SELECT x FROM  E_numbers
 UNION
 SELECT x FROM E1 UNION SELECT x FROM  E2;

 -- E - E_union = 0 --
 SELECT count(*) AS "E-E_union=0" FROM (SELECT x FROM E EXCEPT SELECT x FROM E_union);

L’exercice proposé ci-dessous propose un récapitulatif des notions abordées précédemment sur les ensembles, cardinalité, sous-ensemble et partitions.

• Question
• Solution

Cet exercice est extrait du site de Bertrand Liaudet dans son cours sur la « théorie des ensembles et bases de données ».

Enoncé : 200 élèves participent à une journée de sport. 3 sports sont au programme : le foot, la natation et la course à pieds. Chaque élève peut participer à 1, 2 ou 3 sports. Avec les informations ci-dessous, trouver le nombre d’élèves qui participent à un seul sport, à 2 sports et à trois sports :

• 10 élèves sont blessés et ne participent pas
• 18 participent au 3 sports
• 103 ne font que 2 sports
• 79 font du foot et de la natation
• 19 ne font que le la course
• 129 font de la natation dont 40 que de ça .

Indice :

Cet exercice pourra être résolu par une méthode de représentation d’ensembles sous forme de diagramme de Venn et de calcul de cardinalité d’ensembles.

Votre réponse :

Texte : inputlines1174.txt

A partir des données du problème on peut déjà identifier : - 10 élèves sont blessés et ne participent pas => card(...)=10 - 18 participent au 3 sports => card(... ​∩ ... ​∩ ...)=18 - ...

Zone de saisie de texte

Clavier	Action
F1	Afficher une aide technique
F2	Afficher une aide pédagogique
Ctrl-A	Tout sélectionner
Ctrl-C	Copier la sélection dans le presse-papier
Ctrl-V	Copier le presse-papier dans la sélection
Ctrl-X	Couper la sélection et la copier dans le presse-papier
Ctrl-Z	Annuler la modification
Maj-Ctrl-Z	Rétablir la modification

Menu	Action
	Ré-initialiser les sorties
	Faire apparaître le menu d'aide
	Valider la zone de saisie
	Initialiser la zone de saisie
	Charger le contenu d'un fichier dans la zone de saisie
	Sauvegarder le contenu de la zone de saisie dans un fichier
	Imprimer le contenu de la zone de saisie

Une solution possible :

Cet exercice pourra être résolu par une méthode de représentation d’ensembles sous forme de diagramme de Venn et de calcul de cardinalité d’ensembles.

Ces ensembles représentent l’ensemble des élèves (\(E_1\)) qui ne feront pas de sports et les ensembles d’élèves qui font un ou plusieurs sports :

• \(E= E_1 \cup Football \cup Natation \cup Course\)

où :

• \(card(E)=card(E_1)+card(Football)+card(Natation)+card(Course)=200\)

On défini alors un partitionnement de l’ensemble des élèves (\(E\)) en sous-ensembles :

• les élèves qui ne pourront participer à la journée de sport (\(E_1)\)
• les élèves qui participeront à un seul sport (\(E_2,E_3,E_4)\)
• les élèves qui participeront à deux sports (\(E_5,E_6,E_7)\)
• les élèves qui participeront aux trois sports(\(E_8)\)

représentés par le diagramme de Venn ci-dessous :

A partir des données du problème on peut déjà identifier :

• 10 élèves sont blessés et ne participent pas

  \(\Rightarrow card(E_1)=10\)

• 18 participent au 3 sports

  \(\Rightarrow card(E_8)=18\)

• 103 ne font que 2 sports

• 79 font du foot et de la natation

• 19 ne font que le la course

  \(\Rightarrow card(E_4)=19\)

• 129 font de la natation dont 40 que de ça .

  \(\Rightarrow card(E_3)=40\)

représentés par le diagramme de Venn ci-dessous :

79 font du foot et de la natation :

• \(card(E_5)+card(E_8)=79\)
• \(card(E_5)+18=79\)

\(\Rightarrow card(E_5)=61\)

129 font de la natation dont 40 que de ça :

• \(card(E_3)+card(E_5)+card(E_7)+card(E_8)=129\)
• \(40+61+card(E_7)+18=129\)

\(\Rightarrow card(E_7)=10\)

103 ne font que 2 sports

• \(card(E_5)+card(E_6)+card(E_7)=103\)
• \(61+card(E_6)+10=103\)

\(\Rightarrow card(E_6)=32\)

200 élèves en tout :

• \(card(E_1)+card(E_2)+card(E_3)+card(E_4)+card(E_5)+card(E_6)+card(E_7)+card(E_8)=200\)
• \(10+card(E_2)+40+19+61+32+10+18=200\)

\(\Rightarrow card(E_2)=10\)

On obtient donc la partition suivante de l’ensemble des élèves pour la journée de sport :

Notations

Dans la suite de ce cours nous adopterons une notation préfixée des opérations ensemblistes et autres :

• \(op(A,B)\)

plutôt que la notation infixée des opérations binaires :

• \(A \; op \; B\)

La notation préfixée sera en effet plus explicite pour représenter une opération ayant en entrée 2 ensembles pour générer en sortie un ensemble résultat :

• \(R=op(A,B)\)

Par exemple l’expression algébrique :

• \(R=(A \cup B) \setminus (A \cap B)\)

S’écrira :

• \(R=\setminus(\cup(A,B),\cap(A,B))\)

Et pourra se décomposer en :

• \(R_1=\cup(A,B)\)
• \(R_2=\cap(A,B)\)
• \(R=\setminus(R_1,R_2)\)

Par la suite on pourra représenter cette expression sous forme d’arbre de flux de données entre les opérateurs de l’algèbre relationnelle (\(\cup, \cap, \setminus ...\)).

Ces opérateurs, mis en œuvre dans les SGBD relationnels, serviront à éxécuter sur le serveur de bases de données les requêtes SQL.

Arbre de requêtes

L’expression algébrique suivante :

• \(R=\Pi_{(count(x))}(\setminus(\cup(A,B), \cap (A,B)))\)

utilisant les opérateurs de l’algèbre relationnelle :

• Projection (\(\Pi\)) : réduction du nombre d’informations sur les éléments de l’ensemble.
• Différence (\(\setminus\)) : opération ensembliste de différence entre deux ensembles.
• Intersection (\(\cap\)) : opération ensembliste d’intersection entre deux ensembles.

se représente sous forme d’arbre de flux de données. On pourra appliquer une fonction de calcul (count()) sur la racine de cet arbre (le résultat de la requête).

Si l’arbre de requêtes ci-dessous donne un résultat nul (count(x) = 0) alors les deux ensembles \(A,B\) sont égaux.

On notera la représentation graphique des opérateurs (noeuds de l’arbre) pour symboliser la projection (\(\Pi\)) et les opérations ensemblistes (\(\cup,\cap,\setminus\)).

On trouvera dans l’exercice ci-dessous un éditeur d’arbre de requêtes contenant une palette d’opérateurs de l’algèbre relationnelle permettant de construire vos arbres de requêtes.

• Question
• Solution

Créer l’arbre de requêtes qui permettra de vérifier que les deux ensembles A et B , représentés ci-dessous, sont égaux.

Votre réponse :

Arbre de requêtes : AB.json

Tables Opérateurs unaires Opérateurs binaires

Vue d'ensemble

{ "class": "go.GraphLinksModel", "copiesArrays": true, "copiesArrayObjects": true, "linkFromPortIdProperty": "fromPort", "linkToPortIdProperty": "toPort", "nodeDataArray": [ {"category":"query", "name":"R_1", "info":"QUERY", "key":-2, "loc":"-500 -200"}, {"category":"table", "name":"A", "info":"TABLE", "key":-1, "loc":"-500 -25"}, {"category":"table", "name":"B", "info":"TABLE", "key":-3, "loc":"-300 -25"}, {"category":"query", "name":"R_2", "info":"QUERY", "key":-4, "loc":"-300 -200"} ], "linkDataArray": [ {"from":-1, "to":-2, "fromPort":"", "toPort":"R", "points":[-500,-41.349999999999994,-500,-41.349999999999994,-500,-104.99999999999999,-500,-104.99999999999999,-500,-168.64999999999998,-500,-183.64999999999998]}, {"from":-3, "to":-4, "fromPort":"", "toPort":"R", "points":[-300,-41.349999999999994,-300,-41.349999999999994,-300,-104.99999999999999,-300,-104.99999999999999,-300,-168.64999999999998,-300,-183.64999999999998]} ]} CREATE TABLE A(x INTEGER); INSERT INTO A(x) VALUES (0); INSERT INTO A(x) VALUES (1); INSERT INTO A(x) VALUES (2); INSERT INTO A(x) VALUES (3); INSERT INTO A(x) VALUES (4); INSERT INTO A(x) VALUES (5); INSERT INTO A(x) VALUES (6); INSERT INTO A(x) VALUES (7); INSERT INTO A(x) VALUES (8); INSERT INTO A(x) VALUES (9); CREATE TABLE B(x INTEGER); INSERT INTO B(x) VALUES (9); INSERT INTO B(x) VALUES (8); INSERT INTO B(x) VALUES (7); INSERT INTO B(x) VALUES (6); INSERT INTO B(x) VALUES (5); INSERT INTO B(x) VALUES (4); INSERT INTO B(x) VALUES (3); INSERT INTO B(x) VALUES (2); INSERT INTO B(x) VALUES (1); INSERT INTO B(x) VALUES (0);

Une solution possible :

On vérifiera que le résultat final \(R\) des opérations ensemblistes suivantes est nul

• \(U=\cup(A,B)\)
• \(I=\cap(A,B)\)
• \(E=\setminus(U,I)\)
• \(R=\Pi_{(count(x))}(E)\)

Domaine

Le domaine de la relation \(R \subseteq \times(A,B)\) se définit par l’ensemble des éléments de l’ensemble de départ qui sont en relation avec des éléments de l’ensemble d’arrivée.

• \(dom(R) = \{x \in A \; \vert \; \exists y \in B \; , \; (x,y) \in R \}\)

Ecriture en SQL du domaine de la relation inférieur à du produit cartésien \(\times(A,B)\) :

SELECT A.x AS "domain" FROM A,B WHERE A.x < B.y;

SELECT DISTINCT A.x AS "domain" FROM A,B WHERE A.x < B.y;

Image

L’image de la relation \(R \subseteq \times(A,B)\) se définit par l’ensemble des éléments de l’ensemble d’arrivée qui sont en relation avec des éléments de l’ensemble de départ :

• \(image(R) = \{ y \in B \; \vert \; \exists x \in A \; , \; (x,y) \in R \}\)

Ecriture en SQL de l’image de la relation inférieur à du produit cartésien \(\times(A,B)\) :

SELECT B.y AS "image" FROM A,B WHERE A.x < B.y;
SELECT DISTINCT B.y AS "image" FROM A,B WHERE A.x < B.y;

Fonction

Une relation \(R \subseteq (A \times B)\) est fonctionnelle si :

• \(\forall (x,y,y') \in (A \times B \times B), (x,y) \in R \wedge (x,y') \in R \Rightarrow y = y'\)

Autrement dit, une relation est fonctionnelle (fonction) si :

• au plus un élément de l’ensemble d’arrivée est associé à un élément de l’ensemble départ.

Autrement dit, une relation entre deux ensembles (\(A,B\)) est une fonction, notée \(f\) si :

• \(\forall x \in A\) il existe au plus un \(y \in B\) tel que \(y=f(x)\)

Exemple : la relation définie par \(y = 1/x\) est une fonction de \(\mathbb{R}\) vers \(\mathbb{R}\)

Comme on le voit sur le graphe de la fonction, les éléments de l’ensemble de départ (\(\mathbb{R}\)) sont au plus en relation avec un élément de l’ensemble d’arrivée (\(\mathbb{R}\)).

L’élément \(x=0\) est le seul élément de \(\mathbb{R}\) à ne pas avoir une (et une seule) image dans l’ensemble d’arrivée.

Application

Une relation fonctionnelle \(R \subseteq (A \times B)\) est applicative si :

• \(dom(R) = A\)

ou encore :

• \(\forall x \in A \; , \; \exists ! y \in B : (x,y) \in R\)

Autrement dit une relation fonctionnelle est applicative (est une application) si :

• Pour tout \(x \in A\) il existe un et un seul \(y \in B\) tel que \(y=f(x)\) (\(f\) : application)
• A chaque élément de l’ensemble de départ est associé un unique élément dans l’ensemble d’arrivée.

Ou encore :

• une application est une fonction définie partout

Exemple : la relation fonctionnelle définie par \(y = 1/x\) est une application de \(\mathbb{R}^*\) vers \(\mathbb{R}\)

Comme on le voit sur le graphe de la fonction, tous les éléments de l’ensemble de départ (\(\mathbb{R}^*\)) sont en relation avec un et un seul élément de l’ensemble d’arrivée (\(\mathbb{R}\)).

Injection

Une application \(f : A \rightarrow B\) est injective (injection) si et seulement si :

• \(\forall (x,y) \in (A \times B) \; : \; f(x)=f(y) \Rightarrow x=y\)

ou sa contraposée :

• \(\forall (x,y) \in (A \times B) \; : \; x \neq y \Rightarrow f(x) \neq f(y)\)

Autrement dit tout élément de l’image de la relation (l’ensemble d’arrivée) possède au plus un antécédent dans le domaine (ensemble de départ) de la relation.

Nous invitons le lecteur à trouver par lui-même un exemple d’application injective.

Surjection

Une application est surjective (surjection) si et seulement si :

• \(\forall y \in B \; , \; \exists x \in A \; , \; y=f(x)\)

L’image de la relation est l’ensemble d’arrivée : \(image(R) = B\).

Autrement dit tout élément de l’ensemble d’arrivée possède au moins un antécédent dans l’ensemble de départ.

Exemple : l’application définie par \(y = x^2\) est une application surjective de \(\mathbb{R}\) vers \(\mathbb{R_+}\)

Comme on le voit sur le graphe de la fonction, tous les éléments de l’ensemble d’arrivée (\(\mathbb{R}_+\)) sont en relation avec au moins un élément de l’ensemble de départ (\(\mathbb{R}\)).

Bijection

Une application est bijective (injective et surjective} si et seulement si :

• \(\forall y \in B \; , \; \exists ! x \in A \; , \; y=f(x)\)

Autrement dit :

• tout élément de l’ensemble d’arrivée possède un et un seul antécédent dans l’ensemble de départ et réciproquement.
• l’application définie par \(y = x^3\) est une application surjective de \(\mathbb{R}\) vers \(\mathbb{R_+}\)

Comme on le voit sur le graphe de la fonction, tous les éléments de l’ensemble d’arrivée (\(\mathbb{R}\)) sont en relation avec un et un seul un élément de l’ensemble de départ (\(\mathbb{R}\)).

En résumé :

Diagramme de Venn pour une application injective,surjective et bijective :

Graphes de fonction pour une application injective, surjective et bijective :

Exemple :

L’exrcice ci-dessous permettra au lecteur de se familiariser avec les notions d’applications injective, surjective, bijective.

• Question
• Solution

Suivant les ensembles de départ et d’arrivée :

1. \(f : \mathbb{R} \rightarrow \mathbb{R}\)
2. \(f : \mathbb{R_+} \rightarrow \mathbb{R}\)
3. \(f : \mathbb{R} \rightarrow \mathbb{R_+}\)
4. \(f : \mathbb{R_+} \rightarrow \mathbb{R_+}\)

La fonction \(f : x \longrightarrow x^2\) est-elle :

• injective
• surjective
• bijective
• aucun des trois cas possibles

Votre réponse :

Texte : inputlines1190.txt

dans le premier cas la fonction est : ....

Zone de saisie de texte

Clavier	Action
F1	Afficher une aide technique
F2	Afficher une aide pédagogique
Ctrl-A	Tout sélectionner
Ctrl-C	Copier la sélection dans le presse-papier
Ctrl-V	Copier le presse-papier dans la sélection
Ctrl-X	Couper la sélection et la copier dans le presse-papier
Ctrl-Z	Annuler la modification
Maj-Ctrl-Z	Rétablir la modification

Menu	Action
	Ré-initialiser les sorties
	Faire apparaître le menu d'aide
	Valider la zone de saisie
	Initialiser la zone de saisie
	Charger le contenu d'un fichier dans la zone de saisie
	Sauvegarder le contenu de la zone de saisie dans un fichier
	Imprimer le contenu de la zone de saisie

Une solution possible :

dans le premier cas (\(f : \mathbb{R} \rightarrow \mathbb{R}\)) la fonction (\(f : x \longrightarrow x^2\)) est :

• non-injective : deux éléments de l’ensemble de départ ont la même image \(\{ -1,+1 \} \rightarrow \{ +1 \}\)
• non-surjective : des éléments de l’ensemble d’arrivée n’ont pas d’antécédent (ex : \(y=-4\) n’a pas d’antécédent)
• non-bijective : puisque non-injective et non-surjective

dans le deuxième cas (\(f : \mathbb{R_+} \rightarrow \mathbb{R}\)) la fonction (\(f : x \longrightarrow x^2\)) est :

• injective : Les éléments de l’ensemble d’arrivée ont au plus un antécédent
• non-surjective : des éléments de l’ensemble d’arrivée n’ont pas d’antécédent (ex : \(y=-4\) n’a pas d’antécédent)

dans le troisième cas (\(f : \mathbb{R} \rightarrow \mathbb{R_+}\)) la fonction (\(f : x \longrightarrow x^2\)) est :

• non-injective : deux éléments de l’ensemble de départ ont la même image \(\{ -1,+1 \} \rightarrow \{ +1 \}\)
• surjective : tout élément de l’ensemble d’arrivée a au moins un antécédent
• non-bijective : puisque non-injective

dans le dernier cas (\(f : \mathbb{R_+} \rightarrow \mathbb{R_+}\)) la fonction (\(f : x \longrightarrow x^2\)) est :

• injective : Les éléments de l’ensemble d’arrivée ont au plus un antécédent
• surjective : tout élément de l’ensemble d’arrivée a au moins un antécédent
• bijective : puisque injective et surjective

Union de deux ensembles

L’union de deux ensembles \(A\) et \(B\) est l’ensemble qui contient tous les éléments \(x\) qui appartiennent à \(A\) ou qui appartiennent à \(B\).

On la note classiquement \(A \cup B\).

• \(A \cup B = \{ x \mid ( x \in A ) \lor ( x \in B ) \}\)

Par la suite on utilisera la notation préfixée de l’opérateur binaire d’union :

• \(\cup(A,B) = \{ x \mid ( x \in A ) \lor ( x \in B ) \}\)

que l’on peut aussi écrire avec les fonctions caractéristiques (prédicats: \(P_A,P_B\)) :

• \(\cup(A,B) = \{ x \mid P_A(x) \lor P_B(x) \}\)

Par exemple l’union des ensembles \(A\) et \(B\) :

• \(A = \{ 1, 2, 3 \}, B = \{ 2, 3, 4 \}\)

est l’ensemble :

• \(R=\cup(A,B) = \{1, 2, 3, 4\}\).

Par défaut l’opérateur \(\cup\) élimine les doublons (éléments commun aux deux ensembles). On peut également appliquer un UNION ALL si on ne veut pas les éliminer.

En logique booléenne l’union correspond à l’opérateur logique ou inclusif (\(\lor\)).

N.B: le ou est par défaut inclusif (en cas d’exclusion mutuelle on parlera de ou exclusif).

Intersection de deux ensembles

L’intersection de deux ensembles \(A\) et \(B\) est l’ensemble qui contient tous les éléments \(x\) qui appartiennent à \(A\) et qui appartiennent à \(B\).

On la note classiquement \(A \cap B\).

• \(A \cap B = \{ x \mid ( x \in A ) \land ( x \in B ) \}\)

Par la suite on utilisera la notation préfixée de l’opérateur binaire d’intersection :

• \(\cap(A,B) = \{ x \mid ( x \in A ) \land ( x \in B ) \}\)

que l’on peut aussi écrire avec les fonctions caractéristiques (prédicats: \(P_A,P_B\)) :

• \(\cap(A,B) = \{ x \mid P_A(x) \land P_B(x) \}\)

Par exemple l’intersection des ensembles \(A\) et \(B\) :

• \(A = \{1, 2, 3\}, B = \{2, 3, 4\}\)

est l’ensemble :

• \(R=\cap(A,B) = \{2, 3 \}\).

En logique booléenne l’intersection correspond à l’opérateur logique et (\(\land\)).

N.B: le et est par défaut exclusif (on parlera de et inclusif pour définir l’équivalence logique).

Différence de deux ensembles

La différence entre deux ensembles \(A\) et \(B\) est l’ensemble qui contient les éléments \(x\) qui appartiennent à \(A\) et qui n’appartiennent pas à \(B\).

On la note classiquement \(A \setminus B\).

• \(A \setminus B = \{ x \mid ( x \in A ) \land ( x \notin B ) \}\)

Par la suite on utilisera la notation préfixée de l’opérateur binaire de différence :

• \(\setminus(A,B) = \{ x \mid ( x \in A ) \land ( x \notin B ) \}\)

que l’on peut aussi écrire avec les fonctions caractéristiques (prédicats: \(P_A , P_B\)) :

• \(\setminus(A,B) = \{ x \mid P_A(x) \land \neg P_B(x) \}\)

Par exemple la différence entre les ensembles \(A\) et \(B\) :

• \(A = \{1, 2, 3\}, B = \{2, 3, 4\}\)

est l’ensemble :

• \(R=\setminus(A,B) = \{1 \}\).

L’opérateur de différence n’est pas commutatif :

• \(R=\setminus(B,A) = \{4 \}\).

En logique booléenne la différence correspond à la négation de l’implication (\(\Rightarrow\)).

Implication : « A seulement si B »

• \((A \Rightarrow B) \Leftrightarrow (\neg A \lor B)\)

Non-implication : « A mais pas B »

• \(\neg (A \Rightarrow B) \Leftrightarrow (A \land \neg B)\)

L’implication sera présentée dans la partie « Logique » de ce chapitre.

Représentation des diagrammes de Venn pour l’union (\(\cup\)), l’intersection (\(\cap\)), la différence symétrique (ou exclusif, \(\oplus\)) et la différence (\(\setminus\)).

Disjonction exclusive (\(\oplus\)) :

• \(A \oplus B = \{ x \mid ( x \in A \land x \notin B ) \cup ( x \notin A \land x \in B ) \}\).

Table de vérité de l’opérateur (\(\oplus\)) :

Représentation du diagramme de Venn pour disjonction exclusive (\(\oplus\))

SELECT * FROM A;
SELECT * FROM B;

-- A xor B --
SELECT x AS "A xor B"  FROM A WHERE x NOT IN (SELECT y FROM B)
UNION
SELECT y FROM B WHERE y NOT IN (SELECT x FROM A);

SELECT COALESCE(A.x, B.y) AS "A xor B"
FROM  A FULL OUTER JOIN B
ON A.x = B.y
WHERE A.x IS NULL OR B.y IS NULL;

Propriétés des opérateurs ensemblistes :

L’union et l’intersection sont commutatives :

• \(\cup(A,B) = \cup(B,A)\)
• \(\cap(A,B) = \cap(B,A)\)

L’union et l’intersection sont associatives :

• \(\cup(A,\cup(B,C)) = \cup(\cup(A,B),C)\)
• \(\cap(A,\cap(B,C)) = \cap(\cap(A,B),C)\)

L’union est distributive par rapport à l’intersection :

• \(\cup(A,\cap(B,C)) = \cap(\cup(A,B),\cup(A, C))\)

L’intersection est distributive par rapport à l’union :

• \(\cap(A,\cup(B,C)) = \cup(\cap(A,B),\cap(A, C))\)

L’intersection est distributive par rapport à la différence :

• \(\cap(A,\setminus(B,C)) = \setminus(\cap(A,B),\cap(A, C))\)

Par contre :

La différence n’est pas commutative :

• \(\setminus(A,B) \neq \setminus(B,A)\)

La différence n’est pas associative :

• \(\setminus(A,\setminus(B,C)) \neq \setminus(\setminus(A,B),C)\)

L’union n’est pas distributive par rapport à la différence :

• \(\cup(A,\setminus(B,C)) \neq \setminus(\cup(A,B),\cup(A, C))\)

La différence n’est pas distributive par rapport à l’union :

• \(\setminus(A,\cup(B,C)) \neq \cup(\setminus(A,B),\setminus(A, C))\)

La différence n’est pas distributive par rapport à l’intersection :

• \(\setminus(A,\cap(B,C)) \neq \cap(\setminus(A,B),\setminus(A, C))\)