Simplifying if statement logic

Question

I have seperated out a test to determine if two schedule items overlap because of the unreadability of it.

Is there any application to assist in simplifying a logic statement?

Example: (originally a faulty example, but exposes reasons I request this)

if (x < y && y < z && x < z)  

could be reduced to

if (x < y && y < z)

My code is:

return (shift.Start <= shift2.Start && shift.End >= shift2.End) || (shift2.Start <= shift.Start && shift2.End >= shift.Start)

I would love to make that simpler, and I believe it's possible, just unsure how.

Seeing as this is really language agnostic, even converting to a different script to find possibilities would be nice, no need for it to be in C# for instance.

Answer 1

Be very, very careful with these kinds of changes. They might seem straightforward at inital glance, and boolean logic (and DeMorgan's laws) are not too hard to grasp, but there are often potential gotchas when you look at individual cases:

For example: if (x < y && y < z) could be simplified to if (x < z)

This is not correct, if (x < z), y might still be greater than z. That state would not pass your original tests.

Answer 2

Although x < y && y < z implies x < z (< is transitive), the reverse is not true so the expressions are not equivalent. Indeed if y were defined as, say, Integer y = null, then the former may even cause an NPE in Java, or UNKNOWN in SQL.

Answer 3

You need to be really careful when doing this... the example you gave, for example, simply isn't true... if x=1, y=2, and z=2, then x < y = true, and x < z = true, but y < z = false. For this type of reasoning, you really want to go for code readability in these circumstances and not worry about the most efficient code that you can get.

Answer 4

Not only is this dangerous, but it often leads to harder to maintain code. Boolean logic is easier to understand when broken down into specific steps. Condensing the logic will often lead to harder to understand logic.

i.e. in your example, why are we checking if x < z , when what we really want to know is x < y && y < z?

The simplest solution is often the best one. Condensing your logic into 'cooler' but less readable code is not good in the long run.

Answer 5

Sometimes you can wrap statements such as

shift.Start <= shift2.Start && shift.End >= shift2.End

Into a boolean function to make it more readable such as:

Function ShiftWithinValidRange (terrible name here, but you get the idea)
{
Return (shift.Start <= shift2.Start && shift.End >= shift2.End);
}

Answer 6

When it comes to complex logic statements, you're usually best off with formatting your code in a readable manner than attempting some premature optimization (root of all evil, etc.)

For example:

return (shift.Start <= shift2.Start && shift.End >= shift2.End) || (shift2.Start <= shift.StartTime && shift2.End >= shift.Start)

Can, for readability and maintainability, be refactored to:

bool bRetVal = false;
bRetVal = (    (   (shift.Start <= shift2.Start)
                && (shift.End >= shift2.End))
            || (   (shift2.Start <= shift.StartTime)
                && (shift2.End >= shift.Start)))
return bRetVal;

Most places maintain a coding standard that defines something like the above for large logic blocks. I'd much rather maintain a few extra lines of code that can be read and understood than a one line monstrosity.

Answer 7

Assuming Start and StartTime are actually supposed to be the same field, your condition boils down to

(a <= b && c >= d) || (b <= a && d >= c)

We can turn this into

(a <= b && d <= c) || (b <= a && c <= d)

but this still doesn't look like it simplifies much.

Answer 8

I don't have a general solution for you, but if I use Lisp syntax it looks a lot simpler to me:

(and (< x y)
     (< y z)
     (< x z))

Then notice that the first two clauses:

(and (< x y)
     (< y z))

can be combined into:

(and (< x y z))

So the full expression now looks like:

(and (< x y z)
     (< x z))

Now it's obvious that the second one is redundant, so it's down to:

(and (< x y z))

or simply:

(< x y z)

which in C-syntax is:

(x < y && y < z)

Answer 9

Kill the duplicate logic and you'll kill two birds with one stone. You'll get DRY, and you'll get a function name (the rich man's comment):

class Shift:
  def encompasses(other_shift)
    self.start <= other_shift.start && self.end >= other_shift.end

...

return shift1.encompasses(shift2) || shift2.encompasses(shift1)

Answer 10

I think Wayne Conrad's answer is the right one, but for entertainment purposes only, here's another way to say it (I think):

(long) shift.Start.CompareTo(shift2.Start) * (long) shift.End.CompareTo(shift2.End) <= 0

Is this actually faster? I don't know. It's certainly harder to read.

Answer 11

Is there any application to assist in simplifying a logic statement?

I didn't see anyone addressing this part of the question, So I'll take a stab and see what discussion occurs.

There are techniques for working with boolean logic. Back in my college days (BSEE) we used Karnaugh maps. Basically, you can take a very complex arbitrary truth table and determine a correct and optimized logical expression. We used this to reduce the number of logic gates in a circuit, which is analogous to simplifying a complex if statement.

Pros:

• You can implement/optimize a very complex and arbitrary truth table relatively easily.

Cons:

• The resulting logic usually bore little resemblance to the intent of the truth table. As others have suggested, this is "unreadable".
• A change to a single cell of the truth table would often result in a completely different expression. A simple design tweak becomes a re-write, so it's unmaintainable.
• Non-optimized logic is a lot cheaper than it used to be, while the design costs are the same.

Ultimately, the most critical thing is the correctness of the truth table/logic expression. An error means your program won't work right. No application or design technique will help if you don't properly understand the definition of the logic that needs to be implemented.

In my opinion, few real-world problems are sufficiently complex to truly benefit from this type of technique, but it does exist.