Year 1 of the computer science course of the University of Oxford (Prelims)

2023

Digital systems, linear algebra and introduction to formal proof (A10101W1)

Solutions to all eight questions of the Oxford Preliminary Examination held on 15 June 2023. Source release: released examination archive, member 2022/T/a10101w1.pdf. The cover identifies Trinity Term 2023. The three section headings and all question labels below follow this historical paper; its grouping is independent of subsequent course changes. Although candidates were asked to attempt at most five questions, every marked subpart is solved here.

In 8(b), the source's parenthetical definition describes a dominating set, while its name suggests a vertex cover. Both readings are treated explicitly. In 8(c)–(d), we make the scopes of the printed quantifiers explicit; in particular, the opening universal quantifiers in 8(c) govern both irreflexivity and transitivity. As usual in first-order logic, domains are nonempty, and graphs are finite simple graphs unless an infinite domain is specified.

Digital systems

1

a

Solution

Write an

n

-bit binary string as

A = a_{n - 1} \dots a_{1} a_{0}

, where each

a_{i} \in {0, 1}

and

a_{n - 1}

is most significant. Its unsigned interpretation and two's complement interpretation are

bin (A) = i = 0 \sum n - 1 a_{i} 2^{i}, twoc (A) = - a_{n - 1} 2^{n - 1} + i = 0 \sum n - 2 a_{i} 2^{i} .

Equivalently,

twoc (A) = bin (A) - a_{n - 1} 2^{n}

. The ranges are

0

through

2^{n} - 1

and

- 2^{n - 1}

through

2^{n - 1} - 1

, respectively. The same stored bits can therefore denote different integers depending on the chosen interpretation.

b

Solution

A logical right shift by

k

moves

a_{i + k}

into position

i

and fills the high positions with zero. Its unsigned interpretation is

bin (A LSR k) = \sum_{i = k}^{n - 1} a_{i} 2^{i - k} =: q .

Meanwhile the original unsigned interpretation decomposes as

a = 2^{k} q + r i = 0 \sum k - 1 a_{i} 2^{i}, 0 \leq r \leq 2^{k} - 1.

By integer division, $q = ⌊ a / 2^{k} ⌋$ , exactly the unsigned quotient. Thus the source instruction puts the required quotient into r1. This is a proof from binary representation, rather than an assumption that every kind of right shift implements every kind of division. The displayed bit argument applies to

0 \leq k \leq n

, with endpoint operations implemented as a copy or zero where appropriate.

c

Solution

For a 32-bit machine word and

1 \leq k \leq 31

, use a left bit shift followed by a logical right shift:

lsls r1, r0, #(32-k)
lsrs r1, r1, #(32-k)

The left shift discards all but the lowest

k

bits and moves those retained bits to the top. The logical right shift returns them to their original positions and fills the rest with zero. Hence r1 contains $a mod 2^{k}$ , the remainder identified in (b). For

k = 0

the remainder is zero; for

k = 32

it is

a

, so these endpoints can be handled directly.

On a reduced instruction set computer, a bit mask such as

2^{k} - 1

may not fit an instruction's immediate field. Masking may therefore require materializing the constant in another processor register, possibly using several instructions or a memory load. Small shift counts are directly encodable, so the two shifts can save code space, a temporary processor register, or a load. This is an architecture-dependent advantage, rather than a universal speed claim. The source's compact instruction forms support these immediate shifts, while their bitwise AND form takes its other operand from a processor register.^[ref]

d

Solution

Let

s = 1_{{a < 0}}

, let

b = 1023 s

, and let

u = (a + b) mod 1024

denote the least nonnegative residue. Here

a

is a signed 32-bit two's complement value. The source instructions, annotated with their derived values, are:

