Can all boolean expressions be written sequentially?

Question

I work with some tools, and the only way to determine if this transaction is successful is to go through various checks. However, it is limited in that it can only perform one check at a time, and it should be consistent. Everything should be calculated from left to right.

For instance,

A || C && D 

First it will be calculated using A || C A || C , and then the result will be AND using D

It gets tougher with parentheses. I cannot calculate such an expression since B || C needs to be calculated first. I cannot work with any order of operations;

 A && ( B || C) 

I think I worked on this sequential logical expression,

 C || B && A 

Where C || B C || B , then this result is AND 'd with A

Can all logical expressions work successfully in a sequential boolean expression? (As in my example)

Answer 1

The answer is negative:

Consider A || B && C || D A || B && C || D A || B && C || D , which has a truth table:

 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 

If one could consistently evaluate, there would have to be the last expression, which would be one of two cases:

Case 1:

X || Y X || Y such that Y is one of A,B,C,D , and X is any consecutive Boolean expression.

Now, since in A,B,C,D there is no variable where the whole expression is true when this variable is true, none of:

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

may be the last operation in the expression (for any X).

Case 2:

X && Y : such that Y is one of A,B,C,D , and X is any consecutive Boolean expression.

Now, since in A,B,C,D there is no variable where the whole expression is false when this variable is false, none of:

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

may be the last operation in the expression (for any X).

Therefore, you cannot write (A || B) && (C || D) in this way.

---

The reason you can do this for some expressions, for example: A && ( B || C) becoming C || B && A C || B && A , is that this expression can be constructed recursively from expressions that have one of the two properties above:

IE

The truth table for 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 

What we can quickly see is the property that it is false when A is 0. Thus, our expression can be X && A

Then we select A from the truth table and look only at the lines where A is 1, this is the original:

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

Who has the property that it is true when B is 1 (or C, we can choose here). Thus, we can write the expression as

X || B X || B , and the whole expression becomes X || B && A X || B && A

Then we again reduce the table to the part where B is 0, and we get:

 C 0 | 0 1 | 1 

X is just C. Thus, the final expression is C || B && A C || B && A

Answer 2

It is a problem to rewrite the expression so that no parentheses appear on the right. Logical AND (& and;) and OR (& or;) are commutative:

• A & and; B = B & and; A
• A & or; B = B & or; A

So, you can rewrite any expression of the form "X a (Y)" as "(Y) a X":

• A & and; (B & u; C) = (A & u; B) &; WITH
• A & and; (B & or; C) = (B & or; C) <A
• A & or; (B & a; C) = (B & a; C) or; A
• A & or; (B & or; C) = (B & or; C) or; A

They are also subject to the following laws:

• (A & B) or; (A & and; C)
  = A & u; (B & or; C)
  = (B & or; C) &; A
• (A & or; B) &; (A & or; C)
  = A & or; (B & and; C)
  = (B & u; C) or; A

So many Boolean expressions can be rewritten without parentheses to the right. But, as a counter and shy, for example, there is no way to rewrite an expression such as (A & and; B) & or; (C & and D) if A & ne; C, due to the lack of common factors.

Answer 3

Can't you do it:

 (( A || C ) && D) 

and for your second example:

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

Will this work for you?

Hope this helps ...

Answer 4

You will run into problems if you need to do something like (A || B) && (C || D) , if you cannot save intermediate values ​​for future use.

If you are allowed to create more than one chain and try all of them until none of them passes, or all of them work (therefore, each chain is effectively OR ed with the following), then I should think that you can handle any combination. The above example will become (where each row is a separate request):

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

However, for a very complex test, this can easily get out of hand!