Due to math content, this page has special requirements (including JavaScript) for full functionality.
With your current viewing scenario, it is not appearing and behaving as it is supposed to!
Please visit Dr. Carol J.V. Fisher's Homepage to learn what this site has to offer.
Watch the "Welcome" video to get started—hope to see you back here soon!

Dr. Carol J.V. Fisher's Homepage

For this exercise, you need ♥ INTERNET EXPLORER 6.0 and above, with MathPlayer installed.♥

LOGICAL EQUIVALENCES and
PRACTICE WITH TRUTH TABLES

Jump right to the exercises!

A logical equivalence is a statement that two mathematical sentence forms are completely interchangeable:
if one is true, so is the other; if one is false, so is the other.

For example, we could express that an implication is equivalent to its contrapositive in either of the following ways:

A ⇒ B is (logically) equivalent to (not B) ⇒ (not A)

(A ⇒ B) ⇔ ((not B) ⇒ (not A)) is a logical equivalence

In this section, you will construct truth tables involving implications, equivalences, negations,
and the mathematical words AND and OR.
In the process, you will be introduced to many useful logical equivalences,
and will start to develop intuition for investigating logical equivalences.

NEGATING   AND   and   OR   SENTENCES:
DE MORGAN'S LAWS

How can a sentence "A and B" be false?
The only time an   and   sentence is true is when both subsentences are true.
So, an   and   sentence is false when at least one of the subsentences is false.

Precisely, the truth table below shows that
not(A and B)     is equivalent to     (not A) or (not B)
Here's the intuition you should have when looking at this sentence.
Start with (1) and work your way to (6):

(2) ... is false ...	(1) an "and" sentence ...	(3) ... when ...	(4) ... A is false ...	(5) ... or ...	(6) ... B is false
not ⏞	(A and B) ⏞	is equivalent to ⏞	(not A)) ⏞	or ⏞	(not B)) ⏞

Note that you say "is false" when you see the word "not".

A	B	A and B	not(A and B)	not A	not B	(not A) or (not B)
T	T	T	F	F	F	F
T	F	F	T	F	T	T
F	T	F	T	T	F	T
F	F	F	T	T	T	T

Here's the critical observation:
the columns for   not(A and B)   and   (not A) or (not B)   are identical!
Some people like to think of this as a sort of distributive law,
except that "and" changes to "or" in the distribution process.

IMPORTANCE OF ASSOCIATIVE LAWS

Think about this:
the reason that we can write things like   1 + 2 + 3   without ambiguity,
is because both   (1 + 2) + 3   and   1 + (2 + 3)   give the same result.
If they produced different results, then we'd have to write the parentheses every time we worked with these expressions.

You'll prove in the exercises that: (A or B) or C   is equivalent to   A or (B or C)
and
(A and B) and C   is equivalent to   A and (B and C)

Thus, we can write    A or B or C    and    A and B and C    without ambiguity!

Note that the truth table below involves three subsentences (A, B, and C),
so there are 2³ = 8 rows needed to cover all possible truth values.
Always list the eight rows in exactly the order that is shown here!

A	B	C	A and B	(A and B) and C	B and C	A and (B and C)
T	T	T	T	T	T	T
T	T	F	T	F	F	F
T	F	T	F	F	F	F
T	F	F	F	F	F	F
F	T	T	F	F	T	F
F	T	F	F	F	F	F
F	F	T	F	F	F	F
F	F	F	F	F	F	F

In the exercises, you will construct truth tables to prove all the following logical equivalences.

LOGICAL EQUIVALENCES

NAME/DESCRIPTION	1st sentence	... is equivalent to ...	2nd sentence	INTUITION
de Morgan's Law: negating an "and" sentence	not(A and B)	... is equivalent to ...	(not A) or (not B)	an AND sentence is false when A is false or B is false
de Morgan's Law: negating an "or" sentence	not(A or B)	... is equivalent to ...	(not A) and (not B)	an OR sentence is false when A is false and B is false
associativity of "AND"	(A and B) and C	... is equivalent to ...	A and (B and C)	the grouping doesn't matter in an "AND" sentence
associativity of "OR"	(A or B) or C	... is equivalent to ...	A or (B or C)	the grouping doesn't matter in an "OR" sentence
commutativity of "AND"	A and B	... is equivalent to ...	B and A	the order doesn't matter in an "AND" sentence
commutativity of "OR"	A or B	... is equivalent to ...	B or A	the order doesn't matter in an "OR" sentence
law of double negation	not(not A)	... is equivalent to ...	A	negating twice in succession gets you back to where you started
distributive law	A or (B and C)	... is equivalent to ...	(A or B) and (A or C)	similar to: a(b + c) = ab + ac
distributive law	A and (B or C)	... is equivalent to ...	(A and B) or (A and C)	similar to: a(b + c) = ab + ac
alternate form of an implication	A ⇒ B	... is equivalent to ...	(not A) or B	an implication is true when its hypothesis is false or its conclusion is true
contrapositive of an implication	A ⇒ B	... is equivalent to ...	(not B) ⇒ (not A)	an implication is equivalent to its contrapositive
negating an implication	not(A ⇒ B)	... is equivalent to ...	A and (not B)	an implication is false when its hypothesis is true and its conclusion is false
biconditional statement	A ⇔ B	... is equivalent to ...	(A ⇒ B) and B ⇒ A)	this is justification for the "double arrow" that is used for equivalence

We finish with two important results that allow us to "chain" results together:

LAW OF SYLLOGISM
The following compound mathematical sentence is true, for all possible truth values of P , Q , and R :

IF ( (P⇒Q) and (Q⇒R) ) THEN (P⇒R) Here's the intuition:
Whenever P is true, so is Q ; and,
whenever Q is true, so is R ; so,
whenever P is true, so is R .

LAW OF DETACHMENT
The following compound mathematical sentence is true, for all possible truth values of P and Q :

( P and (P⇒Q))   ⇒  Q Here's the intuition:
If P is true; and,
whenever P is true, so is Q ; then,
Q must be true.

On this exercise, you will not key in your answers.
However, you can check to see if your answer is correct.

LOGICAL EQUIVALENCES and PRACTICE WITH TRUTH TABLES

LOGICAL EQUIVALENCES

LOGICAL EQUIVALENCES and
PRACTICE WITH TRUTH TABLES