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

a

Solution

For bits

a, b

, use two negation logic gates and two AND gates:

L = (\neg a) \land b, G = a \land (\neg b) .

The two unequal bit pairs activate their respective output; the equal pairs activate neither. In particular, a digital comparator never produces

L = G = 1

b

Solution

Split each input into its more and less significant

n

-bit halves:

a = 2^{n} a_{H} + a_{L}

and

b = 2^{n} b_{H} + b_{L}

. Let the two digital comparators produce

(L_{H}, G_{H})

and

(L_{L}, G_{L})

. The more significant halves are equal exactly when

E_{H} = \neg (L_{H} \lor G_{H})

. The comparator composition is therefore

L = L_{H} \lor (E_{H} \land L_{L}), G = G_{H} \lor (E_{H} \land G_{L}) .

Implement

E_{H}

with a logical disjunction followed by a negation, then use two AND gates and two more logical disjunction logic gates. If

a_{H} \neq = b_{H}

, the difference

2^{n} (a_{H} - b_{H})

has magnitude at least

2^{n}

, whereas

∣ a_{L} - b_{L} ∣ \leq 2^{n} - 1

; hence the more significant comparison decides the result. If

a_{H} = b_{H}

, the lower comparison decides it. This proves correctness in every case using a constant number of extra logic gates.

c

Solution

Apply comparator composition recursively in a balanced binary tree, with one-bit digital comparators at its leaves. For a power of two

n

, the circuit size and circuit depth satisfy

S (n) = 2 S (n /2) + O (1), D (n) = D (n /2) + O (1) .

There are

n

leaves and

n - 1

internal nodes, so the circuit size is $O (n)$ and the combinational delay is $O (lo g n)$ . Here each fixed-fan-in logic gate has bounded delay. For arbitrary

n

, pad both inputs with leading zero bits to the next power of two, which is less than

2 n

; this preserves their unsigned interpretation and both bounds.

d

Solution

Use a hierarchical leading-zero counter. A block of

2^{j}

bits returns a zero flag

z

and

j

low count bits

r

: its count leading zeros result is the concatenation

(z, r)

. Thus

z = 1

means that the block is entirely zero and

r = 0

; otherwise

z = 0

and

r

is its leading-zero count. A one-bit block needs just

z = \neg x

and no low count bits.

For a block of

n = 2^{k}

bits, run two such Boolean circuits on the upper and lower halves in parallel. Write their flags as

z_{H}, z_{L}

and their

k - 1

low count bits as

h_{i}, ℓ_{i}

. Set

z = z_{H} \land z_{L}, r_{k - 1} = z_{H} \land \neg z_{L}, r_{i} = (\neg z_{H} \land h_{i}) \lor (z_{H} \land ℓ_{i}) (0 \leq i < k - 1) .

The last expression is a two-input multiplexer. When the upper half is nonzero, its count is already the answer and

r_{k - 1} = 0

. When only the upper half is zero,

r_{k - 1} = 1

supplies the contribution

n /2

while the multiplexers supply the lower half's count. When both halves are zero, the answer is

(1, 0, \dots, 0)

, representing

n

. This special encoding avoids an adder on the critical path.

Each node adds constant circuit depth, even though it uses

O (k)

logic gates for its parallel multiplexers. Hence

D (2^{k}) = D (2^{k - 1}) + O (1) = O (k), S (2^{k}) = 2 S (2^{k - 1}) + O (k) = O (2^{k}) .

Indeed the internal-node work is bounded by a constant times

\sum_{j = 1}^{k} (n / 2^{j}) j < 2 n

, and the

n

leaves add

O (n)

. Delay is $O (lo g n)$ and size is $O (n)$ , counting fixed-fan-in logic gates and the usual wire fan-out model.

Figure 1.
Leading-zero summaries combine in parallel: the input $00000101$ gives the four-bit count $0101$
. Internal nodes display their block length and encoded leading-zero count; leaves display the one-bit count. A count's first bit is the shared all-zero flag. The highlighted branch supplies the low count at the root. **Details**.

2

a

Solution

Use the AAPCS32 convention: r0 holds the input address, r1 the length, and r0 receives the result. The following Thumb instruction set assembly language uses only scratch processor registers, so no callee-saved registers need saving. Assume the array is valid, halfword-aligned, and has nonnegative length; for the mathematical sum assume it fits a signed 32-bit two's complement integer.

