Hi everyone! This online lesson is provided as a resource – we will also go over this material in class.

Lesson 6: Biconditionals, Truth Tables, and Logical Equivalence

Topic. This lesson covers:

  1. Sec 2.4 Biconditional Statements
  2. Sec 2.5 Truth tables for Statements
  3. Sec 2.6 Logical equivalence

Learning Outcomes.

  • Identify instances of biconditional statements in both natural language and first-order logic, and translate between them.
  • Construct truth tables for statements.
  • Determine logical equivalence of statements using truth tables and logical rules.

Homework. There is one WeBWorK assignment on today’s material:

  1. WeBWorK: Assignment3-Sec2.1-2.6

Lecture Notes:

Lesson-6_-Logical-equivalenceDownload

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.

VIDEO: Biconditional

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)?

VIDEO: Logical Equivalence

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)

VIDEO: 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)

Exit Question

We often think of De Morgan’s Laws as a way of distributing a negation \sim across a conjunction \wedge or disjunction \vee. Describe this in your own words by completing the sentence “When we distribute a negation across a conjunction, \sim (P\wedge Q), we must…

Answer

Answers may vary – but one such answer might be:

“…we must apply the negation to both P and Q, and flip the conjunction \wedge into a disjunction \vee“.

Now try the same challenge for the second De Morgan’s Law!