"Discrete Mathematics" — Practice

Question 1

Which of the following is logically equivalent to p implies q?

Accepted Answer

C

Question 2

How many reflexive relations are there on a set with 4 elements?

Accepted Answer

A

Question 3

A simple graph has 6 vertices with degrees 3, 3, 3, 3, 3, 3. How many edges does it have?

Accepted Answer

B

Question 4

Consider the poset of divisors of 12 under divisibility. Is it a lattice, and is it a Boolean algebra?

Accepted Answer

The divisors are 1, 2, 3, 4, 6, 12.

It is a lattice. Meet is the greatest common divisor and join is the least common multiple, and both of any two divisors of 12 are themselves divisors of 12, so every pair has both.

It is not a Boolean algebra. A Boolean algebra must be complemented, meaning every element x has a y with meet 1 and join 12.

Test x = 2. The candidate complement must have gcd 1 with 2, so it must be odd: either 1 or 3. With 1 the join is 2, not 12. With 3 the join is 6, not 12. So 2 has no complement.

The underlying reason is that 12 = 2 squared times 3 has a repeated prime factor. The divisor lattice of a product of distinct primes, such as 30, is isomorphic to a power set and therefore is a Boolean algebra; a repeated factor destroys complementation.

Question 5

Which of the following is a group under the given operation? Justify by checking the axioms.
(i) The set of odd integers under addition.
(ii) The set of non-zero rationals under multiplication.
(iii) The set of 2 by 2 real matrices under multiplication.

Accepted Answer

Check closure first in each case, since that is where most candidates fail.

(i) Odd plus odd is even, so the set is not closed under addition. It is not even a semigroup, and no further axiom needs testing.

(ii) Closure holds, since the product of two non-zero rationals is a non-zero rational. Multiplication of rationals is associative. The identity is 1. Every non-zero rational p/q has inverse q/p, which is again a non-zero rational. So this is a group, and it is abelian since rational multiplication commutes.

(iii) Closure and associativity hold, and the identity matrix is an identity. But inverses fail: a matrix with determinant zero has no multiplicative inverse, and such matrices are in the set. So this is a monoid, not a group. Restricting to invertible matrices gives the general linear group.

Only (ii) is a group.

Question 6

In how many ways can 10 identical chocolates be distributed among 4 distinct children so that each child receives at least one?

Accepted Answer

This is stars and bars with a non-empty constraint, and the objects being identical is what makes the method apply.

Give each child one chocolate first, using 4 of the 10. That satisfies the constraint and leaves 6 chocolates to distribute freely.

Distributing 6 identical objects into 4 distinct boxes with no constraint is C(6 + 4 - 1, 4 - 1) = C(9, 3).

C(9,3) = 84.

Equivalently, the direct formula for the non-empty case is C(r - 1, n - 1) = C(9, 3) = 84, which is the same computation.

The critical assumption is that the chocolates are identical. Had they been distinguishable, the count with no constraint would be 4 to the power 10, and the non-empty count would require inclusion-exclusion instead.

Question 7

Solve a_n = 6a_(n-1) - 9a_(n-2) with a_0 = 2 and a_1 = 9.

Accepted Answer

Write the characteristic equation: r squared = 6r - 9, that is, r squared minus 6r plus 9 = 0.

This factors as (r - 3) squared = 0, so r = 3 is a repeated root.

A repeated root requires the form a_n = (A + Bn) times 3 to the n. Using A times 3 to the n alone would give only one independent solution and could not satisfy two initial conditions.

Apply a_0 = 2: (A + 0) times 1 = A = 2.

Apply a_1 = 9: (A + B) times 3 = 9, so A + B = 3, giving B = 1.

The solution is a_n = (2 + n) times 3 to the n.

Verify at n = 2. The recurrence gives 6(9) - 9(2) = 54 - 18 = 36. The formula gives (2 + 2) times 9 = 36. They agree, which confirms both the repeated-root form and the constants.

Question 8

A connected simple planar graph has 12 vertices and every face is bounded by exactly 3 edges. How many edges and faces does it have?

Accepted Answer

Use the face-edge counting relation together with Euler's formula.

Each face is bounded by 3 edges, and each edge borders exactly 2 faces in a connected plane graph. Counting edge-face incidences two ways gives 3F = 2E, so F = 2E/3.

Substitute into Euler's formula V - E + F = 2 with V = 12:

12 - E + 2E/3 = 2.

So 12 - E/3 = 2, giving E/3 = 10 and E = 30.

Then F = 2(30)/3 = 20.

Check against the planar bound: E at most 3V - 6 gives 30 at most 30, which holds with equality. That equality is exactly what it means for every face to be a triangle, so the graph is a maximal planar graph, and the check confirms the arithmetic rather than merely permitting it.

Question 9

Let the domain be the set of integers and let P(x,y) mean 'x < y'. Determine the truth value of each, and explain the relationship between them.
(i) For all x, there exists y such that P(x,y).
(ii) There exists y such that for all x, P(x,y).

Accepted Answer

Statement (i) says every integer has some integer greater than it. Given any x, take y = x + 1, which is an integer and satisfies x < y. The choice of y depends on x, which the quantifier order permits. So (i) is true.

Statement (ii) says there is a single integer y greater than every integer x. Suppose such a y existed. Then in particular y < y would have to hold when x is taken to be y itself, which is false. So no such y exists, and (ii) is false.

The relationship is that (ii) implies (i) but not conversely. If one fixed y works for all x, then certainly each x has some y, namely that one. The reverse fails exactly when the witness must depend on the universally quantified variable, which is the case here.

This pair is the standard demonstration that unlike quantifiers do not commute, and it is worth carrying as the concrete example whenever a question presents two quantifier orderings and asks which implies which.

Practice — "Discrete Mathematics"

Sign in to save attempts to your dashboard and track your accuracy over time

Find a verified tutor

Join a live course

Browse coaching centres

About

Categories

Support

Documentation

Get Study Tips & Updates

Download Our App

Download for iOS

Download for Android

Popular Cities