In constraint satisfaction, constraint inference is a relationship between constraints and their consequences. A set of constraints
D
entails a constraint
C
if every solution to
D
is also a solution to
C
. In other words, if
V
is a valuation of the variables in the scopes of the constraints in
D
and all constraints in
D
are satisfied by
V
, then
V
also satisfies the constraint
C
.
Some operations on constraints produce a new constraint that is a consequence of them. Constraint composition operates on a pair of binary constraints
(
(
x
,
y
)
,
R
)
and
(
(
y
,
z
)
,
S
)
with a common variable. The composition of such two constraints is the constraint
(
(
x
,
z
)
,
Q
)
that is satisfied by every evaluation of the two non-shared variables for which there exists a value of the shared variable
y
such that the evaluation of these three variables satisfies the two original constraints
(
(
x
,
y
)
,
R
)
and
(
(
y
,
z
)
,
S
)
.
Constraint projection restricts the effects of a constraint to some of its variables. Given a constraint
(
t
,
R
)
its projection to a subset
t
′
of its variables is the constraint
(
t
′
,
R
′
)
that is satisfied by an evaluation if this evaluation can be extended to the other variables in such a way the original constraint
(
t
,
R
)
is satisfied.
Extended composition is similar in principle to composition, but allows for an arbitrary number of possibly non-binary constraints; the generated constraint is on an arbitrary subset of the variables of the original constraints. Given constraints
C
1
,
…
,
C
m
and a list
A
of their variables, the extended composition of them is the constraint
(
A
,
R
)
where an evaluation of
A
satisfies this constraint if it can be extended to the other variables so that
C
1
,
…
,
C
m
are all satisfied.
