When one is introduced to Boolean algebra in high school it is easy to assume that it is quite simple. Things are either true or false? Got it. Let’s move on.
It turns out, however, that it gets a tad more complicated than that, primarily because computers can only do Boolean algebra (processing an electronic cycle or the lack thereof) and everything must be built from that. What results is that you get these really interesting ideas such as K-Maps, which require understanding how binary works. Boolean algebra involves number theory and is actually a vast field.
The most important concept is that you can mimic an OR gate using an AND gate, and an AND gate using an OR gate.
If you NOT your variables before you OR them, then NOT them again, it’s the exact same thing as if you ANDed them. Likewise, if you NOT your variables before you AND them, then NOT them again, it’s the exact same thing as if you ORed them.
Don’t believe me? Create a chart from 00 to 11 and flesh out the table using the psuedocode below, assuming that
thing2 are of type bool.
!(!thing1 || !thing2) == (thing1 && thing2)
thing1 || thing2 == !(!thing1 && !thing2)
I sometimes wonder how many self-taught programmers without a computer science background know about this. It’s very important — not just in theory, but in practice. I had a friend who vastly sped up an SQL query by going from an OR gate to using an AND gate — the return set was precisely the same, but it became much faster as a result.
Update 5/5/14: Because the false of false is true, the above classical statements can be rearranged with the following, respectively:
!thing1 || !thing2 == !(thing1 && thing2)
!(thing1 || thing2) == !thing1 && !thing2