rem1024:
    asrs r3, r0, #31    // r3 = -s: all zero bits or all one bits
    lsrs r3, r3, #22    // r3 = b = 1023*s
    adds r0, r0, r3     // r0 = a+b
    lsls r0, r0, #22    // r0 has word value (a+b)*2^22 modulo 2^32
    lsrs r0, r0, #22    // r0 = u = (a+b) modulo 1024, in 0,...,1023
    subs r0, r0, r3     // r0 = u-b
    bx lr              // return u-b

The first instruction is an arithmetic right shift, so it replicates the sign bit. The second is a logical right shift, turning the all-one word into

1023

. The paired shifts then extract the low ten bits, as in (c). Their effect is the residue of

a + b

even if its two's complement interpretation is negative, because

1024

divides the word modulus

2^{32}

. The adjusted value

a + b

is representable for every input: positive inputs are unchanged, and negative inputs gain only

1023

For

a \geq 0

b = 0

, so the return value is the usual nonnegative remainder

a mod 1024

. For

a < 0

, put

t = - a > 0

as a mathematical integer, and write

t = 1024 q + r

with

0 \leq r < 1024

. If

r = 0

, then

u = 1023

and the return value is zero. If

1 \leq r \leq 1023

, then

u = (- t + 1023) mod 1024 = 1023 - r, u - b = - r .

These are precisely the remainders for C integer division, whose quotient truncates towards zero. In every case the result has the dividend's sign or is zero, has magnitude below

1024

, and satisfies

a = 1024 q_{C} + r_{C}

. The proof includes the smallest representable input:

t = - a

was used only in mathematical reasoning, not as an overflowing machine operation.^[ref]

e

Solution

Use the same bias, then an arithmetic right shift by ten:

div1024:
    asrs r3, r0, #31    // -1 when a<0, otherwise 0
    lsrs r3, r3, #22    // b = 1023 when a<0, otherwise 0
    adds r0, r0, r3     // a+b, representable for every signed input
    asrs r0, r0, #10    // floor((a+b)/1024)
    bx lr

An arithmetic right shift of a two's complement integer computes division rounded down. For

a \geq 0

, this already equals truncation towards zero. For

a < 0

, the signed power-of-two division by biasing identity is

trunc (a /1024) = ⌊ \frac{a + 1023}{1024} ⌋ .

Indeed, writing

- a = 1024 q + r

with

0 \leq r < 1024

makes the adjusted numerator

- 1024 q + (1023 - r)

; its quotient rounded down is

- q

for every

r

, including zero. Thus the code returns the signed quotient in all cases and contains no data-dependent branch. The final bx lr simply returns to the caller.

2

a

Solution

Use a message-passing mutual exclusion server with an owner field and a FIFO queue. A request includes its client's identity. The server handles one received message at a time, and a client has at most one outstanding request. The following pseudocode assumes reliable message passing and compliant clients:

owner = NONE
waiting = empty FIFO queue

forever:
    (kind, client) = receive_from_any_client()
    if kind == REQUEST:
        waiting.push_back(client)
    else if kind == RELEASE:
        assert client == owner
        owner = NONE

    if owner == NONE and not waiting.empty():
        owner = waiting.pop_front()
        send(owner, GRANT)

A client sends REQUEST, waits for GRANT, runs its complete animation, and sends RELEASE before making another request.

The invariant proving mutual exclusion is: at most one client has received an unreturned grant, and that client is owner. Only the final block issues a grant, and it first requires no current owner. A valid release removes that ownership. Since clients use the display only while holding a grant, simultaneous use is impossible. The FIFO queue prevents accepted requests from being overtaken by later ones. With eventual message delivery, continued server execution, and finite animations, each accepted request is eventually served; these progress assumptions are separate from the safety invariant.

b

Solution

Use two FIFO queues, one for each priority class, and perform nonpreemptive strict-priority arbitration whenever the display becomes free:

owner = NONE
ordinary = empty FIFO queue
urgent = empty FIFO queue

