Five inspection stations each send one Boolean flag: 1 means a fault was detected; 0 means no fault was detected. The panel should light exactly when at least one flag is 1. This is a specification about every possible input, not just the flags currently observed. It does not promise that the stations themselves detected every real fault.
Build the panel using only two-input OR gates. Such a gate has outputs 0, 1, 1, 1 on input pairs (0,0), (0,1), (1,0), (1,1), respectively. A wire copies a value; it does not perform another OR operation. A circuit here is a finite directed network with no directed cycles, so its dependencies can be evaluated in order.
Write an output prediction for flags (0,1,0,0,1). Then change the question: how many gates are used, and how many gate stages lie on the longest dependency path? These two counts need not agree.
Predict
A balanced tree is convenient when the number of leaves is a power of two. For five flags, use eight leaves and put a constant zero in each unused position. Predict whether padding changes the panel’s meaning. Check the identity x∨0=x, where ∨ denotes OR, for both possible values of x.
We count the gates in the specified network, even when an optimizer could remove a gate connected to a constant. Work W means the number of distinct gates evaluated once. Depth D means the largest number of gates on an input-to-output path. Inputs and constants have depth zero; a gate’s depth is one plus the largest depth of its predecessors.
Under an ideal model with enough gates operating concurrently, unit gate delay, and ignored wire delay, depth describes the number of required stages. Work remains a separate resource count. Actual electronic timing also depends on wiring, load and gate technology; this lesson does not estimate those quantities.
Experiment
Cover the output labels and calculate the tree from left to right. At each gate, name the set of real stations it summarizes. Then change only the second input from 1 to 0 and identify which intermediate values change. The last real flag still keeps the final alarm on.
Rectangles are gates; lines are wires. Horizontal placement shows dependency stages, not measured elapsed time. Padding is explicitly labeled.
Stage
Values in top-to-bottom order
Gates at this stage
Inputs
0, 1, 0, 0, 1, 0, 0, 0
0
First pairs
1, 0, 1, 0
4
Second pairs
1, 1
2
Root
1
1
This network uses W=4+2+1=7 gates and D=3 stages. A left-to-right chain on the five real flags instead uses four gates with depth four. The balanced padded tree buys smaller depth here by using more gates. A carefully pruned balanced tree can also reduce work; do not silently count that different network when describing the diagram.
Understand
The right induction claim describes every subtree, not just the root: its output is 1 if and only if at least one of its leaves is 1. At a leaf, the statement is the definition of its value. At an internal node, the OR truth table says its output is 1 exactly when at least one child output is 1. The induction hypotheses translate those two possibilities into a one-valued leaf in either child subtree. Their union is precisely the parent’s leaves. This proves both directions, including the no-false-alarm direction when all leaves are zero. Identity padding then removes the artificial leaves from the specification.
For m=2ᵏ leaves, the specified balanced construction obeys
W(1)=0; W(m)=2W(m/2)+1; hence W(m)=m−1.
D(1)=0; D(m)=D(m/2)+1; hence D(m)=k.
The work recurrence adds the gates in both subtrees. The depth recurrence takes their maximum, because independent branches can operate concurrently in the ideal model. Adding both depths would describe a sequential schedule, not the circuit’s longest dependency path.
For arbitrary n≥1 real flags, choose m=2^ceil(log₂ n). Then D=ceil(log₂ n) and W=m−1. When n>1, minimality gives m/2<n≤m, so n−1≤W<2n−1. For n=1 there is just a wire: work and depth are both zero. An empty collection can be assigned the constant-zero alarm separately; log₂ 0 is not used.
Why not claim one stage for all n by drawing a single giant OR? That would permit unbounded fan-in, a different gate model. With at most two incoming wires per gate, a depth-d output can depend on at most 2ᵈ distinct input variables. At depth zero it depends on at most one. Each further gate combines at most two predecessor dependency sets, so their union has at most twice that bound. Shared subcircuits do not increase a union’s size beyond its sum. Since OR depends essentially on each flag—set all others to zero to witness this—any such circuit needs depth at least ceil(log₂ n). The balanced construction attains that depth bound, although this argument says nothing about its work optimality.
Apply
Design a panel for six fault flags. State its specification before drawing gates. First use the padded balanced construction; then produce an unpadded tree by removing identity operations. Give a general reason the edited circuit remains correct, not just one successful trace. Compare it with a sequential chain and identify the longest path in each drawing.
Compare a worked design after making your own
Pad six leaves to eight with two zeros. The original network has seven gates and depth three. The pair of padded zeros can be replaced by a constant zero, and its parent’s OR with zero can be replaced by a wire. This leaves five gates and depth three: a four-flag subtree and a two-flag subtree feed the root. The chain also has five gates but depth five. Each removal preserves output by the OR identity. For all-zero real inputs every design outputs zero; a one-valued real input propagates through OR ancestors to the root.
Now suppose a flag means healthy, and an alarm means at least one device is unhealthy. Predict what happens if someone uses an AND tree padded with zeros and negates its root. Diagnose the failure on an all-healthy input before choosing a replacement identity. This semantic change is part of the problem; recycling the previous padding without checking meaning creates a false alarm.
Continue
Use the written tasks to prove a changed circuit, inspect a shared computation, and compare a multi-output design. A circuit drawing, one input trace and a general specification proof are different evidence. Include all three when explaining your design, then report cost under the declared gate and scheduling assumptions.
For each answer, ask: which gates are actually present, which intermediate results are reused, and which path forces the depth? A correct output does not by itself certify an efficient implementation. Conversely, a shallow network is not useful until its output is proved to satisfy the required condition for every allowed input.
Apply · explain · revise
Practice and reasoning
Drafts save locally as you type. Reveal worked solutions when useful; the site remembers that exposure. Automatic matches check the requested answer, while written arguments require review against the rubric.
Seven flags, in order, are (0,0,1,0,0,1,0). Append zero flags to reach the next power of two and combine adjacent pairs with two-input OR gates at each level. Record every level, total gates and depth. Now delete unnecessary zero-padding logic to obtain a tree with seven real leaves: state its gate count and achievable depth, and explain why the two correct circuits need not have equal work.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
For every n≥1, let m be the smallest power of two at least n. Define a balanced OR circuit on m leaves, with the last m−n leaves fixed to zero. Prove for all assignments that the output is 1 exactly when at least one of the n real inputs is 1. Derive the unpruned work W and depth D, handle n=1, and bound the padding overhead relative to n.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Allow arbitrary Boolean gates with at most two incoming wires, constants, shared subcircuits and unlimited fan-out, but no cycles. Inputs have depth zero. Prove that an output of depth d can depend on at most 2ᵈ distinct input variables. Deduce a lower bound for any circuit computing OR of n independently variable inputs. Explain precisely why a single n-input OR gate does not refute the bound.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
A panel needs every prefix alarm pⱼ=x₁∨⋯∨xⱼ, for 1≤j≤n, not only the final alarm. Design A sets p₁=x₁ and pⱼ=pⱼ₋₁∨xⱼ. Design B builds a separate unpadded balanced binary tree for each prefix, using j−1 gates and depth ceil(log₂ j); it shares no gates between outputs. Prove both correct. Compare total work and maximum output depth in general and at n=6. State the resource assumptions behind any parallel advantage.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Let a=x₁∨x₂, b=a∨x₃, c=a∨x₄ and z=b∨c. Prove z is the four-input alarm. Count distinct gates and output depth when a is computed once and reused. Compare with a balanced four-leaf OR tree. A learner expands z into a formula and counts two copies of a: explain which cost has changed and why output equivalence does not settle the issue.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Each of n≥1 bits means a device is healthy when it equals 1. A panel must output an alarm exactly when at least one device is unhealthy. A proposal pads to m=2^ceil(log₂ n) leaves with zeros, ANDs the leaves in a balanced tree, then negates the root. Diagnose all n for which the padding can force an alarm. Repair the padding, prove correctness, and count two-input AND and one-input NOT gates and depth, including n=1.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Reflect and continue
Before marking this lesson complete, explain one key idea without the worked solution and identify a condition that matters. Marking complete records participation, not independent mastery.
