Equivalent Boolean Expressions: De Morgan's Laws
Introduction: 3.6.0
- De Morgan’s laws simplify boolean expressions
De Morgan’s Laws: 3.6.1
- Developed by Augustus De Morgan in the 1800s
- Show how to simplify the negation of complex boolean expressions using
&&
or||
- simplify complex expressions by flipping operators to create a simpler, equivalent expression
- A negation turns a true statement false and a false statement true
Equivalencies
- move the NOT inside, AND becomes OR
- move the NOT inside, OR becomes AND
not (a and b) => (not a) or (not b)
not (a or b) => (not a) and (not b)
in java
!(a && b) is the same as !a || !b
!(a || b) is equivalent to !a && !b
- Can also be used with relational operators
- To move the NOT, flip the sign
Original expression | Simplified expression |
---|---|
!(c == d) | (c != d) |
!(c != d) | (c == d) |
!(c < d) | (c >= d) |
!(c > d) | (c <= d) |
!(c <= d) | (c > d) |
!(c >= d) | (c < d) |
Truth Tables: 3.6.2
- Shows that two expressions are equivalent
a | b | !(a&&b) |
!a||!b |
---|---|---|---|
true | true | false | false |
false | true | true | true |
true | false | true | true |
false | false | true | true |
Simplifying Boolean Expressions: 3.6.3
- Some expressions can be simplified multiple times using De Morgan’s laws
!(x < 3 && y > 2)
!(x < 3) || !(y > 2)
(x >= 3 || y <= 2)
Summary: 3.6.5
- De Morgan’s laws can make simpler, equivalent expressions
!(a && b)
is the same as!a || !b
!(a||b)
is the same as!a && !b
- Relational operators can be simplified by flipping the operator
- Truth tables can be used to check the equivalence of two expressions
- Equivalent expressions will always evaluate to the same value
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
This was adapted from the CS Awesome curriculum, which was created by
Barbara Ericson, Beryl Hoffman, and many other CS Awesome contributors. All rights reserved.
CS Awesome is licensed under CC BY-NC-SA 4.0.