forever:
    message = receive_from_any_client()
    if message.kind == REQUEST:
        assert message.priority in {0, 1}
        if message.priority == 1:
            urgent.push_back(message.client)
        else:
            ordinary.push_back(message.client)
    else if message.kind == RELEASE:
        assert message.client == owner
        owner = NONE

    if owner == NONE:
        if not urgent.empty():
            owner = urgent.pop_front()
        else if not ordinary.empty():
            owner = ordinary.pop_front()
        if owner != NONE:
            send(owner, GRANT)

The same ownership invariant proves mutual exclusion. Among requests already accepted by the server, every pending urgent request takes precedence over every ordinary one. Each class retains its own arrival order. A newly received urgent request goes ahead of waiting ordinary requests but waits for the current animation's RELEASE; the given protocol has no interruption or revocation operation.

This is strict priority at dispatch, based on requests the server has received. Requests still in transit cannot influence a decision. If the transport provides a mailbox-draining operation, the server may also collect all currently delivered requests before dispatching; the two-FIFO queue selection rule remains the same.

Strict priority does not guarantee starvation freedom for ordinary clients under an endless supply of urgent work. If urgent traffic eventually stops, accepted requests have only finitely many earlier requests, and all service times are finite, every pending ordinary request is eventually granted. Guaranteeing ordinary progress under unlimited urgent traffic would require a different fairness policy, such as limiting consecutive urgent grants; that would relax strict priority.

c

Solution

A LIFO stack can make waiting clients starve. Suppose client

A

waits at the bottom of the stack. Before each current owner releases, a fresh client submits a request. That newest request is pushed above

A

and is selected next. Every animation can finish promptly while

A

waits forever.

This is LIFO starvation: service completion alone does not ensure starvation freedom. A FIFO queue prevents newer same-priority requests from passing

A

, whereas replacing either priority-class FIFO queue by a LIFO stack adds this problem even within one priority class. Strict priority can already starve ordinary work, as in (b); the LIFO stack introduces a further unfairness that can also affect urgent work.

3

a

Solution

Use a three-sample run detector. Just before clock edge

t

, let two stored bits

p

and

q

hold the input values at edges

t - 1

and

t - 2

. Initialise both to zero. With input

a_{t}

, define

w_{t} = a_{t} \land p \land q, p^{'} = a_{t}, q^{'} = p .

Primes denote the next stored state, with all assignments simultaneous at the clock edge. The output is the logical conjunction of the present input and its two preceding samples. By induction on clock edges, the stated interpretation of

p, q

is maintained, proving the required behaviour. Two bits of state suffice.

b

Solution

Store two bits: the output

z

, initially zero, and an armed bit

e

, initially one. Define the synchronous sequential circuit by

z^{'} = z \oplus (e \land c), e^{'} = d \lor (e \land \neg c) .

Here

\oplus

is exclusive or, and the input restriction

c \land d = 0

excludes conflicting commands. The output is the current stored

z

When armed, a sampled

c = 1

toggles

z

and clears

e

. Further

c

samples leave the output unchanged. A sampled

d = 1

sets

e = 1

without changing

z

, allowing a later

c

to toggle it again. The same clock edge cannot both rearm and trigger because

c, d

are never simultaneously high. Thus the first

c

toggles from zero to one, and subsequent toggles each require a new

d

followed by a later

c

c

Solution

Share the input-history bits of (a) between a high-run detector and a low-run detector. With

p, q

the two preceding input samples, put

c = a \land p \land q, d = \neg a \land \neg p \land \neg q .

These detector outputs are mutually exclusive. Feed them into (b). An explicit four-bit synchronous sequential circuit, with initial state

(p, q, e, z) = (0, 0, 1, 0)

, is

p^{'} = a, q^{'} = p, e^{'} = d \lor (e \land \neg c), z^{'} = z \oplus (e \land c) .

Every right-hand side uses the old state and the current input. In particular, the run detectors' combinational outputs are sampled by the toggle module at that same edge; there is no extra pipeline stage.

The first three consecutive high samples make

c = 1

at the third edge, toggling

z

and clearing

e

. Continuing high input cannot toggle it again. Only three consecutive low samples can make

d = 1

