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
  1. !(x < 3 && y > 2)
  2. !(x < 3) || !(y > 2)
  3. (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