Primary reference: Chapter 2 (Logic), Chapter 7 (Proving Non-Conditional Statements), particularly sections 7.1 and 7.3, Chapter 9 (Disproof) of Book of Proof by Richard Hammack
Content covered in this unit includes:
The meaning of the terms statement and open sentence
The meaning of the logical connectives and, or, not, implies, and if and only if ($\wedge$, $\vee$, $\sim$, $\Rightarrow$, and $\Leftrightarrow$, respectively)
The use of truth tables to describe a logical statement (possibly including any of the logical connectives mentioned above) or to show that two logical statements are (or are not) equivalent
The meaning of the universal quantifier ($\forall$) and the existential quantifier ($\exists$)
The strategy for proving a universally quantified (”for all”) statement:
<aside>
Proposition. For all $x$, $P(x)$.
Proof. Suppose $x$. … Therefore $P(x)$.
</aside>
The strategy for proving an existentially quantified (”there exists”) statement:
<aside>
Proposition. There exists an $x$ such that $P(x)$.
Proof. Let $x$ be… [describe a specific example]. … Therefore $P(x)$.
</aside>
The strategy for disproving a false statement $P$, which is to prove $\mathord{\sim} P$
De Morgan’s laws for negating statements with and or or:
$$ \begin{aligned} \mathord{\sim} (P \wedge Q) \quad&=\quad (\mathord{\sim} P) \vee (\mathord{\sim} Q) \\ \mathord{\sim} (P \vee Q) \quad&=\quad (\mathord{\sim} P) \wedge (\mathord{\sim} Q) \\ \end{aligned} $$
The equivalence of a conditional statement with its contrapositive:
$$ P \Rightarrow Q \quad=\quad (\mathord{\sim} Q) \Rightarrow (\mathord{\sim} P) $$
The negation of a universally or existentially quantified statement:
$$ \begin{aligned} \mathord{\sim} (\forall x, P(x)) \quad&=\quad \exists x, \mathord{\sim} P(x) \\ \mathord{\sim} (\exists x, P(x)) \quad&=\quad \forall x, \mathord{\sim} P(x) \\ \end{aligned} $$
The strategy for proving a biconditional (”if and only if”) statement:
<aside>
Proposition. $P$ if and only if $Q$.
Proof. Suppose $P$. … Therefore $Q$. Conversely, suppose $Q$.
…
Therefore $P$. We conclude that $P$ if and only if $Q$.
</aside>