COMP1001E1-21

Question 1 This question is about Logic and Set Theory.
[overall 40 marks]
a) Use a truth table to show that ((P ) Q) _ (¬R ) ¬P)) ^ P equals
¬(P ) (¬Q ^ ¬R)). [12 marks]
b) Let A = {a,b,c,d,e,f,g}, B = {b,a,g}, C = {f,a,d,e} and D =
{a,g,e,d}.
(i) What is the powerset of B?
(ii) Let n = |P(C)| and m = |B ⇥ D|. What are n and m?
(iii) Draw an Euler diagram of A, B and C.
(iv) Draw a Venn diagram of A, B and C.
(v) Let E = P ? (A \ C) \ (A \ (D \ B)) ? . What is |E|?
[3 + 3 + 4 + 4 + 2 = 16 marks]
c) For the same sets A,B,C,D: Consider the statement 8 x2A,y2A ? x 62
B ^ y 62 B ^ x 62 C ^ y 62 C ^ x 62 D ^ y 62 D ) x = y ? .
(i) What does this statement mean?
(ii) Is the statement true? Why?
(iii) First, rewrite the formula only using existential quantification.
Then rewrite the formula so that it does does not contain im-
plication and disjunction. Argue why the meaning (in natural
language) of your resulting formula is the same.
[4 + 4 + 4 = 12 marks]

Question 2 This question is about Relations and Number Theory.
[overall 30 marks]
a Let R ✓ N ⇥ N, and (n,m) 2 R i↵ n 2 + m  50, and let S ✓ N ⇥ N,
and (n,m) 2 S i↵ n 2 ? 2 · m = 50.
(i) What are the set of departure, set of destination, domain and
image of R? Explain why.
(ii) Which of the following properties hold for R: Reflexivity, ir-
reflexivity, symmetry, antisymmetry, transitivity and connex (or
none).
(iii) What are the domain and image of S? And is S a function, a
partial function, a multi-valued function, or not a function?
[5 + 5 + 5 = 15 marks]
b Let a be a positive integer, with gcd(a,99) = 1 and gcd(a,100) = 1.
(i) Show that gcd(a,6655) = 1.
(ii) Given gcd(a,98) 6= 1 and gcd(a,101) 6= 1, show that a > 700.
(iii) What is 11 mod 4? What is 12 mod 4? What is gcd(12,4)?
What is lcm(11,4)?
(iv) Let f : Z ! Z, be f(n) = 2 · n + 3. Let g : Z ! Z, be g(n) = n 2 .
Show that for all integers k, g ? f(k) ⌘ mod 4 1
[4 + 4 + 3 + 4 = 15 marks]

Question 3 This question is about proofs:
[overall 30 marks]
a Prove 8 x2U (8 y2U (P(x,y) _ Q(x,y))) |= 9 x2U (9 y2U (P(x,y)))_
8 x2U (8 y2U (Q(x,y))) formally. [8 marks]
b Let f : Z ! Z be some function over the integers. Select an appro-
priate proof technique (direct, contradiction, induction, invariant or
pigeonhole), and prove that if you have: a, f(a), f(f(a)), f(f(f(a)))
and f(f(f(f(a)))), then at least 2 of those numbers are equivalent
modulo 4. [7 marks]
c Define t(0) = 2, and t(n) = t(n ? 1) 2
(i) According to this definition, what are t(1),t(2) and t(3)?
(ii) Use induction to prove that for n 2 N, t(n) = 2 (2
n ) . Write down
your base case and induction step clearly.
(iii) The formula in question looks like (2 2 ) n . However, this is not the
same as 2 (2
n ) . Can you show that (2 2 ) n
< 2 (2
n ) , as long as n > 2?
[2 + 8 + 5 = 15 marks]