Logic, Proofs and Discrete Math: math practice, College – download the PDF

by
7 October 20267 October 2026

Rate this post

Math practice College : Logic, Proofs and Discrete Math — Zyro the alien explorer of Planète Maths

21 problems graded by difficulty (★ easy, ★★ medium, ★★★ hard). Try first, without looking at the solutions!

Sommaire

1 A truth table ★★★

Build the truth table of \(p\land\lnot q\). For which truth values of \(p\) and \(q\) is it true?

2 Negating statements ★★★

Write the negation of each statement. (a) “Every dog in the park is on a leash.” (b) “The pizza is cold and the salad is warm.”

3 Converse and contrapositive ★★★

Consider: “If an integer is divisible by 6, then it is divisible by 3.” Write its converse and its contrapositive. Which of them is true?

4 Set operations ★★★

Let \(A=\{1,2,3,4,5,6\}\) and \(B=\{2,4,6,8,10\}\). Find \(A\cap B\), \(A\cup B\), \(A\setminus B\) and \(|A\cup B|\).

5 Outfits ★★★

A runner owns 5 shirts, 4 pairs of shorts and 3 pairs of running shoes. How many different outfits can she make with one of each?

6 Committee or officers ★★★

A robotics team has 7 members. (a) In how many ways can a 2-person repair crew be chosen? (b) In how many ways can a captain and a co-captain be chosen?

7 First terms of a recurrence ★★★

A sequence satisfies \(a_1=3\) and \(a_{n+1}=2a_n+1\). Compute \(a_2,\dots,a_5\).

8 Sum of two odd integers ★★★

Prove directly that the sum of two odd integers is even.

9 Quantifier order ★★★

Over the integers, decide whether each statement is true and justify. (a) \(\forall x\,\exists y\ (x+y=0)\). (b) \(\exists y\,\forall x\ (x+y=0)\). Write the negation of (b).

10 Sum of odd numbers ★★★

Prove by induction that \(1+3+5+\cdots+(2n-1)=n^2\) for all \(n\ge1\).

11 Injective or surjective? ★★★

Let \(f:\mathbb{Z}\to\mathbb{Z}\), \(f(x)=2x+3\), and \(g:\mathbb{Z}\to\mathbb{Z}\), \(g(x)=x^2\). Decide whether each is injective and whether each is surjective.

12 Handshake and Euler ★★★

A graph has vertices 1 to 5 and edges 1–2, 2–3, 3–4, 4–1, 1–3 and 4–5. List the degrees, check the handshake theorem, and decide whether an Euler path exists.

13 Arranging letters ★★★

How many distinct arrangements of all the letters of the word LEVEL are there?

14 Two simple recurrences ★★★

(a) A gym has 5 members and gains 4 new members each week, so \(a_n=a_{n-1}+4\), \(a_0=5\). Find a closed form and \(a_{10}\). (b) A culture of 3 bacteria doubles each hour: \(b_n=2b_{n-1}\), \(b_0=3\). Find \(b_8\).

15 Irrationality of the square root of 3 ★★★

Prove by contradiction that \(\sqrt3\) is irrational. (You may use: if \(3\mid a^2\) then \(3\mid a\).)

16 An inequality by induction ★★★

Prove that \(2^n>n^2\) for all integers \(n\ge5\).

17 Three overlapping clubs ★★★

Among 100 first-year students, 60 take computer science (C), 45 take math (M) and 40 take statistics (S). Also 25 take C and M, 20 take C and S, 15 take M and S, and 10 take all three. How many take none of the three?

18 Binary strings without two 1s in a row ★★★

Let \(s_n\) be the number of binary strings of length \(n\) with no two consecutive 1s. (a) Find \(s_1\) and \(s_2\). (b) Explain why \(s_n=s_{n-1}+s_{n-2}\). (c) Compute \(s_8\).

19 Round robin and odd degrees ★★★

(a) In a tournament, each of 12 teams plays every other team once. How many games are played? (b) Show that a graph with 7 vertices cannot have every vertex of degree 3.

20 Composition and inverse ★★★

Let \(f(x)=3x-5\) and \(g(x)=x^2+1\) on the real numbers. (a) Find \(f^{-1}(x)\). (b) Compute \(g\circ f\) and \(f\circ g\) as formulas. (c) Evaluate both at \(x=2\).