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

Use Karnaugh maps with rows

w x

and columns

yz

, both in Gray code order

00, 01, 11, 10

. Juxtaposition means Boolean conjunction,

+

means Boolean disjunction, and a bar means Boolean negation. The minimal sum of products forms are

c = \overset{w}{ˉ} x + \overset{w}{ˉ} z + \overset{x}{ˉ} \overset{y}{ˉ},

and

d = w \overset{x}{ˉ} \overset{y}{ˉ} + \overset{w}{ˉ} \overset{x}{ˉ} y + \overset{w}{ˉ} y \overset{z}{ˉ} + \overset{w}{ˉ} \overset{x}{ˉ} \overset{z}{ˉ} + \overset{w}{ˉ} x \overset{y}{ˉ} z .

For

c

, the groups are

{4, 5, 6, 7}

{1, 3, 5, 7}

and

{0, 1, 8, 9}

. For

d

, take

{8, 9}

{2, 3}

{2, 6}

{0, 2}

and the isolated minterm

{5}

. Every group contains only required ones. The last

c

group wraps between the top and bottom map rows.

These covers are minimal:

c

needs its three essential groups, forced by inputs 6, 3 and 8. For

d

, input 5 is isolated, while 9, 3 and 6 each force their respective pair; input 0 still needs a further group. These five groups also attain the minimum literal count of 16.

Solution

Use

w, x, y

as the three select bits of the 8-to-1 multiplexer, so address

i = 4 w + 2 x + y

selects data input

D_{i}

. Connect

(D_{0}, D_{1}, D_{2}, D_{3}, D_{4}, D_{5}, D_{6}, D_{7}) = (\overset{z}{ˉ}, 1, z, \overset{z}{ˉ}, 1, 0, 0, 0) .

A single NOT gate produces

\overset{z}{ˉ}

, shared by

D_{0}

and

D_{3}

; the other connections are wires and constant logic levels. For each fixed select address the data input reproduces the corresponding two rows of the truth table, including zeros for all invalid codes.

d

Solution

Only now may the invalid codes 10–15 be marked as don't-care conditions. The

f

Karnaugh map gives

f = w + x \overset{y}{ˉ} + x \overset{z}{ˉ} + \overset{y}{ˉ} \overset{z}{ˉ} .

The groups are

{8, \dots, 15}

{4, 5, 12, 13}

{4, 6, 12, 14}

and

{0, 4, 8, 12}

. They cover all required ones, avoid valid-digit zeros, and may assign either output to invalid codes. The valid inputs 0, 5, 6 and 9 cannot share a valid implicant with each other, so at least four product terms are necessary. The displayed four-term cover uses only seven literals.

2

a

Solution

Use a four-state Moore machine. In state

A

wait for an outer-sensor activation;

B

combines the outer-only and both-sensors phases;

C

records that the visitor has reached the inner-only phase;

I

emits the one-cycle count pulse. Only

I

has INC = 1.

The complete state transition table, with input order

x_{1} x_{0}

, is

state    00    01    11    10    INC
 A        A     B     B     A      0
 B        A     B     B     C      0
 C        I     B     B     C      0
 I        A     B     B     A      1

For a normal entry the states are

A \to B \to B \to C \to I

; retreat after the first sensor instead gives

A \to B \to A

with no pulse. Repeated samples at one sensor remain in the corresponding phase. State

I

always exits on the next edge, so its output lasts exactly one clock period; an outer activation on that next edge goes directly to

B

, allowing the next visitor to start immediately.

This follows the question's single-visitor entry model and merges the two outer-active phases as its hint requests. Inputs are sampled synchronously; the table also specifies deterministic recovery for other sampled combinations. It is not a specification of a bidirectional occupancy counter for arbitrary overlapping entry and exit traffic.

Figure 1.
Four-state visitor-entry Moore machine with a one-clock output pulse
. Original state diagram. Edge labels use $x_{1} x_{0}$ . State I emits the count pulse; its transitions can accept the next visitor without an extra idle clock. **Details**.

b

Solution

Encode

(q_{1} q_{0})

A = 00

B = 01

C = 11

I = 10

, with reset to

A

. Two positive-edge-triggered D flip-flops store the state. Minimizing the Boolean functions from the complete table gives

D_{0} = x_{0} + q_{0} x_{1}, D_{1} = \overset{x}{ˉ}_{0} q_{0} (x_{1} + q_{1}), I NC = q_{1} \overset{q}{ˉ}_{0} .

Equivalently, the minimal sum of products form of

D_{1}

\overset{x}{ˉ}_{0} q_{0} x_{1} + \overset{x}{ˉ}_{0} q_{0} q_{1}

