Boolean expression simplification solutions

Complete the Boolean expression simplification exercises before reviewing the solutions.

Review the Boolean expression simplification solutions with AP CS Tutor Brandon Horn.

Exercise 1

Distribute the not.

!(a && b && c)
!a || !b || !c

De Morgan’s Law:

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

Exercise 2

(a && b) && !(a && b)
false

Let c represent the repeated expression a && b. The expression becomes:
c && !c

The left side requires that c be true. The right side requires that c be false. The sides are combined with and (&&). It is not possible for c to be both true and false, so the entire expression always evaluates to false.

Not all Boolean expressions always evaluate to true or always evaluate to false. In general, writing such an expression in code would be a logical error. Expressions that always evaluate to true or always evaluate to false may be featured on the AP CS A Exam. If an expression really does always evalute to the same value, don’t be afraid to select that answer choice.

Other simplifications include:

c || !c always evaluates to true.

c && c is equivalent to c.

c || c is equivalent to c.

c == c always evaluates to true.

Exercise 3

!((x < y) && (r >= s))
!(x < y) || !(r >= s)
x >= y || r < s

De Morgan’s Law results in the and (&&) becoming or (||) when the not (!) is distributed over it.

The opposite of less tha (<) is greater than or equal to (>=). The opposite of >= is <.

A common mistake is assuming that the opposite of greater than (>) is less than (<).

Exercise 4

(x > y) || (x <= y)
(x > y) || !(x > y)
true

The intermediate step is obtained by extracting a not (!) from the right side. The resulting expression is equivalent to c || !c. (See the explanation for Exercise 2.)

It is also possible to determine that the expression always evaluates to true without the intermediate step. The left side of the original expression checks if x is greater than y. The right side checks if x is less than or equal to y. One or the other must be true. The expressions are combined with or (||).

Exercise 5

(a && b) && (!a || !b)
(a && b) && !(a && b)
false

The intermediate step is obtained by extracting a not (!) from the right side. The resulting expression is equivalent to c && !c. (See the explanation for Exercise 2.)

It is also possible to determine that the expression always evaluates to false without the intermediate step. The left side checks if both a and b are true. The right side checks if at least 1 is false. The expressions are combined with and (&&).

Exercise 6

(a || b) && a
a

The expression simplifies to a because both of the statements below are true.

If a is true, the entire expression is true.
If a is false, the entire expression is false.

b is not relevant. Note that if only 1 of the statements above was true, the expression would not simplify to a.

Exercise 7

(a && b) || b
b

If b is true, the entire expression is true. If b is false, the entire expression is false. The expression simplifies to b. a is irrelevant.

Exercise 8

(a && b) || (a && b)
a && b

This is equivalent to c || c. (See the explanation for Exercise 2.)

Exercise 9

(a || b) || a
a || b

The expression a || b is already true if a is true. The extra || a is irrelevant.

Exercise 10

(a || b) || !(a || b)
true

This is equivalent to c || !c. (See the explanation for Exercise 2.)

Exercise 11

!((x < y) || (q > r))
!(x < y) && !(q > r)
x >= y && q <= r

Exercise 12

(a || b) && (!a && !b)
false

The left side says at least 1 of a and b must be true. The right side says both a and b must be false. Both side must be true. This is not possible.

It is also possible to simplify the expression by extracting a not (!) from the right side.

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

This is equivalent to c && !c. (See the explanation for Exercise 2.)

Exercise 13

!(a || b)

The expression is to true when a || b is false. a || b is false when both a and b are false. The expression evaluates to true when both a and b are false.

This demonstrates De Morgan’s Law.

Exercise 14

Tell when the expression will evaluate to true.

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

The left side is true when at least 1 of a and b is true. The right side is true when at least 1 of a and b is false. The expression is true when either a or b is true but not both.

This is known as exclusive or (xor). Some other programming languages offer xor as a logical operator.

Comments

Comment on Boolean expression simplification