Main content
AP®︎/College Computer Science Principles
Course: AP®︎/College Computer Science Principles > Unit 3
Lesson 6: Logical equivalenceEquivalent compound Booleans
AP.CSP:
AAP‑2 (EU)
, AAP‑2.L (LO)
Many logical expressions use a mix of
NOT, AND, and OR. Though compound logical expressions can seem complicated, there are some useful logical equivalence rules that can help.We are going to consider two rules that were known by Greek and Medieval logicians. However, they were named for the logician Augustus De Morgan who wrote them down in the 1800s, so they're commonly called De Morgan’s Laws.
Rule #1
Let's start with a real world example:
The countries of Egypt and Sudan claim different areas of land as part of their country. A very unique aspect of this particular border is that there is actually an area of land that neither Egypt nor Sudan claims. This arises because the area is an uninhabited part of the Sahara desert and more importantly accepting that area of land would mean giving up a larger and inhabited area of land that both countries claim. A picture of the area is below:
We can describe that area of land in English:
The desert area is not claimed by Egypt and also not claimed by Sudan.
That's logically equivalent to this statement:
The desert area is not claimed by Egypt or Sudan.
Hopefully reading both statements makes it clear that they describe the same thing. If not, read the sentences again and think about why they are the same. It may also be helpful to look at the map again. On the map the statements describe the area in white (signifying that neither country claims the land).
Now, translating the original English sentence into pseudocode:
NOT claimedByEgypt AND NOT claimedBySudanThat condition is the same as:
NOT (claimedByEgypt OR claimedBySudan)The general form of this logical equivalence rule is:
| Expression | Equivalent | |
|---|---|---|
NOT A AND NOT B | ≡ | NOT (A OR B) |
Keep in mind that the equivalence holds in both directions. That means if you see this condition...
NOT (A OR B)...you can change it to:
NOT A AND NOT B...and it will have the same meaning!
Rule #2
To understand a similar rule let’s look at a unique road tunnel in the Marin Headlands, an area near San Francisco, California. This tunnel is only wide enough to support vehicle travel in a single direction at a time.
Due to this constraint, the tunnel is nicknamed the “Five-Minute Tunnel”, since it has traffic lights at either end that allow traffic only in one direction for five minute intervals.
What's a logical rule that would keep this tunnel safe? To prevent collisions, we need to ensure the traffic in each direction cannot travel at the same time. This could be stated as:
The tunnel is not used (at the same time) by Eastbound traffic and Westbound traffic.
Translating that rule into pseudocode:
NOT (eastboundTraffic AND westboundTraffic)That's logically equivalent to this condition:
NOT eastboundTraffic OR NOT westboundTrafficThe second pseudocode condition might feel harder to parse than the first, but it makes more sense when you think about the rules of the tunnel in another way: In at least one direction, there is no traffic using the tunnel. Either there's no traffic going east (
NOT eastboundTraffic) or no traffic going in the other direction (NOT westboundtraffic). Both conditions describe the rules of the tunnel equally well since they are logically equivalent.
The general form of this rule is:
| Expression | Equivalent | |
|---|---|---|
NOT (A AND B) | ≡ | NOT A OR NOT B |
Breaking down the rules
There are many ways to think about this rule. One is considering it similar to the distributive property from algebra:
When we have something like:
-(-x + -y)it is the same as
x - ywhich is the result of distributing the
- sign to each sign and operation -(-x) -+ -(-y)Distributing the negative changed the sign on the numbers and changed the addition between the numbers to subtraction.
Although not entirely the same, similar reasoning can help you remember these rules. For this condition:
NOT (A AND B)It is like distributing the
NOT to A, B and the AND. AbecomesNOT ABbecomesNOT BANDbecomesOR(like addition to subtraction)
So distributing looks like:
NOT A NOT AND NOT BNOT A OR NOT BThe distribution approach also works for the first rule mentioned.
Starting with:
NOT (A OR B)Distributing:
NOT A NOT OR NOT BAfter negating
OR:NOT A AND NOT BWant to join the conversation?
In the section "Breaking down the rules", I believe there is a mistake. It says that -(-x + -y) is equivalent to x-y. This is incorrect. -(-x + -y) is equivalent to x+y.(25 votes)
- * - = +
+ * + = +
- * + = -
+ * - = -
this is the rule,
and also -(x + y) = x-y
-(x - y) = x+y
-(x * y) = -xy not -x * -y(0 votes)
wait a minute...
-(-x + -y) = -(-x -y) = x + y(8 votes)
I think there's a mistake：
【Original Text:】
"When we have something like:
-(-x + -y)
it is the same as
x - y"
【It should be:】
"When we have something like:
-(-x + -y)
it is the same as
x + y"
right?(8 votes)- yes u r right. and i don't understand the need for confusing examples.
suppose if x=2 and y=3
so,-(-2+(-3)=-(-5);
-(-5)=+5.
And x+y= 2+3=5
so yeah you are right(1 vote)
- Does (A and B) = A or B(0 votes)
(A and B) will only return true if both A and B are true. If anyone of the two are false, or if both are false, then (A and B) will equal false.
For example, here are the conditions where (A and B) = true:
A = true: B = True;
(A or B) will return true if either one or both are true. It will only return false if both A and B are false.
Here the examples where (A or B) = true:
1. A = true: B = true;
2. A = true: B = false;
3. A = false: B = true;(2 votes)
- In this phrase: "Either there's no traffic going east (NOT eastboundTraffic) or no traffic going in the other direction (NOT westboundtraffic)." We should have (NOT westboundTraffic) instead of (NOT westboundtraffic).
Thank you.(0 votes)