.syntax unified
.thumb
.thumb_func
sum16:
    movs r2, #0             @ accumulated sum
    cmp  r1, #0
    ble  .Ldone             @ empty array; also returns 0 if n < 0
.Lloop:
    movs r3, #0             @ Thumb signed load needs a register offset
    ldrsh r3, [r0, r3]      @ signed halfword at a; offset read before r3 changes
    adds r2, r2, r3         @ include this signed value
    adds r0, r0, #2         @ advance by one short, not one byte
    subs r1, r1, #1         @ one fewer element remains
    bne  .Lloop
.Ldone:
    movs r0, r2             @ result register
    bx   lr                 @ leaf routine: lr was not overwritten

After

j

iterations, the loop invariant is that r2 contains the first

j

elements' sum, r0 points to element

j

, and r1 is

n - j

. The sign extension in ldrsh supplies the correct signed addend. One iteration preserves this loop invariant, and the decreasing remaining length proves algorithm termination. For the seven-element calls, the sum lies between

- 229376

and

229369

, so it fits. For longer arrays that overflow, these instructions compute the sum modulo

2^{32}

; that is not a claim about defined signed C programming language overflow behavior. The operand forms are those of the paper's reference sheet.^[ref]

b

Solution

Let the stored bits be

b_{15}, \dots, b_{0}

and let

s = b_{15}

. The sign extension performed by ldrsh keeps output bit

i

equal to

b_{i}

for

0 \leq i \leq 15

, and sets every output bit

16 \leq i \leq 31

s

. Thus a nonnegative halfword gets sixteen leading zero bits, while a negative halfword gets sixteen leading one bits.

Its signed 32-bit two's complement value is

- s 2^{31} + s \sum_{i = 16}^{30} 2^{i} + \sum_{i = 0}^{15} b_{i} 2^{i} = - s 2^{16} + s 2^{15} + \sum_{i = 0}^{14} b_{i} 2^{i} = - s 2^{15} + i = 0 \sum 14 b_{i} 2^{i} .

The last expression is exactly the original signed 16-bit value. The equality uses the finite geometric series

\sum_{i = 16}^{30} 2^{i} = 2^{31} - 2^{16}

. In particular, simply inserting zero bits would be wrong for a negative halfword: its unsigned interpretation differs from its signed value by

2^{16}

c

Solution

Keep total in the callee-saved register r4, and the first returned sum in the callee-saved register r5. Suppose the surrounding function has made an aligned stack frame with the local seven-halfword array at the current sp, occupying fourteen bytes in a sixteen-byte slot. One possible frame setup is push {r4,r5,r6,lr} followed by sub sp,sp,#16; the earlier code initializes total, regular, and special before this fragment.

    ldr  r0, =regular       @ assembler literal load of the global array address
    movs r1, #7
    bl   sum16
    movs r5, r0             @ first sum must survive the next call

    add  r0, sp, #0         @ current frame's local special array
    movs r1, #7
    bl   sum16
    muls r0, r5, r0         @ second sum times first sum
    adds r4, r4, r0         @ update total

The AAPCS32 permits each call to overwrite r0–r3, r12, and condition flags, but requires preservation of r4–r8, r10, r11, and sp. Thus both r4 and r5 remain valid even if sum16 is replaced by another conforming implementation. bl changes the link processor register lr, so the enclosing function saves its own return address in its prologue. Its epilogue can use add sp,sp,#16 and pop {r4,r5,r6,pc}. The frame uses thirty-two bytes in total, preserving the required eight-byte stack pointer alignment at both calls.^[ref]

The two calls may be evaluated in this order. Assume the product and final addition fit the signed 32-bit result expected by the source program; unlike each individual seven-element sum, their product need not fit. The assembly language operations retain their low 32 bits if this assumption fails, whereas signed integer overflow in the C programming language has different semantics.

3

a

Solution

Maintain the latest five temperature readings in a circular buffer, together with their running sum. The following C programming language code spells out the message passing interface rather than assuming a particular library: send(dst,&m) is a blocking synchronous message passing send; receive(src,&m) receives from the specified sender or ANY and returns the sender's identity; sendrec(dst,&m) atomically sends the request and waits for that sender's reply in the same message object. Successful, reliable operations are assumed. Message contents are copied by the interface.

enum { ANY = -1, TIMER = 1, TEMP = 2 };
enum { PULSE, PING, REQUEST, REPLY };
typedef struct {
    int type;
    int period_ms;
    double value;
} Message;

extern void send(int dst, const Message *m);
extern int receive(int src, Message *m);
extern void sendrec(int dst, Message *m);

void smooth(void) {
    double history[5] = {0};
    double sum = 0;
    int count = 0, next = 0;
    Message m = { .type = PULSE, .period_ms = 1000 };
    send(TIMER, &m);                 /* subscribe once */

    for (;;) {
        int sender = receive(count < 5 ? TIMER : ANY, &m);
        if (sender == TIMER && m.type == PING) {
            Message t = { .type = REQUEST };
            sendrec(TEMP, &t);       /* matching REPLY contains t.value */
            if (count == 5)
                sum -= history[next];
            else
                ++count;
            history[next] = t.value;
            sum += t.value;
            next = (next + 1) % 5;
        } else if (count == 5 && m.type == REQUEST) {
            Message answer = { .type = REPLY, .value = sum / 5.0 };
            send(sender, &answer);
        }
    }
}

Before the fifth reading, selective reception from TIMER prevents premature client requests from being accepted. Such clients wait at their synchronous sends; they are not given a partial arithmetic mean. Thereafter the operating-system process receives both timer messages and client requests. Each accepted PING initiates one measurement; each accepted client request returns the arithmetic mean of the five most recently completed measurements, without initiating another measurement or changing the circular buffer.

The loop invariant is that count is the number of valid readings, capped at five, sum is their sum, and next is the next unused slot during startup or the oldest slot afterwards. Removing the overwritten reading and adding the new one preserves this loop invariant. Each update and reply uses

O (1)

time complexity and

O (1)

storage, since the window length is fixed. Under timely sensor replies, timer delivery and process scheduling, measurements are initiated once per second. The next parts explain failures of these timing assumptions; the code does not promise one-second sampling when the sensor itself cannot sustain it.

b

Solution

With synchronous message passing, the smoothing operating-system process can still be waiting for TEMP when its next PING is due. If the timer service sends to subscribers serially, it blocks on this unready recipient and cannot deliver the other subscribers' ticks: one slow sensor can delay every timer client through head-of-line blocking. Once it resumes, implementations may deliver late ticks, drift from their schedule, or accumulate overdue work.

The consequence depends on the delivery model. With buffered sends the timer need not block immediately, but its queue can grow or overflow; the smoothing operating-system process still cannot process readings at a sustained rate faster than the sensor. A nonblocking notification mechanism or separate timer-delivery workers can isolate other subscribers, while coalescing missed ticks prevents an unlimited backlog. These changes do not make an over-slow sensor meet the original sampling rate.

c

Solution

With a synchronous reply, send(client,&answer) blocks until the client receives. An indefinitely unready client therefore stalls the smoothing operating-system process, which may in turn stall the timer service and its other clients as in the preceding part. If the client is merely delayed, this is blocking and delayed service; a deadlock requires a circular wait or a client that will never receive.

Requiring correctly used synchronous send-and-receive helps. A client calling sendrec(SMOOTH,&m) is committed to waiting for the matching reply as soon as its request has been accepted. This closes the scheduling window between a separate send and receive and prevents unrelated client computation from postponing that receive. It does not by itself fix slow measurements, arbitrary failures, circular dependencies between other services, or lack of CPU scheduling. With buffered replies the initial effect may instead be queue growth, depending on the message passing contract.

d

Solution

In a cooperative scheduler, a permanently runnable background operating-system process that never yields can monopolize the CPU. The timer service, smoothing operating-system process, and display may then fail to run even when their messages are ready. Correct message passing alone does not supply process scheduling.

Use timer-driven scheduling preemption, so an interrupt can force a context switch without cooperation. To give the measurement and display work bounded response despite background computation, use priority scheduling with the background operating-system process below the responsive services, or an explicit reservation policy. Round-robin scheduling gives CPU access among a fixed finite runnable set, but meeting a particular deadline additionally requires bounded service execution and sufficient CPU capacity.

4

a

Solution

Write

A = diag (λ_{1}, \dots, λ_{n})

and

v_{i} = P^{- 1} e_{i}

, where

e_{i}

are the standard basis vectors. Since

A P^{- 1} = P^{- 1} A

A v_{i} = P^{- 1} A e_{i} = λ_{i} v_{i} .

Thus the columns of $P^{- 1}$ form an eigenbasis, and the requested ordered basis is

D = (P^{- 1} e_{1}, \dots, P^{- 1} e_{n})

. Its basis matrix is

P^{- 1}

, giving

[t]_{D} = P A P^{- 1} = A

. More completely, for each distinct eigenvalue

λ

, its eigenspace is

E_{λ} (A) = span {P^{- 1} e_{i} : λ_{i} = λ} .

All nonzero vectors in these eigenspaces are eigenvectors; when an eigenvalue repeats, they need not be individual columns of

P^{- 1}

b

Solution

Let

P A P^{- 1} = diag (α_{1}, \dots, α_{n})

and

PB P^{- 1} = diag (β_{1}, \dots, β_{n})

. Then

P (A + B) P^{- 1} = diag (α_{1} + β_{1}, \dots, α_{n} + β_{n}) .

By matrix similarity, every eigenvalue of $A + B$ is $α_{i} + β_{i}$ for some $i$ . These are corresponding eigenvalues on the common eigenbasis, rather than every possible pairwise sum. This is eigenvalue addition in a common eigenbasis.

c

Solution

With the two diagonal matrices from the preceding part, write

D_{A} = P A P^{- 1}

and

D_{B} = PB P^{- 1}

. Their diagonal products agree entry by entry, so

D_{A} D_{B} = D_{B} D_{A}

. Therefore

A B = P^{- 1} D_{A} D_{B} P = P^{- 1} D_{B} D_{A} P = B A .

Hence simultaneous diagonalization implies that

A, B

are commuting operators.

d

Solution

Using

B A = A B

and linearity,

B (A v) = A (B v) = A (λ v) = λ A v .

This establishes that commuting maps preserve eigenspaces. The vector

A v

can be zero, so this step alone does not assert that

A v

is an eigenvector.

e

Solution

Work over the field containing the stated

n

distinct eigenvalues of

B

; in a real formulation these must be real to obtain real eigenvectors. Choose one eigenvector for each distinct eigenvalue. By independence of eigenvectors for distinct eigenvalues, these

n

vectors are a basis. Consequently each eigenspace

E_{λ} (B)

has dimension one: in an expansion in this eigenbasis,

Bw = λ w

forces every coefficient with a different eigenvalue to vanish.

Now let

v \neq = 0

be any eigenvector of

B

. By part (d),

A v

belongs to its one-dimensional eigenspace, so

A v = μv

for some scalar

μ

. This proves that $v$ is an eigenvector of $A$ , including the case

A v = 0

, where

μ = 0

. This is the crucial one-dimensional step in simple spectrum gives simultaneous diagonalization.

f

Solution

The

n

independent eigenvectors

v_{1}, \dots, v_{n}

B

from part (e) are also eigenvectors of

A

. Put

S = (v_{1} \dots v_{n})

and

P = S^{- 1}

. Then

P A P^{- 1} = diag (μ_{1}, \dots, μ_{n}), PB P^{- 1} = diag (λ_{1}, \dots, λ_{n}) .

This supplies the required simultaneous diagonalization over the same field as in part (e).

g

Solution

For

n = 2

, take

A = (0010), B = I_{2} .

They are commuting operators because every matrix commutes with the identity matrix. However

A

has only the eigenvalue zero, and

ker A = span {(1, 0)^{T}}

has dimension one. It has no eigenbasis, so it cannot appear in any simultaneous diagonalization. Equivalently, a diagonal matrix similar to this nonzero nilpotent matrix would have to be zero, an impossibility. For any prescribed

n \geq 2

, use

A = E_{12}

and

B = I_{n}

; its zero eigenspace has dimension

n - 1

. For

n = 1

no such example exists.

5

a

Solution

The zero matrix has the required pattern, and matrix addition and scalar multiplication preserve every prescribed zero entry. This proves the vector subspace condition. A basis consists of the matrix units

{E_{ii} : 1 \leq i \leq n} \cup {E_{i, i + 1}, E_{i + 1, i} : 1 \leq i < n} .

They independently select every permitted entry of a tridiagonal matrix, so the dimension is $n + 2 (n - 1) = 3 n - 2$ for

