Main content

AP®︎/College Computer Science Principles

Course: AP®︎/College Computer Science Principles > Unit 3

Lesson 6: Logical equivalence

Combining equivalence rules

AP.CSP:

AAP‑2 (EU)

AAP‑2.L (LO)

Now that we have a firm grasp on many logical equivalence rules, we can use them together to yield some interesting results.

Combining with `NOT NOT`

Recall that NOT (NOT A) is equivalent to A.

Consider this compound expression:

NOT (NOT isMoving AND NOT isAlive)

Applying De Morgan's Law, that's equivalent to:

NOT (NOT isMoving) OR NOT (NOT isAlive)

And that can be simplified all the way to:

isMoving OR isAlive

Combining with `NOT =`

Another rule is that NOT = is equivalent to ≠.

Consider this expression:

NOT (myAge = cousinsAge AND myAge = friendsAge)

Applying De Morgan's law, this can be written as:

NOT myAge = cousinsAge OR NOT myAge = friendsAge

And by using ≠, that can be simplified further:

myAge ≠ cousinsAge OR myAge ≠ friendsAge

Check Your Understanding

Consider the pseudocode:

NOT (lightOn AND NOT doorClosed)

Assume that:

lightOn is logically equivalent to NOT lightOff
doorClosed is logically equivalent to NOT doorOpened

Which pseudo code is equivalent:

All together now!

Now that we have all these tools, let's work through some examples that use many rules.

Example 1

Consider the following:

NOT (NOT A = B OR C > 100)

This is equivalent to (De Morgan’s Law):

NOT (NOT A = B) AND NOT (C > 100)

Is equivalent to (two NOT’s):

A = B AND NOT (C > 100)

Is equivalent to (NOT > to ≤):

A = B AND C ≤ 100

Example 2

Intro

Sometimes the path to simplifying an expression starts by making the expression longer. This is usually done by adding NOTs to enable the applying of De Morgan's laws.

The goal is usually to get to an expression like:

NOT A AND NOT B

So that we can then turn it into an expression like:

NOT (A OR B)

Example

Let's start with the expression:

A = B AND C = D

On the first look it might not seem like this can be changed to anything and that we can't use De Morgan's laws because there are no NOTs. So this is a good time to try to add some NOTs.

Again our expression:

A = B AND C = D

Is equivalent to (two NOTs):

NOT (NOT A = B) AND NOT (NOT C = D)

Is equivalent to (NOT =):

NOT A ≠ B  AND NOT C ≠ D

Is equivalent to (De Morgan's law):

NOT (A ≠ B OR C ≠ D)

To recap, we first made our expression longer, so that we could apply De Morgan's Law. The final result in this case is more complex (and therefore maybe not something you would actually do), but the next example will show where adding NOTs might be especially useful.

Example 3

Consider this expression:

A ≥ B AND A ≠ B

Is equivalent to (NOT <):

NOT A < B AND A ≠ B

Is equivalent to (NOT =):

NOT A < B AND NOT A = B

Is equivalent to (De Morgan's law):

NOT (A < B OR A = B)

Is equivalent to (definition of "less than or equal"):

NOT (A ≤ B)

Is equivalent to (NOT >):

A > B

To verify the answer, think about the first statement:

A ≥ B AND A ≠ B

This says A is either greater than B or equal to B AND A is not equal to B.

This means that A can only be greater than B (since it cannot be equal to B).

A > B

That's exactly our simplified equivalence!