Past exam of the year 1 of the computer science course of the University of Oxford / 2019

a

Solution

Use a logical right shift to discard one inspected bit at a time. The following Thumb instruction set subroutine accepts the word in r0, returns its population count in r0, preserves r4, and otherwise uses caller-saved processor registers.

popcount_loop:
    push {r4}
    movs r1, #0
    movs r2, #1
    movs r3, #32
pop_loop:
    movs r4, r0
    ands r4, r4, r2
    adds r1, r1, r4
    lsrs r0, r0, #1
    subs r3, r3, #1
    bne pop_loop
    movs r0, r1
    pop {r4}
    bx lr

ands extracts the current least significant bit; adds includes it in the count. lsrs fills the newly vacant high position with zero. subs immediately precedes bne, so the branch tests the zero flag from decrementing the loop counter, not a flag left by the shift.

After

k

iterations, the accumulator contains the number of one bits in the original word's

k

lowest positions, and the remaining word is the original unsigned interpretation shifted right by

k

. This loop invariant holds initially and is preserved by each iteration. At

k = 32

every position has been inspected, proving the result. The given example therefore returns 10, and the all-zero and all-one words return 0 and 32. The accumulator cannot overflow: it never exceeds 32.

b

Solution

Extract successive bytes into indices of the byte-table population count table. The last shift leaves only the original high byte, so that index needs no final mask.

popcount_table:
    push {r4}
    adr r2, popbyte
    movs r3, #255
    movs r1, r0
    ands r1, r1, r3
    ldrb r4, [r2, r1]
    lsrs r0, r0, #8
    movs r1, r0
    ands r1, r1, r3
    ldrb r1, [r2, r1]
    adds r4, r4, r1
    lsrs r0, r0, #8
    movs r1, r0
    ands r1, r1, r3
    ldrb r1, [r2, r1]
    adds r4, r4, r1
    lsrs r0, r0, #8
    ldrb r1, [r2, r0]
    adds r0, r4, r1
    pop {r4}
    bx lr

Place the byte table at an aligned nearby label in the instruction-address range of adr. That instruction forms the table's address relative to the program counter; it does not load a table entry. Each ldrb uses register-offset addressing: the base is r2, the byte offset is the index register, and the loaded byte is zero-extended. Because entries occupy one byte, the index needs no scaling. ldrb r1, [r2, r1] uses the old r1 to form the address before overwriting it with the result.

Every bit belongs to exactly one extracted byte, so adding the four table counts gives the whole word's population count, independently of endianness. The calculation reads four bytes from the table and contains no loop.

c

Solution

Count executed instructions, excluding the caller's branch-with-link and assuming the register-return and stack instructions shown above. The shift loop executes six instructions per iteration, plus four entry instructions and three exit instructions: $6 \cdot 32 + 7 = 199$ instructions. The unrolled table subroutine executes 21 instructions, including four byte loads.

If every instruction, including a table load and a branch, costs one time unit, the ratio is $199/21 \approx 9.48$ in favour of the table version. A more informative simple model assigns cost

L

to each table load and unit cost to the other displayed instructions: its cost is

17 + 4 L

, versus 199 for the loop under the same unit branch assumption. Thus this model favours lookup when

L < 45.5

Real running time depends on the processor and memory system. Taken branches can incur extra instruction-fetch or pipeline costs, favouring the unrolled version; slow flash or cache miss events on the 256-byte table can erode that advantage. Instruction and table placement also matter. These assumptions prevent instruction counts from becoming an unsupported universal cycle claim. For a fixed 32-bit argument both implementations have constant worst-case work; the gain is a constant factor, not a different asymptotic class.

d

Solution

Let the new byte table store

L [0] = 8

and, for

1 \leq b \leq 255

L [b] = 7 - ⌊ lo g_{2} b ⌋

. Thus it stores the number of leading zeros in an eight-bit argument:

L [1] = 7

L [2] = L [3] = 6

, and

L [128], \dots, L [255] = 0

. All entries fit in one byte.

countlz:
    adr r3, lzbyte
    movs r1, #0
    lsrs r2, r0, #24
    bne lz_found
    movs r1, #8
    lsrs r2, r0, #16
    bne lz_found
    movs r1, #16
    lsrs r2, r0, #8
    bne lz_found
    movs r1, #24
    movs r2, r0