. The displayed factorization saves duplicated logic. The equations use only AND gates, OR gates and NOT gates; connect

D_{j}

to the corresponding flip-flop data input and use one common clock.

For example,

C

with input

00

gives

(D_{1} D_{0}) = 10

, entering the pulse state. In

I

, either

x_{0} = 1

gives

01

x_{0} = 0

gives

00

, independently of

x_{1}

; the pulse cannot persist. The four states are distinguishable by their current output or future response to inputs

00

and

10, 00

, so two state bits are also necessary.

c

Solution

Address a read-only memory with the two state bits and two input bits. Each word stores the two next-state bits and INC, so a direct replacement for all the combinational logic is $16 \times 3$ bits, or 48 bits. Program its 16 words from the state table, duplicating a state's output over all four input addresses. The two D flip-flops and clock remain outside the ROM.

If INC retains its separate two-state-bit decoder, only the next-state logic needs a $16 \times 2$ -bit ROM, plus that output gate. Storing output in a separate state-only ROM would use

4 \times 1

further bits. These factored options have a different boundary from replacing all the combinational logic with one ROM.

3

a

Solution

Device independence lets an application request input-output through a uniform interface without depending on a particular device's control registers, instruction protocol or geometry. A device driver translates the abstract requests into device-specific operations. Replacing one supported disk model with another can then preserve the application's file-reading interface.

b

i

Solution

First-come-first-served disk scheduling follows the arrival order:

133 -> 76 -> 157 -> 91 -> 142 -> 97 -> 135 -> 112 -> 23

The total seek distance is

57 + 81 + 66 + 51 + 45 + 38 + 23 + 89 = 450 tracks .

The initial position is 133; the earlier completed request at 135 is used to determine direction for the elevator policy, not added again to this total.

ii

Solution

Shortest-seek-time-first disk scheduling chooses the nearest remaining track after each service:

133 -> 135 -> 142 -> 157 -> 112 -> 97 -> 91 -> 76 -> 23

The distances are

2, 7, 15, 45, 15, 6, 15, 53

, giving 158 tracks. There are no distance ties along this service sequence.

iii

Solution

The previous motion from 135 to 133 fixes the initial direction as downward. Under SCAN disk scheduling, the head continues to the physical endpoint 0 before reversing:

133 -> 112 -> 97 -> 91 -> 76 -> 23 -> 0 -> 135 -> 142 -> 157

Thus SCAN crosses $133 + 157 = 290$ tracks, stopping once the final pending request has been served.

If “elevator” means LOOK disk scheduling, reversal occurs at the lowest pending request, 23, rather than track 0. Its route omits 0, and the total is $(133 - 23) + (157 - 23) = 244$ tracks. Stating the turnaround convention is necessary to make the numerical answer unambiguous.

Figure 1.
Disk scheduling service paths and the SCAN–LOOK turnaround distinction
. Original paths from the given starting position. The extra zero-track endpoint in SCAN is a movement step rather than a serviced request. Totals measure absolute track displacement. **Details**.

c

Solution

Conditioning on a cache hit or cache miss, the expected latency is

T (h) = h \cdot 1 + (1 - h) \cdot 45 = 45 - 44 h ms, 0 \leq h \leq 1.

This is a straight line from

(0, 45)

(1, 1)

; at hit rate

1/2

, the mean is 23 ms. The 45 ms is already the complete miss-service time in the question, so another cache-lookup millisecond is not added to it.

Figure 1.
Mean service time as a function of cache hit rate
. Original plot of $T (h) = 45 - 44 h$ milliseconds, including the endpoint and midpoint values. **Details**.

d

Solution

At 6000 revolutions per minute the disk makes 100 revolutions per second, so one turn takes 10 ms and the mean rotational latency is 5 ms. Adding seek time, data transfer time and controller overhead gives, using decimal MB,

12 + 5 + \frac{512}{5 \cdot 1 0 ^{6}} 1 0^{3} + 2 = 19.1024 ms \approx 19.1 ms .

Using

1 MB = 2^{20}

bytes instead gives 19.09765625 ms, with the same rounded answer. The calculation assumes the stated rate applies to the sector transfer and that the seek and overhead are each paid once.

e

Solution

Use binary units

1 KB = 2^{10}

bytes and

1 MB = 2^{20}

bytes, consistent with the given binary GB convention. Reading one average file takes seek plus rotation plus transfer; moving it requires the same costs again on the write:

t_{file} = 2 (0.005 + 0.004 + \frac{8 \cdot 2 ^{10}}{8 \cdot 2 ^{20}}) = 0.019953125 s \approx 20 ms .

