Является ли один ряд ограничений подмножеством другого?

Question

У меня есть две серии ограничений S и S ', они описывают возможно бесконечно большие множества. Скажем, например, S: x <= 10 and y <= x и S': x <= 20 and y <= 20. Теперь я хочу знать, является ли S подмножеством S'?

Я думал, что могу попытаться решить что-то вроде: S' and not (S and S'), если не удалось найти решение S является подмножеством S '.

Как бы поместить это в пролог, это надежное решение? Я использую gprolog, но я могу переключиться на другую реализацию.

Answer 1

Комментарий по @false правильно, насколько я могу судить: даны два множества S и S «: если S является подмножеством S», то пересечение дополнения из S «и S должен быть пустым множеством (нет элементов за пределами S», которые являются элементами S).

Кажется, что constraint programming over finite domains должен делать трюк, если вы имеете дело с целыми числами. Использование SWI-Prolog 7.3, и делает свой пример вручную, я получаю:

?- use_module(library(clpfd)). 
true. 

?- \+ (X #=< 10, Y #=< X, #\ X #=< 20 #\/ #\ Y #=< 20). 
true. 

Второй запрос должен гласить:

\+ (% succeed if no solutions 
    X #=< 10, Y #=< X, % set S and... 
    #\ X #=< 20 #\/ #\ Y #=< 20 % complement of set S' (De Morgan's Law) 
). 

Я думаю, что дополнение S "мог бы также было написано как:

\# (X #=< 20 #/\ Y #=< 20) 

Если вы хотите иметь более общее решение, которое вы должны выяснить способ, чтобы найти дополнение произвольного множества ограничений s. Обратите внимание: может использовать логический код Пролога (запятая), но вы не можете использовать дизъюнкцию как ИЛИ.