- DelphiTools - https://www.delphitools.info -

Cleanup your ugly Boolean expressions with De Morgan’s laws

Posted By Eric Grange On In Tips | Comments Disabled

This is a simple trick that can be handy to cleanup or simplify Boolean expressions, and is always good to have in your code-writing toolchest: De Morgan’s laws [1].

These two laws allow to apply a negation to an and or or expression:

So basically when you distribute a not, an or becomes an and, and vice-versa.

Also keep in mind some simple comparison negation rules:

Exemple: testing if a TRect overlaps another TRect

Now, I don’t know how your mind works, but in my case the above question is initially non-intuitive for me to solve, while its negation, ie. testing if a TRect doesn’t overlap another is simple. The R1 rectangle doesn’t overlap R2 if it’s fully to its left or right, or fully above or below:

notOverlapping :=
       (R1.Right <= R2.Left)  // right edge of R1 is to the left edge of R2
    or (R1.Left >= R2.Right)  // left edge of R1 is right of right edge of R2
    or (R1.Bottom <= R2.Top)  // bottom edge of R1 is above top edge of R2
    or (R1.Top >= R2.Bottom); // top edge of R1 is below bottom edge of R2

which means the overlapping test is

overlapping := not (   (R1.Right <= R2.Left) or (R1.Bottom <= R2.Top)
                    or (R1.Left >= R2.Right) or (R1.Top >= R2.Bottom));

Let’s apply De Morgan’s law:

overlapping := (    (not (R1.Right <= R2.Left)) and (not (R1.Left >= R2.Right))
                and (not (R1.Bottom <= R2.Top)) and (not (R1.Top >= R2.Bottom));

And then apply the negations to the comparison:

overlapping :=     (R1.Right > R2.Left) and (R1.Left < R2.Right)
               and (R1.Bottom > R2.Top) and (R1.Top < R2.Bottom);

Which gives another interpretation to rectangle overlap.

Of course this works both way, if the last form was used but you can’t figure heads or tails, you could apply Morgan’s law in reverse and go back to the first form, which might make things easier to understand.

Morgan’s Laws and the Delphi compiler

The Delphi compiler knows about Morgan’s laws and will apply them automatically when “not” is applied to “and“/”or“, and so will compile the first form in the same way as the transformed from below.

The compiler does it to eliminates the need to compute a sub-expression and process the “not” operator and perform Boolean shortcut evaluation.

Conclusion: feel free to use Morgan’s Law to cleanup your ugly/obscure Boolean expressions, an extra “not” in front is free.

Further Boolean Algebra

You can also factorize Boolean expression, and apply more simplification rules (cf. Linear Algebra [2]), even though the above are those most commonly encountered when writing code.

Below are a few other less commonly encountered simplifications which can be helpful, as the compiler won’t perform them, and they can be occasionally used to drastically clean up existing code: