Sadly I did not scan in my paper notes for this class, so all I have is this small cheatsheet.

# Vocabulary

• Axiom: A statement simply accepted to be true.
• Theorem: A statement proved to be true using the axioms.
• Lemma: A small theorem used in a specific proof to make the proof cleaner/easier.
• Proposition: A sentence with one of two truth values.
  • "The sky is blue."
  • "4 divides 5."
• Universe ($\mathcal{U}$): All possible elements within the realm of discussion.
• Open Sentence: A propsoition dependent on a variable within the universe.
• Universal Quantifier ($\mathrm{\forall }$): $(\mathrm{\forall }x)P(x)$ is true iff the truth set of $P(x)$ is $\mathcal{U}$.
• Existential Quantifier ($\mathrm{\exists }$): $(\mathrm{\exists }x)P(x)$ is true iff the truth set of $P(x)$ is non-empty.
• Unique Quantifier ($\mathrm{\exists }!$): $(\mathrm{\exists }!x)P(x)$ is true iff the truth set of $P(x)$ contains only one value.
• Set: A collection of unique elements that cannot contain itself. (Sets can be elements!)
• Argot: The standard human language used to describe logical statements.

# Logical Equivalences

Let $P$, $Q$, and $R$ be propositions about elements $x$ in universe $\mathcal{U}$. We write $P(x)$ iff proposition $P$ holds for some specific element $x\in \mathcal{U}$. If we instead write simply $P$, we consider some specific element $x\in \mathcal{U}$ where $P(x)$ holds.

• Double Negation:
  • $P⟺\mathrm{\neg }(\mathrm{\neg }P)$
• Commutative Law:
  • $P\vee Q⟺Q\vee P$
  • $P\wedge Q⟺Q\wedge P$
• Associative Law:
  • $P\vee (Q\vee R)⟺(P\vee Q)\vee R$
  • $P\wedge (Q\wedge R)⟺(P\wedge Q)\wedge R$
• Distributive Law:
  • $P\wedge (Q\vee R)⟺(P\wedge Q)\vee (P\wedge R)$
  • $P\vee (Q\wedge R)⟺(P\vee Q)\wedge (P\vee R)$
• DeMorgan's Law:
  • $\mathrm{\neg }(P\wedge Q)⟺\mathrm{\neg }P\vee \mathrm{\neg }Q$
  • $\mathrm{\neg }(P\vee Q)⟺\mathrm{\neg }P\wedge \mathrm{\neg }Q$
• Implication Properties:
  • $P⟹Q⟺\mathrm{\neg }P\vee Q$
  • $\mathrm{\neg }(P⟹Q)⟺P\wedge \mathrm{\neg }Q$
  • $\mathrm{\neg }(P\wedge Q)⟺P⟹\mathrm{\neg }Q$
  • $\mathrm{\neg }(P\wedge Q)⟺Q⟹\mathrm{\neg }P$
  • $(P⟺Q)⟺(P⟹Q)\wedge (Q⟹P)$
  • $P⟹(P⟹R)⟺(P\wedge Q)⟹R$
  • $P⟹(P\wedge R)⟺(P⟹Q)\wedge (P⟹R)$
  • $(P\wedge Q)⟹R⟺(P⟹R)\wedge (Q⟹R)$
  • Contraposition:
    • $P⟹Q⟺\mathrm{\neg }Q⟹\mathrm{\neg }P$
• Quantifiers and Negation: Normally, this would be written out in English instead of being symbolic. However, to avoid ambiguity, we write this symbolically.
  • $\mathrm{\neg }[(\mathrm{\exists }x)P(x)]⟺(\mathrm{\forall }x)[\mathrm{\neg }P(x)]$
  • $\mathrm{\neg }[(\mathrm{\forall }x)P(x)]⟺(\mathrm{\exists }x)[\mathrm{\neg }P(x)]$

# Set Equivalences

Let $A$ and $B$ be sets in some universe $\mathcal{U}$.

• $A^c=\{x\in \mathcal{U}:x\notin A\}$
• $A-B=A\mathrm{\setminus }B=A\cup B^c$
• $A\subset B=B^c\subset A^c$
• DeMorgan's Law:
  • ${\left(\bigcap _{A\subseteq \mathcal{U}}\mathcal{U}\right)}^c=\bigcup _{A\subseteq \mathcal{U}}(A^c)$
  • ${\left(\bigcup _{A\subseteq \mathcal{U}}\mathcal{U}\right)}^c=\bigcap _{A\subseteq \mathcal{U}}(A^c)$

# Argot of Logical Statements

Let $P$ and $Q$ be propositions.

• $P⟹Q$
  • $P$ implies $Q$.
  • If $P$, then $Q$.
  • $Q$, if $P$.
  • $P$ only if $Q$.
  • $Q$, when $P$.
  • $Q$ whenever $P$.
  • $P$ is sufficient for $Q$
  • $Q$ is necessary for $P$.
  • $Q$ is a necessary consequent of $P$.
• $P⟺Q$
  • $P$ implies $Q$, and conversely.
  • $P$ if and only if $Q$.
  • $P$ iff $Q$.
  • $P$ is equivalent to $Q$.
  • $P$ is necessary and sufficient for $Q$.