Введение

В задачах удовлетворения ограничений, логический вывод ограничений – это связь между ограничениями и их следствиями. Набор ограничений влечет за собой ограничение, если каждое решение, удовлетворяющее , также является решением для . Иными словами, если является оценкой переменных в областях действия ограничений в , и все ограничения в удовлетворяются , то также удовлетворяет ограничению .

Некоторые операции над ограничениями приводят к новому ограничению, являющемуся их следствием. Композиция ограничений применяется к паре бинарных ограничений и с общей переменной. Композиция таких двух ограничений – это ограничение , которое удовлетворяется каждой оценке двух переменных, не имеющих общих значений, для которых существует значение общей переменной , такое что оценка этих трех переменных удовлетворяет двум исходным ограничениям и .

Проекция ограничений ограничивает влияние ограничения некоторыми его переменными. Для заданного ограничения , его проекция на подмножество его переменных – это ограничение , которое удовлетворяется оценкой, если эту оценку можно расширить на остальные переменные таким образом, чтобы исходное ограничение было удовлетворено. Расширенная композиция по принципу схожа с композицией, но допускает произвольное количество ограничений, которые могут быть небинарными; полученное ограничение задается на произвольном подмножестве переменных исходных ограничений. Для заданных ограничений и списка их переменных, расширенная композиция этих ограничений – это ограничение , где оценка удовлетворяет этому ограничению, если ее можно расширить на остальные переменные так, чтобы все ограничения были удовлетворены.