Solution to COMP 9020 - Foundation of Computer Science Assignment 2

This document presents a detailed solution to an assignment in Foundation of Computer Science (COMP 9020). The assignment covers topics including function composition, transitive relations, graph theory, and propositional logic. Question 1 involves proving properties of transitive relations. Question 2 focuses on formulating an examination timetable using graph theory. Question 3 explores the relationship between vertices, edges, and faces in planar graphs. Question 4 deals with semantics and truth tables for propositional logic. The solution provides step-by-step explanations and justifications for each answer.

Running Heading: Foundation of Computer Science
Assignment 2
Student’s Name
Course Code: COMP 9020
Institution Affiliation

Running Heading: Foundation of Computer Science
Question One
Solution
a. Given that f : S → T and g :T → U are functions. Is f : g a function
f : g Is a function, it’s the composition function of f : S → T and g : T → U ,
which is given byf ∘ g: S → U , which can also be written as f : g (Suppes, 1999).
b. Showing that R=R ∪ (R ;R), given that R ⊆S × S istransitive
Let R
⊆ S × S be any binary relation on a set S. Considering relations;
R0 =R and Ri +1=Ri ∪ (Ri ;R) for i≥ 0
Then by for i=1, Ri ∪ ( Ri ; R )=R1 ∪ ( R1 ; R )
¿ R ∪( R ; R)
Therefore,
Ri +1=Ri ∪ ( Ri ; R )
Ri +1=R ∪(R ; R)
Since,R0 =R, thus by induction Ri +1=R (Ward, 2005)
Hence,
R=R ∪ ( R ; R )
c. Proving that Ri ¿ R j ,for all j ≥ i , given that Ri ¿ Ri+1for some i, for all j ≥ i
By induction, R=Rn ⊆ R, to establish Ri ¿ Ri+1

Running Heading: Foundation of Computer Science
Suppose for any ( a , c ) ∈ Ri +1, there exist a a ∈ A such that ( a , b ) ∈ Ri∧ ( b , c ) ∈ R
Therefore by induction
( a , b ) ∈ R∧ ( b , c ) ∈ R
Due to transitivity ofR, then we have( a , c ) ∈ R. This prove that
Ri ¿ Ri+1
Since j is greater than i, therefore i+1 can represent as it also greater than i. This shows that
Ri ¿ R j , for j>i
d. Proving that Rk ⊆ Ri ,for all k ≥ 0, if Ri ¿ Ri+1 ,for some i,
Suppose that for some values , Ri ⊆R, particulary, R2 ⊆R
For all values a , b , c ∈ A such that( a , b ) , ( b , c ) ∈ R, there will be ( a , c ) ∈ R2
As a result, ( a , c ) ∈ R, this shows the transitivity of R (Wallis, 2011).
Supposing R is transitive, by induction Ri ⊆R can be proved.
Wheni=1, then R1=R ⊆ R, thus Ri ⊆R.
Therefore, since any power of R leads toRi ⊆R, by transitivity
Rk ⊆ Ri
e. Explaining why Rn ¿ Rn+1
By induction, R=Rn ⊆ R, to establish Rn ¿ Rn+1
Suppose for any ( a , c ) ∈ Rn +1, there exist a b ∈ A such that ( a , b ) ∈ Rn∧ ( b , c ) ∈ R .
Therefore by induction, ( a , b ) ∈ R∧ ( b , y ) ∈ R

Running Heading: Foundation of Computer Science
Due to the transitivity of R, then we have( a , c ) ∈ R.
Thus, Rn ¿ Rn+1
f. Showing that R¿ is transitive.
Suppose that for some values , Rn ⊆ R, particulary, R2 ⊆ R
For all values a , b , c ∈ A such that( a , b ) , ( b , c ) ∈ R, there will be ( a , c ) ∈ R2
As a result, ( a , c ) ∈ R, which shows that R is transitive.
Thus R¿ is transitive.

Running Heading: Foundation of Computer Science
Question Two
Examination timetable
a. Formulation process
Analyze the information in the table above to determine subjects’ combination of every
student. Below is a table showing the results.
Student Subjects Combination
Harry Potions and Herbology
Ron Potions and Charms
Malfoy Potions
Luna Charms and Transfiguration
Ginny Charms
George Herbology
Neville Herbology and Astronomy
Hermion
e
Astronomy and Transfiguration
Seamus Astronomy
Fred Transfiguration
To obtain the edges and vertices of the graph, the subjects will be considered as the
nodes. Edges between nodes will be drawn if there’s common student.

