To understand DeMorgan's Laws, it might help to look at a boolean algebra over the elements {0, 1}, in terms of truth tables. Note that there are other boolean algebras for which there are other elements (for instance, fuzzy logic), so this is
not an acceptable mathematical proof, but just provides some basic understanding.
p or q:p and q:not p:Now, let's use the above truth tables to check out DeMorgan's Laws in action.
not (p and q) vs. not p or not q:
| p | q | not (p and q) | not p or not q |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
not (p or q) vs. not p and not q:
| p | q | not (p or q) | not p and not q |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 |
Anyways, this should give you some understand as to why, in a sort of hand-wavey way. You can definitely prove both properties using the fundamental properties of boolean algebra, but I won't do that (unless I feel bored later). Again, truth tables aren't a mathematical proof.
if you want the analogy, treat it as
not x = -x
x and y = x*y
x or y = x+y
This isn't exactly right. Tell me where this breaks down, or how to make it more exact.
I have a few nitpicks :D
x or y isn't equivalent to
x + y, because
x + y is not necessarily defined for a boolean algebra, or if it could be defined, it might not be closed over the set that a boolean algebra might consider. The set {T, F} may have no meaningful way of adding its elements. Addition isn't closed under the set {0, 1} (1 + 1 is outside the set {0, 1}). Addition
modulo 2 is closed under {0, 1} but this is exclusive or.
Likewise,
not x isn't equivalent to
-x, because it isn't arithmetic negation. In general, logical and arithmetic negation are quite different because
not 0 = 1 while
-0 = 0.
Furthermore,
x and y might not be defined as
x * y depending on the algebra, but in fact be something like
min(x, y) which gives rather different results for other elements in the set besides the unit element 1 and zero element 0.
Developer