lz_found:
    ldrb r2, [r3, r2]
    adds r0, r1, r2
    bx lr

The high byte is tried first. A failed test proves that byte was zero, so the next right-shifted value is again a byte-sized index without masking: all higher bytes have already been proved zero. The offset in r1 counts those skipped zero bytes in bits. Adding the table result for the first nonzero byte gives the leading-zero count. If every byte is zero, the last lookup contributes eight to the offset 24, giving 32. The example with high byte one gives 7. At most three conditional branches and one table read are needed; no per-bit loop is used.

2

a

Solution

Give the hardware to a single device driver process. Other processes request a conversion through message passing and never touch its memory-mapped input-output registers. The following is protocol pseudocode for Phōs: its operation names specify their required semantics, rather than asserting an unverified spelling of a particular 2019 C interface. The hardware actions and the request/reply design are fully specified.

Use a FIFO queue of accepted requests, each containing its sender and a per-call token. Bind the device's interrupt to a persistent notification addressed to the driver before any conversion is started. A notification must remain pending if it arrives before the driver next waits; this is the lost-wakeup avoidance requirement. The driver receives both client requests and interrupt notifications in its event loop.

configure sensor and connect its interrupt notification to this process
TEMP_DATARDY := 0
clear stale pending interrupt notification
enable sensor interrupt and interrupt-controller delivery
pending := empty FIFO
active := none

forever:
    if active is none and pending is not empty:
        active := remove oldest request from pending
        TEMP_DATARDY := 0
        clear stale pending interrupt notification
        TEMP_START := 1

    event := wait for a request or persistent interrupt notification

    if event is REQUEST(sender, token):
        append (sender, token) to pending

    if event is sensor interrupt and active is not none:
        if TEMP_DATARDY != 0:
            value := TEMP_TEMP
            TEMP_DATARDY := 0
            acknowledge the interrupt through the OS interrupt mechanism
            send RESULT(active.token, value) to active.sender
            active := none

After receiving an idle-time request, the next loop iteration starts its conversion before waiting again. While a conversion is in progress, additional requests join the queue without starting another conversion. A completed reading is copied before its ready flag is cleared, and the next request cannot start until the current result has been delivered. Spurious or stale notifications do not complete a request unless the device's ready register confirms completion.

Clearing old status and notification precedes TEMP_START; doing so afterwards could erase a very fast completion. The operating system interrupt binding and persistent notification cover completion in the interval between starting the device and entering the wait. Register accesses must use the platform's device-access semantics, including required volatile-qualified objects in C or ordering primitives. Exact initialization and interrupt-connection call names remain an implementation binding, not invented Phōs API calls. The later teaching site's named system is documented separately; it is not used as proof of an identical historical API.^[ref]

b

Solution

Provide a blocking request-reply sensor conversion operation, using synchronous send-and-receive when the system supplies it:

get_temp():
    token := a new token for this process's call
    reply := request-and-wait(
        destination = temperature_driver,
        message = REQUEST(self, token),
        expected_reply = RESULT(token, value))
    return reply.value

Here request-and-wait means sending the request and remaining ready to accept its matching response; it denotes a protocol action, not a claimed library symbol. Separate blocking send and receive operations are also adequate if they preserve the sender identity and the reply cannot be lost between them. With a synchronous reply, the driver simply waits until this client's receive is ready.

The call returns only after the driver has selected this request, issued TEMP_START, observed completion, read the new value and replied with the matching token. Each call therefore starts its own fresh conversion and returns its own result. It never returns a cached sample or another caller's reply. Local request and response storage belong to the calling process and are not a shared global message buffer.

c

Solution

Safety: only the driver accesses the sensor, and active identifies at most one conversion. Accepted requests are serialized by the FIFO queue. The reply destination and token identify the owner of the resulting sample; no caller can clear another conversion's ready flag or consume another result. Receiving new requests while busy only changes the queue, not the active measurement. These are mutual exclusion and request/result association properties, not timing guesses.

Progress: assume each started conversion completes in finite time, the corresponding notification is eventually delivered, the driver and compliant clients are eventually scheduled, and pending message acceptance is fair. A caller remains ready to receive its reply. Every accepted request has finitely many earlier requests in the queue, and later arrivals cannot overtake it. Each earlier request is completed and removed in finite time, so the caller eventually becomes active and receives its own reading. Fair acceptance extends this argument from accepted requests to callers waiting to submit one.

These assumptions are necessary for starvation freedom. A failed sensor, a client that disappears before accepting a synchronous reply, or an unfair scheduler can prevent progress; serialization alone cannot prove otherwise. Under the stated operating model, simultaneous calls are safe and every call completes. A single shared “latest temperature” variable would not establish either a fresh conversion per call or correct reply ownership.

3

a

Solution

The two lower conducting branches are the series pairs controlled by

a, b

and by

c, d

. Their overall NMOS transistor conduction condition is

ab \lor c d

. Apply complementary CMOS network duality: the upper network has the parallel pair of PMOS transistors controlled by $a, b$ , in series with the parallel pair controlled by $c, d$ . Its first end connects to the high rail, its last end connects to

z

, and the junction between the two pairs is internal to the upper network.

Figure 1.
Original completed pull-up networks derived by complementary CMOS network duality
. **Details**.

The left panel gives that completion. Every upper transistor uses its correspondingly named input and conducts when that input is low. Its conducting condition is

(\neg a \lor \neg b) \land (\neg c \lor \neg d)

, exactly the complement of the lower condition. Thus the ideal static circuit connects the output to one supply rail for every stable binary input.

b

Solution

The lower network pulls the output low exactly when either series branch conducts. Therefore the Boolean function is

z = \neg (ab \lor c d) = (\neg a \lor \neg b) \land (\neg c \lor \neg d) .

The inversion is important:

ab \lor c d

describes connection to the low rail, not a high output. The pull-up network found in part a implements the complementary high condition.

c

Solution

Joining the two middle nodes makes the upper lower-network transistors, controlled by

a, c

, parallel with each other. The lower transistors, controlled by

b, d

, are also parallel. These two parallel groups are in series, so the lower conducting condition becomes

(a \lor c) \land (b \lor d)

Its dual upper network must be two parallel branches, one containing the series PMOS transistor pair $a, c$ , the other the series pair $b, d$ . This is the right panel of the original drawing. Its condition is

(\neg a \land \neg c) \lor (\neg b \land \neg d)

. Merely leaving the old upper network unchanged would break CMOS complementarity for some inputs, allowing a supply short rather than defining the required logic.

d

Solution

The modified output is