Running Heading: Foundation of Computer Science
Three Question
a. Number of Edges that a graph of n vertices and 1 face should have.
According to Leversha (2002), the number of vertices, edges and faces are related by the
following formula
vertices−edges +face=2
Therefore, the number of edges of the graph with n vertices and 1 face be will be given
by
n−edges+ 1=2
n−edges=1
edges=n−1
b. Developing an equation that relates number of vertices (n), number of edges (m) and
number of faces (f).
To do this, the following two planar graphs will be considered
P
H
C
T
A

Running Heading: Foundation of Computer Science
ii
i
The first planar graph has 8 vertices, 6 faces, and 12 edges, whereas the second one has 5
vertices, 3 faces and 6 edges. Considering the formula in a above, the three properties of the
planar graph will be associated as follows.
n−m+ f
Substituting n , m∧f with their corresponding values from the two graphs, to obtain two
expressions
8−12+6=2… … … .. i
¿ 5−6+3=2… … … …ii
The two expressions produce similar results, 2. Therefore, due to their common outcomes, the
number of vertices (n), number of edges (m) and number of faces (f) of a planar graph can be
related by the following equation n−m+ f =2
c. Induction on f , what will happen when if one edge is erased

Running Heading: Foundation of Computer Science
n−m+ f =2 ,deducting 1 ¿ m(number of edges)
n− ( m−1 ) +f =2
n−m+ f =1
Considering the first planar graph in b above, n=8 , m=12 ,∧f =6
n−m+ f =1
Make f the subject of the formula
f =1+12−8=5
Therefore, the number of faces is 5 after the deletion of one edge, which reflects a decrease
of 1 from the original number of faces. This shows that when the numbers of edges on a
planar graph change, the number of faces will change with the same value.
Question Four

Running Heading: Foundation of Computer Science
Given the valuation v : Prob → B, Semantics for ∘ as v ( ϕ ∘ψ ) =! v (ϕ)∧v (ψ )
a. Truth table for ( p ∘q) ∘( p ∘q)
This statement is logically equivalent to( p ∧q)( p ∧ q),
Given that p∧q are proposition formula and interpretation function I, which assigns 1,
when p and q are true and 0, when p and q are false. The true table will be as shown
below.
p q p ∧q p ∧q ( p ∧q)( p ∧ q)
1 1 1 1 1
1 0 0 0 0
0 1 0 0 0
0 0 0 0 0
b. Giving a logically equivalent formula using ◦ and propositional variables.
i. ¬ p
This negation propositional variable p (Aigner, 2007)
If p is a propositional variable that defines the formula of ψ ∧ϕ then
p=ψ ∧ ϕ , by implication
p=ψ ∘ ϕ
Therefore, negating the propositional variable

Running Heading: Foundation of Computer Science
¬ p=¬(ψ ∘ ϕ)
ii. p ∨q
This disjunction of the two variables p∧q
Assuming that q is a negative statement of p, then p ∨q will lead to
¿(ψ ∘ ϕ)∨¬(ψ ∘ϕ )
iii. p →q
This is an implication and conditional statement, which states if p is true then q
(Jenkyns& Stephenson, 2012).
Using the proposition formulae, p →q will lead to
¿( ψ ∘ ϕ)→¬(ψ ∘ ϕ)
iv. p ↔q
This is a conditional statement. This states that p is true if and only if q is true
(Belcastro, 2012).
Using the propositional formulae, p ↔q will result to
(ψ ∘ϕ )→ ¬(ψ ∘ ϕ )

Running Heading: Foundation of Computer Science
References
Aigner, M. (2007). Discrete mathematics, translated from the 2004 German original by David
Kramer. American Mathematical Society.
Belcastro, S. M. (2012). Discrete mathematics with ducks. CRC Press.
Jenkyns, T., & Stephenson, B. (2012). Fundamentals of discrete math for computer science.
London: Springer-Verlag
Leversha, G. (2002). Combinatorics and graph theory, by John M. Harris, Jeffry L. Hirst,
Michael J. Mossinghoff. Pp. 225.£ 24 (hb). 2000. ISBN 0 387 98736 3 (Springer-Verlag). The
Mathematical Gazette, 86(505), 177-178.
Suppes, P. (1999). Introduction to logic. Courier Corporation.
Ward, M. (2005). Sets, functions, and logic: an introduction to abstract mathematics (3rd edn),
by Keith Devlin.ISBN 1 58488 449 5 (Chapman & Hall/CRC). The Mathematical Gazette,
89(514), 182-183.
Wallis, W. D. (2011). A beginner's guide to discrete mathematics. Springer Science & Business
Media.