Logical Equivalence

Return to List of Lectures

Previous Lecture

Questions?

Truth Tables

Example (Progress Check 2.3). Build a truth table for P ↔ Q, i.e., (Q → P) ∧ (P → Q)

A truth table is a table of when statements are true or false, lets you break complicated logical expressions into simpler parts. Each row corresponds to one combination of truth values for variables, but be sure you cover all possible combinations. You need 2^s rows if you have s variables.

P	Q	Q → P	P → Q	(Q → P) ∧ (P → Q)
T	T	T	T	T
T	F	T	F	F
F	T	F	T	F
F	F	T	T	T

Logical Equivalence

Section 2.2

de Morgan’s Laws:

• ¬(P ∧ Q) ≡ ¬P ∨ ¬Q
• ¬(P ∨ Q) ≡ ¬P ∧ ¬Q

Question: How to make intuitive sense of equivalencies involving conditionals with conjunctions & disjunctions? For instance, why is “if P then Q or R” equivalent to “if P and not Q then R”?

• Suppose P → (Q ∨ R), e.g., “if it’s Monday then I’m in Math 239 or I’m having lunch”
• Further suppose P is true, so Q is true or R is true (or both), e.g., “it really is Monday, so I’m in Math 239, or I’m having lunch, or doing both”
• Now finally suppose Q is false, e.g., “it’s Monday but I’m not in Math 239.” Since one of Q and R must be true, the only choice left is that R is true (e.g., “I’m definitely having lunch”)

Example (Progress Check 2.7). Use equivalencies to prove that P → (Q ∨ R) ≡ (P ∧ ¬Q) → R

(P ∧ ¬Q) → R ≡ ¬(P ∧ ¬Q) ∨ R ≡ ¬P ∨ Q ∨ R ≡ ¬P ∨ (Q ∨ R) ≡ P → (Q ∨ R)

Problem set

Next

Sets

Read section 2.3 from start through “Some Set Notation,” plus subsection “The Empty Set”

i.e., bottom 1/3 of page 52 through top 2/3 of page 56, plus bottom 1/4 of page 60.

Next Lecture