Mst14S2

The University of New South Wales

Mid-Session Test

2014/09/01

COMP9020

Foundations of Computer Science

Time allowed: 1 hour

Total number of questions: 5

Maximum number of marks: 25

Not all questions are worth the same.

Answer all questions.

Textbooks, lecture notes, etc. are not permitted.

Calculators may not be used.

Answers must be written in ink. Use a pencil or the back of the booklet for

rough work. Your rough work will not be marked.

You can answer the questions in any order.

You may take this question paper out of the exam.

Write your answers into the answer booklet provided.

Question 1 (6 marks)

For each of the following formulae, analyse and prove whether it is valid or not.

A ∨ ¬B ⇔ (B ⇒ (A ∧ B))

(¬(A ∧ B) ∨ C) ⇒ (A ⇒ C)

(¬(A ∧ B) ∨ C) ⇒ ¬(A ⇒ C)

(1)

(2)

(3)

Answer:

A

F

F

T

T

B

F

T

F

T

A ∨ ¬B (B ⇒ (A ∧ B))

T

T

F

F

T

T

T

T

Figure 1: Truth table for question 1.1

A ∨ ¬B ⇔ (B ⇒ (A ∧ B))

is valid.

We can prove this either using a truth table shown in Figure 1 where we note that the two

columns on the right are equal, meaning that the two sub-formulae are indeed equivalent, or

via a chain of equivalences:

A ∨ ¬B ⇔ ¬B ∨ A

⇔ (¬B ∨ A) ∧ T

⇔ (¬B ∨ A) ∧ (¬B ∨ B)

⇔ (¬B ∨ (A ∧ B))

⇔ (B ⇒ (A ∧ B))

(¬(A ∧ B) ∨ C) ⇒ (A ⇒ C)

commutativity

identity

excluded middle

distribution

implication

is not valid

Consider A = T ∧ C = F ∧ B = F.

(¬(T ∧ F) ∨ F) ⇔ T

⇒F

⇔ (T ⇒ F)

(¬(A ∧ B) ∨ C) ⇒ ¬(A ⇒ C)

Consider A = T ∧ C = T.

(¬(T ∧ B) ∨ T) ⇔ T

⇒F

⇔ ¬(T ⇒ T)

is not valid

Question 2 (5 marks)

Prove that

n

i=0

2i = 2n+1 − 1 for all n ∈ N.

Answer: by induction on n. Base case

n+1

0

i=0

2i = 20 = 1 = 20+1 − 1. Inductive case

n

i

n+1

2 =2

i=0

n+1

+

2i

i=0

n+1

=2

+2

−1

n+2

=2

−1 .

by the ind. hyp.

Question 3 (5 marks)

Prove or disprove that S \ (T ∩ U ) = (S \ T ) ∪ (S \ U ) for all sets S, T , and U .

Answer: S \ (T ∩ U ) = (S \ T ) ∪ (S \ U ) is valid.

Proof:

S \ (T ∩ U ) = S ∩ (T ∩ U )

= S ∩ (T ∪ U )

= (S ∩ T ) ∪ (S ∩ U )

= (S \ T ) ∪ (S \ U )

Question 4...