Assignment -

Note: In your assignment, how you arrived at your solution is as important (if not more so) than the solution itself and will be assessed accordingly. There may be more than one way to find a solution, and your approach should contain enough detail to justify its correctness. Lecture content can be assumed to be common knowledge.

1. If R₁ ⊆ S × T and R₂ ⊆ T × U are binary relations, the composition of R₁ and R₂ is the relation R₁; R₂ defined as:

R₁; R₂ := {(a, c) : There exists b ∈ T such that (a, b) ∈ R₁ and (b, c) ∈ R₂}

(a) If f : S → T and g : T → U are functions is f; g a function?

(b) If R ⊆ S × S is transitive, show that R = R ∪ (R; R). (Hint: One way to show A = B is to show A ⊆ B and B ⊆ A. One of these directions is trivial.)

Let R ⊆ S × S be any binary relation on a set S. Consider the sequence of relations R⁰, R¹, R², . . ., defined as follows:

R⁰ := R, and

Rⁱ⁺¹ := Rⁱ ∪ (Rⁱ; R) for i ≥ 0

(c) Prove that if Rⁱ = Rⁱ⁺¹ for some i, then Rⁱ = R^j for all j ≥ i.

(d) Prove that if Rⁱ = Rⁱ⁺¹ for some i, then R^k ⊆ Rⁱ for all k ≥ 0.

(e) If |S| = n, explain why Rⁿ = Rⁿ⁺¹. (Hint: Show that if (a, b) ∈ Rⁿ⁺¹ then (a, b) ∈ Rⁱ for some i < n + 1.)

In the above sequence, Rⁿ is defined to be the transitive closure of R, denoted R^∗ (closely related to the ∗ operator used to describe the set of all words over an alphabet).

(f) Show that R^∗ is transitive.

2. The following table describes several subjects and the students taking them:

You have been tasked to create an examination timetable for these subjects, and your goal is to find the smallest number of timeslots needed so that all subjects can be examined, without any conflicts occurring (i.e. no students having to take two or more exams at the same time).

(a) Explain how this can be formulated as a graph-based problem. That is, describe what the vertices and edges would be, and how to relate the given problem to a common graph problem.

(b) For this problem in particular determine the minimum number of timeslots required.

(c) Suppose instead your goal was to determine the largest number of subjects that can be examined at the same time without conflicts. How do your answers to (a) and (b) change?

3. Given a plane-drawing (i.e. no crossing edges) of a connected planar graph G, a face is a region that is enclosed by edges. For example, the following plane-drawing of K₄ has 3 faces (labelled 1, 2, 3):

(a) How many edges must a connected graph with n vertices and 1 face have?

(b) By examining several planar graphs, come up with an equation that relates the number of vertices (n), the number of edges (m) and the number of faces (f) of a plane-drawing of a planar graph.

(c) Prove, by induction on f or otherwise, that your formula is correct.

Hint: What happens if you delete an edge of a plane-drawing that doesn't disconnect the graph?

4. Extend the syntactical definition of propositional formulae to include the connective o:

• If φ and ψ are propositional formulae, then (φ o ψ) is a propositional formula.

Given a truth valuation v : Prop → B, define the semantics for o as

v(φ o ψ) = !(v(φ) & v(ψ))

(a) Draw the truth table for (p o q) o (p o q). Give a logically equivalent formula.

(b) For each of the following formulae, give a logically equivalent formula that only uses o and propositional variables. Justify your answer.

i. ¬ p

ii. p ∨ q

iii. p → q

iv. p ↔ q