z^{'} = \neg ((a \lor c) \land (b \lor d)) = (\neg a \land \neg c) \lor (\neg b \land \neg d) .

For example, $(a, b, c, d) = (1, 0, 0, 1)$ gives $z = 1$ and $z^{'} = 0$ . Neither original series branch is complete, but the new connection supplies the cross-route through the transistors controlled by

a, d

. Interchanging those roles gives the other cross-route example. In fact

(a \lor c) (b \lor d) = ab \lor a d \lor b c \lor c d

, so the modified circuit has added exactly those two possible lower conduction routes.

e

Solution

Let

a_{k}

be the input sampled at clock edge

k

. The desired registered output after that edge is $z_{k} = a_{k - 2} a_{k - 1} (1 - a_{k})$ . Only the last two high samples matter: a longer high run still has two high samples immediately before its first low sample.

A direct synchronous 110 detector uses three D flip-flops, holding

q_{1}, q_{2}, z

, with a common clock and initial state zero. Use the following next-state equations, all evaluated from the old state and the input at the active clock edge:

q_{1}^{+} = a, q_{2}^{+} = q_{1} \land a, z^{+} = q_{2} \land \neg a .

After an edge,

q_{1}

records the latest sample and

q_{2}

records whether the latest two samples were high. The final equation consequently produces the required pulse from the preceding two-high state and the new low sample. A synchronous reset sets all three state bits to zero. The output is the stored z flip-flop value, so it changes only after clock edges; exposing the unregistered expression

q_{2} \land \neg a

would let input transitions between edges alter the output.

Figure 1.
Original sampled-input and registered-output trace for a synchronous 110 detector
. **Details**.

An equivalent finite-state machine has states R (no current high run), H (one high), HH (at least two highs), and P (the pulse state). Its output is one only in P:

State	Next on 0	Next on 1	Output
`R`	`R`	`H`	0
`H`	`R`	`HH`	0
`HH`	`P`	`HH`	0
`P`	`R`	`H`	1

The pulse cannot last two cycles: after the low input that creates it,

q_{2}

is zero, so the next output is zero regardless of the next input. The detector rearms without a global stop and handles repeated patterns indefinitely. The three-flip-flop construction is deliberately direct; minimum storage was not required.

4

a

Solution

Subtract the first vertex from the other two, giving side vectors

(2, 1)

and

(3, 4)

. Their determinant is

2 \cdot 4 - 3 \cdot 1 = 5

, the signed area of the corresponding parallelogram. The triangle occupies half that area, hence its area is $5/2$ . Taking the absolute value would remove any sign change caused by reversing the vertex order. This is the determinant formula for triangle area.

b

i

Solution

Let

c_{1} = (1, 1, 1)^{T}

and

c_{2} = (2, - 2, 6)^{T}

. The remaining columns are

3 c_{1}

and

2 c_{2}

, so these two vectors span the column space. They are linearly independent: the determinant of their first two coordinates is

- 4 \neq = 0

. Therefore ${(1, 1, 1)^{T}, (2, - 2, 6)^{T}}$ is a basis of the range, and the matrix rank is two.

Equivalently the range is the plane

y_{3} = 2 y_{1} - y_{2}

: both displayed basis vectors satisfy this equation, and their two-dimensional span fills that plane.

ii

Solution

The independent-column representation gives

T (x) = c_{1} (x_{1} + 3 x_{3}) + c_{2} (x_{2} + 2 x_{4})

. Thus a vector lies in the kernel of a linear map represented by this matrix precisely when

x_{1} = - 3 x_{3}

and

x_{2} = - 2 x_{4}

. Writing the two free coordinates separately gives

x = x_{3} - 3 010 + x_{4} 0 - 2 01 .

The two displayed vectors are linearly independent, so they form a basis of the kernel. Its dimension two also agrees with the rank-nullity theorem,

4 = 2 + 2

c

i

Solution

A

m \times n

, then

Y

n \times m

. The equation

A Y = I_{m}

makes every standard basis vector of

R^{m}

a linear combination of the columns of

A

: take the corresponding column of

Y

as coefficients. Hence the column space is all of

R^{m}

, giving $rank (A) = m$ . In particular,

n \geq m

and

A

has full row rank.

ii

Solution

The system is consistent for every $b \in R^{m}$ : take

x = Yb

, since

A (Yb) = (A Y) b = b

. Thus

Y

is a right inverse giving an explicit solution for every right-hand side.

All solutions are

Yb + u

with

u

in the kernel of a linear map represented by

A

. The rank-nullity theorem gives kernel dimension

n - m

; the solution is unique when

n = m

, and is nonunique when

n > m

d

i

Solution

True. Transposing the inverse identities shows

(X^{- 1})^{T} = (X^{T})^{- 1}

. If

X^{T} = X

, this becomes

(X^{- 1})^{T} = X^{- 1}

, exactly the symmetric matrix condition. The reasoning uses the matrix inverse and transpose identities, without assuming that different matrix factors commute.

ii

Solution

True. Using the same transpose identity and

X^{T} = - X

gives

(X^{- 1})^{T} = (X^{T})^{- 1} = (- X)^{- 1} = - X^{- 1} .

The final equality follows by multiplying

- X

and

- X^{- 1}

in either order and obtaining the identity. Thus the inverse is a skew-symmetric matrix as well. The invertibility hypothesis is retained throughout.

e

Solution

True for these square matrices. The determinant multiplication identity gives

det (X Y) = det X det Y

. Since

X Y

is invertible, its determinant is nonzero; both factors are therefore nonzero, so both matrices have matrix inverses.

Equivalently,

Y

must be injective and

X

must be surjective, and either property implies invertibility for an endomorphism of a finite-dimensional vector space. The equal square dimensions matter: a rectangular matrix and a right inverse can have identity product without being mutually invertible square matrices.

5

a

i

Solution

True. The rank-nullity theorem gives

dim N (A) = n - r = 0

. The only vector in this zero-dimensional kernel of a linear map is the zero vector.

ii

Solution

False. Take

A = (1, 0)^{T}

, an

m = 2

n = 1

matrix of matrix rank one, and

b = (0, 1)^{T}

. Then

A x = (x, 0)^{T}

never equals

b

. Full column rank implies injectivity, not surjectivity onto a larger codomain.

iii

Solution

True. A square matrix with matrix rank

n

is invertible, and its transpose has the same rank. Applying the rank-nullity theorem to both

A

and

A^{T}

gives nullity zero in each case, so both kernels are

{0}

iv

Solution

False. Triviality of

N (A)

gives

r = n

, while triviality of

N (A^{T})

gives

r = m

because transpose preserves matrix rank. Both conditions therefore force

m = n

, contradicting the stated unequal dimensions.

b

i

Solution

Choose

r

independent columns of

A

that form a basis of its column space, and put them in

B \in R^{m \times r}

. For each column

a_{j}

A

, let

c_{j}

be its coordinate vector in that basis; put these coordinate vectors in

C \in R^{r \times n}

. The column equations

a_{j} = B c_{j}

give $A = BC$ .

By construction

B

has full column rank

r

. The columns of

C

corresponding to the selected basis columns are the standard vectors of

R^{r}

, so

C

has full row rank

r

. This proves the requested rank factorization. When

r = 0

A = 0

and the corresponding empty-column and empty-row factors have the required shapes and rank zero.

ii

Solution

Not unique in general. For any invertible

r \times r

matrix

S

A = (BS) (S^{- 1} C)

is another rank factorization, with the same full ranks. This is a change of basis in the intermediate

r

-dimensional space. For example, even

[1] = [1] [1] = [2] [1/2]

has different full-rank factors. Once a particular ordered basis

B

is fixed, its coordinate matrix

C

is unique; it is the basis choice that creates the freedom.

c

Solution

For the first matrix choose its single independent column:

B_{1} = 111, C_{1} = (111) .

Their product has every column equal to

B_{1}

, and both factors have rank one.

For the second matrix, the first and third columns are independent and the second equals the first, giving

B_{2} = 120001, C_{2} = (101001) .

Multiplication reconstructs the stated matrix. The first factor has independent columns and the second has independent rows, so both have matrix rank two, as required for a rank factorization.

d

Solution

The two square products can have different sizes, but their matrix traces are both the same finite double sum:

tr (X Y) = \sum_{i = 1}^{l} (X Y)_{ii} = \sum_{i = 1}^{l} \sum_{j = 1}^{k} X_{ij} Y_{ji} = \sum_{j = 1}^{k} \sum_{i = 1}^{l} Y_{ji} X_{ij} = tr (Y X) .

Interchanging two finite sums and commuting their scalar factors is valid over the real numbers. No commutation of the matrix products themselves is asserted. This proves the cyclic property of the trace in the rectangular-factor case.

e

Solution

Let

r = rank (A)

. If

r = 0

, the matrix is zero and the identity is immediate. Otherwise choose the rank factorization

A = BC

from part b. The column space of

B

is the image of

A

An idempotent matrix acts as the identity on its image: if

u = A v

, then

A u = A^{2} v = A v = u

. Applying this to each column of

B

gives

A B = B

. Substituting

A = BC

yields

B (CB - I_{r}) = 0

. Since

B

has full column rank, the represented map is injective, so each column of

CB - I_{r}

is zero. Thus

CB = I_{r}

Now the rectangular cyclic property of the trace gives

tr (A) = tr (BC) = tr (CB) = tr (I_{r}) = r = rank (A) .

This proves that the trace of an idempotent equals its rank using the supplied factorization method. Orthogonality of the projection is unnecessary: the argument applies to every real idempotent matrix.

6

a

i

Solution

The characteristic polynomial is

det (A - λ I) = (2 - λ) (10 - λ) - 9 = λ^{2} - 12 λ + 11 = (λ - 1) (λ - 11) .

Thus the eigenvalues are 1 and 11. Corresponding eigenvectors are

(3, - 1)^{T}

and

(1, 3)^{T}

. Their dot product is zero and each has Euclidean norm

10

. Normalizing gives

P = \frac{1}{10} (3 - 1 13), D = (10011) .

The columns are orthonormal, so

P^{T} P = I

. The eigenvector equations give

A P = P D

and hence

P^{T} A P = D

, proving the claimed orthogonal diagonalization of a real symmetric matrix.

ii

Solution

Set

y = P^{T} x

. Because

P

is an orthogonal matrix,

x = P y

and

x = 0

exactly when

y = 0

. The preceding diagonalization gives

x^{T} A x = y^{T} Dy = y_{1}^{2} + 11 y_{2}^{2} \geq y_{1}^{2} + y_{2}^{2} = ∥ x ∥_{2}^{2} .

Consequently $x^{T} A x \geq 0$ , with equality only when $x = 0$ . The matrix is a symmetric positive-definite matrix, not merely positive semidefinite. In the original coordinates the same identity is

x^{T} A x = \frac{( 3 x _{1} - x _{2} ) ^{2} + 11 ( x _{1} + 3 x _{2} ) ^{2}}{10},

which also makes positivity transparent.

iii

Solution

Real symmetry and positive definiteness are sufficient, and the preceding parts establish both properties for this matrix. If a residual becomes zero, stop: the solution has been reached and the displayed step quotient should not be evaluated as

0/0

For a convergence justification, let

x_{*}

solve

A x_{*} = b

, let

e = x_{*} - x

, and let

r = A e

. The quadratic energy error is

E = e^{T} A e /2

. Moving by

α r

, with

α = (r^{T} r) / (r^{T} A r)

, is exact line search for a positive-definite quadratic and gives

E_{new} = E - \frac{( r ^{T} r ) ^{2}}{2 r ^{T} A r} .

Writing

λ_{m i n}, λ_{m a x} > 0

for the extreme eigenvalues, one has

r^{T} A r \leq λ_{m a x} r^{T} r

and

r^{T} r = e^{T} A^{2} e \geq λ_{m i n} e^{T} A e

. Therefore

E_{new} \leq (1 - \frac{λ _{m i n}}{λ _{m a x}}) E .

The factor lies below one, so the energy tends to zero and positive definiteness forces

x \to x_{*}

. Here the bound is

E_{new} \leq (10/11) E

, since the eigenvalues are 1 and 11. This proves convergence for every initial vector, rather than merely checking one numerical iteration.

iv

Solution

From the zero initial vector, the linear-system residual is

r_{0} = (1, 1)^{T}

. Then

r_{0}^{T} r_{0} = 2

A r_{0} = (5, 13)^{T}

, and

r_{0}^{T} A r_{0} = 18

. The step is

α_{0} = 1/9

, giving

x_{1} = (1/9 1/9) .

As a check, the new residual is

(4/9, - 4/9)^{T}

, orthogonal to the preceding residual as expected after this exact line search. It is nonzero, so one iteration has not already solved the system.

b

i

Solution

The normal equations for linear least squares are

A^{T} A x = A^{T} b .

The supplied QR decomposition gives full column rank because

R

is invertible and

Q^{T} Q = I

. Hence, for every nonzero

u

u^{T} A^{T} A u = ∥ A u ∥_{2}^{2} > 0

. Thus

A^{T} A

is a symmetric positive-definite matrix and the displayed square system is nonsingular.

ii

Solution

Substitution gives

R^{T} R x = R^{T} Q^{T} b

. Since

R^{T}

is invertible, cancel it on the left to obtain the nonsingular triangular system

R x = Q^{T} b .

This is the reduced QR least-squares solution. Its geometric justification is the orthogonal decomposition

∥ A x - b ∥_{2}^{2} = ∥ R x - Q^{T} b ∥_{2}^{2} + ∥ (I - Q Q^{T}) b ∥_{2}^{2} .

The second term is independent of

x

, while invertibility of

R

lets the first term be zero at exactly one point. Although

Q^{T} Q = I_{M}

, one must not replace

Q Q^{T}

I_{N}

Q

is tall and its product

Q Q^{T}

is the orthogonal projection onto its column space.

iii

Solution

The supplied factors give

Q^{T} b = (0, 2)^{T}

. Back substitution in

R x = Q^{T} b

yields

2 y = 2

and

10 x + 4 y = 0

, so

x = - 2/5, y = 1.

Multiplying by the original matrix gives

(1, 1, 1, 1)^{T}

, so this least-squares minimizer has residual zero: this particular overdetermined system is exactly consistent. Full column rank still guarantees uniqueness of the minimizer.

7

a

Solution

The implication introduction rule assumes $ϕ$ locally, derives $ψ$ under that assumption, then concludes $ϕ \to ψ$ while discharging the temporary assumption.
The disjunction elimination rule uses $ϕ \lor ψ$ and two local cases: one derives a common conclusion $κ$ from $ϕ$ , and the other derives that same $κ$ from $ψ$ . It concludes $κ$ and discharges both case assumptions.
The negation introduction rule assumes $ϕ$ locally and derives logical falsity. Discharging that assumption gives $\neg ϕ$ .

The boxes delimit a subproof and identify the lifetime of its temporary assumptions. A result depending on a boxed assumption is available inside that box and its nested boxes; it cannot simply be exported outside. The enclosing rule specifies what may be exported and which assumptions are discharged. Other premises on which the derivation depends remain undischarged. This assumption discharge discipline distinguishes a conditional argument from an unconditional proof.

b

Solution

Derive each negated component in its own subproof, then combine them. Assumption lines below begin local scopes; the listed discharge ranges close those scopes.

Line	Formula	Justification
1	$\neg (ϕ \lor ψ)$	Premise
2	$ϕ$	Assume locally
3	$ϕ \lor ψ$	Disjunction introduction rule, left, 2
4	$⊥$	Negation elimination rule, 1 and 3
5	$\neg ϕ$	Negation introduction rule, discharging 2–4
6	$ψ$	Assume locally
7	$ϕ \lor ψ$	Disjunction introduction rule, right, 6
8	$⊥$	Negation elimination rule, 1 and 7
9	$\neg ψ$	Negation introduction rule, discharging 6–8
10	$\neg ϕ \land \neg ψ$	Conjunction introduction rule, 5 and 9

Only the original premise remains open. No classical principle is needed for this direction of De Morgan's laws.

c

Solution

Assume the conjunction and obtain a contradiction in each of the two cases supplied by the premise:

Line	Formula	Justification
1	$\neg ϕ \lor \neg ψ$	Premise
2	$ϕ \land ψ$	Assume locally
3	$ϕ$	Conjunction elimination rule, left, 2
4	$ψ$	Conjunction elimination rule, right, 2
5	$\neg ϕ$	Assume first case
6	$⊥$	Negation elimination rule, 3 and 5
7	$\neg ψ$	Assume second case
8	$⊥$	Negation elimination rule, 4 and 7
9	$⊥$	Disjunction elimination rule, 1, 5–6 and 7–8
10	$\neg (ϕ \land ψ)$	Negation introduction rule, discharging 2–9

The two case assumptions disappear at line 9, while the conjunction assumption remains available until line 10. The proof uses only the primitive rules printed in the paper.

d

Solution

The supplied double-negation elimination rule provides the classical step needed to recover each positive component:

Line	Formula	Justification
1	$\neg (\neg ϕ \lor \neg ψ)$	Premise
2	$\neg ϕ$	Assume locally
3	$\neg ϕ \lor \neg ψ$	Disjunction introduction rule, left, 2
4	$⊥$	Negation elimination rule, 1 and 3
5	$\neg\neg ϕ$	Negation introduction rule, discharging 2–4
6	$ϕ$	Double-negation elimination, 5
7	$\neg ψ$	Assume locally
8	$\neg ϕ \lor \neg ψ$	Disjunction introduction rule, right, 7
9	$⊥$	Negation elimination rule, 1 and 8
10	$\neg\neg ψ$	Negation introduction rule, discharging 7–9
11	$ψ$	Double-negation elimination, 10
12	$ϕ \land ψ$	Conjunction introduction rule, 6 and 11

Both local negated assumptions have been discharged. The proof establishes the positive conjunction without assuming an unproved derived version of De Morgan's laws.

e

Solution

Write

H

for

(ϕ \to ψ) \to ϕ

. The following derives Peirce's law directly from the printed primitive rules, including double-negation elimination:

Line	Formula	Justification
1	$H$	Assume for the final implication
2	$\neg ϕ$	Assume locally
3	$ϕ$	Assume inside the scope of 2
4	$⊥$	Negation elimination rule, 2 and 3
5	$ψ$	Logical falsity elimination rule, 4
6	$ϕ \to ψ$	Implication introduction rule, discharging 3–5
7	$ϕ$	Implication elimination rule, 1 and 6
8	$⊥$	Negation elimination rule, 2 and 7
9	$\neg\neg ϕ$	Negation introduction rule, discharging 2–8
10	$ϕ$	Double-negation elimination, 9
11	$((ϕ \to ψ) \to ϕ) \to ϕ$	Implication introduction rule, discharging 1–10

Every assumption is discharged, so the last formula is a theorem. In particular, no unproved appeal to the derived RAA rule is hidden in the argument.

8

a

Solution