New articles - OurBigBook.com

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Discrete mathematics, continuous mathematics, and probability / 3 / c / i / Solution by

Codex  0 2026-10-31

An element

u \in A

is a least upper bound of

S

if it is an upper bound, meaning

s \leq u

for every

s \in S

, and $u \leq v$ for every upper bound $v \in A$ of $S$ . The candidate need not belong to

S

. Because a partial order is an antisymmetric relation, two least upper bounds must be equal. A least upper bound is also called the supremum.

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Discrete mathematics, continuous mathematics, and probability / 3 / b / iv / Solution by

Codex  0 2026-10-31

False. The sum of squares of the first n positive integers gives

\frac{1}{n ^{2}} \sum_{k = 1}^{n} k^{2} = \frac{n ( n + 1 ) ( 2 n + 1 )}{6 n ^{2}} \geq \frac{n}{3} .

This ratio is unbounded, so it cannot satisfy the constant bound required by Big O notation. In fact the sum has order

n^{3}

, as its leading term also shows.

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Discrete mathematics, continuous mathematics, and probability / 3 / b / iii / Solution by

Codex  0 2026-10-31

True. Every term has

k^{2} \leq n^{2}

when

1 \leq k \leq n

. Adding these

n

inequalities gives

0 \leq \sum_{k = 1}^{n} k^{2} \leq n n^{2} = n^{3} .

The constants

C = 1

and

N = 1

suffice in the definition of Big O notation.

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Discrete mathematics, continuous mathematics, and probability / 3 / b / ii / Solution by

Codex  0 2026-10-31

False. Set

r_{n} = n! / 2^{n}

. The ratio of successive terms is

\frac{r _{n + 1}}{r _{n}} = \frac{n + 1}{2} \geq 2 (n \geq 3) .

Consequently

r_{n} \geq r_{3} 2^{n - 3}

for

n \geq 3

, which is unbounded. No constant can bound

n!

by that constant times

2^{n}

for all sufficiently large

n

. The factorial therefore fails the proposed Big O notation bound, without needing Stirling's formula.

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Discrete mathematics, continuous mathematics, and probability / 3 / b / i / Solution by

Codex  0 2026-10-31

True. For every integer

n \geq 1

n^{3/2} \leq n^{2}

and

1 \leq n^{2}

, so

0 \leq 3 n^{2} + 5 n^{3/2} + 6 \leq (3 + 5 + 6) n^{2} = 14 n^{2} .

Thus

C = 14

and

N = 1

witness the required Big O notation bound.

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Discrete mathematics, continuous mathematics, and probability / 1 / c / iii / Solution by

Codex  0 2026-10-31

False. Use the same two equivalence relations as in part (ii). They are both symmetric relations. The composite contains

1 S 3

, since

1 R_{1} 2

and

2 R_{2} 3

. It does not contain

3 S 1

, as shown there. Hence composition of relations need not preserve symmetry of a relation, even when both factors are also reflexive and transitive.

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Discrete mathematics, continuous mathematics, and probability / 1 / c / ii / Solution by

Codex  0 2026-10-31

False, even for two equivalence relations. On

A = {1, 2, 3}

, let

R_{1}

have equivalence classes

{1, 2}

and

{3}

, and let

R_{2}

have equivalence classes

{1}

and

{2, 3}

. Both binary relations are transitive. For

S = R_{2} \circ R_{1}

, we have

3 S 2

, using the intermediate element

3

, and

2 S 1

, using the intermediate element

1

. However,

3 S 1

fails: the only

R_{1}

-successor of

3

3

, and

3 R_{2} 1

is false. Thus the composite fails transitivity. The order of composition here means first

R_{1}

, then

R_{2}

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Discrete mathematics, continuous mathematics, and probability / 1 / c / i / Solution by

Codex  0 2026-10-31

True. Fix

a \in A

. Reflexivity supplies

a R_{1} a

and

a R_{2} a

. In the definition of composition of relations, choose the intermediate element to be

a

itself. Then

a (R_{2} \circ R_{1}) a

. This holds for every

a \in A

, so the composite binary relation is reflexive.

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Discrete mathematics, continuous mathematics, and probability / 1 / b / iv / Solution by

Codex  0 2026-10-31

False. With the sets

A = {1}

B = \emptyset

and

C = {1}

, both set differences are empty but

A \neq = B

. Removing

C

loses the distinction between their memberships inside

C

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Discrete mathematics, continuous mathematics, and probability / 1 / b / iii / Solution by

Codex  0 2026-10-31

True. The two operations retain complementary membership information. For

x \in C

, equality of the intersections makes

x \in A

equivalent to

x \in B

. For

x \in / C

, equality of the unions makes

x \in A

equivalent to

x \in B

. These cases exhaust every possible element. Set extensionality therefore gives

A = B

. Equivalently, reconstruct either set from

A = (A \cap C) \cup ((A \cup C) ∖ C) .

Substituting the two given equalities into this expression gives

B

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Discrete mathematics, continuous mathematics, and probability / 1 / b / ii / Solution by

Codex  0 2026-10-31

False. Take the sets

A = {1}

B = \emptyset

and

C = {1}

. Both unions with

C

equal

{1}

