Problem Sheet 1 Mathematics for AI
Problem Sheet 1 Week 2
This problem sheet consists of two questions. Each question contains three parts.
• Parts a), worth 40% of the marks in each question, test your knowledge of the core
material, and you should aim to provide good answers to this part of all questions.
• Parts b), worth 30% of the marks in each question, involve taking the concepts you have
been taught, but applying them in ways you may not have directly been shown. You
should attempt all the parts b), but you can still get a good mark without completing
all of them.
• Parts c), worth 30% of the marks in each question, are difficult questions which will test your understanding of the concepts taught in unfamiliar situations.
Question 1 (50%):
a) Translate the following sentences into propositional logic. Your formalizations should
be as detailed as possible.
i) Alice will go to the cinema or the theatre.
ii) Two is a prime number and not an odd number.
iii) If the speed limit is 30mph and I am driving at 25mph, then I am not breaking the
law.
iv) If Bob is not sleeping then he is working, eating, or relaxing.
v) Carlos will go to the park only if it is not raining.
Translate the following sentences into predicate logic. Your formalizations should be as
detailed as possible.
vi) Everyone is mortal.
vii) Unicorns do not exist.
viii) Every professional tennis player could beat any amateur tennis player.
ix) Everyone has either a father or a mother.
x) Somebody has visited every country that currently exists.
b) Consider the following formula of propositional logic:
P = ((A∧B)∨(¬A∧¬B)) →C
i) Suppose A = “I will go to the shops”, B = “I will go out for lunch” , C = “My
partner will be unhappy”. Translate P into an English sentence.
Problem Sheet 1 Mathematics for AI
ii) Suppose A is true, B is false and C is true. Is P true or false? Briefly explain
why.
iii) Which truth values for A , B and C result in P being false?
c) Consider the sentence “There is an animal in the zoo such that, if that animal is sleeping,
then every animal in the zoo is sleeping.”, formalised in predicate logic by the sentence
Q = ∃x(P x →∀yP y)
i) Suppose the zoo contains two animals, and both are sleeping. Is Q true or false?
ii) Now suppose one animal is sleeping, and one is awake. Is Q true or false?
iii) Now suppose we still know that the zoo contains two animals, but we do not know
how many are sleeping or awake. Can we know if Q is true or false?
iv) Now suppose we don’t know how many animals the zoo contains, except that there
is at least one animal, and we don’t know how many are awake or asleep. Can we
know if Q is true or false?
Question 2 (50%):
a) Identify which of these relations are reflexive, which are symmetric, which are transitive,
and which are equivalence relations. You do not need to show any working.
i) A is the set of all animals, R1 = {(a,b) |a is the same species as b}⊆A×A
ii) R2 = {(m,n) |m2 ≤n2}⊆Z×Z
iii) R3 = {(x,y) |x + y < 1}⊆R×R
iv) B = {0,1,2} , R4 = {(0,0),(0,1),(1,0),(1,1),(2,2)}⊆B×B
v) B = {0,1,2} , R5 = {(0,1),(1,2),(2,0)}⊆B×B
b) We define a function f : N→Z such that:
f (x) =
x 2 if x is even
−x+12 if x is odd
i) Prove that f is an injection.
ii) Prove that f is a bijection.
iii) Given that f is a bijection, find the inverse function f −1 : Z→N
iv) Given the previous parts, what can we say about the cardinality of N and Z ?
c) In this problem sheet, we will call a relation R geometric if ∀x,y,z(xRy∧xRz →yRz)
i) Prove that if a relation is geometric and reflexive, then it is also symmetric.
Problem Sheet 1 Mathematics for AI
ii) Using the previous part, prove that if a relation is geometric and reflexive, then it
is an equivalence relation.
iii) Let f : A→B be a function. We define the relation
R⊆A×A, R = {(x,y) | f (x) = f (y)}
By showing that it is geometric and reflexive, show that R is an equivalence
relation. What are the equivalence classes of R ?
