Page 114 - 4495

( def , con )  C та def ,( con )  C, деcon  .
1 2 
Суть полягає в тому, що якщо P є удосконаленням P, то множи-
на відповідних кортежів з P включена в множину оптимальних кор-

тежів з P. Задача знаходження оптимальних кортежів у P зводиться
до пошуку оптимальних кортежів у P.
Модель оцінного задоволення обмежень, в якій визначено удо-

сконалення, не має жодного часткового впорядкування. Розглянемо
наслідки означення напівкільцевої CSP з урахуванням існування не-

порівнюваних напівкільцевих значень (a  ) b . Зазначимо, для почат-
S
ку, що непорівнюваність напівкільцевих значень de  та de  у по-
) (t
)
(r
f
f
чатковій задачі P не несе за собою жодних зв’язків у вдосконалені
задачі і вони можуть стати в задачі P або порівнюваними або не порі-
внюваними. Такий висновок ставить у відповідність наведене вище
означення удосконалення класичному означенню удосконалення з
теорії множин і якщо щось є непорівнюваним у початковій частково

впорядкованій множині, тільки удосконалення може, або навіть по-
винне впорядкувати це. Так чи інакше, протилежне твердження має
строгий наслідок, як показано у виводі 2.

Вивід 2. Нехай напівкільцева CSP P є удосконаленням Pта зада-
но два кортежі: t  (t ,...,t )та r  (r ,...,r ), де t r  , таких, що
D
1 con 1 con , i i
( )r
def (t )  def (r ) . Тоді справедливо, що def  ( )t  ' def 
S S
Припустимо, що нерівність def  ( )t  ' def  є нерівною. Це означає,
( )r
S
що de  та de  є впорядковані. Наявність будь – якого впорядку-
f
) (t
)
(r
f
вання між цими напівкільцевими значеннями означає, що повинна
бути певна впорядкованість між def ) (t та def (r ), відповідно до озна-
чення 41. Однак, оскільки ці елементи не порівнювані враховуючи
припущення виводу, ми прийшли до суперечності, що доводить пра-
вильність цього виводу.

Означення 42 (еквівалентність II). Дві напівкільцеві CSP P та
Pназиваються (строго) еквівалентними, якщо кожне з них є строгим
удосконаленням іншого.

Еквівалентні напівкільцеві CSP визначають одне й те саме впоря-
дкування над кортежами значень у множині V і мають однакову від-
повідну множину оптимальних кортежів і задача знаходження опти-
мальних кортежів еквівалентна в обох CSP. Зазначимо, що дві еквіва-

лентні напівкільцеві CSP не обов’язково мають однакові значення в
кортежах, вони тільки впорядковують їх однаково. Тобто, це визна-
чення є слабким за означенням 40.

114