CSC165H1 Problem Set 1

CSC165H1 Problem Set 1

1. [6 marks] Truth tables and formulas. Consider the following formula:
:r ) (:p ) q)
(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.
(c) [2 marks] Write formula that is logically equivalent to the converse of the given formula, and that
doesn't use ) or ,, in other words it uses only ^;_, or :. Show how you derived the result.
2. [6 marks] one-to-one and onto
Use the following de nitions in the questions below.
Onto(f): 8n 2 N; 9m 2 N; f(m) = n, for f : N ! N.
OneToOne(f): 8m; n 2 N; m 6= n ) f(m) 6= f(n), for f : N ! N.
(a) [1 mark] Suppose :Onto(g). Write this in predicate logic without using the predicate name Onto.
(b) [1 mark] Suppose :OneToOne(h). Write this in predicate logic without using the predicate name
OneToOne.
(c) [1 mark] Give an example of a function f : N ! N where Onto(f) and OneToOne(f).
(d) [1 mark] Give an example of a function f : N ! N where :Onto(f) and OneToOne(f).
(e) [1 mark] Give an example of a function f : N ! N where Onto(f) and :OneToOne(f).
(f) [1 mark] Give an example of a function f : N ! N where :Onto(f) and :OneToOne(f).
3. [7 marks] modular arithmetic
(a) [2 marks] Prove Example 2.19(1) from the course notes.
(b) [2 marks] Prove Example 2.19(3) from the course notes.
(c) [3 marks] Use Example 2.19(3) to  nd the units digit of 257256. Use Example 2.19(3) to prove your
result | we will not accept the argument that you used a calculator or programming language to
compute this with brute force.
4. [7 marks] remainders
(a) [1 mark] Prove:
9x 2 [0; 34]; x  3 mod 5 ^ x  5 mod 7
(b) [1 mark] Prove:
9m1; m2 2 Z;(m1  7) + (m2  11) = 1
. . . by  nding suitable values for m1 and m2.
(c) [2 marks] Assume that m1; m2 are integers such that (m1  7) + (m2  11) = 1. Prove:
8a1; a2 2 Z;(a2  m1  7) + (a1  m2  11)  a2 mod 11
(d) [3 marks] Prove that if p1; p2 are any two distinct primes and a1; a2 are any two integers, then there
is some integer x such that x  a1 mod p1 and x  a2 mod p2. Hint: Note that gcd(p1; p2) = 1, read
the material on gcd in the course notes, and read the previous part of this question.
Page 2/2