(Solved): 1. For the Boolean variables \( x, y, z \), let \( g(x, y, z)=x(\bar{y}+z)+\overline{(\bar{x} y)} ...

1. For the Boolean variables \( x, y, z \), let \( g(x, y, z)=x(\bar{y}+z)+\overline{(\bar{x} y)} \overline{(x+z)} \). (a) [3 marks]. Use the laws for Boolean algebra to write the formula for \( g \) in disjunctive normal form. (As a check, there are 4 terms in the sum and two of the terms are \( x \bar{y} \bar{z} \) and \( \bar{x} \bar{y} \bar{z} \).) (b) [3 marks]. Use Karnaugh maps to minimize the expression found in the previous part. (If you weren't able to use Boolean laws to obtain the DNF expression, then construct a Boolean table for \( g \), and find the DNF from the table.) 2. Suppose \( A, B \), and \( C \) are sets. For each of the following conditions, can you conclude that \( A=B \) ? If so, provide reasons. If not, provide a counter example. (a) \( [2 \) marks]. \( A \cup C=B \cup C \). (b) \( [2 \) marks \( ] . A \cap C=B \cap C \). (c) [2 marks]. \( A \cup C=B \cup C \) and \( A \cap C=B \cap C \). 3. Suppose \( X \) is a set. A partition of \( X \) is a set \( \left\{A_{1}, A_{2}, \cdots, A_{n}\right\} \) where - each of the \( A_{i} \) is non empty; - \( X=A_{1} \cup A_{2} \cdots \cup A_{n} \); - the sets \( A_{1}, A_{2}, \cdots, A_{n} \) are pairwise disjoint. (For example, \( A_{2} \cap A_{5}=\varnothing \).) (a) [2 marks]. Write down 2 different partitions of \( \{1,2,3,4\} \). (b) [2 marks]. Is the power set of \( \{1,2,3,4\} \) a partition of \( \{1,2,3,4\} \) ? If not, which of the three conditions above is not met? 4. [4 marks]. Let \( S \) be the set of all bit strings (a sequence of 1 s and 0 s) of length 2 or more. Let \( R \) be a relation on \( S \) of all pairs \( (x, y) \) where \( x \) and \( y \) are in \( S \) and \( x \) and \( y \) have the same first 2 bits. Is \( R \) is an equivalence relation? If so, what are the equivalence classes? RECURSION, INDUCTION AND COUNTING 5. (a) [4 marks]. Use the Euclidean algorithm to find the greatest common divisor \( g \) and the least common multiple \( \ell \) of the numbers 1149 and 525. Show your working. (b) [3 marks]. Use the extended Euclidean algorithm to find integers \( s \) and \( t \) such that \[ s \times 1149+t \times 525=6 \] (c) [1 mark]. Explain briefly why it is impossible to find integers \( s \) and \( t \) such that \[ s \times 1149+t \times 525=2 . \] (d) [2 marks]. Find integers \( s \) and \( t \) such that \[ s \times 1149+t \times 525=0 . \] Show your working. (Hint: this does not use the extended Euclidean algorithm. Think about \( \ell \).) 6. Consider the sequence of numbers \( \vec{a} \) defined recursively as follows: - Base case: \( a_{0}=3 \). - Recursive case: for \( n \geqslant 1 \), we have \( a_{n}=a_{n-1}+2 n+1 \). (a) [2 marks]. Calculate \( a_{1}, a_{2}, a_{3} \) and \( a_{4} \). (b) [4 marks]. The sequence \( \vec{a} \) is a quadratic sequence. Find integers \( p, q, r \) such that \[ a_{n}=p+q \times n+r \times n^{2} \] for every natural number \( n \). Be sure to justify how you got your answer. 7. [4 marks]. Consider the sequence of numbers \( \vec{b} \) defined recursively as follows: - Base case: \( b_{0}=3 \). - Recursive case: for \( n \geqslant 1 \), we have \( b_{n}=2 b_{n-1}+n \). Give a proof by induction that \( b_{n}=5 \times 2^{n}-n-2 \) for each natural number \( n \).