Welcome to Software Development on Codidact!
Will you help us build our independent community of developers helping developers? We're small and trying to grow. We welcome questions about all aspects of software development, from design to code to QA and more. Got questions? Got answers? Got code you'd like someone to review? Please join us.
Understanding "de Morgan's laws"
While trying to understand logical 'or'/'and', I encountered another problem (I'm writing Python code here, but my question is about the logic, not about any given programming language). I have some code like:
if x or y:
pass
else:
do_something()
(Of course, following the other Q&A, I made sure that the real x and y make sense independently as conditions.)
I wanted to focus on the else case, because it's actually interesting. I figured out that I could negate the condition to flip the cases, and then the else: pass part would be unnecessary:
if not(x or y):
do_something()
However, other obvious attempts did not work:
if not x or y:
do_something()
if not x or not y:
do_something()
if (not x) or (not y): # not even with more parentheses!
do_something()
I asked about this elsewhere and was told it had something to do with "de Morgan's laws". What does this mean? Can I use these "laws" to understand how to write the code correctly? How exactly do they apply?
1 answer
Overview
de Morgan's 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:
-
negating both sides;
-
swapping "and" for "or", and vice-versa;
-
negating the result.
Examples:
By applying the steps, we find that x or y is equivalent to not((not x) and (not y)):
x or y
(not x) or (not y) # negate each side independently
(not x) and (not y) # replace 'or' with 'and'
not((not x) and (not y)) # negate the entire expression
Similarly, m and n is equivalent to not((not m) or (not n)):
m and n
(not m) and (not n) # negate each side independently
(not m) or (not n) # replace 'and' with 'or'
not((not m) or (not n)) # negate the entire expression
We can also start with negated sub-expressions:
(not x) or (not y)
not((not x)) or not((not y)) # negate each side independently
x or y # cancel double negations (we can do this freely any time)
x and y # replace 'or' with 'and'
not(x and y) # negate the entire expression
and:
(not m) and (not n)
not((not m)) and not((not n)) # negate each side independently
m and n # cancel double negations (we can do this freely any time)
m or n # replace 'and' with 'or'
not(m or n) # negate the entire expression
Notice that if we apply the procedure twice and make sure to cancel all pairs of negations, we'll get the original result back.
Even though new programmers often get this wrong, the rule 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 nots). 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.
Applications
-
Here is a two and a half hour video exposition of the functional completeness of NAND.
-
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 writtenx != yThus, we can transform(a == b) or (c == d)intonot((a != b) and (c != d)).Here is a quick reference table:
Original expression Negation x == yx != yx != yx == yx < yx >= yx > yx <= yx <= yx > yx >= yx < 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".)
-
A common logical error in code looks like (again, this is a Python example, but the principle applies to other languages):
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, theorshould be replaced withand. 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 ofx == 1 and x == 2, which obviously is never met.)
1 comment thread