and rearm it; interrupted low runs do not suffice. After rearming, a new three-sample high run produces the next toggle. This proves the debounced toggle switch behaviour, including rejection of short high and low disturbances.

Figure 1.
The debounced toggle switch rejects interrupted runs, toggles on the third consecutive high sample, and rearms only on the third consecutive low sample; stored outputs are shown just after each clock edge
. **Details**.

d

Solution

Four state bits are necessary and sufficient. For each output value, distinguish three armed situations, remembering a trailing high run of length

0, 1, 2

, and three disarmed situations, remembering a trailing low run of length

0, 1, 2

. Thus a direct minimal behavioural description has

2 (3 + 3) = 12 states, ⌈ lo g_{2} 12 ⌉ = 4 bits .

All twelve situations are reachable. Different output values are immediately distinguishable. Within an armed group, a suitable number of high samples distinguishes the three run lengths by when the next toggle occurs. Within a disarmed group, a suitable number of low samples followed by three highs distinguishes the three rearming distances. An armed situation and a disarmed situation of the same output value are distinguished by an all-high continuation: the armed one eventually toggles and the disarmed one does not. Hence these twelve situations cannot be merged in a finite-state machine implementing the specification.

The shared-history design in (c) uses four bits, meeting this lower bound. Its sixteen encoded states have some behaviourally equivalent histories, so its encoding need not use only twelve combinations. Building two separate copies of (a) plus the two-bit module (b) would use six state-bearing elements; sharing the input history saves two.

Linear algebra

4

a

Solution

The

m

columns of

L

form a basis of

ker A^{⊤}

, so that null space has dimension

m

. The rank-nullity theorem applied to

A^{⊤} : R^{n} \to R^{n}

gives

rank A^{⊤} = n - m

. A matrix and its transpose have equal matrix rank, hence

rank A = n - m .

b

Solution

A^{⊤} x = 0

, the vector

x

belongs to the null space for which the columns of

L

are a basis. It is therefore a linear combination of those columns, so

x = L y

for some

y \in R^{m}

. Conversely, each column is annihilated by

A^{⊤}

, hence

A^{⊤} L = 0

and

x = L y

implies

A^{⊤} x = 0

. Thus

A^{⊤} x = 0 ⟺ x = L y for some y \in R^{m} .

The coordinate vector

y

is unique because the columns of

L

are linearly independent.

c

Solution

The analogous null space statement is

A x = 0 ⟺ x = R y for some y \in R^{m} .

Here the rank-nullity theorem and (a) ensure that

ker A

also has dimension

m

d

Solution

The columnwise null space conditions say

A^{⊤} L = 0

and

A R = 0

. Therefore

A^{⊤} B = A^{⊤} L R^{⊤} = 0, A B^{⊤} = A (R L^{⊤}) = (A R) L^{⊤} = 0.

Both right-hand sides are the

n \times n

zero matrix.

e

Solution

Both

L

and

R

have

m

linearly independent columns. The Gram matrix

R^{⊤} R

is invertible because

y^{⊤} R^{⊤} R y = ∥ R y ∥^{2} > 0 (y \neq = 0) .

Consequently

R^{⊤}

is a surjective linear map: for any

y \in R^{m}

, the choice

x = R (R^{⊤} R)^{- 1} y

satisfies

R^{⊤} x = y

. Hence

im B = L (im R^{⊤}) = im L .

The latter image of a linear map has dimension

m

, giving $rank B = m$ . If

m = 0

B = 0

and the conclusion is immediate. This argument explains why the product retains its full possible matrix rank; a general product of two matrices need not do so.

f

Solution

Expand the product and use (d) together with its transpose:

M M^{⊤} = (A + B) (A^{⊤} + B^{⊤}) = A A^{⊤} + A B^{⊤} + B A^{⊤} + B B^{⊤} = A A^{⊤} + B B^{⊤} .

Indeed

A B^{⊤} = 0

and

B A^{⊤} = (A B^{⊤})^{⊤} = 0