A half-full 16 GB disk contains

8 \cdot 2^{30}

used bytes, or

N = 2^{20}

average files. Under the stated per-file disk compaction model,

T = N t_{file} = 20922.368 s \approx 5.81 hours .

A calculation with decimal KB and MB changes the unrounded figures, so the unit convention must be retained consistently. This model charges one seek and rotational delay on each read and each write; it does not assume a single streaming pass over the whole disk.

4

a

Solution

As written, the assertion needs a nonzero-vector assumption: the singleton set containing the zero vector is mutually orthogonal but is linearly dependent. For the linear independence of nonzero orthogonal vectors, suppose

\sum_{i = 1}^{k} α_{i} q_{i} = 0

. Taking the inner product with

q_{j}

gives

0 = \sum_{i} α_{i} ⟨ q_{i}, q_{j} ⟩ = α_{j} ∥ q_{j} ∥^{2} .

Since

q_{j} \neq = 0

, positive definiteness gives

∥ q_{j} ∥^{2} > 0

, hence

α_{j} = 0

. This holds for every

j

, proving linear independence under the necessary assumption.

b

Solution

The Gram-Schmidt process constructs the vectors in order:

v_{j} = x_{j} - \sum_{i < j} ⟨ q_{i}, x_{j} ⟩ q_{i}, q_{j} = \frac{v _{j}}{∥ v _{j} ∥}, j = 1, \dots, k .

The empty sum at

j = 1

is zero. Each subtraction removes the projection onto one previous unit vector, so

v_{j}

is orthogonal to their span. Linear independence of the inputs ensures

v_{j} \neq = 0

in exact arithmetic, and normalization gives unit length.

In floating-point arithmetic, subtracting nearly equal projections can amplify roundoff and cause loss of orthogonality, especially for nearly dependent columns. Modified Gram-Schmidt, reorthogonalization, or Householder QR factorization can improve numerical behaviour; no implementation can remove the underlying sensitivity of nearly dependent input data.

c

Solution

In the column convention used for QR factorization, an

m \times k

real matrix has orthonormal columns when

Q^{T} Q = I_{k}

. This says that each column has unit norm and distinct columns have zero inner product. If

Q

is square, then

Q^{T} Q = I

provides a left inverse; a square matrix with a left inverse is invertible, so $Q^{- 1} = Q^{T}$ , and also

Q Q^{T} = I

. Such a square matrix is an orthogonal matrix. A rectangular matrix with orthonormal columns generally has no two-sided inverse.

d

Solution

The first two columns are already orthogonal and have norms 15 and 5. Their normalized versions are

q_{1} = (3, 4, 0, 0)^{T} /5

and

q_{2} = (0, 0, 4, - 3)^{T} /5

. Their inner products with the third column are 10 and 5. Subtracting these projections leaves

(20, - 15, 0, 0)^{T}

, whose norm is 25. Thus an economy-size QR factorization is

Q = \frac{1}{5} 3400 004 - 3 4 - 3 00, R = 150005010525 .

Direct multiplication gives

Q^{T} Q = I_{3}

and

QR = A

. If a full square

Q

is required, append

q_{4} = (0, 0, 3, 4)^{T} /5

and append a zero fourth row to

R

; the product is unchanged and the completed

Q

is an orthogonal matrix.

5

a

Solution

An elementary matrix acts on rows by left multiplication. In the stated order, the three matrices are

E_{s} = 1000010000300001, E_{a} = 1000 010 - 3 00100001, E_{p} = 0001010000101000 .

The first scales row 3, the second adds

- 3

times row 2 to row 4, and the third swaps rows 1 and 4. Right multiplication would instead perform column operations.

b

Solution

Undo each elementary row operation: divide row 3 by 3, add 3 times row 2 to row 4, and repeat the same swap. Hence

E_{s}^{- 1} = 10000100 00 1/3 0 0001, E_{a}^{- 1} = 1000010300100001, E_{p}^{- 1} = E_{p} .

Multiplying each inverse by its original matrix gives the identity matrix.

c

Solution

First add row 1 to rows 2 and 3. This is the product of two elementary matrices, written compactly as

E_{1} = 1110010000100001, E_{1} A = 1000 - 1 0 - 1 - 2 001 - 1 1222 .

Swap rows 2 and 4 with

P

, then subtract half of the new row 2 from row 3 with

E_{2}

P = 1000000100100100, E_{2} = 1000 01 - 1/2 0 00100001 .

This gives the upper triangular matrix

