Truth Tables and De Morgan's Rules
8. Equivalent Boolean Expressions
Answer:
Yes. The two fragments are equivalent. It may have taken you a while to figure this out,
and you may not be completely convinced.
Equivalent Boolean Expressions
To decide if the two fragments are equivalent, pick some example values for speed and memory and see if the expressions evaluate the to the same boolean values. A systematic way of to check two boolean
expressions is to use a truth table. To start, look at the "speed" question:
|
speed > 2000
|
speed <= 2000
|
|---|---|
|
F
|
T
|
|
T
|
F
|
If it is False that the speed greater than 2000, then it is True that the speed is less than or equal to 2000.
If it is True that the speed greater than 2000, then it is False that the speed is less than or equal to 2000.
Only one of X>Y and X<=Y can be true for particular values of X and Y.
Another way to say this is !(X>Y) and X<=Y are equivalent. The last two columns of the following table show equivalent expressions.
speed > 2000 |
!(speed > 2000) |
speed <= 2000 |
|---|---|---|
F |
T |
T |
T |
F |
F |
It is also true that X>Y and !(X<=Y) are equivalent. This is demonstrated in the following question.
Question 8:
Fill in the following table. Fill the cells of a row so they are consistent with the first cell of the row.
The first column and the last column have the same T/F values, which shows that
speed > 2000 is equivalent to !(speed <= 2000).