g

Solution

Fix one common eigenvector

v \neq = 0

, and write

A A^{⊤} v = λ v

and

B B^{⊤} v = μv

. By (d),

A A^{⊤} B B^{⊤} = A (A^{⊤} B) B^{⊤} = 0,

λ μv = 0

and at least one of the two eigenvalues is zero.

To exclude both being zero, use the kernel of a Gram product identity:

v^{⊤} A A^{⊤} v = ∥ A^{⊤} v ∥^{2}, v^{⊤} B B^{⊤} v = ∥ B^{⊤} v ∥^{2} .

If both products annihilate

v

, then

A^{⊤} v = B^{⊤} v = 0

. By (b),

v \in im L

, and by (e), this is

im B

. On the other hand,

B^{⊤} v = 0

makes

v

orthogonal to every vector in

im B

. In particular

v

is orthogonal to itself, so

∥ v ∥^{2} = 0

and

v = 0

, a contradiction.

Therefore each specified common eigenvector belongs to exactly one of $ker (A A^{⊤})$ and $ker (B B^{⊤})$ . Both eigenvalues are nonnegative by the displayed squared-norm identities, so the other eigenvalue is strictly positive. This is the spectral mechanism behind orthogonal null-space completion of a square matrix.

5

a

Solution

Take

V = R^{2}

and the linear map

h (x, y) = (x, 0)

. Then

R (h) = span {(1, 0)}, N (h) = span {(0, 1)} .

These two vector subspaces have zero intersection and together span

R^{2}

, so $V = R (h) \oplus N (h)$ as a direct sum of vector spaces.

b

Solution

Take

V = R^{2}

and the linear map

h (x, y) = (y, 0)

. Then

R (h) = N (h) = span {(1, 0)} .

Their intersection is nonzero and their sum is only one-dimensional. Hence $V \neq = R (h) \oplus N (h)$ . This nilpotent linear map has

h^{2} = 0

, illustrating why taking sufficiently high powers changes the situation.

c

Solution

For

v \in R (h^{m + k})

, choose

u

with

v = h^{m + k} u = h^{m} (h^{k} u)

. Thus

v \in R (h^{m})

, proving

R (h^{m + k}) \subseteq R (h^{m}) .

This is the decreasing-image part of stabilization of images of powers of a linear map. The convention

h^{0} = id_{V}

includes

m = 0

and

k = 0

d

Solution

Apply

h

to both sides of

R (h^{m}) = R (h^{m + 1})

. Because

h (R (h^{j})) = R (h^{j + 1})

, we obtain

R (h^{m + 1}) = R (h^{m + 2})

. Repeating this argument proves equality at every later step. More formally, an induction on

k

gives

R (h^{m + k}) = R (h^{m}) for all k \geq 0.

The base case is

k = 0

; the induction step follows from applying the linear map

h

and then the assumed first equality. Thus one equality permanently stabilizes the descending sequence of images of a linear map.

e

Solution

The dimensions of the nested images of a linear map

V = R (h^{0}) \supseteq R (h) \supseteq \dots

can strictly decrease at most

n

times. If all the first

n

inclusions are strict,

R (h^{n}) = 0

and is stable. Otherwise an earlier equality occurs and (d) makes every subsequent image equal. Thus in all cases

R (h^{n}) = R (h^{2 n}) .

By the rank-nullity theorem and inclusion of the null spaces, this also gives

ker h^{n} = ker h^{2 n}

. If

v \in R (h^{n}) \cap ker h^{n}

, write

v = h^{n} u

. Then

0 = h^{n} v = h^{2 n} u

, so

u \in ker h^{2 n} = ker h^{n}

and

v = 0

. Hence the intersection is zero. Finally the rank-nullity theorem gives

dim R (h^{n}) + dim ker h^{n} = n .

(3)

Zero intersection and this dimension sum prove

V = R (h^{n}) \oplus N (h^{n}) .

(4)