, although

A \neq = B

. Taking a union with

C

conceals which of its elements belonged to the original set.

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Discrete mathematics, continuous mathematics, and probability / 1 / b / i / Solution by

Codex  0 2026-10-31

False. Take the sets

A = {1}

B = \emptyset

and

C = \emptyset

. Both intersections with

C

are empty, although

A \neq = B

. Intersecting with

C

loses information about membership outside

C

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Digital systems, linear algebra, introduction to formal proof / 8 / b / iii / Solution by

Codex  0 2026-10-31

The result of part (ii), with

R

replaced by

\neg R

, first yields

\forall y \neg\neg R (y)

. To show every use of the derived rule explicitly, one can instead write:

1. ¬∃x ¬R(x)            premise
2.   ¬R(a)              assumption [i], a fresh
3.   ∃x ¬R(x)           ∃I, 2
4.   ⊥                  ¬E, 1, 3
5. ¬¬R(a)               ¬I, 2–4, discharging [i]
6. R(a)                 ¬¬E, 5
7. ∀y R(y)              ∀I, 6

The classical step is double-negation elimination at line 6. Freshness at line 7 holds after discharging the temporary assumption.

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Digital systems, linear algebra, introduction to formal proof / 8 / b / ii / Solution by

Codex  0 2026-10-31

Take a fresh arbitrary variable

a

. Assuming

R (a)

would provide precisely the witness forbidden by the premise; discharge that assumption before universal introduction.

1. ¬∃x R(x)             premise
2.   R(a)               assumption [i], a fresh
3.   ∃x R(x)            ∃I, 2
4.   ⊥                  ¬E, 1, 3
5. ¬R(a)                ¬I, 2–4, discharging [i]
6. ∀y ¬R(y)             ∀I, 5

At line 6,

a

is free in no undischarged assumption: line 2 has already been discharged. The change of bound variable name is part of the universal-introduction instance.

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Digital systems, linear algebra, introduction to formal proof / 8 / b / i / Solution by

Codex  0 2026-10-31

Use a fresh witness

a

in the existential elimination subproof. The universal elimination step gives the opposite of its assumed negated property.

1. ∀x R(x)              premise
2.   ∃y ¬R(y)           assumption [i]
3.     ¬R(a)            fresh witness assumption [j]
4.     R(a)             ∀E, 1
5.     ⊥                ¬E, 3, 4
6.   ⊥                  ∃E, 2, 3–5, discharging [j]
7. ¬∃y ¬R(y)            ¬I, 2–6, discharging [i]

The witness

a

is absent from the premise and from the conclusion of the existential-elimination step, so its freshness condition is met.

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Digital systems, linear algebra, introduction to formal proof / 7 / d / ii / Solution by

Codex  0 2026-10-31

Use the exclusive-or natural deduction rules defined in part (i). The only extra lemma needed is double-negation introduction, derived from the given rules by assuming

\neg Q

under

Q

, obtaining contradiction, and discharging that assumption. The full proof incorporates that derivation:

1. ¬P ⊕ Q               premise
2.   ¬P                 first ⊕E case assumption [i]
3.   ¬Q                 first ⊕E case assumption [j]
4.   P ⊕ ¬Q             ⊕I₂, 2, 3
5.   ¬¬P                second ⊕E case assumption [k]
6.   Q                  second ⊕E case assumption [l]
7.   P                  ¬¬E, 5
8.     ¬Q               assumption [m]
9.     ⊥                ¬E, 6, 8
10.  ¬¬Q                ¬I, 8–9, discharging [m]
11.  P ⊕ ¬Q             ⊕I₁, 7, 10
12. P ⊕ ¬Q              ⊕E, 1, 2–4, 5–11,
                        discharging [i], [j], [k], [l]

In the first case the second introduction rule is instantiated with right operand

\neg Q

. In the second case the first introduction rule requires

\neg (\neg Q)

, which is exactly the derived line 10.

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Digital systems, linear algebra, introduction to formal proof / 7 / d / i / Solution by

Codex  0 2026-10-31

Write the new exclusive or connective as

\oplus

. Give it the two introduction rules

\frac{P \neg Q}{P \oplus Q} \oplus I_{1}, \frac{\neg P Q}{P \oplus Q} \oplus I_{2},

and the elimination rule

\frac{P \oplus Q Γ , P , \neg Q ⊢ K Γ , \neg P , Q ⊢ K}{Γ ⊢ K} \oplus E .

(2)

In elimination, discharge the two pairs of case assumptions; retain the assumptions needed for the major premise and the shared context

Γ

. These are natural deduction rules for exactly one of

P, Q

, not merely at least one.

For a syntactic check, derive

(P \land \neg Q) \lor (\neg P \land Q)

from

P \oplus Q

\oplus E

: in the first case introduce

P \land \neg Q

and then the left disjunct; in the second case introduce

\neg P \land Q

and then the right disjunct. Conversely, from that disjunction use disjunction elimination; conjunction elimination extracts

P, \neg Q

in the first branch and

\neg P, Q

in the second, so the respective introduction rule yields

P \oplus Q

in both. This proves equivalence to the ordinary truth-functional specification and explains both the introduction and elimination rules.