U = E_{2} P E_{1} A = 1000 - 1 - 2 00 0 - 1 3/2 0 1212 .

(3)

Because

P^{- 1} = P

, rearranging yields the convention $A = P LU$ , where

L = P E_{1}^{- 1} P E_{2}^{- 1} = 10 - 1 - 1 01 1/2 0 00100001 .

(4)

The conjugation by

P

moves the earlier elimination multipliers to the appropriate rows. Ignoring this permutation when forming

L

would give an incorrect PLU factorization. Here the same permutation is its own inverse, so

P A = LU

also holds.

d

Solution

The determinant of the unit lower triangular matrix

L

is 1. There is one row swap, so

det P = - 1

, and the upper triangular matrix has determinant

1 \cdot (- 2) \cdot (3/2) \cdot 2 = - 6

. Therefore

det A = det P det L det U = 6.

6

a

Solution

For an

m \times n

matrix, its row space is the span of its rows, a subspace of

R^{n}

; its column space is the span of its columns, a subspace of

R^{m}

. Its null space is

ker A = {x \in R^{n} : A x = 0}

. The rank of a matrix is the dimension of its column space, equal to the dimension of its row space. The rank-nullity theorem gives

dim ker A = n - rank A

b

Solution

Let the original rows be

r_{1}, \dots, r_{5}

. Begin with rows

r_{2}

r_{3} - r_{2}

and

r_{4}

(1, 1, 0, 0), (0, 1, 1, 0), (0, 0, 1, 1) .

Subtract the third from the second, then subtract that new second row from the first. The resulting rows are

(1, 0, 0, 1), (0, 1, 0, - 1), (0, 0, 1, 1) .

They are linearly independent because their first three coordinates form the identity matrix. All original rows lie in their span:

r_{1} = 2 r_{2} + r_{4}

and

r_{5} = r_{2} - (r_{3} - r_{2}) + r_{4}

. Thus they form a basis of the row space, and $rank A = 3$ . Equivalently, these are the nonzero rows of the reduced row echelon form, with two further zero rows.

c

Solution

The pivot columns are columns 1, 2 and 3 of the original matrix. A basis for its column space is therefore

⎩ ⎨ ⎧ 21101, 21200, 10110 ⎭ ⎬ ⎫ .

Use the original columns, rather than the columns of the row-reduced matrix: elementary row operations preserve column dependence relations, but can change the column space as a subspace of

R^{5}

d

Solution

The reduced homogeneous system is

x_{1} + x_{4} = 0

x_{2} - x_{4} = 0

x_{3} + x_{4} = 0

. Set

x_{4} = t

to obtain

ker A = span ⎩ ⎨ ⎧ - 1 1 - 1 1 ⎭ ⎬ ⎫, dim ker A = 1.

The rank-nullity theorem confirms

3 + 1 = 4

, and substitution verifies that the displayed vector is annihilated by

A

e

Solution

A particular solution is

x_{p} = (1, 0, - 1, 0)^{T}

, as direct substitution into all five equations verifies. Add any vector in the null space to obtain every solution:

x = 10 - 1 0 + t - 1 1 - 1 1, t \in R .

Conversely, the difference of any two solutions is annihilated by

A

, so there are no further solutions. This is the affine solution space of a consistent linear system.

7

a

Solution

Implication introduction assumes

ϕ

temporarily, derives

ψ

, and discharges that assumption to conclude

ϕ \to ψ

. Disjunction elimination starts from

ϕ \lor ψ

and derives the same conclusion

κ

in two separate branches, one assuming

ϕ

and the other assuming

ψ

The boxes delimit subproofs: a locally assumed formula is available inside its box but cannot be used unconditionally outside it. Discharging a box records exactly which dependency has been removed. The proofs below use a vertical bar to mark each active box.

b

Solution

Apply negation introduction separately to the two disjuncts, then conjunction introduction:

 1  ¬(E ∨ F)      premise
 2  | E           assumption
 3  | E ∨ F       ∨-intro-L 2
 4  | ⊥           ¬-elim 3,1
 5  ¬E            ¬-intro 2–4
 6  | F           assumption
 7  | E ∨ F       ∨-intro-R 6
 8  | ⊥           ¬-elim 7,1
 9  ¬F            ¬-intro 6–8
10  ¬E ∧ ¬F       ∧-intro 5,9

No assumption from either branch remains open in the conclusion apart from the original premise.

c

Solution

The derived proof by contradiction rule is

\frac{Γ , \neg ϕ ⊢ ⊥}{Γ ⊢ ϕ} RAA,

where the displayed assumption

\neg ϕ

is discharged. Replace each use by negation introduction, giving

