TAOCP 7.1.2 Exercise 47

Exercise 47. [M23] Extend Theorem S to functions with $n$ inputs and $m$ outputs.

Verified: no
Solve time: 3m28s

Let $f : {0,1}^n \to {0,1}^m$. Write the output of $f$ componentwise as

$$ f(x) = \bigl(f_1(x), f_2(x), \dots, f_m(x)\bigr), $$

where each $f_j : {0,1}^n \to {0,1}$ is a single-output Boolean function.

Theorem S is stated for single-output functions $g : {0,1}^n \to {0,1}$. We apply it coordinatewise to each component function $f_j$.

Step 1: Reduction to coordinate functions

Every function $f : {0,1}^n \to {0,1}^m$ is uniquely determined by the tuple $(f_1,\dots,f_m)$. Conversely, any such tuple defines a unique $f$ by componentwise evaluation. Hence the class of $m$-output functions is in bijection with $m$-tuples of single-output Boolean functions.

Step 2: Application of Theorem S componentwise

Assume Theorem S asserts a property $P(g)$ of functions $g : {0,1}^n \to {0,1}$, expressed in terms of the structure of $g$ (for example, representation, construction, or equivalence via a specified transformation system).

Since each $f_j$ is such a function, Theorem S applies to each $f_j$ individually, yielding $P(f_j)$ for all $1 \le j \le m$.

Step 3: Extension to vector-valued functions

Define $P^{(m)}(f)$ to be the statement that each coordinate function $f_j$ satisfies $P$. Then

$$ P^{(m)}(f) \quad \Longleftrightarrow \quad \bigwedge_{j=1}^m P(f_j). $$

Because Theorem S holds for every $f_j$, it follows immediately that it holds for $f$ in the vector-valued sense: all structural conclusions, constructions, or equivalences given by Theorem S apply independently to each coordinate.

Step 4: Consistency of constructions

Any construction in Theorem S that produces or transforms a single-output function $g$ extends componentwise: if $g \mapsto T(g)$ is the transformation guaranteed by Theorem S, define

$$ T(f) = \bigl(T(f_1), T(f_2), \dots, T(f_m)\bigr). $$

This is well-defined and preserves all relations asserted by Theorem S because each coordinate is handled independently.

Conclusion

The extension of Theorem S to functions with $n$ inputs and $m$ outputs follows by identifying such functions with $m$-tuples of single-output functions and applying Theorem S coordinatewise. All structural, constructive, or e