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.
These two laws allow to apply a negation to an and or or expression:
- (not A) and (not B) <=> not (A or B)
- (not A) or (not B) <=> not (A and B)
So basically when you distribute a not, an or becomes an and, and vice-versa.
Also keep in mind some simple comparison negation rules:
- not (A < B) <=> (A >= B)
- not (A > B) <=> (A <= B)
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), 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:
- A or (A and B) <=> A
- A and (A or B) <=> A
- A or (not A and B) <=> A or B
- A and (not A or B) <=> A and B
- (A and B) or (A and not B) <=> A
- (A or B) and (A or not B) <=> A
You cleaned the stylesheet, I think. Fits perfect.
@Michael
Ok, the formatting returned.
So obvious, yet often overlooked. Nice post!
Well, when I see code like :
if Something = False then…
or:
if not(Something = True) then…
I guess Morgan’s Law are above some heads. Sigh!
No kidding, I’ve seen this and even the:
if Something = True then
Your subject also overlapps with the “Full Boolean evaluation” compiler tip.
because when you finally establish that:
overlapping := (R1.Right > R2.Left) and (R1.Left R2.Top) and (R1.Top < R2.Bottom);
Then you basically force a full boolean evaluation, while a standard "if then if then if then" would exit the branch at the first false assumptiom.
Basically I just mean that your "and" chain will be slower than a "if then" chain.
This would make such a great article on PGD! Heck Pascal Gamer Magazine too!
Yes, and full Boolean evaluation breaks a lot of code IME. I’ve also no idea what upsides it can have, so this an option probably best left forgotten 🙂
Feel free to reuse!
@Eric
It has it’s uses, and recently caused a bug in one of our programs:
// Run several Methods that return a bool. Do seomthing if at least one of them was true, yet perform all of them:
procedure Foo;
var
i: Integer;
doSomething: Boolean;
begin
doSomething := false;
for i := Low(MyMethods) to High(MyMethods) do
doSomething := doSomething or MyMethods[i];
if doSomething then
JustDoIt(now);
end;
This was in context of a system that displays data from a DB when changed, distributed via sockets in a thread. If at least one change had an impact on the visuals, a PostMessage() had to be done to cause synchronous changing of the controls. With short evaluation, only a few of the update notifications were considered, and the screens did not always show what the database said.
Took some while before I noticed that short eval was my problem here.
On the other hand, things like
if Assigned(Bar) and (Bar.SomeMethod(Foo)) then …
of course relies on shot eval to happen.
@Klaus
Boolean “And” is short-circuiting by default, so an “if then” chain is unnecessary.
One addition: Boolean expressions could be simplified using Karnaugh maps. This is especially useful for Boolean expressions containing more than just two variables.
Nice post. I’ve translated it to Russian here
http://cooldelphi.blogspot.com/2013/01/blog-post_18.html
I’d also like to mention: along with compilers use this boolean stuff to simplify expressions, protectors or obfuscators use the same to make it harder to read.
@Yanniel
Only if you have something critical that the compiler can’t simplify on its own. The output of such simplifications can look rather incomprehensible to regular humans 🙂
@Eric
You could probably put a comment in the code saying: “simplified using Karnaugh maps”. As I see it, a non-simplified Boolean expression could be incomprehensive (and nasty) as well.