This is the finite-dimensional Fitting decomposition. It includes the zero-dimensional case, for which

V = 0

and the assertion is immediate.

6

a

Solution

Let

E_{ij}

denote a matrix unit, with its only nonzero entry equal to one in row

i

, column

j

. A basis for the vector space of real skew-symmetric matrices is

{E_{ij} - E_{ji} : 1 \leq i < j \leq n}, dim = \frac{n ( n - 1 )}{2} .

Each upper-triangular entry is free, its reflected lower-triangular entry is its negative, and every diagonal entry is zero. This is the basis of the space of real skew-symmetric matrices.

b

Solution

Using linearity and involutivity of the matrix transpose,

(B - B^{⊤})^{⊤} = B^{⊤} - B = - (B - B^{⊤}) .

Therefore $B - B^{⊤}$ is a skew-symmetric matrix.

c

Solution

Split

B

into its symmetric part and skew-symmetric part:

B = S \frac{B + B ^{⊤}}{2} + K \frac{B - B ^{⊤}}{2} .

Taking the transpose gives

S^{⊤} = S

and

K^{⊤} = - K

. Thus

S

is a symmetric matrix and

K

a skew-symmetric matrix. These formulas also show uniqueness, since a real matrix that is both symmetric and skew-symmetric is zero.

d

Solution

A^{⊤} = - A

, then the dot product satisfies

(A x) \cdot y = x^{⊤} A^{⊤} y = - x^{⊤} A y = - (A y) \cdot x .

Conversely, the assumed dot product identity gives

x^{⊤} (A^{⊤} + A) y = 0

for every

x, y

. Take

x = e_{i}

and

y = e_{j}

from the standard basis: every entry of

A^{⊤} + A

is zero. Hence $A^{⊤} = - A$ , proving the equivalence.

e

Solution

A

is a skew-symmetric matrix, the scalar

x^{⊤} A x

equals its own transpose, so

x^{⊤} A x = x^{⊤} A^{⊤} x = - x^{⊤} A x,

and it is zero over the real numbers.

Conversely, suppose the quadratic form

x^{⊤} A x

vanishes for every real vector. Substituting

x = e_{i}

gives

a_{ii} = 0

. Substituting

x = e_{i} + e_{j}

gives

a_{ij} + a_{ji} = 0

for

i \neq = j

. Therefore

A^{⊤} = - A

. This proves the quadratic-form criterion for a skew-symmetric matrix:

x^{⊤} A x = 0 for every x ⟺ A^{⊤} = - A .

f

Solution

For a real eigenvalue

λ

, choose a nonzero real eigenvector

v

with

A v = λ v

. By (e),

0 = v^{⊤} A v = λ v^{⊤} v .

Since

v^{⊤} v = ∥ v ∥^{2} > 0

, $λ = 0$ . If eigenvectors were initially allowed to be complex, the real matrix

A - λ I

has a nonzero real null space whenever it has a nonzero complex null space, so this choice of

v

remains justified.

g

Solution

The determinant is invariant under transpose, while multiplying all

n

rows by

- 1

multiplies it by

(- 1)^{n}

. Thus, for odd integer

n

det A = det A^{⊤} = det (- A) = (- 1)^{n} det A = - det A .

Over the real numbers, this forces $det A = 0$ , so

A

is a singular matrix. This is the odd-dimensional skew-symmetric singularity theorem.

h

Solution

(I + A) x = 0

, take its dot product with

x

and apply (e):

0 = x^{⊤} (I + A) x = ∥ x ∥^{2} + x^{⊤} A x = ∥ x ∥^{2} .

Hence

x = 0

. A square matrix with zero null space is an invertible matrix by the rank-nullity theorem. Therefore $I + A$ is nonsingular. This proves invertibility of identity plus a real skew-symmetric matrix.

Introduction to formal proof

7

a

Solution

Use

0

and

1

for false and true truth values. The truth table is:

