Logical Equivalence

Return to Course Outline

Previous Lecture

Misc

Colloquium

“Waring’s Problem over Finite Fields.”

Background: Every positive integer can be written as a sum of 4 perfect squares, e.g., 4=1²+1²+1²+1², 8 = 2²+2²+0²+0², etc. Waring generalizes this to any power, not just squares: for every n, there is g(n), such that every positive integer can be written as a sum of g(n) nth powers.

Yesim Demiroglu, University of Rochester.

Thursday, February 1, 2:30 PM, Newton 203.

Extra credit for going and writing a paragraph or so about connections you make to the talk.

Questions?

Logical Equivalence

Section 2.2.

Equivalences for Conditionals

Rephrase the conditionals below without an explicit conditional, and the non-conditionals as conditionals:

• If it’s sunny then I wear a hat. Use the equivalence “P→ Q” is equivalent to “¬P ∨ Q,” then this becomes “it’s not sunny or I’m wearing a hat”
• It’s not really true that if x is a real number then calculating 3x+1 makes a genie appear. From “¬(P→ Q)” being equivalent to “P ∧ ¬Q,” this becomes “x is a real number but calculating 3x+1 does not make a genie appear.”
• Today it’s sunny and I’m not wearing a hat. This is of the form P ∧ ¬Q, so it’s a negated conditional: “it’s not true that if it’s sunny then I wear a hat.”
• Either Geneseo doesn’t have 3:00 AM classes, or we’ve all been lucky not to have to take (or teach) them. This is of the form ¬P ∨ Q, so it’s a conditional: “if Geneseo has 3 AM classes, then we’re lucky not to take them.”

Algebraically

Finish Progress Check 2.7.1 (using equivalences to prove that (P ∧ ¬ Q) → R ≡ P → (Q ∨ R), starting with (P ∧ ¬ Q) → R ≡ ¬(P ∧ ¬ Q) ∨ R).

1. (P ∧ ¬ Q) → R ≡ ¬(P ∧ ¬ Q) ∨ R
2. ≡ (¬P ∨ Q) ∨ R (deMorgan’s law)
3. ≡ ¬P ∨ (Q ∨ R) (associativity of or — you could prove this via a truth table)
4. ≡ P → (Q ∨ R) (equivalence for implication)

Key Ideas

Equivalences for conditionals are tricky, but they are helpful for rewriting conditionals as expressions involving the other logical operators or vice versa.

Equivalences provide a set of algebraic rules that can be used as an alternative to truth tables in proofs. Using the equivalences often makes the proof shorter if there are more than 2 or 3 variables.

Next

Introduction to sets.

Read the following parts of section 2.3:

1. Preview activity 1 (last half of page 52 through top 2 lines of page 54).
2. “Some Set Notation” (bottom 2/3 of page 55 through top 2/3 of page 56).
3. “The Empty Set” (bottom 1/3 of page 60).

Next Lecture