# Problem Sheet 1 Mathematics for AI

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 ?