# 3.6. Equivalent Boolean Expressions (DeMorgan’s Laws)¶

DeMorgan’s Laws were developed by Augustus De Morgan in the 1800s. They show how to handle the negation of a complex conditional, which is a conditional statement with more than one condition joined by an and (&&) or or (||), such as `(x < 3) && (y > 2)`

. When you negate one of these complex conditionals, you can simplify it by flipping the operators and end up with an equivalent expression. De Morgan’s Laws state that:

not (a and b) is the same as (not a) or (not b). In Java this is written as !(a && b) == !a || !b

not (a or b) is the same as (not a) and (not b). In Java this is written as !(a || b) == !a && !b

Although you do not have to memorize DeMorgan’s Laws for the 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. For example, we can show that !(a && b) == !a || !b by constructing the truth table below and seeing that they give identical results for the 2 expressions (the last 2 columns in the table below are identical!).

a |
b |
!(a && b) |
!a || !b |
---|---|---|---|

true |
true |
false |
false |

false |
true |
true |
true |

true |
false |
true |
true |

false |
false |
true |
true |

Often, you can simplify boolean expressions to create equivalent expressions. For example, applying DeMorgan’s Laws to `!(x < 3 && y > 2)`

yields `!(x < 3) || !(y > 2)`

. This can then be simplified further by flipping the operators instead of keeping the not operator. So, `!(x < 3) || !(y > 2)`

is simplified to `(x >= 3 || y <= 2)`

where the relational operators are flipped and the negation is removed. So,

```
!(x < 3 && y > 2) == !(x < 3) || !(y > 2) == (x >= 3 || y <= 2)
```

The negation can be removed if you flip the relational operator. For example, not (c equals d) is the same as saying c does not equal d. The not in the relational expressions below is equivalent to flipping the relational operator to its opposite sign.

!(c == d) == (c != d)

!(c != d) == (c == d)

!(c < d) == (c >= d)

!(c > d) == (c <= d)

!(c <= d) == (c > d)

!(c >= d) == (c < d)

For what values of x and y will the code below print true? Try out different values of x and y to check your answer.

- first case
- This will be printed if x is greater or equal to 3 and y is less than or equal to 2. The first part is true but the second is false. Since the statements are joined by an and the complex conditional is false.
- second case
- This will be printed if x is less than 3 or y is greater than 2. In this case the first will be false, but the second true so since the statements are joined with an or the complex conditional is true.

3-6-1: What is printed when the following code executes and x equals 4 and y equals 3?

```
if (!(x < 3 || y > 2)) System.out.println("first case");
else System.out.println("second case");
```

- first case
- This will be printed if x is greater than or equal to 3 or y is less than or equal to 2. In this case x is greater than 3 so the first condition is true.
- second case
- This will be printed if x is less than 3 and y is greater than 2.

3-6-2: What is printed when the following code executes and x equals 4 and y equals 3?

```
if (!(x < 3 && y > 2)) System.out.println("first case");
else System.out.println("second case");
```

## 3.6.1. Programming Challenge : Truth Tables POGIL¶

We encourage you to do this activity as a POGIL (Process Oriented Guided Inquiry Learning) group activity. POGIL groups are self-managed teams of up to 4 students where everyone has a POGIL role and works together to solve the problems, making sure that everyone in the team participates and learns.

Explore the following problems with your group:

Complete a truth table for the boolean expression: !(x == 0 || x >= 1). Is this the set of positive or negative numbers?

Complete a truth table for the boolean expression: !(x == 0) && !(x >= 1). Is this the set of positive or negative numbers?

Complete a truth table for the boolean expression: (x != 0) || (x < 1). Is this the set of positive or negative numbers?

Are the 3 boolean expressions equivalent? Why or why not?

Test your answers using the active code window below.

Complete the following exercises 3-6-3 through 3-6-6 in your POGIL groups.

- (x < 2) || (y > 4)
- The negation of x > 2 is x <= 2
- (x < 2) && (y > 4)
- Don't forget that the and is changed to an or
- (x <= 2) || (y >= 4)
- The x > 2 becomes x <= 2, the y < 4 becomes y >= 4 and the and changes to or
- (x <= 2) && (y >= 4)
- Don't forget that the and is changed to an or

3-6-3: Which of the following is the same as the code below?

```
!(x > 2 && y < 4)
```

- (x != 2) || (y < 4)
- The negation of y > 4 is y <= 4
- (x != 2) && (y < 4)
- Don't forget that the and is changed to an or
- (x != 2) && (y <= 4)
- Don't forget that the and is changed to an or
- (x != 2) || (y <= 4)
- The and is changed to an or, the (x == 2) becomes (x != 2) and (y > 4) becomes (y <= 4)

3-6-4: Which of the following is the same as the code below?

```
!(x == 2 && y > 4)
```

- (x == 5) || (y == 7)
- The negation of && is || and the negation of != is ==
- (x == 5) && (y == 7)
- The negation of && is ||
- (x != 5) || (y != 7)
- The negation of x != 5 is x == 5. The negation of y != 7 is y == 7.
- (x < 5) || (x > 5) || (y > 7) || (y < 7)
- The negation of == is != which is the same as < or >. The negation of != is ==.

3-6-5: Which of the following is the same as the code below?

```
!(x!=5 && y!=7)
```

- (x > 5) && (y < 7)
- The negation of && is || and the negation of y > 7 is y <= 7.
- (x > 5) || (y < 7)
- The negation of y > 7 is y <= 7.
- (x > 5) && (y <= 7)
- The negation of && is ||.
- (x > 5) || (y <= 7)
- The negation of (x <= 5) is (x > 5). The negation of && is ||. The negation of (y > 7) is (y <= 7).

3-6-6: Which of the following is the same as the code below?

```
!(x<= 5 && y > 7)
```

## 3.6.2. Summary¶

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

!(a && b) == !a || !b

!(a || b) == !a && !b

A negated conditional with a relational operator can be simplified by flipping the relational operator and removing the not.

!(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 can be used to prove that 2 Boolean expressions are identical.

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