учитывая набор условий, алгоритмически определить, что только одно может быть истинным

Question

Учитывая набор из двух или более логических условий, возможно ли алгоритмически определить, что ровно ОДНО из них будет оцениваться как ИСТИНА? Например:

# this should pass, since for every X, only one condition is taken
cond 1: (X >= 1.0) 
cond 2: (X < 1.0)

# this should fail
cond 1: (X < 1.0)
cond 2: (X > 2.0)

# this should also fail, since X=1.0 would meet both conditions
cond 1: (X < 2.0)
cond 2: (X > 0.0)

# there may be more than one variable involved
cond 1: (X >= 1.0 && Y >= 0)
cond 2: (X < 1.0 && Y <= -1)

Эти условия генерируются из предметно-ориентированного языка и используются для определения следующего пути выполнения. то есть пользователи составляют условие для каждого параметра, когда дерево выполнения разделяется на несколько путей, а условие, которое оценивается как истинное, определяет путь, который должен быть выбран. Чтобы симуляция была действительной, это должен быть только один возможный путь, который может быть выбран для любых заданных значений.

В настоящее время я оцениваю эти условия во время выполнения и выкидываю истерику, если более одного (или ни одного) из них истинны.

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

обновление

Что касается того, что может быть включено в условия, сфера применения на практике довольно широка. Все это возможные условия:

• X >= Y && Y < Z
• X.within_radius(0.4)
• X IN some_array
• X * Y < Z

окончательное обновление

Похоже, что решение, охватывающее все возможные условия, невозможно (или, по крайней мере, учитывая мои ограниченные знания, невозможно в течение времени, отведенного для решения проблемы). Я вернусь к этому когда-нибудь, но пока принимаю ответ, который выдвинул меня вперед.

Answer 1

РЕДАКТИРОВАТЬ: Я буду повторять, потому что кажется, что другие ответы предполагают кучу вещей, которые с тех пор были подтверждены:

Если вы можете указать свои условия (и ограничение, что только одно из них верно) в терминах арифметики Пресбургера , то вы можете написать процедуру принятия решения для статической проверки этого свойства. Это кажется вполне достижимым из приведенных выше примеров.

Подход "тупого инструмента" заключается в том, чтобы в основном взаимодействовать с чем-то вроде автоматического средства доказательства теорем или решателя SMT (где вы в основном пытались бы доказать отрицание утверждения "существует некоторое значение x, которое удовлетворяет условию1 XOR ограничение2") ). Я программно взаимодействовал с CVC3 и раньше, и мне было приятно с ним работать, но я понимаю, что его превзошли другие решатели SMT.

Все, что вы делаете для решения этой проблемы, вероятно, в конечном итоге будет приближаться к реализации некоторых видов инструментов, которые я предложил, я думаю. В зависимости от того, как именно указаны ваши ограничения, вы можете уйти с реализацией какой-то процедуры принятия решения для чего-то вроде арифметики Пресбургера .

Answer 2

Если вы хотите выяснить, является ли истинным только одно условие (из двух или более возможных условий), может быть полезно обратиться к этому вопросу xor для SO: xor-of-three-values ​​.Взяв непосредственно из его ответа:

(a ^ b ^ c) && !(a && b && c)

В вашем случае:

(cond 1 ^ cond 2 ^ cond 3) && !(cond 1 && cond 2 && cond 3)

Существует также общее решение, при котором вы увеличиваете счетчик каждый раз, когда выполняется любое условие, затем проверяете счет против1 раз все условия были проверены.

Answer 3

В общем, нет.Но если вы действительно спрашиваете, возможно ли это, учитывая условия, состоящие из логических логических комбинаций неравенств на конечном множестве независимых целочисленных переменных с константами, тогда есть надежда.Вы можете полностью проверить, переставив переменные с константами, которые появляются в ваших неравенствах (и +1 и -1 из этих констант), и убедившись, что число условий, которые выполняются, всегда равно 1.

Answer 4

Являются ли строительные блоки ваших условий просто

• целочисленная переменная,
• оператор сравнения из (<, <=,>,> =),
• числа (предположим, целые числа)?

И окончательные условия строятся из них с использованием && и ||?

Можем ли мы считать, что все целочисленные переменные независимы?

В этих условиях я бы предположил, что это можно проверить алгоритмически. Я бы поместил все допустимые диапазоны для каждой переменной в структуру данных и проверил бы пересечения.

РЕДАКТИРОВАТЬ: так как это, кажется, не так, лучшее решение, вероятно, будет группировать различные типы условий, чтобы условия в каждой группе можно было статически оценить друг против друга. Тип условий, предполагаемых мной из вашего первого описания, будет только одной из этих групп.