Macquarie University Department of Mathematics MATH1007 Discrete Mathematics I S2 2020 Assignment 1 Due 8:00 pm, Monday 7 September 2020 Assignments are to be submitted electronically via the Assignment 1 page on MATH1007’s iLearn site. This assignment will be marked out of 100. The mark for each question is displayed next to it. This assignment is worth 20% of the overall unit marks. Your work may be hand-written or prepared electronically, and submitted online as a single PDF or Word file. If it is hand-written, take clear scans or photographs of your work and combine these into a single file. If you find that a question in this assignment confuses you, seek clarification of its meaning by posting a question to the MATH1007 forum. Keep an eye on the forum, as Dom is well known for giving hints to assist with the harder questions. Be aware that work that is illegible, because of poor hand-writing say, or due to poor contrast within the scan or photograph, will not be marked. Solutions without at least a brief explanation or justification will receive no, or only partial, marks. Logic and Boolean Algebra 1. Give the converse, the contrapositive, and the inverse of these conditional statements (a) If |y| = y, then y ≥ 0. [6 marks] Recall: the absolute value function for real numbers is given by |x| = x for x ≥ 0, and |x| = −x for x < 0. It might help you to sketch the graph of this function. (b) If n ≥ 3, then n2 ≥ 9. [6 marks] For each of the resulting propositions indicate whether they are true or false. Show your work. 2. Let P (x) and Q(x) be propositional functions. Show that [12 marks] ∃x (P (x)→ Q(x)) ≡ ∀xP (x)→ ∃y Q(y) . 3. Your boss asks you to design a Boolean circuit that verifies whether a given integer 0 ≤ x < 16 is divisible by 5. Every such number is represented in binary using four bits, say b3b2b1b0, and so your Boolean circuit will have four inputs. For instance, the number 13 is written in binary as 1101 and so to test its divisibility by 5 a user would feed the values b0 = 1, b1 = 0, b2 = 1 and b3 = 1 into the inputs of your circuit. This Boolean circuit will have a single output, which should deliver the value 1 if the input values represent a number that is divisible by 5 and 0 otherwise. Recall that the number 0 is divisible by 5. (a) Write down the truth table of the Boolean function F (b0, b1, b2, b3) that implements this “divisible by 5” operation. [4 marks] (b) Construct a Boolean expression in disjunctive normal form that implements the Boolean function that you wrote down in 3a. [3 marks] (c) Implement the Boolean expression constructed in 3b as a Boolean circuit. Draw your circuit. [5 marks] 4. Use Half-adders and Adders to design a Boolean circuit that computes the integer 3x for 0 ≤ x < 8. In your design you should try to be as economical as possible, by using the smallest number of Half-adders and Adders that you can. [14 marks] Note: your Boolean circuit will have 3 inputs and 5 outputs. ©2020, Department of Mathematics & Statistics, Macquarie University. 1 Graph Theory 5. Consider the graph G given by the following adjacency table a b c d e f g b a a c c a b c g d c f e g and the graph H given by the following adjacency matrix: t u v w x y z t 0 0 0 1 1 0 0 u 0 0 1 0 0 0 0 v 0 1 0 0 1 1 1 w 1 0 0 0 0 0 0 x 1 0 1 0 0 0 1 y 0 0 1 0 0 0 0 z 0 0 1 0 1 0 0 (a) Is either of G or H (or both) a tree? [2 marks] (b) Write down the degree sequences of G and H. Are they the same or different? [2 marks] (c) Is G bipartite? If it is then draw it in a way that clearly demonstrates that fact, otherwise explain how you know it isn’t. [2 marks] (d) Is H bipartite? If it is then draw it in a way that clearly demonstrates that fact, otherwise explain how you know it isn’t. [2 marks] (e) Is G isomorphic to the graph H? If it is then give the correspondence between the vertices of G and H which demonstrates that isomorphism, otherwise explain how you know it isn’t. [4 marks] (f) Let K be the graph obtained by deleting the edge cg from the graph G. Find a connected graph K ′ that has the same degree sequence as K but is not isomorphic to K, or explain why that isn’t possible. [5 marks] 6. Given an integer n > 0, the hypercube graph Qn of degree n (we use the letter Q here for “Qube”) is defined to be the graph with • Vertices corresponding to binary numbers bn−1bn−2…b1b0 with n binary digits (bits), and • Edges two vertices an−1an−2…a1a0 and bn−1bn−2…b1b0 have an (un-directed) edge between them if they only differ by a single bit. In other words, they have an edge between them if and only if there is a 0 ≤ i < n with ai ̸= bi and such that for all j ̸= i with 0 ≤ j < n we have aj = bj . So, for example, Q4 has vertices: {0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111} Its vertices 0101 and 0111 have an edge between them, because they only differ in their second digit. On the other hand 0101 and 1111 do not have an edge between them because they differ in their second and fourth digit. Question continues on next page. 2 ©2020, Department of Mathematics & Statistics, Macquarie University. (a) How many vertices does Qn have? [3 marks] (b) How many edges does Qn have? [3 marks] (c) For what values of n is Qn bipartite? [3 marks] (d) For what values of n is Qn a tree? [3 marks] (e) Show that the graphs Q1, Q2 and Q3 are planar by drawing them. [5 marks] (f) Does the graph Q4 have a Hamiltonian circuit? If it does write down a Hamiltonian circuit that demonstrates that fact, if it doesn’t explain why not. [6 marks] (g) (HD Question) Is the statement “for all n ≥ 4 the hyper cube Qn is non-planar” true? If it is not true draw a counter example, otherwise give an argument to support your conclusion. [10 marks] Hint: Euler’s formula may come in handy here. ©2020, Department of Mathematics & Statistics, Macquarie University. 3