$A$	$B$	$C$	$A \leftrightarrow B$	$\neg B \to C$	$φ$
$0$	$0$	$0$	$1$	$0$	$0$
$0$	$0$	$1$	$1$	$1$	$1$
$0$	$1$	$0$	$0$	$1$	$0$
$0$	$1$	$1$	$0$	$1$	$0$
$1$	$0$	$0$	$0$	$0$	$0$
$1$	$0$	$1$	$0$	$1$	$0$
$1$	$1$	$0$	$1$	$1$	$1$
$1$	$1$	$1$	$1$	$1$	$1$

The two satisfying rows with

A = B = 1

combine by eliminating

C

, while the remaining satisfying row has

A = B = 0, C = 1

. An equivalent disjunctive normal form is therefore

(A \land B) \lor (\neg A \land \neg B \land C) .

Expanding the logical biconditional into its two implications, and using

\neg B \to C \equiv B \lor C

, gives the conjunctive normal form

(\neg A \lor B) \land (A \lor \neg B) \land (B \lor C) .

Each form has exactly the same three satisfying assignments as the original propositional formula.

b

Solution

Apply structural induction to the formation of a propositional formula. Let

L (θ)

and

R (θ)

count its opening and closing parentheses, and use the usual grammar generated by propositional variables, any allowed truth constants, negation, and parenthesized binary logical connectives.

An atomic variable or truth constant contains neither kind of parenthesis, so

L = R = 0

. If

L (α) = R (α)

, prefixing negation leaves both counts unchanged. If the notation writes a negated formula with an extra pair of parentheses, it adds one to each and still preserves equality.

For a binary construction

(α \circ β)

, where

\circ

is an allowed binary logical connective,

L ((α \circ β)) = L (α) + L (β) + 1, R ((α \circ β)) = R (α) + R (β) + 1.

The two induction hypotheses make these equal. Every grammar construction preserves the property, so every propositional formula contains equally many left and right parentheses. This is balanced parentheses in propositional syntax.

c

Solution

Apply the propositional substitution simultaneously to the atomic variables:

φS = ((X \lor Y) \land (X \lor \neg Y)) \lor ((Y \to X) \to \neg X) .

By distributivity and the complementary literals

Y, \neg Y

(X \lor Y) \land (X \lor \neg Y) \equiv X .

The other disjunct simplifies using logical implication and absorption:

(Y \to X) \to \neg X \equiv \neg (\neg Y \lor X) \lor \neg X \equiv (Y \land \neg X) \lor \neg X \equiv \neg X .

(3)

Thus $φS \equiv X \lor \neg X \equiv ⊤$ , a tautology.

d

Solution

Interpret

x_{1}, \dots, x_{n}

as the bits of a binary number, with

x_{1}

most significant. Construct a propositional formula saying that this number is strictly less than

k

. This gives a quadratic-size formula with prescribed model count.

For

0 < k < 2^{n}

, write

k = (b_{1} \dots b_{n})_{2}

. For each

i

with

b_{i} = 1

, define the conjunction

