Post History

## Overview

[de Morgan's laws](https://en.wikipedia.org/wiki/De_Morgan%27s_laws) are *rules of logic* that allow you to transform one conditional expression into another, equivalent expression. Because (in Boolean logic) two negations cancel each other out (i.e. `not(not x)` is equivalent to `x`), we can also infer rules for *negating* an expression.

The core idea is that, given a simple logical-and or logical-or with a left-hand side and a right-hand side, we can get an equivalent result by:

1. negating both sides;

1. swapping "and" for "or";

1. negating the result.

Thus, `x or y` is equivalent to `not((not x) and (not y))`; and `m and n` is equivalent to `not((not m) or (not n))`.

Equivalently: `(not x) or (not y)` is equivalent to `not(x and y)` (after cancelling some not-pairs), and `(not m) and (not n)` is equivalent to `not(x or y)` (after cancelling some not-pairs).

Notice that this is self-consistent. If we apply the procedure twice and then cancel out all the not-pairs, we'll get the original result back.

It also actually makes sense in natural English: "one of these things is true" means the same thing as "these things aren't both false".

## Proof

We can prove this simply by inspection (building some truth tables). For example:

| `x and y` | `x` true | `x` false |
| - | - | - |
| **`y` true** | true | false |
| **`y` false** | false | false |

Therefore, by the double-negation principle:

| `x and y` | `(not x)` false | `(not x)` true |
| - | - | - |
| **`(not y)` false** | true | false |
| **`(not y)` true** | false | false |

If we negate the expression, that is equivalent to negating all results:

| `not (x and y)` | `(not x)` false | `(not x)` true |
| - | - | - |
| **`(not y)` false** | false | true |
| **`(not y)` true** | true | true |

And swapping rows and columns for clarity:

| `not (x and y)` | `(not x)` true | `(not x)` false |
| - | - | - |
| **`(not y)` true** | true | true |
| **`(not y)` false** | true | false |

But now we can see that the truth table for `not (x and y)` is identically the truth table for `(not x) or (not y)`, QED.

## Importance

These laws entail that we always have two fundamental ways to write the same expression (notwithstanding useless pairs of `not`s). Thus, *we can choose* between them as we see fit, to make the code easier to read and understand.

Because, again, two negations cancel each other out in Boolean logic, and because the last step is negation, this also gives us an easy way to negate an expression (which is useful for inverting `if`/`else` logic). Given the condition `x or y`, we can get the opposite condition by applying the *first two* steps - thus, `(not x) and (not y)`.

Finally, this rule has important applications in *hardware*. A NOT gate can be created from a NAND gate by simply connecting both inputs to the same source; and an AND gate is of course just the inverse of NAND, so we can create it by connecting NOT to the output of NAND. Then, because of de Morgan's laws, we see that we can construct an OR gate by connecting NOT to *each input* of NAND. Further following this chain of logic, we can demonstrate that *every combinatorial logic circuit* can be created from [a combination of NAND gates](https://en.wikipedia.org/wiki/NAND_logic).

## Examples and extensions

1. [Here is a two and a half hour video exposition](https://www.youtube.com/watch?v=2vIogCBiRsY) of the [functional completeness](https://en.wikipedia.org/wiki/Functional_completeness) of NAND.

1. Relational operators also have negations. In particular, `!=` and `==` are typically defined as opposites (some programming languages use different symbols); `not(x == y)` could equivalently be written `x != y` Thus, we can transform `(a == b) or (c == d)` into `not((a != b) and (c != d))`.

    Here is a quick reference table:

    | Original expression | Negation |
    | - | - |
    | `x == y` | `x != y` |
    | `x != y` | `x == y` |
    | `x < y` | `x >= y` |
    | `x > y` | `x <= y` |
    | `x <= y` | `x > y` |
    | `x >= y` | `x < y` |

(We can think of these operators as implementing 3-input truth tables, where the inputs are `x < y`, `x == y` and `x > y` - except skipping the ones for "always true" and "always false".)

1. A common logical error in code looks like (again, this is a Python example, but the principle applies to other languages):

    ```python
    if x != 1 or x != 2:
        print("neither 1 nor 2")
    ```

    The intent was to negate the condition `x == 1 or x == 2`. But because of de Morgan's law, the `or` should be replaced with `and`. The consequence of this error is that *the condition is always met*. (To see that more easily, *apply the law*: our wrong condition is thus the negation of `x == 1 and x == 2`, which obviously is *never* met.)