Ok, so I realise there is a wikipedia article on the whole life of De Morgan but this article is intended to summarise the details and use of his work on boolean logic, specifically for use in programming and circuits. De Morgans law can prove genuinely usefull and is capable of increasing the efficiency or your code in many circumstances.
So who is this guy?
Augustus De Morgan was born in India in June 1806 before moving to London, UK where he passed away in March 1871. De Morgan had a passion for mathematics and problem solving and is responsible for many mathmatic theories we now take for granted such as….
> The Distributive Law (or the expansion of brackets)
Whereby a(b+2) = ab + 2a
> The Commutative Law
Wherby a+b = b+a, and a x b = b x a
> And most famously…De Morgan’s Law
De Morgan’s Law
A law which explains how boolean statements and conditions can be changed and manipulated, without effecting their outcomes. To show why this might be usefull see the example below (two equivalent boolean expressions in c++ where a and b represent boolean variables).
- a && b
- !(!a || !b)
Thats right, although looking nothing alike, they will always provide the same answer!
Here are the truth tables for each expression
The truth tables clearly show that although one of the expressions looks more daunting than its partner, they are both equivalent and produce exactly the same output with all possible combinations of a and b.
As you can see in the truth tables, aswell as one of the expressions being longer than the other (in characters), there are also more steps involved in coming to the outcome, 3 compared to 6 (as represented by collumns in the truth tables), in theory making one twice as efficient as its equivalent. During compilation, in some situations these un-necessary long expressions written in c++ (or similar) will be transfered to their simpler origins during the translation to Assembly, but in more complicated situations, the compiler will simply ignore your badly thought out, inefficient expression and translate them just as inefficiently to assembly (the code which gets executed by your processor).
The method is easier than you might imagine. In all cases follow the following three steps…
- Switch the operator
Here we switch the AND to an OR or swap the OR for an AND
- Invert Both Sides of the Operator
- Invert the whole operation
A Graphical representation using AND and OR Gates…
And for those of you who aren’t fans of reading, a video I found on youTube made by students studying De Morgan’s Law.