Reasoning: An Introduction to Logic, Sets, and Functions

Subsection 3.3.4 More Identities

We present the rest of the identities without proof. You should try a few of the proofs yourself.

Equivalence: ( p ≡ q ) ≡ ( p → q ) ∧ ( q → p )

In other words, two statements are equivalent just in case each implies the other.

This rule suggests a way to go about proving that two statements are equivalent. Construct two proofs, one for each direction of the implication.

Idempotence: ( p ∧ p ) ≡ p

( p ∨ p ) ≡ p

“Idempotence” is a big word that just means, “has the same power as itself”. Despite the word, these laws probably seem completely obvious. If we or (or and ) something with itself, we just get back what we started with. These laws, while seemingly trivial, can be very useful when we need to simplify logical expressions.

De Morgan’s Laws: ¬( p ∧ q ) ≡ ¬ p ∨ ¬ q .

¬( p ∨ q ) ≡ ¬ p ∧ ¬ q .

These two laws are named for the important 19 th century logician Augustus De Morgan. They are useful in simplifying expressions because they attach not s to smaller units, thus making them easier to work with. When we use De Morgan’s laws, we sometimes describe what we’re doing as, “pushing not through and ” or, “pushing not through or .”

Read De Morgan’s laws carefully: When we apply them, or s become and s and and s become or s.

English aside

Consider the English sentence, “I won’t touch beets or okra.” Do you agree that this means both no beets and no okra for me?

Let’s give names to these sentences:

B: I will touch beets.

O: I will touch okra.

We can write our sentence in logic as:

\(\neg (B \vee O) \)

Using the second of De Morgan’s laws, we can rewrite that as:

\(\neg B \wedge \neg O \)

A straightforward translation of this into English gives us:

I won’t touch beets and I won’t touch okra.

English aside

Here’s another one, this time going from and to or: Consider the sentence, “You can’t have both cake and pie.” Do you agree that this means that you’re not getting pie or you’re not getting cake?

Let’s give names to these sentences:

C: You can have cake.

P: You can have pie.

We can write our sentence in logic as:

\(\neg (C \vee P) \)

Using the first of De Morgan’s laws, we can rewrite that as:

\(\neg C \vee \neg P \)

In other words, either you’re not getting cake or you’re not getting pie.

But, the Cooperative Principle may come into play:

This sentence doesn’t actually say that you’re even going to get one of them. You might be both cake and pie deprived. But most of us agree that if that were the case, it would be uncooperative to say this. The mean person should have said, “You’re not getting cake or pie.”

Commutativity of or and and : ( p ∨ q ) ≡ ( q ∨ p ).

( p ∧ q ) ≡ ( q ∧ p ).

Like addition and multiplication, both or and and are commutative.

Notice that implies isn’t on this list; it isn’t commutative.

Associativity of or and and : ( p ∨ ( q ∨ r )) ≡ (( p ∨ q ) ∨ r ).

( p ∧ ( q ∧ r )) ≡ (( p ∧ q ) ∧ r ).

Again, like addition and multiplication, both or and and are associative.

Notice again that implies isn’t on this list. That’s because it isn’t associative.

Distributivity of and and or : ( p ∧ ( q ∨ r )) ≡ (( p ∧ q ) ∨ ( p ∧ r )).

( p ∨ ( q ∧ r )) ≡ (( p ∨ q ) ∧ ( p ∨ r )).

Just as addition distributes over multiplication, and distributes over or and vice versa.

Conditional Disjunction : ( p → q ) ≡ (¬ p ∨ q ).

Sometimes it’s useful to think of this as an alternative way of writing ( p → q ). It avoids the use of implies, which may seem confusing.

English aside

We sometimes use this alternative in English. An equivalent fortune would have been, “If you display your treasures, people will become envious.”

Lots of people think that the word “implies” connotes a causal relationship (in addition to the purely logical one that we’re working with). If you, or your audience, is inclined to make this mistake, it reduces confusion if you use Conditional Disjunction to avoid using the word, “implies”.

Contrapositive : ( p → q ) ≡ (¬ q → ¬ p ).

The intuition here is that, if p implies q but we observe not q , then we know that p must be false. For example, if rain implies wet sidewalks and we observe dry sidewalks, we can conclude that there isn’t rain.