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