IS.6: EQUIVALENT BOOLEAN EXPRESSIONS

OBJECTIVES

I can:

• compare and contrast equivalent Boolean expressions

• apply De Morgan’s Laws to Boolean expressions

De Morgan's Laws were developed by Augustus De Morgan in the 1800s.

These laws show how to simplify the negation of a complex boolean expression.

Recall that a complex boolean expression is multiple expressions joined by an AND (&&) or OR (||) such as (x < 3) && (y > 2).

When you negate one of these complex expressions, you can simplify it by flipping the operators and you will have an equivalent expression.

Here is an easy way to remember De Morgan's Laws:

Move the NOT inside, AND becomes OR

Move the NOT inside, OR becomes AND

In Java, De Morgan's Laws are written with the following operators:

You can also simplify negated boolean expressions that have relational operators like <, >, ==. 

You can move the negation inside the parentheses by flipping the relational operator to its opposite sign.

For example, !(c == d) is the same as saying c != d.

An easy way to remember this is:

To move the NOT, flip the sign.

Notice that == becomes !=, but < becomes >=:

TRUTH TABLES

Although you do not need to memorize De Morgan's Laws for the exam, you should be able to show that two boolean expressions are equivalent.

One wat to do this is by using truth tables.

For example, we can show that !(a && b) is equivalent to !a || !b by constructing a table below and seeing that they give identical results for the 2 expressions (see, the last two columns in the table below are identical!).

SIMPLIFYING BOOLEAN EXPRESSIONS

Often, you can simplify boolean expressions to create equivalent expressions.

For example, applying De Morgan's Laws to !(x < 3 && y > 2) yields !(x < 3) || !(y > 2) as seen in the figure below.

This can be simplified further by flipping the relational operators to remove the not.

So, !(x < 3) || !(y > 2) is simplified to (x >= 3 || y <= 2) where the relational operators are flipped and the negation is removed.

These two steps used to simplify this boolean expression are shown below:

HELPFUL TRUTH TABLES

The not operator ( ! ) is also known as the inverter. 

Notice how the outputs (3rd column) are inverted!

SUMMARY

• De Morgan's Laws can be applied to Boolean expressions to create equivalent ones:

  • !( a && b ) is equivalent to !a || !b

  • !(a || b) is equivalent to !a && !b

• A negated expression with a relational operator can be simplified by flipping the relational operator to its opposite sign:

  • !( a == b) is equivalent to (a != b)

  • !( a != b) is equivalent to (a == b)

  • !( a < b) is equivalent to (a >= b)

  • !( a > b) is equivalent to (a <= b)

  • !( a <= b) is equivalent to (a > b)

  • !( a >= b) is equivalent to (a < b)

• Truth tables can be used to prove that 2 Boolean expressions are identical.

• Equivalent Boolean expressions will evaluate to the same value in all cases.

EVIDENCE

1) Complete the following Google Form. This form must be 100% correct and includes released AP practice questions. To stop working and return later, hit submit! You can "edit your response" and continue where you left off.

IS.6 Evidence 

2) MC Exam Practice: This lesson has additional practice problems which can be found on the MC Exam Practice page with an answer key! Use ctrl + f to search for different objectives throughout the year. You could look at these questions now, or, save these practice questions for later and use them to review! The choice is yours.