n \geq 1

b

i

Solution

For

D = diag (d_{1}, d_{2}, d_{3})

, the upper entry of

D^{- 1} A D

in positions

i, i + 1

b_{i} d_{i + 1} / d_{i}

, and the corresponding lower entry is

c_{i} d_{i} / d_{i + 1}

. They are equal when

(d_{i + 1} / d_{i})^{2} = c_{i} / b_{i}

. All coefficients used here are positive, so choose

D = diag (1, c_{1} / b_{1}, c_{1} c_{2} / (b_{1} b_{2})) .

Direct matrix multiplication gives the symmetric matrix

D^{- 1} A D = a_{1} b_{1} c_{1} 0 b_{1} c_{1} a_{2} b_{2} c_{2} 0 b_{2} c_{2} a_{3} .

Its pattern remains tridiagonal. This is positive diagonal symmetrization of a tridiagonal matrix.

ii

Solution

For the analogous positive off-diagonal entries in size

n

, take

d_{1} = 1, d_{i} = j = 1 \prod i - 1 \frac{c _{j}}{b _{j}} (2 \leq i \leq n), D = diag (d_{1}, \dots, d_{n}) .

The same entrywise computation gives

(D^{- 1} A D)_{ii} = a_{i}

and

(D^{- 1} A D)_{i, i + 1} = (D^{- 1} A D)_{i + 1, i} = b_{i} c_{i}

, with every other entry zero. Thus the result is a symmetric matrix with a tridiagonal pattern. Positivity of the diagonal entries

a_{i}

is not needed for this positive diagonal symmetrization of a tridiagonal matrix; positivity of

b_{i}, c_{i}

ensures the displayed positive, invertible

D

. In particular, the assertion is not an arbitrary-real-coefficient symmetrization claim when the off-diagonal signs differ.

iii

Solution

They are similar matrices, so their eigenvalues, with algebraic multiplicities, are identical. Explicitly,

det (t I - D^{- 1} A D) = det (D^{- 1} (t I - A) D) = det (t I - A) .

Moreover their eigenvectors correspond by

A v = λ v ⟺ (D^{- 1} A D) (D^{- 1} v) = λ D^{- 1} v

. Since the transformed matrix is a real symmetric matrix, the spectral theorem for real symmetric matrices also shows that

A

has real eigenvalues and is a diagonalizable matrix.

c

Solution

Use banded Gaussian elimination followed by back substitution. To distinguish the right-hand side from the upper-diagonal coefficients

b_{i}

, write it as

r_{i}

. If the modified pivot elements are nonzero, the tridiagonal elimination recurrences are

p_{1} = a_{1}, q_{1} = r_{1}, m_{i} = \frac{c _{i - 1}}{p _{i - 1}}, p_{i} = a_{i} - m_{i} b_{i - 1}, q_{i} = r_{i} - m_{i} q_{i - 1} (2 \leq i \leq n) .

They eliminate just the one entry below each pivot element. Solve the resulting upper bidiagonal matrix system by

x_{n} = q_{n} / p_{n}, x_{i} = (q_{i} - b_{i} x_{i + 1}) / p_{i} (i = n - 1, \dots, 1) .

There is a bounded number of arithmetic operations per row in each sweep, giving $O (n)$ arithmetic operations and $O (n)$ storage. The unpivoted recurrences cost

8 n - 7

arithmetic operations under the usual scalar-operation count.

For a general tridiagonal matrix, nonsingularity alone does not guarantee these pivot elements. If a zero or unsafe pivot element occurs, use partial pivoting between the current row and the next row. These are the only possible nonzero candidates in the current column; adjacent row swaps introduce at most a second upper diagonal. Tracking that fill-in keeps both Gaussian elimination and back substitution at

O (n)

arithmetic operations. For example,

(0110)

is invertible but requires a row swap. If the input is singular, report a zero final pivot element; a unique solution cannot be promised, and compatibility or free-variable analysis is a separate issue. No nonsingularity or safe-pivot assumption is silently inferred from the word tridiagonal.

d

i

Solution

Let

f_{j}

be the determinant of the leading

j \times j

principal submatrix. Expansion along the last row gives an

a_{j} f_{j - 1}

term and a

c_{j - 1}

term with negative cofactor sign. In the latter minor, the final column has only

b_{j - 1}

