CMPD133 Discrete Structure

--- 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 $$ ### :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\}$ ### :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$ ### :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 $$ ### :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$ #### `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)$== ## 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` = b2a3c - String with no element is called **null string** and is denoted as $\land$. - **A*** 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 W1 and W2 are two strings, the string consisting of W1 followed by W2, written $W_1\cdot W_2$ is called concatenation of W1 and W2 #### `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) # 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 # 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 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. #### 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> # 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 >$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 } ``` >1st path: $a\rightarrow a=(a,a)$ >2nd path: $a\rightarrow b=(a,b)$ >3rd path: $a\rightarrow b\rightarrow c=(a,c)$ >4th path: $a\rightarrow b\rightarrow c\rightarrow d=(a,d)$ >5th path: $a\rightarrow b\rightarrow c\rightarrow d\rightarrow e=(a,e)$ >6th path: $b\rightarrow c=(b,c)$ >7th path: $b\rightarrow c\rightarrow d=(b,d)$ >8th path: $b\rightarrow c\rightarrow e=(b,e)$ >9th path: $c\rightarrow d=(c,d)$ >10th path: $c\rightarrow e=(c,e)$ >11th 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)$ ## 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**