3.6 Equivalent Boolean Expressions
In this section, you will apply some of the concepts of booleans and logical expressions as you evaluate expressions to determine whether they are equivalent.
Augustus De Morgan was a British mathematician who devised two laws to help understand equivalent boolean expressions.
- not(A and B) is the same as (not A) or (not B)
- not(A or B) is the same as (not A) and (not B)
Collectively these two laws are known as De Morgan’s Law. At the heart of these laws, De Morgan is saying that you can transform one expression into an equivalent expression. In terms of boolean expressions, you saw that 2 expressions are equivalent if they both evaluate to the same value for all cases. In the case of De Morgan’s law, that means that regardless of whether A is true or false and B is true or false, not(A and B) will always be the same as (not A) or (not B). Likewise, not(A and B) will always be the same as (not A) and (not B).
To help better understand De Morgan’s Law, you can use truth tables. Truth tables look at various values of boolean variables and expressions and can be used to prove boolean identities such as De Morgan’s Law.
De Morgan’s First Law states that not(A and B) is the same as (not A) or (not B). If you were to put this in terms of Java, it would look like this:
Let’s break this down in a truth table.
A | B | A&&B | !(A&&B) | !A | !B | !A || !B |
---|---|---|---|---|---|---|
T | T | T | F | F | F | F |
T | F | F | T | F | T | T |
F | T | F | T | T | F | T |
F | F | F | T | T | T | T |
Notice in the table above how our two columns that contain expressions show the same values for each expression for all 4 possible combinations of values for A and B. As a result, you can see that the two expressions are equivalent.
Turning now to De Morgan’s Second Law, you can do the same thing. Expressed as a Java expression, De Morgan’s second law states:
Let’s take a look at the truth table for this law.
A | B | A||B | !(A||B) | !A | !B | !A && !B |
---|---|---|---|---|---|---|
T | T | T | F | F | F | F |
T | F | T | F | F | T | F |
F | T | T | F | T | F | F |
F | F | F | T | T | T | T |
Again, if you focus on the two highlighted columns, you can see that the two sides of the expression in De Morgan’s second law are also equivalent.
Truth tables can be powerful tools to help determine if two or more expressions are equivalent. To use a truth table, it is best to break down expressions into small pieces and then build them back up. Let’s take a look at this expression:
Under what circumstances would this expression evaluate to true
? You can use a truth table to answer that question. You should lay the truth table out to follow the order of operations, which means you will evaluate the NOT operators first, then the AND operators, and finally the OR operator.
A | B | !B | A && !B | !A | !A && B | A && !B || !A && B |
---|---|---|---|---|---|---|
T | T | F | F | F | F | F |
T | F | T | T | F | F | T |
F | T | F | F | T | T | T |
F | F | T | F | T | F | F |
When you lay out the results in a truth table, it is easy to see that the expression will evaluate to true anytime A and B have opposite values.
-
Incorrect
Correct
No Answer was selected
Invalid Answer
Which of the following logical statements is equivalent to
Where
A
andB
are boolean values.
This program reads input from the user to determine if the user can ride the rollercoasters and swim in the pools at the amusement park.
The program computes 2 boolean expressions in order to determine what the user is allowed to do:
and
Convert these two lines into their equivalent De Morgan style boolean expressions. Negate the AND in the first statement and negate the OR in the second statement using De Morgan’s Laws.
Your resulting boolean expression for cannotRide
should include both oldEnough
and tallEnough
. Your resulting boolean expression for cannotSwim
should include both canSwim
and hasLifeJacket
.
The resulting program should still be able to successfully determine if the user can ride the rides and swim in the pool.