Simpson, Andrew. Discrete Mathematics by Example

Posted on April 5, 2017 by Ernesto Garbarino

Predicate Logic

Truth Tables

Precedence Level

\[ \begin{aligned} & \neg && \textrm{negation} && \textrm{not} \\ & \land && \textrm{conjunction} && \textrm{and} \\ & \lor && \textrm{disjunction} && \textrm{or} \\ & \Rightarrow && \textrm{implication} && \textrm{implies} \\ & \Leftrightarrow && \textrm{equivalence} && \textrm{if and only if} \\ \end{aligned} \]

Negation

\[ \begin{aligned} & \ \ \ p && \ \neg \ p \\ & \textit{true} && \textit{false} \\ & \textit{false} && \textit{true} \\ \end{aligned} \]

Conjunction

\[ \begin{aligned} & \ \ \ p && \ \ \ q && p \land q \\ & \textit{true} && \textit{true} && \textit{true} \\ & \textit{true} && \textit{false} && \textit{false} \\ & \textit{false} && \textit{true} && \textit{false} \\ & \textit{false} && \textit{false} && \textit{false} \\ \end{aligned} \]

Disjunction

\[ \begin{aligned} & \ \ \ p && \ \ \ q && p \lor q \\ & \textit{true} && \textit{true} && \textit{true} \\ & \textit{true} && \textit{false} && \textit{true} \\ & \textit{false} && \textit{true} && \textit{true} \\ & \textit{false} && \textit{false} && \textit{false} \\ \end{aligned} \]

Implication

\[ \begin{aligned} & \ \ \ p && \ \ \ q && p \Rightarrow q \\ & \textit{true} && \textit{true} && \textit{true} \\ & \textit{true} && \textit{false} && \textit{false} \\ & \textit{false} && \textit{true} && \textit{true} \\ & \textit{false} && \textit{false} && \textit{true} \\ \end{aligned} \]

Equivalence

\[ \begin{aligned} & \ \ \ p && \ \ \ q && p \Leftrightarrow q \\ & \textit{true} && \textit{true} && \textit{true} \\ & \textit{true} && \textit{false} && \textit{false} \\ & \textit{false} && \textit{true} && \textit{false} \\ & \textit{false} && \textit{false} && \textit{true} \\ \end{aligned} \]

Laws

