Page 133 - 4495

  
max( , ) (max( , ),a b  a b  ,max( , ))a b .
1 1 h h
Проблема полягає в тому, що така операція не є монотонною на

напівкільцевому впорядкування  , тобто приходимо до суперечли-
S 2
вості з базовими принципами с-напівкільця. Нагадаємо, що

[a  S b ] min( , )a b  ] b та покажемо приклад, що демонструє немоно-

тонну поведінку операції  для такого визначення напівкільця.
Приклад 4. Нехай (0,1) та (1,0) належать напівкільцевій множині

A. Тоді правильно, що (0,1)  (1,0) . Домножимо обидві сторони нерів-
S
 
ності на (0,1), ми повинні отримати max((0,1),(1,0)  S max(1,0),(1,0)) ,
виходячи із монотонності. Однак одержуємо результат (1,1)  (1,0), що
S
суперечить монотонності.
Покажемо, що кожна мультиплікативна операція в с-напівкільці
для компаратора «краще в найгіршому випадку» повинна бути немо-
нотонною на напівкільцевому впорядкуванні, тобто, що не існує кла-

су напівкільцевої CSP, який би розв’язував ІО з цим компаратором.
Нехай маємо ІО C C  C  { , } { }c c  c таку, в якій справедлива
1 2 1 2 3
нерівність ( ) (w c e c ) w ( ) (c e c  для кожного присвоєння  . Відпові-
)
1 1 2 2
дний клас напівкільцевої CSP може бути заданий як
( ,C con ) ({(def ,con ) (c def ,con ),i  1 3},con  con  con ). Такий клас
i i i i i 1 2 3
напівкільцевої CSP повинен задовольняти нерівність для c та c , що
1 2
була задана в описі задачі. Нерівність
def (t  con )  def (t  con )
1 con 1 S 2 con 2
cправедлива для всіх кортежів t , визначених на змінній в con тому,

що обидва обмеження належать до одного і того ж рівня ІО, і c зав-
2
жди більш важливе, ніж c (з припущення). Обмеження c належить
1 3
до нижчого рівня, ніж c , тому справедлива також нерівність
1
con con
 : t def (t  )  def (t  ). Додамо до обох сторін нерівності c , і з
3 con S 1 con 2
3 1
монотонності  над  одержимо:
S
con con con con
def (t  ) def (t  )  def (t   def (t  )
3 con 2 con S 1 con 2 con
3 2 1 2
Обмеження c та c знаходиться на одному рівні ієрархії, а c бі-
1 2 2
льше за вагою, ніж c . Відповідно повинна бути правильною рівність
1
con con con
def (t  ) def (t  )  def (t  ) для всіх кортежів t , заданих на
1 con 1 2 con 2 S 2 con 2
змінних con. Отже, приходимо до виразу:
con con con
def (t  ) def (t  )  def (t  ).
3 con 2 con S 2 con
3 2 2
Однак, виходячи із ієрархічної поведінки компаратора, отримує-

133