nonzero, and deleting that row and column leaves the leading

(j - 2) \times (j - 2)

principal submatrix. Thus the tridiagonal determinant recurrence is

f_{0} = 1, f_{1} = a_{1}, f_{j} = a_{j} f_{j - 1} - c_{j - 1} b_{j - 1} f_{j - 2} (j \geq 2) .

Here

f_{0} = 1

is the empty determinant convention, needed to include

f_{2} = a_{1} a_{2} - b_{1} c_{1}

. The derivation uses cofactor expansion, so the recurrence relation remains valid when coefficients or intermediate determinants vanish; it never divides by a pivot element.

ii

Solution

Evaluate the recurrence relation successively, retaining only the preceding two values. Each of the

n - 1

updates uses three multiplications and one subtraction. Hence $4 (n - 1) = O (n)$ arithmetic operations and $O (1)$ auxiliary storage suffice, excluding the stored input. Naively branching into two recursive calls would repeat work; the sequential computation is essential. This is an arithmetic-operation bound, not a bit-complexity bound for arbitrarily large exact integers.

6

a

Solution

Writing the given bases as

(u_{1}, \dots, u_{p})

and

(v_{1}, \dots, v_{q})

, a basis of the Cartesian product with its componentwise vector space operations is

((u_{1}, 0), \dots, (u_{p}, 0), (0, v_{1}), \dots, (0, v_{q})) .

This is the direct sum basis. Therefore $dim (W_{1} \times W_{2}) = p + q = dim W_{1} + dim W_{2}$ . The construction includes zero-dimensional factors, whose corresponding portion of the basis is empty.

b

i

Solution

The intersection of vector subspaces

W_{1} \cap W_{2}

contains zero, so

(0, 0) \in U

. If

(u, - u), (v, - v) \in U

and

a, b

are scalars, then

a (u, - u) + b (v, - v) = (a u + b v, - (a u + b v)) \in U,

because

a u + b v \in W_{1} \cap W_{2}

by the vector subspace conditions. These pairs belong to

W_{1} \times W_{2}

, since both

u

and

- u

belong to the required factors. Thus $U$ is a vector subspace of $W_{1} \times W_{2}$ .

ii

Solution

Define

f : W_{1} \cap W_{2} \to U

f (u) = (u, - u)

. It is well-defined by the definition of

U

, and

f (a u + b v) = (a u + b v, - a u - b v) = a f (u) + b f (v) .

Thus

f

is a linear map. If

f (u) = f (v)

, comparing first components gives

u = v

, proving injectivity. Every element of

U

has the form

(u, - u) = f (u)

, proving surjectivity. Hence $f$ is a linear isomorphism, with inverse

(u, - u) \mapsto u

, and

dim U = dim (W_{1} \cap W_{2})

c

Solution

Every output

u_{1} + u_{2}

lies in the sum of subspaces

W_{1} + W_{2}

, since it is a linear combination of members of the two vector subspaces. For

u = (u_{1}, u_{2})

v = (v_{1}, v_{2})

and scalars

a, b

g (a u + b v) = (a u_{1} + b v_{1}) + (a u_{2} + b v_{2}) = a (u_{1} + u_{2}) + b (v_{1} + v_{2}) = a g (u) + b g (v) .

Therefore $g$ is a linear map. Every vector in

W_{1} + W_{2}

is such an output: group the terms of any linear combination from

W_{1} \cup W_{2}

according to their originating vector subspace. Thus the addition map of subspaces is also surjective.

d

Solution

The kernel of a linear map

g

is precisely

U

, since

g (u_{1}, u_{2}) = 0 ⟺ u_{2} = - u_{1} ⟺ (u_{1}, u_{2}) = (u, - u), u \in W_{1} \cap W_{2} .

Part (c) gives

im g = W_{1} + W_{2}

. Apply the rank-nullity theorem to the finite-dimensional vector space

W_{1} \times W_{2}

, and then parts (a) and (b):

dim W_{1} + dim W_{2} = dim (W_{1} \times W_{2}) = dim ker g + dim im g = dim (W_{1} \cap W_{2}) + dim (W_{1} + W_{2}) .

This proves the dimension formula for a sum of subspaces. The kernel of a linear map records exactly the freedom to transfer a shared vector from one summand to the other without changing their sum.

7

a

Solution

Eliminating logical implications gives

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

