EF Equivalence

Section 2.1 Equivalence

equivalent statements: 🔗
statements $A, B$ such that $A \leftrightarrow B$ is a tautology
$A \Leftrightarrow B$: 🔗
statements $A$ and $B$ are equivalent

Test 2.1.1. Equivalence of logical statements.

Statements

A

and

B

are logically equivalent if

A

and

B

always have the same output truth value whenever the same input truth values are substituted for the substatement variables in each. That is,

A \Leftrightarrow B

if $A$ and $B$ have the same truth table.

🔗

Worked Example 2.1.2. Testing logical equivalence.

🔗

Demonstrate that the following are equivalent statements.

$A :$	If it’s nice outside, I will ride my bike.
$B :$	It’s not nice outside, or I will ride my bike.

Solution.

Let

p

represent the substatement “it’s nice outside,” and let

q

represent the substatement “I will ride my bike.” Then the equivalence we want to establish is

p \to q \Leftrightarrow \neg p \lor q .

We can analyze the truth tables of both statements in the same table.

$p$	$q$	$\neg p$	$\neg p \lor q$	$p \to q$
$T$	$T$	$F$	$T$	$T$
$T$	$F$	$F$	$F$	$F$
$F$	$T$	$T$	$T$	$T$
$F$	$F$	$T$	$T$	$T$

We see that the two statements always have the same truth value in all rows of the truth table, so they are equivalent.

🔗

Note 2.1.3.

🔗

Worked Example 2.1.2 shows that the basic conditional connective “if … then …” can be constructed out of the basic connectives “not” and “or”.

🔗

Worked Example 2.1.4.

🔗

Demonstrate the equivalence

p \leftrightarrow q \Leftrightarrow \neg p \leftrightarrow \neg q .

Solution.

Again we build a truth table, and see that the “output” columns for the two statements are identical.

$p$	$q$	$\neg p$	$\neg q$	$p \leftrightarrow q$	$\neg p \leftrightarrow \neg q$
$T$	$T$	$F$	$F$	$T$	$T$
$T$	$F$	$F$	$T$	$F$	$F$
$F$	$T$	$T$	$F$	$F$	$F$
$F$	$F$	$T$	$T$	$T$	$T$

🔗

Proposition 2.1.5.

🔗

Logical equivalence has the following properties.

🔗
It is reflexive. That is, $A \Leftrightarrow A$ is always true.
🔗
It is symmetric. That is, whenever $A \Leftrightarrow B,$ then also $B \Leftrightarrow A .$
🔗
It is transitive. That is, whenever $A \Leftrightarrow B$ and $B \Leftrightarrow C,$ then also $A \Leftrightarrow C .$
🔗
Every pair of tautologies is an equivalent pair of logical statements.
🔗
Every pair of contradictions is an equivalent pair of logical statements.

🔗

Check your understanding.

🔗

Thinking in terms of truth tables, consider why each of the statements of Proposition 2.1.5 holds.

Elementary Foundations: An introduction to topics in discrete mathematics

Search Results: