---
# System prepended metadata

title: CMPD133 Discrete Structure
tags: [notes]

---

---
title: CMPD133 Discrete Structure
tags: notes
---


# Chapter 1: Fundamentals

## Sets
- A collection of data or objects
- Each entity is called element or member, defined by symbol ∈
- Order is not important
- Repeated element is not important

$$
A = \{ 1, 2, 3, 4, 5\}
\\B = \{2,3,1,5,4\}
\\C = \{1,2,1,3,4,5\}
$$

- Thus sets A and B are equal

$$
A = B,\space 1\in A,\space 2\in A\\but \space 7 \notin A
$$

<br>

### :book: Ways to describe set
:::success
- $A = \{x\mid1\le x\le5\}$
- $A = \{x\mid x\text{ is an integer from 1 to 5, both included}\}$
- $A=\{x\mid x+1;\space0\le x\le5\}$
:::

- If set has no element, it is called the empty set, denoted by $\{\}$ or $\varnothing$
- Let $D=\{6,7,8\}$, $A$ and $D$ are called **Disjoint Sets** because it have no element in common
- Set $A$ is called **finite** if it has $n$ district elements, where $n\in N$ (nonnegative number)
- The number of its elements, $n$ is called the **cardinality** of $R$, denoted by $|R|=5$
- A set that is not finite is called infinite
    - e.g. $C=\{x\mid x\ge1\}$

<br>

### :book: Subsets

- If <ins>every element</ins> of A is also an element of B, we say that **A is a subset of B**, or A is contained in B, written as $A\subseteq B$
    - $\subset$ means **proper subset**, where $A\subset B,A\ne B$

<br>

### :book: Power set

- A set that contains all its subset as its element
- Denoted by P(A)

$$
A=\{1,2\}\\
P(A)=\{\{1\},\{2\},\{1,2\},\varnothing\}\\
P|(A)|=4
$$

<br>

### :book: Operation on Sets

#### `Complement`

- Given $U$, a universal set, $U-A$ is called the **complement** of $A$, denoted by $A'$, or $A^c$

$$
A'=\{x\mid x\notin A\}
$$

- If $A$ and $B$ are two sets, the **complement of $B$ with respect to $A$** is a set that contain all elements that belong to $A$ but not $B$, denoted by $A-B$

<br>

#### `Symmetric Difference`

- Given $A$ and $B$ are two sets. Their **symmetric difference** is a set that contain all elements that belong to $A$ or $B$ but not to both A and B, denoted by $A\oplus B.$

$$
A\oplus B =\{x\mid (x\in A \text{ AND }x\notin B)\\\text{OR}\\(x\in B\text{ AND }x\notin A)\}
$$

- In simpler term, ==$(A\cup B)-(A\cap B)$==

<br>

## Sequence

- A list of objects in its order
- List might be ended after $n, n\in N$ and it is named as **Finite Sequence**
- List that have no ending value is called as **Infinite Sequence**
- Elements might have redundancy
- If the sequence depends on previous value, it is called **Recursive Sequence**

:::info
:notebook: **Example:** Recursive Sequence
$$
A_n=A_{n-1}+5;\,\\ A_1=1;\\2\le n\le \infty
$$
$$
\text{where: }A_2=A_1+5\\
\qquad\quad A_3=A_2+5
$$
:::

- If the sequence not depend on the previous value, where value can be directly retrieved, it is called **Explicit Sequence**

:::info
:notebook: **Example:** Explicit Sequence
$$
A_n=n^2+1;\\
1\le n\le\infty
$$
$$
\text{where: }A_1=1+1=2\\
\qquad\quad A_2=4+1=5\\
\qquad\quad\; A_3=9+1=10
$$
:::

- Both sequence can have an **Increasing** or **Decreasing** sequence

### :pushpin: String

- Sequences or letters or other symbols that is written without commas are also referred as strings
- An infinite string such as `abababa...` may be regarded as infinite sequnce of `a,b,a,b,a,b,a...`
- The **set corresponding to sequence** is simply the set of all distinct elements in the sequence
    - e.g. 1: `1,4,8,9,2...` is `{1,4,8,9,2...}`
    - e.g. 2: `a,b,a,b,a,b...` is simply `{a,b}`
- Order is taken into account since string is a sequence. `baac` is different from `acab`
- Repitition in a string can be specified by superscript.
    - `bbaaac` = b<sup>2</sup>a<sup>3</sup>c
- String with no element is called **null string** and is denoted as $\land$.
- **A<sup>*</sup>** denote all the strings over $A$, including null string

:::info
:notebook: **Example:**
$$
A=\{a,b,c,\ldots,z\}\\
\text{then: }A^*=\{aaa, computer,denda, ...\}
$$
:::

:::info
:notebook: **Example:**
$$
\text{let }X=\{a,b\}\\
X^*=\{a,b,baba,\land,b^2a^{29},\ldots\}
$$
:::

- Number of elements in any string $A$ is called Elements' Length, denoted as $|A|$
    - If $A = abcde...z$, then $|A|=26$

#### `Concatenation`

- If W<sub>1</sub> and W<sub>2</sub> are two strings, the string consisting of W<sub>1</sub> followed by W<sub>2</sub>, written $W_1\cdot W_2$ is called concatenation of W<sub>1</sub> and W<sub>2</sub>

#### `Subsequence`

- A new sequence can be build from original sequence, but the order of elements must remains

:::info
:notebook: **Example:**

$T=a,a,b,c,q$
where $T_1=a,\;T_2=a,\;T_3=b,\;T_4=c,\;T_5=q$

$S=b,c$ is a subsequence of $T$
but  $R=c,b$ is not a subsequence of $T$
:::

## Matrix

***Diagonal matrix***

$$
A=
\begin{bmatrix}
8&0&0&0\\
0&3&0&0\\
0&0&7&0\\
0&0&0&1
\end{bmatrix}
$$

***Transposition matrix***

$$
A=
\begin{bmatrix}
2&-3&5\\
6&1&3\\
\end{bmatrix}\quad
A^T=
\begin{bmatrix}
2&6\\
-3&1\\
5&3
\end{bmatrix}
$$

***Symmetrical matrix***

$$
A=\begin{bmatrix}
\color{red}{1}&2&-3\\
2&\color{red}{4}&5\\
-3&5&\color{red}{6}
\end{bmatrix}
$$

### :pushpin: Boolean Matrix

- A matrix where all entries are either 1 or 0 only
- There are 3 operations on Boolean:
    - Join $\lor$ (or)
    - Meet $\land$ (and)
    - Product $\bigodot$ (same as normal matrix product)
    
<br>

# Chapter 2: Logic

$\lor$ : **Conjunction** (OR)
$\land$ : **Disjunction** (AND)

**De Morgan Laws**: $\neg(p\land q)=\neg p\lor\neg q$

## Conditional statements

- ==If p then q==
- p implies q
- if p, q
- p only if q
- p is sufficient for q
- q if p
- q is necessary for p

$p\rightarrow q$

| $p$ | $q$ | $p\rightarrow q$ |
| :--------: | :--------: | :--------: |
| T | T | T |
|T|F|F|
|F|T|T|
|F|F|T|

- **Conditional** = $p\rightarrow q$
- **Converse** = $q\rightarrow p$
- **Inverse** = $\neg p\rightarrow\neg q$
- **Contrapositive** = $\neg q\rightarrow\neg p$

### Biconditional

- ==p if and only if q==
- p is necessary and sufficient for q
- if p, then q, and conversely

$p\leftrightarrow q$

|$p$|$q$|$p\leftrightarrow q$|
|:---:|:---:|:---:|
|T|T|T|
|T|F|F|
|F|T|F|
|F|F|T|

- A statement that is true for all possible values is called a **tautology**
    - also for two logically equivalent statement
- A statement that is always false for all possible values of its propositional variables is called a **contradiction**.
    - $p\land\neg p$
- A statement that can be either true of false, depending on the truth values of its propositional variables is called a **contingency**.
    - $(p\land q)\land(p\lor q)$

### Quantifier

**Universal Quantification $\forall$**
"For all values of x, P(x) is true"

**Existential Quantification $\exists$**
"There exists a value of x for which P(x) is true"

### Theorem

**Commutative**
- $p\lor q\equiv q\lor p$
- $p\land q\equiv q\land p$

**Associative**
- $p\lor(q\lor r)\equiv(p\lor q)\lor r$
- $p\land(q\land r)\equiv(p\land q)\land r$

**Distributive**
- $p\lor(q\lor r)\equiv(p\lor q)\land(p\lor r)$
- $p\land(q\land r)\equiv(p\land q)\lor(p\land r)$

**Idempotent**
- $p\lor p\equiv p$
- $p\land p\equiv p$

**Negation**
- $\neg(\neg p)\equiv p$
- $\neg(p\lor q)\equiv(\neg p)\land(\neg q)$
- $\neg(p\land q)\equiv(\neg p)\lor(\neg q)$

## Induction

1. Test if $P(n_0)$ is correct.
2. Get the $P(k)$.
3. Get the $P(k+1)$.
4. Expand RHS
5. Identify P(k) from LHS

<br>

# Chapter 3: Counting Method

## Permutation

- An order of objects, number of sequence

$_nP_r=\frac{n!}{(n-r)!}$

## Combination

- Order does not matter
- We count number of subset

$_nC_r=\frac{n!}{r!(n-r)!}$

## Pigeonhole

#### Example 1

If 8 people were chosen, at least 2 people were being born in the same day (Monday to Sunday). Show that by using pigeonhole principle

<span style="color:DarkBlue">Because there are 8 people and only 7 days per week, so **Pigeonhole Principle** says that, at least two or more people were being born in the same day.</span>

#### Example 2

Show that if any five numbers from 1 to 8 are chosen, two of them will add to 9.

<div style="color:darkblue">

$A_1=\{1,8\}\quad A_2=\{2,7\}\quad A_3=\{3,6\}\quad A_4=\{4,5\}$

Each of the 5 numbers chosen must belong to one of these sets. $n=4,\,m=5$. Since there are only four sets, the **pigeonhole principle** tells us that two of the chosen numbers belong to the same set. These numbers add up to 9.
</div>

<br>

# Chapter 4: Relations

## Product Set

#### Example

>$A=\{1,2,3\}$ and $B=\{r,s\}$
$A\times B=\{(1,r),(1,s),(2,r),(2,s),(3,r),(3,s)\}$
$B\times A=\{(r,1),(r,2),(r,3),(s,1),(s,2),(s,3)\}$

Therefore $A\times B\ne B\times A$

## Relation

- Relation between 2 set wheere its value was determined by a condition. All elements in that relation must fulfill the condition

### Set

#### Example 1

>$A=\{1,2,3\}$ and $B=\{r,s\}$
Condition: Relation from A to B
$R=\{(1,r),(2,s),(3,r)\}$

#### Example 2

>$A=\{1,2,3,4,5\}$ and $B=\{1,2,3,4,5\}$
>
>a R b if and only if a < b
>
>$R=\{(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),\\(2,5),(3,4),(3,5),(4,5)\}$

### Matrix

#### Example 1

>$M_R=\begin{bmatrix}
1&0&0&1\\
0&1&1&0\\
1&0&1&0\\
\end{bmatrix}$
>
>Find the Set for Relation
>
>$R=\{(a_1,b_1),(a_1,b_4),(a_2,b_2),\\(a_2,b_3),(a_3,b_1),(a_3,b_3)\}$

### Diagraph

#### Example 1

>$A=\{a,b,c,d\}$
$R=\{(a,a),(a,b),(b,a),\\(b,b),(b,c),(b,d),(c,d),(d,a)\}$
>
>Show R in a diagraph
>
```graphviz
digraph set {
    node[shape=circle];
    rankdir="LR";
    a->a
    a->b
    b->a
    b->b
    b->c
    b->d
    c->d
    d->a
}
```

