Page 111 - 4495

її вбудований елемент, та 0 – абсорбуючий.
c– напівкільце (на півкільце базоване на обмеженнях) – це на
півкільце A , , ,0,1  , таке, в якому операція  – ідемпотентна 1 – її аб-

сорбуючий елемент, а  – комутативна.

Нехай маємо відношення  на множині A таке, що a  b, якщо
S S
a  b  b. Тоді не важко довести, що  – частковий порядок, 0 – його
S
найменший елемент, 1 – найбільший. Тоді відношення  можна ви-
S
користовувати для порівняння кортежів і обмежень: якщо a  b, то це
S
інтуїтивно означає, що b краще, ніж a. Слід зазначити, що  може не
S
бути загальним порядком, що є суттєвою відмінністю від оцінного

задоволення обмежень, в якому всі преференції є строго впорядкова-
ними. Прийнято вважати, що значення a і b із напівкільця A є не по-
рівнюваними і позначаються a  , якщо виконується умова:
S
(a  b  ) a  (a  b  ) b .
Інша властивість, яку можна одержати з атрибутів с-напівкільця

монотонністю обох напівкільцевих операцій, тобто нерівність a  a
S

означає, що a  b  a   b і a b  a   b для всіх , ,a a bA
S S
Означення 32. Система обмежень – це кортеж CS  (S , D ,V ), де S –
c– напівкільце, D– скінченна множина (область визначення, домен

змінних), та V – впорядкована множина змінних.
Означення 33 (обмеження). У напівкільці S  A , , ,0,1  і системі

обмежень CS  (S , D ,V ), обмеженням називається пара (def ,con ), де

con  V та def : D con  A . Тому, обмеження визначає множину змінних
(con ) і присвоює кожному кортежу значень цих змінних значення із на
півкільця.

Означення 34 (задача). М’яка CSP – це пара (C ,con )визначена на
V
системі обмежень (S ,D ,V ), де con  а C – множина обмежень.
con– є множиною змінних для множини C , яка в свою чергу, мо-
же також містити змінні, які не входять в con.
Операції

Нагадаємо визначення проекції кортежу t  проектує кортеж
X
Y
значень, визначений на множині X у кортеж на множині Y (для дета-
льнішого опису див. означення 13).

Означення 35 (комбінація). Нехай задано обмеження
c
c  (def ,con ) та c  (def ,con ). Їхньою комбінацією c  буде обмежен-
1 1 1 2 2 2 1 2
ня (def ,con )в якому множина con буде являти собою об’єднання мно-
жин con і con : con  con  con , а def буде визначатися таким чином:
1 2 1 2

111