Lesson 6: Biconditionals, Truth Tables, and Logical Equivalence

Hi everyone! Read through the material below, watch the videos, and follow up with your instructor if you have questions.

Vocabulary

• converse
• if and only if
• logically equivalent
• contrapositive
• De Morgan’s Laws
• open sentence

When are two statements “the same”?

Introduction

A key idea in high school algebra is considering “when are two expressions the same” – for example, we learn that:

$$2x+6 = 2 (x+3)$$

One of the big ideas in algebra is that there are rules for determining when two expressions are equal (for example, it is the rule called “the distributive property” which shows that the expression on the left $2x+6$ is equal to the expression on the right $2(x+3)$).

Today we will consider a similar question in Logic – when are two statements “the same”? (Instead of saying they are “equal”, we call them “logically equivalent” – but our real goal is to understand when two statements mean the same thing). We will also learn some of the rules to determine when when statements are logically equivalent (for example, De Morgan’s Laws).

Definitions and Theorems

• The statement $Q\implies P$ is called the converse of $P\implies Q$.
  NOTE: A conditional statement and its converse express entirely different things!
• $P\iff Q$ means $(P\implies Q)\wedge (Q\implies P)$.  It is read “$P$ if and only if $Q$”.
• List of alternative phrases, all of which mean $P\iff Q$:
  • $P$ if and only if $Q$
  • $P$ is a necessary and sufficient condition for $Q$.
  • For $P$ is it necessary and sufficient that $Q$.
  • If $P$, then $Q$, and conversely.
• Two statements are logically equivalent if their truth values match up line-for-line in a truth table.  In symbols, we express this using the equals sign.
• RULE: We are allowed to replace a statement with a logically equivalent statement
• The contrapositive of $P\implies Q$ is $(\sim Q)\implies (\sim P)$.
• A sentence whose truth depends on the value of one or more variables is called an open sentence.  An open sentence is not a statement.

Comparing the conditional and its converse

Definition. If $P\implies Q$ is a conditional statement, then its converse is the statement $Q\implies P$.

Example 1: Do $P\implies Q$ and $Q\implies P$ mean the same thing?
Create truth tables for both expressions. Do they agree everywhere (that is, do they have the same truth value when starting with the same P and Q)?

However, it is sometimes the case that $P\implies Q$ and $Q\implies P$ are both true. For example:
($n$ is even) $\implies$ ($n$ is divisible by $2$), and
($n$ is divisible by $2$) $\implies$ ($n$ is even)

For this particular $P$ and $Q$, we have both $P\implies Q$ and $Q\implies P$, so we have $(P\implies Q)\wedge (Q\implies P)$. We have a shorthand notation for this situation, called the biconditional:

Definition. The biconditional $P \iff Q$ means $(P\implies Q)\wedge (Q\implies P)$.

Example 2. Find the truth table for $P \iff Q$.
Observe the truth values for $P \iff Q$ compared with the truth values of the original $P$ and $Q$. Any conclusions?

List of alternative phrases, all of which mean $P\iff Q$:

• $P$ if and only if $Q$
• $P$ is a necessary and sufficient condition for $Q$.
• For $P$ is it necessary and sufficient that $Q$.
• If $P$, then $Q$, and conversely.

Logical Equivalence

Definition. Two statements are logically equivalent if their truth values match up line-for-line in a truth table. In symbols, we express this using the equals sign.

Example 3: Is $P \Leftrightarrow Q$ logically equivalent to $(P \wedge Q) \vee(\sim P \wedge \sim Q)$?

The above example shows that $P \Leftrightarrow Q$ is logically equivalent to $(P \wedge Q) \vee(\sim P \wedge \sim Q)$. This means we can write an equals sign in between them:
$$P \Leftrightarrow Q = (P \wedge Q) \vee(\sim P \wedge \sim Q)$$
and we can always substitute/replace one of these expressions with the other. This is the first of many rules, or logical equivalences, we will discover – the rest of the lesson is about three more important logical equivalences.

Contrapositive

We learned above that the conditional $P\implies Q$ is not equivalent to the converse $Q\implies P$. However, the conditional is equivalent to another expression in which the positions of $Q$ and $P$ are reversed.

Example 4: Which of the following is logically equivalent to $P\implies Q$?

1. $Q\implies P$ (the converse)
2. $\sim Q\implies P$
3. $Q\implies \sim P$
4. $\sim Q \implies \sim P$ (the contrapositive)

De Morgan’s Laws

Example 5: Use truth tables to verify the following rules (called De Morgan’s Laws).

1. $\sim (P\wedge Q) = (\sim P \vee \sim Q)$
2. $\sim (P\vee Q) = (\sim P \wedge \sim Q)$