Main content

AP®︎/College Computer Science Principles

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

Lesson 6: Logical equivalence

Equivalence between conditionals and Booleans

AP.CSP:

AAP‑2 (EU)

AAP‑2.L (LO)

AAP‑2.L.3 (EK)

AAP‑2.L.4 (EK)

Google Classroom

It's important to understand logical equivalence when writing computer programs so that your program's behavior is both logically correct and understandable by other programmers. There are many ways to write code that is logically equivalent, but there is often one way that is clearer and more concise than the others.

Let's look at some logical flows in pseudocode that can be simplified using logical equivalence rules and alternative programming structures.

Structural equivalence

First, let’s consider an example where we are trying to set a variable which reports if something is frequently used. We might write code like:

if (numUsers > 100) {
  isFrequentlyUsed ← true
} else {
  isFrequentlyUsed ← false
}

This seems like perfectly reasonable and clear code. However, the astute observer will note that the only operation done in each block of the if/else is setting the value of isFrequentlyUsed. It sets that value to:

true if numUsers > 100 is true
false in the else case (where numUsers > 100 is false)

We can replace the entire if/else block with a single line of code:

isFrequentlyUsed ← numUsers > 100

This will check numUsers > 100, produce a boolean (true or false), and then assign the value directly to the variable isFrequentlyUsed

To generalize this rule, if there's an if/else of this form:

if (E) {
  V ← true
} else {
  V ← false
}

This statement is logically equivalent:

V ← E

Structural equivalence with negation

Consider the code below that does a similar but opposite operation, reporting if something is rarely used:

if (numUsers > 100) {
  isRarelyUsed ← false
} else {
  isRarelyUsed ← true
}

At first, it seems like we are stuck because now our code is doing the opposite of the above. It sets the value to:

false if numUsers > 100 is true (not the same value!)
true otherwise (when numUsers > 100 is false)

Fortunately, we can use the logical equivalence rule from the first article on equivalent simple booleans, and use NOT to get the opposite value of a Boolean.

So the above if/else is the same as this line of code:

isRarelyUsed ← NOT (numUsers > 100)

In general our rule is this:

if (E) {
  V ← false
} else {
  V ← true
}

Can be replaced by:

V ← NOT (E)

Check Your Understanding

Consider the code:

if (age < 18) {
  isAdult = false
} else {
  isAdult = true
}

Which of the following is logically equivalent?

(Choice B)
isAdult ← 18

Want to join the conversation?

Sort by:

Julig C
Posted 2 months ago. Direct link to Julig C's post “Congratulations if you ma...”
Congratulations if you made it this far, keep going!
Button navigates to signup pageComment on Julig C's post “Congratulations if you ma...”
(13 votes)
Answer
Andrew Agarwal
Posted 4 months ago. Direct link to Andrew Agarwal's post “So you use a boolean(I lo...”
So you use a boolean(I love knowing what it is it brings me power, just like knowing the Mitochondria is the powerhouse of the cell), to identify the line of code above?

The Mitochondria is the powerhouse of the cell.
Button navigates to signup pageButton navigates to signup page
(4 votes)
Answer