Une contrainte est une relation entre différentes
variables. Cette relation peut être définie en extension ou en
intension :
· Pour définir une contrainte en extension, on
énumère les tuples de valeurs appartenant à la relation.
Par exemple, si les domaines des variables x et y contiennent les valeurs 0, 1
et 2, alors on peut définir la contrainte »x est plus petit que
y» en extension par »(x=0 et y=1) ou (x=0 et y=2) ou (x=1 et
y=2)», ou encore par »(x,y) élément-de {(0,1), (0,2),
(1,2)}»
· Pour définir une contrainte en intention, on
utilise des propriétés mathématiques connues. Par exemple:
»x < y» ou encore »A etB non(C)»
L'aritéd'une contrainte est le nombre de variables sur
lesquelles elle porte. On dira que la contrainte est:
· unaire si son aritéest égale
à 1 (elle ne porte que sur une variable). Par exemple »x x x =
4» ou encore »est-un-triangle(y)»
· binaire si son aritéest égale
à 2 (elle met en relation 2 variables). Par exemple »x =6 y»
ou encore»A?B = A»
· ternaire si son aritéest égale
à 3 (elle met en relation 3 variables). Par exemple »x + y < 3 x
z - 4» ou encore »(non x) ou y ou z = vrai»
· n-aire si son aritéest égale
à n (elle met en relation un ensemble de n variables). On dira
également dans ce cas que la contrainte est globale. Par exemple, une
contrainte globale courante (et très pratique) est la contrainte
»toutesDifférentes(E)», oùE est un ensemble de
variables, qui contraint toutes les variables appartenant à E à
prendre des valeurs différentes.
2.1.4 Différents types de contraintes
On distingue différents types de contraintes en
fonction des domaines de valeurs des variables [1] :
· Les contraintes numériques, portant
sur des variables à valeurs numériques : une contrainte
numérique est une égalité(=) , une différence (6=)
ou une inégalité(<, =, >, =) entre deux ex-
10
pressions arithmétiques.
On distingue:
- les contraintes numériques sur les réels, quand
les variables de la contrainte peuvent prendre
des valeurs réelles, par exemple une contrainte physique
comme »U = R x I»
- les contraintes numériques sur les entiers, quand les
variables de la contrainte ne peuvent
prendre que des valeurs entières, par exemple une
contrainte sur le nombre de personnes pouvant
être embarqués dans un avion.
On distingue également :
- les contraintes numériques linéaires, quand les
expressions arithmétiques sont linéaires
Par exemple »4 x x - 3 x y + 8 x z
< 10»
- les contraintes numériques non linéaires, quand
les expressions arithmétiques contiennent des
produits de variables, ou des fonctions logarithmiques,
exponentielles...
Par exemple »x x x = 2» ou
»sinus(x) + z x log(y) =
4».
· Les contraintes booléennes, portant
sur des variables à valeur booléenne (vrai ou faux) : une
contrainte booléenne est une implication (=), une équivalence (?)
ou une non équivalence (~) entre deux expressions
logiques.
Par exemple »(non a) ou b =
c» ou encore »non (a ou b) ? (c
et d)».
· Les contraintes de Herbrand, portant sur des
variables à valeur dans l'univers de Herbrand : une contrainte de
Herbrand est une égalité(=) ou inégalité(6=) entre
deux termes (appelés aussi arbres) de l'univers de Herbrand. En
particulier, unifier deux termes Prolog revient à poser une contrainte
d'égalitéentre eux. Par exemple l'unification de
»f(X, Y )»avec
»f(g(a), Z)» s'exprime par la
contrainte »f(X,Y ) =
f(g(a),Z)».
· ... et bien d'autres encore, comme les contraintes sur
les ensembles, ...
