Sem IV Mathematics Summary

Cheatsheet Content

### Number Systems #### Number System Basics - **Definition:** Mathematical notation for representing numbers using digits/symbols. Defines the base (radix) of counting. - **Common Types:** - **Decimal (Base 10):** Digits 0-9 - **Binary (Base 2):** Digits 0-1 (Fundamental for computers, 1 bit, 8 bits = 1 byte) - **Octal (Base 8):** Digits 0-7 (Common in Unix file permissions, 1 octal digit = 3 binary bits) - **Hexadecimal (Base 16):** Digits 0-9 and A-F (A=10, B=11, C=12, D=13, E=14, F=15). Used in memory addressing, color codes. (1 hex digit = 4 binary bits / nibble) #### Binary to Decimal Conversion - **Method:** Multiply each binary digit by $2^n$ (where $n$ is positional power, starting from 0 at rightmost bit) and sum results. - **Example:** $(1011)_2 = 1 \cdot 2^3 + 0 \cdot 2^2 + 1 \cdot 2^1 + 1 \cdot 2^0 = 8 + 0 + 2 + 1 = (11)_{10}$ #### Decimal to Octal Conversion - **Method:** Repeatedly divide by 8, noting remainders. Read remainders from bottom up. - **Example:** $(324)_{10}$ - $324 \div 8 = 40$ R $4$ - $40 \div 8 = 5$ R $0$ - $5 \div 8 = 0$ R $5$ - Answer: $(504)_8$ #### Binary to Hexadecimal Conversion - **Method:** Group binary digits into sets of 4 from the right. Convert each group to its hexadecimal equivalent. - **Example:** $(101000)_2$ - Group: $0010 \vert 1000$ - $0010 = 2$ - $1000 = 8$ - Answer: $(28)_{16}$ #### Binary to Octal Conversion - **Method:** Group binary digits into sets of 3 from the right. Convert each group to its octal equivalent. - **Example:** $(10011001)_2$ - Group: $010 \vert 011 \vert 001$ - $010 = 2$ - $011 = 3$ - $001 = 1$ - Answer: $(231)_8$ - **Fractional Part Example:** $(10.11001101)_2$ - Integer: $010 = 2$ - Fractional (pad to groups of 3): $110 \vert 011 \vert 010 = 6, 3, 2$ - Answer: $(2.632)_8$ #### Hexadecimal to Binary Conversion - **Method:** Convert each hexadecimal digit into its 4-bit binary equivalent. - **Example:** $(2.6)_{16}$ - $2_{16} = 0010_2$ - $6_{16} = 0110_2$ - Answer: $(0010.0110)_2$ #### Hexadecimal to Decimal Conversion - **Method:** Multiply each hexadecimal digit by $16^n$ (positional power) and sum. - **Example:** $(13A2)_{16} = 1 \cdot 16^3 + 3 \cdot 16^2 + 10 \cdot 16^1 + 2 \cdot 16^0 = 4096 + 768 + 160 + 2 = (5026)_{10}$ - **Fractional Part Example:** $(BD17.93)_{16}$ - $B=11, D=13$ - $11 \cdot 16^3 + 13 \cdot 16^2 + 1 \cdot 16^1 + 7 \cdot 16^0 + 9 \cdot 16^{-1} + 3 \cdot 16^{-2}$ - $= 45056 + 3328 + 16 + 7 + 0.5625 + 0.01171875 \approx (48407.574)_{10}$ ### Set Theory & Relations #### Set Definition - **Definition:** A well-defined collection of distinct objects (elements/members). - **Notation:** $A = \{1, 2, 3, 4\}$ or $B = \{x \mid x \text{ is a positive integer } #### Power Set - **Definition:** The set of all subsets of a set A, including the empty set ($\emptyset$) and A itself. - **Cardinality:** If $|A| = n$, then $|P(A)| = 2^n$. - **Example:** $A = \{1, 2\} \rightarrow P(A) = \{\emptyset, \{1\}, \{2\}, \{1,2\}\}$ (4 subsets, $2^2 = 4$) #### Cardinality of a Set - **Definition:** The number of elements in a set A, written $|A|$. - **Example:** $A = \{2, 4, 6, 8\} \rightarrow |A| = 4$ - **Infinite Sets:** For natural numbers $\mathbb{N}$, cardinality is denoted as $\aleph_0$ (aleph-null). #### Inclusion-Exclusion Principle - **For two sets A and B:** $|A \cup B| = |A| + |B| - |A \cap B|$ - **For three sets A, B, and C:** $|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |B \cap C| - |A \cap C| + |A \cap B \cap C|$ #### Relation Definition - **Definition:** A relation $R$ from set A to set B is a subset of $A \times B$ (Cartesian product). It associates elements of A with elements of B. - **Example:** $A=\{1,2\}, B=\{a,b\} \rightarrow R = \{(1,a),(2,b)\}$ is a relation from A to B. - **'iff' Statement:** $aRb \Leftrightarrow (a,b) \in R$ - **Example:** $R = \{(a,b) \mid a \text{ divides } b\}$ means $aRb$ if and only if $a$ divides $b$. #### Digraph (Directed Graph) - **Definition:** A graphical representation of a relation. Elements are vertices (nodes), ordered pairs are directed arrows (edges). - **Self-loop:** If $(a,a) \in R$, it is shown as a loop at vertex $a$. #### Matrix Relation - **Definition:** A boolean (0/1) matrix $M$ where $M_{ij} = 1$ if $(a_i, b_j) \in R$, and $M_{ij} = 0$ if $(a_i, b_j) \notin R$. #### Set Operations Example - Let $N = \{1,2,3,...\}$, $A = \{1,2,4,6,8\}$, $B = \{2,4,5,9\}$, $C = \{x \mid x \text{ is a positive integer, } x \le 5\} = \{1,2,3,4,5\}$, $D = \{7,8,9\}$ - $A - B = \{1, 6, 8\}$ (Elements in A but not B) - $A \oplus B = (A \cup B) - (A \cap B) = \{1,2,4,5,6,8,9\} - \{2,4\} = \{1,5,6,8,9\}$ - $B \oplus C = \{2,4,5,9\} \oplus \{1,2,3,4,5\} = \{1,3,9\}$ - $C \oplus D = \{1,2,3,4,5\} \oplus \{7,8,9\} = \{1,2,3,4,5,7,8,9\}$ - $A \cup B = \{1,2,4,5,6,8,9\}$. Complement in $N$ is $N - (A \cup B) = \{3,7,10,11,...\}$ #### Inclusion-Exclusion Example - Given $|A|=6, |B|=8, |C|=6, |A \cup B \cup C|=11, |A \cap B|=3, |A \cap C|=2, |B \cap C|=5$. Find $|A \cap B \cap C|$. - Using formula: $|A \cup B \cup C| = |A|+|B|+|C| - |A \cap B| - |B \cap C| - |A \cap C| + |A \cap B \cap C|$ - $11 = 6 + 8 + 6 - 3 - 5 - 2 + |A \cap B \cap C|$ - $11 = 10 + |A \cap B \cap C|$ - $|A \cap B \cap C| = 1$ ### Logical Operations #### Statement Definition - **Definition:** A declarative sentence that is either TRUE (T) or FALSE (F), but not both. - **Examples:** 'The sun rises in the east' (True), '2 + 2 = 5' (False) - **Non-examples:** Questions ('Are you there?'), commands. #### Principle of Mathematical Induction (PMI) - **To prove P(n) is true for all $n \ge 1$:** 1. **Base Case:** Show P(1) is true. 2. **Inductive Step:** Assume P(k) is true for some $k \ge 1$ (Inductive Hypothesis). Then show P(k+1) is also true. - **Conclusion:** P(n) is true for all $n \ge 1$. #### Types of Logical Operations 1. **Negation ($\neg p$ or $\sim p$):** 'NOT p'. Reverses truth value. | p | $\neg$p | |---|---| | T | F | | F | T | 2. **Conjunction ($p \land q$):** 'p AND q'. True only when both p and q are true. | p | q | $p \land q$ | |---|---|-------| | T | T | T | | T | F | F | | F | T | F | | F | F | F | 3. **Disjunction ($p \lor q$):** 'p OR q'. True when at least one of p or q is true. | p | q | $p \lor q$ | |---|---|-------| | T | T | T | | T | F | T | | F | T | T | | F | F | F | 4. **Conditional ($p \rightarrow q$):** 'If p then q'. False only when p is true and q is false. | p | q | $p \rightarrow q$ | |---|---|-----------| | T | T | T | | T | F | F | | F | T | T | | F | F | T | 5. **Biconditional ($p \leftrightarrow q$):** 'p if and only if q'. True when p and q have the same truth value. - $p \leftrightarrow q \equiv (p \rightarrow q) \land (q \rightarrow p)$ #### Tautology, Contradiction, Contingency - **Tautology:** A compound statement that is always TRUE. - **Example:** $p \lor \neg p$ (Law of Excluded Middle) - **Contradiction:** A compound statement that is always FALSE. - **Example:** $p \land \neg p$ - **Contingency:** A compound statement that is neither a tautology nor a contradiction (true for some assignments, false for others). - **Example:** $p \leftrightarrow q$ ### Recurrence Relations (RR) & Numerical Methods #### Recurrence Relation - **Definition:** An equation defining a sequence where each term is a function of its preceding terms. - **Example:** $a_n = a_{n-1} + a_{n-2}$ (Fibonacci Sequence) - **Order:** Determined by the number of previous terms used. #### Types of Recurrence Relations 1. **Linear RR:** Each term is a linear combination of previous terms. - **Example:** $a_n = 2a_{n-1} + 3$ 2. **Non-linear RR:** Terms involve powers or products. - **Example:** $a_n = a_{n-1}^2$ 3. **Homogeneous RR:** $f(n) = 0$ (no separate function of n). - **Example:** $a_n = a_{n-1} + a_{n-2}$ 4. **Non-Homogeneous RR:** $f(n) \ne 0$. - **Example:** $a_n = 2a_{n-1} + n$ #### General Solution for RR - **Repeated Roots:** For characteristic equation with repeated root $r$: - $a_n = (C_1 + C_2 \cdot n) \cdot r^n$ - For k-fold repeated root: $a_n = (C_1 + C_2 n + C_3 n^2 + \dots + C_k n^{k-1}) \cdot r^n$ - **Distinct Roots:** For 2nd order linear homogeneous RR with distinct roots $r_1$ and $r_2$: - $a_n = C_1 \cdot r_1^n + C_2 \cdot r_2^n$ #### Difference Table - **Definition:** An organized table of values of a function $f(x)$ and its forward differences ($\Delta f, \Delta^2 f$, etc.) used in numerical analysis for interpolation. - **Finite Difference Table:** Records function values at equally spaced intervals, computes differences for polynomial interpolation and numerical integration. #### Formula for Finite Difference of functions ($\Delta^n f_0$) - The $n^{th}$ forward difference is: $\Delta^n f_0 = \sum_{r=0}^n (-1)^{n-r} C(n,r) f_r$ $= f_n - C(n,1)f_{n-1} + C(n,2)f_{n-2} - \dots + (-1)^n f_0$ #### Formula for Divided Difference of functions $f[x_0,x_1,x_2,...]$ - **First divided difference:** $f[x_0,x_1] = \frac{f(x_1)-f(x_0)}{x_1-x_0}$ - **Second divided difference:** $f[x_0,x_1,x_2] = \frac{f[x_1,x_2]-f[x_0,x_1]}{x_2-x_0}$ - **$n^{th}$ divided difference:** $f[x_0,\dots,x_n] = \frac{f[x_1,\dots,x_n]-f[x_0,\dots,x_{n-1}]}{x_n-x_0}$ #### RR Solution Example - **Problem:** Solve $a_n = 2a_{n-1} + 1$ with I.C. $a_1 = 7$. - This is a non-homogeneous RR. Find homogeneous + particular solution. - **Homogeneous:** $a_n^{(h)} = C \cdot 2^n$ - **Particular:** Assume $a_n^{(p)} = A$ (constant). - $A = 2A + 1 \Rightarrow A = -1$ - **General solution:** $a_n = C \cdot 2^n - 1$ - **Apply I.C. $a_1 = 7$:** $7 = C \cdot 2^1 - 1 \Rightarrow 2C = 8 \Rightarrow C = 4$ - **Answer:** $a_n = 4 \cdot 2^n - 1 = 2^{n+2} - 1$ ### Groups and Semi-Groups #### Commutativity - **Definition:** A binary operation $*$ on a set $G$ is commutative if for all $a, b \in G$: $a * b = b * a$. - **Example:** Addition: $a+b = b+a$ for all real numbers. #### Semi-Group - **Definition:** An algebraic system $(G, *)$ satisfying: 1. **Closure:** For all $a, b \in G \Rightarrow a * b \in G$ 2. **Associativity:** $(a * b) * c = a * (b * c)$ for all $a, b, c \in G$ - **Example:** $(\mathbb{Z}, +)$ (integers under addition) is a semi-group. 1. Sum of any two integers is an integer (Closure). 2. $(a+b)+c = a+(b+c)$ (Associativity). #### Monoid - **Definition:** A semi-group with an identity element. It is $(G, *)$ satisfying: 1. Closure 2. Associativity 3. **Identity:** $\exists e \in G$ such that $a * e = e * a = a$ for all $a \in G$ - **Example:** $(\mathbb{Z}, +)$ with identity $0$; $(\mathbb{Z}, \times)$ with identity $1$. #### Identity Element - **Definition:** An element $e$ in a set $G$ with operation $*$ is an identity if for all $a \in G$: $a * e = e * a = a$. - **Example:** $0$ is identity for addition ($a+0=a$); $1$ is identity for multiplication ($a \times 1=a$). #### Group - **Definition:** An algebraic structure $(G, *)$ satisfying: 1. Closure: $a * b \in G$ for all $a, b \in G$ 2. Associativity: $(a * b) * c = a * (b * c)$ 3. Identity: $\exists e \in G$ such that $a * e = e * a = a$ 4. Inverse: For each $a \in G, \exists a^{-1} \in G$ such that $a * a^{-1} = e$ - **Example:** $(\mathbb{Z}, +)$ (integers under addition). #### Abelian Group - **Definition:** A group $(G, *)$ is Abelian (or commutative) if in addition to the four group axioms: $a * b = b * a$ for all $a, b \in G$. - **Example:** $(\mathbb{Z}, +)$: $a+b = b+a$ for all integers, so it is Abelian. #### Cancellation Laws - In a group $(G,*)$, for all $a,b,c \in G$: - **Left Cancellation:** If $a * b = a * c \Rightarrow b = c$ - **Right Cancellation:** If $b * a = c * a \Rightarrow b = c$ #### Subgroup - **Definition:** A non-empty subset $H$ of a group $(G,*)$ is a subgroup if $(H,*)$ is itself a group. - **Subgroup test:** $H$ is a subgroup if and only if for all $a,b \in H \Rightarrow a * b^{-1} \in H$. #### Abelian Group Example - **Problem:** Let $G$ be the set of all non-zero real numbers with $a * b = ab/2$. Show $(G,*)$ is Abelian Group. - **Closure:** $a * b = ab/2$. Since $a,b \ne 0$ and real, $ab/2 \ne 0$ and is real. - **Associativity:** $(a * b) * c = (ab/2) * c = (ab/2)c/2 = abc/4$. $a * (b * c) = a * (bc/2) = a(bc/2)/2 = abc/4$. - **Identity:** $a * e = ae/2 = a \Rightarrow e = 2$. Check: $2 * a = 2a/2 = a$. - **Inverse:** $a * a^{-1} = aa^{-1}/2 = 2 \Rightarrow a^{-1} = 4/a$. Check: $a * (4/a) = (a \cdot 4/a)/2 = 4/2 = 2$. - **Commutativity:** $a * b = ab/2 = ba/2 = b * a$. - **Conclusion:** $(G,*)$ is an Abelian Group.