Annexe A
Annexe mathématique
Cette annexe est inspirée de [7].
A.1 Logique fondamentale
Les expressions logiques dénotent des prédicats qui
ont une interprétation dans le domaine des valeurs de
vérité : true et false.
|
Symbole
|
Signification
|
Définition
|
|
?
|
et logique
|
|
|
#172;
|
négation
|
|
|
?
|
ou logique
|
a ? b = #172;(#172;a ? #172;b)
|
|
implication
|
a b = #172;a ? #172;b
|
|
?
|
équivalence
|
a ? b = (a b) ? (b a)
|
On peut quantifier les prédicats par les quantificateurs
universel et existentiel.
|
Symbole
|
Signification
|
Syntaxe
|
Définition
|
|
?
|
pour tout
|
?Id_liste.(Prdicat)
|
|
|
?
|
il existe
|
?Id_liste.(Prdicat)
|
?x.(P) = #172;?x.(#172;P
)
|
Le non-terminal Id_liste
représente une liste d'identificateurs séparés par
des virgules. Le non-terminal Prdicat désigne un
prédicat quelconque .
A.2 Ensemble
On désigne par s et t deux ensembles.
x un élément de s. On dispose des
prédicats suivants relatifs aux ensembles:
|
Symbole
|
Signification
|
Définition
|
|
?
|
appartient à
|
|
|
??
|
n'appartient pas
|
x ? s = #172;(x ? s)
|
|
?
|
est inclus dans
|
s ? t = s ? P(t)
|
|
??
|
n' est pas inclus dans
|
s ?? t = #172;(s ? t)
|
|
?
|
est strictement inclus dans
|
s ? t = (s ? t ? s =? t)
|
|
??
|
n'est pas strictement inclus dans
|
s ?? t = #172;(s ? t)
|
A.3 Tuple
|
Syntaxe
|
|
Nom
|
|
(a1,a2,
|
,an)
|
tuple d'éléments
|
|
(x,y)
|
|
paire ordonnées d'éléments
|
|
first
|
|
permet d'extraire le premier élément d'une paire
ordonnée
|
|
second
|
|
permet d'extraire le second élément d'une paire
ordonnée
|
A.4 Relations
Les relations sont un cas particulier de constructions
d'ensembles.
|
Symbole
|
Siginification
|
Définition
|
|
E1 ? E2
|
relations entre deux ensembles
|
E1 ? E2 . = E1 × E2
|
On définit le domaine d'une relation comme les
éléments du premier ensemble E1 qui sont effectivement en
relation avec des éléments du second ensemble E2. Le codomaine
est l'ensemble des points du second ensemble E2 qui sont en relation avec des
éléments du premier ensemble E1. L'image d'un ensemble par une
relation, notée r[F] est l'ensemble des éléments de E2 qui
sont en relation avec les éléments de F par la relation r. Plus
formellement :
Annexe A. Annexe mathématique
|
Condition
|
Expression
|
Définition
|
|
r ? E1×E2
|
dom(r)
|
{x|x ? E1 ? ?y.(y ? E2 ?
(x ?? y) ? r)}
|
|
r ? E1×E2
|
ran(r)
|
{y|y ? E2 ? ?x.(x ? E1 ?
(x ?? y) ? r)}
|
|
r ? E1×E2
et F ? E1
|
r[F]
|
{y|y ? E2 ? ?x.(x ? F ? (x ??
y) ? r)}
|
A.4.1 Opérations stir les relations
Il existe de nombreuses opérations sur les relations.
Les opérations sur les ensembles s'appliquent évidemment aux
relations (qui sont effectivement des ensembles de couples). En particulier,
une relation vide est la même chose qu'un ensemble vide.
Néanmoins, il y a quelques opérations spécifiques, dont la
plupart sont très usuelles. On a la relation identité sur un
ensemble, qui à chaque élément associe le même
élément. La relation inverse d'une relation don-née. On
distingue ensuite trois formes de composition de relations. Enfin, on a les
opérations de projection qui construisent les relations entre les
ensembles paramètres et les éléments projetées
droite ou gauche.
|
Condition
|
Expression
|
Définition
|
|
id(E)
|
{x,y|(x ?? y) ? E×E ? x =
y}
|
|
r ? s ? t
|
r-1
|
{y,x|(y ?? x) ? t×s ? (x ??
y) ? r
|
|
r1 ? t ? u
r2 ? u ? v
|
r1;r2
|
{x,z|x,z ? t×v?
?y.(y ? u ? (x ??
y) ? r1 ? (y ?? z) ? r2}
|
|
r1 ? t ? u
r2 ? t ? v
|
r1?r2
|
{x, (y, z)|x, (y, z) ?
t×(u×v)?
(x ?? y) ? r1 ? (x ?? z)
? r2}
|
|
r1 ? t ? u
r2 ? v ? w
|
r1 ? r2
|
{(x,z),(y,a)|(x,z),(y,a)
?
(t×v)×(u×w)?
(x
?? y) ? r1 ? (z ?? a) ?
r2}
|
|
prj1(E,F)
|
{x,y,z|x,y,z ? E×F×E ? z = x}
|
|
prj2(E,F)
|
{x,y,z|x,y,z ? E×F×F ? z = y}
|
| 
