A short interrupt handler should acknowledge the detector and count work; a timed finite-state machine should generate the flashes. A Boolean “someone arrived” variable cannot preserve several queued detections. This is an interrupt-driven pulse sequencer. Initialise the light off, the pending-event counter to zero and the sequencer to
IDLE before enabling interrupts.In the following pseudocode, interrupt acknowledgement uses the source-specified operation of writing zero. The atomic operation and timer calls name abstract services, not undocumented device registers of a particular microcontroller.
eye_handler():
if EYE_DETECTED != 0:
EYE_DETECTED = 0
pending = pending + 1
try_take_event():
briefly mask the detector interrupt
if pending == 0: taken = false
else: pending = pending - 1; taken = true
restore the previous interrupt mask
return taken
service(now):
if state == ON and elapsed(now, started) >= one_second:
LIGHT = 0
state = GAP
started = now
if state == GAP and elapsed(now, started) >= one_second:
state = IDLE
if state == IDLE and try_take_event():
LIGHT = 1
state = ON
started = nowThe main program repeatedly handles a new event or the next timer deadline and calls
service. The ON state lasts one second; every completed flash enters GAP, even if the queue is empty at that instant. An arrival during that gap must wait for it to expire. Otherwise turning the light off and immediately treating the device as idle could allow a new flash too soon. Once a gap has expired, a queued event starts a new flash; if no work is pending the device remains idle. Removing a pending event only when a flash starts gives one completed flash per consumed event.An interrupt can arrive during the main program's decrement. Without a critical section, its increment can be overwritten by a race condition. Merely declaring the counter
volatile, as in volatile-qualified objects in C, does not make the decrement an atomic operation. Short interrupt masking, or an appropriate atomic operation, protects it; interrupts must remain enabled during the one-second intervals so that detections continue to be recorded.A calibrated busy-wait loop is simple, but occupies the CPU and its duration depends on instruction timing, compiler transformations and time spent in interrupts. Polling a hardware timer avoids calibration dependence but still consumes CPU while polling. A timer interrupt or timer comparison deadline permits useful work or safe sleeping between transitions and is preferable for precise timing. If sleeping, the test for queued work and entry into sleep must avoid a lost wake-up. By the modulo-counter elapsed-time identity, a wrapping digital counter is usable if elapsed-time subtraction is unsigned and the real observation interval is less than its modulus; a wide enough counter or suitable bounded intervals make this explicit. Software dispatch adds bounded latency, so the specification is achieved to timer/interrupt-service resolution; stricter physical pulse-width requirements call for hardware output comparison or a suitably prioritised timer handler.
Finally, the device register is only a single-bit event latch. Two physical detections before acknowledgement may coalesce, so no software can recover their multiplicity from that bit alone. The event counter must also have enough capacity for the allowed backlog; indefinitely many arrivals faster than one flash every two seconds cannot be guaranteed with finite storage. These are explicit hardware/rate assumptions, not missing input files. Keeping the handler short minimises the rearming interval but cannot abolish those limitations.
Use four working processor registers by packing the growing quotient into the vacated low bits of the shifting dividend. The following is A32 assembly language with conditional execution, an allowed instance of the question's general 32-bit Reduced instruction set computer. It is not restricted to the sixteen-bit encodings in the supplied Thumb instruction set table. On entry
r0 is the dividend and r1 the positive divisor; r2 becomes the high remainder machine word and r3 counts iterations. The quotient is returned in r0 and the ordinary remainder remains in r2.mov r2, #0
mov r3, #32
loop:
adds r0, r0, r0
adcs r2, r2, r2
cmp r2, r1
subcs r2, r2, r1
adc r0, r0, #0
subs r3, r3, #1
bne loop
bx lrHere
subcs means conditional sub when arithmetic carry is set, without the flag-setting suffix. adc also preserves flags. Consequently the arithmetic carry from cmp survives until it is inserted as the next quotient bit. The loop has seven instructions, one of them conditional, and no data-dependent branch. Its sole branch is the backwards loop branch, taken 31 times. It uses no separate quotient processor register, zero processor register, temporary comparison processor register or saved arithmetic carry processor register. A Thumb instruction set rendering using conditional execution would need an explicit conditional-execution encoding such as it cs; that is an additional encoded instruction, not an unexplained free operation.The packed restoring division loop invariant relates it to the displayed algorithm. Specifically, let , let retain its original mathematical value, and let be the number of completed iterations. Define the processed prefix , its quotient and remainder . The processor register loop invariant isThe two terms in the low machine word occupy disjoint bit positions. Its next outgoing arithmetic carry is therefore the next original dividend bit, not a quotient bit.
adds shifts the low machine word; adcs doubles the high remainder and incorporates that dividend bit. cmp decides whether this trial remainder is at least the divisor; subcs performs the conditional subtraction, and adc appends its decision to the shifted quotient. This is exactly the doubling, compare/subtract and quotient-bit update, with the counter maintained separately. Before processing bit , the trial remainder is at most , so the high-word addition does not require a hidden 33rd remainder bit for this 32-bit dividend problem. After 32 iterations the residual dividend portion is zero, giving the stated outputs.There is a printed source error in the auxiliary bound. At the initial state, choosing valid inputs makes the printed strict inequality false. The algorithm instead preserves for its unpacked 64-bit variable, together with its printed equality loop invariant. Doubling and subtracting when necessary preserves that corrected bound. At termination the equality becomes ; since is then divisible by , it gives . This source error does not invalidate the algorithm or the packed implementation. The figure is mathematical pseudocode: its
2^32 denotes exponentiation, rather than C's XOR operator.The displayed A32 routine assembled successfully with Clang and was disassembled to check the conditional and non-flag-setting forms. Its carry flag model was checked exhaustively at an eight-bit machine word size and against boundary and randomized 32-bit divisions. No native ARM architecture family execution is claimed.
A subtract with carry instruction consumes the no-borrow carry flag. Its arithmetic is . Hence a low-limb
subs followed immediately by a high-limb sbcs propagates exactly the low subtraction's borrow.subs r0, r0, r2
sbcs r1, r1, r3It uses an ordinary 32-bit adder by complementing every bit of the subtrahend and adding the incoming arithmetic carry. For , the unreduced adder sum isIf this is , rearrangement gives . Thus both the result and outgoing no-borrow flag have the required meanings. With incoming arithmetic carry one this becomes ordinary subtraction.[ref]
Thumb 16-bit instruction set quick reference by Arm. Page 1, Add with carry and Subtract with carry: subtraction subtracts NOT C-bit
Let
r1:r0 hold the first operand, high limb first, and r3:r2 the second. In assembly language the addition can be written:adds r0, r0, r2
adcs r1, r1, r3The first instruction produces the low result and its arithmetic carry; the second immediately consumes that arithmetic carry while adding the high limbs. No intervening flag-setting instruction is permitted.
For a proof, put and denote the input limbs by . If the low addition gives and arithmetic carry , then . The high addition gives and final arithmetic carry , so . Multiplying the second identity by and combining yieldsThe processor register pair is the correct result modulo , and the final arithmetic carry records overflow beyond that unsigned width. If the mathematical sum fits in 64 bits, no reduction changes it.
Put for an -bit processor register. The carry flag for addition satisfies : the result retains the low bits and records an arithmetic carry beyond them.
For the ARM architecture family subtraction convention, . Thus means no borrow, equivalently the unsigned minuend is at least the subtrahend. This flag is different from signed overflow: an arithmetic carry decision is not a test of the signed result.
Write the bit vector as , with the least significant bit. Its unsigned interpretation of a bit string is , where each . The range is the integers from through ; a leading one contributes positive weight , not a sign.
Let abbreviate , and group the three equality alternatives on the left. The proof uses the binary disjunction elimination rule twice, so no unproved three-way derived rule is needed.
| Line | Formula | Justification |
|---|---|---|
| 1 | Premise | |
| 2 | Assume for the first implication | |
| 3 | Assume for the second implication | |
| 4 | Assume with fresh witness name | |
| 5 | Universal quantifier elimination rule, 1 | |
| 6 | Assume the first outer case | |
| 7 | Assume the first inner case | |
| 8 | Equality elimination rule, 7 and 4 | |
| 9 | Negation elimination rule, 2 and 8 | |
| 10 | Logical falsity elimination rule, 9 | |
| 11 | Assume the second inner case | |
| 12 | Equality elimination rule, 11 and 4 | |
| 13 | Disjunction introduction rule, left, 12 | |
| 14 | Disjunction elimination rule, 6, 7–10 and 11–13 | |
| 15 | Assume the second outer case | |
| 16 | Equality elimination rule, 15 and 4 | |
| 17 | Disjunction introduction rule, right, 16 | |
| 18 | Disjunction elimination rule, 5, 6–14 and 15–17 | |
| 19 | Existential quantifier elimination rule, 3 and 4–18 | |
| 20 | Implication introduction rule, discharging 3–19 | |
| 21 | Implication introduction rule, discharging 2–20 |
The witness name is absent from and from every assumption remaining after line 19, so the existential elimination is legal. Each equality is used in the forward direction supplied by the printed equality rule. The three named constants need not denote distinct objects: the case proof requires only that they exhaust the domain. This is existential quantification over a finitely named domain followed by exclusion of the first case.
For readability write for the uninterpreted relation . In the first proof, introduce the universal quantifier inside the existential witness scope:
| Line | Formula | Justification |
|---|---|---|
| 1 | Premise | |
| 2 | Assume with fresh witness name | |
| 3 | Universal quantifier elimination rule, 2; choose fresh arbitrary | |
| 4 | Existential quantifier introduction rule, 3 | |
| 5 | Universal quantifier introduction rule, 4; is absent from open assumptions | |
| 6 | Existential quantifier elimination rule, 1 and 2–5 |
| Line | Formula | Justification |
|---|---|---|
| 1 | Premise; choose arbitrary and fresh for this premise | |
| 2 | Assume with fresh , also different from | |
| 3 | Universal quantifier elimination rule, 2 | |
| 4 | Existential quantifier introduction rule, 3 | |
| 5 | Existential quantifier elimination rule, 1 and 2–4 | |
| 6 | Universal quantifier introduction rule, 5 |
These are distinct proof trees: the final two rule applications are interchanged, and their freshness conditions have been checked in their respective contexts. They express the quantifier order and uniform witness principle: a single witness working for every object also supplies a witness for each object individually.
The converse is not valid. In a domain interpret as equality of its arguments. Every object has a witness, namely itself, but no one object equals both 0 and 1. The premise of the converse is true and its conclusion false. The symbol is an arbitrary binary relation here; no set-membership axioms may be imposed on it without an additional premise.
The displayed derivation is invalid, although its final conjecture is valid. Its existential-elimination step exports with the local witness name still free, violating the eigenvariable condition. Introducing an existential quantifier afterwards does not repair that earlier invalid rule application.
Move the existential quantifier introduction rule inside the witness scope:
| Line | Formula | Justification |
|---|---|---|
| 1 | Premise | |
| 2 | Premise | |
| 3 | Assume with fresh | |
| 4 | Universal quantifier elimination rule, 1 | |
| 5 | Implication elimination rule, 3 and 4 | |
| 6 | Existential quantifier introduction rule, 5 | |
| 7 | Existential quantifier elimination rule, 2 and 3–6 |
In a finite domain , a true existential premise says that at least one satisfies . The subproof treats its witness as an unknown object named , derives without relying on which object was chosen, and can therefore be applied to the actual witness. Thus follows whenever the existential premise is true. This argument does not require knowing the domain's size or selecting a particular named element in advance.
The existential quantifier elimination rule in sequent form records the same assumption discharge: a derivation of yields . The natural-deduction box represents the temporary witness assumption that the sequent rule replaces by the existential premise.
The eigenvariable condition requires that have no free occurrence in the other undischarged assumptions, the existential premise or the exported conclusion . Bound occurrences can be renamed harmlessly. This freshness condition keeps from denoting a previously special object and prevents witness escape. Without it, one could export from , falsely asserting that an arbitrarily named object has the witness property. A two-element domain with only one element satisfying supplies an immediate counterexample.
Write for . The following derives Peirce's law directly from the printed primitive rules, including double-negation elimination:
| Line | Formula | Justification |
|---|---|---|
| 1 | Assume for the final implication | |
| 2 | Assume locally | |
| 3 | Assume inside the scope of 2 | |
| 4 | Negation elimination rule, 2 and 3 | |
| 5 | Logical falsity elimination rule, 4 | |
| 6 | Implication introduction rule, discharging 3–5 | |
| 7 | Implication elimination rule, 1 and 6 | |
| 8 | Negation elimination rule, 2 and 7 | |
| 9 | Negation introduction rule, discharging 2–8 | |
| 10 | Double-negation elimination, 9 | |
| 11 | Implication introduction rule, discharging 1–10 |
The supplied double-negation elimination rule provides the classical step needed to recover each positive component:
| Line | Formula | Justification |
|---|---|---|
| 1 | Premise | |
| 2 | Assume locally | |
| 3 | Disjunction introduction rule, left, 2 | |
| 4 | Negation elimination rule, 1 and 3 | |
| 5 | Negation introduction rule, discharging 2–4 | |
| 6 | Double-negation elimination, 5 | |
| 7 | Assume locally | |
| 8 | Disjunction introduction rule, right, 7 | |
| 9 | Negation elimination rule, 1 and 8 | |
| 10 | Negation introduction rule, discharging 7–9 | |
| 11 | Double-negation elimination, 10 | |
| 12 | Conjunction introduction rule, 6 and 11 |
Both local negated assumptions have been discharged. The proof establishes the positive conjunction without assuming an unproved derived version of De Morgan's laws.
Assume the conjunction and obtain a contradiction in each of the two cases supplied by the premise:
| Line | Formula | Justification |
|---|---|---|
| 1 | Premise | |
| 2 | Assume locally | |
| 3 | Conjunction elimination rule, left, 2 | |
| 4 | Conjunction elimination rule, right, 2 | |
| 5 | Assume first case | |
| 6 | Negation elimination rule, 3 and 5 | |
| 7 | Assume second case | |
| 8 | Negation elimination rule, 4 and 7 | |
| 9 | Disjunction elimination rule, 1, 5–6 and 7–8 | |
| 10 | Negation introduction rule, discharging 2–9 |
Derive each negated component in its own subproof, then combine them. Assumption lines below begin local scopes; the listed discharge ranges close those scopes.
| Line | Formula | Justification |
|---|---|---|
| 1 | Premise | |
| 2 | Assume locally | |
| 3 | Disjunction introduction rule, left, 2 | |
| 4 | Negation elimination rule, 1 and 3 | |
| 5 | Negation introduction rule, discharging 2–4 | |
| 6 | Assume locally | |
| 7 | Disjunction introduction rule, right, 6 | |
| 8 | Negation elimination rule, 1 and 7 | |
| 9 | Negation introduction rule, discharging 6–8 | |
| 10 | Conjunction introduction rule, 5 and 9 |
Only the original premise remains open. No classical principle is needed for this direction of De Morgan's laws.
- The implication introduction rule assumes locally, derives under that assumption, then concludes while discharging the temporary assumption.
- The disjunction elimination rule uses and two local cases: one derives a common conclusion from , and the other derives that same from . It concludes and discharges both case assumptions.
- The negation introduction rule assumes locally and derives logical falsity. Discharging that assumption gives .
The boxes delimit a subproof and identify the lifetime of its temporary assumptions. A result depending on a boxed assumption is available inside that box and its nested boxes; it cannot simply be exported outside. The enclosing rule specifies what may be exported and which assumptions are discharged. Other premises on which the derivation depends remain undischarged. This assumption discharge discipline distinguishes a conditional argument from an unconditional proof.
There are unlisted articles, also show them or only show them.