Equivalent Boolean Expressions

In this lesson, we’ll see how De Morgan’s laws can simplify any complex boolean statement.

Overview of De Morgan’s laws

Augustus De Morgan, a mathematician presented some transformation rules. In English, we can represent the rules as:

• The negation of a disjunction is the conjunction of the negations.
• The negation of a conjunction is the disjunction of the negations.

A disjunction is a compound statement formed by joining two statements with the connector: OR.

A conjuction is a compound statement formed by joining two statements with the connector: AND.

Mathematically, we can write the laws as:

• not (A or B) = (not A) and (not B)
• not (A and B) = (not A) or (not B)

In Java, De Morgan’s laws are written with the following operators:

• !(A || B) = !A && !B
• !(A && B) = !A || !B

Although you do not have to memorize De Morgan’s laws for the AP CS A Exam, you should be able to show that two boolean expressions are equivalent. One way to do this is by using truth tables.

Evaluating via truth tables

Truth tables can be used to prove boolean identities. Let’s construct the table for !(A || B) = !A && !B.