Fill This Form To Receive Instant Help
Fill This Form To Receive Instant Help
Homework answers / question archive / Discrete Mathematics Assignment 1 1
Discrete Mathematics Assignment 1
1. (Logic) Give an answer for each item below.
(a) Produce the truth table for the proposition
(
(p ∧ q) ∨ (p → q)
)
→ p.
Classify this proposition as a tautology, contradiction, or contingency. No need to justify your answer.
(b) Consider the propositions
p : I will go to the movies; q : it is raining.
Write the following sentence using propositional logic:
I will only go to the movies if it is not raining.
(c) The universe of discourse is U = Z = {0, ±1, ±2, ±3 . . . }. Is the following statement true or false? Justify.
∀x ∀y ∃ z (x < y) → (x = y + z
2
).
[4+4+4 = 12 marks]
2. (Sets) Given the universal set U = Z = {0, ±1, ±2, ±3 . . . }, we define, for each integer
n ∈ Z, the set
An = {m ∈ Z | n ≤ m}.
For example, the sets A0, A2 and A−1 are described below:
A0 = {0, 1, 2, . . . } = N, A2 = {2, 3, 4, 5, . . . }, A−1 = {−1, 0, 1, 2, . . . }.
(a) Show that for all integers n we have An+1 ⊂ An.
(b) Define the set B = A0 ∩ A1 ∩ A2 ∩ · · · (an infinite intersection). List all elements of
B.
(c) Use intersections, unions, and complements, if necessary, to express the set C =
{1, 2, 3, 4} in terms of the various sets An.
[4+4+4 = 12 marks]
3. (Logic) Let U = N = {0, 1, 2, 3 . . . } be the universal set. We define predicates P and Q as
follows:
P(x): x is a prime number. Q(x, y): x divides y.
Side note: The number 1 is not prime. The statement Q(2, 9) is false because 2 does not
divide 9 within the natural numbers.
For each item below, translate the English language statement into formal language, or
translate the formal statement into English, whichever one is appropriate.
(a) For any natural number n there is a prime number bigger than n.
(b) There is a number that divides every number.
(c) There is a number that can be divided by every number.
(d) ∀ x∀ y
(
(
(y ?= 1) ∧ Q(x, y)
)
→
(
(x = 1) ∨ (x = y)
)
)
→ P(y).
[3+3+3+3 = 12 marks]
4. (Sets) In a survey of 558 people about their streaming services memberships, the following
information was obtained.
• People mostly subscribe to one of the three main streaming services: Inertflix, That
Jungle, and Not very Magic Kingdom (from now on represented by the letters I, J,
and K, respectively).
• 11 people subscribe to all three (I, J, and K).
• 32 people subscribe to both I and J.
• 21 people subscribe to both J and K.
• 53 people subscribe to both K and I.
• 205 people subscribe to I.
• 180 people subscribe to J.
• 197 people subscribe to K.
Please justify your answers:
(a) How many people subscribe to both I and K, but not J?
(b) How many people in the set J ∩ I
c ∩ Kc
?
(c) How many people subscribe to more than one service?
(d) How many people subscribe to I and one (as opposed to two) other service?
(e) How many people do not subscribe to any of the three main streaming services?
[4+4+4+4+4 = 20 marks]
5. (Induction) We will prove by induction that
11n − 7
n
is divisible by 4, for n = 1, 2, 3, etc.
(a) Verify the base case, when n = 1.
(b) Write down the statement S(k) (which we assume to be true for a fixed k), and the
statement S(k + 1), that we want to prove.
(c) Prove that S(k) implies S(k + 1).
[2+3+10 = 15 marks]
6. (Methods of proof) We take U to contain the positive real numbers. Consider the statement
if x ∈ U is bigger than 1, then x
2 > x.
(a) Give a direct proof of this statement.
(b) Write down the contrapositive of the statement (don’t need to prove it).
(c) If you were attempting a proof by contradiction, what would be the hypotheses used
in your proof?
[10+3+2 = 15 marks]
7. (Relations) Consider the set A = {1, 2, 3, 4, 5}, and a relation R on A defined by
xRy ⇐⇒ 2x − y is an integer multiple of 3.
(a) List all elements y for which 1Ry is true.
(b) Is R reflexive? Justify.
(c) Is R symmetric? Justify.
(d) Is R antisymmetric? Justify.
(e) Is R transitive? Justify
