164 lines
5.0 KiB
Markdown
164 lines
5.0 KiB
Markdown
---
|
||
type: theoretical
|
||
---
|
||
|
||
## Sets
|
||
|
||
A **set** is an unordered collection of unique objects (elements) with no duplicates.
|
||
|
||
### Notation
|
||
- $x \in A$: "x is an element of set A."
|
||
- $x \notin A$: "x is not an element of set A."
|
||
|
||
### Intervals of $\mathbb{R}$
|
||
An **interval** is a subset of $\mathbb{R}$ (the real numbers) defined by two endpoints $a$ and $b$. Any real number between $a$ and $b$ belongs to the interval.
|
||
|
||
### Cardinality
|
||
The **cardinality** of a set $S$ is the number of elements it contains, denoted $|S|$.
|
||
- **Finite Set**: A set with a finite number of elements. Example: $S = \{a, b, c\}$, $|S| = 3$.
|
||
- **Infinite Set**: A set that is not finite. Example: $\mathbb{N}, \mathbb{Z}, \mathbb{R}$.
|
||
- **Power Set**: For a finite set $S$, the cardinality of its power set $P(S)$ (set of all subsets of $S$) is $2^{|S|}$.
|
||
|
||
**Example**: For $S = \{a, b, c\}$, $P(S)$ contains $8 = 2^3$ subsets.
|
||
|
||
---
|
||
|
||
## Set Operations
|
||
|
||
Let $U$ be the universal set, and let $A$ and $B$ be subsets of $U$:
|
||
|
||
- **Union**: $A \cup B = \{x \mid x \in A \lor x \in B\}$
|
||
- **Intersection**: $A \cap B = \{x \mid x \in A \land x \in B\}$
|
||
- **Set Difference**: $A \setminus B = \{x \mid x \in A \land x \notin B\}$
|
||
- **Complement**: $\bar{A} = U \setminus A$, the set of all elements not in $A$.
|
||
|
||
---
|
||
|
||
## Proof Styles for Set Properties
|
||
|
||
### Annotated Linear Proof (ALP)
|
||
A **chain-of-equivalences proof** involves showing the equivalence of two sets step by step.
|
||
|
||
**Example**: Prove $A \cup (B \cup C) = (A \cup B) \cup C$.
|
||
|
||
- Start from $x \in A \cup (B \cup C)$ and simplify:
|
||
$$
|
||
x \in A \cup (B \cup C) \iff x \in A \lor (x \in B \lor x \in C) \iff (x \in A \lor x \in B) \lor x \in C \iff x \in (A \cup B) \cup C.
|
||
$$
|
||
|
||
- Conclude that the left-hand side equals the right-hand side.
|
||
|
||
---
|
||
|
||
## Sequences
|
||
|
||
A **sequence** is an ordered list of objects where repetition is allowed, and the order matters.
|
||
|
||
### Examples
|
||
1. Finite sequence: $1, 2, 3, 5, 7$ (length 5).
|
||
2. Infinite sequence: $0, 2, 4, 6, \ldots$ (continues indefinitely).
|
||
3. A sequence differs from a set: $1, 2, 3$ is not the same as $3, 2, 1$.
|
||
|
||
### Specifying Sequences
|
||
1. **Recursive Definition**:
|
||
- Example: $s_0 = 3$, $s_n = 2 \cdot s_{n-1} + 7$, defines $3, 13, 33, \ldots$.
|
||
2. **Explicit Definition**:
|
||
- Example: $s_n = n^2$ defines $0, 1, 4, 9, 16, \ldots$.
|
||
|
||
---
|
||
|
||
## Characteristic Function
|
||
|
||
The **characteristic function** of a set $A \subseteq U$ is a function $f_A : U \to \{0, 1\}$:
|
||
$$
|
||
f_A(x) =
|
||
\begin{cases}
|
||
1, & \text{if } x \in A, \\
|
||
0, & \text{if } x \notin A.
|
||
\end{cases}
|
||
$$
|
||
|
||
### Purpose
|
||
Characteristic functions represent sets mathematically and are useful for computations.
|
||
|
||
**Example**:
|
||
- $U = \{a, b, c, d, e\}$, $A = \{b, d\}$.
|
||
- Representation of $U$: $(1, 1, 1, 1, 1)$.
|
||
- Representation of $A$: $(0, 1, 0, 1, 0)$.
|
||
|
||
---
|
||
|
||
## Strings and Languages
|
||
|
||
### Formal Languages
|
||
1. **Alphabet ($\Sigma$)**: A non-empty set of symbols (letters).
|
||
2. **Word (String)**: A finite sequence of symbols from $\Sigma$.
|
||
- Example: $\Sigma = \{a, b\}$, string: $babab$.
|
||
3. **Empty String ($\epsilon$)**: A string with no symbols ($|\epsilon| = 0$).
|
||
4. **Language ($L$)**: A subset of $\Sigma^*$, the set of all possible strings over $\Sigma$.
|
||
Regex. Used for [Pattern matching](Pattern%20matching.md)
|
||
### Regular Sets and Expressions
|
||
1. $\alpha \cdot \beta$ (concatenation): Combine two sets of strings.
|
||
2. $\alpha | \beta$ (union): Combine strings from either set.
|
||
3. $\alpha^*$ (Kleene star): All strings formed by repeatedly concatenating elements of $\alpha$.
|
||
|
||
**Example**:
|
||
- Let $L$ correspond to $(a | b)^*(c | \epsilon)$.
|
||
- True/False:
|
||
- $abbac \in L$: True.
|
||
- $abccc \in L$: False.
|
||
- $abaa \in L$: False.
|
||
|
||
|
||
---
|
||
|
||
## Integers
|
||
|
||
### Primes
|
||
- **Prime Number**: A positive integer greater than 1 with only two divisors: 1 and itself.
|
||
- Examples: $2, 3, 5, 7$.
|
||
- **Euclid's Theorem**: There are infinitely many primes.
|
||
|
||
**Proof Sketch**:
|
||
1. Assume a finite list of primes $p_1, p_2, \ldots, p_n$.
|
||
2. Let $q = (p_1 \cdot p_2 \cdot \ldots \cdot p_n) + 1$.
|
||
3. If $q$ is prime, it’s not in the list.
|
||
4. If $q$ is not prime, it must be divisible by some prime not in the list.
|
||
|
||
### Prime Factorization
|
||
Every integer $n > 1$ can be uniquely expressed as a product of primes:
|
||
$$
|
||
n = p_1^{k_1} \cdot p_2^{k_2} \cdot \ldots \cdot p_s^{k_s}.
|
||
$$
|
||
|
||
**Examples**:
|
||
1. $60 = 2^2 \cdot 3 \cdot 5$.
|
||
2. $168 = 2^3 \cdot 3 \cdot 7$.
|
||
|
||
---
|
||
|
||
## Matrices and Boolean Operations
|
||
|
||
### Boolean Operations
|
||
- **OR ($\lor$)**: $a \lor b = \max(a, b)$.
|
||
- **AND ($\land$)**: $a \land b = \min(a, b)$.
|
||
|
||
**Example**: For $a, b \in \{0, 1\}$:
|
||
- $1 \lor 0 = 1$.
|
||
- $1 \land 0 = 0$.
|
||
|
||
---
|
||
|
||
## Mathematical Structures
|
||
|
||
### Arity and Notation
|
||
- **Arity**: The number of arguments an operation takes.
|
||
- **Unary**: Takes one argument (e.g., complement of a set).
|
||
- **Binary**: Takes two arguments (e.g., addition: $x + y$).
|
||
- **Nullary**: Takes no arguments (e.g., constant: $1$).
|
||
|
||
**Prefix/Infix/Postfix Notation**:
|
||
- **Prefix**: Operator first (e.g., $+ x y$).
|
||
- **Infix**: Operator between arguments (e.g., $x + y$).
|
||
- **Postfix**: Operator last (e.g., $x y +$).
|