The purpose of this section is more to make you aware that there are logical implications rather than to gain an in-depth understanding of what they are. Once again…there is an entire field of study related to all of this boolean algebra that is beyond the scope of what I want to cover.
We need to establish what I mean by a “law” in this context. You’re actually already familiar with the base idea although you might not know it. Laws like these mean rules that work for all possible values like associativity, commutativity, and distribution. When you see these in math, we talk about them in regard to each of the two basic operations that we have.
| Law | Example |
|---|---|
| Associativity of Addition | (x+y)+z = x+(y+z) |
| Associativity of Multiplication | (x*y)*z = x*(y*z) |
| Commutativity of Addition | x+y = y+x |
| Commutativity of Multiplication | x*y = y*x |
| Distributivity | x*(y+z) = x*y + x*z |
Hopefully those sound familiar! There are similar rules for boolean logic, and while we won’t focus on most of them, I want to focus primarily on a pair of laws known as De Morgan’s Laws. They are essentially the distribution of a NOT over OR or AND. In the example shown below notice that I used p and q rather than T or F. This is because the laws work for all values, not just a specific example. (Similar to why I used variables in the table above.)
¬(p∧q) ↔ ¬p ∨ ¬q
Notice that the operation between the two terms switched! This can be confusing for many people at first, so let’s take a look at a specific example.
If I tell you that you may not have cookies or ice cream tonight, one way to write that is
Can you have cookies? No. Can you have ice cream? No. Or in other words…
Hopefully with an example it becomes a bit clearer why the symbol switches between them.
While we can look at a specific case and see that the rule works, how can we convince ourselves definitively that the law works for all values? In our standard math system we need robust proofs that cover all possible types of combinations of numbers in order to be sure that a rule works. However, the fact that we’re dealing strictly with booleans makes this incredibly easy. How many different possible combinations of p and q are there? (Hint…the answer is four.)
In order to show that the law works in general we can look at every possible combination and check it out.
¬(T) ↔ F ∧ F
F ↔ F
It works!
¬(T) ↔ F ∧ T
F ↔ F
It works!
¬(T) ↔ T ∧ F
F ↔ F
It works!
¬(F) ↔ T ∧ T
T ↔ T
It works!
With only four options we have now verified one of the laws always works. But even with the finite nature of such a proof it can get tedious to write it all out and check it. Luckily, we have an even easier way, which we will discuss in the next section!
← Previous PageNext Page →