logical expressions simplification with short circuit evaluation

M

mingze zhang

Hi all,

We all know that logical expressions can be manipulated or simplified,
for example,

1. (x && y) || (x && z) is equivalent to x && (y || z)
2. x && (x || y) is equivalent to x
3. (x || y) && (x || z) is equivalent to x || (y && z)

4. (y && x) || (z && x) is equivalent to (y || z) && x
5. (x || y) && x is equivalent to x
6. (y || x) && (z || x) is equivalent to (y && z) || x

But this simplification is apparently not all valid if short-circuit
evaluation is considered. In the above examples, Cases 1-3 are valid,
but 4-6 are not (assume x, y, z may have side effects).

So here comes my question, is there a general guideline to simplify a
very complicated logical expression (under short-circuit equivalence)
when some of the logic expressions have side effect and some do not.

I know some compilers may do this kind of simplification. I just want
to know whether there are some tutorial or general procedures so that
I can quickly catch up. I tried to search on Google but with no good
luck.

Thanks in advance.
Vincent
 
M

mingze zhang

Hi all,

We all know that logical expressions can be manipulated or simplified,
for example,

 1. (x && y) || (x && z) is equivalent to x && (y || z)
 2. x && (x || y) is equivalent to x
 3. (x || y) && (x || z) is equivalent to x || (y && z)

 4. (y && x) || (z && x) is equivalent to (y || z) && x
 5. (x || y) && x is equivalent to x
 6. (y || x) && (z || x) is equivalent to (y && z) || x

But this simplification is apparently not all valid if short-circuit
evaluation is considered. In the above examples, Cases 1-3 are valid,
but 4-6 are not (assume x, y, z may have side effects).

So here comes my question, is there a general guideline to simplify a
very complicated logical expression (under short-circuit equivalence)
when some of the logic expressions have side effect and some do not.

I know some compilers may do this kind of simplification. I just want
to know whether there are some tutorial or general procedures so that
I can quickly catch up. I tried to search on Google but with no good
luck.

Thanks in advance.
Vincent

I was wrong. All 1-6 cannot be simplified.
 
G

Gene

Hi all,

We all know that logical expressions can be manipulated or simplified,
for example,

 1. (x && y) || (x && z) is equivalent to x && (y || z)
 2. x && (x || y) is equivalent to x
 3. (x || y) && (x || z) is equivalent to x || (y && z)

 4. (y && x) || (z && x) is equivalent to (y || z) && x
 5. (x || y) && x is equivalent to x
 6. (y || x) && (z || x) is equivalent to (y && z) || x

But this simplification is apparently not all valid if short-circuit
evaluation is considered. In the above examples, Cases 1-3 are valid,
but 4-6 are not (assume x, y, z may have side effects).

So here comes my question, is there a general guideline to simplify a
very complicated logical expression (under short-circuit equivalence)
when some of the logic expressions have side effect and some do not.

I know some compilers may do this kind of simplification. I just want
to know whether there are some tutorial or general procedures so that
I can quickly catch up. I tried to search on Google but with no good
luck.

Thanks in advance.
Vincent

By "not valid" I assume you mean that the transformed expressions may
evaluate predicates a different number of times, allowing side effects
of functions embedded in the predicates to differ. This is true.

To avoid it, you can translate short circuit expressions as
conditionals:

x || y becomes x != 0 ? 1 : y != 0 ? 1 : 0
x && y becomes x != 0 ? y != 0 ? 1 : 0 : 0

and then reason about these to get new identities for simplification.
 
Joined
Oct 22, 2011
Messages
1
Reaction score
0
The simplify expression they logically manipulative and simplified with logical compair with other component which gives exact value in coordination in //X is equal or not that's find by multiplication of X and Y that's coordinate value compair with given term in question in this method x&&y=x&&z which are logically devloped
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,731
Messages
2,569,432
Members
44,832
Latest member
GlennSmall

Latest Threads

Top