Труды КНЦ вып.8 (ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ вып. 3/2017(8))

формализации ограничений используются не D-системы (матрицы дизъюнктов), а С-системы (матрицы конъюнктов), а также разработан оригинальный метод распространения ограничений для этого случая. Задача удовлетворения ограничений (CSP) - это тройка ( V, D, С), где (1) V = {vi, ..., v„} - множество переменных; (2) D = {D\, ..., Dn} - множество доменов; каждый домен Д - конечное множество, содержащее возможные значения, соответствующей переменной; (3) С = {Ci, ..., Сп} - множество ограничений. Ограничение С - отношение, определённое на подмножестве значений всех переменных, т.е. Сгс D\ х ... х /)„. Заданная (частичная или полная) подстановка значений переменных удовлетворяет ограничению Сь если каждая переменная получила такое значение, что соответствующий кортеж значений принадлежит С*. Множество всевозможных подстановок для всех переменных является пространством, содержащим решение CSP-задачи. Решением CSP-задачи является такая подстановка для всех переменных, при которой все ограничения удовлетворены. Если для некоторой задачи имеется, по крайней мере, одно решение, то задача является разрешимой, иначе - неразрешимой (противоречивой, переограниченной). По сути, в виде задачи CSP предлагается представлять качественные абстракции физических законов, например, закон Кирхгоффа, закон Ома. Для использования качественных моделей требуются определенные методы проведения качественных рассуждений, изложению которых и посвящена настоящая статья. Сам характер вывода в рамках парадигмы программирования в ограничениях заключается в упрощении задачи CSP, то есть в приведении ее к задаче, содержащей меньшее количество ограничений, меньшее количество значений в доменах переменных и т.п. С помощью С-систем удобно моделировать дизъюнктивные нормальные формы (ДНФ) конечных предикатов. Продемонстрируем это на примере: ф(х, y , z ) = (x =a,b) л (у =а,с) \/ (z =d ). Для простоты все переменные определены на одном и том же множестве {a,b,c,d } . Здесь и далее будем использовать запись вида (х = а,Ъ) для обозначения выражения (х =a ) v (х =Ь ). Учитывая, что область истинности одноместного предиката (х =а,Ь ) есть {а, Ь}, то область истинности предиката ср(х, y ,z ) может быть представлена в виде следующей С-системы: {а,Ь} {а,с} * * * {d} Атрибуты X, Y, Z С -системы R \XYZ\ соответствуют переменным х, у, z формулы cp (x ,y ,z ). Заметим, что сокращенное обозначение всего диапа­ зона возможных значений (домена) атрибута. В том случае, если CSP представлена в виде совокупности С-систем, целью преобразований является приведение системы ограничений к более простому виду, где содержится меньшее количество С-систем, строк С-систем, столбцов (атрибутов) С-систем, значений в доменах атрибутов и т. п [4 - 9]. Перечислим утверждения, позволяющие реализовывать подобный вывод для случая, когда ограничения представлены в виде набора С-систем. R[XYZ] = 99