Notation
Notation is incredibly useful to write proofs. This page collects some notation that is used in this course.
Discrete Math Notation
In this part of the note we collect notation that you should have seen in CSE 191.
Logical Connectives
| Notation | Meaning |
| $P \wedge Q$ | The logical AND of boolean variables $P$ and $Q$ |
| $P \vee Q$ | The logical OR of boolean variables $P$ and $Q$ |
| $\neg P$ | Negation of the boolean variable $P$ |
| $P \implies Q$ | Logically equivalent to $\neg P\vee Q$ |
| $\forall x P(x)$ | For every $x$ (in the appropriate domain), the boolean predicate $P(x)$ is true |
| $\exists x P(x)$ | There exists at least one $x_0$ (in the appropriate domain), the boolean predicate $P(x_0)$ is true |
Set Connectives
| Notation | Meaning |
| $x\in S$ | Element $x$ belongs to set $S$ |
| $\bar{S}$ | Complement of $S$ |
| $S\subseteq T$ | $S$ is a subset of $T$ (they can be equal). Logically, $\forall x(x\in S\implies x\in T)$ |
| $S\supseteq T$ | $T\subseteq S$ |
| $S\cap T$ | Intersection of sets $S$ and $T$; i.e. $x\in S\cap T$ if and only if $x\in S\wedge x\in T$ |
| $S\cup T$ | Union of sets $S$ and $T$; i.e. $x\in S\cup T$ if and only if $x\in S \vee x\in T$ |
| $\emptyset$ | The empty set, i.e. the set with no elements |
| $S\setminus T$ | Set difference of $S$ and $T$. $S\setminus T= S\cap \bar{T}$ |
| $S\times T$ | Cartesian product of $S$ and $T$. $S\times T=\{(a,b)|a\in S\text{ and } b\in T\}$ |
| $[m]$ | The set $\{1,2,\dots,m\}$ |
Other Notation
| Notation | Meaning |
| $\left\lfloor \frac{m}{n} \right\rfloor$ | $m/n$ rounded down to the largest integer $\le m/n$ |
| $\left\lceil \frac{m}{n}\right\rceil$ | $m/n$ rounded up to the smallest integer $\ge m/n$ |