SUNY Geneseo Department of Mathematics
Wednesday, February 6
Math 239 01
Spring 2019
Prof. Doug Baldwin
The equivalencies in the table at the end of section 2.2 are mainly important because they are often used to prove things about logical (Boolean) statements. You don’t need to memorize them in detail, but knowing what kinds of things they let you do, and thus when you might want to go look them up, would be good.
Section 2.2.
Prove that ¬(P ↔ Q) ≡ (P ∨ Q) ∧ (¬P ∨ ¬Q).
We wrote this proof formally in LaTeX. Here is the LaTeX source file, and here is the resulting PDF.
Prove that ¬(P → (Q ∨ R)) ≡ P ∧ ¬ Q ∧ ¬ R.
As with proofs based on other algebras, there are lots of ways this one could go. Try a couple of equivalencies that would rewrite parts of the lefthand side (or righthand side) and see if one suggests more that can complete the proof.
The basic reasoning we came up with is this: ¬(P → (Q ∨ R)) ≡ P ∧ ¬ (Q ∨ R) ≡ P ∧ ¬ Q ∧ ¬R
A formal presentation of this proof in LaTeX appears in the same source and PDF files as the truth table proof.
So far we’ve made precise some useful vocabulary (“and,” “or,” “not,” “if,” etc.) for theorems and proofs, and developed some algebra for reasoning about the underlying concepts.
How about the words “some” and “all” (e.g., “there is some integer n such that n, n+2, and n+4 are all prime”)?
A big part of what we need is a way to specify “some” or “all” of what — i.e., we need sets.
So read...
from section 2.3