MCD4440 Discrete Mathematics For Computer Sciences 2023

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

MCD4440

Discrete Mathematics For Computer Sciences

Assignment

Trimester 3 2023

Status: Individual

Weighting: 5%

Word limit: No limit

Due date: 10:00 AM, Monday 13th November, 2023.

Question 1: 8 marks

Question 2: 8 marks

Question 3: 5 marks

Question 4: 5 marks

Question 5: 2 marks

Question 6: 8 marks

Question 7: 4 marks

Question 8: 7 marks

Mathematical communication: 3 marks

Instructions:

❼ Read and understand the Monash College assessment policy and penalties for plagiarism, cheating and collusion as listed in the Unit Outline.

❼ Read and understand the “Student Writing Guide.” There will be marks awarded to mathematical communication.

❼ Clearly show all workings/calculations/diagrams etc.

❼ When you complete your assignment solutions, it is not necessary to restate the question, your solutions should be written such that the reader could determine what the question may have been.

❼ Attach the completed and signed assignment coversheet, and write the tutor’s name.

❼ Keep a copy of your assignment for your record.

❼ Please upload your completed assignment as a pdf file with the completed assignment cover sheet in the link provided on Moodle.

❼ A penalty of 10% applies for each day after the due date excluding weekends.

1.  For the following groups of statements, select which statement or statements are true. For those that are true, briefly explain why.

(a)     i.  8 divides 32

ii.  32 divides 8

iii.  8 divides 30

iv.  30 divides 8

(b)     i.  7 ≡ 19  (mod 12)

ii.  7 ≡ 20  (mod 12)

iii.  7 ≡ 21  (mod 12)

iv.  7 ≡ 22  (mod 12)

(c)     i.  There exists some positive integer n such that 22 divides 2021n  ii.  There exists some positive integer n such that 22 divides 2022n iii.  There exists some positive integer n such that 22 divides 2023n iv.  There exists some positive integer n such that 22 divides 2024n

(d)    i. There exists an integer n 13 such that gcd(n,13) = 1

ii. There exists an integer n 13 such that gcd(n,13) = n

iii. There exists an integer n 13 such that gcd(n,13) = 13

iv.  None of the above are true.

2. Use Euclid’s algorithm to find g, where g = gcd(468, 333), and then to find a,b ∈ Z such that g = 468a + 333b.

3. Use a truth table to show that (p∧q) → ¬r and ¬p∨(q → ¬r) are logically equivalent.

4. Use laws of logic to show that (p ∧ q) ∨ (p ∧ q) ∨ ¬(¬p ∧ p) is logically equivalent to T or logically equivalent to F. State, with a brief explanation, whether this statement is a tautology, a contradiction, or neither.  Name each logic law as you use it, and take care to apply only one logic law per line.

5. Write down the contrapositive and the negation of the statement “If it is raining, then the grass is wet.”

6. Let P(x,y) be the predicate “x2 ≡ y  (mod 4).” Let x range over the integers andy range over the set {0, 1}. Determine which of the following statements are true, providing a brief justification for each of your answers.

(a) ∃x∃yP(x,y)

(b) ∃x∀yP(x,y)

(c) ∀y∃xP(x,y)

(d) ∃y∀x¬P(x,y)

7.  Consider the sentence (二xP(x) V 二xQ(x)) 一 (二x(P(x) V Q(x))).  Is this sentence valid? If it is, explain why. If it is not, give an interpretation under which it is false.

8. Prove using simple induction that 3 divides n3 - n for all integers n ≥ 1.

Mathematical  Communication:  In this assignment marks will be awarded for mathematical communication.   Read  the  “Student  Writing  Guide”  for  assistance  with  this.    You should be attempting to implement good mathematical communication in all of your tutorial work, assignments, tests and exams. This includes but is not restricted to:

❼ Clear explanations/reasoning for key steps in working;

❼ Write explanations/reasoning in a clear coherent sentence structure with no shorthand or mathematical symbols;

❼ Take care with spelling and grammar;

❼ Notation  and symbols are used correctly and used where they are meant to be.  Some examples of not doing this are; not using determinant notation when you are calculating the determinant of a matrix, placing an equal sign between limit notation and the ex- pression the limit is meant to be evaluating (for example 0 = x2 ), not dropping equal signs leaving the working look like an array of algebraic expressions with no connection, splitting up derivative notation as if it were a fraction; and so on.

❼ Each answer should have a concluding sentence which should indicate the purpose of your working and what the result means in context of the question;

❼ Where possible you should check your final result makes sense with respect to the infor- mation given in the question.


2023-11-09