Main content

## AP®︎/College Computer Science Principles

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

Lesson 6: Logical equivalence# Equivalent 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 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!

## 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. One is considering it similar to the distributive property from algebra:

When we have something like:

`-(-x + -y)`

it is the same as

`x - y`

which 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`

. `A`

becomes`NOT A`

`B`

becomes`NOT B`

`AND`

becomes`OR`

(like addition to subtraction)

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?

- 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)