Logic, sets and proof techniques – university Year 1 maths worksheet with answers to download as PDF

Write the negation of each statement in words, without using the phrase "it is not the case that". Then say whether the original statement or its negation is true.

1. For all real numbers \(x\), \(x^2>0\). [3 marks]
2. There exists an integer \(n\) such that \(n^2=2\). [3 marks]
3. For every integer \(n\), if \(n\) is prime then \(n\) is odd. [3 marks]

Complete a truth table (or reason carefully) to answer each question.

1. Show that \(P\Rightarrow Q\) is logically equivalent to \(\neg P\vee Q\). [3 marks]
2. Show that \((P\Rightarrow Q)\wedge(Q\Rightarrow R)\Rightarrow(P\Rightarrow R)\) is a tautology. [4 marks]

Consider the statement S: "If \(n^2\) is even, then \(n\) is even", where \(n\) is an integer.

1. Write the converse of S. [1 mark]
2. Write the contrapositive of S. [2 marks]
3. Which of S, its converse and its contrapositive are true? Justify briefly. [4 marks]

Let \(A=\{1,2,3,4,5,6\}\), \(B=\{2,4,6,8\}\) and \(U=\{1,2,\dots,10\}\).

1. Find \(A\cup B\), \(A\cap B\) and \(A\setminus B\). [3 marks]
2. Find \(A^c\) and \(A\triangle B\) (the elements in exactly one of \(A\), \(B\)). [3 marks]
3. How many subsets does \(A\) have? How many have exactly 2 elements? [3 marks]

Prove each statement directly. Define your integers clearly.

1. The sum of two odd integers is even. [3 marks]
2. If \(n\) is odd then \(n^2-1\) is divisible by 8. [4 marks]
3. The product of two consecutive integers is even. [3 marks]

Prove each statement by induction for all integers \(n\ge1\).

1. \(1+2+\cdots+n=\dfrac{n(n+1)}2\) [5 marks]
2. \(\displaystyle\sum_{i=1}^ni^2=\dfrac{n(n+1)(2n+1)}6\) [6 marks]

Four cards lie on a table. Each has a letter on one side and a number on the other. You can see E, K, 4 and 7. A teacher claims: "If a card has a vowel on one side, then it has an even number on the other side." You may turn over some cards to test the claim.

1. Write the claim in the form \(P\Rightarrow Q\).
2. Which cards could possibly break the claim, if turned over?
3. Which cards must you turn over to check the claim? Explain.
4. Why is turning over the 4 a waste of time?

In a class of 40 students, 25 study maths, 18 study physics and 8 study both.

1. Draw a Venn diagram in words, and find how many study only maths and only physics.
2. How many study at least one of the two subjects, and how many study neither?
3. Check with the formula \(|M\cup P|=|M|+|P|-|M\cap P|\).
4. One student is picked at random. Find the probability that the student studies exactly one of the two subjects.

A pizzeria offers 6 toppings. A customer chooses any set of toppings (including none). Two orders are the same if they have the same set of toppings.

1. How many different orders are possible?
2. How many orders have at least one topping?
3. How many orders have exactly 3 toppings?
4. How many have at most 2 toppings? What fraction of all orders is that?

A sports club announces: "If it rains, the match is cancelled." Let \(R\): it rains, \(C\): the match is cancelled.

1. Complete the last column.
2. Write the contrapositive in words. If the match was not cancelled, what can you conclude?
3. The match was cancelled. Can you conclude that it rained? Explain.
4. Write the converse and give a real-life reason why it might be false.

Maya puts £1 in her money jar in week 1, £2 in week 2, £3 in week 3, and so on, adding one pound more each week.

1. How much has she saved after 5 weeks? After 20 weeks?
2. Prove by induction that after \(n\) weeks she has saved £\(\dfrac{n(n+1)}2\).
3. After how many weeks does she first have more than £500?
4. How much does she put in during week 32, and how does it compare with the total saved by the end of week 31?

