Description
Problem 1 (40 marks)
For this question, let F denote the set of well-formed formulas over a set Prop of propositional variables.
(a) Show that the logical equivalence relation, ≡, is an equivalence relation on F. (12 marks)
(b) List four elements in [⊥], the equivalence class of ⊥. (4 marks)
(c) For all ϕ, ϕ
0
, ψ, ψ
0 ∈ F with ϕ ≡ ϕ
0 and ψ ≡ ψ
0
; show that:
(i) ¬ϕ ≡ ¬ϕ
0
(4 marks)
(ii) ϕ ∧ ψ ≡ ϕ
0 ∧ ψ
0
(4 marks)
(iii) ϕ ∨ ψ ≡ ϕ
0 ∨ ψ
0
(4 marks)
Let us define F≡ to be the set of equivalence classes of F under ≡. That is,
F≡ := {[ϕ] : ϕ ∈ F}.
Part (c) above shows that the following operations are well-defined1 on F≡:
• [ϕ] ∧ [ψ] defined to be [ϕ ∧ ψ]
• [ϕ] ∨ [ψ] defined to be [ϕ ∨ ψ]
• [ϕ]
0 defined to be [¬ϕ]
(d) Show that F≡ together with the operations defined above forms a Boolean Algebra. Note: you will
have to give a suitable definition of a zero element and a one element in F≡. (12 marks)
1well-defined means that the output is not dependent on different representations of the same input.
1
Problem 2 (10 marks)
This is the Petersen graph:
0
1
2 3
4
5
6
7 8
9
(a) Give an argument to show that the Petersen graph does not contain a subdivision of K5. (5 marks)
(b) Show that the Petersen graph contains a subdivision of K3,3. (5 marks)
Problem 3 (10 marks)
Harry would like to take each of the following subjects: Defence against the Dark Arts; Potions; Herbology;
Transfiguration; and Charms. Unfortunately some of the classes clash, meaning Harry cannot take them
both.
The list of clashes are:
• Defence against the Dark Arts clashes with Potions and Charms
• Potions also clashes with Herbology
• Herbology also clashes with Transfiguration, and
• Transfiguration also clashes with Charms.
Harry would like to know the maximum number of classes he can take.
(a) Model this as a graph problem. Remember to:
(i) Clearly define the vertices and edges of your graph. (4 marks)
(ii) State the associated graph problem that you need to solve. (2 marks)
(b) Give the solution to the graph problem corresponding to this scenario; and solve Harry’s problem.
(4 marks)
2
Problem 4 (22 marks)
Recall from Assignment 2 the definition of a binary tree data structure: either an empty tree, or a node
with two children that are trees.
Let T(n) denote the number of binary trees with n nodes. For example T(3) = 5 because there are five
binary trees with three nodes:
(a) Using the recursive definition of a binary tree structure, or otherwise, derive a recurrence equation for
T(n). (8 marks)
A full binary tree is a non-empty binary tree where every node has either two non-empty children (i.e. is
a fully-internal node) or two empty children (i.e. is a leaf).
(b) Using observations from Assignment 2, or otherwise, explain why a full binary tree must have an odd
number of nodes. (4 marks)
(c) Let B(n) denote the number of full binary trees with n nodes. Derive an expression for B(n), involving
of T(n
0
) where n
0 ≤ n. Hint: Relate the internal nodes of a full binary tree to T(n). (6 marks)
A well-formed formula is in Negated normal form if it consists of just ∧, ∨, and literals (i.e. propositional
variables or negations of propositional variables). That is, a formula that results after two steps of the
process for transforming a formula into a logically equivalent one. For example, p ∨ (¬q ∧ ¬r) is in
negated normal form; but p ∨ ¬(q ∨ r) is not.
Let F(n) denote the number of well-formed, negated normal form formulas2
there are that use precisely
n propositional variables exactly one time each. So F(1) = 2, F(2) = 16, and F(4) = 15360.
(d) Using your answer for part (c), give an expression for F(n). (4 marks)
2Note: we do not assume ∧ and ∨ are associative
3
Problem 5 (18 marks)
Consider the following graph:
v1 v2
v4 v3
and consider the following process:
• Initially, start at v1.
• At each time step, choose one of the vertices adjacent to your current location uniformly at random,
and move there.
Let p1(n), p2(n), p3(n), p4(n) be the probability your location after n time steps is v1, v2, v3, or v4
respectively. So p1(0) = 1 and p2(0) = p3(0) = p4(0) = 0.
(a) Express p1(n + 1), p2(n + 1), p3(n + 1), and p4(n + 1) in terms of p1(n), p2(n), p3(n), and p4(n).
(6 marks)
(b) As n gets larger, each pi(n) converges to a single value (called the steady state) which can be determined by setting pi(n + 1) = pi(n) in the above equations. Determine the steady state probabilities
for all vertices. (8 marks)
(c) The distance between any two vertices is the length of the shortest path between them. What is your
expected distance from v1 in the steady state? (4 marks)