CSC165H1: Problem Set 1

CSC165H1 Problem Set 1
CSC165H1: Problem Set 1

General instructions
Please read the following instructions carefully before starting the problem set. They contain important
information about general problem set expectations, problem set submission instructions, and reminders
of course policies.
? Your problem sets are graded on both correctness and clarity of communication. Solutions which
are technically correct but poorly written will not receive full marks. Please read over your solutions
carefully before submitting them. Proofs should have headers and bodies in the form described in
the course note.
? Each problem set may be completed in groups of up to three. If you are working in a group for this
problem set, please consult https://github.com/MarkUsProject/Markus/wiki/Student_Groups
for a brief explanation of how to create a group on MarkUs.
Exception: Problem Sets 0 and 1 must be completed individually.
? Solutions must be typeset electronically, and submitted as a PDF with the correct ?lename. Handwritten submissions will receive a grade of ZERO.
The required ?lename for this problem set is problem set1.pdf.
? Problem sets must be submitted online through MarkUs. If you haven't used MarkUs before, give
yourself plenty of time to ?gure it out, and ask for help if you need it! If you are working with a
partner, you must form a group on MarkUs, and make one submission per group. \I didn't know
how to use MarkUs" is not a valid excuse for submitting late work.
? Your submitted ?le should not be larger than 9MB. This may happen if you are using a word
processing software like Microsoft Word; if it does, you should look into PDF compression tools to
make your PDF smaller, although please make sure that your PDF is still legible before submitting!
? The work you submit for credit must be your own; you may not refer to or copy from the work of
other groups, or external sources like websites or textbooks. You may, however, refer to any text
from the Course Notes (or posted lecture notes), except when explicitly asked not to.
Additional instructions
? Final expressions must have negation symbols (:) applied only to predicates or propositional variables, e.g. :p or :P rime(x). To express \a is not equal to b," you can write a 6= b.
? When rewriting logical formulas into equivalent forms (e.g., simplifying a negated formula or removing implication operators), you must show all of the simplification steps involved, not just the ?nal
result. We are looking for correct use of the various simpli?cation rules here.
? You may not de?ne your own predicates or sets for this problem set; please work with the de?nitions
provided in the questions, or from the course notes.
Page 1/3
CSC165H1, Fall 2017 Problem Set 1
1. [4 marks] Truth tables and formulas. Consider the following formula:
(p _ q) ) r
(a) [2 marks] Write the truth table for the formula. (No need to show your calculations).
(b) [2 marks] Write a logically equivalent formula that doesn't use ) or ,, in other words it uses only
^;_, or :. Show how you derived the result.
2. [10 marks] congruence
Find a natural number m congruent to 5 (mod 7), and another natural number n congruent to 2 (mod 7).
Find what the product mn is congruent to (mod 7), and then make a statement about the congruence of
the product of any pairs of natural numbers that have the same congruences as the m and n you found,
(mod 7).
(a) [5 marks] Write a predicate formula that expresses your statement in the form of a universally
quanti?ed implication. If you believe the statement, prove it true. If you disbelieve the statement,
prove it false.
(b) [5 marks] Write the converse of your formula from the previous part. If you believe the converse,
prove it true. If you disbelieve the converse, prove it false.
3. [4 marks] one-to-one pigeonholes
The pigeonhole principle says, informally, that if n pigeons roost in fewer than n pigeonholes, at least one
pigeonhole will be crowded with more than 1 pigeon.
To make this precise, we ?rst formalize the notion of un-crowded for f : D 7! R:
OneToOne(f): 8x; y 2 D; x 6= y ) f(x) 6= f(y), where f : D 7! R, jDj; jRj 2 N
+.
Let F = ff j f : D 7! R ^ jDj 0 ^ jRj 0g The pigeonhole principle says that:
8f 2 F; OneToOne(f) ) jDj ? jRj
(a) [4 marks] Use the pigeonhole principle to prove that if n ? 2 people go to the same party, there are at
least 2 people who shake hands with the same number of other people. Hint: Take the set of people
at the party as your domain, de?ne a function that evaluates how many people each person shook
hands with.
You may also use the pigeonhole principle in subsequent questions in this assignment.
4. [21 marks] modular arithmetic with primes
Let a; p be natural numbers with p prime and gcd(a; p) = 1. Let T = f1; : : : ; p 1g, the positive integers
less than p.
De?ne rp(x) as the remainder after division of x by p.
Prove each of the following claims. You may use the result of an earlier claim to help prove a later claim,
for example Claim (e) might help prove Claim (f). You may even use an earlier claim you haven't proven
to help prove a later claim.
(a) [3 marks] Claim: frp(an) j n 2 Tg ? T. Hint: Consider the material in Characterizations in the
course notes.
Page 2/
CSC165H1, Fall 2017 Problem Set 1
(b) [3 marks] Claim: If n1 and n2 are distinct numbers in T, then rp(an1) 6= rp(an2). Hint: Consider the
material in Characterizations in the course notes.
(c) [3 marks] Claim: jfrp(an) j n 2 Tgj = jTj.
(d) [3 marks] Claim: frp(an) j n 2 Tg = T. Hint: For ?nite sets A and B if A ? B then jBj = jBnAj+jAj.
(e) [3 marks] Claim: ?
i=p1
i=1 rp(ai) = ?i=p1
i=1 i.
(f) [3 marks] Claim: rp(a
p1
) = 1. Hint: You may assume, as a consequence of Example 2.18, that if for
i 2 f1; 2; : : : ; kg ai ? bi (mod p), then ?k
1ai ? ?
k
1
bi (mod p). You may also assume, as an extension
of Example 2.14, that for any k 1, if prime p - b1 ^ p - b2 ^ ? ? ? ^ p - bk, then p - (b1 b2 ? ? ? bk).
(g) [3 marks] Claim: If a is an arbitrary natural number that isn't divisible by 5, then r5(a
100) = 1.
5. [6 marks] primes
Since, as shown in the course notes, there are in?nitely many primes, it is not possible for a consecutive
sequence of composite (non-prime) natural numbers to stretch on forever. However, arbitrarily long
prime-free sequences exist. On the other hand, for any natural number we can always set an upper bound
on how far away the next prime can be.
Prove each of the following statements. You may use the Prime predicate.
(a) [3 marks] Claim: For any k 2 N there is some n 2 N such that n; n + 1; : : : ; n + k are composite. Hint:
Think about (k + 2)!.
(b) [3 marks] Claim: For any positive natural number n there exists a prime p with n < p < n! + 2. Hint:
Think about n!, and the proof of Theorem 2.3, that there are in?nitely many primes.
Page