wait a minute... -(-x + -y) = -(-x -y) = x + y

So just put the - sign aside. (-x+-y) is equal to (-x-y) because (+-) = (-). now take the - sign back. -(-x-y). think of your math course, the distribution multiplication. - is equal to -1. -1 * -x = x. -1 * -y = y. x+y is the answer.

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?

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

Does (A and B) = A or B

(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;

Main content

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

Lesson 6: Logical equivalence

Equivalent compound Booleans

Google Classroom

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 claimedBySudan

That 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!

Check Your Understanding

Consider this boolean expression about the categorization of rice:

NOT foodType = "fruit" AND NOT foodType = "vegetable"

Which of the following expressions is logically equivalent?

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 westboundTraffic

The 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. For this condition:

NOT (A AND B)

It is like distributing the NOT to A, B and the AND.

A becomes NOT A
B becomes NOT B
AND becomes OR

So distributing looks like:

NOT A   NOT AND   NOT B

NOT A   OR        NOT B

The distribution approach also works for the first rule mentioned.

Starting with:

NOT (A OR B)

Distributing:

NOT A   NOT OR   NOT B

After negating OR:

NOT A   AND      NOT B

Want to join the conversation?

Sort by:

Sajan Patel
Posted 3 years ago. Direct link to Sajan Patel's post “In the section "*Breaking...”
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.
Button navigates to signup pageComment on Sajan Patel's post “In the section "*Breaking...”
(32 votes)
Answer
- BigK DM
  Posted 6 months ago. Direct link to BigK DM's post “Yes, you are right.”
  Yes, you are right.
  Button navigates to signup page
  (4 votes)
Minseo Lim
Posted a year ago. Direct link to Minseo Lim's post “wait a minute... -(-x + -...”
wait a minute...
-(-x + -y) = -(-x -y) = x + y
Button navigates to signup pageComment on Minseo Lim's post “wait a minute... -(-x + -...”
(24 votes)
Answer
- jimbuckhorn
  Posted 4 months ago. Direct link to jimbuckhorn's post “So just put the - sign as...”
  So just put the - sign aside. (-x+-y) is equal to (-x-y) because (+-) = (-). now take the - sign back. -(-x-y). think of your math course, the distribution multiplication. - is equal to -1. -1 * -x = x. -1 * -y = y. x+y is the answer.
  Button navigates to signup page
  (2 votes)
JiaqiFan42
Posted a year ago. Direct link to JiaqiFan42's post “I think there's a mistake...”
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?
Button navigates to signup pageButton navigates to signup page
(18 votes)
Answer
- tafseerahmad357
  Posted a year ago. Direct link to tafseerahmad357's post “yes u r right. and i don'...”
  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
  Comment on tafseerahmad357's post “yes u r right. and i don'...”
  (3 votes)
Daniel Chang
Posted 3 years ago. Direct link to Daniel Chang's post “Does (A and B) = A or B”
Does (A and B) = A or B
Button navigates to signup pageButton navigates to signup page
(1 vote)
Answer
- Geniusboy100
  Posted 3 years ago. Direct link to Geniusboy100's post “(A and B) will only retur...”
  (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;
  Button navigates to signup page
  (3 votes)
nathan.christopher787
Posted 23 days ago. Direct link to nathan.christopher787's post “The statement "The desert...”
The statement "The desert area is not claimed by Egypt or Sudan." should be "The desert area is not claimed by Egypt nor Sudan."
Button navigates to signup pageButton navigates to signup page
(1 vote)
Answer
Ruslan Apostol
Posted 3 years ago. Direct link to Ruslan Apostol's post “In this phrase: "Either t...”
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.
Button navigates to signup pageButton navigates to signup page
(1 vote)
Answer
Joseph Lodes
Posted 22 days ago. Direct link to Joseph Lodes's post “Why do most variables sta...”
Why do most variables start with a lowercase letter, but words following start with an uppercase letter? (ex. "eastboundTraffic" or "blueNeckTie").
Button navigates to signup pageButton navigates to signup page
(1 vote)
Answer
- Isaiah
  Posted 20 days ago. Direct link to Isaiah's post “This is Camel Case. There...”
  This is Camel Case. There are different ways to write variables since they generally can't have spaces. We either use underscores, dashes, title case, all lowercase/uppercase, or camel case
  Examples:
  Titlecase variable: MyVariableThatIsCool
  Camelcase variable: myVariableThatIsCool
  all lowercase: myvariablethatiscool
  all caps: MYVARIABLETHATISCOOL
  dashes: my-variable-that-is-cool
  underscores: my_variable_that_is_cool
  
  There are other standards too but these are most common.
  You can use whatever works as long as you are consistent.
  I personally prefer Camel Case or underscores.
  Button navigates to signup page
  (1 vote)