Thomas Sampson

De Morgan’s Law

10 Comments

Augustus De Morgan

Introduction

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).

  1. a && b
  2. !(!a || !b)

Thats right, although looking nothing alike, they will always provide the same answer!

Prove It!!!…

Here are the truth tables for each expression

Truth Tables (click to enlarge)

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.

Why Bother?

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

The method is easier than you might imagine. In all cases follow the following three steps…

  1. Switch the operator
    Here we switch the AND to an OR or swap the OR for an AND
  2. Invert Both Sides of the Operator
  3. Invert the whole operation

A Graphical representation using AND and OR Gates…

visual.jpg
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.

Advertisements

Author: tomtech999

I have recently graduated with a 1st class degree in MComp Games Software Development at Sheffield Hallam University, focusing primarily on application development in C++, with experience in graphics programming, scripting languages, DVCS/VCS and web technology. In my spare time I enjoy Drumming, Reading and Snowboarding!

10 thoughts on “De Morgan’s Law

  1. Hey Tom,

    Sorry to say I haven’t frequented your blog lately, I promise I’ll add it to my feeds and check it out more often!

    This was a very interesting article! Granted, I lost you after you stated De Morgan’s laws. Good point you made about efficiency, althoygh I only followed as far as algbraic efficiency in the form of factorisation 😛

    Anyway, keep it up! I’ll be here more often!

    How did you get your Flickr photos down the side? Are they definied images or randomly generated? If it’s the latter then I’m very very interested in how you did it!

    Take care mate, talk soon.

    Ben

  2. Hey Ben!! Thanks for the response. I use WordPress which allows you to paste your flickr photo url, from which it makes the wall of photos on my blog. However I don’t think this is exclusive to wordpress, head to the flickr site and I think you can make an emeddable ‘badge’ for your blog. Speak soon

    Tom

  3. Cheers for the heads up about the Flickr Badge! I haven’t got round to adding it to my blog yet (I’m going for a redesign when I get chance) but I used it on here: http://www.woodseatsventureunit.com (let me know what you think of the site)

    I added your blog to my feeds so I’ll be on here whenever you post something new! 😀

    Oh and thanks for your suggestion about my relationships with my Access Project – I was hesitant at first because I’d put so much work into it, and for other reasons, but the points FOR scrapping all the crap I’d done overbalanced the points AGAINST, so I went ahead and now everything’s soooo much simpler and more efficient! I’ll show you when the system’s finished, it’s pretty cool and has some nice features and functions.

    I’ll have you on hand for when it needs testing! Hehe, I know how much you love Access!

    Hope to catch you on the bus again soon.

    Ben

  4. cool article…thanks tom

  5. Hi,

    Thanks for this interesting article!
    Can you help me with this one..
    how is (A+BC) = (A + B)(A + C) I have been struggling with this for some time now..

    Thanks,
    Amit

  6. hey.. I got it..
    (A+BC) = (A + B)(A + C)

    RHS:
    AA+AC+AB+BC
    A (1+C+B) + BC
    A . 1 + BC
    A+BC

    hence proved..
    🙂

  7. thedictum,

    If what you’re doing is algebraic maths then I fail to see how LHS = RHS, if what you’re doing is some sort of computer language I am unfamiliar with then maybe you’re right and I apologise.

    If you’re doing maths, then I see a fault on your second line of working; you start with A^2 + AC + AB + BC and go straight to A(1 + C + B) which is not correct. You are taking a factor of A out of the first three terms, but for the first term of A squared, taking a factor of A out leaves A, not 1.

    Ben

  8. q. from boolean algebra(computer science)

    ___
    (a+b)*(a*b)=?

  9. (a+b).((a.b)wholebar)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s