An absorption step simplifies this to the disjunctive normal form

A \lor \neg B \lor C .

Each one-literal term is a permitted logical conjunction in a disjunctive normal form.

b

Solution

The given logical implication is false exactly when

A = B

and

C \neq = D

. For every literal on

A, B, C, D

, there is such a false Boolean valuation making that literal true. For a prescribed value of

A

B

, give the other the same value and choose

C \neq = D

. For a prescribed value of

C

D

, give the other the opposite value and choose

A = B

Consequently no literal implies the whole propositional formula: there is no one-literal implicant. If an equivalent disjunctive normal form contained a one-literal conjunction term

ℓ

, then every Boolean valuation satisfying

ℓ

would satisfy that disjunctive normal form, contradicting its equivalence to the given propositional formula. This proves the claim. Even if auxiliary Boolean variables are allowed in the equivalent expression, a one-literal term on one of them fails too: fix any false Boolean valuation of the original four and set the auxiliary literal true. The word “conjunct” here refers to a conjunction term in the disjunctive normal form, not a factor in a conjunctive normal form.

c

Solution

Use structural induction on the propositional formula. The induction claim is that its truth value under the all-one Boolean valuation is one. A variable has this truth value by definition. For the induction step, suppose the immediate subformulas

α, β

each have truth value one. Then

[[α \lor β]] = 1 \lor 1 = 1, [[α \land β]] = 1 \land 1 = 1, [[α \to β]] = 1 \to 1 = 1.

These are all permitted construction cases. Thus every such propositional formula evaluates to one. Equivalently, the three logical connectives define one-preserving Boolean functions, and composition preserves this property. The variable-only base grammar matters: admitting a constant false formula would invalidate the claim.

d

Solution

Let

F = (A \to C) \lor (B \to C)

and

H = (A \lor B) \to C

, so the two displayed propositional formulas are

φ = F \to H

and

ψ = H \to F

. Their complete truth tables are

A 00001111 B 00110011 C 01010101 A \to C 11110101 B \to C 11011101 F 11111101 H 11010101 φ 11010111 ψ 11111111

Therefore $ψ$ is a tautology; $φ$ is not. For example

(A, B, C) = (0, 1, 0)

makes the antecedent

F

true via

A \to C

, while

H

is false because

B

is true and

C

is false. This explains why having just one of the two logical implications is insufficient for the forward direction.

e

Solution

Only

ψ

requires a natural deduction proof. Assume

h : (A \lor B) \to C

. Within that assumption, temporarily assume

a : A

. By disjunction introduction, obtain

A \lor B

; applying

h

by the implication elimination rule gives

C

. Discharge

a

by the implication introduction rule to derive

A \to C

. Disjunction introduction now gives

(A \to C) \lor (B \to C)

. Finally discharge

h

by the implication introduction rule:

\frac{[( A \lor B ) \to C ] ^{1} \frac{[ A ] ^{2}}{A \lor B} \lor I _{L} \frac{( A \lor B ) \to C A \lor B}{C} \to E \frac{C}{A \to C} \to I ^{, 2} \frac{A \to C}{( A \to C ) \lor ( B \to C )} \lor I _{L}}{( ( A \lor B ) \to C ) \to ( ( A \to C ) \lor ( B \to C ) )} \to I^{, 1} .

All temporary assumptions are discharged. No classical rule is needed; the same proof works in Intuitionistic propositional logic. The false propositional formula

φ

has no proof in this sound natural deduction system.

φ = \exists m \forall x \neg (x < m) .

In the closed interval

[0, 1]

, the witness is

m = 0

. In the open interval

(0, 1)

, every possible witness

m

has the smaller member

m /2

, so the first-order sentence is false. These witnesses are explanations in the ambient real numbers, not additional symbols in the first-order signature.

b

Solution

Express that the order is a dense order:

ψ = \forall x \forall y (x < y \to \exists z (x < z \land z < y)) .

In either real interval,

(x + y) /2

lies strictly between any two distinct ordered elements and remains in the domain. In the integers,

x = 0, y = 1

have no intervening integer, so this first-order sentence is false. The endpoints of a closed interval do not prevent a dense order.

c

Solution

Combine a minimum with an adjacent pair in a linear order:

ξ = (\exists m \forall x \neg (x < m)) \land \exists u \exists v (u < v \land \neg\exists w (u < w \land w < v)) .

