1. **Show that $t \wedge s$ can be derived from the premises $p \to q$, $q \to \neg r$, $r$, $p \lor (t \wedge s)$.** - From $r$ and $q \to \neg r$, since $r$ is true, $q$ must be false to avoid contradiction. - From $p \to q$ and $q$ false, $p$ must also be false. - Since $p$ is false, $p \lor (t \wedge s)$ reduces to $t \wedge s$. - Therefore, $t \wedge s$ can be derived. 2. **Using mathematical induction, prove that $8^n - 3^n$ is divisible by 5 for all natural numbers $n$.** - Base case ($n=1$): $8^1 - 3^1 = 8 - 3 = 5$, divisible by 5. - Inductive hypothesis: Assume $8^k - 3^k$ is divisible by 5. - Inductive step: $$8^{k+1} - 3^{k+1} = 8 \cdot 8^k - 3 \cdot 3^k = 8 (8^k - 3^k) + 3^k (8 - 3)$$ - By hypothesis, $8^k - 3^k$ is divisible by 5; $8 - 3 = 5$ is divisible by 5. - Hence, $8^{k+1} - 3^{k+1}$ is divisible by 5. - By induction, the statement is true for all $n$. 3. **Let $f: G \to G'$ be a group homomorphism from $(G, *)$ to $(G', \Delta)$. (i) Show that $f(e) = e'$, where $e$ and $e'$ are identity elements of $G$ and $G'$ respectively. **Proof:** - For any $a \in G$, $f(a) = f(a * e) = f(a) \Delta f(e)$. - Multiplying both sides on the right by $f(e)^{-1}$ gives $f(a) \Delta e' = f(a)$. - Thus, $f(e) = e'$. (ii) For any $a \in G$, prove that $f(a^{-1}) = [f(a)]^{-1}$. **Proof:** - Since $a * a^{-1} = e$, applying $f$ yields $$f(a) \Delta f(a^{-1}) = f(e) = e'.$$ - So, $f(a^{-1})$ is the inverse of $f(a)$ in $G'$. - Hence $f(a^{-1}) = [f(a)]^{-1}$. 4. **Show that $*$ defined on $\mathbb{R} \setminus \{-\frac{1}{2}\}$ by $a * b = a + b + 2ab$ is an abelian group operation.** - **Closure:** For $a,b \neq -\frac{1}{2}$, $a + b + 2ab$ is a real number. - **Associativity:** Check $a*(b*c) = (a*b)*c$: $$b*c = b + c + 2bc,$$ $$a*(b*c) = a + (b + c + 2bc) + 2a(b + c + 2bc) = a + b + c + 2bc + 2ab + 2ac + 4abc,$$ $$(a*b)*c = (a + b + 2ab) + c + 2(a + b + 2ab)c = a + b + 2ab + c + 2ac + 2bc + 4abc,$$ - Both expressions are equal; so associative. - **Identity:** Find $e$ such that $a*e = a$: $$a + e + 2ae = a \Rightarrow e + 2ae = 0 \Rightarrow e(1 + 2a) = 0.$$ - Since $a \neq -\frac{1}{2}$, $1 + 2a \neq 0$, so $e=0$. - **Inverses:** Find $a^{-1}$ such that $a * a^{-1} = 0$: $$a + a^{-1} + 2 a (a^{-1}) = 0,$$ $$a^{-1} (1 + 2a) = -a,$$ $$a^{-1} = \frac{-a}{1 + 2a}.$$ - **Commutativity:** $$a * b = a + b + 2ab = b + a + 2ba = b * a.$$ - Thus, $(\mathbb{R} \setminus \{-\frac{1}{2}\}, *)$ is an abelian group. 5. **Show that the premises are inconsistent: - If Raja misses many classes, then he fails in the final examination. - If Raja fails in the final examination, then he is uneducated. - If Raja reads a lot of books, then he is not uneducated. - Raja misses many classes and reads a lot of books.** - Let $M$ = Raja misses many classes, $F$ = Raja fails final, $U$ = Raja is uneducated, $R$ = Raja reads a lot. - Premises: - $M \to F$ - $F \to U$ - $R \to \neg U$ - $M \wedge R$ - From $M$, $F$ follows. - From $F$, $U$ follows. - From $R$, $\neg U$ follows. - Thus, $U$ and $\neg U$ both hold: a contradiction. - Hence premises are inconsistent. 6. **Find code words generated by parity check matrix $H$ and encoding function $e: B^3 \to B^6$.** - Given $H = \begin{bmatrix}1 & 1 & 1 \\ 0 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}$. - Encoding maps 3-bit vectors $(b_1 b_2 b_3)$ to 6-bit code words. - Typically, code words $c$ satisfy $Hc^T=0$. - As this is a parity check matrix of size $5 \times 3$, but maps from $B^3$ to $B^6$, likely encoding is $e(x) = (x, Px)$ where $P$ is a matrix so that $H e(x)^T=0$. - Without explicit $P$, we list all vectors $x$ in $B^3$ and their codewords $e(x)$: - $000 \to 000000$ - $001 \to$ find codeword satisfying parity conditions - $010 \to ...$ - $011 \to ...$ - $100 \to ...$ - $101 \to ...$ - $110 \to ...$ - $111 \to ...$ (Explicit calculation of each codeword requires $P$ or more info, which is not provided.) 7.**(i) Using truth tables, prove $p \to (q \to p) \equiv \neg p \to (p \to q)$.** | $p$ | $q$ | $q \to p$ | $p \to (q \to p)$ | $p \to q$ | $\neg p$ | $\neg p \to (p \to q)$ | |-----|-----|-----------|--------------------|-----------|----------|-------------------------| | T | T | T | T | T | F | T | | T | F | T | T | F | F | T | | F | T | F | T | T | T | T | | F | F | T | T | T | T | T | - Columns for $p \to (q \to p)$ and $\neg p \to (p \to q)$ match. - So they are logically equivalent. 7.**(ii) Prove every subgroup of a cyclic group is cyclic.** - Let $G = \langle g \rangle$ be cyclic and $H \leq G$. - If $H = \{e\}$, trivial cyclic. - If not, let $h = g^m$ be element of $H$ with smallest positive exponent $m$. - Claim: $H = \langle h \rangle$. - For arbitrary $g^k \in H$, by division algorithm $k = mq + r$ with $0 \le r < m$. - Then $g^k = g^{mq + r} = g^{mq} g^r = (g^m)^q g^r = h^q g^r$. - Since $h^q \in H$ and $g^k \in H$, $g^r = g^{-mq}g^k = h^{-q} g^k \in H$. - By minimality of $m$, $r=0$. - Thus, $g^k = h^q$ so $H = \langle h \rangle$. - Hence $H$ is cyclic.