Main content
AP®︎/College Computer Science Principles
Course: AP®︎/College Computer Science Principles > Unit 3
Lesson 6: Logical equivalenceCombining equivalence rules
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
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
NOT
s 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
NOT
s. So this is a good time to try to add some NOT
s.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
NOT
s 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!
Want to join the conversation?
- this is confusing!!(7 votes)
- *AllTogetherNow!*(3 votes)
- ik your head is fried. open a code compiler and run the codes. try python. it would be simpler to understand.(2 votes)
- Just running the code does not help you understand why it works. (Also, Python is not a compiled language; it is interpreted.)(1 vote)