Logical Equivalences and Practice with Truth Tables

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 \Rightarrow B\,$ is (logically) equivalent to $\,(\text{not }B) \Rightarrow (\text{not }A)$

or

‘$(A \Rightarrow B) \ \ \Longleftrightarrow \ \ ((\text{not }B) \Rightarrow (\text{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'll 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 \text{ 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:

$\text{not}(A \text{ and } B)$ is equivalent to

$ (\text{not } A) \text{ or } (\text{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
$\overbrace{\text{not}}$	$\overbrace{(A\text{ and }B)}$	$\overbrace{\text{is equivalent to}}$	$\overbrace{(\text{not }A)}$	$\overbrace{\text{ or }}$	$\overbrace{(\text{not }B)}$

In particular, note that you say ‘is false’ when you see the word ‘not’.

$A$	$B$	$A \text{ and } B$	$\text{not}(A \text{ and } B)$	$\text{not } A$	$\text{not } B$	$(\text{not } A) \text{ or } (\text{not } B)$	$(\text{not}(A \text{ and } B))\iff ((\text{not } A) \text{ or } (\text{not } B))$
T	T	T	F	F	F	F	T
T	F	F	T	F	T	T	T
F	T	F	T	T	F	T	T
F	F	F	T	T	T	T	T

Here's the critical observation:
the columns for ‘$\,\text{not}(A \text{ and } B)\,$’ and ‘$\,(\text{not } A) \text{ or } (\text{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.

For simplicity, in the subsequent truth tables we will not include the last column—the one that shows that the ‘is equivalent to’ statement is always true.
This last column takes up a lot of space, and makes things look more complicated than they really are.
It is equally convincing to compare the two relevant columns, to show that they are identical.

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 \text{ or } B) \text{ or } C\,$ is equivalent to $\,A \text{ or } (B \text{ or } C)$
Below, it is shown that:

$(A \text{ and } B) \text{ and } C\,$ is equivalent to $\,A \text{ and } (B \text{ and } C)$
Thus (yeh!) we can write ‘$\,A \text{ or } B \text{ or } C\,$’ and ‘$\,A \text{ and } B \text{ and } C\,$’ without ambiguity.

Note that the truth table below involves three subsentences ($\,A\,$, $\,B\,$, and $\,C\ $),
so there are $\,2^3 = 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 \text{ and } B$	$(A \text{ and } B) \text{ and } C$	$B \text{ and } C$	$A \text{ and } (B \text{ 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	$1^{\text{st}}\,$ sentence	... is equivalent to ...	$2^{\text{nd}}\,$ sentence	INTUITION
de Morgan's Law: negating an ‘and’ sentence	$\text{not}(A \text{ and } B)$	... is equivalent to ...	$(\text{not }A) \text{ or } (\text{not }B)$	an ‘and’ sentence is false when $\,A\,$ is false or $\,B\,$ is false
de Morgan's Law: negating an ‘or’ sentence	$\text{not}(A \text{ or }B)$	... is equivalent to ...	$(\text{not }A) \text{ and }(\text{not }B)$	an ‘or’ sentence is false when $\,A\,$ is false and $\,B\,$ is false
associativity of ‘and’	$(A \text{ and }B) \text{ and }C$	... is equivalent to ...	$A \text{ and }(B \text{ and }C)$	the grouping doesn't matter in an ‘and’ sentence
associativity of ‘or’	$(A \text{ or }B) \text{ or }C$	... is equivalent to ...	$A \text{ or }(B \text{ or }C)$	the grouping doesn't matter in an ‘or’ sentence
commutativity of ‘and’	$A \text{ and } B$	... is equivalent to ...	$B \text{ and } A$	the order doesn't matter in an ‘and’ sentence
commutativity of ‘or’	$A \text{ or } B$	... is equivalent to ...	$B \text{ or } A$	the order doesn't matter in an ‘or’ sentence
law of double negation	$\text{not}(\text{not }A)$	... is equivalent to ...	$A$	negating twice in succession gets you back to where you started
distributive law	$A \text{ or }(B \text{ and }C\,)$	... is equivalent to ...	$(A \text{ or }B) \text{ and }(A \text{ or }C\,)$	similar to: $\,a(b + c) = ab + ac$
distributive law	$A \text{ and }(B \text{ or }C\,)$	... is equivalent to ...	$(A \text{ and }B) \text{ or }(A \text{ and }C\,)$	similar to: $\,a(b + c) = ab + ac$
alternate form of an implication	$A \Rightarrow B$	... is equivalent to ...	$(\text{not }A) \text{ or }B$	an implication is true when the hypothesis is false or the conclusion is true
contrapositive of an implication	$A \Rightarrow B$	... is equivalent to ...	$(\text{not }B) \Rightarrow (\text{not }A)$	an implication is equivalent to its contrapositive
negating an implication	$\text{not}(A \Rightarrow B)$	... is equivalent to ...	$A \text{ and }(\text{not }B)$	an implication is false when the hypothesis is true and the conclusion is false
biconditional statement	$A \Longleftrightarrow B$	... is equivalent to ...	$(A \Rightarrow B) \text{ and } (B \Rightarrow A)$	this is justification for the ‘double arrow’ that is used for equivalence

TAUTOLOGIES

A tautology is a mathematical sentence form that is always true.
For example, ‘$\,(A\text{ and }B)\Rightarrow A\,$’ is a tautology, as the truth table below confirms:

$A$	$B$	$A\text{ and }B$	$(A\text{ and }B)\Rightarrow A$
T	T	T	T
T	F	F	T
F	T	F	T
F	F	F	T

Here's the intuition for the tautology ‘$\,(A\text{ and } B)\Rightarrow A\,$’:
the only way an ‘and’ sentence is true is when both subsentences are true.
Thus, if ‘$\,A\text{ and }B\,$’ is true, then (in particular) $\,A\,$ must be true.
Check that ‘$\,(A\text{ and }B)\Rightarrow B\,$’ is also a tautology.

Note that a logical equivalence is a particular type of tautology—
one that tells us that two different sentence forms always have the same truth values, regardless of the truth values of the components.

Difference in usage between the words ‘tautology’ and ‘identity’

Although the words ‘identity’ and ‘tautology’ are both used in mathematics to refer to sentences that are always true,
there is a slight difference in usage.

The word ‘tautology’ tends to be used in logic, where the ‘pieces’ of the (always true) sentence have the choice of being either true or false.
For example, ‘$\,(A\text{ and }B)\Rightarrow A\,$’ is a tautology: the sentence is always true; the ‘pieces’ $\,A\,$ and $\,B\,$ can be true or false.
The sentence ‘$\,A\text{ or } (\text{not }A)\,$’ is another tautology: the sentence is always true; the ‘piece’ $\,A\,$ can be true or false.

The word ‘identity’, on the other hand, tends to be used for mathematical sentences outside of the realm of logic that are always true.
Here are some examples from algebra and trigonometry (and don't worry if something is unfamiliar here):

‘$\,x^2-y^2 = (x-y)(x+y)\,$’ is an identity from algebra.
Here, $\,x\,$ and $\,y\,$ represent real numbers.
No matter what real numbers $\,x\,$ and $\,y\,$ are chosen, the sentence is true.
You should recognize this as the formula for factoring a difference of squares.
‘$\,\sin^2\theta + \cos^2\theta = 1\,$’ is an identity from trigonometry.
Here, you can think of $\,\theta\,$ (the Greek letter ‘theta’) as a real number, or the measure of an angle.
This is such an important identity that it's given a name—the Pythagorean Identity.
(And—yes—there is a connection to the Pythagorean Theorem!)
‘$\,|a + b| \le |a| + |b|\,$’ is an identity from algebra.
Here, $\,a\,$ and $\,b\,$ represent real numbers.
Note that identities don't need to be statements of equality.

We finish with two important tautologies 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\Rightarrow Q)\text{ and }(Q\Rightarrow R))\,$ then $\,(P\Rightarrow 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\text{ and }(P\Rightarrow Q))\ \Rightarrow\ Q$

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

Master the ideas from this section
by practicing the exercise at the bottom of this page.

When you're done practicing, move on to:
Applying Logical Equivalences
to Algebraic and Geometric Statements

(MAX is 16; there are 16 different problem types.)