|Vertex|a|b|c|d|
|---|:---:|:---:|:---:|:---:|
|In-degree|3|2|1|2|
|Out-degree|2|4|1|1|

### Path in relation

- Path length *n* will involve ***n+1*** elements

#### Example 1

```graphviz
digraph path{
    node[shape=circle];
    rankdir="LR"
    1->2
    2->2
    2->3
    2->4
    2->5
    4->3
    5->4
    5->1
}
```

- $\pi_1$: 1,2,5,4,3 is a path length 4 from vertex 1 to vertex 3
- $\pi_2$: 1,2,5,1 is a path length 3 from vertex to itself
- A path that start and ends at the same vertex is called a **cycle**

### Reachability

- Reachability is a concept in which there is a realtion between x and y in whatever length possible
- Written as $xR^\infty y$

#### Example 1

>$A=\{a,b,c,d,e\}$
>$R=\{(a,a),(a,b),(b,c),(c,d),(c,e),(d,e)\}$
>Identify all $xR^\infty y$

```graphviz
digraph reach{
    node[shape=circle];
    rankdir="LR";
    a->a
    a->b
    b->c
    c->d
    c->e
    d->e
}
```

>1<sup>st</sup> path: $a\rightarrow a=(a,a)$
>2<sup>nd</sup> path: $a\rightarrow b=(a,b)$
>3<sup>rd</sup> path: $a\rightarrow b\rightarrow c=(a,c)$
>4<sup>th</sup> path: $a\rightarrow b\rightarrow c\rightarrow d=(a,d)$
>5<sup>th</sup> path: $a\rightarrow b\rightarrow c\rightarrow d\rightarrow e=(a,e)$
>6<sup>th</sup> path: $b\rightarrow c=(b,c)$
>7<sup>th</sup> path: $b\rightarrow c\rightarrow d=(b,d)$
>8<sup>th</sup> path: $b\rightarrow c\rightarrow e=(b,e)$
>9<sup>th</sup> path: $c\rightarrow d=(c,d)$
>10<sup>th</sup> path: $c\rightarrow e=(c,e)$
>11<sup>th</sup> path: $d\rightarrow e=(d,e)$
>
>$xR^\infty y=(a,a),(a,b),(a,c),(a,d),(a,e),(b,c),\\(b,d),(b,e),(c,d),(c,e),(d,e)$

<br>

## Properties of relation

- Reflexive and Irreflexive
- Symmetric
- Asymmetric
- Antisymmetric

### Reflexive

$\begin{bmatrix}
\color{red}{1}&x&x\\
x&\color{red}{1}&x\\
x&x&\color{red}{1}\\
\end{bmatrix}$

### Irreflexive

$\begin{bmatrix}
\color{red}{0}&x&x\\
x&\color{red}{0}&x\\
x&x&\color{red}{0}\\
\end{bmatrix}$

### Symmetric

$\begin{bmatrix}
1&\color{blue}{1}&\color{blue}{0}\\
\color{blue}{1}&0&\color{blue}{1}\\
\color{blue}{0}&\color{blue}{1}&0\\
\end{bmatrix}$

### Antisymmetric

$\begin{bmatrix}
1&\color{blue}{1}&\color{blue}{1}\\
\color{blue}{0}&0&\color{blue}{1}\\
\color{blue}{0}&\color{blue}{0}&1\\
\end{bmatrix}$

### Asymmetric

$\begin{bmatrix}
\color{red}{0}&\color{blue}{1}&\color{blue}{1}\\
\color{blue}{0}&\color{red}{0}&\color{blue}{1}\\
\color{blue}{0}&\color{blue}{0}&\color{red}{0}\\
\end{bmatrix}$

### Transitive

$M_R\,^2=M_R$

## Equivalence Relation

- If the relation is **reflexive**, **symmetric**, and **transitive**