In the Tower of Hanoi puzzle, \(n\) discs of different sizes are moved from one peg to another, one disc at a time, never placing a larger disc on a smaller one. The minimum number of moves is \(M_n=2^n-1\).

1. Check the formula for \(n=1,2,3\).
2. Prove by induction that \(M_n=2^n-1\) satisfies \(M_{n+1}=2M_n+1\) and hence that the formula holds.
3. Find \(M_{10}\) and \(M_{20}\).
4. If one move takes one second, how many days does \(M_{20}\) take to the nearest tenth of a day?

On a 12-hour clock, define \(a\sim b\) if \(12\mid(a-b)\), that is, if the hours \(a\) and \(b\) show the same time on the dial.

1. Show that \(\sim\) is an equivalence relation on the integers.
2. What are the equivalence classes?
3. It is 9 o'clock now. What time will the clock show in 100 hours?
4. What time did it show 250 hours ago?

The pigeonhole principle states that if more than \(n\) objects are placed into \(n\) boxes, then some box contains at least two objects.

1. Show that among any 13 people, two share the same birth month.
2. Show that in a lecture of 367 students, two share a birthday (counting 29 February).
3. How many people must you pick to be sure that at least 3 share a birth month?
4. Prove the principle by contradiction.

In 1772 Euler observed that \(f(n)=n^2+n+41\) is prime for many small values of \(n\). Consider the conjecture C: "\(n^2+n+41\) is prime for every integer \(n\ge0\)".

1. Check three of the values in the table.
2. Show that \(f(40)\) is not prime. What does this show about the conjecture?
3. Show that \(f(41)\) is not prime without a calculator.
4. Explain why no number of successful examples can prove C, but a single failure can disprove it.

The function \(F:\mathbb R\to\mathbb R\), \(F(C)=\dfrac95C+32\) converts Celsius to Fahrenheit, and \(K(C)=C+273.15\) converts Celsius to kelvin.

1. Show that \(F\) is injective and surjective, and find its inverse.
2. Find the composite function that converts Fahrenheit to kelvin: \(K\circ F^{-1}\).
3. Find the temperature at which \(F(C)=C\).
4. Is \(F\) a bijection when restricted to \(C\ge-273.15\) with codomain \(\mathbb R\)? Explain.

Cards numbered by the integers are dealt into three piles according to the rule: cards \(a\) and \(b\) go to the same pile if \(3\mid(a-b)\).

1. Prove that "same pile" is an equivalence relation on \(\mathbb Z\).
2. List the three equivalence classes.
3. In which pile does card 100 go? Card \(-7\)?
4. Show that if \(a\sim b\) and \(c\sim d\) then \(a+c\sim b+d\) and \(ac\sim bd\).

A rational number can be written as \(\dfrac pq\) in lowest terms. Prove the following by contradiction.

1. \(\sqrt2\) is irrational.
2. \(\sqrt2+1\) is irrational (you may use part (a)).
3. There are no positive integers \(a,b\) with \(2^a=3^b\).
4. Deduce that \(\log_23\) is irrational.

The table compares \(2^n\) and \(n^2\) for small \(n\).

1. For which \(n\) in the table is \(2^n>n^2\) false?
2. Prove by induction that \(2^n>n^2\) for all integers \(n\ge5\).
3. Prove by induction that \(7^n-1\) is divisible by 6 for all \(n\ge1\).
4. An algorithm takes \(2^n\) steps and another takes \(n^2\) steps. What does part (b) mean for large inputs?

Prove that every integer \(n\ge2\) can be written as a product of primes (a prime on its own counts as a product of one prime).

1. State the base case and the strong induction hypothesis.
2. Prove the induction step by considering two cases: \(n\) prime and \(n\) not prime.
3. Apply the idea to write 360 as a product of primes.
4. Why is ordinary induction (using only the case \(n-1\)) not enough for this proof?