\[ \begin{aligned} (\neg \ \textit{true}) &\Leftrightarrow \textit{false} &&[\textrm{3.1} \ \neg \ \textrm{definition}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% (\neg \ \textit{false}) &\Leftrightarrow \textit{true} &&[\textrm{3.1} \ \neg \ \textrm{definition}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% (\neg \ \neg \ p) &\Leftrightarrow p &&[\textrm{3.2 Double negation elimination}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% (p \land p) &\Leftrightarrow p &&[\textrm{3.3 Idempotency}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% (p \land \textit{true}) &\Leftrightarrow p &&[\textrm{3.4}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% (p \land \textit{false}) &\Leftrightarrow \textit{false} &&[\textrm{3.5}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% (p \land (\neg \ p)) &\Leftrightarrow \textit{false} &&[\textrm{3.6}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% (p \land q) &\Leftrightarrow (q \land p) &&[\textrm{3.7 Commutativity}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% p \land (q \land r) &\Leftrightarrow (p \land q) \land r &&[\textrm{3.8 Associativity}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \neg \ (p \land q) &\Leftrightarrow ((\neg \ p) \lor (\neg \ q)) &&[\textrm{3.9 de Morgan}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \neg \ (p \lor q) &\Leftrightarrow ((\neg \ p) \land (\neg \ q)) &&[\textrm{3.9 de Morgan}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% (p \lor p) &\Leftrightarrow p &&[\textrm{3.10 Idempotency}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% (p \lor \textit{false}) &\Leftrightarrow p &&[\textrm{3.11}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% (p \lor \textit{true}) &\Leftrightarrow \textit{true} &&[\textrm{3.12}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% p \lor (q \lor r) &\Leftrightarrow (p \lor q) \lor r &&[\textrm{3.13 Associativity}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% (p \lor q) &\Leftrightarrow (q \lor p) &&[\textrm{3.14 Commutativity}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% ((\neg \ p) \lor p) &\Leftrightarrow \textit{true} &&[\textrm{3.15 Excluded middle}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% p \lor (q \land r) &\Leftrightarrow (p \lor q) \land (p \lor r) &&[\textrm{3.16 Distributivity}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% (p \land q) \lor r &\Leftrightarrow (p \lor r) \land (q \lor r) &&[\textrm{3.16 Distributivity}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% p \land (q \lor r) &\Leftrightarrow (p \land q) \lor (p \land r) &&[\textrm{3.17 Distributivity}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% (p \lor q) \land r &\Leftrightarrow (p \land r) \lor (q \land r) &&[\textrm{3.17 Distributivity}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% (p \Rightarrow q) &\Leftrightarrow ((\neg \ p) \lor q) &&[\textrm{3.18} \Rightarrow \textrm{definition}]\\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% ((p \Leftrightarrow q) \Leftrightarrow r) &\Leftrightarrow (p \Leftrightarrow (q \Leftrightarrow r)) &&[\textrm{3.19 Associativity}]\\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% (p \Leftrightarrow q) &\Leftrightarrow (q \Leftrightarrow p) &&[\textrm{3.20 Commutativity}]\\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% (p \Leftrightarrow p) &\Leftrightarrow \textit{true} &&[\textrm{3.21}]\\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% (p \Leftrightarrow (\neg \ p)) &\Leftrightarrow \textit{false} &&[\textrm{3.22}]\\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% (p \Leftrightarrow q) &\Leftrightarrow ((p \Rightarrow q) \land (q \Rightarrow p)) &&[\textrm{3.23} \Leftrightarrow \textrm{definition}]\\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% (p \Rightarrow q) \land p &\Leftrightarrow q &&[\textrm{Modus ponens}]\\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% (p \Rightarrow q) \land (\neg \ q) &\Leftrightarrow \neg \ p &&[\textrm{Modus tollens}]\\ \end{aligned} \]

Rules for Proof Trees

Implication

\[\dfrac{p \Rightarrow q \quad p}{q} \ \ [\Rightarrow \textrm{elim}]\]

\[\dfrac{ \begin{array}{c}\lceil p\rceil _1\\ \vdots \\ q\\ \end{array} }{p \Rightarrow q} \ \ [\Rightarrow \textrm{intro}_1]\]

True

\[\dfrac{}{\mathit{true}} \ \ [\textit{true} \ \textrm{intro}]\]

Conjunction

\[\dfrac{p \land q}{p} \ \ [\land \ \textrm{elim}_1]\]

\[\dfrac{p \land q}{q} \ \ [\land \ \textrm{elim}_2]\]

\[\dfrac{p \quad q}{p \land q} \ \ [\land \ \textrm{intro}]\]

Disjunction

\[\dfrac{ \begin{array}{ccc} \lceil p\rceil _1 & \lceil q\rceil _1 & \\ \vdots & \vdots & \\ r & r & p \lor q\\ \end{array} }{r} \ \ [\lor \ \textrm{elim}_1]\]

\[\dfrac{p}{p \lor q} \ \ [\lor \ \textrm{intro}_1]\]

\[\dfrac{q}{p \lor q} \ \ [\lor \ \textrm{intro}_2]\]

Equivalence

\[\dfrac{p \Leftrightarrow q}{p \Rightarrow q} \ \ [\Leftrightarrow \textrm{elim}_1]\]

\[\dfrac{p \Leftrightarrow q}{q \Rightarrow p} \ \ [\Leftrightarrow \textrm{elim}_2]\]

\[\dfrac{p \Rightarrow q \quad q \Rightarrow p}{p \Leftrightarrow q} \ \ [\Leftrightarrow \textrm{intro}]\]

Negation

\[\dfrac{ \begin{array}{c} \neg \ p \\ \vdots \\ \mathit{false} \end{array} }{\ p} \ \ [\neg \ \textrm{elim}]\]

\[\dfrac{ \begin{array}{c} p \\ \vdots \\ \mathit{false} \end{array} }{\neg \ p} \ \ [\neg \ \textrm{intro}]\]

False Introduction

\[\dfrac{p \quad \neg \ p}{\mathit{false}} \ \ [\textit{false} \ \textrm{intro}]\]

Set Theory

Laws

Whenever a set such as \(S\), or an element such as \(s\) appear in a law, one should read “for any set \(S\) and for any element \(s\)” before considering such a law.

\[ \begin{aligned} \neg \ (s \in S) &\Leftrightarrow s \notin S &&[\textrm{4.1}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% x \in \emptyset &\Leftrightarrow \mathit{false} &&[\textrm{4.2}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% (S \subseteq T \land T \subseteq S) &\Leftrightarrow S = T &&[\textrm{4.3}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \emptyset &\subseteq S &&[\textrm{4.4}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% S &\subseteq S &&[\textrm{4.5}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \neg \ (S \subseteq T) &\Leftrightarrow S \nsubseteq T &&[\textrm{4.6}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% S \subseteq T &\Leftrightarrow (S \subset T \lor S = T) &&[\textrm{4.7}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% S \not\subset T &\Leftrightarrow \neg \ (S \subset T) &&[\textrm{4.8}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% S &\not\subset S &&[\textrm{4.9}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% S \subset T \ &\Rightarrow T \not\subset S &&[\textrm{4.10}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% S \supset T &\Leftrightarrow T \subseteq S &&[\textrm{4.11}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% a \in S \cup T &\Leftrightarrow (a \in S \lor a \in T) &&[\textrm{4.12}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% S \cup \emptyset &= S &&[\textrm{4.13}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% S \cup S &= S &&[\textrm{4.14}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% S \cup T &= T \cup S &&[\textrm{4.15 Commutativity}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% R \cup (S \cup T) &= (R \cup S) \cup T &&[\textrm{4.16 Associativity}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% S &\subseteq S \cup T &&[\textrm{4.17}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% a \in S \cap T &\Leftrightarrow (a \in S \land a \in T) &&[\textrm{4.18}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% S \cap \emptyset &= \emptyset &&[\textrm{4.19}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% S \cap S &= S &&[\textrm{4.20}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% S \cap T &= T \cap S &&[\textrm{4.21 Commutativity}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% R \cap (S \cap T) &= (R \cap S) \cap T &&[\textrm{4.22 Associativity}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% S \cap T &\subseteq S &&[\textrm{4.23}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% R \cup (S \cap T) &= (R \cup S) \cap (R \cup T) &&[\textrm{4.24 Distributivity}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% R \cap (S \cup T) &= (R \cap S) \cup (R \cap T) &&[\textrm{4.24 Distributivity}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% a \in S \setminus T &\Leftrightarrow (a \in S \land a \notin T) &&[\textrm{4.25}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% S \setminus \emptyset &= S &&[\textrm{4.26}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% S \setminus S &= \emptyset &&[\textrm{4.27}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \emptyset \setminus S &= \emptyset &&[\textrm{4.28}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% R \setminus (S \cup T) &= (R \setminus S) \cap (R \setminus T) &&[\textrm{4.29}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% R \setminus (S \cap T) &= (R \setminus S) \cup (R \setminus T) &&[\textrm{4.29}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% S \setminus T &\subseteq S &&[\textrm{4.30}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% S = T &\Leftrightarrow (x \in S \Leftrightarrow x \in T) &&[\textrm{4.31}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \#\emptyset &= 0 &&[\textrm{4.32}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \# (S \cap T) &= \# S - \# (S \setminus T) &&[\textrm{4.33}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \# (S \cup T) &= \# S + \# T - \# (S \cap T) &&[\textrm{4.34}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \# (S \setminus T) &= \# S - \# (S \cap T) &&[\textrm{4.35}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% S \in \mathbb{P} \ T &\Leftrightarrow S \subseteq T &&[\textrm{4.36}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \emptyset &\in \mathbb{P} \ S &&[\textrm{4.37}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% S &\in \mathbb{P} \ S &&[\textrm{4.38}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \# (\mathbb{P} \ S) &= 2^{\# (S)} &&[\textrm{4.39}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% x \in \bigcup X &\Leftrightarrow \exists S : X \ \bullet \ x \in S &&[\textrm{4.40}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% x \in \bigcap X &\Leftrightarrow \forall S : X \ \bullet \ x \in S &&[\textrm{4.41}] \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \end{aligned} \]

Glossary

BibTex

@book{simpson2002,
  title = "Discrete Mathematics by Example",
  author = "Simpson, A.C.",
  year = "2002",
  publisher = "McGraw-Hill",
}