The logical opposite trick
I know things have been pretty quiet around her lately. I’ve just moved to NY from San Francisco and I wanted to get back to writing with a little logic trick I picked up during my time as a Philosophy major in college.
Consider the following question:
We know how to say ‘If both A and B are true’ (A && B) but how would you reverse it and ask ‘If both A and B are false?
If you said, or thought ‘!(A && B)’ you’d be wrong. In this case, if either a or b is true your statement will resolve to ‘true’. While (!A && !B) is a correct answer, there’s a cleaner way to write it: ‘!(A || B)’.
This reveals, albeit poorly with short statements, an easy trick to reversing the ‘trueness’ of a statement. Put a ! outside the statement and then exchange all ‘ands’ and ‘ors’. It works even in more complex logical statements. Example:
if(A && (B || C)) reversed is if( !(A || (B && C)) ) Go ahead, run the matrix, I’ll wait…
This trick also works if you want to remove all the ‘!’s from a statement. if(!A && !B || !C) is actually equivalent to if( !(A || B && C) )
How, you might ask, could this possibly be useful? I’ve used it several times when an if statement or function returning a boolean becomes hopelessly complex. I’ve also used it when, due to code changes, it becomes faster to check for a few disqualifying cases rather than verifying a large number of qualifying statements. Further, sometimes it’s just easier to read a bunch of statements that are true then parse a bunch that are not.
Lastly, if I have to construct a logical statement for, say, when something shouldn’t be cached I’ll often write out all the logical cases when should and then use this trick to reverse them.
This may be obvious to the hard-core, but it’s something I’ve taught to several co-workers over the years. Happy hacking! Let me know if you’re in the NYC area.
Update: Thanks to a few of you for pointing out that these are called: De Morgan’s Laws
August 4th, 2010 at 10:41 am
Some fancier IDEs like Jetbrains’ IDEA will do these kinds of translations as automatic refactorings for you.
August 4th, 2010 at 10:43 am
De Morgan’s laws are fun, but caution is to be employed.
If (A&&(B||C)) should result in a cache operation, !(A||(B&&C)) is not the inverse of that. You will get extra writes on B&&C as well as any true A.
August 4th, 2010 at 10:45 am
Indeed
Here’s the more formal version: http://en.wikipedia.org/wiki/De_Morgan%27s_laws
August 4th, 2010 at 11:09 am
You know, while we’re on this subject, there’s a good programmatic reason to prefer the use of AND comparisons, because as soon as any part of that operator fails, the rest of the logic is not parsed.
In addition to being faster (if you have an expensive call on the second half), you can avoid system-level problems if the first half of the AND validates that the second half of the AND can be executed without error.
For example:
if (exists(Object) && Object.IsGreen) …
While a simplified example, if one starts negating that kind of logic, it gets either expensive or bomb-y.
I guess that’s why they pay you programmer-types the big bucks.