Rewrite each of the following sentences so that the negation operator appears only within the
predicates (i.e., no negation is outside a quantifier or an expression involving logical connectives).
Explain how you obtain the results (generic explanations will give no credit).
a) ¬∃y∃xP(x, y)
b) ¬∀x∃y(P(x, y) ∧ Q(x, y))
c) ¬∃y(∃xR(x, y) ∨ ∀xS(x, y))
4 Cartesian Products
Consider the sets A = {a, b, c}, B = {dog, cat, mouse}, C = {T rue, F alse}. Answer the following
questions.
a) What is the set A × C?
b) How many elements are in A × B × C × A? Justify your answer.
c) Write one element of A × B × C × A.
d) Is A × B = B × A? Justify your answer.
e) Is (T rue, T rue, Dog) an element of C × B × C? Justify your answer.
5 Arguments
Determine if the following arguments are correct or not (you must justify your answer).
a) Every student enrolled in CSE015 has access to computer Lab #2. Jennifer does not have
access to computer Lab #2. Therefore Jennifer is not enrolled in CSE015.
b) Every student majoring in computer science must take CSE120. Jake is taking CSE120.
Therefore Jake is majoring in computer science.
6 Functions
Consider the following functions from Z × Z → Z. For each function state if the function is injective,
surjective, bijective, or none of the former. Justify each answer. Correct answers without justification
will give no credit.
a) f(x, y) = x + y
b) f(x, y) = |x + y| (here | · | is the absolute value function)
c) f(x, y) = x
2 − y
2
7 Order of Growth
For each of the following couple of functions, say if 1) the first function is big-O of the second
function, but the second is not big-O of the first function; 2) the second function is big-O of the
first function, but the first function is not big-O of the second function; 3) both functions big-O
of each other; 4) none of the former statements is true. Motivate your choice. Answers without
explanation will give no credit even if correct.
a) f1(n) = 4n
2 + log n f2(n) = 21n +
√
n
b) f1(n) = 3n
2 + 2n f2(n) = 4n
2 + 45n
c) f1(n) = 2n
3 + 4n log n f2(n) = n log n + 3n
2 + 12n
3
d) f1(n) = 4n
2
log n
2 + 21n f2(n) = 0.002n
3 + n
8 Induction
Using the principle of induction, prove that the following formula is true for each n ≥ 1:
Xn
i=1
2
i−1
· i = 2n
(n − 1) + 1
9 Modular Arithmetic
Consider arithmetic modulo m with m = 13. Answer the following questions and explain how you
obtain your results.
a) What is the result of 5 +m 8?
b) What is the additive inverse of 9 (modulo m)?
c) Is 4 ≡ 38(modm)?
d) Using the division algorithm, determine −4 mod m.
10 Cryptography
Consider the case where plaintext messages are only composed of upper case letters of the English
alphabet and spaces. Therefore there are 27 different symbols to represent (26 letters and the space).
Consider an encoding where the space is 0, A is 1, B is 2, . . . , Z is 26. Using a shift cipher with
key k = 4 a plain text message was encrypted, and the following ciphertext was obtained:
HMWGVIXIDQEXL
What was the original plaintext message? Explain how you obtain the result. Simply giving the
correct answer will not give any credit.
Sample Solution