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

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

• Разбор логического выражения, такого как «A && (B || C)», в классическое дерево синтаксического анализа, которое представляет выражение, в котором каждый узел в дереве является либо переменной, либо логической операцией, либо «&&», «| | ", или"! " (НЕ) с двумя дочерними элементами, являющимися его операндами. Это классическое дерево разбора. Множество примеров того, как это сделать, можно найти в Google.

• Перевод моей схемы в реальный код C ++. Это тоже зависит от вас, но я думаю, что реализация должна быть довольно очевидной, если вы осознаете общий подход.

Чтобы решить эту проблему, я буду использовать двухэтапный подход.

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

2. На втором этапе я исключу из списка всех возможных наборов те наборы, которые логически невозможны. Это может показаться запутанным, поэтому сначала я объясню вторую фазу.

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

typedef std::set<std::pair<std::string, bool>> values_t;

Здесь std::pair<std::string, bool> представляет переменную с именем std::string, имеющую это bool значение. Например:

{"a", true}

Означает, что значение переменной «a» имеет значение true. Отсюда следует, что этот std::set представляет собой набор переменных и их соответствующих значений.

Все эти потенциальные решения будут:

typedef std::list<values_t> all_values_t;

Вот как мы представим список всех комбинаций значений всех переменных, которые производят результат либо true, либо false. Вы можете использовать std::vector вместо std::list, это не имеет особого значения.

Теперь обратите внимание, что values_t может иметь и то, и другое:

 {"a", true}

и

 {"a", false}

в комплекте. Это означает, что для того, чтобы выражение оценивалось как true или false, «a» должно быть одновременно истинным и ложным.

Но это, очевидно, логически невозможно. Итак, на этапе 2 этого решения вам нужно будет просто пройти через все отдельные values_t в all_values_t и удалить «невозможное» values_t, которое содержит как true, так и false для некоторой переменной. Способ сделать это должен показаться довольно очевидным, и я не буду тратить время на его описание, но этап 2 должен быть простым после завершения этапа 1.

Для этапа 1 наша цель - разработать функцию, которая примерно так описана:

all_values_t phase1(expression_t expr, bool goal);

expr - это проанализированное представление вашего логического выражения в виде дерева синтаксического анализа (как я упоминал в начале, выполнение этой части будет зависеть от вас). goal - это то, как вы хотите, чтобы проанализированное выражение оценивалось следующим образом: phase1() возвращает все возможные all_values_t, для которых expr оценивается как true или false, как указано в "цели". Вы, очевидно, вызовете phase1(), передав true как «цель» вашего ответа, потому что это то, что вы хотите выяснить. Но phase1() будет вызывать себя рекурсивно, с true или false «целью», чтобы творить чудеса.

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

Хорошо, теперь вы понимаете концепцию. Если да, то теперь вы должны согласиться со мной, что phase1() уже сделано. Оно работает! Доказательство по индукции начинается с предположения, что phase1() делает то, что должно делать. phase1() будет делать рекурсивные вызовы самому себе, и, поскольку phase1() возвращает правильный результат, phase1() может просто полагаться на себя, чтобы во всем разобраться. Видишь, как это просто?

У phase1() действительно есть одна "простая" задача:

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

• Верните соответствующий all_values_t, исходя из этого.

Вот и все. Мы воспользуемся обеими возможностями по очереди.

1. Узел верхнего уровня - это переменная.

Итак, если ваше выражение - это просто переменная, и вы хотите, чтобы выражение возвращало goal, тогда:

values_t v{ {name, goal} };

Есть только один возможный способ для выражения оценивать goal: очевидная простая задача: переменная и goal ее значение.

И есть только одно возможное решение. Других альтернатив нет:

all_values_t res;

res.push_back(v);

return res;

Другая возможность состоит в том, что узел верхнего уровня в выражении является одной из логических операций: and, or, or not.

Опять же, мы разделим и победим это и займемся каждым, по отдельности.

Допустим, это «нет». Что же нам тогда делать? Это должно быть легко:

return phase1(child1, !goal);

Просто вызовите phase1() рекурсивно, передав дочерний узел выражения «not» с логическим инвертированием goal. Итак, если ваш goal был истинным, используйте phase1(), чтобы вернуться с тем, какие значения для подвыражения «не» являются ложными, и наоборот. Помните, что доказательство по индукции предполагает, что phase1() работает так, как рекламируется, поэтому вы можете положиться на него, чтобы получить правильный ответ для подвыражения.

Теперь должно стать очевидно, как работает остальная часть phase1(). Осталось только две возможности: логическая операция «И» и «ИЛИ».

Для операции «and» мы отдельно рассмотрим, должна ли «цель» операции «and» быть true или false.

Если goal истинно, вы должны использовать phase1(), чтобы получить all_values_t, чтобы оба подвыражения были истинными:

all_values_t left_result=phase1(child1, true);

all_values_t right_result=phase1(child2, true);

Затем просто объедините два результата вместе. Напомним, что all_values_t - это список всех возможных значений. Каждое значение в all_values_t (которое может быть пустым списком / вектором) представляет одно возможное решение. И левое, и правое подвыражения должны быть логически объединены, но любое возможное решение из left_result может сочетаться с любым right_result. Любое потенциальное решение с истинным левым подвыражением может (и должно) соответствовать любому потенциальному решению с истинным правым подвыражением.

Таким образом, all_values_t, который необходимо вернуть, в данном случае получается путем выполнения декартова произведения между left_result и right_result. То есть: взять первое значение, первое values_t std::set в left_result, затем добавить к этому набору первый right_result std::set, затем первый left_result со вторым right_result и так далее; затем второй left_result с первым right_result, затем второй right_result и так далее. Каждая из этих комбинаций push_back() вставляется в all_values_t, который возвращается из этого вызова в phase1 ().

Но ваш goal должен иметь выражение «и», возвращающее false, вместо этого вам просто нужно сделать вариант этого три раза. Первый раз позвонив phase1(child1, false) с phase1(child2, false); затем phase1(child1, true) с phase1(child2, false); и, наконец, phase1(child1, false) и phase1(child2, true). Либо child1, либо child2, либо оба должны оцениваться как false.

Итак, мы позаботимся об операции «И».

Последняя и последняя возможность для phase1() иметь дело - это логическая операция или. Теперь вы сможете понять, как это сделать самостоятельно, но я кратко резюмирую это:

Если goal ложно, вы должны вызвать phase1(child1, false) с phase1(child2, false), а затем объединить оба результата вместе, как декартово произведение. Если goal истинно, вы сделаете три набора рекурсивных вызовов для трех других возможностей и объедините все вместе.

Готово. Для phase1() больше нечего делать, и мы завершили доказательство по индукции.

Ну, я немного соврал. Вам также нужно будет выполнить небольшую «Фазу 3». Напомним, что в «Фазе 2» мы исключили все невозможные решения. Что ж, возможно, что в результате всего этого в окончательном списке возможных решений один и тот же values_t будет встречаться более одного раза в all_values_t, так что вам просто нужно вывести его.

P.S. Также можно избежать дискретного этапа 2, выполняя его «на лету» как часть этапа 1. Этот вариант также станет вашим домашним заданием.