Logic, Proofs and Discrete Math: practice solutions, College

Rate this post

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

Written solutions to the chapter problems. Check each step, then correct yourself.

1 A truth table ★★★

We fill the rows in order.

\(p\)	\(q\)	\(\lnot q\)	\(p\land\lnot q\)
T	T	F	F
T	F	T	T
F	T	F	F
F	F	T	F

The statement is true only when \(p\) is true and \(q\) is false. (This is also the negation of \(p\Rightarrow q\).)

2 Negating statements ★★★

(a) “There is a dog in the park that is not on a leash” (the negation of \(\forall\) is \(\exists\) with a negated property).

(b) By De Morgan: “The pizza is not cold or the salad is not warm.”

3 Converse and contrapositive ★★★

Converse: “If an integer is divisible by 3, then it is divisible by 6.” Contrapositive: “If an integer is not divisible by 3, then it is not divisible by 6.”

The original is true, so its contrapositive is true. The converse is false: 9 is divisible by 3 but not by 6.

4 Set operations ★★★

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

Check: \(|A\cup B|=6+5-3=8\), which matches the list of 8 elements.

5 Outfits ★★★

The three choices are independent, so we multiply: \(5\times4\times3=60\).

She can make 60 different outfits.

6 Committee or officers ★★★

(a) Order does not matter: \(C(7,2)=\dfrac{7\cdot6}{2}=21\).

(b) Order matters (the roles differ): \(P(7,2)=7\cdot6=42\).

7 First terms of a recurrence ★★★

\(a_2=2\cdot3+1=7\), \(a_3=2\cdot7+1=15\), \(a_4=2\cdot15+1=31\), \(a_5=2\cdot31+1=63\).

The terms are 3, 7, 15, 31, 63, and \(a_5=63\).

8 Sum of two odd integers ★★★

Let the integers be \(2a+1\) and \(2b+1\) with \(a,b\) integers. Their sum is \((2a+1)+(2b+1)=2a+2b+2=2(a+b+1)\).

Since \(a+b+1\) is an integer, the sum is a multiple of 2, so it is even. \(\blacksquare\)

9 Quantifier order ★★★

(a) True: given \(x\), choose \(y=-x\).

(b) False: for any fixed \(y\), take \(x=1-y\); then \(x+y=1\ne0\).

Negation of (b): \(\forall y\,\exists x\ (x+y\ne0)\), which is exactly what we just showed.

10 Sum of odd numbers ★★★

Base: for \(n=1\) the left side is 1 and the right side is \(1^2=1\).

Step: assume \(1+3+\cdots+(2n-1)=n^2\). Add the next odd number \(2(n+1)-1=2n+1\): \(n^2+2n+1=(n+1)^2\).

So the formula holds for \(n+1\), and by induction for all \(n\ge1\). \(\blacksquare\)

11 Injective or surjective? ★★★

f is injective: if \(2a+3=2b+3\) then \(a=b\). f is not surjective: every output \(2x+3\) is odd, so 4 is never reached.

g is not injective: \(g(2)=g(-2)=4\). g is not surjective: no integer squared equals \(-1\).

12 Handshake and Euler ★★★

Degrees: vertex 1 has neighbors 2, 4, 3 so degree 3; vertex 2 has degree 2; vertex 3 has neighbors 2, 4, 1 so degree 3; vertex 4 has neighbors 3, 1, 5 so degree 3; vertex 5 has degree 1.

Sum: \(3+2+3+3+1=12=2\cdot6\), and there are 6 edges. The handshake theorem holds.

The odd vertices are 1, 3, 4 and 5: four of them. An Euler path needs 0 or 2 odd vertices, so none exists.

13 Arranging letters ★★★

LEVEL has 5 letters with L twice, E twice and V once. Dividing out the repeats: \(\dfrac{5!}{2!\,2!}=\dfrac{120}{4}=30\).

There are 30 distinct arrangements.

14 Two simple recurrences ★★★

(a) Arithmetic: \(a_n=5+4n\), so \(a_{10}=5+40=45\) members.

(b) Geometric: \(b_n=3\cdot2^n\), so \(b_8=3\cdot256=768\) bacteria.

15 Irrationality of the square root of 3 ★★★

Suppose \(\sqrt3=\dfrac ab\) with \(a,b\) positive integers and the fraction in lowest terms. Then \(a^2=3b^2\), so \(3\mid a^2\), hence \(3\mid a\), say \(a=3k\).

Then \(9k^2=3b^2\), so \(b^2=3k^2\), hence \(3\mid b\). Now 3 divides both \(a\) and \(b\), contradicting lowest terms.

So \(\sqrt3\) is irrational. \(\blacksquare\)

16 An inequality by induction ★★★

Base: \(n=5\): \(2^5=32>25=5^2\).

Step: assume \(2^n>n^2\) with \(n\ge5\). Then \(2^{n+1}=2\cdot2^n>2n^2\). Now \(2n^2\ge(n+1)^2\) is equivalent to \(n^2\ge2n+1\), true for \(n\ge3\) (since \(n^2\ge3n\ge2n+1\)).

So \(2^{n+1}>(n+1)^2\), and the claim holds for all \(n\ge5\). \(\blacksquare\)

17 Three overlapping clubs ★★★

Inclusion–exclusion: \(|C\cup M\cup S|=60+45+40-25-20-15+10=95\).

So \(100-95=5\) students take none of the three subjects.

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

(a) \(s_1=2\) (strings 0, 1) and \(s_2=3\) (00, 01, 10).

(b) For \(n\ge3\), look at the first symbol. If it is 0, the rest is any valid string of length \(n-1\): \(s_{n-1}\) ways. If it is 1, the next symbol must be 0 and the rest is any valid string of length \(n-2\): \(s_{n-2}\) ways.

19 Round robin and odd degrees ★★★

(a) This is the number of edges of \(K_{12}\): \(C(12,2)=\dfrac{12\cdot11}{2}=66\) games.

(b) If all 7 degrees were 3, the sum would be \(21\). By the handshake theorem the sum must be even (twice the number of edges), but 21 is odd. Contradiction, so no such graph exists.