Γ ⊢ \neg\neg ϕ

, followed by double-negation elimination, giving

Γ ⊢ ϕ

. Applying this replacement recursively removes all RAA occurrences while preserving the final conclusion and open premises. This uses the classical double-negation rule already supplied in the paper; it is not a general derivation of classical RAA from intuitionistic rules alone.

d

Solution

A derivation of the law of excluded middle using only the supplied primitive rules is

1  | ¬(A ∨ ¬A)    assumption
2  | | A          assumption
3  | | A ∨ ¬A     ∨-intro-L 2
4  | | ⊥          ¬-elim 3,1
5  | ¬A           ¬-intro 2–4
6  | A ∨ ¬A       ∨-intro-R 5
7  | ⊥            ¬-elim 6,1
8  ¬¬(A ∨ ¬A)     ¬-intro 1–7
9  A ∨ ¬A         ¬¬-elim 8

Both boxes have been discharged, so the final formula has no undischarged assumptions.

e

i

Solution

Split on the law of excluded middle for

A

, then use disjunction elimination:

 1  D ∧ E          premise
 2  (A ∧ D) → B    premise
 3  (¬A ∧ E) → B   premise
 4  D              ∧-elim-L 1
 5  E              ∧-elim-R 1
 6  A ∨ ¬A         excluded middle
 7  | A            assumption
 8  | A ∧ D        ∧-intro 7,4
 9  | B            →-elim 2,8
10  | ¬A           assumption
11  | ¬A ∧ E       ∧-intro 10,5
12  | B            →-elim 3,11
13  B              ∨-elim 6,7–9,10–12

The two occurrences of

B

have identical type and depend only on the corresponding temporary branch assumption and the original premises.

ii

Solution

Now derive the needed

D

E

inside its respective subproof:

 1  A → D          premise
 2  ¬A → E         premise
 3  (A ∧ D) → B    premise
 4  (¬A ∧ E) → B   premise
 5  A ∨ ¬A         excluded middle
 6  | A            assumption
 7  | D            →-elim 1,6
 8  | A ∧ D        ∧-intro 6,7
 9  | B            →-elim 3,8
10  | ¬A           assumption
11  | E            →-elim 2,10
12  | ¬A ∧ E       ∧-intro 10,11
13  | B            →-elim 4,12
14  B              ∨-elim 5,6–9,10–13

Implication elimination supplies the branch-specific premise before conjunction introduction packages it for the final implication.

8

a

Solution

In a finite domain, an existential quantifier says that at least one candidate satisfies

ϕ

. Reason with a fresh name

v

for such an unspecified witness. If the same conclusion

κ

follows using only

ϕ (v)

and the original premises, without depending on which candidate

v

names, then

κ

follows from the existential premise itself.

This is exactly existential elimination in boxed form: the sequent

Γ, ϕ (v) ⊢ κ

is the branch inside the box. The eigenvariable

v

must not occur free in the original undischarged context or in the exported conclusion

κ

. Otherwise the proof could smuggle in information about a specially chosen individual or export a fact about a witness whose name has just left scope. Freshness does not mean that the domain contains an additional object; it means that its temporary name carries no other assumptions.

b

Solution

A uniform witness can serve every particular input. Two natural deduction proofs differ in whether universal introduction happens outside or inside the existential witness box.

Proof 1:
1  ∃y ∀x R(x,y)      premise
2  | ∀x R(x,b)       assumption, b fresh
3  | R(a,b)          ∀-elim 2, with a arbitrary
4  | ∃y R(a,y)       ∃-intro 3
5  ∃y R(a,y)         ∃-elim 1,2–4
6  ∀x ∃y R(x,y)      ∀-intro 5

Proof 2:
1  ∃y ∀x R(x,y)      premise
2  | ∀x R(x,b)       assumption, b fresh
3  | R(a,b)          ∀-elim 2, with a arbitrary
4  | ∃y R(a,y)       ∃-intro 3
5  | ∀x ∃y R(x,y)    ∀-intro 4
6  ∀x ∃y R(x,y)      ∃-elim 1,2–5

In both proofs

a

is absent from the original premise. In the second it is also absent from the witness assumption, whose

x

is bound; universal generalization is therefore legal inside that box. The exported conclusions contain no free

b

The converse is not valid. On the domain

{0, 1}

, interpret

R (x, y)

x = y

. For each

x

, choose

y = x

, so

\forall x \exists y R (x, y)

holds. Neither single choice of

y

equals both 0 and 1, so

\exists y \forall x R (x, y)

fails. This is the distinction between a pointwise witness and a uniform witness.

c

Solution