[0, 1] \cup [2, 3]

, choose

m = 0, u = 1, v = 2

. The minimum and the adjacent pair in a linear order both exist. In

[0, 1]

, the dense order property rules out such an adjacent pair. In

Z

, adjacent pairs exist, but no minimum exists: for any

m

, the integer

m - 1

is smaller. Thus this first-order sentence has precisely the required three truth values. Neither the endpoints nor the numerical witnesses occur as constant symbols in the first-order sentence.

Figure 1.
A minimum and an adjacent pair distinguish the two-interval order from a closed interval and the integers
. Orange highlights the consecutive domain members $1$ and $2$ in the two-interval order. The dotted arrow crosses points absent from that domain. A closed real interval has intervening domain members; the integers have adjacent pairs but no minimum. **Details**.

d

Solution

Use the intended first-order structure of real arithmetic, with Int selecting the integers;

z

is the parameter in

ϕ_{z}

. A suitable first-order formula is

ϕ_{z} = \exists r (r * r = (1 + 1) * z \land \neg\exists p \exists q (Int (p) \land Int (q) \land \neg (q = 0) \land q * r = p)) .

The first condition requires a real square root of

2 z

. The second excludes every representation as a rational number

p / q

with a nonzero integer denominator. This uses only the listed function and constant symbols, the Int predicate and logical equality; in particular,

2

is written

1 + 1

and there is no extra division symbol. A square root exists exactly when

z \geq 0

, and either sign of a root is a rational number exactly when the other sign is a rational number, so the absence of a positivity condition on

r

does not affect the claim about the principal square root. At

z = 0

the formula is false; for

z < 0

there is no real witness. The meanings of

+

and

*

as real arithmetic, not just the meaning of Int, are part of this interpretation.

e

Solution

Two unary predicates suffice. Require all four unary predicate types to be inhabited:

\exists x (P (x) \land Q (x)) \land \exists x (P (x) \land \neg Q (x)) \land \exists x (\neg P (x) \land Q (x)) \land \exists x (\neg P (x) \land \neg Q (x)) .

There are no constants, no logical equality and no nonunary predicates. Any two of these conditions disagree on at least one predicate, so one domain element cannot witness both. Hence every satisfying first-order structure has at least four elements, by distinct witnesses from incompatible unary predicates. Conversely take domain

{a, b, c, d}

P = {a, b}

and

Q = {a, c}

: the four elements realize the four displayed unary predicate types, respectively. These element names describe the example; they are not constants in the first-order sentence.

y

x < y

is under

\exists x

, which would capture the inserted

x

. The other occurrence, in the outside disjunct

y < z

, has no enclosing quantifier. The inner

\forall z

does not bind the occurrence of

y

in its antecedent, so it creates no additional capture at that substitution site.

Rename the bound

x

to a fresh

u

, then carry out capture-avoiding first-order substitution. The result is

φ [x + z / y] = (\exists u (u < x + z \to \forall z (u < z + 2))) \lor (x + z < z) .

The inserted

z

u < x + z

remains free because it lies outside the scope of

\forall z

. One may additionally rename that bound

z

for readability, but it is not necessary for correctness.

ii

Solution

The term $x + z$ is free for substitution for $z$ . The only free occurrence of the target

z

is in the outside disjunct

y < z

, beyond both quantifier scopes. The occurrences under

\forall z

are bound variables and are not replaced. Therefore no renaming is required, and

φ [x + z / z] = (\exists x (x < y \to \forall z (x < z + 2))) \lor (y < x + z) .

The new

x

and

z

in the last disjunct are free. First-order substitution replaces the original free occurrences once; it does not recursively substitute into the inserted term.

g

Solution

The printed expression has one unmatched closing parenthesis. Remove that final surplus parenthesis and read the first disjunct as

\exists x P (x)

; the other disjunct has outer universal quantification over the displayed implication. To distinguish the two independent bound uses of

x

, rename the first to

u

Push the outer negation through the logical disjunction and through the quantifiers. Negating the implication preserves its existential antecedent and negates its consequent. Applying De Morgan's laws and the quantifier negation rules gives the negation normal form

(\forall u \neg P (u)) \land \exists x [(\exists y Q (x, y)) \land (\forall z \neg R (z)) \land (\exists t \neg T (x, t))] .