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

## Reviews

There are no reviews yet.