Могут ли все логические выражения быть записаны последовательно?

Question

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

Например,

A || C && D

Сначала будет вычислено A || C, а затем результат будет AND обработан D.

Сложнее с круглыми скобками.Я не могу вычислить выражение как это, так как B ||C должен быть вычислен в первую очередь.Я не могу работать с каким-либо порядком операций;

A && ( B || C)

Я думаю, что я дошел до этого последовательного логического выражения,

C || B && A

Где сначала вычисляется C || B, затемэтот результат равен AND 'd с A

Можно ли все логические выражения успешно преобразовать в последовательное логическое выражение?(Как пример, который я имею)

Answer 1

Ответ «нет»:

Рассмотрим A || B && C || D, в котором есть таблица истинности:

A | B | C | D |
0 | 0 | 0 | 0 | 0
0 | 0 | 0 | 1 | 0
0 | 0 | 1 | 0 | 0
0 | 0 | 1 | 1 | 0
0 | 1 | 0 | 0 | 0
0 | 1 | 0 | 1 | 1
0 | 1 | 1 | 0 | 1
0 | 1 | 1 | 1 | 1
1 | 0 | 0 | 0 | 0
1 | 0 | 0 | 1 | 1
1 | 0 | 1 | 0 | 1
1 | 0 | 1 | 1 | 1
1 | 1 | 0 | 0 | 0
1 | 1 | 0 | 1 | 1
1 | 1 | 1 | 0 | 1
1 | 1 | 1 | 1 | 1

Если бы можно было выполнить последовательную оценку, то должно быть последнее выражение, которое быбыть одним из двух случаев:

Случай 1:

X || Y такой, что Y является одним из A,B,C,D, а X является любым последовательным логическим выражением.

Теперь, поскольку в A,B,C,D нет переменной, где все выражение истинно, когда эта переменная истинна, ни одно из:

X || A
X || B
X || C
X || D

не может быть последней операцией в выражении (для любого X).

Случай 2:

X && Y: такой, что Y является одним из A,B,C,D, а X является любым последовательным логическим выражением.

Теперь, поскольку в A,B,C,D нет переменной, где все выражение ложно, когда эта переменная ложна, ни одно из:

X && A
X && B
X && C
X && D

не может быть последней операцией в выражении (для любого X).

Поэтому вы не можете написать (A || B) && (C || D) таким образом.

---

Причина, по которой вы можете сделать это для некоторых выражений, таких как: A && ( B || C) становится C || B && A, заключается в том, чтовыражение может быть построено рекурсивно из выражений, которые имеют одно из двух указанных выше свойств:

IE.

Таблица истинности для A && ( B || C):

A | B | C |
0 | 0 | 0 | 0
0 | 0 | 1 | 0
0 | 1 | 0 | 0
0 | 1 | 1 | 0
1 | 0 | 0 | 0
1 | 0 | 1 | 1
1 | 1 | 0 | 1
1 | 1 | 1 | 1

, котораямы можем быстро увидеть, что имеет свойство ложно всякий раз, когда A равно 0. Поэтому наше выражение может быть X && A.

Затем мы вынимаем A из таблицы истинности и смотрим только на те строки, где A равно 1это оригинал:

B | C
0 | 0 | 0
0 | 1 | 1
1 | 0 | 1
1 | 1 | 1

, который обладает свойством True, когда B равен 1 (или C, мы можем выбрать здесь).Таким образом, мы можем записать выражение как

X || B, и все выражение станет X || B && A

Затем мы снова уменьшим таблицу до части, где B было 0, и получим:

C
0 | 0
1 | 1

X - это просто C. Итак, окончательное выражение - C || B && A

Answer 2

Это проблема переписывания выражения, чтобы справа не было скобок.Логическое И (∧) и ИЛИ (∨) оба коммутативны:

• A ∧ B = B ∧ A
• A ∨ B = B ∨ A

Таким образом, вы можете переписать любое выражение вида «X a (Y)» как «(Y) a X»:

• A ∧ (B ∧ C) = (A ∧ B) ∧C
• A ∧ (B ∨ C) = (B ∨ C) ∧ A
• A ∨ (B ∧ C) = (B ∧ C) ∨ A
• A∨ (B ∨ C) = (B ∨ C) ∨ A

Они также являются распределительными по следующим законам:

• (A ∧ B) ∨ (A∧ C)
  = A ∧ (B ∨ C)
  = (B ∨ C) ∧ A
• (A ∨ B) ∧ (A ∨ C)
  = A ∨ (B∧ C)
  = (B ∧ C) ∨ A

Так что много булевых выражений можно переписать без скобок справа.Но, как контрпример, нет способа переписать выражение, такое как (A ∧ B) ∨ (C ∧ D), если A ≠ C, из-за отсутствия общих факторов.

Answer 3

Вы столкнетесь с проблемами, если вам понадобится что-то вроде (A || B) && (C || D), если вы не можете сохранить промежуточные значения для дальнейшего использования.

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

(A && C) ||
(A && D) ||
(B && C) ||
(B && D)

Однако, для очень сложной проверки это может легко выйти из-под контроля!

Answer 4

Не могли бы вы просто сделать это:

(( A || C ) && D)

и для вашего второго примера:

((( A && C ) || B ) && A )

Будет ли это работать для вас?

Надеюсь, что поможет...