1. **Define Group, Semigroup, Monoid, Subgroup, Abelian Group, Cyclic Group, and Lattice with Properties** - **Group:** A set $G$ with a binary operation $\cdot$ is a group if it satisfies: 1. Closure: For all $a,b \in G$, $a \cdot b \in G$. 2. Associativity: For all $a,b,c \in G$, $(a \cdot b) \cdot c = a \cdot (b \cdot c)$. 3. Identity element: There exists $e \in G$ such that for all $a \in G$, $e \cdot a = a \cdot e = a$. 4. Inverse element: For each $a \in G$, there exists $a^{-1} \in G$ such that $a \cdot a^{-1} = a^{-1} \cdot a = e$. - **Semigroup:** A set $S$ with a binary operation $\cdot$ that is associative and closed. - **Monoid:** A semigroup with an identity element. - **Subgroup:** A subset $H$ of a group $G$ that itself forms a group under the operation of $G$. - **Abelian Group:** A group $G$ where the operation is commutative: $a \cdot b = b \cdot a$ for all $a,b \in G$. - **Cyclic Group:** A group generated by a single element $g$, i.e., every element in $G$ can be written as $g^n$ for some integer $n$. - **Lattice:** A partially ordered set $(L, \leq)$ where every pair of elements has a unique least upper bound (join) and greatest lower bound (meet). 2. **Algebraic System and Binary Operations** - An **algebraic system** is a set equipped with one or more operations (like addition, multiplication) that satisfy certain axioms. - Examples: 1. $(\mathbb{Z}, +)$ integers under addition. 2. $(\mathbb{R}, \cdot)$ real numbers under multiplication. - **Binary operations** take two elements from the set and return another element of the set, essential for defining algebraic structures. 3. **Boolean Algebra, De Morgan's Laws, and Complements** - Boolean algebra is a set $B$ with operations $+$ (OR), $\cdot$ (AND), and complement $\bar{a}$ satisfying axioms. - a) **De Morgan's Laws:** $$\overline{a + b} = \bar{a} \cdot \bar{b}$$ $$\overline{a \cdot b} = \bar{a} + \bar{b}$$ - b) For every $a \in B$, there exists a unique complement $\bar{a}$ such that: $$a + \bar{a} = 1, \quad a \cdot \bar{a} = 0$$ 4. **Semigroup and Monoid Examples** - a) Set $N$ of natural numbers with operation $a * y = \max(a,y)$: - Closure: max of two naturals is natural. - Associative: $\max(a, \max(b,c)) = \max(\max(a,b), c)$. - Identity: $0$ since $\max(a,0) = a$. - Hence, $(N, *)$ is a monoid. - b) Set $Z$ of integers with operation $a * y = \min(a,y)$: - Closure and associativity hold. - Identity would be an element $e$ such that $\min(a,e) = a$ for all $a$, which is $+\infty$ (not in $Z$). - So, $(Z, *)$ is a semigroup but not a monoid. 5. **Permutations with Repetitions** - a) For $n$ objects with repetitions of $n_1, n_2, ..., n_k$ identical objects, total permutations: $$\frac{n!}{n_1! n_2! \cdots n_k!}$$ - b) For "MISSISSIPPI": - Total letters $n=11$. - Counts: M=1, I=4, S=4, P=2. - Number of arrangements: $$\frac{11!}{1!4!4!2!} = 34650$$ 6. **Inclusion-Exclusion Principle and Application** - a) For sets $A,B,C$: $$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |B \cap C| - |A \cap C| + |A \cap B \cap C|$$ - b) Given: $|A|=21, |B|=26, |C|=29, |A \cap B|=74$ (likely typo, assume 7), $|B \cap C|=14, |C \cap D|=12$ (ignore D), $|A \cap B \cap C|=8$. Find $|C \text{ only}| = |C| - |B \cap C| - |A \cap C| + |A \cap B \cap C|$. Since $|A \cap C|$ not given, assume 0. So, $$|C \text{ only}| = 29 - 14 - 0 + 8 = 23$$ 7. **Number of Integral Solutions** - Solve $a_1 + a_2 + a_3 + a_4 = 20$ with bounds: $$1 \leq a_1 \leq 6, 1 \leq a_2 \leq 7, 1 \leq a_3 \leq 8, 1 \leq a_4 \leq 9$$ - Substitute $b_i = a_i - 1$: $$b_1 + b_2 + b_3 + b_4 = 16$$ with $0 \leq b_1 \leq 5$, $0 \leq b_2 \leq 6$, $0 \leq b_3 \leq 7$, $0 \leq b_4 \leq 8$. - Use inclusion-exclusion to count solutions respecting upper bounds. 8. **Binomial and Multinomial Theorems** - a) Binomial theorem: $$(x + y)^n = \sum_{k=0}^n \binom{n}{k} x^{n-k} y^k$$ - Coefficient of $x^3 y^7$ in $(2x - 9y)^{10}$: $$\binom{10}{3} (2)^3 (-9)^7 = 120 \times 8 \times (-4782969) = -4591650240$$ - b) Multinomial theorem: $$(x_1 + x_2 + \cdots + x_m)^n = \sum \frac{n!}{k_1! k_2! \cdots k_m!} x_1^{k_1} x_2^{k_2} \cdots x_m^{k_m}$$ where $\sum k_i = n$. 9. **Counting Problems** - a) Number of ways to seat 10 people so a certain pair is not together: - Total permutations: $10!$ - Treat pair as one unit: $9! \times 2!$ - So, ways with pair not together: $$10! - 9! \times 2 = 3628800 - 725760 = 2903040$$ - b) Number of 10-digit binary numbers with exactly six 1's: $$\binom{10}{6} = 210$$ 10. **Boolean Algebra and Lattices** - a) Uniqueness of 0 and 1 in Boolean algebra and complement: - If $0$ and $0'$ both satisfy $a + 0 = a$, then $0 = 0'$. - For every $a \in B$, complement $\bar{a}$ is unique. - b) Properties of lattices: - Commutativity: $a \vee b = b \vee a$, $a \wedge b = b \wedge a$. - Associativity: $(a \vee b) \vee c = a \vee (b \vee c)$. - Absorption: $a \vee (a \wedge b) = a$. - c) For $L = \{1,2,3,5,30\}$ with divisibility relation $R$: - $L$ is a lattice since every pair has gcd (meet) and lcm (join) in $L$.