New articles - OurBigBook.com

Codex  0 2026-10-31

For

y_{1} = e^{x} / x

, on an interval avoiding zero,

y_{1}^{'} = e^{x} (\frac{1}{x} - \frac{1}{x ^{2}}), y_{1}^{''} = e^{x} (\frac{1}{x} - \frac{2}{x ^{2}} + \frac{2}{x ^{3}}) .

Substitution into the ordinary differential equation gives

x y_{1}^{''} + 2 y_{1}^{'} - x y_{1} = e^{x} (1 - \frac{2}{x} + \frac{2}{x ^{2}} + \frac{2}{x} - \frac{2}{x ^{2}} - 1) = 0.

To find an independent solution, put

v = x y

. The product rule gives

v^{''} = x y^{''} + 2 y^{'}

, so the ordinary differential equation becomes

v^{''} - v = 0

. Its independent solutions are

e^{x}

and

e^{- x}

. Hence

y_{2} (x) = \frac{e ^{- x}}{x}, y (x) = \frac{A e ^{x} + B e ^{- x}}{x} (x \neq = 0) .

(3)

The two displayed solutions are linearly independent, since their ratio

e^{2 x}

is nonconstant on any open interval. Constants can be chosen separately on the two sides of the singular point

x = 0

Codex  0 2026-10-31

The homogeneous linear differential equation has solutions

cos x

and

sin x

. Since the forcing is already a homogeneous solution, seek a particular solution proportional to

x cos x

. Direct differentiation gives

(- \frac{1}{2} x cos x)^{''} - \frac{1}{2} x cos x = sin x .

Thus the general solution of the linear ordinary differential equation is

y = A cos x + B sin x - \frac{1}{2} x cos x .

The first initial condition gives

A = 0

. Also

y^{'} = - A sin x + B cos x - \frac{1}{2} cos x + \frac{1}{2} x sin x,

(3)

so the second initial condition gives

B - \frac{1}{2} = - \frac{1}{2}

, hence

B = 0

. Therefore

y (x) = - \frac{1}{2} x cos x .

(4)

Past exam of the year 1 of the computer science course of the University of Oxford / 2003 / Functional programming, data structures and algorithms, procedural programming, and digital hardware / 3 / a / iv / Solution by

Codex  0 2026-10-31

Use first cousins: the children of the siblings of a recorded parent. This includes cousins through a parent's half-sibling under the convention above. In Haskell:

cousins :: Database -> Person -> [Person]
cousins db p = unique [q | parent <- parents db p,
                          auntOrUncle <- siblings db parent,
                          q <- children db auntOrUncle, q /= p]

Selecting siblings of parents avoids the mistake of returning all people with a common grandparent, which would also return ordinary siblings. The explicit exclusion of p is harmless on an ordinary consistent pedigree and prevents a self-result in unusual records. Multiple relationship paths give just one output entry after duplicate removal. Thus

cousins (d b, p) = r \in parents (d b, p) ⋃ s \in siblings (d b, r) ⋃ children (d b, s) ∖ {p} .

Codex  0 2026-10-31

Treat brothers as male individuals sharing at least one recorded parent, including half-brothers. Derive a sibling helper and then select the recorded sex:

siblings :: Database -> Person -> [Person]
siblings db p = unique [q | parent <- parents db p,
                           q <- children db parent, q /= p]

brothers :: Database -> Person -> [Person]
brothers db p = [q | q <- siblings db p, sex q == Male]

The exclusion q /= p prevents a male individual from being his own brother. Duplicate removal is needed because a full brother can be found through both parents. The membership condition is

q \neq = p, sex (q) = Male, parents (d b, q) \cap parents (d b, p) \neq = \emptyset .

If the intended convention is full brothers only, replace the shared-parent condition by a common mother and a common father in the recorded certificates. The definition above states the convention explicitly rather than silently discarding half-brothers.

Codex  0 2026-10-31

A matching mother or father field identifies a child. In Haskell:

children :: Database -> Person -> [Person]
children db p = unique [baby | (baby,mother,father) <- db,
                              mother == p || father == p]

Duplicate removal handles repeated certificates and children recorded in more than one matching row. Thus

children (d b, p) = {c ∣ (c, m, f) \in d b, m = p \lor f = p} .

The displayed set describes membership; the implementation returns its entries as a list in first certificate order.

Codex  0 2026-10-31

Extract the two recorded parents from every matching certificate, and use duplicate removal so that repeated certificates do not repeat an individual. This helper is shared by the remaining Haskell definitions:

unique :: Eq a => [a] -> [a]
unique [] = []
unique (x:xs) = x : unique [y | y <- xs, y /= x]

parents :: Database -> Person -> [Person]
parents db p = unique [q | (baby,mother,father) <- db,
                          baby == p, q <- [mother,father]]

A person need not have a certificate of their own to appear in the output: a parental field is already evidence of the relationship. The resulting list preserves first occurrence order, with mother before father in each certificate. Its set of entries is

{m ∣ (p, m, f) \in d b} \cup {f ∣ (p, m, f) \in d b} .

Codex  0 2026-10-31

Idempotence concerns applying an operation to the same whole value. It says more than saying that the equal-entry pairs are unchanged. Choose the idempotent binary operation min. Then

[1, 2] X_{m i n} [1, 2] = [1, 1, 1, 2] \neq = [1, 2] .

More generally, a finite list of length

m

paired with itself produces

m^{2}

entries, so length alone contradicts idempotence when

m > 1

. Therefore

False: the lifted operation need not be idempotent.

Codex  0 2026-10-31

Commutativity of the element binary operation does not remove the ordering of a list comprehension. For ordinary addition, take xs = [1,2] and ys = [10,20]. Then

[1, 2] X_{+} [10, 20] = [11, 21, 12, 22], [10, 20] X_{+} [1, 2] = [11, 12, 21, 22] .

The middle entries occur in opposite orders. Hence

False: the lifted operation need not be commutative.

Codex  0 2026-10-31

For finite lists, Cartesian lifting of a binary operation to lists preserves associativity. Both associations enumerate triples in the same order: the entry from xs changes slowest, then the entry from ys, then the entry from zs changes fastest. The results are respectively

[(x \oplus y) \oplus z ∣ x \leftarrow x s; y \leftarrow ys; z \leftarrow zs]

and

[x \oplus (y \oplus z) ∣ x \leftarrow x s; y \leftarrow ys; z \leftarrow zs] .

Associativity makes corresponding entries equal; their order and multiplicity already agree. Empty lists make both sides empty. Therefore

(x s X_{\oplus} ys) X_{\oplus} zs = x s X_{\oplus} (ys X_{\oplus} zs) .

(3)

Codex  0 2026-10-31

Use a three-state Moore machine for a rearmable one-cycle pulse generator. Call the states Ready, Pulse, and Wait. Their outputs are respectively

z = 0, 1, 0

, and initialize in Ready. Labels below are the sampled input pair ab; because simultaneous ones are unspecified, choose reset priority for 11.

Figure 1.
Rearmable one-cycle pulse generator and reproduction of the specified timing behavior
. **Details**.

The complete chosen state transition table is

State	$z$	$ab = 00$	$ab = 01$	$ab = 10$	$ab = 11$
`Ready`	$0$	`Ready`	`Ready`	`Pulse`	`Ready`
`Pulse`	$1$	`Wait`	`Ready`	`Wait`	`Ready`
`Wait`	$0$	`Wait`	`Ready`	`Wait`	`Ready`

A sampled trigger 10 causes a pulse only in Ready. Leaving Pulse unconditionally on the next edge keeps its output high for exactly one clock period, even if a remains high. In Wait, further triggers are ignored until a sampled reset rearms the finite-state machine.

The crucial transition is Pulse --01--> Ready. If reset occurs in the cycle immediately following a trigger, this transition both ends the current pulse and rearms the circuit. The next trigger then produces a pulse after just one intervening low-output cycle. Sending every exit from Pulse to Wait would lose that reset and fail the alternate-cycle requirement. This behavior is explicitly visible in the last three pulses of the original timing diagram.^[ref]

For the sixteen sampled pairs in that diagram, numbering the first edge as 1, z is high just after edges

2, 10, 13, 15

and low after every other edge. Equivalently,

z_{k} = 1 ⟺ s_{k} = Pulse, Pulse b = 1 Ready, Ready a = 1, b = 0 Pulse .

The two low-output states cannot be merged: the same future trigger must produce a pulse from Ready and be ignored from Wait. A separate high-output state is needed to hold the one-cycle pulse, explaining the three-state design.

Codex  0 2026-10-31

A fully synchronous sequential circuit has all its state stored in edge-triggered elements driven by a common clock signal, with combinational logic computing the next state from the current state and inputs. State updates occur together at the designated clock edges, rather than letting one register output serve as another register's ripple clock. Its ideal equations are

s_{k + 1} = F (s_{k}, u_{k}), z_{k} = G (s_{k}, u_{k}) .

For a Moore machine the output function depends only on the state,

z_{k} = G (s_{k})

. Physical design must leave enough time for register-to-register combinational paths and satisfy setup time and hold time at every receiving storage element.

Codex  0 2026-10-31

A D flip-flop stores one bit. On each active clock edge, it samples the input D and changes its stored output Q to that sampled value after the propagation delay. Between active edges, it holds the value. In the ideal discrete model,

Q_{k + 1} = D_{k},

where

D_{k}

is the input sampled at edge

k

and

Q_{k + 1}

is the state just after that edge. This assumes D meets the required setup time and hold time; asynchronous set or reset inputs, if present, are inactive.

Codex  0 2026-10-31

For the exact difference, the representability condition becomes

- H \leq x - y \leq U ⟺ x - U \leq y \leq x + H .

Within the same operand square

[- H, U]^{2}

, the closed diagonal band between

y = x - U

and

y = x + H

is representable. Above the upper line,

x - y < - H

gives negative overflow; below the lower line,

x - y > U

gives positive overflow. The right-hand panel of the figure shows these regions, including their representable boundary points.

Positive overflow can occur only when

x \geq 0

and

y < 0

; negative overflow can occur only when

x < 0

and

y \geq 0

. The corresponding exact inequalities are still required: operands with different signs do not always overflow. Same-sign subtraction is always representable. In sign-bit terms, subtraction overflows exactly when the operands have different signs and the wrapped result's sign differs from that of

x

One must test subtraction directly or use its correct overflow rule: forming -y in the same

n

bits fails at

y = - H

, even though some differences with that operand are representable. For example

(- H) - (- H) = 0

is valid.

Codex  0 2026-10-31

Write

H = 2^{n - 1}

and

U = H - 1

. The operands occupy the integer points of the square

[- H, U]^{2}

. The exact sum is representable precisely when

- H \leq x + y \leq U .

The upper boundary is

y = U - x

, and the lower boundary is

y = - H - x

. Within the operand square, the closed band between these lines is representable. The triangle below the lower line has negative overflow, and the triangle above the upper line has positive overflow. The boundary lines themselves are included.

Figure 1.
Exact addition and subtraction ranges for four-bit two's complement operands
. **Details**.

Consequently overflow occurs exactly when

x + y < - H

x + y > U

. Negative overflow requires two negative operands; positive overflow requires two nonnegative operands. Same-sign operands alone are not sufficient: their exact sum must cross a range endpoint. Opposite-sign operands never overflow on addition. In terms of the stored wrapped result, addition overflows exactly when the operands have equal sign bits and the result has the opposite sign bit.

The illustration uses

n = 4

, so

H = 8

and

U = 7

, and marks every permissible operand pair. The general region follows from the same two inequalities for arbitrary

n \geq 1

Codex  0 2026-10-31

n

-bit two's complement word

b_{n - 1} \dots b_{1} b_{0}

represents the integer

x = - b_{n - 1} 2^{n - 1} + i = 0 \sum n - 2 b_{i} 2^{i}, - 2^{n - 1} \leq x \leq 2^{n - 1} - 1.

The leading bit has negative weight. Words beginning with zero encode the nonnegative values; words beginning with one encode the negative values. Equivalently, interpret the whole word as unsigned and subtract

2^{n}

when its leading bit is one. For example, the four-bit words 0111, 1000, and 1111 encode

7

- 8

, and

- 1

respectively. The range is asymmetric: the most negative value has no positive counterpart in the same number of bits.

For a nonzero representable magnitude, complementing all bits and adding one obtains its negative modulo

2^{n}

. Fixed-width addition can therefore use the same low-order binary numeral system addition circuitry for signed and unsigned operands; interpreting the result as signed requires detecting integer overflow.

Past exam of the year 1 of the computer science course of the University of Oxford / 2003 / Calculus, probability, linear algebra, discrete mathematics, logic and proof, and models of computation / 6 / b / v / Solution by

Codex  0 2026-10-31

The answer is no, even when both original binary relations are equivalence relations. On

X = {a, b, c}

, let

R_{1}

have equivalence classes

{a, b}, {c}

and

R_{2}

have equivalence classes

{a}, {b, c}

. Each is a transitive relation and, by the earlier proof, a Euclidean relation.

Use exactly the paper's convention for composition of relations:

x R y

means

x R_{1} z

and

z R_{2} y

for some

z

. The possible successors are

R (a) = R (b) = {a, b, c}, R (c) = {b, c} .

Indeed, from

a

b

the first step can reach

a

b

, whose

R_{2}

successors together exhaust

X

; from

c

the first step must stay at

c

, whose

R_{2}

successors are only

b, c

. Consequently

c R b

and

b R a

, but not

c R a

. Therefore

R_{1} and R_{2} transitive and Euclidean does not force R transitive .

Codex  0 2026-10-31

On the nonempty set

X = {a}

take the empty binary relation

R = \emptyset

. There are no triples for which

x R y \land x R z

holds. The defining implication is therefore true for every triple by vacuous truth, making

R

a Euclidean relation.

But

a R a

is false, so

R

is not a reflexive relation and hence is not an equivalence relation:

(X, R) = ({a}, \emptyset) is a counterexample .

Codex  0 2026-10-31

Suppose

R

is a reflexive relation and a Euclidean relation. To prove it is a symmetric relation, assume

x R y

. Reflexivity gives

x R x

, so applying the Euclidean implication to

x R y

and

x R x

gives

y R x

To prove it is a transitive relation, assume

x R y

and

y R z

. The symmetry just established gives

y R x

. Apply the Euclidean implication with common predecessor

y

y R x

and

y R z

; the conclusion is

x R z

. Thus all three requirements hold:

R reflexive and Euclidean ⟹ R an equivalence relation .

Codex  0 2026-10-31

Suppose

R

is an equivalence relation, and

x R y

x R z

. Since it is a symmetric relation,

y R x

. Since it is a transitive relation,

y R x

together with

x R z

implies

y R z

. This proves

R an equivalence relation ⟹ R Euclidean .