T_{i} = (⋀_{j < i} ℓ_{j}) \land \neg x_{i}, ℓ_{j} = {x_{j}, \neg x_{j}, b_{j} = 1, b_{j} = 0.

The empty prefix for

i = 1

is omitted. Let $φ_{k} = ⋁_{i : b_{i} = 1} T_{i}$ . A Boolean valuation satisfies

T_{i}

exactly when its first difference from the binary representation of

k

is at position

i

, changing a one of

k

to a zero. All later bits are unrestricted. Hence these cases are disjoint and cover exactly the numbers

0, \dots, k - 1

Alternatively, counting the disjoint cases directly gives

# {satisfying assignments of φ_{k}} = \sum_{i : b_{i} = 1} 2^{n - i} = k .

Each

T_{i}

has length

O (i)

, including its logical connectives and parentheses; the total length is at most a constant multiple of

\sum_{i = 1}^{n} i = O (n^{2})

. The endpoints are

φ_{0} = ⊥

and

φ_{2^{n}} = ⊤

. If constants are unavailable and

n \geq 1

, use

x_{1} \land \neg x_{1}

and

x_{1} \lor \neg x_{1}

instead. Assignments are counted over all

n

specified variables, including any absent from the formula. For

n = 0

, the constants describe the two possible counts, zero and one. Thus the construction covers

0 \leq k \leq 2^{n}

, including the endpoint zero despite the source's word “positive”.

For example,

n = 4, k = 11 = (1011)_{2}

gives the disjoint cases

0 * * *

100 *

and

1010

, with

8 + 2 + 1 = 11

satisfying assignments.

Figure 1.
A quadratic-size formula with prescribed model count accepts the eleven four-bit numbers below $11$ : three disjoint prefix cases contribute $8$ , $2$ and $1$ satisfying assignments
. **Details**.

e

Solution

Keep the premise

P \to Q

open. Assume

Q \to \neg P

, then temporarily assume

P

. Two applications of the implication elimination rule produce

Q

and then

\neg P

, contradicting the temporary

P

. Discharge

P

using the negation introduction rule, then discharge

Q \to \neg P

using the implication introduction rule.

1. 2. 3. 4. 5. 6. 7. 8. P \to Q Q \to \neg P P Q \neg P ⊥ \neg P (Q \to \neg P) \to \neg P premise assumption [i] assumption [j] \to -elimination, 1, 3 \to -elimination, 2, 4 \neg -elimination, 3, 5 \neg -introduction, 3 - 6; [j] discharged \to -introduction, 2 - 7; [i] discharged .

This natural deduction proof uses only the supplied introduction and elimination rules. Line 6 is an application of the negation elimination rule; no classical contradiction principle is needed.

8

a

Solution

The nonempty simple graphs having an independent vertex cover of size at most two. The witnesses

x, y

select the cover. The clause

\neg E (x, y)

makes the selected vertices nonadjacent; the universal clause forbids every edge whose two endpoints both lie outside the selected set.

The witnesses need not be distinct, so a one-vertex cover is permitted by choosing

x = y

. A nonempty edgeless graph also satisfies the formula. The empty graph does not, because the existential quantifiers have no witnesses. Here independent vertex cover has its standard vertex cover meaning; 8(b)'s differing parenthetical definition is addressed separately below.

b

Solution

The source's explicit parenthetical condition is domination: every unselected vertex has a neighbour in the selected set. Together with independence this defines an independent dominating set. A first-order sentence expressing that definition with size at most three is

\exists x_{1} \exists x_{2} \exists x_{3} (1 \leq i < j \leq 3 ⋀ (x_{i} = x_{j} \lor \neg E (x_{i}, x_{j})) \land \forall v (i = 1 ⋁ 3 v = x_{i} \lor i = 1 ⋁ 3 E (v, x_{i}))) .

The finite conjunctions and disjunctions abbreviate three explicitly fixed terms, so this is a first-order formula. Repeated witnesses allow one- or two-element choices; the first conjunction enforces independence only between distinct selected vertices. The last clause says that every vertex is selected or adjacent to a selected vertex. With the usual nonempty-domain convention, any such choice has size at least one, so repeated witnesses cover all possibilities of size at most three.

For the standard meaning of independent vertex cover, replace the domination clause by

\forall u \forall v (E (u, v) \to (⋁_{i = 1}^{3} u = x_{i} \lor ⋁_{i = 1}^{3} v = x_{i})) .

This instead demands that every edge has a selected endpoint. These interpretations differ: in a triangle in a graph, any singleton is an independent dominating set, but no independent vertex cover exists. Giving both clauses avoids silently treating the source's two definitions as equivalent.

c

Solution

Read the initial universal quantifiers as governing the conjunction of irreflexivity and transitivity. Explicitly, the intended first-order sentence asserts

\forall x \forall y \forall z (\neg Q (x, x) \land ((Q (x, y) \land Q (y, z)) \to Q (x, z))) \land \forall x \exists y Q (x, y) .