Discrete Mathematics

For \(f(g(.))\) to be onto, the values produced by \(g\) only have to be enough for \(f\) to reach every element of \(C\). That puts no one-to-one or onto condition on \(g\) itself.

Counterexample: \(A = \{1, 2\}\), \(B = \{p, q\}\), \(C = \{z\}\), with \(g(1) = g(2) = p\) and \(f(p) = f(q) = z\). Both \(f\) and \(f(g(.))\) are onto, yet \(g\) is not one-to-one (1 and 2 both go to \(p\)) and not onto (\(q\) is never reached). So (A), (B) and (C) are false.

Answer: D

“Exactly one mother” means: \(x\) has at least one mother \(y\), and nobody other than \(y\) is a mother of \(x\).

• (A) False: it only says \(x\) has some mother \(y\) and some non-mother \(z\); a second mother is not ruled out.
• (B) True: \(y\) is a mother of \(x\), and every \(z\) different from \(y\) is not a mother of \(x\).
• (C) False: it says that if \(y\) is a mother of \(x\), then some \(z\) equal to \(y\) is a mother of \(x\). That is always true (take \(z = y\)), so it neither forces a mother to exist nor limits how many there are.
• (D) True: \(\lnot \exists z\, (noteq(z, y) \land mother(z, x))\) is equivalent to \(\forall z\, (noteq(z, y) \to \lnot mother(z, x))\), so (D) says the same as (B).

Answer: B, D

Check the axioms for pointwise addition of functions from \(A\) to \(A\).

• Closure: \(f_1(n) + f_2(n)\) is again a non-negative integer, so \(f_1 \odot f_2 \in \mathrm{F}\).
• Associativity and commutativity come straight from ordinary addition at each \(n\).
• Identity: the zero function \(z(n) = 0\) is in \(\mathrm{F}\), and \(f \odot z = f\).
• Inverses fail: for the constant function \(f(n) = 1\), the inverse would need \(g(n) = -1\), which is not in \(A\).

So \((\mathrm{F}, \odot)\) is a commutative (Abelian) monoid but not a group. (A) and (C) are wrong because it is not a group; (D) is wrong because \(\odot\) is commutative.

Answer: B

Option A is the principle of mathematical induction: \(P(0)\) holds, and truth passes from each \(x\) to \(x + 1\), so it reaches 1, 2, 3, … and hence every natural number. It is true for every predicate \(P\).

Each other option fails for some predicate:

• B: take \(P(x)\) to be “\(x \le 5\)”. Both premises hold, but \(P(6)\) is false.
• C: take “\(x \le 1000\)”. Both premises hold, but \(P(1001)\) is false.
• D: take “\(x \ge 1000\)”. Both premises hold, but \(P(0)\) is false.

Answer: A

Each \(f \in \mathcal{F}\) is an \(n\)-bit vector, and \(f \preccurlyeq g\) compares the vectors position by position.

• Reflexive: \(f(x) \le f(x)\). Antisymmetric: \(f \preccurlyeq g\) and \(g \preccurlyeq f\) force \(f(x) = g(x)\) for every \(x\). Transitive, because \(\le\) is. So it is a partial order (B).
• Any two functions have a greatest lower bound, the pointwise minimum, and a least upper bound, the pointwise maximum, so it is a lattice (C): the Boolean lattice of subsets of \(\{1, \ldots, n\}\).
• It is not symmetric: the all-0 function is \(\preccurlyeq\) the all-1 function, but not the other way round. So A is false, and D is false because an equivalence relation must be symmetric.

Answer: B, C

A one-to-one and onto function (a bijection) exists between two finite sets exactly when they have the same number of elements. Let \(|A| = n \ge 1\).

• Condition (i) gives \(|B| = n\).
• Condition (ii) gives \(|A \cup B| = |A \times A| = n^{2}\).

The union of two \(n\)-element sets has between \(n\) elements (when \(A = B\)) and \(2n\) elements (when they are disjoint), so \(n \le n^{2} \le 2n\), which forces \(n \le 2\).

• \(n = 1\): take \(A = B = \{a\}\); then \(|A \cup B| = 1 = 1^{2}\).
• \(n = 2\): take disjoint \(A = \{a, b\}\) and \(B = \{c, d\}\); then \(|A \cup B| = 4 = 2^{2}\).

Both values occur, so \(|A|\) has 2 possible values.

Answer: 2

By Cayley’s formula, the complete graph on \(n\) labelled vertices has \(n^{n-2}\) spanning trees, so \(K_{4}\) has \(4^{4-2} = 16\).

A direct count agrees. A spanning tree on 4 vertices has 3 edges, and \(K_{4}\) has 6 edges, so there are \(\binom{6}{3} = 20\) sets of 3 edges. Three edges on four vertices fail to form a tree only when they make a triangle (leaving the fourth vertex isolated), and \(K_{4}\) has 4 triangles: \(20 - 4 = 16\). They are the 12 paths and the 4 stars on A, B, C, D.

Answer: 16

Take a proper colouring with exactly \(k\) colours. Its colour classes are independent sets that split the \(n\) vertices into \(k\) groups.

• (B) True: the largest of the \(k\) classes has at least \(n/k\) vertices.
• (C) True: every two colour classes must be joined by at least one edge, otherwise they could share a colour and \(k - 1\) colours would do. That gives at least \(\binom{k}{2} = k(k - 1)/2\) edges.
• (A) False: the 5-cycle needs 3 colours but contains no triangle.
• (D) False: the complete graph \(K_{k}\) has chromatic number \(k\), yet every vertex has degree \(k - 1\).

Answer: B, C

• (A) False: \((a \mathbin{\lozenge} b) \mathbin{\lozenge} c = a + 2b + 2c\), but \(a \mathbin{\lozenge} (b \mathbin{\lozenge} c) = a + 2(b + 2c) = a + 2b + 4c\).
• (B) True: \(\square\) is ordinary multiplication, which is associative.
• (C) False: \(a \mathbin{\lozenge} (b \mathbin{\square} c) = a + 2bc\), while \((a \mathbin{\lozenge} b) \mathbin{\square} (a \mathbin{\lozenge} c) = (a + 2b)(a + 2c)\). For \(a = b = c = 1\) these are 3 and 9.
• (D) True: \(a \mathbin{\square} (b \mathbin{\lozenge} c) = a(b + 2c) = ab + 2ac = (a \mathbin{\square} b) \mathbin{\lozenge} (a \mathbin{\square} c)\). It also holds from the right, since \((b + 2c)a = ba + 2ca\).

So multiplication distributes over \(\lozenge\), because \(\lozenge\) is a linear combination of its operands, but not the other way round.

Answer: B, D

“\(X\) when \(Y\)” means “whenever \(Y\) holds, \(X\) holds”, which is the implication \(Y \rightarrow X\).

• The condition \(Y\) is “student scores more than 50% marks”, that is \(q\).
• The consequence \(X\) is “fail grade cannot be given”, that is \(\neg p\).

So the statement is \(q \rightarrow \neg p\). Option B drops the negation and says a fail grade can be given. Option D, \(\neg p \rightarrow q\), is the converse of \(q \rightarrow \neg p\) and is not equivalent to it, and option C has neither the right direction nor the negation.

Answer: A